mlsanityData to 14 Oct 2026

An Efficient Subgraph GNN with Provable Substructure Counting Power

arXiv 2303.10576 ↗First posted 19 Mar 2023cs.LGcited by 13

Not on the map. Why?

Abstract (arXiv)

We investigate the enhancement of graph neural networks' (GNNs) representation power through their ability in substructure counting. Recent advances have seen the adoption of subgraph GNNs, which partition an input graph into numerous subgraphs, subsequently applying GNNs to each to augment the graph's overall representation. Despite their ability to identify various substructures, subgraph GNNs are hindered by significant computational and memory costs. In this paper, we tackle a critical question: Is it possible for GNNs to count substructures both efficiently and provably? Our approach begins with a theoretical demonstration that the distance to rooted nodes in subgraphs is key to boosting the counting power of subgraph GNNs. To avoid the need for repetitively applying GNN across all subgraphs, we introduce precomputed structural embeddings that encapsulate this crucial distance information. Experiments validate that our proposed model retains the counting power of subgraph GNNs while achieving significantly faster performance.

Key facts. Cited by 13 papers in the map (data through 14 Oct 2026). Builds on 48 of its 82 references that are in the map. First posted on arXiv 19 Mar 2023.

Builds on

48 of 82 references.

References · 48

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,919
  3. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,163
  4. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,576
  5. 2017MoleculeNet: A Benchmark for Molecular Machine Learningcited by 1,051
  6. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
  7. 2018Link Prediction Based on Graph Neural Networkscited by 832
  8. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 728
  9. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 713
  10. 2020Benchmarking Graph Neural Networkscited by 680
  11. 2018Junction Tree Variational Autoencoder for Molecular Graph Generationcited by 652
  12. 2020Principal Neighbourhood Aggregation for Graph Netscited by 478
36 more
  1. 2021Rethinking Graph Transformers with Spectral Attentioncited by 473
  2. 2019MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixingcited by 443
  3. 2019Provably Powerful Graph Networkscited by 389
  4. 2018Invariant and Equivariant Graph Networkscited by 346
  5. 2021Graph Neural Networks with Learnable Structural and Positional Representationscited by 333
  6. 2020Can Graph Neural Networks Count Substructures?cited by 236
  7. 2021Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networkscited by 221
  8. 2021Weisfeiler and Lehman Go Cellular: CW Networkscited by 218
  9. 2021Identity-aware Graph Neural Networkscited by 198
  10. 2021From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awarenesscited by 155
  11. 2019Relational Pooling for Graph Representationscited by 150
  12. 2020Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learningcited by 149
  13. 2021GraphiT: Encoding Graph Structure in Transformerscited by 147
  14. 2021Nested Graph Neural Networkscited by 137
  15. 2020Directional Graph Networkscited by 133
  16. 2019Neural Execution of Graph Algorithmscited by 121
  17. 2021DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networkscited by 118
  18. 2021Breaking the Limits of Message Passing Graph Neural Networkscited by 101
  19. 2020Building powerful and equivariant graph neural networks with structural message-passingcited by 97
  20. 2022GRPE: Relative Positional Encoding for Graph Transformercited by 70
  21. 2021Reconstruction for Powerful Graph Representationscited by 65
  22. 2018On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Propertiescited by 63
  23. 2019k-hop Graph Neural Networkscited by 57
  24. 2021Graph Neural Networks with Local Graph Parameterscited by 52
  25. 2022A Theoretical Comparison of Graph Neural Network Extensionscited by 48
  26. 2021Link Prediction with Persistent Homology: An Interactive Viewcited by 37
  27. 2020The expressive power of kth-order invariant graph networkscited by 34
  28. 2019Neural Subgraph Isomorphism Countingcited by 27
  29. 2021Cycle Representation Learning for Inductive Relation Predictioncited by 23
  30. 2021How to transfer algorithmic reasoning knowledge to learn new algorithms?cited by 22
  31. 2020Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Resultscited by 19
  32. 2017On the Combinatorial Power of the Weisfeiler-Lehman Algorithmcited by 18
  33. 2021Ego-GNNs: Exploiting Ego Structures in Graph Neural Networkscited by 17
  34. 2022Neural Approximation of Graph Topological Featurescited by 17
  35. 2022Weisfeiler and Leman Go Infinite: Spectral and Combinatorial Pre-Coloringscited by 15
  36. 2021Graph Convolutional Networks with Dual Message Passing for Subgraph Isomorphism Counting and Matchingcited by 11

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 4; 2024: 1; 2025: 7; 2026: 1.

13 papers.

Sort:

  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. 2025Beyond Message Passing: Neural Graph Pattern Machinecited by 17
  4. 2023Extending the Design Space of Graph Neural Networks by Rethinking Folklore Weisfeiler-Lehmancited by 13
  5. 2023Cycle Invariant Positional Encoding for Graph Representation Learningcited by 8
  6. 2025Enhancing Graph Representation Learning with Localized Topological Featurescited by 6
  7. 2025Open Your Eyes: Vision Enhances Message Passing Neural Networks in Link Predictioncited by 2
  8. 2024Exact Acceleration of Subgraph Graph Neural Networks by Eliminating Computation Redundancycited by 0
  9. 2025OpenGLT: A Comprehensive Benchmark of Graph Neural Networks for Graph-Level Taskscited by 0
  10. 2025BEACON: A Benchmark for Efficient and Accurate Counting of Subgraphscited by 0
  11. 2025Exact Subgraph Isomorphism Network with Mixed L0,2 Norm Constraint for Predictive Graph Miningcited by 0
  12. 2025On The Expressive Power of GNN Derivativescited by 0
1 more
  1. 2026Invariant-Based Weight Sharing for Message Passingcited by 0