CoChat

How Powerful are Graph Neural Networks?

Open access

The 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.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.1810.00826

Cites

44 of 44 references verified0 citation errors · 0 not checkable

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.

A few free checks a day · papers already verified open instantly · results are public

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

Cited by

See all 6,078

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)
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
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.