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 WeisfeilerLehman 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.
This papers presents an interesting take on Weisfeiler-Lehman-type GNNs, where it shows that a WL-GNNs classification power is related to its ability to represent multisets. The authors show a few exemplar networks where the mean and the max aggregators are unable to distinguish different multisets, thus losing classification power. The paper also proposes averaging the node representation with its neighbors (foregoing the “concatenate” function) and using sum pooling rather than mean pooling as aggregator. All these observations are wrapped up in a GNN, called GIN. The experiments on Table 1 are inconclusive, unfortunately, as the average accuracies of the different methods are often close and there are no confidence intervals and statistical tests to help guide the reader to understand the significance of the results.
My chief concern is equating the Weisfeiler-Lehman test (WL-test) with Weisfeiler-Lehman-type GNNs (WL-GNNs). The WL-test relies on countable set inputs and injective hash functions. Here, the paper is oversimplifying the WL-GNN problem. After the first layer, a WL-GNN is operating on uncountable sets. On uncountable sets, saying that a function is injective does not tells us much about it; we need a measure of how closely packed we find the points in the function’s image (a measure in measure theory, a density in probability). On countable sets, saying a function is injective tells us much about the function. Moreover, the WL-test hash function does not even need to operate over sets with total or even partial orders. As a neural network, the WL-GNN “hash” ($f$ in the paper) must operate over a totally ordered set (\mathbb{R}^n, n > 0). Porting the WL-test argument of “convergence to unique isomorphic fingerprints” to a WL-GNN requires a measure-theoretic analysis of the output of the WL-GNN layers, and careful analysis if the total order of the set does not create attractors when they are applied recursively. 
To illustrate the above *attractor* point, let’s consider the construct of Theorem 1 of (Xu et al., 2018), where the WL-GNN “hash” ($f$) is (roughly) described as the transition probability matrix of a random walk on the input graph. Under well-known conditions, the successive application of this operator ("hash" or transition probability matrix P in this case) can go towards an attractor (the steady state). Here, we need a measure-theoretic analysis of the “hash” even if it is bijective: random walk mixing. The random walk transition operator can be invertible (bijective), but we still say the random walker will mix, i.e., the walker forgets where it started, even if the transition operation can be perfectly undone by inversion (P^{-1}). In a WL-GNN that only uses the last layer for classification, this would manifest itself as poor performance in a WL-GNN with a large number of layers, and vanishing gradients. Of course, since (Xu et al., 2018) argued to revert back to the framework of (Duvenaud et al., 2015) of using the embeddings of all layers, one can argue that this mixing problem is just a problem of “wasted computation”.
The matrix analysis of the last paragraph also points to another potential problem with the sum aggregator. GIN needs to be shallow. With ReLU activations the reason is simple: for an adjacency matrix $A$, the value of $A^j$ grows very quickly with $j$ (diverges). With sigmoid activations, GIN would experience vanishing gradients in graphs with high variance in node degrees.
The paper should be careful with oversimplifications. Simplifications are useful for insight but can be dangerous if not prefaced by clear warnings and a good understanding of their limitations. I am not asking for a measure-theoretic analysis revision of the paper (it could be left to a follow-up paper). I am asking for a *relatively long* discussion of the limitations of the analysis.
Suggestions to strengthen the paper:
•	Please address the above concerns.
•	Table 1 should have confidence intervals (a statistical analysis of significance would be a welcome bonus).
•	Please mention the classes of graphs where the WL-test cannot distinguish two non-isomorphic graphs. See (Douglas, 2011), (Cai et al., 1992) and (Evdokimov and Ponomarenko, 1999) for the examples. It is important for the WL-GNN literature to keep track of the more fundamental limitations of the method.
•	(Hamilton et al, 2017) also uses the LSTM aggregator, besides max aggregator and mean aggregator, which outperforms both max and mean in some tasks. Does the LSTM aggregator also outperforms the sum aggregator in the tasks of Table 1? It is important for the community to know if unusual aggregators (such as the asymmetric LSTM) have some yet-to-be-discovered class-distinguishing power.
--------- Update -------
The counter-example in 
https://openreview.net/forum?id=ryGs6iA5Km&noteId=rkl2Q1Qi6X
is indeed a problem for Theorem 3 if  \{h_v^{(k-1)}, h_u^{(k-1)} : u \in \mathcal{N}_v\} is not a typo for a set of tuples \{(h_v^{(k-1)}, h_u^{(k-1)}) : u \in \mathcal{N}_v\}. Unfortunately, in their proof, the submission states "difficulty in proving this form of aggregation mainly lies in the fact that it does not immediately distinguish the root or central node from its neighbors", which means \{h_v^{(k-1)}, h_u^{(k-1)} : u \in \mathcal{N}_v\} is actually \{h_v^{(k-1)}\} \cup \{ h_u^{(k-1)} : u \in \mathcal{N}_v\}, which is not as powerful as WL. Concatenating is more powerful than the summing the node's own embedding, but it results in a  simpler model and could be easier to learn in practice. And I am still concerned about the countable x uncountable domain/image issue I raised in my review.
Still, the reviewers seem to be doing all the discussion among themselves, with no input from the authors. I am now following Reviewer 2.
----
Reverting my score to my original score. The authors have addressed most of my concerns, thank you. The restricted theorems and propositions better describe the contribution.
I would like to note that while the proof of (Xu et al., 2018) is limited that does not mean it is not applicable to GIN or GraphSAGE or similar models. The paper uses 5 GNN layers, which in my experience is the maximum I could ever use with GNNs without seeing a degradation in performance. I don't think this should be a topic for this paper, though.
Xu, K., Li, C., Tian, Y., Sonobe, T., Kawarabayashi, K., & Jegelka, S. (2018). Representation Learning on Graphs with Jumping Knowledge Networks. In ICML.
Cai, J. Y., Fürer, M., & Immerman, N. (1992). An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4), 389-410.
Douglas, B. L. (2011). The Weisfeiler-Lehman method and graph isomorphism testing. arXiv preprint arXiv:1101.5211.
Evdokimov, S., & Ponomarenko, I. (1999). Isomorphism of coloured graphs with slowly increasing multiplicity of Jordan blocks. Combinatorica, 19(3), 321-333.