Graph neural networks (GNNs) are a powerful tool to learn representations on graphs by iteratively aggregating features from node neighbourhoods. Many variant models have been proposed, but there is limited understanding on both how to compare different architectures and how to construct GNNs systematically. Here, we propose a hierarchy of GNNs based on their aggregation regions. We derive theoretical results about the discriminative power and feature representation capabilities of each class. Then, we show how this framework can be utilized to systematically construct arbitrarily powerful GNNs. As an example, we construct a simple architecture that exceeds the expressiveness of the Weisfeiler-Lehman graph isomorphism test. We empirically validate our theory on both synthetic and real-world benchmarks, and demonstrate our example's theoretical power translates to strong results on node classification, graph classification, and graph regression tasks.
The paper proposes minor modifications to Graph Convolutional Networks (GCNs) that as proven by the authors enable learning of local features in networks, namely the aggregation over powers of the adjacency matrix (effectively counting random walks within the neighborhood) and aggregating over connections within nodes in the neighborhood.
GCNs are of interest to 
The paper is well written and clear.
The mathemeatical derivations are clearly structured.
The authors provide a large set of experiments on simulated and real data from different domains and relevant supervised tasks (node classifiation, graph classification and graph regression).
Source code is provided.
experimental results:
- For the simulation in Table 2, a 1-layer network seems like it would hield an advantage for the unstructured Erdös Renyi graphs. As I understand, the proposed GCN should by construction count the triangles (target variable) for each node embedding and then predict a linear function of those aggregated. My intuition says that this may even be an advantage over adding more layers. The text states the opposite. Here it would be interesting to see the effect of adding layers, or aggregating over longer random walks.
Here, it would be important to get the prediction of an untrained baseline in addition to the GCN baseline (e.g. the expected number of triangles/4cycles based on number of nodes in the Erdös Renyi model) to understand the scale the Mean Squared Error lives on and what the relative improvement means.