How Powerful are Graph Neural Networks?
By Keyulu Xu, Weihua Hu, Jure Leskovec, Stefanie Sabrina Jegelka. 2018
10,110 citations recorded by the source corpus.
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.
Subfields: Artificial Intelligence, Statistical and Nonlinear Physics, Graph Learning
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Yoshua Bengio
- Mohit Bansal
- Percy Liang
- Quoc V. Le
- Jianfeng Gao
- Ruslan Salakhutdinov
- Sergey Levine
- Dacheng Tao
In Statistical and Nonlinear Physics
- Jure Leskovec
- William L. Hamilton
- Stephan Günnemann
- Matthias Fey
- Bryan Perozzi
- Michael M. Bronstein
- Philip S. Yu
- Huan Liu
In Graph Learning
- William L. Hamilton
- Jure Leskovec
- Stephan Günnemann
- Matthias Fey
- Michael M. Bronstein
- Marinka Zitnik
- Rex Ying
- Jian Tang
Citations in the corpus
- Graph-based, Self-Supervised Program Repair from Diagnostic Feedback (2020, background): “Graph neural nets (GNN), such as graph attention net (Velikovi et al., 2018), graph convolutional net (Kipf & Welling, 2017), graph isomorphism net (Xu et al., 2019) pre-training Typically, the self-supervised objective is different from the target task: For instance, in image recognition, Vincent…”
- Multiset-Equivariant Set Prediction with Approximate Implicit Differentiation (2021, background): “The difference between operating on sets versus multisets has also been studied in the context of graph neighborhood aggregation (Xu et al., 2018).”
- Strategies for Pre-training Graph Neural Networks (2019, methodology): “We mainly study Graph Isomorphism Networks (GINs) (Xu et al., 2019), the most expressive and state-of-the-art GNN architecture for graph-level prediction tasks.”
- Directional Message Passing for Molecular Graphs (2020, background): “Instead, they usually use a cutoff distance c , which means they cannot distinguish between certain molecules (Xu et al., 2019).”
- Fast Graph Representation Learning with PyTorch Geometric (2019, background): “…(Hamilton et al., 2017), the attention-based operators GAT (Veličković et al., 2018) and AGNN (Thekumparampil et al., 2018), the Graph Isomorphism Network (GIN) from Xu et al. (2019), and the Approximate Personalized Propagation of Neural Predictions (APPNP) operator (Klicpera et al., 2019).”
- Position-aware Graph Neural Networks (2019, methodology): “We consider 4 variants of GNNs, each with three layers, including GCN (Kipf & Welling, 2017), Graph-SAGE (Hamilton et al., 2017a), Graph Attention Networks (GAT) (Velickovic et al., 2018) and Graph Isomorphism Network (GIN) (Xu et al., 2019).”
- Unsupervised Inductive Whole-Graph Embedding by Preserving Graph Proximity (2019, methodology): “GIN has been proven to be theoretically the most powerful GNN under the neighbor aggregation framework (Xu et al., 2019).”
- Graph Warp Module: an Auxiliary Module for Boosting the Power of Graph Neural Networks (2019, background): “Moreover, the architecture they proposed as a solution to this problem, (designated as GIN in the Fig.”
- Set2Graph: Learning Graphs From Sets (2020, background): “…e.g., set learning (Zaheer et al., 2017; Qi et al., 2017), graph learning (Kipf & Welling, 2016; Gilmer et al., 2017; Veliˇckovi´c et al., 2017; Xu et al., 2019; Kondor et al., 2018; Maron et al., 2019b;a), learning images with rotational and reflectional symmetries (Cohen & Welling, 2016a;b;…”
- TANKBind: Trigonometry-Aware Neural NetworKs for Drug-Protein Binding Structure Prediction (2022, methodology): “We use Graph Isomorphism Network (GIN) Xu et al. [2018] to embed the compound and arrive at feature h c ∈ R m × s after graph propagation, where m is the number of heavy atoms and s is the embedding size.”
- Masked Label Prediction: Unified Massage Passing Model for Semi-Supervised Classification (2020, methodology): “…are two main kinds of methods to implement message passing model, Graph Neural Networks (GNNs) [ Kipf and Welling, 2016; Hamilton et al. , 2017; Xu et al. , 2018b; Liao et al. , 2019; Xu et al. , 2018a ] and Label Propagation Algorithms (LPAs) [ Zhu et al. , 2003; Zhang and Lee, 2007; Wang and…”
- Lifelong Graph Learning (2020, background): “limits its usage to large graphs and makes it inapplicable to lifelong learning either. It becomes more severe when the neighbor features are concatenated and propagated to the next layer iteratively [44], resulting in the effect of "neighbor explosion." As mentioned in Section 2, to scale”
- Just Jump: Dynamic Neighborhood Aggregation in Graph Neural Networks (2019, methodology): “GNNs follow a simple neighborhood aggregation procedure motivated by two major perspectives: The generalization of classical CNNs to irregular domains (Shuman et al., 2013), and their strong relations to the Weisfeiler & Lehman (1968) algorithm (Xu et al., 2019; Morris et al., 2019).”
- Simplifying Graph Convolutional Networks (2019, methodology): “Since GIN is not initially evaluated on citation networks, we implement GIN following Xu et al. (2019) and use hyperopt to tune weight decay and learning rate for 60 iterations.”
- A simple yet effective baseline for non-attribute graph classification (2018, background): “…Kernel (DGK)[YV15a], RetGK[ZWX + 18], FGSD[VZ17], Weisfeiler-Lehman optimal assignment kernel (WL-OA)[KGW16], and 5 graph neural networks: PATCHYSAN (PSCN) [NAK16], GRAPHSAGE[HYL17], DIFFPOOL[YYM + 18], Graph Isomorphism Network GIN[XHLJ18], Diffusion-convolutional neural networks (DCNN) [AT16].”
- Towards Sparse Hierarchical Graph Classifiers (2018, methodology): “Lastly, inspired by the JK-net architecture [27, 26], we perform this summarisation after each conv-pool block of the network, and aggregate all of the summaries together by taking their sum.”
- From Few to More: Large-scale Dynamic Multiagent Curriculum Learning (2019, methodology): “Inspired by Graph Neural Network (GNN) (Xu et al. 2019), to this end, we propose a novel network architecture named Dynamic Agent-number Network (DyAN) to address the above problems.”