• German
German

Main Navigation

A6  Resource-efficient Graph Mining


kersting.jpg
Prof. Dr. Kersting, Kristian
mutzel.jpeg
Prof. Dr. Mutzel, Petra
Sohler.JPG
Prof. Dr. Sohler, Christian
Linked data and networks occur often in the context of embedded systems. Sensors, RFID-chips, cameras, etc. of products of our daily life continuously produce data and communicate with each other as well as the user. A natural representation of linked data are graphs where objects correspond to the vertices of the graph and the links to its edges. In this project, we will develop new approaches and algorithms for the classification of graphs and linked data sets under resource constraints. To this aim, randomized approaches from algorithmic theory, approaches for mining and learning with graphs (in particular graph kernels) and algorithmic engineering approaches will be combined.

Project management:

Prof. Dr. Kersting, Kristian
Prof. Dr. Mutzel, Petra
Prof. Dr. Sohler, Christian

Project members:

Droschinsky, Andre
Erdmann, Elena
Dr. Kriege, Nils
Mladenov, Martin
Morris, Christopher
Dr. Rey, Anja
Zey, Bernd

Publications:

Boekler/etal/2017a Bökler, Fritz and Ehrgott, Matthias and Morris, Christopher and Mutzel, Petra. Output-sensitive complexity of multiobjective combinatorial optimization. In Journal of Multi-Criteria Decision Analysis, Vol. 24, No. 1-2, 2017.


Kriege/etal/2017a Kriege, Nils M. and Neumann, Marion and Morris, Christopher and Kersting, Kristian and Mutzel, Petra. A Unifying View of Explicit and Implicit Feature Maps for Structured Data: Systematic Studies of Graph Kernels. In Journal of Machine Learning Research (submitted), 2017.


Kriege/Morris/2017a Kriege, Nils M. and Morris, Christopher. Recent Advances in Kernel-Based Graph Classification. In European Conference on Machine Learning (ECML), 2017.


Molina/etal/2017a Molina, Alejandro and Natarajan, Sriraam and Kersting, Kristian. Poisson Sum-Product Networks: A Deep Architecture for Tractable Multivariate Poisson Distributions. In Satinder Singh and Shaul Markovitch (editors), Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), AAAI Press, 2017.


Morris/etal/2017a Morris, Christopher and Kersting, Kristian and Mutzel, Petra. Global Weisfeiler-Lehman Graph Kernels. In CoRR, 2017.


Bauckhage/Kersting/2016a Bauckhage, Christian and Kersting, Kristian. Collective Attention on the Web. In Foundations and Trends in Web Science, Vol. 5, No. 1-2, pages 1-136, 2016.


Das/etal/2016a Das, Mayukh and Wu, Yunqing and Khot, Tushar and Kersting, Kristian and Natarajan, Sriraam. Scaling Lifted Probabilistic Inference and Learning Via Graph Databases,. In Proceedings of the SIAM International Conference on Data Mining (SDM), 2016.


Erdmann/etal/2016b Erdmann, Elena and Boczek, Karin and Koppers, Lars and von Nordheim, Gerret and Poelitz, Christian and Molina, Alejandro and Morik, Katharina and Mueller, Henrik and Rahnenfuehrer, Joerg and Kersting, Kristian. Machine Learning meets Data-Driven Journalism: Boosting International Understanding and Transparency in News Coverage. In Proceedings of the 2016 ICML Workshop on #Data4Good: Machine Learning in Social Good Applications, 2016.


Kriege/etal/2016a Nils M. Kriege and Pierre-Louis Giscard and Richard C. Wilson. On Valid Optimal Assignment Kernels and Applications to Graph Classification. In CoRR, Vol. abs/1606.01141, 2016.


Kriege/etal/2016b Nils M. Kriege and Pierre-Louis Giscard and Richard C. Wilson. On Valid Optimal Assignment Kernels and Applications to Graph Classification. In Advances in Neural Information Processing Systems (NIPS), 2016.


Mladenov/etal/2016a Mladenov, Martin and Heinrich, Danny and Kleinhans, Leonard and Gonsior, Felix and Kersting, Kristian. RELOOP: A Python-Embedded Declarative Language for Relational Optimization. In Working Notes of the First AAAI Workshop on Declarative Learning Based Programming (DeLBP), AAAI Press, 2016.


Morris/etal/2016a Morris, Christopher and Kriege, Nils M. and Kersting, Kristian and Mutzel, Petra. Faster Kernels for Graphs with Continuous Attributes via Hashing. In Francesco Bonchi and Josep Domingo-Ferrer (editors), IEEE International Conference on Data Mining (ICDM), 2016.


Neumann/Garnett/2016a Neumann, Marion and Garnett, Roman and Bauckhage, Christian and Kersting, Kristian. Propagation kernels: efficient graph kernels from propagated information. In Machine Learning, Vol. 102, No. 2, pages 209--245, 2016.


Szymanski/etal/2016a Szymanski, Piotr and Kajdanowicz, Tomasz and Kersting, Kristian. How Is a Data-Driven Approach Better than Random Choice in Label Space Division for Multi-Label Classification?. In Entropy, Vol. 18, No. 8, pages 282, 2016.


Bauckhage/etal/2015a Bauckhage, Christian and Kersting, Kristian and Hadiji, Fabian. Parameterizing the Distance Distribution of Undirected Networks. In Tom Heskes and Marina Meila (editors), Proceedings of the 31th Conference on Uncertainty in Artificial Intelligence (UAI), AUAI, 2015.


Bauckhage/etal/2015b Bauckhage, Christian and Kersting, Kristian and Hadiji, Fabian. How Viral are Viral Movies?. In Proceedings of the 9th International AAAI Conference on Web and Social Media (ICWSM), 2015.


Kriege/2015a Nils Morten Kriege. Comparing Graphs: Algorithms & Applications. Department of Computer Science, TU Dortmund, 2015.


  • Boekler/etal/2017a - Output-sensitive complexity of multiobjective combinatorial optimization
  • Kriege/etal/2017a - A Unifying View of Explicit and Implicit Feature Maps for Structured Data: Systematic Studies of Graph Kernels
  • Kriege/Morris/2017a - Recent Advances in Kernel-Based Graph Classification
  • Molina/etal/2017a - Poisson Sum-Product Networks: A Deep Architecture for Tractable Multivariate Poisson Distributions
  • Morris/etal/2017a - Global Weisfeiler-Lehman Graph Kernels
  • Bauckhage/Kersting/2016a - Collective Attention on the Web
  • Das/etal/2016a - Scaling Lifted Probabilistic Inference and Learning Via Graph Databases,
  • Erdmann/etal/2016b - Machine Learning meets Data-Driven Journalism: Boosting International Understanding and Transparency in News Coverage
  • Kriege/etal/2016a - On Valid Optimal Assignment Kernels and Applications to Graph Classification
  • Kriege/etal/2016b - On Valid Optimal Assignment Kernels and Applications to Graph Classification
  • Mladenov/etal/2016a - RELOOP: A Python-Embedded Declarative Language for Relational Optimization
  • Morris/etal/2016a - Faster Kernels for Graphs with Continuous Attributes via Hashing
  • Neumann/Garnett/2016a - Propagation kernels: efficient graph kernels from propagated information
  • Szymanski/etal/2016a - How Is a Data-Driven Approach Better than Random Choice in Label Space Division for Multi-Label Classification?
  • Bauckhage/etal/2015a - Parameterizing the Distance Distribution of Undirected Networks
  • Bauckhage/etal/2015b - How Viral are Viral Movies?
  • Kriege/2015a - Comparing Graphs: Algorithms & Applications

Final Thesis:

Bause/2017a Franka Bause. Approximation der Editierdistanz für Graphen in linearer Zeit. TU Dortmund, 2017.


Rentz/2017a Martin Rentz. Approximative Algorithmen für das Assignment-Problem mit Hilfe von hierarchischem Clustering. TU Dortmund, 2017.


Ayaz/2016a Serdar Ayaz. Approximation des Weisfeiler-Lehman-Isomorphie-Tests durch Sampling. TU Dortmund University, 2016.


Kramer/2016a Robert Kramer. Algorithmen für gerichtetes Matching in Graphen. TU Dortmund, 2016.


Osthues/2016a Christopher Osthues. Experimenteller Vergleich von Labeling-Verfahren für Graphkerne. TU Dortmund, 2016.


Stallmann/2016a Jan Stallmann. Betrachtung von Pfadkreuzungen zur Erweiterung von Random-Walk-Kernels. Faculty of Computer Science, TU Dortmund University, 2016.


Walker/2016a Walker, Marcel. Dimensionsreduktion von Merkmalsvektoren von expliziten Graphkernen. TU Dortmund University, 2016.


Wisniewski/2016a Daniel Wisniewski. Theoretische Analyse von Graphkernen. Faculty of Computer Science, TU Dortmund University, 2016.


  • Bause/2017a - Approximation der Editierdistanz für Graphen in linearer Zeit
  • Rentz/2017a - Approximative Algorithmen für das Assignment-Problem mit Hilfe von hierarchischem Clustering
  • Ayaz/2016a - Approximation des Weisfeiler-Lehman-Isomorphie-Tests durch Sampling
  • Kramer/2016a - Algorithmen für gerichtetes Matching in Graphen
  • Osthues/2016a - Experimenteller Vergleich von Labeling-Verfahren für Graphkerne
  • Stallmann/2016a - Betrachtung von Pfadkreuzungen zur Erweiterung von Random-Walk-Kernels
  • Walker/2016a - Dimensionsreduktion von Merkmalsvektoren von expliziten Graphkernen
  • Wisniewski/2016a - Theoretische Analyse von Graphkernen

Preliminary Work:

Kersting/etal/2014a Kersting, Kristian and Mladenov, Martin and Garnett, Roman and Grohe, Martin. Power Iterated Color Refinement. In Brodley, Carla and Stone, Peter (editors), Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence (AAAI-14), AAAI Press, 2014.


Kriege/etal/2014a Kriege, Nils and Neumann, Marion and Kersting, Kristian and Mutzel, Petra. Explicit versus Implicit Graph Feature Maps: A Computational Phase Transition for Walk Kernels. In Kumar, Ravi and Toivonen, Hannu (editors), Proceedings of the IEEE International Conference on Data Mining (ICDM), IEEE, 2014.


Bauckhage/etal/2013b Bauckhage, Christian and Kersting, Kristian and Rastegarpanah, Bashir. The Weibull as a Model of Shortest Path Distributions in Random Networks. In L. Adamic and L. Getoor and B. Huang and J. Leskovec and J. McAuley (editors), Working Notes of the International Workshop on Mining and Learning with Graphs, Chicago, IL, USA, 2013.


Gronemann/etal/2013a M. Gronemann and M. Jünger and P. Mutzel and N. Kriege. MolMap -- Visualizing Molecule Libraries as Topographic Maps. In Proc.\ Int. Conf. Computer Graphics Theory and Applications and International Conference on Information Visualization Theory and Applications (GRAPP & IVAPP), 2013.


Neumann/etal/2013a M. Neumann and R. Garnett and K. Kersting. Coinciding Walk Kernels: Parallel Absorbing Random Walks for Learning with Graphs and Few Labels. In Cheng Soon Ong and Tu Bao Ho (editors), Proceedings of the 5th Annual Asian Conference on Machine Learning (ACML 2013), Vol. 29, pages 357-372, 2013.


Newman/Sohler/2013a I. Newman and C. Sohler. Every Property of Hyperfinite Graphs Is Testable. In SIAM J. Comput., Vol. 42, No. 3, pages 1095-1112, 2013.


Kriege/Mutzel/2012a N. Kriege and P. Mutzel. Subgraph Matching Kernels for Attributed Graphs. In Proc. of the 29th Int. Conf. on Machine Learning (ICML), Omnipress, 2012.


Neumann/etal/2012a M. Neumann and N. Patricia and R. Garnett and K. Kersting. Efficient Graph Kernels by Randomization. In P. Flach and T. De Bie and N. Cristianini (editors), Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD 2012), Bristol, UK, Springer, 2012.


Czumaj/etal/2011a A. Czumaj and M. Monemizadeh and K. Onak and C. Sohler. Planar Graphs: Random Walks and Bipartiteness Testing. In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science, pages 423-432, 2011.


Klein/etal/2011a K. Klein and N. Kriege and P. Mutzel. CT-index: Fingerprint-based Graph Indexing Combining Cycles and Trees. In IEEE 27th Int. Conf. on Data Engineering (ICDE), pages 1115 -1126, 2011.


Czumaj/Sohler/2010a A. Czumaj and C. Sohler. Testing Expansion in Bounded-Degree Graphs. In Combinatorics, Probability & Computing, Vol. 19, No. 5-6, pages 693-709, 2010.


Czumaj/etal/2009a A. Czumaj and A. Shapira and C. Sohler. Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs. In SIAM J. Comput., Vol. 38, No. 6, pages 2499-2510, 2009.


Ljubic/etal/2006a Ljubi\'c, I. and Weiskircher, R. and Pferschy, U. and Klau, G. and Mutzel, P. and Fischetti, M.. An Algorithmic Framework for the Exact Solution of the Prize-Collecting Steiner Tree Problem. In Mathematical Programming, Vol. Series B 105, pages 427-449, 2006.