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
We investigate message-passing graph neural networks with random node features. Random node features are known to enhance the expressiveness of graph neural networks (GNNs) both theoretically and empirically.
arXiv:2510. 10101v4 Announce Type: replace Abstract: Understanding the interplay between generalization, expressivity, and the geometry of the input space is a central challenge in graph learning.
By Martin Carrasco, Caio F. Deberaldini Netto, Vahan A. Martirosyan, Ehimare Okoyomon, Caterina Graziani
arXiv:2601. 23207v2 Announce Type: replace-cross Abstract: Understanding what graph neural networks can learn, especially their ability to learn to execute algorithms, remains a central theoretical challenge.
By Muhammad Fetrat Qharabagh, Artur Back de Luca, George Giapitzakis, Kimon Fountoulakis
arXiv:2412. 19419v2 Announce Type: replace-cross Abstract: Graph neural networks are deep neural networks designed for graphs with attributes attached to nodes or edges.
By James H. Tanis, Chris Giannella, Adrian V. Mariano, Daoud Meerzaman
arXiv:2607. 26699v1 Announce Type: new Abstract: We investigate message-passing graph neural networks with random node features.
By Lukas Gonon, Thilo Meyer-Brandis, Niklas Weber
arXiv:2606. 07598v1 Announce Type: cross Abstract: We propose a topological framework for comparing trained Graph Neural Networks (GNNs) by mapping the Stochastic Block Models (SBMs) induced on the graphon-signal space of a Message Passing Neural Network (MPNN) onto the unit $n$-sphere $\sphere^{n-1}\subset\R^n$.
By Gopal Anantharaman
arXiv:2606. 26662v1 Announce Type: cross Abstract: Graph Neural Differential Equations (GNDEs) model continuous-time graph dynamics by parameterizing Neural ODE velocity fields with Graph Neural Networks.
By Mingsong Yan, Zhida Wang, Sui Tang
Positional encodings (PEs) enhance the power of graph neural networks (GNNs), both theoretically and empirically. Two of the most popular families of PEs - spectral (e.
arXiv:2311. 07073v3 Announce Type: replace Abstract: Graph-based message-passing neural networks (MPNNs) have achieved remarkable success in both node and graph-level learning tasks.
By Dai Shi, Andi Han, Lequan Lin, Yi Guo, Junbin Gao
arXiv:2607. 03109v1 Announce Type: cross Abstract: We study a graph classification problem involving over 20 million graphs, arising from high-order perturbative computations of correlators in planar $\mathcal{N}=4$ super-Yang--Mills, a model closely related to the theory of the strong nuclear force.
By Rigers Aliaj, Gabriele Dian, Reza Doobary, Paul Heslop
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