Most of the existing Graph Neural Networks (GNNs) are the mere extension of the Convolutional Neural Networks (CNNs) to graphs. Generally, they consist of several steps of message passing between the nodes followed by a global indiscriminate feature pooling function. In many data-sets, however, the nodes are unlabeled or their labels provide no information about the similarity between the nodes and the locations of the nodes in the graph. Accordingly, message passing may not propagate helpful information throughout the graph. We show that this conventional approach can fail to learn to perform even simple graph classification tasks. We alleviate this serious shortcoming of the GNNs by making them a two step method. In the first of the proposed approach, a graph embedding algorithm is utilized to obtain a continuous feature vector for each node of the graph. The embedding algorithm represents the graph as a point-cloud in the embedding space. In the second step, the GNN is applied to the point-cloud representation of the graph provided by the embedding method. The GNN learns to perform the given task by inferring the topological structure of the graph encoded in the spatial distribution of the embedded vectors. In addition, we extend the proposed approach to the graph clustering problem and an architecture for graph clustering is presented. Moreover, the spatial representation of the graph is utilized to design a new graph pooling algorithm. We turn the problem of graph down-sampling into a column sampling problem, i.e., the sampling algorithm selects a subset of the nodes whose feature vectors preserve the spatial distribution of all the feature vectors. We apply the proposed approach to several popular benchmark data-sets and it is shown that the proposed geometrical approach strongly improves the state-of-the-art result for several data-sets. For instance, for the PTC data-set, the state-of-the-art result is improved for more than 22 %.
The authors argue that graph neural networks based on the message passing frameworks are not able to infer the topological structure of graphs. Therefore, they propose to use the node embedding features from DeepWalk as (additional) input for the graph convolution. Moreover, a graph pooling operator is proposed, which clusters node pairs in a greedy fashion based on the l2-distances between feature vectors. The proposed methods are evaluated on seven common benchmark datasets and achieve better or comparable results to existing methods. Moreover, the method is evaluated using synthetic toy examples, showing that the proposed extensions help to infer topological structures.
A main point of criticism is that the authors claim that graph convolution is not able to infer the topological structure of a graph when no labels are present. In fact the graph convolution operator is closely related to the Weisfeiler-Lehman heuristic for graph isomorphism testing and can distinguish most graphs in many practical application. Therefore, it is not clear why DeepWalk features would increase the expressive power of graph convolution. It should be stated clearly which structural properties can be distinguished using DeepWalk features, but no with mere graph convolution.
The example on page 4 provides only a weak motivation for the approach: The nodes v_1 and v_2 should be indistinguishable since they are generated using the same generator. Thus, the problem is the mean/max pooling, and not the graph convolution. When using the sum-aggregation and global add pooling, graphs with two clusters and graphs with three clusters are distinguishable again. Further insights how DeepWalk helps to learn more "meaningful" topological features are required to justify its use.
Clustering nodes that are close in feature space for pooling is a reasonable idea. However, this contradicts the intuition of clustering neighboring nodes in the graph. A short discussion of this phenomenon would strengthen the paper in my opinion.
There are several other questions that not been answered adequately in the article.
* The 10-fold cross validation is usually performed using an additional validation set. What kind of stopping criteria has bee use? * It would be helpful to provide standard deviations on these small datasets (although a lot of papers sadly dismiss them).
* I really like the use of synthetic data to show superior expressive power, but I am unsure whether this can be contributed to DeepWalk or the use of the proposed pooling operator (or both). Please divide the results for these toy experiments in "GEO-DEEP" and "GEO-deep no pooling". As far as I understand, node features in different clusters should be indistinguishable from each other (even when using DeepWalk), so I contribute this success to the proposed pooling operator.
* A visualization of the graphs obtained by the proposed pooling operator would be helpful. How do the coarsened graphs look like? Given that any nodes can end up in the same cluster, and the neighborhood is defined to be the union of the neighboring nodes of the node pairs, I guess coarsened graphs are quite dense.
* DiffPool (NIPS 2018, Ying et al.) learns assignment matrices based on a simple GCN model (and thus infers topological structure from message passing). How is the proposed pooling approach related to DiffPool (except that its non-differentiable)? How does it perform when using only the features generated by a GCN? How does it compare to other pooling approaches commonly used, e.g., Graclus? At the moment, it is quite hard to judge the benefits of the proposed pooling operator in comparison to others.
In summary, the paper presents promising experimental results, but lacks a theoretical justification or convincing intuition for the proposed approach. Therefore, at this point I cannot recommend its acceptance.
Minor remarks:
* p2: The definition of "neighbour set" is needless in its current form.
* p2: The discussion of graph kernels neglects the fact that many graph kernels compute feature vectors that can be used with linear SVMs.
-----------
Update:
The comment of the authors clarified some misunderstandings. I now agree that the combination of DeepWalk features and GNNs can encode more/different topological information. I still think that the paper does not make this very clear and does not provide convincing examples. I have update my score accordingly.