mlsanityData to 7 Oct 2026

What graph neural networks cannot learn: depth vs width

arXiv 1907.03199 ↗First posted 6 Jul 2019cs.LG stat.MLcited by 195

Not on the map. Why?

Abstract (arXiv)

This paper studies the expressive power of graph neural networks falling within the message-passing framework (GNNmp). Two results are presented. First, GNNmp are shown to be Turing universal under sufficient conditions on their depth, width, node attributes, and layer expressiveness. Second, it is discovered that GNNmp can lose a significant portion of their power when their depth and width is restricted. The proposed impossibility statements stem from a new technique that enables the repurposing of seminal results from distributed computing and leads to lower bounds for an array of decision, optimization, and estimation problems involving graphs. Strikingly, several of these problems are deemed impossible unless the product of a GNNmp's depth and width exceeds a polynomial of the graph size; this dependence remains significant even for tasks that appear simple or when considering approximation.

Key facts. Cited by 195 papers in the map (data through 7 Oct 2026). First posted on arXiv 6 Jul 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 35; 2022: 52; 2023: 30; 2024: 40; 2025: 21; 2026: 17.

195 papers.

Sort:

By area:

  1. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 702
  2. 2021Graph Neural Networks with Learnable Structural and Positional Representationscited by 326
  3. 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
  4. 2022How Powerful are Spectral Graph Neural Networkscited by 169
  5. 2021Frame Averaging for Invariant and Equivariant Network Designcited by 166
  6. 2021Equivariant Subgraph Aggregation Networkscited by 154
  7. 2021From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awarenesscited by 154
  8. 2023Graph Inductive Biases in Transformers without Message Passingcited by 150
  9. 2021Nested Graph Neural Networkscited by 136
  10. 2023Representational Strengths and Limitations of Transformerscited by 132
  11. 2021Interpreting and Unifying Graph Neural Networks with An Optimization Frameworkcited by 131
  12. 2021Scalars are universal: Equivariant machine learning, structured like classical physicscited by 127
38 more
  1. 2021DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networkscited by 117
  2. 2022Not too little, not too much: a theoretical analysis of graph (over)smoothingcited by 106
  3. 2022A Generalization of ViT/MLP-Mixer to Graphscited by 93
  4. 2022How Powerful are K-hop Message Passing Graph Neural Networkscited by 90
  5. 2023Everything is Connected: Graph Neural Networkscited by 85
  6. 2021OOD-GNN: Out-of-Distribution Generalized Graph Neural Networkcited by 78
  7. 2024Transformers, parallel computation, and logarithmic depthcited by 75
  8. 2021Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalizationcited by 70
  9. 2024Understanding Transformer Reasoning Capabilities via Graph Algorithmscited by 64
  10. 2022Benchmarking Graphormer on Large-Scale Molecular Modeling Datasetscited by 63
  11. 2022Theory of Graph Neural Networks: Representation and Learningcited by 60
  12. 2021On Provable Benefits of Depth in Training Graph Convolutional Networkscited by 58
  13. 2022Provably expressive temporal graph networkscited by 56
  14. 2022Boosting the Cycle Counting Power of Graph Neural Networks with I2-GNNscited by 55
  15. 2023How does over-squashing affect the power of GNNs?cited by 53
  16. 2022A Short Tutorial on The Weisfeiler-Lehman Test And Its Variantscited by 52
  17. 2021Graph Neural Networks with Local Graph Parameterscited by 51
  18. 2022A Theoretical Comparison of Graph Neural Network Extensionscited by 47
  19. 2022Message passing all the way upcited by 47
  20. 2022Shortest Path Networks for Graph Property Predictioncited by 46
  21. 2022Graph Neural Networks for Wireless Communications: From Theory to Practicecited by 44
  22. 2021Boost then Convolve: Gradient Boosting Meets Graph Neural Networkscited by 42
  23. 2021VQ-GNN: A Universal Framework to Scale up Graph Neural Networks using Vector Quantizationcited by 39
  24. 2021p-Laplacian Based Graph Neural Networkscited by 39
  25. 2022On Representing Linear Programs by Graph Neural Networkscited by 39
  26. 2021Lipschitz Normalization for Self-Attention Layers with Application to Graph Neural Networkscited by 38
  27. 2021On Representation Knowledge Distillation for Graph Neural Networkscited by 38
  28. 2023Equivariant Polynomials for Graph Neural Networkscited by 38
  29. 2022SizeShiftReg: a Regularization Method for Improving Size-Generalization in Graph Neural Networkscited by 36
  30. 2023Cooperative Graph Neural Networkscited by 35
  31. 2022Generalised Implicit Neural Representationscited by 31
  32. 2024How Do Large Language Models Understand Graph Patterns? A Benchmark for Graph Pattern Comprehensioncited by 30
  33. 2025Relational Graph Transformercited by 30
  34. 2024Simulation of Graph Algorithms with Looped Transformerscited by 29
  35. 2021Spatial Aggregation and Temporal Convolution Networks for Real-time Krigingcited by 27
  36. 2023The Expressive Power of Graph Neural Networks: A Surveycited by 27
  37. 2021On the Universality of Graph Neural Networks on Large Random Graphscited by 26
  38. 2023Probabilistically Rewired Message-Passing Neural Networkscited by 26

50 most cited of 195 All 195 (JSON)