mlsanityData to 7 Oct 2026

Subgraphormer: Unifying Subgraph GNNs and Graph Transformers via Graph Products

arXiv 2402.08450 ↗First posted 13 Feb 2024cs.LGcited by 8

Not on the map. Why?

Abstract (arXiv)

In the realm of Graph Neural Networks (GNNs), two exciting research directions have recently emerged: Subgraph GNNs and Graph Transformers. In this paper, we propose an architecture that integrates both approaches, dubbed Subgraphormer, which combines the enhanced expressive power, message-passing mechanisms, and aggregation schemes from Subgraph GNNs with attention and positional encodings, arguably the most important components in Graph Transformers. Our method is based on an intriguing new connection we reveal between Subgraph GNNs and product graphs, suggesting that Subgraph GNNs can be formulated as Message Passing Neural Networks (MPNNs) operating on a product of the graph with itself. We use this formulation to design our architecture: first, we devise an attention mechanism based on the connectivity of the product graph. Following this, we propose a novel and efficient positional encoding scheme for Subgraph GNNs, which we derive as a positional encoding for the product graph. Our experimental results demonstrate significant performance improvements over both Subgraph GNNs and Graph Transformers on a wide range of datasets.

Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Builds on 56 of its 74 references that are in the map. First posted on arXiv 13 Feb 2024.

Builds on

56 of 74 references.

References · 56

  1. 2017Attention Is All You Needcited by 59,932
  2. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 29,915
  3. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  4. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  5. 2017Graph Attention Networkscited by 8,854
  6. 2018How Powerful are Graph Neural Networks?cited by 4,355
  7. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,414
  8. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,148
  9. 2017Modeling Relational Data with Graph Convolutional Networkscited by 1,684
  10. 2020Reformer: The Efficient Transformercited by 1,658
  11. 2021Transformers in Vision: A Surveycited by 1,009
  12. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
38 more
  1. 2021How Attentive are Graph Attention Networks?cited by 818
  2. 2016Automatic chemical design using a data-driven continuous representation of moleculescited by 762
  3. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 702
  4. 2020Benchmarking Graph Neural Networkscited by 672
  5. 2021MViTv2: Improved Multiscale Vision Transformers for Classification and Detectioncited by 516
  6. 2020Principal Neighbourhood Aggregation for Graph Netscited by 477
  7. 2021Rethinking Graph Transformers with Spectral Attentioncited by 468
  8. 2017Residual Gated Graph ConvNetscited by 341
  9. 2018Invariant and Equivariant Graph Networkscited by 339
  10. 2021Graph Neural Networks with Learnable Structural and Positional Representationscited by 326
  11. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 312
  12. 2021ASAM: Adaptive Sharpness-Aware Minimization for Scale-Invariant Learning of Deep Neural Networkscited by 293
  13. 2022Long Range Graph Benchmarkcited by 258
  14. 2021Weisfeiler and Lehman Go Cellular: CW Networkscited by 218
  15. 2022Structure-Aware Transformer for Graph Representation Learningcited by 191
  16. 2022Sign and Basis Invariant Networks for Spectral Graph Representation Learningcited by 176
  17. 2021Equivariant Subgraph Aggregation Networkscited by 154
  18. 2021From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awarenesscited by 154
  19. 2021GraphiT: Encoding Graph Structure in Transformerscited by 146
  20. 2021Nested Graph Neural Networkscited by 136
  21. 2021AMMUS : A Survey of Transformer-based Pretrained Models in Natural Language Processingcited by 131
  22. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 121
  23. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  24. 2021DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networkscited by 117
  25. 2022Understanding and Extending Subgraph GNNs by Rethinking Their Symmetriescited by 112
  26. 2022Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networkscited by 94
  27. 2018Small ReLU networks are powerful memorizers: a tight analysis of memorization capacitycited by 76
  28. 2022GRPE: Relative Positional Encoding for Graph Transformercited by 67
  29. 2021Reconstruction for Powerful Graph Representationscited by 65
  30. 2023A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Testscited by 64
  31. 2022Ordered Subgraph Aggregation Networkscited by 57
  32. 2022Your Transformer May Not be as Powerful as You Expectcited by 55
  33. 2022Boosting the Cycle Counting Power of Graph Neural Networks with I2-GNNscited by 55
  34. 2022A Theoretical Comparison of Graph Neural Network Extensionscited by 47
  35. 2022Message passing all the way upcited by 47
  36. 2021From block-Toeplitz matrices to differential equations on graphs: towards a general theory for scalable masked Transformerscited by 38
  37. 2023Equivariant Polynomials for Graph Neural Networkscited by 38
  38. 2022SpeqNets: Sparsity-aware Permutation-equivariant Graph Networkscited by 37

50 most cited of 56 All 56 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 2; 2025: 4; 2026: 2.

8 papers.

  1. 2025Can Classic GNNs Be Strong Baselines for Graph-level Tasks? Simple Architectures Meet Excellencecited by 24
  2. 2024A Flexible, Equivariant Framework for Subgraph GNNs via Graph Products and Graph Coarseningcited by 8
  3. 2024Homomorphism Counts as Structural Encodings for Graph Learningcited by 6
  4. 2025Balancing Efficiency and Expressiveness: Subgraph GNNs with Walk-Based Centralitycited by 5
  5. 2025Learning Dynamic Graphs via Tensorized and Lightweight Graph Convolutional Networkscited by 0
  6. 2025On The Expressive Power of GNN Derivativescited by 0
  7. 2026Enhanced Graph Transformer with Serialized Graph Tokenscited by 0
  8. 2026Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networkscited by 0