mlsanityData to 14 Oct 2026

How Powerful are Graph Neural Networks?

arXiv 1810.00826 ↗First posted 1 Oct 2018cs.LG cs.CV stat.MLcited by 4,393

Not on the map. Why?

Cited by 68 in Diffusion models, but placed by its own abstract, which didn’t fit.

Abstract (arXiv)

Graph Neural Networks (GNNs) are an effective framework for representation learning of graphs. GNNs follow a neighborhood aggregation scheme, where the representation vector of a node is computed by recursively aggregating and transforming representation vectors of its neighboring nodes. Many GNN variants have been proposed and have achieved state-of-the-art results on both node and graph classification tasks. However, despite GNNs revolutionizing graph representation learning, there is limited understanding of their representational properties and limitations. Here, we present a theoretical framework for analyzing the expressive power of GNNs to capture different graph structures. Our results characterize the discriminative power of popular GNN variants, such as Graph Convolutional Networks and GraphSAGE, and show that they cannot learn to distinguish certain simple graph structures. We then develop a simple architecture that is provably the most expressive among the class of GNNs and is as powerful as the Weisfeiler-Lehman graph isomorphism test. We empirically validate our theoretical findings on a number of graph classification benchmarks, and demonstrate that our model achieves state-of-the-art performance.

Key facts. Cited by 4,393 papers in the map (data through 14 Oct 2026). First posted on arXiv 1 Oct 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2020: 1; 2021: 567; 2022: 727; 2023: 842; 2024: 919; 2025: 750; 2026: 587.

4,393 papers.

Sort:

By area:

  1. 2021Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gaugescited by 1,167
  2. 2021How Attentive are Graph Attention Networks?cited by 835
  3. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 713
  4. 2022DiGress: Discrete Denoising diffusion for graph generationcited by 520
  5. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 478
  6. 2021Rethinking Graph Transformers with Spectral Attentioncited by 473
  7. 2022GraphMAE: Self-Supervised Masked Graph Autoencoderscited by 448
  8. 2021Beyond Low-frequency Information in Graph Convolutional Networkscited by 362
  9. 2021GemNet: Universal Directional Graph Neural Networks for Moleculescited by 343
  10. 2023A critical look at the evaluation of GNNs under heterophily: Are we really making progress?cited by 343
  11. 2021Graph Neural Networks with Learnable Structural and Positional Representationscited by 333
  12. 2021OGB-LSC: A Large-Scale Challenge for Machine Learning on Graphscited by 329
38 more
  1. 2021Do Transformers Really Perform Bad for Graph Representation?cited by 320
  2. 2021Graph Self-Supervised Learning: A Surveycited by 289
  3. 2021Graph Contrastive Learning Automatedcited by 287
  4. 2021On Explainability of Graph Neural Networks via Subgraph Explorationscited by 281
  5. 2024A Survey on Vision-Language-Action Models for Embodied AIcited by 279
  6. 2021Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Predictioncited by 275
  7. 2020Permutation Invariant Graph Generation via Score-Based Generative Modelingcited by 270
  8. 2021Combinatorial optimization and reasoning with graph neural networkscited by 268
  9. 2021Therapeutics Data Commons: Machine Learning Datasets and Tasks for Drug Discovery and Developmentcited by 264
  10. 2022Equiformer: Equivariant Graph Attention Transformer for 3D Atomistic Graphscited by 264
  11. 2022Long Range Graph Benchmarkcited by 263
  12. 2021Pre-training Molecular Graph Representation with 3D Geometrycited by 248
  13. 2023One for All: Towards Training One Graph Model for All Classification Taskscited by 243
  14. 2021Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networkscited by 221
  15. 2023DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimizationcited by 221
  16. 2023Language is All a Graph Needscited by 220
  17. 2021Weisfeiler and Lehman Go Cellular: CW Networkscited by 218
  18. 2022Neural Sheaf Diffusion: A Topological Perspective on Heterophily and Oversmoothing in GNNscited by 214
  19. 2021ChemRL-GEM: Geometry Enhanced Molecular Representation Learning for Property Predictioncited by 204
  20. 2021CodeNet: A Large-Scale AI for Code Dataset for Learning a Diversity of Coding Taskscited by 200
  21. 2021Adversarial Graph Augmentation to Improve Graph Contrastive Learningcited by 200
  22. 2021Identity-aware Graph Neural Networkscited by 198
  23. 2022Representing Long-Range Context for Graph Neural Networks with Global Attentioncited by 195
  24. 2022Structure-Aware Transformer for Graph Representation Learningcited by 194
  25. 2023Large Language Models on Graphs: A Comprehensive Surveycited by 192
  26. 2022Discovering Invariant Rationales for Graph Neural Networkscited by 188
  27. 2022Pure Transformers are Powerful Graph Learnerscited by 188
  28. 2022Rethinking Graph Neural Networks for Anomaly Detectioncited by 187
  29. 2022Vision GNN: An Image is Worth Graph of Nodescited by 186
  30. 2021Self-Supervised Learning of Graph Neural Networks: A Unified Reviewcited by 184
  31. 2021Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networkscited by 182
  32. 2021Is Homophily a Necessity for Graph Neural Networks?cited by 182
  33. 2022Graph neural networks for materials science and chemistrycited by 182
  34. 2024LLaGA: Large Language and Graph Assistantcited by 181
  35. 2022Sign and Basis Invariant Networks for Spectral Graph Representation Learningcited by 179
  36. 2021Anomaly Detection on Attributed Networks via Contrastive Self-Supervised Learningcited by 177
  37. 2021Are we really making much progress? Revisiting, benchmarking, and refining heterogeneous graph neural networkscited by 176
  38. 2022Graph Neural Networks for Graphs with Heterophily: A Surveycited by 175

50 most cited of 4,393 All 4,393 (JSON)