How Powerful are Graph Neural Networks

Published on Oct 1, 2018 in ICLR (International Conference on Learning Representations)
Keyulu Xu12
Estimated H-index: 12
(MIT: Massachusetts Institute of Technology),
Weihua Hu19
Estimated H-index: 19
(Stanford University)
+ 1 AuthorsStefanie Jegelka38
Estimated H-index: 38
(MIT: Massachusetts Institute of Technology)
Sources
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.
馃摉 Papers frequently viewed together
2016CVPR: Computer Vision and Pattern Recognition
4 Authors (Kaiming He, ..., Jian Sun)
References0
Newest
Cited By1326
Newest
#1Hong Yang (USYD: University of Sydney)
#2Ling Chen (UTS: University of Technology, Sydney)H-Index: 26
Last. Peng Zhang (GU: Guangzhou University)H-Index: 53
view all 5 authors...
Abstract null null Attributed graphs refer to graphs where both node links and node attributes are observable for analysis. Attributed graph embedding enables joint representation learning of node links and node attributes. Different from classical graph embedding methods such as Deepwalk and node2vec that first project node links into low-dimensional vectors which are then linearly concatenated with node attribute vectors as node representation, attributed graph embedding fully explores data de...
Source
#1Vincenzo Ferrero (OSU: Oregon State University)H-Index: 3
#2Bryony DuPont (OSU: Oregon State University)H-Index: 9
Last. Daniele Grandi (Autodesk)H-Index: 1
view all 4 authors...
Source
#1Pushpak Pati (IBM)H-Index: 7
#2Guillaume Jaume (EPFL: 脡cole Polytechnique F茅d茅rale de Lausanne)H-Index: 7
Last. Daniel RiccioH-Index: 22
view all 17 authors...
Cancer diagnosis, prognosis, and therapy response predictions from tissue specimens highly depend on the phenotype and topological distribution of constituting histological entities. Thus, adequate tissue representations for encoding histological entities is imperative for computer aided cancer patient care. To this end, several approaches have leveraged cell-graphs, capturing the cell-microenvironment, to depict the tissue. These allow for utilizing graph theory and machine learning to map the ...
Source
#1Hakim Hafidi (ENST: T茅l茅com ParisTech)H-Index: 2
#2Mounir GhoghoH-Index: 33
Last. Ananthram Swami (ARL: United States Army Research Laboratory)H-Index: 67
view all 4 authors...
Abstract null null Contrastive learning has become a successful approach for learning powerful text and image representations in a self-supervised manner. Contrastive frameworks learn to distinguish between representations coming from augmentations of the same data point (positive pairs) and those of other (negative) examples. Recent studies aim at extending methods from contrastive learning to graph data. In this work, we propose a general framework for learning node representations in a self s...
Source
#1Hanjie Liu (SEU: Southeast University)
#2Jinren Zhang (SEU: Southeast University)
Last. Jinde Cao (SEU: Southeast University)H-Index: 136
view all 4 authors...
Abstract null null Emotion classification based on neurophysiology signals has being a challenging issue in the literature. Recent neuroscience findings suggest that brain network structure underlying the different emotions provide a window in understanding human affection. In this paper, we propose a novel method to capture the distinct minimum spanning tree (MST) topology underpinning the different emotions. Specifically, we propose a hierarchical aggregation-based graph neural network to inve...
Source
#1Ankith Mohan (SC: University of Southern California)H-Index: 2
#2Aiichiro Nakano (SC: University of Southern California)H-Index: 62
Last. Emilio Ferrara (SC: University of Southern California)H-Index: 57
view all 3 authors...
Abstract null null Given: (a) clean training dataset, (b) trained graph machine learning pipeline, and (c) noisy test dataset; how do we make the pipeline robust to such noise? In an attempt to answer this question, we propose a modification to the pipeline that exploits both the content addressability of a restricted Boltzmann machine and the message passing capabilities of a graph neural network. We investigate which of the hidden layers of the pipeline is best suited for our proposed modifica...
Source
#1Liang Yang (CASHIPS: Hefei Institutes of Physical Science)H-Index: 39
Last. Yuanfang Guo (Beihang University)H-Index: 11
view all 7 authors...
#1Qi Wang (Fudan University)H-Index: 2
#2Chunlei Tang (Brigham and Women's Hospital)
Abstract null null Traveling salesman and vehicle routing problems with their variants, as classic combinatorial optimization problems, have attracted considerable attention for decades of their theoretical and practical value. Many classic algorithms have been proposed, for example, exact algorithms, heuristic algorithms, solution solvers, etc. Still, due to their complexity, even the most advanced traditional methods require too much computational time or are not well-defined mathematically; a...
Source
#1Xuan Yu (SHU: Shanghai University)H-Index: 3
#2Suixiang Shi (SHU: Shanghai University)H-Index: 3
Last. Lingyu Xu (SHU: Shanghai University)H-Index: 6
view all 3 authors...
Abstract null null Air temperature prediction is a significant task for researchers and forecasters in the field of meteorology. In this paper, we present an innovative, deep spatial鈥搕emporal learning air temperature forecasting framework based on graph attention network and gated recurrent unit. Particularly, historical observations containing multiple environmental variables at different stations are constructed as graph signals. The original stations鈥 conditions and the learned attention info...
Source
#1Yuanyuan Shen (Hunan University)
#2Manman Peng (Hunan University)
Last. Qiang Wu (Hunan University)
view all 4 authors...
Abstract null null Development of the parallel processing technology is necessary to solve problems created by programs with complex structures that are computation- and data-intensive. In the parallelization process, the detection of parallelism is an important task. Automatic parallelism analysis tools help programmers in finding parallelism. However, these tools have limitations in analyzing complex programs. Herein, we propose a data-driven method that can be applied to parallelism detection...
Source
This website uses cookies.
We use cookies to improve your online experience. By continuing to use our website we assume you agree to the placement of these cookies.
To learn more, you can find in our Privacy Policy.