Graph  Neural Networks
52895589
How Powerful are Graph Neural Networks?
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.
ICLR
Keyulu Xu Weihua Hu Jure Leskovec Stefanie Jegelka
57375753
A Comprehensive Survey on Graph Neural Networks
Deep learning has revolutionized many machine learning tasks in recent years, ranging from image classification and video processing to speech recognition and natural language understanding. The data in these tasks are typically represented in the Euclidean space. However, there is an increasing number of applications, where data are generated from non Euclidean domains and are represented as graphs with complex relationships and interdependency between objects. The complexity of graph data has imposed significant challenges on the existing machine learning algorithms. Recently, many studies on extending deep learning approaches for graph data have emerged. In this article, we provide a comprehensive overview of graph neural networks (GNNs) in data mining and machine learning fields. We propose a new taxonomy to divide the state of the art GNNs into four categories, namely, recurrent GNNs, convolutional GNNs, graph autoencoders, and spatial temporal GNNs. We further discuss the applications of GNNs across various domains and summarize the open source codes, benchmark data sets, and model evaluation of GNNs. Finally, we propose potential research directions in this rapidly growing field.
IEEE Transactions on Neural Networks and Learning Systems
Zonghan Wu Shirui Pan Fengwen Chen Guodong Long Chengqi Zhang Philip S Yu
213085920
Strategies for Pre training Graph Neural Networks
Many applications of machine learning require a model to make accurate pre dictions on test examples that are distributionally different from training ones, while task specific labels are scarce during training. An effective approach to this challenge is to pre train a model on related tasks where data is abundant, and then fine tune it on a downstream task of interest. While pre training has been effective in many language and vision domains, it remains an open question how to effectively use pre training on graph datasets. In this paper, we develop a new strategy and self supervised methods for pre training Graph Neural Networks (GNNs) The key to the success of our strategy is to pre train an expressive GNN at the level of individual nodes as well as entire graphs so that the GNN can learn useful local and global representations simultaneously. We systematically study pre training on multiple graph classification datasets. We find that naive strategies, which pre train GNNs at the level of either entire graphs or individual nodes, give limited improvement and can even lead to negative transfer on many downstream tasks. In contrast, our strategy avoids negative transfer and improves generalization significantly across downstream tasks, leading up to 9.4% absolute improvements in ROC AUC over non pre trained models and achieving state of the art performance for molecular property prediction and protein function prediction.
ICLR
Weihua Hu Bowen Liu Joseph Gomes Marinka Zitnik Percy Liang Vijay S Pande Jure Leskovec
56517517
Graph Neural Networks: A Review of Methods and Applications
Lots of learning tasks require dealing with graph data which contains rich relation information among elements. Modeling physics system, learning molecular fingerprints, predicting protein interface, and classifying diseases require a model to learn from graph inputs. In other domains such as learning from non structural data like texts and images, reasoning on extracted structures, like the dependency tree of sentences and the scene graph of images, is an important research topic which also needs graph reasoning models. Graph neural networks (GNNs) are connectionist models that capture the dependence of graphs via message passing between the nodes of graphs. Unlike standard neural networks, graph neural networks retain a state that can represent information from its neighborhood with arbitrary depth. Although the primitive GNNs have been found difficult to train for a fixed point, recent advances in network architectures, optimization techniques, and parallel computation have enabled successful learning with them. In recent years, systems based on variants of graph neural networks such as graph convolutional network (GCN) graph attention network (GAT) gated graph neural network (GGNN) have demonstrated ground breaking performance on many tasks mentioned above. In this survey, we provide a detailed review over existing graph neural network models, systematically categorize the applications, and propose four open problems for future research.
AI Open
Jie Zhou Ganqu Cui Zhengyan Zhang Cheng Yang Zhiyuan Liu Maosong Sun
53219431
Session based Recommendation with Graph Neural Networks
The problem of session based recommendation aims to predict user actions based on anonymous sessions. Previous methods model a session as a sequence and estimate user representations besides item representations to make recommendations. Though achieved promising results, they are insufficient to obtain accurate user vectors in sessions and neglect complex transitions of items. To obtain accurate item embedding and take complex transitions of items into account, we propose a novel method, i.e. Session based Recommendation with Graph Neural Networks, SR GNN for brevity. In the proposed method, session sequences are modeled as graphstructured data. Based on the session graph, GNN can capture complex transitions of items, which are difficult to be revealed by previous conventional sequential methods. Each session is then represented as the composition of the global preference and the current interest of that session using an attention network. Extensive experiments conducted on two real datasets show that SR GNN evidently outperforms the state of the art session based recommendation methods consistently.
AAAI
Shu Wu Yuyuan Tang Yanqiao Zhu Liang Wang Xing Xie Tieniu Tan
211677851
Benchmarking Graph Neural Networks
Graph neural networks (GNNs) have become the standard toolkit for analyzing and learning from data on graphs. As the field grows, it becomes critical to identify key architectures and validate new ideas that generalize to larger, more complex datasets. Unfortunately, it has been increasingly difficult to gauge the effectiveness of new models in the absence of a standardized benchmark with consistent experimental settings. In this paper, we introduce a reproducible GNN benchmarking framework, with the facility for researchers to add new models conveniently for arbitrary datasets. We demonstrate the usefulness of our framework by presenting a principled investigation into the recent Weisfeiler Lehman GNNs (WL GNNs) compared to message passing based graph convolutional networks (GCNs) for a variety of graph tasks, i.e. graph regression/classification and node/link prediction, with medium scale datasets.
ArXiv
Vijay Prakash Dwivedi Chaitanya K Joshi Thomas Laurent Yoshua Bengio Xavier Bresson
208291327
SuperGlue: Learning Feature Matching With Graph Neural Networks
This paper introduces SuperGlue, a neural network that matches two sets of local features by jointly finding correspondences and rejecting non matchable points. Assignments are estimated by solving a differentiable optimal transport problem, whose costs are predicted by a graph neural network. We introduce a flexible context aggregation mechanism based on attention, enabling SuperGlue to reason about the underlying 3D scene and feature assignments jointly. Compared to traditional, hand designed heuristics, our technique learns priors over geometric transformations and regularities of the 3D world through end to end training from image pairs. SuperGlue outperforms other learned approaches and achieves state of the art results on the task of pose estimation in challenging real world indoor and outdoor environments. The proposed method performs matching in real time on a modern GPU and can be readily integrated into modern SfM or SLAM systems. The code and trained weights are publicly available at github.com/magicleap/SuperGluePretrainedNetwork.
2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)
Paul-Edouard Sarlin Daniel DeTone Tomasz Malisiewicz Andrew Rabinovich
67855539
Predict then Propagate: Graph Neural Networks meet Personalized PageRank
Neural message passing algorithms for semi supervised classification on graphs have recently achieved great success. However, for classifying a node these methods only consider nodes that are a few propagation steps away and the size of this utilized neighborhood is hard to extend. In this paper, we use the relationship between graph convolutional networks (GCN) and PageRank to derive an improved propagation scheme based on personalized PageRank. We utilize this propagation procedure to construct a simple model, personalized propagation of neural predictions (PPNP) and its fast approximation, APPNP. Our model's training time is on par or faster and its number of parameters on par or lower than previous models. It leverages a large, adjustable neighborhood for classification and can be easily combined with any neural network. We show that this model outperforms several recently proposed methods for semi supervised classification in the most thorough study done so far for GCN like models. Our implementation is available online.
ICLR
Johannes Klicpera Aleksandar Bojchevski Stephan Gunnemann
202539008
Measuring and Relieving the Over smoothing Problem for Graph Neural Networks from the Topological View
Graph Neural Networks (GNNs) have achieved promising performance on a wide range of graph based tasks. Despite their success, one severe limitation of GNNs is the over smoothing issue (indistinguishable representations of nodes in different classes) In this work, we present a systematic and quantitative study on the over smoothing issue of GNNs. First, we introduce two quantitative metrics, MAD and MADGap, to measure the smoothness and over smoothness of the graph nodes representations, respectively. Then, we verify that smoothing is the nature of GNNs and the critical factor leading to over smoothness is the low information to noise ratio of the message received by the nodes, which is partially determined by the graph topology. Finally, we propose two methods to alleviate the over smoothing issue from the topological view: (1) MADReg which adds a MADGap based regularizer to the training objective;(2) AdaGraph which optimizes the graph topology based on the model predictions. Extensive experiments on 7 widely used graph datasets with 10 typical GNN models show that the two proposed methods are effective for relieving the over smoothing issue, thus improving the performance of various GNN models.
AAAI
Deli Chen Yankai Lin Wei Li Peng Li Jie Zhou Xu Sun
52919090
Weisfeiler and Leman Go Neural: Higher order Graph Neural Networks
In recent years, graph neural networks (GNNs) have emerged as a powerful neural architecture to learn vector representations of nodes and graphs in a supervised, end to end fashion. Up to now, GNNs have only been evaluated empirically showing promising results. The following work investigates GNNs from a theoretical point of view and relates them to the 1 dimensional Weisfeiler Leman graph isomorphism heuristic (1 WL) We show that GNNs have the same expressiveness as the 1 WL in terms of distinguishing non isomorphic (sub )graphs. Hence, both algorithms also have the same shortcomings. Based on this, we propose a generalization of GNNs, so called k dimensional GNNs (k GNNs) which can take higher order graph structures at multiple scales into account. These higher order structures play an essential role in the characterization of social networks and molecule graphs. Our experimental evaluation confirms our theoretical findings as well as confirms that higher order information is useful in the task of graph classification and regression.
AAAI
Christopher Morris Martin Ritzert Matthias Fey William L Hamilton Jan Eric Lenssen Gaurav Rattan Martin Grohe