b'Martin Grohe'

research

∙ 09/19/2023

On the Parameterized Complexity of Learning Monadic Second-Order Formulas

Within the model-theoretic framework for supervised learning introduced ...

0 Steffen van Bergerem, et al. ∙

research

∙ 09/01/2023

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

The recent Long-Range Graph Benchmark (LRGB, Dwivedi et al. 2022) introd...

0 Jan Tönshoff, et al. ∙

research

∙ 08/29/2023

Structural Node Embeddings with Homomorphism Counts

Graph homomorphism counts, first explored by Lovász in 1967, have recent...

0 Hinrikus Wolf, et al. ∙

research

∙ 08/23/2023

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

The k-dimensional Weisfeiler-Leman (k-WL) algorithm is a simple combinat...

0 Martin Grohe, et al. ∙

research

∙ 04/25/2023

Simulating Logspace-Recursion with Logarithmic Quantifier Depth

The fixed-point logic LREC= was developed by Grohe et al. (CSL 2011) in ...

0 Steffen van Bergerem, et al. ∙

research

∙ 03/08/2023

The Descriptive Complexity of Graph Neural Networks

We analyse the power of graph neural networks (GNNs) in terms of Boolean...

0 Martin Grohe, et al. ∙

research

∙ 02/22/2023

Some Might Say All You Need Is Sum

The expressivity of Graph Neural Networks (GNNs) is dependent on the agg...

0 Eran Rosenbluth, et al. ∙

research

∙ 01/30/2023

The Iteration Number of the Weisfeiler-Leman Algorithm

We prove new upper and lower bounds on the number of iterations the k-di...

0 Martin Grohe, et al. ∙

research

∙ 01/26/2023

WL meet VC

Recently, many works studied the expressive power of graph neural networ...

0 Christopher Morris, et al. ∙

research

∙ 08/22/2022

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

We propose a universal Graph Neural Network architecture which can be tr...

20 Jan Tönshoff, et al. ∙

research

∙ 07/27/2022

Physical Pooling Functions in Graph Neural Networks for Molecular Property Prediction

Graph neural networks (GNNs) are emerging in chemical engineering for th...

10 Artur M. Schweidtmann, et al. ∙

research

∙ 06/30/2022

Graph Similarity Based on Matrix Norms

Quantifying the similarity between two graphs is a fundamental algorithm...

0 Timo Gervens, et al. ∙

research

∙ 06/01/2022

Graph Machine Learning for Design of High-Octane Fuels

Fuels with high-knock resistance enable modern spark-ignition engines to...

6 Jan G. Rittig, et al. ∙

research

∙ 04/14/2022

Solving AC Power Flow with Graph Neural Networks under Realistic Constraints

In this paper we propose a graph neural network architecture solving the...

9 Luis Böttcher, et al. ∙

research

∙ 01/27/2022

Probabilistic Query Evaluation with Bag Semantics

We initiate the study of probabilistic query evaluation under bag semant...

0 Martin Grohe, et al. ∙

research

∙ 12/18/2021

Weisfeiler and Leman go Machine Learning: The Story so far

In recent years, algorithms and neural architectures based on the Weisfe...

65 Christopher Morris, et al. ∙

research

∙ 11/22/2021

Homomorphism Tensors and Linear Equations

Lovász (1967) showed that two graphs G and H are isomorphic if and only ...

0 Martin Grohe, et al. ∙

research

∙ 06/30/2021

Logarithmic Weisfeiler-Leman Identifies All Planar Graphs

The Weisfeiler-Leman (WL) algorithm is a well-known combinatorial proced...

0 Martin Grohe, et al. ∙

research

∙ 04/29/2021

The Logic of Graph Neural Networks

Graph neural networks (GNNs) are deep learning architectures for machine...

50 Martin Grohe, et al. ∙

research

∙ 03/11/2021

Dynamic Database Embeddings with FoRWaRD

We study the problem of computing an embedding of the tuples of a relati...

0 Jan Toenshoff, et al. ∙

research

∙ 02/24/2021

On the Parameterized Complexity of Learning Logic

We analyse the complexity of learning first-order definable concepts in ...

0 Steffen van Bergerem, et al. ∙

research

∙ 02/17/2021

Graph Learning with 1D Convolutions on Random Walks

We propose CRaWl (CNNs for Random Walks), a novel neural network archite...

13 Jan Toenshoff, et al. ∙

research

∙ 01/28/2021

Probabilistic Data with Continuous Distributions

Statistical models of real world data typically involve continuous proba...

0 Martin Grohe, et al. ∙

research

∙ 12/28/2020

Automorphism groups of graphs of bounded Hadwiger number

We determine the structure of automorphism groups of finite graphs of bo...

0 Martin Grohe, et al. ∙

research

∙ 11/30/2020

Standard Probabilistic Databases

Probabilistic databases (PDBs) model uncertainty in data in a quantitati...

0 Martin Grohe, et al. ∙

research

∙ 11/02/2020

Recent Advances on the Graph Isomorphism Problem

We give an overview of recent advances on the graph isomorphism problem....

0 Martin Grohe, et al. ∙

research

∙ 10/30/2020

Independence in Infinite Probabilistic Databases

Probabilistic databases (PDBs) model uncertainty in data. The current st...

0 Martin Grohe, et al. ∙

research

∙ 10/02/2020

The Surprising Power of Graph Neural Networks with Random Node Initialization

Graph neural networks (GNNs) are effective models for representation lea...

0 Ralph Abboud, et al. ∙

research

∙ 09/29/2020

Database Repairing with Soft Functional Dependencies

A common interpretation of soft constraints penalizes the database for e...

0 Nofar Carmeli, et al. ∙

research

∙ 08/21/2020

Tuple-Independent Representations of Infinite Probabilistic Databases

Probabilistic databases (PDBs) are probability spaces over database inst...

0 Nofar Carmeli, et al. ∙

research

∙ 05/20/2020

The Effects of Randomness on the Stability of Node Embeddings

We systematically evaluate the (in-)stability of state-of-the-art node e...

2 Tobias Schumacher, et al. ∙

research

∙ 04/16/2020

Isomorphism Testing for Graphs Excluding Small Minors

We prove that there is a graph isomorphism test running in time n^polylo...

0 Martin Grohe, et al. ∙

research

∙ 03/27/2020

word2vec, node2vec, graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Data

Vector representations of graphs and relational structures, whether hand...

0 Martin Grohe, et al. ∙

research

∙ 03/24/2020

Deep Weisfeiler Leman

We introduce the framework of Deep Weisfeiler Leman algorithms (DeepWL),...

0 Martin Grohe, et al. ∙

research

∙ 03/18/2020

Counting Bounded Tree Depth Homomorphisms

We prove that graphs G, G' satisfy the same sentences of first-order log...

0 Martin Grohe, et al. ∙

research

∙ 01/17/2020

Generative Datalog with Continuous Distributions

Arguing for the need to combine declarative and probabilistic programmin...

0 Martin Grohe, et al. ∙

research

∙ 09/18/2019

RUN-CSP: Unsupervised Learning of Message Passing Networks for Binary Constraint Satisfaction Problems

Constraint satisfaction problems form an important and wide class of com...

7 Jan Toenshoff, et al. ∙

research

∙ 04/15/2019

A Linear Upper Bound on the Weisfeiler-Leman Dimension of Graphs of Bounded Genus

The Weisfeiler-Leman (WL) dimension of a graph is a measure for the inhe...

0 Martin Grohe, et al. ∙

research

∙ 04/14/2019

Infinite Probabilistic Databases

Probabilistic databases (PDBs) are used to model uncertainty in data in ...

0 Martin Grohe, et al. ∙

research

∙ 01/29/2019

Canonisation and Definability for Graphs of Bounded Rank Width

We prove that the combinatorial Weisfeiler-Leman algorithm of dimension ...

0 Martin Grohe, et al. ∙

research

∙ 10/04/2018

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

In recent years, graph neural networks (GNNs) have emerged as a powerful...

0 Christopher Morris, et al. ∙

research

∙ 07/02/2018

Probabilistic Databases with an Infinite Open-World Assumption

Probabilistic databases (PDBs) introduce uncertainty into relational dat...

0 Martin Grohe, et al. ∙

research

∙ 03/19/2018

An improved isomorphism test for bounded-tree-width graphs

We give a new fpt algorithm testing isomorphism of n-vertex graphs of tr...

0 Martin Grohe, et al. ∙

research

∙ 03/15/2018

Definable decompositions for graphs of bounded linear cliquewidth

We prove that for every positive integer k, there exists an MSO_1-transd...

0 Mikołaj Bojańczyk, et al. ∙

research

∙ 02/26/2018

A Finite-Model-Theoretic View on Propositional Proof Complexity

We establish new, and surprisingly tight, connections between propositio...

0 Erich Grädel, et al. ∙

research

∙ 02/24/2018

Weisfeiler-Leman meets Homomorphisms

In this paper, we relate a beautiful theory by Lovász with a popular heu...

0 Holger Dell, et al. ∙

research

∙ 02/23/2018

Graph Similarity and Approximate Isomorphism

The graph similarity problem, also known as approximate graph isomorphis...

0 Martin Grohe, et al. ∙

research

∙ 02/13/2018

A Faster Isomorphism Test for Graphs of Small Degree

Luks's algorithm (JCSS 1982) to test isomorphism of bounded degree graph...

0 Martin Grohe, et al. ∙

research

∙ 02/13/2018

Towards faster isomorphism tests for bounded-degree graphs

Luks' algorithm (JCSS 1982) to test isomorphism of bounded degree graphs...

0 Martin Grohe, et al. ∙

research

∙ 11/13/2017

Constraint Solving via Fractional Edge Covers

Many important combinatorial problems can be modeled as constraint satis...

0 Martin Grohe, et al. ∙

Martin Grohe

Featured Co-authors