Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualization
Not on the map. Why?
Abstract (arXiv)
We propose and study Hierarchical Ego Graph Neural Networks (HEGNNs), an expressive extension of graph neural networks (GNNs) with hierarchical node individualization, inspired by the Individualization-Refinement paradigm for isomorphism testing. HEGNNs generalize subgraph-GNNs and form a hierarchy of increasingly expressive models that, in the limit, distinguish graphs up to isomorphism. We show that, over graphs of bounded degree, the separating power of HEGNN node classifiers equals that of graded hybrid logic. This characterization enables us to relate the separating power of HEGNNs to that of higher-order GNNs, GNNs enriched with local homomorphism count features, and color refinement algorithms based on Individualization-Refinement. Our experimental results confirm the practical feasibility of HEGNNs and show benefits in comparison with traditional GNN architectures, both with and without local homomorphism count features.
Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 35 of its 60 references that are in the map. First posted on arXiv 16 Jun 2025.
Builds on
35 of 60 references.
References · 35
- 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
- 2017Neural Message Passing for Quantum Chemistrycited by 3,487
- 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,576
- 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
- 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 713
- 2020Benchmarking Graph Neural Networkscited by 680
- 2020A Generalization of Transformer Networks to Graphscited by 661
- 2020Principal Neighbourhood Aggregation for Graph Netscited by 478
- 2017Representation Learning on Graphs: Methods and Applicationscited by 457
- 2019Provably Powerful Graph Networkscited by 389
- 2021Graph Neural Networks with Learnable Structural and Positional Representationscited by 333
- 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 198
23 more
- 2021Identity-aware Graph Neural Networkscited by 198
- 2020Random Features Strengthen Graph Neural Networkscited by 186
- 2021From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awarenesscited by 155
- 2021Equivariant Subgraph Aggregation Networkscited by 154
- 2021Nested Graph Neural Networkscited by 137
- 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 122
- 2022Understanding and Extending Subgraph GNNs by Rethinking Their Symmetriescited by 112
- 2023Everything is Connected: Graph Neural Networkscited by 85
- 2021Reconstruction for Powerful Graph Representationscited by 65
- 2023A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Testscited by 64
- 2022Ordered Subgraph Aggregation Networkscited by 57
- 2021Graph Neural Networks with Local Graph Parameterscited by 52
- 2022A Theoretical Comparison of Graph Neural Network Extensionscited by 48
- 2020The expressive power of kth-order invariant graph networkscited by 34
- 2023On the Stability of Expressive Positional Encodings for Graphscited by 33
- 2023The Descriptive Complexity of Graph Neural Networkscited by 26
- 2025Learning Efficient Positional Encodings with Graph Neural Networkscited by 24
- 2024Homomorphism Counts for Graph Neural Networks: All About That Basiscited by 16
- 2024Decidability of Graph Neural Networks via Logical Characterizationscited by 14
- 2024Almost Surely Asymptotically Constant Graph Neural Networkscited by 7
- 2022Graph Representation Learning with Individualization and Refinementcited by 3
- 2021Improving the Expressive Power of Graph Neural Network with Tinhofer Algorithmcited by 1
- 2024Lov'asz Theorems for Modal Languagescited by 1
Built on by
Citing papers per year: 2025: 1; 2026: 2.
3 papers.