The Correspondence Between Bounded Graph Neural Networks and Fragments of First-Order Logic
Graph Neural Networks (GNNs) address two key challenges in applying deep learning to graph-structured data: they handle varying size input graphs and ensure invariance under graph isomorphism. While GNNs have demonstrated broad applicability, understanding their expressive power remains an important question. In this paper, we show that bounded GNN architectures correspond to specific fragments of first-order logic (FO), including modal logic (ML), graded modal logic (GML), modal logic with the universal modality (ML(A)), the two-variable fragment (FO2) and its extension with counting quantifiers (C2). To establish these results, we apply methods and tools from finite model theory of first-order and modal logics to the domain of graph representation learning. This provides a unifying framework for understanding the logical expressiveness of GNNs within FO.
Code (0)
등록된 구현이 없습니다.
Tasks
Graph Representation LearningRepresentation LearningSimilar Papers 제목 키워드 기반
Tractable Weighted First-Order Model Counting with Bounded Treewidth Binary Evidence
The Weighted First-Order Model Counting Problem (WFOMC) asks to compute the weighted sum of models of a given first-order logic sentence over a given domain. Conditioning WFOMC on evidence -- fixing the truth values of a…
Clique-Width and Directed Width Measures for Answer-Set Programming
Disjunctive Answer Set Programming (ASP) is a powerful declarative programming paradigm whose main decision problems are located on the second level of the polynomial hierarchy. Identifying tractable fragments and develo…
Exact alignment recovery for correlated Erdős-Rényi graphs
We consider the problem of perfectly recovering the vertex correspondence between two correlated Erd\H{o}s-R\'enyi (ER) graphs on the same vertex set. The correspondence between the vertices can be obscured by randomly p…
Expressive Power of Deep Homomorphism Networks over Relational Databases
The expressive limitations of message-passing Graph Neural Networks (GNNs) have motivated a wide range of more powerful graph learning architectures. We advocate Deep Homomorphism Networks (DHNs) as a model particularly …
Graph LearningCorrelated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities
We consider the task of learning latent community structure from multiple correlated networks. First, we study the problem of learning the latent vertex correspondence between two edge-correlated stochastic block models,…
Graph Matching