HOW POWERFUL ARE GRAPH NEURAL NETWORKS?
HOW POWERFUL ARE GRAPH NEURAL NETWORKS?
ABSTRACT
Graph Neural Networks are an effective framework for representation learning of graphs. Graph Neural Networks 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 Graph Neural Network variants have been proposed and have achieved state-of-the-art results on both node and graph classification tasks. However, despite Graph Neural Networks 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 Graph Neural Networks to capture different graph structures. Our results characterize the discriminative power of popular Graph Neural Network 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 Graph Neural Networks 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.
One INTRODUCTION
One INTRODUCTION
Learning with graph structured data, such as molecules, social, biological, and financial networks, requires effective representation of their graph structure. Recently, there has been a surge of interest in Graph Neural Network approaches for representation learning of graphs. Graph Neural Networks broadly follow a recursive neighborhood aggregation (or message passing) scheme, where each node aggregates feature vectors of its neighbors to compute its new feature vector. After k iterations of aggregation, a node is represented by its transformed feature vector, which captures the structural information within the node's k-hop neighborhood. The representation of an entire graph can then be obtained through pooling, for example, by summing the representation vectors of all nodes in the graph.
Many Graph Neural Network variants with different neighborhood aggregation and graph-level pooling schemes have been proposed. Empirically, these Graph Neural Networks have achieved state-of-the-art performance in many tasks such as node classification, link prediction, and graph classification. However, the design of new Graph Neural Networks is mostly based on empirical intuition, heuristics, and experimental trial-and-error. There is little theoretical understanding of the properties and limitations of Graph Neural Networks, and formal analysis of Graph Neural Networks' representational capacity is limited.
Here, we present a theoretical framework for analyzing the representational power of Graph Neural Networks. We formally characterize how expressive different Graph Neural Network variants are in learning to represent and distinguish between different graph structures. Our framework is inspired by the close connection between Graph Neural Networks and the Weisfeiler-Lehman graph isomorphism test, a powerful test known to distinguish a broad class of graphs. Similar to Graph Neural Networks, the Weisfeiler-Lehman test iteratively updates a given node's feature vector by aggregating feature vectors of its network neighbors. What makes the Weisfeiler-Lehman test so powerful is its injective aggregation update that maps different node neighborhoods to different feature vectors. Our key insight is that a Graph Neural Network can have as large discriminative power as the Weisfeiler-Lehman test if the Graph Neural Network's aggregation scheme is highly expressive and can model injective functions.
To mathematically formalize the above insight, our framework first represents the set of feature vectors of a given node's neighbors as a multiset, i.e., a set with possibly repeating elements. Then, the neighbor aggregation in Graph Neural Networks can be thought of as an aggregation function over the multiset. Hence, to have strong representational power, a Graph Neural Network must be able to aggregate different multisets into different representations. We rigorously study several variants of multiset functions and theoretically characterize their discriminative power, i.e., how well different aggregation functions can distinguish different multisets. The more discriminative the multiset function is, the more powerful the representational power of the underlying Graph Neural Network.
Our main results are summarized as follows:
One) We show that Graph Neural Networks are at most as powerful as the Weisfeiler-Lehman test in distinguishing graph structures.
Two) We establish conditions on the neighbor aggregation and graph readout functions under which the resulting Graph Neural Network is as powerful as the Weisfeiler-Lehman test.
Three) We identify graph structures that cannot be distinguished by popular Graph Neural Network variants, such as Graph Convolutional Networks and GraphSAGE, and we precisely characterize the kinds of graph structures such Graph Neural Network-based models can capture.
Four) We develop a simple neural architecture, Graph Isomorphism Network, and show that its discriminative/representational power is equal to the power of the Weisfeiler-Lehman test.
We validate our theory via experiments on graph classification datasets, where the expressive power of Graph Neural Networks is crucial to capture graph structures. In particular, we compare the performance of Graph Neural Networks with various aggregation functions. Our results confirm that the most powerful Graph Neural Network by our theory, i.e., Graph Isomorphism Network, also empirically has high representational power as it almost perfectly fits the training data, whereas the less powerful Graph Neural Network variants often severely underfit the training data. In addition, the representationally more powerful Graph Neural Networks outperform the others by test set accuracy and achieve state-of-the-art performance on many graph classification benchmarks.