Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: ============ 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.
review_title: Official Blind Review #4

final_score: rating: 6: Weak Accept
review_content: In this work the authors point out an issue related to graph neural networks. Specifically, if two nodes, that may be far apart in the graph, may be represented as (almost) the same vector. This is simply because when no features/labels are associated with nodes, and the local structure around those two nodes is very similar then the local aggregation of information will result in a similar representation.  Therefore the authors introduce an embedding first of the graph in the Euclidean space using DeepWalk and then use this embedding in combination with the design of a CNN. The authors propose a pooling method that outperforms several state-of-the-art pooling techniques on real data. Overall, the empirical results are supportive of the fact that the proposed method can help improve the performance of GNNs. 

Overall I found the results of this paper to be weak, but nonetheless the paper is well-written and contains some interesting ideas. Hence my rating. Some questions follow. 

- While the authors call this as an "issue" it is more like a feature of these methods.  For instance, in "RolX: Structural Role Extraction & Mining in Large Graphs" by Henderson et al. this "issue" could turn out to be an interesting feature of the GNNs in the sense that these nodes may have a similar (structural) role.  It would be nice to have a short discussion related to this line of research in social networks' analysis. 
-  Some components of the CNN (e.g., node sampling) could be done using  well-developed tools for sampling matrices from numerical linear algebra, or by introducing some randomness when sampling a node as in kmeans++. 
- Graph downsampling appears to be an expensive operation. Can you please comment on the running times? The issue of scalability is not discussed, and the reader cannot easily infer to what sizes this method can scale up to. 
- Using other graph tasks, that are classical but also more challenging (e.g., learning 2-connected components of a graph just to mention something that comes up) would be interesting to see in Section 5.2.
-  It would have been interesting to see the effect of the embedding step on the accuracy on the real data. E.g., using node2vec or standard spectral embeddings. 


[Edit: The authors have replied to my comments, and the other reviewers' comments in great detail. Therefore I upgrade my score.] 
review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: The authors propose in this paper to complement the node attributes in a graph with vectors obtained using a graph embedding algorithm. More precisely, they propose a graph neural network that apply several layers of graph convolution in parallel to the node attributes and to the embedding, then takes an average of the result, which is fed to another series of graph convolution. This is combined with some form of sampling which strongly resembles median based quantization but is solved with some basic heuristics and without acknowledging the resemblance (I might be missing something). 

Globally, I find this paper very unclear. The authors are mixing references to graph convolution for fixed graph structure with references about general graph neural networks. Their goal is not clearly stated from the beginning and in many places the discussion lacks of focus and is difficult to follow. In the experimental evaluation several values are very close one to another and the statistical significativity of the differences is not assessed. 
review_title: Official Blind Review #1

Meta-review: The authors identify a limitation of aggregating GNNs, which is that global structure can be mostly lost. They propose a method which combines a graph embedding with the spatial convolution GNN and show that the resulting GNN can better distinguish between similar local structures. 

The reviewers were mixed in their scores. The proposed approach is clearly motivated and justified and may be relelvant for some graphnet researchers, but the approach is only applicable in some circumstances - in other cases it may be desirable to ignore global structure. This, plus the high computational complexity of the proposed approach, mean that the significance is weaker. Overall the reviewers felt that the contribution was not significant enough and that the results were not statistically convincing.  Decision is to reject.
Decision: Reject