Venue: ICLR 2018 conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: The paper proposes a new method (Ego-CNN) to compute supervised embeddings of graphs based on the neighborhood structure of nodes. Using an approach similar to attention and deconvolution, the paper also aims to detect substructures in graphs that are important for a given supervised task.

Learning graph representations is an important task and fits well into ICLR. The paper pursues interesting ideas and shows promising experimental results. I've also found the focus of the paper on interpretability (by detecting important substructures) interesting and promising. However, in its current form, I am concerned about both the novelty and the clarity of the paper.

Regarding novelty: The general idea of Ego-CNN seems to be quite closely related to the model of Kipf and Welling [2]. Unfortunately, this connection is neither made clear in the discussion of related work, nor does the experimental evaluation include a comparison. In particular, the paper mentions that Ego-CNN is similar to the Weißfeiler-Lehman (WL) algorithm. However, the same is the case for [2] (see Appendix A in [2] for a discussion). It would therefore be important to discuss the benefits of Ego-CNN over [2] clearly, especially since [2] is arguably simpler and doesn't require a fixed-size neighborhood.

Regarding clarity: In general, the paper would greatly benefit from a clearer discussion of methods and results. For instance,
- The paper lacks a complete formal definition of the model.
- Detecting critical substructures is an explicit focus of the paper. However, Section 4.1 provides only a very short description of the proposed approach and lacks again any formal definition. Similarly, the experimental results in Section 5.3 require a deeper analysis of the detected substructures as the presented examples are mostly anecdotal. For instance, quantitative results on synthetic graphs (where the critical substructures are known) would improve this section.
- The discussion of scale-free regularization in Section 4.2 is very hand-wavy. It lacks again any formal proof that the proposed approach exploits scale-free structures or even a proper motivation why this regularization should improve results. Furthermore, the experimental results in Section 5.2 are only evaluated on a single dataset and it is difficult to say whether the improvement gains are due to some scale-free property of the model. For instance, the improvement could also just stem from the different architecture and/or decreased overfitting due to the decreased number of parameters from weight-tying.
 
Further comments:
- The discussion of related work is sometimes unclear. For instance, precisely why can't Neural Fingerprint detect critical structures? Similarly, how is the k-node neighborhood constraint of Patchy-San different than the one of Ego-CNN?
- In graph theory, the standard notion of neighborhood are all nodes adjacent to a given node, e.g., see [1]
- The writing could be improved, since I found some passages difficult to read due to typos and sentence structure.

[1] https://en.wikipedia.org/wiki/Neighbourhood_(graph_theory)
[2] Kipf et al. "Semi-supervised classification with graph convolutional", 2017.
review_title: Review

final_score: rating: 4: Ok but not good enough - rejection
review_content: Dear authors,

Thank you for your contribution to ICLR. The problem you are addressing with your work is important. Your paper is well-motivated. Detecting and exploiting "critical structures" in graphs for graph classification is indeed something that is missing in previous work. 

After the introduction you discuss some related work. While I really appreciate the effort you put into this section (including the figures etc.) there are several inaccuracies in the portrayal of existing methods. Especially the comparison to Patchy-san is somewhat vague. Please make sure that you clearly state the differences between patchy-san and Ego-CNNs. What exactly is it that Patchy cannot achieve that you can. I believe I understood what the advantages of the proposed method are but it took a while to get there. Just one example to show you what I mean; you write:

"The reason why the idea of Patchy-San fails to generalize into multiple layers is that its definition of
neighborhood, which is based on adjacency matrix, is not static and may not corresponding to local
regions in the graph. "

It is very difficult to understand what it is that you want to express with the above sentence. Its definition of neighborhood is based on adjacency matrix - what does that mean? A neighborhood is a set of nodes, no? Why is it that their definition of neighborhood might not correspond to local regions? In general, you should try to be more precise and concise when discussing related work. 

Section 3, the most important section in the paper that describes the proposed Ego-CNN approach, should also be written more clearly. For instance, it would be good if you could define the notion of an "Ego-Convolution layer." You use that term without properly defining it and it is difficult to make sense of the approach without understanding it. Also, you contrast your approach with patchy and write that "Our main idea is to use the egocentric design, i.e. the neighborhood at next
layer is defined on the same node." Unfortunately, I find it difficult to understand what this means. In general, this section is very verbose and needs a lot more work. This is at the moment also the crucial shortcoming of the paper. You should spent more time on section 3 and formally and more didactically introduce your approach. In my opinion, without a substantial improvement of this section, the paper should not be accepted. 

The experiments are standard and compare to numerous existing state of the art methods. The data sets are also rather standard. The one thing I would add to the results are the standard deviations. It is common to report those. Also, in the learning for graph structured data, the variance can be quite high and providing the stddev would at least indicate how significant the improvements are. 

I also like the visualizations and the discussion of the critical structures found in some of the graphs.

Overall, I think this is an interesting paper that has a lot of potential. The problem, however, is that the presentation of the proposed approach is verbose and partially incomprehensible. What exactly is different to existing approaches? What exactly is the formal definition of the method? All of this is not well presented and, in my opinion, requires another round of editing and reviews.


review_title: Interesting topic but poor/informal presentation 

final_score: rating: 7: Good paper, accept
review_content: The authors proposed a convolutional framework based on merging ego-networks. It combines graph embedding layers with task driven output layers, producing interpretable results for critical structure detection. While based on existing embedding methods such as Patchy-San, the contribution of ego-centric convolution and multi-layer architechture is novel and has a lot of potential in applications. The overall presentation of the draft is also of high quality. I recommend its publication at ICLR.

Here is a list of suggested changes to further improve the draft,

1. The two panels of Figure 1 seems redundant.

2. Figure 4 does not provide useful information, especially in terms of how overlapping neighborhoods are aggregated at deeper layers.

3. There seems to be a mistake in Figure 5 with the top neighborhood in white

4. The connection between weight-tying and scale-free structure needs better explanation. Are the authors trying to say that fractal processes generates power-law degree distributions?

5. The visualization of critical structures are very helpful. However, it might be better to look into structures in high level layers for truly global signatures. This is especially the case for the reddit dataset, where visualizations at the node and edge level creates hairballs.


review_title: A well desgined architechture for task driven graph embedding

Meta-review: This paper deals with the important topic of learning better graph representations and shows promise in helping to detect critical substructures of graph that would help with the interpretability of representations. Unfortunately, this work fails to accurately portray how it relates to previous work (in particular, Niepert et al, Kipf et al, Duvenaud et al) and falls short of providing clear and convincing explanations of what it can do that these models can't, without including all of them in experimental comparisons. 
Decision: Reject