The spatial convolution layer which is widely used in the Graph Neural Networks (GNNs) aggregates the feature vector of each node with the feature vectors of its neighboring nodes. The GNN is not aware of the locations of the nodes in the global structure of the graph and when the local structures corresponding to different nodes are similar to each other, the convolution layer maps all those nodes to similar or same feature vectors in the continuous feature space. Therefore, the GNN cannot distinguish two graphs if their difference is not in their local structures. In addition, when the nodes are not labeled/attributed the convolution layers can fail to distinguish even different local structures. In this paper, we propose an effective solution to address this problem of the GNNs. The proposed approach leverages a spatial representation of the graph which makes the neural network aware of the differences between the nodes and also their locations in the graph. The spatial representation which is equivalent to a point-cloud representation of the graph is obtained by a graph embedding method. Using the proposed approach, the local feature extractor of the GNN distinguishes similar local structures in different locations of the graph and the GNN infers the topological structure of the graph from the spatial distribution of the locally extracted feature vectors. Moreover, the spatial representation is utilized to simplify the graph down-sampling problem. A new graph pooling method is proposed and it is shown that the proposed pooling method achieves competitive or better results in comparison with the state-of-the-art methods.
============ After rebuttal ============
I thank the authors for carefully discussing the points of my review. I have upgraded the score to marginal acceptance (6).
============ Original review ============
In this paper, the authors identify a shortcoming of existing GNN architectures for graph classification tasks -- specifically, the fact that, in the featureless regime, the graph convolutional layers rely on propagating very rudimentary structural information, making it hard (or impossible) to distinguish graphs with similar local structure. To fix the problem, the authors propose to augment the input feature space with graph-structural embeddings (computed by an algorithm like DeepWalk), and processing those in parallel with any other input features available.
On existing real-world datasets, as well as synthetic datasets carefully constructed to illustrate this phenomenon, the proposed pipeline matches or exceeds the version without the structural embedding inputs. Further, the authors note that the structural embeddings could be used to propose a novel graph pooling method -- one which attempts to preserve as diverse structural feature sets as possible. It is shown that this method is competitive to other differentiable pooling methods, like DiffPool and Graph U-Nets. Lastly, the authors demonstrate that the addition of pooling layers does not help baseline GNNs on the synthetically constructed tasks, as the fundamental issue of handling similar local structures is still not addressed.
I believe that the paper clearly exposes and proposes a nice idea which could hold great potential, and which can be useful to graph representation learning practitioners. I am particularly happy with the design of the synthetic experiments. However, I find that, in its current form, the manuscript is narrowly below the bar for a venue like ICLR.
Comments:
* The observation that existing GNN layers may struggle with distinguishing featureless graphs is not particularly novel. It's largely the centerpiece of the (already cited) work of Xu et al. (ICLR 2019), and I believe that its relevance and relation to the authors' work should be better stressed in the related work section.
* The usage of DeepWalk to encode structural information (and even to be used as initial features for a GNN) is, ultimately, also not necessarily a novel idea. At least, it's something that should be clear to any expert GNN practitioner already: if useful features are missing from the graph, a method like DeepWalk (if applicable; see below!) could be a go-to method for obtaining such features. In its current form, I don't see that the authors are proposing anything substantially architecturally novel, and their contribution is primarily on the data/feature engineering side.
* The above point is not necessarily problematic, but if the aim is to stress the importance of the architectural novelties of the proposed GNN-ESR model more, and not just the added features, I would recommend the authors to perform a few ablations: e.g. seeing how well would processing a concatenation of E and F in the same GNN layer perform.
* Many of the standard graph classification datasets are known to be noisy and unreliable (see e.g. Luzhnica, Day and Liò (ICML GraphReasoning Workshop 2019). This means that it is a must to report error bars of the cross-validation experiments. It's hard to say that many of the improvements depicted here are statistically significant otherwise.
* I have concerns about the computational complexity, or even feasibility, of using DeepWalk-like methods in the general case, e.g. for node classification. Namely, if such layers are to be applied in inductive settings (with nodes gradually added to graphs), one would require re-running DeepWalk every time a new node is added. The authors should comment on this adequately, and perhaps discuss the feasibility of other unsupervised embedding techniques for obtaining the e-vectors -- such as VGAE (Kipf and Welling, NIPS BDL 2016), GraphSAGE (Hamilton et al., NIPS 2017), Graph2Gauss (Bojchevski and Günnemann, ICLR 2018) or DGI (Veličković et al., ICLR 2019).
* While I find the proposed pooling method interesting (and more grounded in the graph's structural features than other proposed works), I find that there are many potential limitations to be discussed. For example, the fact that we start from a random first index means that we cannot rely on the obtained pooling to always be the same -- could this cause undesirable variance at test time? Furthermore, the downsampling from A^3 is a sure-fire way to obtain dense graphs after the first pooling -- potentially severely limiting the applicability of the method for large graphs. In my opinion, the authors should appropriately comment on these and perform ablations against pooling with A and A^2 (as was done in Graph U-Nets). It should also be interesting to note that there exist other structurally-informed pooling methods; see e.g. the Clique pooling method from Luzhnica, Day and Liò (ICLR RLGM 2019).
Given all of the above, I recommend (marginal) rejection, but am open to improving my score if the authors appropriately address the aforementioned comments.
Some minor comments and thoughts:
* The paper has several typos and grammar issues, and a typo pass is highly encouraged to aid clarity;
* The "attention mechanism" of Equation (5--6) seems to be nonparametric? If so, it might be interesting to compare with a version that features learnable queries, e.g. using the Transformer-style attention.
* In Equation (3), should the first min actually be a max? As we're maximising the overall minimum distances between topological features.
* I'm not sure that the paper is anywhere clear on what's the exact GNN layer being used. Could this be clarified and made more explicit? It's critical to reproducibility.
* I find it curious that the authors needed to resort to using batch normalisation---I usually found it to either have no meaningful effect on the results on the graph classification benchmarks, or it made results worse. Can the authors comment on this decision?
* The idea to concatenate output of all convolutional layers is heavily resembling Jumping Knowledge networks (Xu et al., ICML 2018), and I believe they should be appropriately cited.