research
∙
09/19/2023
On the Parameterized Complexity of Learning Monadic Second-Order Formulas
Within the model-theoretic framework for supervised learning introduced ...
share
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...
research
∙
08/29/2023
Structural Node Embeddings with Homomorphism Counts
Graph homomorphism counts, first explored by Lovász in 1967, have recent...
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...
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 ...
research
∙
03/08/2023
The Descriptive Complexity of Graph Neural Networks
We analyse the power of graph neural networks (GNNs) in terms of Boolean...
research
∙
02/22/2023
Some Might Say All You Need Is Sum
The expressivity of Graph Neural Networks (GNNs) is dependent on the agg...
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...
research
∙
01/26/2023
WL meet VC
Recently, many works studied the expressive power of graph neural networ...
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...
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...
research
∙
06/30/2022
Graph Similarity Based on Matrix Norms
Quantifying the similarity between two graphs is a fundamental algorithm...
research
∙
06/01/2022
Graph Machine Learning for Design of High-Octane Fuels
Fuels with high-knock resistance enable modern spark-ignition engines to...
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...
research
∙
01/27/2022
Probabilistic Query Evaluation with Bag Semantics
We initiate the study of probabilistic query evaluation under bag semant...
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...
research
∙
11/22/2021
Homomorphism Tensors and Linear Equations
Lovász (1967) showed that two graphs G and H are isomorphic if and only ...
research
∙
06/30/2021
Logarithmic Weisfeiler-Leman Identifies All Planar Graphs
The Weisfeiler-Leman (WL) algorithm is a well-known combinatorial proced...
research
∙
04/29/2021
The Logic of Graph Neural Networks
Graph neural networks (GNNs) are deep learning architectures for machine...
research
∙
03/11/2021
Dynamic Database Embeddings with FoRWaRD
We study the problem of computing an embedding of the tuples of a relati...
research
∙
02/24/2021
On the Parameterized Complexity of Learning Logic
We analyse the complexity of learning first-order definable concepts in ...
research
∙
02/17/2021
Graph Learning with 1D Convolutions on Random Walks
We propose CRaWl (CNNs for Random Walks), a novel neural network archite...
research
∙
01/28/2021
Probabilistic Data with Continuous Distributions
Statistical models of real world data typically involve continuous proba...
research
∙
12/28/2020
Automorphism groups of graphs of bounded Hadwiger number
We determine the structure of automorphism groups of finite graphs of bo...
research
∙
11/30/2020
Standard Probabilistic Databases
Probabilistic databases (PDBs) model uncertainty in data in a quantitati...
research
∙
11/02/2020
Recent Advances on the Graph Isomorphism Problem
We give an overview of recent advances on the graph isomorphism problem....
research
∙
10/30/2020
Independence in Infinite Probabilistic Databases
Probabilistic databases (PDBs) model uncertainty in data. The current st...
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...
research
∙
09/29/2020
Database Repairing with Soft Functional Dependencies
A common interpretation of soft constraints penalizes the database for e...
research
∙
08/21/2020
Tuple-Independent Representations of Infinite Probabilistic Databases
Probabilistic databases (PDBs) are probability spaces over database inst...
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...
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...
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...
research
∙
03/24/2020
Deep Weisfeiler Leman
We introduce the framework of Deep Weisfeiler Leman algorithms (DeepWL),...
research
∙
03/18/2020
Counting Bounded Tree Depth Homomorphisms
We prove that graphs G, G' satisfy the same sentences of first-order log...
research
∙
01/17/2020
Generative Datalog with Continuous Distributions
Arguing for the need to combine declarative and probabilistic programmin...
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...
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...
research
∙
04/14/2019
Infinite Probabilistic Databases
Probabilistic databases (PDBs) are used to model uncertainty in data in ...
research
∙
01/29/2019
Canonisation and Definability for Graphs of Bounded Rank Width
We prove that the combinatorial Weisfeiler-Leman algorithm of dimension ...
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...
research
∙
07/02/2018
Probabilistic Databases with an Infinite Open-World Assumption
Probabilistic databases (PDBs) introduce uncertainty into relational dat...
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...
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...
research
∙
02/26/2018
A Finite-Model-Theoretic View on Propositional Proof Complexity
We establish new, and surprisingly tight, connections between propositio...
research
∙
02/24/2018
Weisfeiler-Leman meets Homomorphisms
In this paper, we relate a beautiful theory by Lovász with a popular heu...
research
∙
02/23/2018
Graph Similarity and Approximate Isomorphism
The graph similarity problem, also known as approximate graph isomorphis...
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...
research
∙
02/13/2018
Towards faster isomorphism tests for bounded-degree graphs
Luks' algorithm (JCSS 1982) to test isomorphism of bounded degree graphs...
research
∙
11/13/2017