Arrow Research search

Author name cluster

Martin Grohe

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

57 papers
2 author rows

Possible papers

57

AAAI Conference 2026 Conference Paper

Repetition Makes Perfect: Recurrent Graph Neural Networks Match Message Passing Limit

  • Eran Rosenbluth
  • Martin Grohe

We precisely characterize the expressivity of computable Recurrent Graph Neural Networks (recurrent GNNs). We prove that recurrent GNNs with finite-precision parameters, sum aggregation, and ReLU activation, can compute any graph algorithm that respects the natural message-passing invariance induced by the Color Refinement (or Weisfeiler-Leman) algorithm. While it is well known that the expressive power of GNNs is limited by this invariance [Morris et al., AAAI 2019; Xu et al., ICLR 2019], we establish that recurrent GNNs can actually match this limit. This is in contrast to non-recurrent GNNs, which have the power of Weisfeiler-Leman only in a very weak, "non-uniform", sense where each graph size requires a different GNN to compute with. Our construction introduces only a polynomial overhead in both time and space. Furthermore, we show that by incorporating random initialization, for connected graphs recurrent GNNs can express all graph algorithms. In particular, any polynomial-time graph algorithm can be emulated on connected graphs in polynomial time by a recurrent GNN with random initialization.

PDF Details DOI

CSL Conference 2025 Conference Paper

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 monadic second-order logic (MSO). We show that the problem of learning an MSO-definable concept from a training sequence of labeled examples is fixed-parameter tractable on graphs of bounded clique-width, and that it is hard for the parameterized complexity class para-NP on general graphs. It turns out that an important distinction to be made is between 1-dimensional and higher-dimensional concepts, where the instances of a k-dimensional concept are k-tuples of vertices of a graph. For the higher-dimensional case, we give a learning algorithm that is fixed-parameter tractable in the size of the graph, but not in the size of the training sequence, and we give a hardness result showing that this is optimal. By comparison, in the 1-dimensional case, we obtain an algorithm that is fixed-parameter tractable in both.

Details

ICLR Conference 2024 Conference Paper

Distinguished In Uniform: Self-Attention Vs. Virtual Nodes

  • Eran Rosenbluth
  • Jan Tönshoff
  • Martin Ritzert
  • Berke Kisin
  • Martin Grohe

Graph Transformers (GTs) such as SAN and GPS are graph processing models that combine Message-Passing GNNs (MPGNNs) with global Self-Attention. They were shown to be universal function approximators, with two reservations: 1. The initial node features must be augmented with certain positional encodings. 2. The approximation is non-uniform: Graphs of different sizes may require a different approximating network. We first clarify that this form of universality is not unique to GTs: Using the same positional encodings, also pure MPGNNs and even 2-layer MLPs are non-uniform universal approximators. We then consider uniform expressivity: The target function is to be approximated by a single network for graphs of all sizes. There, we compare GTs to the more efficient MPGNN + Virtual Node architecture. The essential difference between the two model definitions is in their global computation method: Self-Attention Vs Virtual Node. We prove that none of the models is a uniform-universal approximator, before proving our main result: Neither model’s uniform expressivity subsumes the other’s. We demonstrate the theory with experiments on synthetic data. We further augment our study with real-world datasets, observing mixed results which indicate no clear ranking in practice as well.

Details

ICML Conference 2024 Conference Paper

Position: Future Directions in the Theory of Graph Machine Learning

  • Christopher Morris 0001
  • Fabrizio Frasca
  • Nadav Dym
  • Haggai Maron
  • Ismail Ilkan Ceylan
  • Ron Levie
  • Derek Lim
  • Michael M. Bronstein

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 disciplines, from life to social and engineering sciences. Despite their practical success, our theoretical understanding of the properties of GNNs remains highly incomplete. Recent theoretical advancements primarily focus on elucidating the coarse-grained expressive power of GNNs, predominantly employing combinatorial techniques. However, these studies do not perfectly align with practice, particularly in understanding the generalization behavior of GNNs when trained with stochastic first-order optimization techniques. In this position paper, we argue that the graph machine learning community needs to shift its attention to developing a balanced theory of graph machine learning, focusing on a more thorough understanding of the interplay of expressive power, generalization, and optimization.

Details

TMLR Journal 2024 Journal Article

Where Did the Gap Go? Reassessing the Long-Range Graph Benchmark

  • Jan Tönshoff
  • Martin Ritzert
  • Eran Rosenbluth
  • Martin Grohe

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 evidence suggests that on these tasks Graph Transformers significantly outperform Message Passing GNNs (MPGNNs). In this paper, we carefully reevaluate multiple MPGNN baselines as well as the Graph Transformer GPS (Rampášek et al. 2022) on LRGB. Through a rigorous empirical analysis, we demonstrate that the reported performance gap is overestimated due to suboptimal hyperparameter choices. It is noteworthy that across multiple datasets the performance gap completely vanishes after basic hyperparameter optimization. In addition, we discuss the impact of lacking feature normalization for LRGB's vision datasets and highlight a spurious implementation of LRGB's link prediction metric. The principal aim of our paper is to establish a higher standard of empirical rigor within the graph machine learning community.

PDF Details

FOCS Conference 2023 Conference Paper

Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements

  • Martin Grohe
  • Moritz Lichter
  • Daniel Neuen
  • Pascal Schweitzer

The k-dimensional Weisfeiler-Leman (k-WL) algorithm is a simple combinatorial algorithm that was originally designed as a graph isomorphism heuristic. It naturally finds applications in Babai’s quasipolynomial-time isomorphism algorithm, practical isomorphism solvers, and algebraic graph theory. However, it also has surprising connections to other areas such as logic, proof complexity, combinatorial optimization, and machine learning. The algorithm iteratively computes a coloring of the k-tuples of vertices of a graph. Since Fürer’s linear lower bound [ICALP 2001], it has been an open question whether there is a super-linear lower bound for the iteration number for k-WL on graphs. We answer this question affirmatively, establishing an $\Omega\left(n^{k / 2}\right)$-lower bound for all k.

Details

IJCAI Conference 2023 Conference Paper

One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfaction

  • Jan Tönshoff
  • Berke Kisin
  • Jakob Lindner
  • Martin Grohe

We propose a universal Graph Neural Network architecture which can be trained as an end-2-end search heuristic for any Constraint Satisfaction Problem (CSP). Our architecture can be trained unsupervised with policy gradient descent to generate problem specific heuristics for any CSP in a purely data driven manner. The approach is based on a novel graph representation for CSPs that is both generic and compact and enables us to process every possible CSP instance with one GNN, regardless of constraint arity, relations or domain size. Unlike previous RL-based methods, we operate on a global search action space and allow our GNN to modify any number of variables in every step of the stochastic search. This enables our method to properly leverage the inherent parallelism of GNNs. We perform a thorough empirical evaluation where we learn heuristics for well known and important CSPs, both decision and optimisation problems, from random data, including graph coloring, MAXCUT, and MAX-k-SAT, and the general RB model. Our approach significantly outperforms prior end-2-end approaches for neural combinatorial optimization. It can compete with conventional heuristics and solvers on test instances that are several orders of magnitude larger and structurally more complex than those seen during training.

PDF Details DOI

IJCAI Conference 2023 Conference Paper

Some Might Say All You Need Is Sum

  • Eran Rosenbluth
  • Jan Tönshoff
  • Martin Grohe

The expressivity of Graph Neural Networks (GNNs) is dependent on the aggregation functions they employ. Theoretical works have pointed towards Sum aggregation GNNs subsuming every other GNNs, while certain practical works have observed a clear advantage to using Mean and Max. An examination of the theoretical guarantee identifies two caveats. First, it is size-restricted, that is, the power of every specific GNN is limited to graphs of a specific size. Successfully processing larger graphs may require an other GNN, and so on. Second, it concerns the power to distinguish non-isomorphic graphs, not the power to approximate general functions on graphs, and the former does not necessarily imply the latter. It is desired that a GNN's usability will not be limited to graphs of any specific size. Therefore, we explore the realm of unrestricted-size expressivity. We prove that basic functions, which can be computed exactly by Mean or Max GNNs, are inapproximable by any Sum GNN. We prove that under certain restrictions, every Mean or Max GNN can be approximated by a Sum GNN, but even there, a combination of (Sum, [Mean/Max]) is more expressive than Sum alone. Lastly, we prove further expressivity limitations for GNNs with a broad class of aggregations.

PDF Details DOI

TMLR Journal 2023 Journal Article

Walking Out of the Weisfeiler Leman Hierarchy: Graph Learning Beyond Message Passing

  • Jan Tönshoff
  • Martin Ritzert
  • Hinrikus Wolf
  • Martin Grohe

We propose CRaWl, a novel neural network architecture for graph learning. Like graph neural networks, CRaWl layers update node features on a graph and thus can freely be combined or interleaved with GNN layers. Yet CRaWl operates fundamentally different from message passing graph neural networks. CRaWl layers extract and aggregate information on subgraphs appearing along random walks through a graph using 1D Convolutions. Thereby it detects long range interactions and computes non-local features. As the theoretical basis for our approach, we prove a theorem stating that the expressiveness of CRaWl is incomparable with that of the Weisfeiler Leman algorithm and hence with graph neural networks. That is, there are functions expressible by CRaWl, but not by GNNs and vice versa. This result extends to higher levels of the Weisfeiler Leman hierarchy and thus to higher-order GNNs. Empirically, we show that CRaWl matches state-of-the-art GNN architectures across a multitude of benchmark datasets for classification and regression on graphs.

PDF Details

JMLR Journal 2023 Journal Article

Weisfeiler and Leman go Machine Learning: The Story so far

  • Christopher Morris
  • Yaron Lipman
  • Haggai Maron
  • Bastian Rieck
  • Nils M. Kriege
  • Martin Grohe
  • Matthias Fey
  • Karsten Borgwardt

In recent years, algorithms and neural architectures based on the Weisfeiler–Leman algorithm, a well-known heuristic for the graph isomorphism problem, have emerged as a powerful tool for machine learning with graphs and relational data. Here, we give a comprehensive overview of the algorithm’s use in a machine-learning setting, focusing on the supervised regime. We discuss the theoretical background, show how to use it for supervised graph and node representation learning, discuss recent extensions, and outline the algorithm’s connection to (permutation-)equivariant neural architectures. Moreover, we give an overview of current applications and future directions to stimulate further research. [abs] [ pdf ][ bib ] &copy JMLR 2023. ( edit, beta )

PDF Details

ICML Conference 2023 Conference Paper

WL meet VC

  • Christopher Morris 0001
  • Floris Geerts
  • Jan Tönshoff
  • Martin Grohe

Recently, many works studied the expressive power of graph neural networks (GNNs) by linking it to the $1$-dimensional Weisfeiler-Leman algorithm ($1\text{-}\mathsf{WL}$). Here, the $1\text{-}\mathsf{WL}$ is a well-studied heuristic for the graph isomorphism problem, which iteratively colors or partitions a graph’s vertex set. While this connection has led to significant advances in understanding and enhancing GNNs’ expressive power, it does not provide insights into their generalization performance, i. e. , their ability to make meaningful predictions beyond the training set. In this paper, we study GNNs’ generalization ability through the lens of Vapnik-Chervonenkis (VC) dimension theory in two settings, focusing on graph-level predictions. First, when no upper bound on the graphs’ order is known, we show that the bitlength of GNNs’ weights tightly bounds their VC dimension. Further, we derive an upper bound for GNNs’ VC dimension using the number of colors produced by the $1\text{-}\mathsf{WL}$. Secondly, when an upper bound on the graphs’ order is known, we show a tight connection between the number of graphs distinguishable by the $1\text{-}\mathsf{WL}$ and GNNs’ VC dimension. Our empirical study confirms the validity of our theoretical findings.

Details

MFCS Conference 2022 Conference Paper

Graph Similarity Based on Matrix Norms

  • Timo Gervens
  • Martin Grohe

Quantifying the similarity between two graphs is a fundamental algorithmic problem at the heart of many data analysis tasks for graph-based data. In this paper, we study the computational complexity of a family of similarity measures based on quantifying the mismatch between the two graphs, that is, the "symmetric difference" of the graphs under an optimal alignment of the vertices. An important example is similarity based on graph edit distance. While edit distance calculates the "global" mismatch, that is, the number of edges in the symmetric difference, our main focus is on "local" measures calculating the maximum mismatch per vertex. Mathematically, our similarity measures are best expressed in terms of the adjacency matrices: the mismatch between graphs is expressed as the difference of their adjacency matrices (under an optimal alignment), and we measure it by applying some matrix norm. Roughly speaking, global measures like graph edit distance correspond to entrywise matrix norms like the Frobenius norm and local measures correspond to operator norms like the spectral norm. We prove a number of strong NP-hardness and inapproximability results even for very restricted graph classes such as bounded-degree trees.

Details

MFCS Conference 2021 Conference Paper

A Deep Dive into the Weisfeiler-Leman Algorithm (Invited Talk)

  • Martin Grohe

The Weisfeiler-Leman algorithm is a well-known combinatorial graph isomorphism test going back to work of Weisfeiler and Leman in the late 1960s. The algorithm has a surprising number of seemingly unrelated characterisations in terms of logic, algebra, linear and semi-definite programming, and graph homomorphisms. Due to its simplicity and efficiency, it is an important subroutine of all modern graph isomorphism tools. In recent years, further applications in linear optimisation, probabilistic inference, and machine learning have surfaced. In my talk, I will introduce the Weisfeiler-Leman algorithm and some extensions. I will discuss its expressiveness and the various characterisations, and I will speak about its applications.

Details

IJCAI Conference 2021 Conference Paper

The Surprising Power of Graph Neural Networks with Random Node Initialization

  • Ralph Abboud
  • İsmail İlkan Ceylan
  • Martin Grohe
  • Thomas Lukasiewicz

Graph neural networks (GNNs) are effective models for representation learning on relational data. However, standard GNNs are limited in their expressive power, as they cannot distinguish graphs beyond the capability of the Weisfeiler-Leman graph isomorphism heuristic. In order to break this expressiveness barrier, GNNs have been enhanced with random node initialization (RNI), where the idea is to train and run the models with randomized initial node features. In this work, we analyze the expressive power of GNNs with RNI, and prove that these models are universal, a first such result for GNNs not relying on computationally demanding higher-order properties. This universality result holds even with partially randomized initial node features, and preserves the invariance properties of GNNs in expectation. We then empirically analyze the effect of RNI on GNNs, based on carefully constructed datasets. Our empirical findings support the superior performance of GNNs with RNI over standard GNNs.

PDF Details DOI

FOCS Conference 2020 Conference Paper

Isomorphism Testing for Graphs Excluding Small Minors

  • Martin Grohe
  • Daniel Wiebking
  • Daniel Neuen

We prove that there is a graph isomorphism test running in time n polylog(h) on n-vertex graphs excluding some h-vertex graph as a minor. Previously known bounds were n poly(h) (Ponomarenko, 1988) and n polylog(n) (Babai, STOC 2016). For the algorithm we combine recent advances in the group-theoretic graph isomorphism machinery with new graph-theoretic arguments.

Details

MFCS Conference 2019 Conference Paper

The Complexity of Homomorphism Indistinguishability

  • Jan Böker
  • Yijia Chen 0001
  • Martin Grohe
  • Gaurav Rattan

For every graph class {F}, let HomInd({F}) be the problem of deciding whether two given graphs are homomorphism-indistinguishable over {F}, i. e. , for every graph F in {F}, the number hom(F, G) of homomorphisms from F to G equals the corresponding number hom(F, H) for H. For several natural graph classes (such as paths, trees, bounded treewidth graphs), homomorphism-indistinguishability over the class has an efficient structural characterization, resulting in polynomial time solvability [H. Dell et al. , 2018]. In particular, it is known that two non-isomorphic graphs are homomorphism-indistinguishable over the class {T}_k of graphs of treewidth k if and only if they are not distinguished by k-dimensional Weisfeiler-Leman algorithm, a central heuristic for isomorphism testing: this characterization implies a polynomial time algorithm for HomInd({T}_k), for every fixed k in N. In this paper, we show that there is a polynomial-time-decidable class {F} of undirected graphs of bounded treewidth such that HomInd({F}) is undecidable. Our second hardness result concerns the class {K} of complete graphs. We show that HomInd({K}) is co-NP-hard, and in fact, we show completeness for the class C_=P (under P-time Turing reductions). On the algorithmic side, we show that HomInd({P}) can be solved in polynomial time for the class {P} of directed paths. We end with a brief study of two variants of the HomInd({F}) problem: (a) the problem of lexographic-comparison of homomorphism numbers of two graphs, and (b) the problem of computing certain distance-measures (defined via homomorphism numbers) between two graphs.

Details

AAAI Conference 2019 Conference Paper

Weisfeiler and Leman Go Neural: Higher-Order Graph Neural Networks

  • Christopher Morris
  • Martin Ritzert
  • Matthias Fey
  • William L. Hamilton
  • Jan Eric Lenssen
  • Gaurav Rattan
  • Martin Grohe

In recent years, graph neural networks (GNNs) have emerged as a powerful neural architecture to learn vector representations of nodes and graphs in a supervised, end-to-end fashion. Up to now, GNNs have only been evaluated empirically—showing promising results. The following work investigates GNNs from a theoretical point of view and relates them to the 1-dimensional Weisfeiler-Leman graph isomorphism heuristic (1-WL). We show that GNNs have the same expressiveness as the 1-WL in terms of distinguishing non-isomorphic (sub-)graphs. Hence, both algorithms also have the same shortcomings. Based on this, we propose a generalization of GNNs, so-called k-dimensional GNNs (k-GNNs), which can take higher-order graph structures at multiple scales into account. These higher-order structures play an essential role in the characterization of social networks and molecule graphs. Our experimental evaluation confirms our theoretical findings as well as confirms that higher-order information is useful in the task of graph classification and regression.

PDF Details

FOCS Conference 2018 Conference Paper

A Faster Isomorphism Test for Graphs of Small Degree

  • Martin Grohe
  • Daniel Neuen
  • Pascal Schweitzer

In a recent breakthrough, Babai (STOC 2016) gave quasipolynomial graph isomorphism test. In this work, we give an improved isomorphism test for graphs of small degree: our algorithms runs in time n^O((log d)^c), where n is the number of vertices of the input graphs, d is the maximum degree of the input graphs, and c is an absolute constant. The best previous isomorphism test for graphs of maximum degree d due to Babai, Kantor and Luks (FOCS 1983) runs in time n^O(d log d).

Details

MFCS Conference 2018 Conference Paper

Graph Similarity and Approximate Isomorphism

  • Martin Grohe
  • Gaurav Rattan
  • Gerhard J. Woeginger

The graph similarity problem, also known as approximate graph isomorphism or graph matching problem, has been extensively studied in the machine learning community, but has not received much attention in the algorithms community: Given two graphs G, H of the same order n with adjacency matrices A_G, A_H, a well-studied measure of similarity is the Frobenius distance dist(G, H): =min_{pi}|A_G^{pi}-A_H|_F, where pi ranges over all permutations of the vertex set of G, where A_G^pi denotes the matrix obtained from A_G by permuting rows and columns according to pi, and where |M |_F is the Frobenius norm of a matrix M. The (weighted) graph similarity problem, denoted by GSim (WSim), is the problem of computing this distance for two graphs of same order. This problem is closely related to the notoriously hard quadratic assignment problem (QAP), which is known to be NP-hard even for severely restricted cases. It is known that GSim (WSim) is NP-hard; we strengthen this hardness result by showing that the problem remains NP-hard even for the class of trees. Identifying the boundary of tractability for WSim is best done in the framework of linear algebra. We show that WSim is NP-hard as long as one of the matrices has unbounded rank or negative eigenvalues: hence, the realm of tractability is restricted to positive semi-definite matrices of bounded rank. Our main result is a polynomial time algorithm for the special case where the associated (weighted) adjacency graph for one of the matrices has a bounded number of twin equivalence classes. The key parameter underlying our algorithm is the clustering number of a graph; this parameter arises in context of the spectral graph drawing machinery.

Details

Highlights Conference 2016 Conference Abstract

Order Invariance on Decomposable Structures

  • Michael Elberfeld
  • Marlin Frickenschmidt
  • Martin Grohe

Order-invariant formulas access an ordering on a structure’s universe, but the model relation is independent of the used ordering. Order invariance is frequently used for logic-based approaches in computer science. Order-invariant formulas capture unordered problems of complexity classes and they model the independence of the answer to a database query from low-level aspects of databases. We study the expressive power of order-invariant monadic second-order (MSO) and first-order (FO) logic on restricted classes of structures that admit certain forms of tree decompositions (not necessarily of bounded width). While order-invariant MSO is more expressive than MSO and, even, CMSO (MSO with modulo-counting predicates), we show that order-invariant MSO and CMSO are equally expressive on graphs of bounded tree width and on planar graphs. This extends an earlier result for trees due to Courcelle. Moreover, we show that all properties definable in order-invariant FO are also definable in MSO on these classes. These results are applications of a theorem that shows how to lift up definability results for order-invariant logics from the bags of a graph’s tree decomposition to the graph itself. This is joint work with Michael Elberfeld and Martin Grohe. It was accepted to LICS 2016.

Details

FOCS Conference 2015 Conference Paper

Isomorphism Testing for Graphs of Bounded Rank Width

  • Martin Grohe
  • Pascal Schweitzer

We give an algorithm that, for every fixed k, decides isomorphism of graphs of rank width at most k in polynomial time. As the rank width of a graph is bounded in terms of its clique width, we also obtain a polynomial time isomorphism test for graph classes of bounded clique width.

Details

STOC Conference 2014 Conference Paper

Deciding first-order properties of nowhere dense graphs

  • Martin Grohe
  • Stephan Kreutzer
  • Sebastian Siebertz

Nowhere dense graph classes, introduced by Nešetřil and Ossona de Mendez [30], form a large variety of classes of "sparse graphs" including the class of planar graphs, actually all classes with excluded minors, and also bounded degree graphs and graph classes of bounded expansion. We show that deciding properties of graphs definable in first-order logic is fixed-parameter tractable on nowhere dense graph classes. At least for graph classes closed under taking subgraphs, this result is optimal: it was known before that for all classes C of graphs closed under taking subgraphs, if deciding first-order properties of graphs in C is fixed-parameter tractable, then C must be nowhere dense (under a reasonable complexity theoretic assumption). As a by-product, we give an algorithmic construction of sparse neighbourhood covers for nowhere dense graphs. This extends and improves previous constructions of neighbourhood covers for graph classes with excluded minors. At the same time, our construction is considerably simpler than those. Our proofs are based on a new game-theoretic characterisation of nowhere dense graphs that allows for a recursive version of locality-based algorithms on these classes. On the logical side, we prove a "rank-preserving" version of Gaifman's locality theorem.

Details

AAAI Conference 2014 Conference Paper

Power Iterated Color Refinement

  • Kristian Kersting
  • Martin Mladenov
  • Roman Garnett
  • Martin Grohe

Color refinement is a basic algorithmic routine for graph isomorphism testing and has recently been used for computing graph kernels as well as for lifting belief propagation and linear programming. So far, color refinement has been treated as a combinatorial problem. Instead, we treat it as a nonlinear continuous optimization problem and prove that it implements a conditional gradient optimizer that can be turned into graph clustering approaches using hashing and truncated power iterations. This shows that color refinement is easy to understand in terms of random walks, easy to implement (matrix-matrix/vector multiplications) and readily parallelizable. We support our theoretical results with experiments on real-world graphs with millions of edges.

PDF Details

MFCS Conference 2013 Conference Paper

Logical and Structural Approaches to the Graph Isomorphism Problem

  • Martin Grohe

Abstract It is a long-standing open question whether there is a polynomial time algorithm deciding if two graphs are isomorphic. Indeed, graph isomorphism is one of the very few natural problems in NP that is neither known to be in P nor known to be NP-complete. The question is still wide open, but a number of deep partial results are known. On the complexity theoretic side, we have good reason to believe that graph isomorphism is not NP-complete: if it was NP-complete, then the polynomial hierarchy would collapse to its second level. On the algorithmic side, we know a nontrivial algorithm with a worst-case running time of \(2^{O(\sqrt{n\log n})}\) and polynomial time algorithms for many specific classes of graphs. Many of these algorithmic results have been obtained through a group theoretic approach that dominated the research on the graph isomorphism problem since the early 1980s. After an introductory survey, in my talk I will focus on approaches to the graph isomorphism problem based on structural graph theory and connections between logical definability, certain combinatorial algorithms, and mathematical programming approaches to the isomorphism problem.

Details

Highlights Conference 2013 Conference Abstract

Tutorial: Logic for algorithms

  • Martin Grohe

The theme of this tutorial is (recent) applications of logic in the design and analysis of efficient algorithms. I will cover the following three topics. Logical techniques in the analysis of generic algorithms Certain generic (families of) algorithms, such as the Weisfeiler-Lehman algorithm for graph isomorphism testing and k-consistency tests for constraint satisfaction problems have logical characterisations. Thus logical techniques can be used to analyse the power of these algorithms and also to prove lower bounds for their running time. Algorithmic meta theorems Algorithmic meta theorems attempt to explain and unify algorithmic results by proving tractability not only for individual problems, but for whole classes of problems. These classes are typically defined in terms of logic. The prototypical example of an algorithmic meta theorem is Courcelle's Theorem, stating that all properties of graphs of bounded tree-width that are definable in monadic second-order logic are decidable in linear time. In the tutorial, I will focus on meta theorems for first-order logic, where by now we have a fairly complete picture of graph classes admitting a nontrivial meta theorem Applications of meta theorems in algorithmic graph structure theory In this last part I will discuss applications of algorithmic meta theorems to problems in algorithmic graph structure theory. By this I mean graph algorithms that use meta theorems to solve tasks for which no other (direct combinatorial) algorithm is known. It is worth noting that the algorithmic problems considered in all three parts are not derived from logic, such as satisfiability or model-checking problems, but "standard" algorithmic problems, often with a strong combinatorial and graph theoretical flavour. On the way, I will introduce the necessary graph theory, including nowhere dense graphs and certain aspects of graph minor theory.

Details

CSL Conference 2012 Conference Paper

Pebble Games and Linear Equations

  • Martin Grohe
  • Martin Otto 0001

We give a new, simplified and detailed account of the correspondence between levels of the Sherali-Adams relaxation of graph isomorphism and levels of pebble-game equivalence with counting (higher-dimensional Weisfeiler-Lehman colour refinement). The correspondence between basic colour refinement and fractional isomorphism, due to Ramana, Scheinerman and Ullman, is re-interpreted as the base level of Sherali-Adams and generalised to higher levels in this sense by Atserias and Maneva, who prove that the two resulting hierarchies interleave. In carrying this analysis further, we here give (a) a precise characterisation of the level-k Sherali-Adams relaxation in terms of a modified counting pebble game; (b) a variant of the Sherali-Adams levels that precisely match the k-pebble counting game; (c) a proof that the interleaving between these two hierarchies is strict. We also investigate the variation based on boolean arithmetic instead of real/rational arithmetic and obtain analogous correspondences and separations for plain k-pebble equivalence (without counting). Our results are driven by considerably simplified accounts of the underlying combinatorics and linear algebra.

Details

CSL Conference 2011 Conference Paper

L-Recursion and a new Logic for Logarithmic Space

  • Martin Grohe
  • Berit Grußien
  • André Hernich
  • Bastian Laubner

We extend first-order logic with counting by a new operator that allows it to formalise a limited form of recursion which can be evaluated in logarithmic space. The resulting logic LREC has a data complexity in LOGSPACE, and it defines LOGSPACE-complete problems like deterministic reachability and Boolean formula evaluation. We prove that LREC is strictly more expressive than deterministic transitive closure logic with counting and incomparable in expressive power with symmetric transitive closure logic STC and transitive closure logic (with or without counting). LREC is strictly contained in fixed-point logic with counting FPC. We also study an extension LREC= of LREC that has nicer closure properties and is more expressive than both LREC and STC, but is still contained in FPC and has a data complexity in LOGSPACE. Our main results are that LREC captures LOGSPACE on the class of directed trees and that LREC= captures LOGSPACE on the class of interval graphs.

Details

CSL Conference 2010 Conference Paper

Randomisation and Derandomisation in Descriptive Complexity Theory

  • Kord Eickmeyer
  • Martin Grohe

Abstract We study probabilistic complexity classes and questions of derandomisation from a logical point of view. For each logic L we introduce a new logic BPL, bounded error probabilistic L, which is defined from L in a similar way as the complexity class BPP, bounded error probabilistic polynomial time, is defined from P. Our main focus lies on questions of derandomisation, and we prove that there is a query which is definable in BPFO, the probabilistic version of first-order logic, but not in C \(^\omega_{\infty{\omega}}\), finite variable infinitary logic with counting. This implies that many of the standard logics of finite model theory, like transitive closure logic and fixed-point logic, both with and without counting, cannot be derandomised. We prove similar results for ordered structures and structures with an addition relation, showing that certain uniform variants of A C 0 (bounded-depth polynomial sized circuits) cannot be derandomised. These results are in contrast to the general belief that most standard complexity classes can be derandomised. Finally, we note that BPIFP+C, the probabilistic version of fixed-point logic with counting, captures the complexity class BPP, even on unordered structures.

Details

FOCS Conference 2008 Conference Paper

Size Bounds and Query Plans for Relational Joins

  • Albert Atserias
  • Martin Grohe
  • Dániel Marx

Relational joins are at the core of relational algebra, which in turn is the core of the standard database query language SQL. As their evaluation is expensive and very often dominated by the output size, it is an important task for database query optimisers to compute estimates on the size of joins and to find good execution plans for sequences of joins. We study these problems from a theoretical perspective, both in the worst-case model, and in an average-case model where the database is chosen according to a known probability distribution. In the former case, our first key observation is that the worst-case size of a query is characterised by the fractional edge cover number of its underlying hypergraph, a combinatorial parameter previously known to provide an upper bound. We complete the picture by proving a matching lower bound, and by showing that there exist queries for which the join-project plan suggested by the fractional edge cover approach may be substantially better than any join plan that does not use intermediate projections.

Details

CSL Conference 2007 Conference Paper

The Ackermann Award 2007

  • Martin Grohe
  • Martin Hyland
  • Johann A. Makowsky
  • Damian Niwinski

Abstract The third Ackermann Award is presented at this CSL’07. This is the first year in which the EACSL Ackermann Award is generously sponsored. Our sponsor for the next three years is the worlds leading provider of personal peripherals, Logitech S. A. , situated in Romanel, Switzerland.

Details

MFCS Conference 2005 Conference Paper

The Expressive Power of Two-Variable Least Fixed-Point Logics

  • Martin Grohe
  • Stephan Kreutzer
  • Nicole Schweikardt

Abstract The present paper gives a classification of the expressive power of two-variable least fixed-point logics. The main results are: 1 The two-variable fragment of monadic least fixed-point logic with parameters is as expressive as full monadic least fixed-point logic (on binary structures). 2 The two-variable fragment of monadic least fixed-point logic without parameters is as expressive as the two-variable fragment of binary least fixed-point logic without parameters. 3 The two-variable fragment of binary least fixed-point logic with parameters is strictly more expressive than the two-variable fragment of monadic least fixed-point logic with parameters (even on finite strings).

Details

CSL Conference 2003 Conference Paper

Comparing the Succinctness of Monadic Query Languages over Finite Trees

  • Martin Grohe
  • Nicole Schweikardt

Abstract We study the succinctness of monadic second-order logic and a variety of monadic fixed point logics on trees. All these languages are known to have the same expressive power on trees, but some can express the same queries much more succinctly than others. For example, we show that, under some complexity theoretic assumption, monadic second-order logic is non-elementarily more succinct than monadic least fixed point logic, which in turn is non-elementarily more succinct than monadic datalog. Succinctness of the languages is closely related to the combined and parameterized complexity of query evaluation for these languages.

Details

FOCS Conference 2003 Conference Paper

The Complexity of Homomorphism and Constraint Satisfaction Problems Seen from the Other Side

  • Martin Grohe

We give a complexity theoretic classification of homomorphism problems for graphs and, more generally, relational structures obtained by restricting the left hand side structure in a homomorphism. For every class C of structures, let HOM(C, /spl I. bar/) be the problem of deciding whether a given structure A /spl isin/ C has a homomorphism to a given (arbitrary) structure B. We prove that, under some complexity theoretic assumption from parameterized complexity theory, HOM(C, /spl I. bar/) is in polynomial time if, and only if, the cores of all structures in C have bounded tree-width (as long as the structures in C only contain relations of bounded arity). Due to a well known correspondence between homomorphism problems and constraint satisfaction problems, our classification carries over to the latter.

Details

FOCS Conference 2002 Conference Paper

The Parameterized Complexity of Counting Problems

  • Jörg Flum
  • Martin Grohe

We develop a parameterized complexity theory for counting problems. As the basis of this theory, we introduce a hierarchy of parameterized counting complexity classes #W[t], for t/spl ges/1, that corresponds to Downey and Fellows' (1999) W-hierarchy and show that a few central W-completeness results for decision problems translate to #W-completeness results for the corresponding counting problems. Counting complexity gets interesting with problems whose decision version is tractable, but whose counting version is hard. Our main result states that counting cycles and paths of length k in both directed and undirected graphs, parameterized by k, are #W[1]-complete. This makes it highly unlikely that any of these problems is fixed-parameter tractable, even though their decision versions are. More explicitly, our result shows that most likely there is no f(k)/spl middot/n/sup c/-algorithm for counting cycles or paths of length k in a graph of size n for any computable function f: /spl Nopf//spl rarr//spl Nopf/ and constant c, even though there is a 2/sup O(k)//spl middot/n/sup 2. 376/ algorithm for finding a cycle or path of length k (2).

Details

CSL Conference 2001 Conference Paper

An Existential Locality Theorem

  • Martin Grohe
  • Stefan Wöhrle

Abstract We prove an existential version of Gaifman’s locality theorem and show how it can be applied algorithmically to evaluate existential first-order sentences in finite structures.

Details

STOC Conference 2001 Conference Paper

Computing crossing numbers in quadratic time

  • Martin Grohe

We show that for every fixed k\ge 0 there is a quadratic time algorithm that decides whether a given graph has crossing number at most k and, if this is the case, computes a drawing of the graph in the plane with at most k crossings.

Details

STOC Conference 2001 Conference Paper

When is the evaluation of conjunctive queries tractable?

  • Martin Grohe
  • Thomas Schwentick
  • Luc Segoufin

The evaluation of conjunctive queries is hard both with respect to its combined complexity (NP-complete) and its parameterized complexity (W[1]-complete). It becomes tractable (PTIME for combined complexity, FPT for parameterized complexity), when the underlying graphs of the conjunctive queries have bounded tree-width [2]. We show that, in some sense, this is optimal both with respect to combined and parameterized complexity: For every class C of graphs, the evaluation of all conjunctive queries whose underlying graph is in C is tractable if, and only if, C has bounded tree-width. A technical result of independent interest is that the colored grid homomorphism problem is NP-complete and, if parameterized by the grid size, W[1]-complete.

Details

CSL Conference 1999 Invited Paper

Descriptive and Parameterized Complexity

  • Martin Grohe

Abstract Descriptive Complexity Theory studies the complexity of problems of the following type: Given a finite structure A and a sentence φ of some logic L, decide if A satisfies φ? In this survey we discuss the parameterized complexity of such problems. Basically, this means that we ask under which circumstances we have an algorithm solving the problem in time f (|φ|)‖ A ‖ c, where ƒ is a computable function and c > 0 a constant. We argue that the parameterized perspective is most appropriate for analyzing typical practical problems of the above form, which appear for example in database theory, automated verification, and artificial intelligence.

Details

CSL Conference 1998 Conference Paper

Canonization for L k -equivalence is Hard

  • Martin Grohe

Abstract Let L k be the k -variable fragment of first-order logic, for some k ≥ 3. We prove that equivalence of finite structures in L k has no P-computable canonization function unless NP ⊑ P/poly. The latter assumption is considered as highly unlikely; in particular it implies a collapse of the polynomial hierarchy. The question for such a canonization function came up in the context of the problem of whether there is a logic for P. Slight modifications of our result yield answers to questions of Dawar, Lindell, and Weinstein [4]and Otto [16] concerning the inversion of the so-called L k -invariants.

Details

MFCS Conference 1998 Conference Paper

Locality of Order-Invariant First-Order Formulas

  • Martin Grohe
  • Thomas Schwentick

Abstract A query is local if the decision of whether a tuple in a structure satisfies this query only depends on a small neighborhood of the tuple. We prove that all queries expressible by order-invariant first-order formulas are local.

Details

FOCS Conference 1996 Conference Paper

Equivalence in Finite-Variable Logics is Complete for Polynomial Time

  • Martin Grohe

How difficult is it to decide whether two finite structures can be distinguished in a given logic? For first order logic, this question is equivalent to the graph isomorphism problem with its well-known complexity theoretic difficulties. Somewhat surprisingly, the situation is much clearer when considering the fragments L/sup k/ of first-order logic whose formulae contain at most k (free or bound) variables (for some k/spl ges/1). We show that for each k/spl ges/2, equivalence in the k-variable logic L/sup k/ is complete for polynomial time under quantifier-free reductions (a weak form of NC/sub 0/ reductions). Moreover, we show that the same completeness result holds for the powerful extension C/sup k/ of L/sup k/ with counting quantifiers (for every k/spl ges/2).

Details

CSL Conference 1994 Conference Paper

Bounded-Arity Hierarchies in Fixed-Point Logics

  • Martin Grohe

Abstract In this paper we prove that for each k, the expressive power of k -ary fixed-point logic, i. e. the fragment of fixed-point logic whose fixed-point operators are restricted to arity ≤ k, strictly exceeds the power of ( k − 1)-ary fixed-point logic. This solves a problem that was posed by Chandra and Harel in 1982. Our proof has a rather general form that applies to several variants of fixed-point logic and also to transitive-closure logic.

Details