GNN Expressivity

GNN: Graph Neural Network

Overview

The field asks whether a graph neural network can distinguish non-isomorphic graphs or represent targets such as cycles, motifs, long-range relations, and node roles; this matters because benchmark accuracy alone does not reveal what information a model can capture. For standard message-passing networks, the one-dimensional Weisfeiler–Leman (1-WL) test is a key reference point, with higher-order WL tests, logic, graph homomorphisms, and circuit complexity providing tools to characterize expressive power. To exceed standard message passing, researchers study higher-order and subgraph methods, positional and spectral encodings, graph transformers, recurrent updates, and structural or topological features, often trading greater discrimination for computational cost and scalability. A central tension is that stronger theoretical expressivity does not guarantee that useful information can be learned reliably, while efficient models may retain WL-style blind spots; current analyses work to separate architectural limits from optimization and data effects.

Latest papers

CardsList

65 papers7 papers in the last four weeks, down 30% on the four weeks before. 0.1% of all new papers.

  1. Improving fine-grained expressivity of graph neural networks

    Nov 15, 2026Yonatan SverdlovGNN ExpressivityEquivariant GNNs

  2. Hierarchical Graph Representation Learning with Pooling-Induced Substructures

    Nov 10, 2026Luca Sbicego, Xiaowen Dong, Dorina ThanouGraph Representation LearningHierarchical GNNs

  3. Pricing Symbolic Rules by What GNNs Leave Unlearned

    Nov 9, 2026Satabarto Sarkar, Prithwineel PaulGraph Neural NetworksGraph Classification

  4. Attention at Absolute Zero

    Nov 9, 2026Mostafa 'Neo' MohsenvandAlgorithmic ReasoningHigher-Order GNNs

  5. Message-passing graph persistence

    Nov 4, 2026Jorge Luiz Franco, Arthur Queiroz Moura, Moacir Ponti +1Persistent HomologyTopological Representation Learning

  6. Invertible Graph Aggregation Can Increase ReLU Readout Width

    Nov 1, 2026Hiroyasu Usami, Masanori Tsukamoto, Kohei HashiguchiGraph Neural NetworksGNN Expressivity

  7. On Counting Graphs for Modal Logic with Counting

    Oct 19, 2026Avijeet Ghosh, François SchwarzentruberGNN Expressivity

  8. Emergent Loop Geometry in Gauge-Equivariant Graph Neural Networks

    Oct 13, 2026Ali Rayat, Gia-Wei ChernEquivariant GNNsGNN Expressivity

  9. Random Probing for Structural Self-Interactions in Graph Neural Networks

    Oct 13, 2026Saku Peltonen, H. Çağrı Bilgi, Kubilay AtasuGraph Neural NetworksGraph Representation Learning

  10. Constant-Depth Rational-Weight GNNs and their Connection to Schanuel's Conjecture

    Oct 12, 2026Daumantas Kojelis, Carsten LutzGraph Neural NetworksGNN Expressivity

  11. The Expressive Power of Random-Feature MPNNs Across Graph Sizes

    Oct 8, 2026Robert R. Nerem, Mitchell Black, Antonis Vasileiou +2GNN ExpressivityMessage Passing Neural Networks

  12. Oscillatory Neural Dynamics over Sheaves

    Oct 7, 2026Jan-Willem Van Looy, Alessandro Trenta, Alessio Gravina +5Long-Range Graph LearningGraph Neural Networks

  13. Get a GRIP, this will be a long TRIP: A Quantifiable Long-Range Framework for Verifying Over-squashing

    Oct 2, 2026Ferran Hernandez Caralt, Simon Heilig, Adrián Bazaga +3Long-Range Graph LearningOver-Squashing in GNNs

  14. Edge-Level Automorphism in GNNs: A Quantitative Framework and Effective Designs For Link Prediction

    Sep 28, 2026Chen Shao, Donald Loveland, Tobias Käfer +1Link PredictionGNN Expressivity

  15. Reachability is not enough: Diagnosing long-range behavior in GNNs

    Sep 27, 2026Filippo Maria BianchiGraph Neural NetworksGNN Expressivity

  16. Repurposing Unified Topological Signatures for Graph Representation Learning

    Sep 15, 2026Sanyam Sanjay Jain, Anshika Krishnatray, Aditya Sharma +1Graph Representation LearningGNN Expressivity

  17. Recurrent Graph Neural Networks with Set-Based Aggregation

    Sep 14, 2026Blai BonetGraph Neural NetworksGNN Expressivity

  18. Edge-Girth as a Structural Edge Feature for Graph Neural Networks

    Sep 1, 2026Lilian Marey, Charlotte LaclauGraph Neural NetworksGraph Representation Learning

  19. Why Multi-Layer Message Passing Works: Completeness Theory for Graph Neural Network Interatomic Potentials

    Sep 1, 2026Pingbing Ming, Han WangMachine Learning Interatomic PotentialsGNN Expressivity

  20. A Unifying Relational Perspective on Expressive Lottery Tickets

    Aug 19, 2026Lorenz Kummer, Samir Moustafa, Anatol Ehrlich +4Graph Neural NetworksGNN Expressivity

  21. The Boolean Power of ReLU

    Aug 12, 2026Pablo Barceló, Floris Geerts, Matthias Lanzinger +2ReLU Neural NetworksGNN Expressivity

  22. When GNNs Fail: Quantifying and Overcoming Temporal Correlation Volatility in Time Series

    Aug 7, 2026Chen Shao, Yue Wang, Zhenyi Zhu +4Multivariate Time Series ForecastingTemporal GNNs

  23. Universality and Approximation Rates of Graph Neural Networks with Random Features

    Jul 29, 2026Lukas Gonon, Thilo Meyer-Brandis, Niklas WeberGraph Neural NetworksEquivariant Neural Networks

  24. CondPSE: A Polynomial-Filtered Structural Encoder with Conditional Modulation for Graphs

    Jul 28, 2026Woohyun Lee, Hogun ParkGraph Representation LearningGraph SSL

  25. A Weisfeiler-Leman Characterization of Global-Attention Graph Transformers for Mixed-Integer Linear Programs

    Jul 20, 2026Md Abrar Jahin, Craig A. Knoblock, Jay PujaraMixed-Integer Linear ProgrammingGNN Expressivity