• German
German

Main Navigation

A6  Resource-efficient Graph Mining


kriege.jpg
Dr. Kriege, Nils
mutzel.jpeg
Prof. Dr. Mutzel, Petra
weichert.png
Dr. Weichert, Frank

The internet of things (IoT) has already started to generate huge amounts of data. Infrastructures, machines, vehicles, and everyday objects such as smartphones or TVs are equipped with intelligent functions that are linked to each other. These objects contain sensors, RFID chips, and cameras that continuously produce data and communicate within these cyber-physical systems (CPSs). A natural representation of a linked data set is provided by a graph, where entities are represented as vertices and their relationships are encoded by edges. Compared to the classical representation of objects as feature vectors, the graph structure additionally allows the representation of the complex relationships between these objects. Project A6 deals with the development of new methods for analysing graphs at a large scale or on a large number of graphs in resource constrained environments.

In the next phase, we would like to bring some of our results into real applications and approach CPSs. Moreover, we want to focus on feature learning techniques for graphs; i.e., our new methods are not based on a predetermined set of features anymore, but learning from the features will be part of the problem. To this end, we want to build on our results in phase 2 on efficient graph kernels and extend them to feature learning. For example, we expand the research of A6 to geometric deep learning, which is an emerging field that extends deep learning techniques for Euclidean domains to graph-structured data. In particular, we would like to apply randomised sampling techniques on problems related to graph kernels and also to geometric deep learning. With our attention towards CPSs, the two aspects dynamic and (soft) real-time are becoming essential. Therefore, we will study learning tasks on dynamic graphs such as sequences and streams of graphs. In order to integrate our new methods into CPSs we need our approaches to obey resource constraints regarding runtime, memory, accuracy, energy, transmission speed and number of labelled data. We will evaluate our methods on specific systems and domains that are relevant in the CRC 876 such as logistic sensor-actuator networks (A4), traffic forecasting (B4), and high-frequent irregularly structured data analysis (C3/C5).

Project management:

Dr. Kriege, Nils
Prof. Dr. Mutzel, Petra
Dr. Weichert, Frank

Project members:

Droschinsky, Andre
Fey, Matthias
Morris, Christopher

Alumni project management:



kersting.jpg
Prof. Dr. Kersting, Kristian
Sohler.JPG
Prof. Dr. Sohler, Christian

Alumni:

Erdmann, Elena
Mladenov, Martin
Dr. Rey, Anja
Dr. Zey, Bernd

Datasets:

Benchmark data sets for graph kernels

Software:

Global Weisfeiler-Lehman Kernels
Hash Graph Kernels
Optimal Assignment Kernels
SplineCNN
Subgraph Matching Kernels

Publications:

Morris/Ritzert/2019a Morris, Christopher and Ritzert, Martin and Fey, Matthias and Hamilton, William L. and Lenssen, Jan Eric and Rattan, Gaurav and Grohe, Martin. Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks. (Accepted for publication), In AAAI Conference on Artificial Intelligence (AAAI), 2019.


CohenSteiner/etal/2017a Cohen-Steiner, David and Kong, Weihao and Sohler, Christian and Valiant, Gregory. Approximating the Spectrum of a Graph. In 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2018.


Fey/etal/2017a Fey, Matthias and Lenssen, Jan Eric and Weichert, Frank and Müller, Heinrich. SplineCNN: Fast Geometric Deep Learning with Continuous B-Spline Kernels. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2018.


Kriege/etal/2018b Kriege, Nils and Morris, Christopher and Rey, Anja and Sohler, Christian. A Property Testing Framework for the Theoretical Expressivity of Graph Kernels. In International Joint Conference on Artificial Intelligence (IJCAI), 2018.


Kriege/etal/2018c Kriege, Nils and Fey, Matthias and Fisseler, Denis and Mutzel, Petra and Weichert, Frank. Recognizing Cuneiform Signs Using Graph Based Methods. In International Workshop on Cost-Sensitive Learning (COST), SIAM International Conference on Data Mining (SDM), 2018.


Lenssen/etal/2018b Lenssen, Jan Eric and Fey, Matthias and Libuschewski, Pascal. Group Equivariant Capsule Networks. In Advances in Neural Information Processing Systems (NIPS), to appear, 2018.


Stoecker/etal/2018a Stöcker, Bianca K. and Schäfer, Till and Mutzel, Petra and Köster, Johannes and Kriege, Nils and Rahmann, Sven. Protein Complex Similarity Based on Weisfeiler-Lehman Labeling. In PeerJ Preprints, Vol. 6, No. e26612, 2018.


Ying/You/2018a Ying, Rex and You, Jiaxuan and Morris, Christopher and Ren, Xiang and Hamilton, William L. and Leskovec, Jure. Hierarchical Graph Representation Learning with Differentiable Pooling. In Neural Information Processing Systems (NIPS) 2019, 2018.


Biedl/Chimani/2017a Biedl, Therese and Chimani, Markus and Derka, Martin and Mutzel, Petra. Crossing Number for Graphs With Bounded Pathwidth. In Yoshio Okamoto and Takeshi Tokuyama (editors), Algorithms and Computation - 28th International Symposium, ISAAC 2017, Vol. 92, pages 1-13, Dagstuhl, Germany, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.


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 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 CoRR, Vol. abs/1703.00676, 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 Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), pages 2357--2363, 2017.


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


Morris/etal/2017b Morris, Christopher and Kersting, Kristian and Mutzel, Petra. Glocalized Weisfeiler-Lehman Graph Kernels: Global-Local Feature Maps of Graphs. In IEEE International Conference on Data Mining (ICDM), pages 327--336, 2017.


Morris/Kriege/2016a Kriege, Nils and Morris, Christopher. Recent Advances in Kernel-Based Graph Classification. In Michelangelo Ceci and Jaakko Hollmen and Ljupčo Todorovski and Celine Vens (editors), European Conference on Machine Learning & Principles and Practice of Knowledge Discovery in Databases (ECML PKDD), Springer, 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.


Giscard/etal/2016a Pierre-Louis Giscard and Nils Kriege and Richard C. Wilson. A general purpose algorithm for counting simple cycles and simple paths of any length. In CoRR, Vol. abs/1612.05531, 2016.


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


Kriege/etal/2016b Kriege, Nils and Giscard, Pierre-Louis and Wilson, Richard C.. On Valid Optimal Assignment Kernels and Applications to Graph Classification. In Advances in Neural Information Processing Systems (NIPS), pages 1623--1631, 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 and Kersting, Kristian and Mutzel, Petra. Faster Kernels for Graphs with Continuous Attributes via Hashing. In IEEE International Conference on Data Mining (ICDM), pages 1095--1100, 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.



Disserations:

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


  • Kriege/2015a - Comparing Graphs: Algorithms & Applications

Final Theses:

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


Feininger/2017a Feininger, David. Experimenteller Vergleich von Algorithmen für inkrementelle Kürzeste-Wege-Probleme. Faculty of Computer Science, TU Dortmund University, 2017.


Foot/2017a Foot, Hermann. Evaluierung von Algorithmen zur Berechnung gerichteter Matchings. Faculty of Computer Science, TU Dortmund University, 2017.


Frickenschmidt/2017a Frickenschmidt, Yannick. Regression von Kürzeste-Wege-Verteilungen in dynamischen Netzwerken. Faculty of Computer Science, TU Dortmund University, 2017.


Funk/2017a Funk, Nicole. Kürzeste-Wege-Kerne für ungewichtete Graphen mit Labeln. Faculty of Computer Science, TU Dortmund University, 2017.


Matuszcyzk/2017a Matuszczyk, Daniel. Multilevel Layout-Methoden für Cluster-Graphen. Faculty of Computer Science, TU Dortmund University, 2017.


Mundorf/2017a Mundorf, Johannes. Implementierung und Evaluierung flussbasierter ILP-Formulierungen für das Steinerwaldproblem. Faculty of Computer Science, TU Dortmund University, 2017.


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


Wisniewski/2017a Wisniewski, Patrick. Ein praxisorientierter Ansatz zur Routenplanung für Wartungseinsätze. Faculty of Computer Science, TU Dortmund University, 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
  • Feininger/2017a - Experimenteller Vergleich von Algorithmen für inkrementelle Kürzeste-Wege-Probleme
  • Foot/2017a - Evaluierung von Algorithmen zur Berechnung gerichteter Matchings
  • Frickenschmidt/2017a - Regression von Kürzeste-Wege-Verteilungen in dynamischen Netzwerken
  • Funk/2017a - Kürzeste-Wege-Kerne für ungewichtete Graphen mit Labeln
  • Matuszcyzk/2017a - Multilevel Layout-Methoden für Cluster-Graphen
  • Mundorf/2017a - Implementierung und Evaluierung flussbasierter ILP-Formulierungen für das Steinerwaldproblem
  • Rentz/2017a - Approximative Algorithmen für das Assignment-Problem mit Hilfe von hierarchischem Clustering
  • Wisniewski/2017a - Ein praxisorientierter Ansatz zur Routenplanung für Wartungseinsätze
  • 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), pages 881--886, 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 Journal on Computing, Vol. 42, No. 3, pages 1095-1112, 2013.


Kriege/Mutzel/2012a Kriege, N. and Mutzel, P.. Subgraph Matching Kernels for Attributed Graphs. In Proceedings of the 29th International Conference 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 Klein, K. and Kriege, N. and Mutzel, P.. 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 Journal on Computing, 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.