59 citations · 376 across the 66 of their papers we have counts for
88 papers
Future Directions in the Theory of Graph Machine Learning
Christopher Morris, Fabrizio Frasca, Nadav Dym +7
Machine learning on graphs, especially using graph neural networks (GNNs), has seen a surge in interest due to the wide availability of graph data across a broad spectrum of discip…
Isomorphism for Tournaments of Small Twin Width
Martin Grohe, Daniel Neuen
We prove that isomorphism of tournaments of twin width at most can be decided in time . This implies that the isomorphism problem for classes of tourname…
Where Did the Gap Go? Reassessing the Long-Range Graph Benchmark
Jan Tönshoff, Martin Ritzert, Eran Rosenbluth +1
The recent Long-Range Graph Benchmark (LRGB, Dwivedi et al. 2022) introduced a set of graph learning tasks strongly dependent on long-range interaction between vertices. Empirical…
The Parameterized Complexity of Learning Monadic Second-Order Logic
Steffen van Bergerem, Martin Grohe, Nina Runde
Within the model-theoretic framework for supervised learning introduced by Grohe and Turán (TOCS 2004), we study the parameterized complexity of learning concepts definable in mona…
Structural Node Embeddings with Homomorphism Counts
Hinrikus Wolf, Luca Oeljeklaus, Pascal Kühner +1
Graph homomorphism counts, first explored by Lovász in 1967, have recently garnered interest as a powerful tool in graph-based machine learning. Grohe (PODS 2020) proposed the theo…
Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements
Martin Grohe, Moritz Lichter, Daniel Neuen +1
The -dimensional Weisfeiler-Leman (-WL) algorithm is a simple combinatorial algorithm that was originally designed as a graph isomorphism heuristic. It naturally finds applic…