Research map / Graph learning / GNN architectures
Subgraphormer: Unifying Subgraph GNNs and Graph Transformers via Graph Products
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 Subgraphormer, which views node-marking Subgraph GNNs as MPNNs on a Cartesian product graph G□G, and combines sparse attention over that product graph with a product-graph Laplacian positional encoding, outperforming Subgraph GNNs and Graph Transformers on ZINC, OGB and Peptides benchmarks.
Problem
Subgraph GNNs are expressive but computationally heavy and lack attention and positional encodings, while Graph Transformers lack subgraph-level structure; the paper asks how to unify the two and how to compute positional encodings for the quadratically-sized subgraph structure efficiently.
Approach
Shows that the maximally expressive node-marking Subgraph GNN (GNN-SSWL+) can be implemented as an MPNN on the Cartesian product G□G, uses the product's internal/external adjacencies as sparse attention masks (SAB), and derives a positional encoding from the product's Laplacian eigenvectors computed as Kronecker products of the original graph's eigenvectors, at the cost of an n-node eigendecomposi
Key results
- On ZINC-12k, Subgraphormer+PE reaches 0.063 MAE (vs. GNN-SSWL+ 0.070 and GPS 0.070), and plain Subgraphormer reaches 0.067 with 293k parameters.
- On ogbg-molbace, Subgraphormer+PE achieves 84.35 ROC-AUC, above GNN-SSWL+ at 82.70.
- On Peptides-struct with 30% sampling, Subgraphormer+PE reaches 0.2475 MAE, the best among listed methods including Graph Transformers, while Peptides-func is comparable to GPS.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add attention blocks (SABs) to GNN-SSWL+ | Subgraphormer · ZINC-12k | MAE: 0.082 ± 0.003 -> 0.067 ± 0.007 | Helped |
| add product graph PE (ablation) | Subgraphormer · ZINC-12k | MAE: 0.067 ± 0.007 -> 0.063 ± 0.001 | Helped |
| add product graph PE (ablation) | Subgraphormer · ZINC-Full | MAE: 0.020 ± 0.002 -> 0.023 ± 0.001 | Hurt |
| add product graph PE (ablation) | Subgraphormer · molhiv | ROC-AUC: 80.38 ±1.92 -> 79.48 ±1.28 | Hurt |
| add product graph PE (ablation) | Subgraphormer · molbace | ROC-AUC: 81.62 ±3.55 -> 84.35 ±0.65 | Helped |
| add product graph PE (ablation) | Subgraphormer · molesol | RMSE: 0.832 ±0.043 -> 0.826 ±0.010 | Helped |
| add product graph PE (ablation) | Subgraphormer · Peptides-func (30% sampling) | AP: 0.6415 ±0.0052 -> 0.6373 ±0.0110 | Hurt |
| add product graph PE (ablation) | Subgraphormer · Peptides-struct (30% sampling) | MAE: 0.2494 ±0.0020 -> 0.2475 ±0.0007 | Helped |
| add product graph PE (ablation) | Subgraphormer · Alchemy-12k | MAE: 0.114 ±0.001 -> 0.113 ±0.002 | Helped |
| add product graph PE (ablation) | Subgraphormer · ZINC-12k, 50% sampling | MAE: 0.084 ±0.002 -> 0.084 ±0.002 | No clear effect |
| add product graph PE (ablation) | Subgraphormer · ZINC-12k, 20% sampling | MAE: 0.121 ±0.007 -> 0.120 ±0.002 | Helped |
| add product graph PE (ablation) | Subgraphormer · ZINC-12k, 5% sampling | MAE: 0.200 ±0.017 -> 0.175 ±0.006 | Helped |
Surprising findings
- On ogbg-molhiv, Subgraphormer+PE (79.48) is slightly below plain Subgraphormer (80.38), so the PE does not help uniformly.
- Product-graph PE does not improve every sampling setting; it helps in 13 of 16 dataset-sampling combinations, so it is not uniformly beneficial.
Limitations
- Operates on n^2 node product graph, which remains costly for large graphs, motivating stochastic subgraph sampling.
- Reported results are averages over only 3 seeds, and std is large on some datasets (e.g., molbace ±3.55).
- Gains over strongest baselines are modest on some datasets such as molhiv and Peptides-func.
Experimental setup
Datasets: ZINC-12k ZINC-Full Alchemy-12k 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 Alchemy-12k
Metrics: MAE ROC-AUC RMSE AP
Baselines: GNN-SSWL+ GNN-SSWL SUN GPS SAN Graphormer GNN-AK+ CIN NGNN DS-GNN
Builds on: GNN-SSWL+ GIN GAT RGCN Graphormer-GD
Closest papers by meaning
- A Flexible, Equivariant Framework for Subgraph GNNs via Graph Products and Graph Coarsening (NeurIPS 2024 · similarity 0.91)
- Translating Subgraphs to Nodes Makes Simple GNNs Strong and Efficient for Subgraph Representation Learning (ICML 2024 · similarity 0.91)
- Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellence (ICML 2025 · similarity 0.89)
- Union Subgraph Neural Networks (AAAI 2024 · similarity 0.89)
- GPEN: Global Position Encoding Network for Enhanced Subgraph Representation Learning (ICML 2025 · similarity 0.89)
- Polynormer: Polynomial-Expressive Graph Transformer in Linear Time (ICLR 2024 · similarity 0.89)
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.