Research map / Graph learning / GNN architectures
A Flexible, Equivariant Framework for Subgraph GNNs via Graph Products and Graph Coarsening
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes CS-GNN, a flexible Subgraph GNN that associates subgraphs with spectral-clustering super-nodes, runs message passing on the coarsened Cartesian product T(G)□G plus symmetry-based equivariant updates, and reports strong ZINC/OGB results across bag sizes.
Problem
Subgraph GNNs scale poorly because they must process a bag of n subgraphs; prior subset-selection methods rely on discrete training-time sampling and are limited to very small bag sizes.
Approach
Associate subgraphs with node clusters (super-nodes) from a coarsening function, view the bag as the Cartesian product of the coarsened graph and the original graph, and add symmetry-based updates from a characterization of linear equivariant layers on the node feature tensor indexed by (S, v); the bag size is controlled by the number of clusters T.
Key results
- On ZINC-12k, CS-GNN with bag size T=3 reaches 0.096 MAE versus 0.104 for the best efficient baseline Mag-GNN (T=3), and 0.062 MAE in the full-bag setting, matching state-of-the-art Subgraph GNNs.
- Removing the symmetry-based updates on ZINC-12k raises MAE at T=2 from 0.109 to 0.143.
- On Peptides-func, CS-GNN reaches 0.6156 AP versus 0.5924 for the random Subgraphormer+PE variant with the same bag size of 35.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use CS-GNN instead of MAG-GNN | ZINC-12k, T=2 · ZINC-12k, T=2 | MAE: 0.106 ± 0.014 -> 0.109 ± 0.005 | Hurt |
| Use CS-GNN instead of MAG-GNN | ZINC-12k, T=3 · ZINC-12k, T=3 | MAE: 0.104 ± N/A -> 0.096 ± 0.005 | Helped |
| Use CS-GNN instead of MAG-GNN | ZINC-12k, T=4 · ZINC-12k, T=4 | MAE: 0.101 ± N/A -> 0.090 ± 0.003 | Helped |
| Use CS-GNN instead of PL | ZINC-12k, T=5 · ZINC-12k, T=5 | MAE: 0.109 ± 0.005 -> 0.095 ± 0.003 | Helped |
| Use CS-GNN instead of the strongest full-bag baseline | ZINC-12k, Full · ZINC-12k, Full | MAE: 0.063 ± 0.001 -> 0.062 ± 0.0007 | Helped |
| Use CS-GNN instead of PL | molhiv, T=2 · molhiv, T=2 | ROC-AUC: 79.13 ± 0.60 -> 77.72 ± 0.76 | Hurt |
| Use CS-GNN instead of PL | molbace, T=2 · molbace, T=2 | ROC-AUC: 78.40 ± 2.85 -> 80.58 ± 1.04 | Helped |
| Use CS-GNN instead of PL | molesol, T=2 · molesol, T=2 | RMSE: 0.877 ± 0.029 -> 0.850 ± 0.024 | Helped |
| Use CS-GNN instead of PL | molhiv, T=5 · molhiv, T=5 | ROC-AUC: 78.49 ± 1.01 -> 79.09 ± 0.90 | Helped |
| Use CS-GNN instead of PL | molbace, T=5 · molbace, T=5 | ROC-AUC: 78.39 ± 2.28 -> 79.64 ± 1.43 | Helped |
| Use CS-GNN instead of PL | molesol, T=5 · molesol, T=5 | RMSE: 0.883 ± 0.032 -> 0.863 ± 0.029 | Helped |
| Add symmetry-based updates (ablation) | CS-GNN, ZINC-12k, T=2 · ZINC-12k, T=2 | MAE: 0.143 ± 0.003 -> 0.109 ± 0.005 | Helped |
Surprising findings
- Unlike the full-bag node-based case, the proposed node marking strategies differ in expressivity under coarsening, with the learned distance function being strictly more expressive for some coarsening functions.
- The symmetry-based updates matter most at the smallest bag size (T=2), where removing them increases MAE by 0.034.
Limitations
- Achieving better performance requires larger bag sizes, which becomes a complexity bottleneck for large graphs.
- Only a subset of the derived equivariant basis is used in the symmetry-based updates, for runtime reasons.
- Only spectral clustering is explored as the coarsening function.
Experimental setup
Datasets: ZINC-12k ZINC-Full ogbg-molhiv ogbg-molbace ogbg-molesol Peptides-func Peptides-struct
Benchmarks: ZINC-12k ZINC-Full ogbg-molhiv ogbg-molbace ogbg-molesol Peptides-func Peptides-struct
Metrics: MAE ROC-AUC RMSE AP
Baselines: GIN OSAN Random PL Mag-GNN GNN-SSWL+ Subgraphormer Subgraphormer + PE GCN GatedGCN+RWSE
Builds on: GNN-SSWL+ Policy-Learn MAG-GNN Subgraphormer GIN
Closest papers by meaning
- Translating Subgraphs to Nodes Makes Simple GNNs Strong and Efficient for Subgraph Representation Learning (ICML 2024 · similarity 0.93)
- Subgraphormer: Unifying Subgraph GNNs and Graph Transformers via Graph Products (ICML 2024 · similarity 0.91)
- Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centrality (ICML 2025 · similarity 0.91)
- EiG-Search: Generating Edge-Induced Subgraphs for GNN Explanation in Linear Time (ICML 2024 · similarity 0.90)
- Efficient Subgraph GNNs by Learning Effective Selection Policies (ICLR 2024 · similarity 0.90)
- Subgraph Invariant Learning Towards Large-Scale Graph Node Classification (AAAI 2025 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.