mlsanityData to 7 Oct 2026

From Relational Pooling to Subgraph GNNs: A Universal Framework for More Expressive Graph Neural Networks

arXiv 2305.04963 ↗First posted 8 May 2023cs.LG cs.AIcited by 17

Not on the map. Why?

Abstract (arXiv)

Relational pooling is a framework for building more expressive and permutation-invariant graph neural networks. However, there is limited understanding of the exact enhancement in the expressivity of RP and its connection with the Weisfeiler Lehman hierarchy. Starting from RP, we propose to explicitly assign labels to nodes as additional features to improve expressive power of message passing neural networks. The method is then extended to higher dimensional WL, leading to a novel k,l-WL algorithm, a more general framework than k-WL. Theoretically, we analyze the expressivity of k,l-WL with respect to k and l and unifies it with a great number of subgraph GNNs. Complexity reduction methods are also systematically discussed to build powerful and practical k,l-GNN instances. We theoretically and experimentally prove that our method is universally compatible and capable of improving the expressivity of any base GNN model. Our k,l-GNNs achieve superior performance on many synthetic and real-world datasets, which verifies the effectiveness of our framework.

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

Builds on

32 of 55 references.

References · 32

  1. 2017Inductive Representation Learning on Large Graphscited by 6,284
  2. 2018How Powerful are Graph Neural Networks?cited by 4,355
  3. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,148
  4. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,571
  5. 2017Deep Setscited by 1,394
  6. 2016Geometric deep learning: going beyond Euclidean datacited by 1,042
  7. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  8. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 702
  9. 2020Benchmarking Graph Neural Networkscited by 672
  10. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 557
  11. 2020Directional Message Passing for Molecular Graphscited by 556
  12. 2020Principal Neighbourhood Aggregation for Graph Netscited by 477
20 more
  1. 2019Provably Powerful Graph Networkscited by 385
  2. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 312
  3. 2020Can Graph Neural Networks Count Substructures?cited by 235
  4. 2021Weisfeiler and Lehman Go Cellular: CW Networkscited by 218
  5. 2021Identity-aware Graph Neural Networkscited by 197
  6. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 190
  7. 2021From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awarenesscited by 154
  8. 2019Relational Pooling for Graph Representationscited by 150
  9. 2021Nested Graph Neural Networkscited by 136
  10. 2022Understanding and Extending Subgraph GNNs by Rethinking Their Symmetriescited by 112
  11. 2021Breaking the Limits of Message Passing Graph Neural Networkscited by 101
  12. 2021Implicit MLE: Backpropagating Through Discrete Exponential Family Distributionscited by 97
  13. 2022How Powerful are K-hop Message Passing Graph Neural Networkscited by 90
  14. 2021SUGAR: Subgraph Neural Network with Reinforcement Pooling and Self-Supervised Mutual Information Mechanismcited by 75
  15. 2023A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Testscited by 64
  16. 2022Ordered Subgraph Aggregation Networkscited by 57
  17. 2022Boosting the Cycle Counting Power of Graph Neural Networks with I2-GNNscited by 55
  18. 2022A Theoretical Comparison of Graph Neural Network Extensionscited by 47
  19. 2022Going Deeper into Permutation-Sensitive Graph Neural Networkscited by 15
  20. 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: 2; 2024: 10; 2025: 3; 2026: 2.

17 papers.

Sort:

By area:

  1. 2024Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressivenesscited by 38
  2. 2024Unifying Generation and Prediction on Graphs with Latent Graph Diffusioncited by 24
  3. 2023Efficient Subgraph GNNs by Learning Effective Selection Policiescited by 17
  4. 2023Extending the Design Space of Graph Neural Networks by Rethinking Folklore Weisfeiler-Lehmancited by 13
  5. 2024On the Theoretical Expressive Power and the Design Space of Higher-Order Graph Transformerscited by 8
  6. 2026Rethinking Diffusion Models with Symmetries through Canonicalization with Applications to Molecular Graph Generationcited by 5
  7. 2024Demystifying Higher-Order Graph Neural Networkscited by 4
  8. 2025Bridging Theory and Practice in Link Representation with Graph Neural Networkscited by 4
  9. 2024Foundations and Frontiers of Graph Learning Theorycited by 3
  10. 2025Do Graph Diffusion Models Accurately Capture and Generate Substructure Distributions?cited by 3
  11. 2024How Hard Is It for Message-Passing GNNs to Simulate One Weisfeiler-Lehman Color-Refinement Step?cited by 2
  12. 2024Towards Stable, Globally Expressive Graph Representations with Laplacian Eigenvectorscited by 2
5 more
  1. 2024GTAGCN: Generalized Topology Adaptive Graph Convolutional Networkscited by 1
  2. 2024Fine-Grained Expressive Power of Weisfeiler-Leman: A Homomorphism Counting Perspectivecited by 0
  3. 2024Exact Acceleration of Subgraph Graph Neural Networks by Eliminating Computation Redundancycited by 0
  4. 2025The Generalized Skew Spectrum of Graphscited by 0
  5. 2026Plain Transformers are Surprisingly Powerful Link Predictorscited by 0