mlsanityData to 13 Oct 2026

Nested Graph Neural Networks

arXiv 2110.13197 ↗First posted 25 Oct 2021cs.LGcited by 136

Not on the map. Why?

Abstract (arXiv)

Graph neural network (GNN)'s success in graph classification is closely related to the Weisfeiler-Lehman (1-WL) algorithm. By iteratively aggregating neighboring node features to a center node, both 1-WL and GNN obtain a node representation that encodes a rooted subtree around the center node. These rooted subtree representations are then pooled into a single representation to represent the whole graph. However, rooted subtrees are of limited expressiveness to represent a non-tree graph. To address it, we propose Nested Graph Neural Networks (NGNNs). NGNN represents a graph with rooted subgraphs instead of rooted subtrees, so that two graphs sharing many identical subgraphs (rather than subtrees) tend to have similar representations. The key is to make each node representation encode a subgraph around it more than a subtree. To achieve this, NGNN extracts a local subgraph around each node and applies a base GNN to each subgraph to learn a subgraph representation. The whole-graph representation is then obtained by pooling these subgraph representations. We provide a rigorous theoretical analysis showing that NGNN is strictly more powerful than 1-WL. In particular, we proved that NGNN can discriminate almost all r-regular graphs, where 1-WL always fails. Moreover, unlike other more powerful GNNs, NGNN only introduces a constant-factor higher time complexity than standard GNNs. NGNN is a plug-and-play framework that can be combined with various base GNNs. We test NGNN with different base GNNs on several benchmark datasets. NGNN uniformly improves their performance and shows highly competitive performance on all datasets.

Key facts. Cited by 136 papers in the map (data through 13 Oct 2026). Builds on 48 of its 72 references that are in the map. First posted on arXiv 25 Oct 2021.

Builds on

48 of 72 references.

References · 48

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,318
  2. 2017Graph Attention Networkscited by 8,888
  3. 2017Inductive Representation Learning on Large Graphscited by 6,303
  4. 2018How Powerful are Graph Neural Networks?cited by 4,373
  5. 2017Neural Message Passing for Quantum Chemistrycited by 3,471
  6. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,422
  7. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,157
  8. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,086
  9. 2014DeepWalk: Online Learning of Social Representationscited by 1,544
  10. 2017Deep Setscited by 1,404
  11. 2013Spectral Networks and Locally Connected Networks on Graphscited by 1,101
  12. 2017MoleculeNet: A Benchmark for Molecular Machine Learningcited by 1,043
36 more
  1. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  2. 2018Link Prediction Based on Graph Neural Networkscited by 829
  3. 2015Gated Graph Sequence Neural Networkscited by 794
  4. 2018Hierarchical Graph Representation Learning with Differentiable Poolingcited by 787
  5. 2015Convolutional Networks on Graphs for Learning Molecular Fingerprintscited by 753
  6. 2020Directional Message Passing for Molecular Graphscited by 559
  7. 2019Graph U-Netscited by 492
  8. 2020Principal Neighbourhood Aggregation for Graph Netscited by 478
  9. 2019MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixingcited by 443
  10. 2019Provably Powerful Graph Networkscited by 386
  11. 2018Invariant and Equivariant Graph Networkscited by 341
  12. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 312
  13. 2019Cormorant: Covariant Molecular Neural Networkscited by 263
  14. 2020DeeperGCN: All You Need to Train Deeper GCNscited by 250
  15. 2019A Fair Comparison of Graph Neural Networks for Graph Classificationcited by 244
  16. 2020Can Graph Neural Networks Count Substructures?cited by 235
  17. 2019What graph neural networks cannot learn: depth vs widthcited by 198
  18. 2021Identity-aware Graph Neural Networkscited by 197
  19. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 192
  20. 2020Random Features Strengthen Graph Neural Networkscited by 184
  21. 2019Universal Invariant and Equivariant Graph Neural Networkscited by 182
  22. 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
  23. 2019On the Universality of Invariant Networkscited by 151
  24. 2019Relational Pooling for Graph Representationscited by 150
  25. 2020Directional Graph Networkscited by 132
  26. 2016Discriminative Embeddings of Latent Variable Models for Structured Datacited by 130
  27. 2020Building powerful and equivariant graph neural networks with structural message-passingcited by 95
  28. 2020Graph Meta Learning via Local Subgraphscited by 89
  29. 2014Propagation Kernelscited by 88
  30. 2019Inductive Matrix Completion Based on Graph Neural Networkscited by 85
  31. 2020OrbNet: Deep Learning for Quantum Chemistry Using Symmetry-Adapted Atomic-Orbital Featurescited by 63
  32. 2019k-hop Graph Neural Networkscited by 57
  33. 2019Coloring graph neural networks for node disambiguationcited by 50
  34. 2020Graph convolutions that can finally model local structurecited by 31
  35. 2020Deep Graph Neural Networks with Shallow Subgraph Samplerscited by 16
  36. 2019Graph Warp Module: an Auxiliary Module for Boosting the Power of Graph Neural Networks in Molecular Graph Analysiscited by 10

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2021: 2; 2022: 30; 2023: 44; 2024: 34; 2025: 20; 2026: 6.

136 papers.

Sort:

By area:

  1. 2022Long Range Graph Benchmarkcited by 261
  2. 2023One for All: Towards Training One Graph Model for All Classification Taskscited by 240
  3. 2022Structure-Aware Transformer for Graph Representation Learningcited by 191
  4. 2022How Powerful are Spectral Graph Neural Networkscited by 169
  5. 2022Data Augmentation for Deep Graph Learning: A Surveycited by 133
  6. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 121
  7. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  8. 2022Understanding and Extending Subgraph GNNs by Rethinking Their Symmetriescited by 112
  9. 2022Universal Prompt Tuning for Graph Neural Networkscited by 100
  10. 2022SPECTRE: Spectral Conditioning Helps to Overcome the Expressivity Limits of One-shot Graph Generatorscited by 98
  11. 2022Brain Network Transformercited by 93
  12. 2022A Generalization of ViT/MLP-Mixer to Graphscited by 93
38 more
  1. 2022How Powerful are K-hop Message Passing Graph Neural Networkscited by 90
  2. 2023DRew: Dynamically Rewired Message Passing with Delaycited by 82
  3. 2022Graph Neural Networks for Link Prediction with Subgraph Sketchingcited by 81
  4. 2023A Comprehensive Survey on Deep Graph Representation Learningcited by 72
  5. 2022A Survey on Graph Representation Learning Methodscited by 66
  6. 2023A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Testscited by 64
  7. 2022Ordered Subgraph Aggregation Networkscited by 57
  8. 2023CktGNN: Circuit Graph Neural Network for Electronic Design Automationcited by 57
  9. 2024GOFA: A Generative One-For-All Model for Joint Graph Language Modelingcited by 56
  10. 2022Boosting the Cycle Counting Power of Graph Neural Networks with I2-GNNscited by 55
  11. 2022A Theoretical Comparison of Graph Neural Network Extensionscited by 47
  12. 2022Shortest Path Networks for Graph Property Predictioncited by 46
  13. 2024Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressivenesscited by 39
  14. 2023Equivariant Polynomials for Graph Neural Networkscited by 38
  15. 2022SpeqNets: Sparsity-aware Permutation-equivariant Graph Networkscited by 37
  16. 2023An Empirical Study of Realized GNN Expressivenesscited by 33
  17. 2023Path Neural Networks: Expressive and Accurate Graph Neural Networkscited by 32
  18. 2023On the Stability of Expressive Positional Encodings for Graphscited by 32
  19. 2023WL meet VCcited by 30
  20. 2023Graph Positional Encoding via Random Feature Propagationcited by 30
  21. 2024A Survey of Geometric Graph Neural Networks: Data Structures, Models and Applicationscited by 28
  22. 2023The Expressive Power of Graph Neural Networks: A Surveycited by 27
  23. 2023Provably Powerful Graph Neural Networks for Directed Multigraphscited by 25
  24. 2024Unifying Generation and Prediction on Graphs with Latent Graph Diffusioncited by 25
  25. 2023Is Distance Matrix Enough for Geometric Deep Learning?cited by 22
  26. 2022PACE: A Parallelizable Computation Encoder for Directed Acyclic Graphscited by 20
  27. 2022A Practical, Progressively-Expressive GNNcited by 20
  28. 2022Understanding Non-linearity in Graph Neural Networks from the Bayesian-Inference Perspectivecited by 19
  29. 2022Geodesic Graph Neural Network for Efficient Graph Representation Learningcited by 19
  30. 2023Pure Message Passing Can Estimate Common Neighbor for Link Predictioncited by 18
  31. 2023From Relational Pooling to Subgraph GNNs: A Universal Framework for More Expressive Graph Neural Networkscited by 17
  32. 2023Efficient Subgraph GNNs by Learning Effective Selection Policiescited by 17
  33. 2022Going Deeper into Permutation-Sensitive Graph Neural Networkscited by 15
  34. 2023GraphGPT: Generative Pre-trained Graph Eulerian Transformercited by 15
  35. 2024On the Expressive Power of Spectral Invariant Graph Neural Networkscited by 15
  36. 2023Are More Layers Beneficial to Graph Transformers?cited by 14
  37. 2023CIN++: Enhancing Topological Message Passingcited by 14
  38. 2024Empowering Graph Invariance Learning with Deep Spurious Infomaxcited by 14

50 most cited of 136 All 136 (JSON)