mlsanityData to 7 Oct 2026

Graph Neural Networks with Local Graph Parameters

arXiv 2106.06707 ↗First posted 12 Jun 2021cs.LGcited by 51

Not on the map. Why?

Abstract (arXiv)

Various recent proposals increase the distinguishing power of Graph Neural Networks GNNs by propagating features between k-tuples of vertices. The distinguishing power of these "higher-order'' GNNs is known to be bounded by the k-dimensional Weisfeiler-Leman (WL) test, yet their mathcal O(nk) memory requirements limit their applicability. Other proposals infuse GNNs with local higher-order graph structural information from the start, hereby inheriting the desirable mathcal O(n) memory requirement from GNNs at the cost of a one-time, possibly non-linear, preprocessing step. We propose local graph parameter enabled GNNs as a framework for studying the latter kind of approaches and precisely characterize their distinguishing power, in terms of a variant of the WL test, and in terms of the graph structural properties that they can take into account. Local graph parameters can be added to any GNN architecture, and are cheap to compute. In terms of expressive power, our proposal lies in the middle of GNNs and their higher-order counterparts. Further, we propose several techniques to aide in choosing the right local graph parameters. Our results connect GNNs with deep results in finite model theory and finite variable logics. Our experimental evaluation shows that adding local graph parameters often has a positive effect for a variety of GNNs, datasets and graph learning tasks.

Key facts. Cited by 51 papers in the map (data through 7 Oct 2026). Builds on 43 of its 81 references that are in the map. First posted on arXiv 12 Jun 2021.

Builds on

43 of 81 references.

References · 43

  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. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,148
  8. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  9. 2020Benchmarking Graph Neural Networkscited by 672
  10. 2019Quantifying the Carbon Emissions of Machine Learningcited by 516
  11. 2016Geometric deep learning on graphs and manifolds using mixture model CNNscited by 468
  12. 2019Provably Powerful Graph Networkscited by 385
31 more
  1. 2017Residual Gated Graph ConvNetscited by 341
  2. 2018Invariant and Equivariant Graph Networkscited by 339
  3. 2017Community Detection and Stochastic Block Modelscited by 317
  4. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 312
  5. 2020Can Graph Neural Networks Count Substructures?cited by 235
  6. 2020Generalization and Representational Limits of Graph Neural Networkscited by 217
  7. 2019What graph neural networks cannot learn: depth vs widthcited by 195
  8. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 190
  9. 2020Random Features Strengthen Graph Neural Networkscited by 184
  10. 2019Universal Invariant and Equivariant Graph Neural Networkscited by 182
  11. 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
  12. 2020Machine Learning on Graphs: A Model and Comprehensive Taxonomycited by 156
  13. 2019On the Universality of Invariant Networkscited by 151
  14. 2020A Survey on The Expressive Power of Graph Neural Networkscited by 111
  15. 2020Expressive Power of Invariant and Equivariant Graph Neural Networkscited by 100
  16. 2020Building powerful and equivariant graph neural networks with structural message-passingcited by 95
  17. 2019Approximation Ratios of Graph Neural Networks for Combinatorial Problemscited by 68
  18. 2018On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Propertiescited by 63
  19. 2019Are Powerful Graph Neural Nets Necessary? A Dissection on Graph Classificationcited by 39
  20. 2020word2vec, node2vec, graph2vec, X2vec: Towards a Theory of Vector Embeddings of Structured Datacited by 38
  21. 2020The expressive power of kth-order invariant graph networkscited by 34
  22. 2020Graph Homomorphism Convolutioncited by 27
  23. 2018Lov'asz Meets Weisfeiler and Lemancited by 26
  24. 2020Let's Agree to Degree: Comparing Graph Convolutional Networks in the Message-Passing Frameworkcited by 24
  25. 2020Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Resultscited by 19
  26. 2017On the Combinatorial Power of the Weisfeiler-Lehman Algorithmcited by 18
  27. 2017Homomorphisms Are a Good Basis for Counting Small Subgraphscited by 14
  28. 2020A Novel Higher-order Weisfeiler-Lehman Graph Convolutioncited by 10
  29. 2019A Hierarchy of Graph Neural Networks Based on Learnable Local Featurescited by 5
  30. 2020Weisfeiler-Lehman Embedding for Molecular Graph Neural Networkscited by 2
  31. 2020Counting Bounded Tree Depth Homomorphismscited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 8; 2023: 18; 2024: 14; 2025: 5; 2026: 3.

51 papers.

Sort:

  1. 2021From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awarenesscited by 154
  2. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 121
  3. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  4. 2022A Survey on Graph Representation Learning Methodscited by 66
  5. 2023A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Testscited by 64
  6. 2022Ordered Subgraph Aggregation Networkscited by 57
  7. 2022Boosting the Cycle Counting Power of Graph Neural Networks with I2-GNNscited by 55
  8. 2022A Theoretical Comparison of Graph Neural Network Extensionscited by 47
  9. 2023Equivariant Polynomials for Graph Neural Networkscited by 38
  10. 2024Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressivenesscited by 38
  11. 2022SpeqNets: Sparsity-aware Permutation-equivariant Graph Networkscited by 37
  12. 2023Cooperative Graph Neural Networkscited by 35
38 more
  1. 2023On the Stability of Expressive Positional Encodings for Graphscited by 31
  2. 2023WL meet VCcited by 30
  3. 2023Fine-grained Expressivity of Graph Neural Networkscited by 25
  4. 2023Provably Powerful Graph Neural Networks for Directed Multigraphscited by 24
  5. 2023Some Might Say All You Need Is Sumcited by 21
  6. 2022Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networkscited by 20
  7. 2024Distinguished In Uniform: Self Attention Vs. Virtual Nodescited by 19
  8. 2023Curvature Filtrations for Graph Generative Model Evaluationcited by 18
  9. 2023Efficient Subgraph GNNs by Learning Effective Selection Policiescited by 17
  10. 2024Homomorphism Counts for Graph Neural Networks: All About That Basiscited by 16
  11. 2022Going Deeper into Permutation-Sensitive Graph Neural Networkscited by 15
  12. 2023An Efficient Subgraph GNN with Provable Substructure Counting Powercited by 13
  13. 2024Weisfeiler-Leman at the margin: When more expressivity matterscited by 13
  14. 2022On the Ability of Graph Neural Networks to Model Interactions Between Verticescited by 12
  15. 2024Towards Bridging Generalization and Expressivity of Graph Neural Networkscited by 12
  16. 2023Expectation-Complete Graph Representations with Homomorphismscited by 10
  17. 2021Graph Filtration Kernelscited by 8
  18. 2023On the Power of the Weisfeiler-Leman Test for Graph Motif Parameterscited by 6
  19. 2024Homomorphism Counts as Structural Encodings for Graph Learningcited by 6
  20. 2023LON-GNN: Spectral GNNs with Learnable Orthonormal Basiscited by 4
  21. 2025Graph Representational Learning: When Does More Expressivity Hurt Generalization?cited by 4
  22. 2023Structural Node Embeddings with Homomorphism Countscited by 3
  23. 2024Iterative Graph Neural Network Enhancement via Frequent Subgraph Mining of Explanationscited by 3
  24. 2024Foundations and Frontiers of Graph Learning Theorycited by 3
  25. 2025Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualizationcited by 3
  26. 2023Permutation-Invariant Graph Partitioning:How Graph Neural Networks Capture Structural Interactions?cited by 2
  27. 2024Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learningcited by 2
  28. 2024Scalable Expressiveness through Preprocessed Graph Perturbationscited by 2
  29. 2024Towards Stable, Globally Expressive Graph Representations with Laplacian Eigenvectorscited by 2
  30. 2023A Network Science perspective of Graph Convolutional Networks: A surveycited by 1
  31. 2024MEGA: Message Passing Neural Networks for Multigraphs with EdGe Attributescited by 1
  32. 2024Generalization of Graph Neural Networks through the Lens of Homomorphismcited by 0
  33. 2024Fine-Grained Expressive Power of Weisfeiler-Leman: A Homomorphism Counting Perspectivecited by 0
  34. 2025Caterpillar GNN: Replacing Message Passing with Efficient Aggregationcited by 0
  35. 2025Exact Subgraph Isomorphism Network with Mixed L0,2 Norm Constraint for Predictive Graph Miningcited by 0
  36. 2025Message Passing on the Edge: Towards Scalable and Expressive GNNscited by 0
  37. 2026Unifying approach to uniform expressivity of graph neural networkscited by 0
  38. 2026Property-Driven Evaluation of GNN Expressiveness at Scale: Datasets, Framework, and Studycited by 0

50 most cited of 51 All 51 (JSON)