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. Learning with graph structured data, such as molecules, social, biological, and financial networks, requires effective representation of their graph structure BID14 . Recently, there has been a surge of interest in Graph Neural Network (GNN) approaches for representation learning of graphs BID23 BID13 BID21 BID34 BID37 . GNNs 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 BID37 BID12 . 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 BID39 , for example, by summing the representation vectors of all nodes in the graph.Many GNN variants with different neighborhood aggregation and graph-level pooling schemes have been proposed BID31 BID3 BID6 BID8 BID13 BID19 BID21 BID23 BID34 BID28 BID37 BID29 BID35 BID39 . Empirically, these GNNs have achieved state-of-the-art performance in many tasks such as node classification, link prediction, and graph classification. However, the design of new GNNs is mostly based on empirical intuition, heuristics, and experimental trial-anderror. There is little theoretical understanding of the properties and limitations of GNNs, and formal analysis of GNNs' representational capacity is limited.Here, we present a theoretical framework for analyzing the representational power of GNNs. We formally characterize how expressive different GNN variants are in learning to represent and distinguish between different graph structures. Our framework is inspired by the close connection between GNNs and the Weisfeiler-Lehman (WL) graph isomorphism test BID36 , a powerful test known to distinguish a broad class of graphs BID2 . Similar to GNNs, the WL test iteratively updates a given node's feature vector by aggregating feature vectors of its network neighbors. What makes the WL test so powerful is its injective aggregation update that maps different node neighborhoods to different feature vectors. Our key insight is that a GNN can have as large discriminative power as the WL test if the GNN'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 GNNs can be thought of as an aggregation function over the multiset. Hence, to have strong representational power, a GNN 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 GNN.Our main results are summarized as follows: 1) We show that GNNs are at most as powerful as the WL test in distinguishing graph structures.2) We establish conditions on the neighbor aggregation and graph readout functions under which the resulting GNN is as powerful as the WL test.3) We identify graph structures that cannot be distinguished by popular GNN variants, such as GCN BID21 and GraphSAGE (Hamilton et al., 2017a) , and we precisely characterize the kinds of graph structures such GNN-based models can capture. In this paper, we developed theoretical foundations for reasoning about the expressive power of GNNs, and proved tight bounds on the representational capacity of popular GNN variants. We also designed a provably maximally powerful GNN under the neighborhood aggregation framework. An interesting direction for future work is to go beyond neighborhood aggregation (or message passing) in order to pursue possibly even more powerful architectures for learning with graphs. To complete the picture, it would also be interesting to understand and improve the generalization properties of GNNs as well as better understand their optimization landscape.A PROOF FOR LEMMA 2Proof. Suppose after k iterations, a graph neural network A has A(G 1 ) = A(G 2 ) but the WL test cannot decide G 1 and G 2 are non-isomorphic. It follows that from iteration 0 to k in the WL test, G 1 and G 2 always have the same collection of node labels. In particular, because G 1 and G 2 have the same WL node labels for iteration i and i + 1 for any i = 0, ..., k − 1, G 1 and G 2 have the same collection, i.e. multiset, of WL node labels l DISPLAYFORM0 as well as the same collection of node neighborhoods l DISPLAYFORM1 . Otherwise, the WL test would have obtained different collections of node labels at iteration i + 1 for G 1 and G 2 as different multisets get unique new labels.The WL test always relabels different multisets of neighboring nodes into different new labels. We show that on the same graph G = G 1 or G 2 , if WL node labels l DISPLAYFORM2 u for any iteration i. This apparently holds for i = 0 because WL and GNN starts with the same node features. Suppose this holds for iteration j, if for any u, v, l DISPLAYFORM3 , then it must be the case that DISPLAYFORM4 By our assumption on iteration j, we must have DISPLAYFORM5 In the aggregation process of the GNN, the same AGGREGATE and COMBINE are applied. The same input, i.e. neighborhood features, generates the same output. Thus, h DISPLAYFORM6 . By induction, if WL node labels l DISPLAYFORM7 u , we always have GNN node features h DISPLAYFORM8 u for any iteration i. This creates a valid mapping φ such that h DISPLAYFORM9 v ) for any v ∈ G. It follows from G 1 and G 2 have the same multiset of WL neighborhood labels that G 1 and G 2 also have the same collection of GNN neighborhood features DISPLAYFORM10 are the same. In particular, we have the same collection of GNN node features DISPLAYFORM11 for G 1 and G 2 . Because the graph level readout function is permutation invariant with respect to the collection of node features, A(G 1 ) = A(G 2 ). Hence we have reached a contradiction.
We develop theoretical foundations for the expressive power of GNNs and design a provably most powerful GNN.
{"src": "scitldr-AIC_train", "paper_id": "ryGs6iA5Km"}