mlsanityData to 7 Oct 2026

SpeqNets: Sparsity-aware Permutation-equivariant Graph Networks

arXiv 2203.13913 ↗First posted 25 Mar 2022cs.LG cs.AI cs.DScited by 37

Not on the map. Why?

Abstract (arXiv)

While (message-passing) graph neural networks have clear limitations in approximating permutation-equivariant functions over graphs or general relational data, more expressive, higher-order graph neural networks do not scale to large graphs. They either operate on k-order tensors or consider all k-node subgraphs, implying an exponential dependence on k in memory requirements, and do not adapt to the sparsity of the graph. By introducing new heuristics for the graph isomorphism problem, we devise a class of universal, permutation-equivariant graph networks, which, unlike previous architectures, offer a fine-grained control between expressivity and scalability and adapt to the sparsity of the graph. These architectures lead to vastly reduced computation times compared to standard higher-order graph networks in the supervised node- and graph-level classification and regression regime while significantly improving over standard graph neural network and graph kernel architectures in terms of predictive performance.

Key facts. Cited by 37 papers in the map (data through 7 Oct 2026). Builds on 83 of its 135 references that are in the map. First posted on arXiv 25 Mar 2022.

Builds on

83 of 135 references.

References · 83

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Graph Attention Networkscited by 8,854
  3. 2017Inductive Representation Learning on Large Graphscited by 6,284
  4. 2018How Powerful are Graph Neural Networks?cited by 4,355
  5. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  6. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
  7. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,414
  8. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
  9. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,571
  10. 2013Spectral Networks and Locally Connected Networks on Graphscited by 1,097
  11. 2017MoleculeNet: A Benchmark for Molecular Machine Learningcited by 1,037
  12. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
38 more
  1. 2018Representation Learning on Graphs with Jumping Knowledge Networkscited by 875
  2. 2020Geom-GCN: Geometric Graph Convolutional Networkscited by 821
  3. 2018Hierarchical Graph Representation Learning with Differentiable Poolingcited by 786
  4. 2015Convolutional Networks on Graphs for Learning Molecular Fingerprintscited by 751
  5. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 718
  6. 2019DropEdge: Towards Deep Graph Convolutional Networks on Node Classificationcited by 679
  7. 2020Directional Message Passing for Molecular Graphscited by 556
  8. 2019Graph U-Netscited by 489
  9. 2020Principal Neighbourhood Aggregation for Graph Netscited by 477
  10. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 471
  11. 2016Geometric deep learning on graphs and manifolds using mixture model CNNscited by 468
  12. 2019MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixingcited by 442
  13. 2019Hyperbolic Graph Convolutional Neural Networkscited by 400
  14. 2019Provably Powerful Graph Networkscited by 385
  15. 2021GemNet: Universal Directional Graph Neural Networks for Moleculescited by 342
  16. 2016Learning Convolutional Neural Networks for Graphscited by 314
  17. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 312
  18. 2017Dynamic Edge-Conditioned Filters in Convolutional Neural Networks on Graphscited by 307
  19. 2019Cormorant: Covariant Molecular Neural Networkscited by 262
  20. 2015Order Matters: Sequence to sequence for setscited by 236
  21. 2020Can Graph Neural Networks Count Substructures?cited by 235
  22. 2021Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networkscited by 219
  23. 2021Weisfeiler and Lehman Go Cellular: CW Networkscited by 218
  24. 2019Position-aware Graph Neural Networkscited by 203
  25. 2021Identity-aware Graph Neural Networkscited by 197
  26. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 190
  27. 2020Random Features Strengthen Graph Neural Networkscited by 184
  28. 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
  29. 2020Machine Learning on Graphs: A Model and Comprehensive Taxonomycited by 156
  30. 2021Equivariant Subgraph Aggregation Networkscited by 154
  31. 2021From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awarenesscited by 154
  32. 2019On the Universality of Invariant Networkscited by 151
  33. 2019Relational Pooling for Graph Representationscited by 150
  34. 2019A Survey on Graph Kernelscited by 148
  35. 2021Nested Graph Neural Networkscited by 136
  36. 2020Directional Graph Networkscited by 132
  37. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 121
  38. 2021DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networkscited by 117

50 most cited of 83 All 83 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 8; 2023: 11; 2024: 10; 2025: 4; 2026: 4.

37 papers.

Sort:

By area:

  1. 2022DiGress: Discrete Denoising diffusion for graph generationcited by 503
  2. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  3. 2022Understanding and Extending Subgraph GNNs by Rethinking Their Symmetriescited by 112
  4. 2023A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Testscited by 64
  5. 2022Ordered Subgraph Aggregation Networkscited by 57
  6. 2023Equivariant Polynomials for Graph Neural Networkscited by 38
  7. 2024Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressivenesscited by 38
  8. 2023WL meet VCcited by 30
  9. 2022Weisfeiler and Leman Go Relationalcited by 28
  10. 2023Fine-grained Expressivity of Graph Neural Networkscited by 25
  11. 2024Pard: Permutation-Invariant Autoregressive Diffusion for Graph Generationcited by 25
  12. 2023Is Distance Matrix Enough for Geometric Deep Learning?cited by 22
25 more
  1. 2022A Practical, Progressively-Expressive GNNcited by 20
  2. 2023Permutation Equivariant Graph Framelets for Heterophilous Graph Learningcited by 19
  3. 2022Learnable Polyphase Sampling for Shift Invariant and Equivariant Convolutional Networkscited by 18
  4. 2023Making Vision Transformers Truly Shift-Equivariantcited by 16
  5. 2023Truly Scale-Equivariant Deep Nets with Fourier Layerscited by 16
  6. 2022Agent-based Graph Neural Networkscited by 13
  7. 2024Weisfeiler-Leman at the margin: When more expressivity matterscited by 13
  8. 2024Towards Principled Graph Transformerscited by 11
  9. 2024Subgraphormer: Unifying Subgraph GNNs and Graph Transformers via Graph Productscited by 8
  10. 2024Aligning Transformers with Weisfeiler-Lemancited by 8
  11. 2022Empowering GNNs via Edge-Aware Weisfeiler-Leman Algorithmcited by 4
  12. 2025Graph Representational Learning: When Does More Expressivity Hurt Generalization?cited by 4
  13. 2024Foundations and Frontiers of Graph Learning Theorycited by 3
  14. 2025Group Downsampling with Equivariant Anti-aliasingcited by 3
  15. 2024Scalable Expressiveness through Preprocessed Graph Perturbationscited by 2
  16. 2024Current Symmetry Group Equivariant Convolution Frameworks for Representation Learningcited by 2
  17. 2025Weisfeiler-Leman Features for Planning: A 1,000,000 Sample Size Hyperparameter Studycited by 2
  18. 2023Fisher Information Embedding for Node and Graph Learningcited by 1
  19. 2026On the Expressive Power of GNNs to Solve Linear SDPscited by 1
  20. 2023Concept Prerequisite Relation Prediction by Using Permutation-Equivariant Directed Graph Neural Networkscited by 0
  21. 2024Graph Learning for Planning: The Story Thus Far and Open Challengescited by 0
  22. 2025Permutation Equivariant Neural Networks for Symmetric Tensorscited by 0
  23. 2026A Boolean Function-Theoretic Framework for Expressivity in GNNs with Applications to Fair Graph Miningcited by 0
  24. 2026Tunable Soft Equivariance with Guaranteescited by 0
  25. 2026Solving Max-Cut to Global Optimality via Feasibility-Preserving Graph Neural Networkscited by 0