How Powerful are Graph Neural Networks?
Open accessThe DOI matches its DataCite record; 44 of the 44 references it cites were found in a registry or an index.
Abstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Adam: A Method for Stochastic Optimization
Kingma, D. P., & Ba, J. (2014) · arXiv · doi:10.48550/arxiv.1412.6980 · Cited by 98,946
LIBSVM: A library for support vector machines
Chang, C.-C., & Lin, C.-J. (2011) · ACM Transactions on Intelligent Systems and Technology · doi:10.1145/1961189.1961199 · Cited by 40,918 · cited 2×
“We compare the GNNs above with a number of state-of-the-art baselines for graph classification: (1) The WL subtree kernel (Shervashidze et al., 2011), where C -SVM (Chang & Lin, 2011) was used as a classifier.”
Method(2014) · Cited by 33,419
Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift
Ioffe, S., & Szegedy, C. (2015) · arXiv · doi:10.48550/arxiv.1502.03167 · Cited by 27,818 · cited 1×
“Batch normalization (Ioffe & Szegedy, 2015) is applied on every hidden layer.”
MethodSemi-supervised classification with graph convolutional networks
Kipf, T. N., & Welling, M. (2016) · arXiv · doi:10.48550/arxiv.1609.02907 · Cited by 24,853
Multilayer feedforward networks are universal approximators
Hornik, K., Stinchcombe, M., & White, H. (1989) · Neural Networks · doi:10.1016/0893-6080(89)90020-8 · Cited by 21,728 · cited 2×
“Moreover, any function g over such pairs can be decomposed as g ( c, We can use multi-layer perceptrons (MLPs) to model and learn f and φ in Corollary 6, thanks to the universal approximation theorem (Hornik et al., 1989; Hornik, 1991).”
BackgroundMethodVeličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., & Bengio, Y. (2017) · arXiv · doi:10.48550/arxiv.1710.10903 · Cited by 12,107
Inductive Representation Learning on Large Graphs
Hamilton, W. L., Ying, R., & Leskovec, J. (2017) · arXiv · doi:10.48550/arxiv.1706.02216 · Cited by 10,639 · cited 9×
“Recently, there has been a surge of interest in Graph Neural Network (GNN) approaches for representation learning of graphs (Li et al., 2016; Hamilton et al., 2017a; Kipf & Welling, 2017; Velickovic et al., 2018; Xu et al., 2018).”
BackgroundMethodInfluentialSelf-citationThe graph neural network model
Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., & Monfardini, G. (2009) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2008.2005605 · Cited by 9,582 · cited 3×
“Not surprisingly, building blocks of GIN, e.g. sum aggregation and MLP encoding, also appeared in other models (Battaglia et al., 2016; Scarselli et al., 2009b; Duvenaud et al., 2015).”
BackgroundResultPointNet: Deep Learning on Point Sets for 3D Classification and Segmentation
Charles, R. Q., Su, H., Kaichun, M., & Guibas, L. J. (2017) · 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2017.16 · Cited by 9,237
Multilayer feedforward networks are universal approximators
HornikK., StinchcombeM., & WhiteH. (1989) · Neural Networks · doi:10.5555/70405.70408 · Cited by 9,081
Veličković, P., Casanova, A., Liò, P., Cucurull, G., Romero, A., & Bengio, Y. (2017) · arXiv (Cornell University) · doi:10.17863/cam.48429 · Cited by 8,657
Nelder, J. A., & Wedderburn, R. W. M. (1972) · Journal of the Royal Statistical Society. Series A (General) · doi:10.2307/2344614 · Cited by 7,194
Approximation capabilities of multilayer feedforward networks
Hornik, K. (1991) · Neural Networks · doi:10.1016/0893-6080(91)90009-t · Cited by 6,091
Advances In Deep Learning On Graphs (Gsp'18 Workshop)
Defferrard, M. (2016) · Figshare · doi:10.5281/zenodo.1286817 · Cited by 4,613
Neural Message Passing for Quantum Chemistry
Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., & Dahl, G. E. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1704.01212 · Cited by 3,440
Convolutional Networks on Graphs for Learning Molecular Fingerprints
Duvenaud, D., Maclaurin, D., Aguilera-Iparraguirre, J., Gómez-Bombarelli, R., Hirzel, T., Aspuru-Guzik, A., & Adams, R. P. (2015) · arXiv · doi:10.48550/arxiv.1509.09292 · Cited by 2,628
Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering
Defferrard, M., Bresson, X., & Vandergheynst, P. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1606.09375 · Cited by 1,673
Weisfeiler-Lehman Graph Kernels
Shervashidze, N., Schweitzer, P., van Leeuwen, E. J., Mehlhorn, K., & Borgwardt, K. M. (2010) · Max Planck Digital Library · Cited by 1,644
Molecular graph convolutions: moving beyond fingerprints
Kearnes, S., McCloskey, K., Berndl, M., Pande, V., & Riley, P. (2016) · Journal of Computer-Aided Molecular Design · doi:10.1007/s10822-016-9938-8 · Cited by 1,631 · cited 1×
“…schemes have been proposed (Scarselli et al., 2009b; Battaglia et al., 2016; Defferrard et al., 2016; Duvenaud et al., 2015; Hamilton et al., 2017a; Kearnes et al., 2016; Kipf & Welling, 2017; Li et al., 2016; Velickovic et al., 2018; Santoro et al., 2017; Xu et al., 2018; Santoro et al., 2018;…”
BackgroundAn End-to-End Deep Learning Architecture for Graph Classification
Zhang, M., Cui, Z., Neumann, M., & Chen, Y. (2018) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v32i1.11782 · Cited by 1,461
A simple neural network module for relational reasoning
Santoro, A., Raposo, D., Barrett, D. G. T., Malinowski, M., Pascanu, R., Battaglia, P., & Lillicrap, T. (2017) · arXiv · doi:10.48550/arxiv.1706.01427 · Cited by 1,281 · cited 2×
“…et al., 2016; Defferrard et al., 2016; Duvenaud et al., 2015; Hamilton et al., 2017a; Kearnes et al., 2016; Kipf & Welling, 2017; Li et al., 2016; Velickovic et al., 2018; Santoro et al., 2017; Xu et al., 2018; Santoro et al., 2018; Verma & Zhang, 2018; Ying et al., 2018; Zhang et al., 2018).”
BackgroundYanardag, P., & Vishwanathan, S. V. N. (2015) · Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining · doi:10.1145/2783258.2783417 · Cited by 1,021
Interaction Networks for Learning about Objects, Relations and Physics
Battaglia, P. W., Pascanu, R., Lai, M., Rezende, D., & Kavukcuoglu, K. (2016) · arXiv · doi:10.48550/arxiv.1612.00222 · Cited by 969 · cited 4×
“Recently, many GNN-based architectures have been proposed, including sum aggregation and MLP encoding (Battaglia et al., 2016; Scarselli et al., 2009b; Duvenaud et al., 2015), and most without theoretical derivation.”
BackgroundResultInfluentialDiffusion-Convolutional Neural Networks
Atwood, J. R., & Towsley, D. (2016) · neural information processing systems · Cited by 925
Representation Learning on Graphs with Jumping Knowledge Networks
Xu, K., Li, C., Tian, Y., Sonobe, T., Kawarabayashi, K., & Jegelka, S. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1806.03536 · Cited by 891
Self-citationHierarchical Graph Representation Learning with Differentiable Pooling
Ying, R., You, J., Morris, C., Ren, X., Hamilton, W. L., & Leskovec, J. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1806.08804 · Cited by 798
Self-citationLearning Convolutional Neural Networks for Graphs
Niepert, M., Ahmed, M. M., & Kutzkov, K. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1605.05273 · Cited by 775
Deep SetsPreprint
Zaheer, M., Kottur, S., Ravanbakhsh, S., Póczos, B., Salakhutdinov, R., & Smola, A. J. (2017) · arXiv (Cornell University) · Cited by 518
An optimal lower bound on the number of variables for graph identification
Cai, J.-Y., F�rer, M., & Immerman, N. (1992) · Combinatorica · doi:10.1007/bf01305232 · Cited by 502
Graph isomorphism in quasipolynomial time [extended abstract]
Babai, L. (2016) · Proceedings of the forty-eighth annual ACM symposium on Theory of Computing · doi:10.1145/2897518.2897542 · Cited by 415
Gated Graph Sequence Neural Networks
Li, Y., Tarlow, D., Brockschmidt, M., & Zemel, R. S. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1511.05493 · Cited by 362
Representation Learning on Graphs: Methods and Applications
Hamilton, W. L., Ying, R., & Leskovec, J. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1709.05584 · Cited by 290
Self-citationGraph Isomorphism in Quasipolynomial Time
Babai, L. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1512.03547 · Cited by 264
Computational Capabilities of Graph Neural Networks
Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., & Monfardini, G. (2009) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2008.2005141 · Cited by 225
Anonymous Walk EmbeddingsPreprint
Ivanov, S., & Burnaev, E. V. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1805.11921 · Cited by 206
Janossy Pooling: Learning Deep Permutation-Invariant Functions for Variable-Size InputsPreprint
Murphy, R. L., Srinivasan, B., Rao, V., & Ribeiro, B. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1811.01900 · Cited by 195
Canonical labelling of graphs in linear average time
Babai, L., & Kucera, L. (1979) · 20th Annual Symposium on Foundations of Computer Science (sfcs 1979) · doi:10.1109/sfcs.1979.8 · Cited by 158
Deriving Neural Architectures from Sequence and Graph KernelsPreprint
Lei, T., Jin, W., Barzilay, R., & Jaakkola, T. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1705.09037 · Cited by 155
Graph Capsule Convolutional Neural NetworksPreprint
Verma, S. M., & Zhang, Z. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1805.08090 · Cited by 143
Measuring abstract reasoning in neural networks
Barrett, D. G. T., Hill, F., Santoro, A., Morcos, A. S., & Lillicrap, T. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1807.04225 · Cited by 135
The Weisfeiler-Lehman Method and Graph Isomorphism TestingPreprint
Douglas, B. L. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1101.5211 · Cited by 85
Isomorphism of Coloured Graphs with Slowly Increasing Multiplicity of Jordan Blocks
Евдокимов, С. А., & Ponomarenko, I. N. (1999) · COMBINATORICA · doi:10.1007/s004930050059 · Cited by 27
Chen, T., Wang, Z., Li, L., Li, D., Li, Z., Chang, X., Bian, P., Liang, G., Wang, Q., & Xie, T. (2025) · Schloss Dagstuhl – Leibniz-Zentrum für Informatik · doi:10.4230/lipics.ecoop.2025.6
Cited by
A Comprehensive Survey on Graph Neural Networks
Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., & Yu, P. S. (2021) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2020.2978386 · Cited by 11,000
“However, Graph Isomorphism Network (GIN) [57] finds that previous MPNN-based methods are incapable of distinguishing different graph structures based on the graph embedding they produced.”
BackgroundMethodInfluentialGraph neural networks: A review of methods and applications
Zhou, J., Cui, G., Hu, S., Zhang, Z., Yang, C., Liu, Z., Wang, L., Li, C., & Sun, M. (2020) · AI Open · doi:10.1016/j.aiopen.2021.01.001 · Cited by 6,880
Graph Neural Networks: A Review of Methods and Applications
Zhou, J., Cui, G., Hu, S., Zhang, Z., Yang, C., Liu, Z., Wang, L., Li, C., & Sun, M. (2018) · arXiv · doi:10.48550/arxiv.1812.08434 · Cited by 6,880
LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation
He, X., Deng, K., Wang, X., Li, Y., Zhang, Y., & Wang, M. (2020) · Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval · doi:10.1145/3397271.3401063 · Cited by 4,430
Hogan, A., Blomqvist, E., Cochez, M., D’amato, C., Melo, G. D., Gutierrez, C., Kirrane, S., Gayo, J. E. L., Navigli, R., Neumaier, S., et al. (2022) · ACM Computing Surveys · doi:10.1145/3447772 · Cited by 1,904
Metadata
- Authors
- Xu, K., Hu, W., Leskovec, J., & Jegelka, S.
- Affiliations
- Massachusetts Institute of Technology (US)
- Stanford University (US)
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2018
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 1810.00826
- OpenAlex
- W2894175828
- Cited by
- 6,078
- References
- 41
- Citations by year
- 2026: 408 · 2025: 837 · 2024: 1293 · 2023: 1064 · 2022: 807 · 2021: 921 · 2020: 570 · 2019: 171 · 2018: 7
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Zenodo (CERN European Organization for Nuclear Research) (cc-by)
- Funders
- National Science Foundation (1553284, CAREER)
- Defense Advanced Research Projects Agency
- Multidisciplinary University Research Initiative
- Army Research Office
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Advanced Graph Neural Networks
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Graph Theory and Algorithms
- Physical Sciences › Computer Science › Artificial Intelligence › Neural Networks and Applications
- Keywords
- graph neural networks, expressiveness, neighborhood aggregation, Kolmogorov-Arnold networks, graph isomorphism, Weisfeiler-Lehman test, graph classification, graph representation learning, graph convolutional networks, GraphSAGE, formal semantics
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.