mlsanityData to 7 Oct 2026

What functions can Graph Neural Networks compute on random graphs? The role of Positional Encoding

arXiv 2305.14814 ↗First posted 24 May 2023cs.LG stat.MLcited by 11

Not on the map. Why?

Abstract (arXiv)

We aim to deepen the theoretical understanding of Graph Neural Networks (GNNs) on large graphs, with a focus on their expressive power. Existing analyses relate this notion to the graph isomorphism problem, which is mostly relevant for graphs of small sizes, or studied graph classification or regression tasks, while prediction tasks on nodes are far more relevant on large graphs. Recently, several works showed that, on very general random graphs models, GNNs converge to certains functions as the number of nodes grows. In this paper, we provide a more complete and intuitive description of the function space generated by equivariant GNNs for node-tasks, through general notions of convergence that encompass several previous examples. We emphasize the role of input node features, and study the impact of node Positional Encodings (PEs), a recent line of work that has been shown to yield state-of-the-art results in practice. Through the study of several examples of PEs on large random graphs, we extend previously known universality results to significantly more general models. Our theoretical results hint at some normalization tricks, which is shown numerically to have a positive impact on GNN generalization on synthetic and real data. Our proofs contain new concentration inequalities of independent interest.

Key facts. Cited by 11 papers in the map (data through 7 Oct 2026). Builds on 35 of its 57 references that are in the map. First posted on arXiv 24 May 2023.

Builds on

35 of 57 references.

References · 35

  1. 2017Attention Is All You Needcited by 59,932
  2. 2018How Powerful are Graph Neural Networks?cited by 4,355
  3. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
  4. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,148
  5. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
  6. 2019Simplifying Graph Convolutional Networkscited by 1,470
  7. 2017Deep Setscited by 1,394
  8. 2021Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gaugescited by 1,131
  9. 2020A Generalization of Transformer Networks to Graphscited by 653
  10. 2019Provably Powerful Graph Networkscited by 385
  11. 2021Graph Neural Networks with Learnable Structural and Positional Representationscited by 326
  12. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 312
23 more
  1. 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
  2. 2018Graph networks as learnable physics engines for inference and controlcited by 242
  3. 2019Position-aware Graph Neural Networkscited by 203
  4. 2019What graph neural networks cannot learn: depth vs widthcited by 195
  5. 2020Random Features Strengthen Graph Neural Networkscited by 184
  6. 2019Universal Invariant and Equivariant Graph Neural Networkscited by 182
  7. 2022Sign and Basis Invariant Networks for Spectral Graph Representation Learningcited by 176
  8. 2019On the Universality of Invariant Networkscited by 151
  9. 2013Consistency of spectral clustering in stochastic block modelscited by 128
  10. 2020Graphon Neural Networks and the Transferability of Graph Neural Networkscited by 117
  11. 2022Not too little, not too much: a theoretical analysis of graph (over)smoothingcited by 106
  12. 2018Billion-scale Commodity Embedding for E-commerce Recommendation in Alibabacited by 105
  13. 2019Transferability of Spectral Graph Convolutional Neural Networkscited by 90
  14. 2020Convergence and Stability of Graph Convolutional Networks on Large Random Graphscited by 75
  15. 2021Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalizationcited by 70
  16. 2022Generalization Analysis of Message Passing Neural Networks on Large Random Graphscited by 58
  17. 2022A Theoretical Comparison of Graph Neural Network Extensionscited by 47
  18. 2020AutoKnow: Self-Driving Knowledge Collection for Products of Thousands of Typescited by 31
  19. 2021On the Universality of Graph Neural Networks on Large Random Graphscited by 26
  20. 2022Effects of Graph Convolutions in Multi-layer Networkscited by 24
  21. 2021Power to the Relational Inductive Bias: Graph Neural Networks in Electrical Power Gridscited by 18
  22. 2023Convergence of Message Passing Graph Neural Networks with Generic Aggregation On Large Random Graphscited by 9
  23. 2022On Classification Thresholds for Graph Attention with Edge Featurescited by 5

Built on by

Cited by year (2026 to 7 Oct)

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

11 papers.

  1. 2023SwinGNN: Rethinking Permutation Invariance in Diffusion Models for Graph Generationcited by 26
  2. 2023Expressive Sign Equivariant Networks for Spectral Geometric Learningcited by 15
  3. 2024Benchmarking Positional Encodings for GNNs and Graph Transformerscited by 13
  4. 2023Quantifying the Optimization and Generalization Advantages of Graph Neural Networks Over Multilayer Perceptronscited by 12
  5. 2025Geometric Algorithms for Neural Combinatorial Optimization with Constraintscited by 4
  6. 2024From Learning to Optimize to Learning Optimization Algorithmscited by 2
  7. 2024Disentangled Structural and Featural Representation for Task-Agnostic Graph Valuationcited by 2
  8. 2024LASE: Learned Adjacency Spectral Embeddingscited by 0
  9. 2025On the Convergence and Size Transferability of Continuous-depth Graph Neural Networkscited by 0
  10. 2026Converse and Collision-Based Achievability for Node Localization with Hybrid Distance-Spectral Graph Positional Encodingscited by 0
  11. 2026Self-Supervised Combinatorial Optimization with Constraints via Frank-Wolfecited by 0