mlsanityData to 7 Oct 2026

Efficient Subgraph GNNs by Learning Effective Selection Policies

arXiv 2310.20082 ↗First posted 30 Oct 2023cs.LGcited by 17

Not on the map. Why?

Abstract (arXiv)

Subgraph GNNs are provably expressive neural architectures that learn graph representations from sets of subgraphs. Unfortunately, their applicability is hampered by the computational complexity associated with performing message passing on many subgraphs. In this paper, we consider the problem of learning to select a small subset of the large set of possible subgraphs in a data-driven fashion. We first motivate the problem by proving that there are families of WL-indistinguishable graphs for which there exist efficient subgraph selection policies: small subsets of subgraphs that can already identify all the graphs within the family. We then propose a new approach, called Policy-Learn, that learns how to select subgraphs in an iterative manner. We prove that, unlike popular random policies and prior work addressing the same problem, our architecture is able to learn the efficient policies mentioned above. Our experimental results demonstrate that Policy-Learn outperforms existing baselines across a wide range of datasets.

Key facts. Cited by 17 papers in the map (data through 7 Oct 2026). Builds on 47 of its 53 references that are in the map. First posted on arXiv 30 Oct 2023.

Builds on

47 of 53 references.

References · 47

  1. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  3. 2018How Powerful are Graph Neural Networks?cited by 4,355
  4. 2016Categorical Reparameterization with Gumbel-Softmaxcited by 2,708
  5. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,414
  6. 2016The Concrete Distribution: A Continuous Relaxation of Discrete Random Variablescited by 1,135
  7. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  8. 2016Automatic chemical design using a data-driven continuous representation of moleculescited by 762
  9. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 718
  10. 2019DropEdge: Towards Deep Graph Convolutional Networks on Node Classificationcited by 679
  11. 2020Benchmarking Graph Neural Networkscited by 672
  12. 2020Principal Neighbourhood Aggregation for Graph Netscited by 477
35 more
  1. 2019Provably Powerful Graph Networkscited by 385
  2. 2018Invariant and Equivariant Graph Networkscited by 339
  3. 2021Graph Neural Networks with Learnable Structural and Positional Representationscited by 326
  4. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 312
  5. 2020Can Graph Neural Networks Count Substructures?cited by 235
  6. 2021Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networkscited by 219
  7. 2021Weisfeiler and Lehman Go Cellular: CW Networkscited by 218
  8. 2021Identity-aware Graph Neural Networkscited by 197
  9. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 190
  10. 2021Equivariant Subgraph Aggregation Networkscited by 154
  11. 2021From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awarenesscited by 154
  12. 2019Relational Pooling for Graph Representationscited by 150
  13. 2021Nested Graph Neural Networkscited by 136
  14. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 121
  15. 2020From Local Structures to Size Generalization in Graph Neural Networkscited by 119
  16. 2021DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networkscited by 117
  17. 2022Understanding and Extending Subgraph GNNs by Rethinking Their Symmetriescited by 112
  18. 2020A Survey on The Expressive Power of Graph Neural Networkscited by 111
  19. 2021Implicit MLE: Backpropagating Through Discrete Exponential Family Distributionscited by 97
  20. 2020Building powerful and equivariant graph neural networks with structural message-passingcited by 95
  21. 2018Small ReLU networks are powerful memorizers: a tight analysis of memorization capacitycited by 76
  22. 2021Reconstruction for Powerful Graph Representationscited by 65
  23. 2023A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Testscited by 64
  24. 2022Ordered Subgraph Aggregation Networkscited by 57
  25. 2022Boosting the Cycle Counting Power of Graph Neural Networks with I2-GNNscited by 55
  26. 2021Graph Neural Networks with Local Graph Parameterscited by 51
  27. 2019Coloring graph neural networks for node disambiguationcited by 49
  28. 2020Graph Policy Network for Transferable Active Learning on Graphscited by 49
  29. 2022A Theoretical Comparison of Graph Neural Network Extensionscited by 47
  30. 2023Equivariant Polynomials for Graph Neural Networkscited by 38
  31. 2019Alchemy: A Quantum Chemistry Dataset for Benchmarking AI Modelscited by 36
  32. 2020Controlling Graph Dynamics with Reinforcement Learning and Graph Neural Networkscited by 30
  33. 2023From Relational Pooling to Subgraph GNNs: A Universal Framework for More Expressive Graph Neural Networkscited by 17
  34. 2022Agent-based Graph Neural Networkscited by 13
  35. 2023An Efficient Subgraph GNN with Provable Substructure Counting Powercited by 13

Built on by

Cited by year (2026 to 7 Oct)

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

17 papers.

Sort:

  1. 2024On the Expressive Power of Spectral Invariant Graph Neural Networkscited by 15
  2. 2024Subgraphormer: Unifying Subgraph GNNs and Graph Transformers via Graph Productscited by 8
  3. 2024A Flexible, Equivariant Framework for Subgraph GNNs via Graph Products and Graph Coarseningcited by 8
  4. 2024GRANOLA: Adaptive Normalization for Graph Neural Networkscited by 7
  5. 2024Preventing Representational Rank Collapse in MPNNs by Splitting the Computational Graphcited by 6
  6. 2025Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centralitycited by 5
  7. 2023Improving Subgraph-GNNs via Edge-Level Ego-Network Encodingscited by 4
  8. 2024Towards Graph Foundation Models: A Study on the Generalization of Positional and Structural Encodingscited by 4
  9. 2025Towards Efficient Training of Graph Neural Networks: A Multiscale Approachcited by 4
  10. 2024DiGRAF: Diffeomorphic Graph-Adaptive Activation Functioncited by 2
  11. 2024Towards Stable, Globally Expressive Graph Representations with Laplacian Eigenvectorscited by 2
  12. 2025Graph Self-Supervised Learning with Learnable Structural and Positional Encodingscited by 1
5 more
  1. 2025A Fused Gromov-Wasserstein Approach to Subgraph Contrastive Learningcited by 1
  2. 2026On the Expressive Power of GNNs to Solve Linear SDPscited by 1
  3. 2025OpenGLT: A Comprehensive Benchmark of Graph Neural Networks for Graph-Level Taskscited by 0
  4. 2025On The Expressive Power of GNN Derivativescited by 0
  5. 2025GoMS: Graph of Molecule Substructure Network for Molecule Property Predictioncited by 0