mlsanityData to 14 Oct 2026

Ordered Subgraph Aggregation Networks

arXiv 2206.11168 ↗First posted 22 Jun 2022cs.LG cs.AI cs.DScited by 57

Not on the map. Why?

Abstract (arXiv)

Numerous subgraph-enhanced graph neural networks (GNNs) have emerged recently, provably boosting the expressive power of standard (message-passing) GNNs. However, there is a limited understanding of how these approaches relate to each other and to the Weisfeiler-Leman hierarchy. Moreover, current approaches either use all subgraphs of a given size, sample them uniformly at random, or use hand-crafted heuristics instead of learning to select subgraphs in a data-driven manner. Here, we offer a unified way to study such architectures by introducing a theoretical framework and extending the known expressivity results of subgraph-enhanced GNNs. Concretely, we show that increasing subgraph size always increases the expressive power and develop a better understanding of their limitations by relating them to the established k-mathsfWL hierarchy. In addition, we explore different approaches for learning to sample subgraphs using recent methods for backpropagating through complex discrete probability distributions. Empirically, we study the predictive performance of different subgraph-enhanced GNNs, showing that our data-driven architectures increase prediction accuracy on standard benchmark datasets compared to non-data-driven subgraph-enhanced graph neural networks while reducing computation time.

Key facts. Cited by 57 papers in the map (data through 14 Oct 2026). Builds on 88 of its 139 references that are in the map. First posted on arXiv 22 Jun 2022.

Builds on

88 of 139 references.

References · 88

  1. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  3. 2017Graph Attention Networkscited by 8,923
  4. 2017Inductive Representation Learning on Large Graphscited by 6,320
  5. 2018How Powerful are Graph Neural Networks?cited by 4,393
  6. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  7. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,919
  8. 2016Categorical Reparameterization with Gumbel-Softmaxcited by 2,739
  9. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,434
  10. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,163
  11. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,089
  12. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,576
38 more
  1. 2016The Concrete Distribution: A Continuous Relaxation of Discrete Random Variablescited by 1,148
  2. 2013Spectral Networks and Locally Connected Networks on Graphscited by 1,102
  3. 2017MoleculeNet: A Benchmark for Molecular Machine Learningcited by 1,051
  4. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
  5. 2018Representation Learning on Graphs with Jumping Knowledge Networkscited by 877
  6. 2018Hierarchical Graph Representation Learning with Differentiable Poolingcited by 787
  7. 2015Convolutional Networks on Graphs for Learning Molecular Fingerprintscited by 754
  8. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 728
  9. 2019DropEdge: Towards Deep Graph Convolutional Networks on Node Classificationcited by 680
  10. 2020Benchmarking Graph Neural Networkscited by 680
  11. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 631
  12. 2020Directional Message Passing for Molecular Graphscited by 561
  13. 2019Graph U-Netscited by 492
  14. 2020Principal Neighbourhood Aggregation for Graph Netscited by 478
  15. 2016Geometric deep learning on graphs and manifolds using mixture model CNNscited by 468
  16. 2019MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixingcited by 443
  17. 2019Hyperbolic Graph Convolutional Neural Networkscited by 402
  18. 2019Provably Powerful Graph Networkscited by 389
  19. 2021GemNet: Universal Directional Graph Neural Networks for Moleculescited by 343
  20. 2016Learning Convolutional Neural Networks for Graphscited by 314
  21. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 313
  22. 2017Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphscited by 310
  23. 2019Cormorant: Covariant Molecular Neural Networkscited by 263
  24. 2015Order Matters: Sequence to sequence for setscited by 237
  25. 2021Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networkscited by 221
  26. 2021Weisfeiler and Lehman Go Cellular: CW Networkscited by 218
  27. 2022Neural Sheaf Diffusion: A Topological Perspective on Heterophily and Oversmoothing in GNNscited by 214
  28. 2019Position-aware Graph Neural Networkscited by 203
  29. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 198
  30. 2021Identity-aware Graph Neural Networkscited by 198
  31. 2020Random Features Strengthen Graph Neural Networkscited by 186
  32. 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
  33. 2021Training Graph Neural Networks with 1000 Layerscited by 169
  34. 2020Machine Learning on Graphs: A Model and Comprehensive Taxonomycited by 156
  35. 2021From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awarenesscited by 155
  36. 2021Equivariant Subgraph Aggregation Networkscited by 154
  37. 2019Relational Pooling for Graph Representationscited by 150
  38. 2019A Survey on Graph Kernelscited by 148

50 most cited of 88 All 88 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 6; 2023: 16; 2024: 17; 2025: 14; 2026: 4.

57 papers.

Sort:

By area:

  1. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  2. 2023A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Testscited by 64
  3. 2022Boosting the Cycle Counting Power of Graph Neural Networks with I2-GNNscited by 56
  4. 2023Rethinking Tokenizer and Decoder in Masked Graph Modeling for Moleculescited by 49
  5. 2024Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressivenesscited by 39
  6. 2023Equivariant Polynomials for Graph Neural Networkscited by 38
  7. 2023An Empirical Study of Realized GNN Expressivenesscited by 33
  8. 2023WL meet VCcited by 31
  9. 2022Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Taskscited by 30
  10. 2022Weisfeiler and Leman Go Relationalcited by 28
  11. 2024Unifying Generation and Prediction on Graphs with Latent Graph Diffusioncited by 25
  12. 2022A Practical, Progressively-Expressive GNNcited by 20
38 more
  1. 2023From Relational Pooling to Subgraph GNNs: A Universal Framework for More Expressive Graph Neural Networkscited by 17
  2. 2023Efficient Subgraph GNNs by Learning Effective Selection Policiescited by 17
  3. 2024On the Expressive Power of Spectral Invariant Graph Neural Networkscited by 15
  4. 2023Extending the Design Space of Graph Neural Networks by Rethinking Folklore Weisfeiler-Lehmancited by 13
  5. 2024Weisfeiler-Leman at the margin: When more expressivity matterscited by 13
  6. 2022Adaptive Perturbation-Based Gradient Estimation for Discrete Latent Variable Modelscited by 12
  7. 2023Distance-Restricted Folklore Weisfeiler-Leman GNNs with Provable Cycle Counting Powercited by 12
  8. 2023MAG-GNN: Reinforcement Learning Boosted Graph Neural Networkcited by 11
  9. 2024On the Completeness of Invariant Geometric Deep Learning Modelscited by 11
  10. 2024Subgraphormer: Unifying Subgraph GNNs and Graph Transformers via Graph Productscited by 8
  11. 2024A Flexible, Equivariant Framework for Subgraph GNNs via Graph Products and Graph Coarseningcited by 8
  12. 2024FSW-GNN: A Bi-Lipschitz WL-Equivalent Graph Neural Networkcited by 8
  13. 2022L2XGNN: Learning to Explain Graph Neural Networkscited by 7
  14. 2024Future Directions in the Theory of Graph Machine Learningcited by 6
  15. 2025Enhancing Graph Representation Learning with Localized Topological Featurescited by 6
  16. 2025Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centralitycited by 5
  17. 2025Graph Representational Learning: When Does More Expressivity Hurt Generalization?cited by 5
  18. 2023Improving Graph Neural Networks on Multi-node Tasks with the Labeling Trickcited by 4
  19. 2023Improving Subgraph-GNNs via Edge-Level Ego-Network Encodingscited by 4
  20. 2024Graph as Point Setcited by 4
  21. 2024Demystifying Higher-Order Graph Neural Networkscited by 4
  22. 2025Homomorphism Expressivity of Spectral Invariant Graph Neural Networkscited by 4
  23. 2023Combining Stochastic Explainers and Subgraph Neural Networks can Increase Expressivity and Interpretabilitycited by 3
  24. 2023Deep Graph Neural Networks via Posteriori-Sampling-based Node-Adaptive Residual Modulecited by 3
  25. 2024Foundations and Frontiers of Graph Learning Theorycited by 3
  26. 2025Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualizationcited by 3
  27. 2024Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learningcited by 2
  28. 2024Towards Stable, Globally Expressive Graph Representations with Laplacian Eigenvectorscited by 2
  29. 2024On the Utilization of Unique Node Identifiers in Graph Neural Networkscited by 2
  30. 2025Generalization Performance of Hypergraph Neural Networkscited by 2
  31. 2025Using Random Noise Equivariantly to Boost Graph Neural Networks Universallycited by 2
  32. 2025Toward a Unified Geometry Understanding: Riemannian Diffusion Framework for Graph Generation and Predictioncited by 2
  33. 2024Fine-Grained Expressive Power of Weisfeiler-Leman: A Homomorphism Counting Perspectivecited by 1
  34. 2025Network Tomography with Path-Centric Graph Neural Networkcited by 1
  35. 2025FedABC: Attention-Based Client Selection for Federated Learning with Long-Term Viewcited by 1
  36. 2026On the Expressive Power of GNNs to Solve Linear SDPscited by 1
  37. 2023Invariant Layers for Graphs with Nodes of Different Typescited by 0
  38. 2024Message Detouring: A Simple Yet Effective Cycle Representation for Expressive Graph Learningcited by 0

50 most cited of 57 All 57 (JSON)