6 papers
A Rank-Preserving Gaifman Normal Form for First-Order Logic on Weighted Structures
Steffen van Bergerem, Martin Grohe, Charlotte Lenz +1
We prove a rank-preserving version of Gaifman's Theorem. Compared to earlier rank-preserving locality theorems (in particular, [Grohe, Kreutzer, Siebertz, JACM 2017]), our theorem…
A Rank-Preserving Gaifman Normal Form
Martin Grohe, Nicole Schweikardt
We introduce a rank measure for first-order logic and prove a "rank-preserving'" version of Gaifman's theorem. Compared to earlier "rank-preserving locality theorems'" (in particul…
Robust Graph Isomorphism, Quadratic Assignment and VC Dimension
Anatole Dahan, Martin Grohe, Daniel Neuen +1
We present an additive -approximation algorithm for the Graph Edit Distance problem (GED) on graphs of VC dimension running in time $n^{O(d/\varepsilon^{2})}…
How Expressive Are Graph Neural Networks in the Presence of Node Identifiers?
Arie Soeteman, Michael Benedikt, Martin Grohe +1
Graph neural networks (GNNs) are a widely used class of machine learning models for graph-structured data, based on local aggregation over neighbors. GNNs have close connections to…
Query Languages for Machine-Learning Models
Martin Grohe
In this paper, I discuss two logics for weighted finite structures: first-order logic with summation (FO(SUM)) and its recursive extension IFP(SUM). These logics originate from fou…
Some Thoughts on Graph Similarity
Martin Grohe
We give an overview of different approaches to measuring the similarity of, or the distance between, two graphs, highlighting connections between these approaches. We also discuss…