# Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries

arXiv: https://arxiv.org/abs/2206.11140 · HTML: https://mlsanity.com/paper/2206.11140/

## Key facts

- Cited by 112 papers in the map (data through 14 Oct 2026).
- Builds on 50 of its 79 references that are in the map.
- First posted on arXiv 22 Jun 2022.

## Builds on (most cited first, 30 of 50)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Automatic chemical design using a data-driven continuous representation of molecules](https://mlsanity.com/paper/1610.02415/) (2016)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [Principal Neighbourhood Aggregation for Graph Nets](https://mlsanity.com/paper/2004.05718/) (2020)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Invariant and Equivariant Graph Networks](https://mlsanity.com/paper/1812.09902/) (2018)
- [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [ASAM: Adaptive Sharpness-Aware Minimization for Scale-Invariant Learning of Deep Neural Networks](https://mlsanity.com/paper/2102.11600/) (2021)
- [Diffusion-Convolutional Neural Networks](https://mlsanity.com/paper/1511.02136/) (2015)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks](https://mlsanity.com/paper/2103.03212/) (2021)
- [Weisfeiler and Lehman Go Cellular: CW Networks](https://mlsanity.com/paper/2106.12575/) (2021)
- [The Surprising Power of Graph Neural Networks with Random Node Initialization](https://mlsanity.com/paper/2010.01179/) (2020)
- [Identity-aware Graph Neural Networks](https://mlsanity.com/paper/2101.10320/) (2021)
- [Universal Invariant and Equivariant Graph Neural Networks](https://mlsanity.com/paper/1905.04943/) (2019)
- [Sign and Basis Invariant Networks for Spectral Graph Representation Learning](https://mlsanity.com/paper/2202.13013/) (2022)
- [From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness](https://mlsanity.com/paper/2110.03753/) (2021)
- [Equivariant Subgraph Aggregation Networks](https://mlsanity.com/paper/2110.02910/) (2021)
- [On the Universality of Invariant Networks](https://mlsanity.com/paper/1901.09342/) (2019)
- [Nested Graph Neural Networks](https://mlsanity.com/paper/2110.13197/) (2021)

## Built on by (most cited first, 30 of 112)

- [Rethinking the Expressive Power of GNNs via Graph Biconnectivity](https://mlsanity.com/paper/2301.09505/) (2023)
- [Universal Prompt Tuning for Graph Neural Networks](https://mlsanity.com/paper/2209.15240/) (2022)
- [A Generalization of ViT/MLP-Mixer to Graphs](https://mlsanity.com/paper/2212.13350/) (2022)
- [A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Tests](https://mlsanity.com/paper/2302.07090/) (2023)
- [Boosting the Cycle Counting Power of Graph Neural Networks with I2-GNNs](https://mlsanity.com/paper/2210.13978/) (2022)
- [Rethinking Tokenizer and Decoder in Masked Graph Modeling for Molecules](https://mlsanity.com/paper/2310.14753/) (2023)
- [A new perspective on building efficient and expressive 3D equivariant graph neural networks](https://mlsanity.com/paper/2304.04757/) (2023)
- [Equivariant Frames and the Impossibility of Continuous Canonicalization](https://mlsanity.com/paper/2402.16077/) (2024)
- [Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness](https://mlsanity.com/paper/2401.08514/) (2024)
- [Equivariant Polynomials for Graph Neural Networks](https://mlsanity.com/paper/2302.11556/) (2023)
- [An Empirical Study of Realized GNN Expressiveness](https://mlsanity.com/paper/2304.07702/) (2023)
- [WL meet VC](https://mlsanity.com/paper/2301.11039/) (2023)
- [Graph Positional Encoding via Random Feature Propagation](https://mlsanity.com/paper/2303.02918/) (2023)
- [Provably Powerful Graph Neural Networks for Directed Multigraphs](https://mlsanity.com/paper/2306.11586/) (2023)
- [The Expressive Power of Graph Neural Networks: A Survey](https://mlsanity.com/paper/2308.08235/) (2023)
- [A Canonicalization Perspective on Invariant and Equivariant Learning](https://mlsanity.com/paper/2405.18378/) (2024)
- [Unifying Generation and Prediction on Graphs with Latent Graph Diffusion](https://mlsanity.com/paper/2402.02518/) (2024)
- [Learning Efficient Positional Encodings with Graph Neural Networks](https://mlsanity.com/paper/2502.01122/) (2025)
- [Is Distance Matrix Enough for Geometric Deep Learning?](https://mlsanity.com/paper/2302.05743/) (2023)
- [A Practical, Progressively-Expressive GNN](https://mlsanity.com/paper/2210.09521/) (2022)
- [Pure Message Passing Can Estimate Common Neighbor for Link Prediction](https://mlsanity.com/paper/2309.00976/) (2023)
- [From Relational Pooling to Subgraph GNNs: A Universal Framework for More Expressive Graph Neural Networks](https://mlsanity.com/paper/2305.04963/) (2023)
- [Efficient Subgraph GNNs by Learning Effective Selection Policies](https://mlsanity.com/paper/2310.20082/) (2023)
- [Approximately Equivariant Graph Networks](https://mlsanity.com/paper/2308.10436/) (2023)
- [Homomorphism Counts for Graph Neural Networks: All About That Basis](https://mlsanity.com/paper/2402.08595/) (2024)
- [On the Expressive Power of Spectral Invariant Graph Neural Networks](https://mlsanity.com/paper/2406.04336/) (2024)
- [CIN++: Enhancing Topological Message Passing](https://mlsanity.com/paper/2306.03561/) (2023)
- [Facilitating Graph Neural Networks with Random Walk on Simplicial Complexes](https://mlsanity.com/paper/2310.19285/) (2023)
- [Fast Encoder-Based 3D from Casual Videos via Point Track Processing](https://mlsanity.com/paper/2404.07097/) (2024)
- [Extending the Design Space of Graph Neural Networks by Rethinking Folklore Weisfeiler-Lehman](https://mlsanity.com/paper/2306.03266/) (2023)

## Abstract (arXiv)

Subgraph GNNs are a recent class of expressive Graph Neural Networks (GNNs) which model graphs as collections of subgraphs. So far, the design space of possible Subgraph GNN architectures as well as their basic theoretical properties are still largely unexplored. In this paper, we study the most prominent form of subgraph methods, which employs node-based subgraph selection policies such as ego-networks or node marking and deletion. We address two central questions: (1) What is the upper-bound of the expressive power of these methods? and (2) What is the family of equivariant message passing layers on these sets of subgraphs?. Our first step in answering these questions is a novel symmetry analysis which shows that modelling the symmetries of node-based subgraph collections requires a significantly smaller symmetry group than the one adopted in previous works. This analysis is then used to establish a link between Subgraph GNNs and Invariant Graph Networks (IGNs). We answer the questions above by first bounding the expressive power of subgraph methods by 3-WL, and then proposing a general family of message-passing layers for subgraph methods that generalises all previous node-based Subgraph GNNs. Finally, we design a novel Subgraph GNN dubbed SUN, which theoretically unifies previous architectures while providing better empirical performance on multiple benchmarks.