The paper introduces recurrent Graph Neural Networks (GNNs) that use set-based aggregation and establishes conditions that can be verified directly from the network weights. It proves a two‑directional equivalence between these networks and the Boolean closure of reachability and safety properties, corresponding to the fragment BΣ◦₁ of the modal μ‑calculus. This equivalence allows for verifiable symbolic explanations of networks that satisfy the identified conditions, without relying on counting logic or external halting signals.
By Blai Bonet
arXiv:2608. 11136v1 Announce Type: new Abstract: Logic Tensor Networks (LTN) provide a neurosymbolic framework in which first-order logic is interpreted through tensor operations, enabling logical constraints to be integrated with differentiable learning.
By Davide Rinaldi, Luciano Serafini
The paper introduces a logic-based framework that extracts global logical rules for node classification in Simple Graph Convolution (SGC) networks. It uses minimal abductive explanations—small sets of node-feature pairs that preserve a node’s predicted class—as an intermediate step. Decision trees trained on these explanations yield compact global rules that retain high fidelity to the original SGC model, as demonstrated on benchmark datasets.
By Bryan Lima Cavalcante, Thiago Alves Rocha
The paper presents a complete characterization of when two deep ReLU networks realize the same function, showing that this occurs iff one can be transformed into the other using a set of axioms from many‑valued logic. It introduces a symbolic calculus that maps networks to substitution graphs, proves a completeness theorem linking equivalent formulas, and provides an algorithm to reconstruct networks from these graphs. The framework yields a new compositional normal form for MV logic that preserves the algebraic structure of deep ReLU networks.
By Yani Zhang, Helmut B\"olcskei
arXiv:2603. 14846v3 Announce Type: replace Abstract: We define an information-complexity property for aggregation functions, capturing a vast range of practical aggregations, and prove that any Message-Passing Graph Neural Network (MP-GNN) model with such aggregations induces only a polynomial number of equivalence classes on all graphs - while the number of non-isomorphic graphs is super-exponential (in number of vertices).
By Eran Rosenbluth
arXiv:2606. 11946v1 Announce Type: cross Abstract: The conventional approach to deep learning over relational databases applies neural models, such as Graph Neural Networks (GNNs), to a graph representation of the database.
By Arie Soeteman, Balder ten Cate, Maurice Funk, Benny Kimelfeld, Carsten Lutz, Moritz Sch\"onherr
The conventional approach to deep learning over relational databases applies neural models, such as Graph Neural Networks (GNNs), to a graph representation of the database. Recent approaches instead operate on databases directly, associating tuples with embeddings and extending query mechanisms to jointly process embeddings and relational content.
arXiv:2602. 10031v2 Announce Type: replace Abstract: Graph neural networks (GNNs) are commonly divided into message-passing neural networks (MPNNs) and spectral GNNs, reflecting two largely separate research traditions in machine learning and signal processing.
By Antonis Vasileiou, Juan Cervino, Pascal Frossard, Charilaos I. Kanatsoulis, Christopher Morris, Michael T. Schaub, Pierre Vandergheynst, Zhiyang Wang, Guy Wolf, Ron Levie
arXiv:2602.13106v2 Announce Type: replace-cross
Abstract: In recent years, there has been growing interest in understanding neural architectures' ability to learn to execute discrete algorithms, a li...
By Solveig Wittig, Antonis Vasileiou, Robert R. Nerem, Timo Stoll, Floris Geerts, Yusu Wang, Christopher Morris
arXiv:2605. 00725v2 Announce Type: replace Abstract: Topological neural networks have emerged as effective tools for modeling higher-order relational structures beyond pairwise graphs, including hypergraphs, simplicial complexes, and cell complexes.
By Jiawen Chen, Qi Shao, Zhiqiang Ge, Duxin Chen, Wenwu Yu
arXiv:2607. 17570v1 Announce Type: new Abstract: Graph foundation models (GFMs) with global attention are increasingly used to represent mixed-integer linear programs (MILPs), aiming to capture structure beyond the locality of standard graph neural networks.
By Md Abrar Jahin, Craig A. Knoblock, Jay Pujara
arXiv:2502. 16533v3 Announce Type: replace-cross Abstract: Graph Transformers (GTs) have demonstrated a strong capability in modeling graph structures by addressing the intrinsic limitations of graph neural networks (GNNs), such as over-smoothing and over-squashing.
By Chaohao Yuan, Kangfei Zhao, Ercan Engin Kuruoglu, Liang Wang, Tingyang Xu, Wenbing Huang, Deli Zhao, Hong Cheng, Yu Rong