Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: GEOM-GCN: GEOMETRIC GRAPH CONVOLUTIONAL NETWORKS 

The paper introduces a novel GCN framework, whose purpose is to overcome weaknesses of existing GCN approaches, namely loss of structural neighbor information and failure to capture important dependencies between distant nodes. The paper uses a mapping from nodes to an embedded space and introduces a second type of a neighborhood: a proximity in the embedded space. In the embedded space, a set of relations of nodes is defined. For each node v, the paper uses a 2-stage convolution scheme: 1) for each neighborhood type, the nodes in the same relation with v are combined; 2) the resulting nodes are again combined into a new feature vector. This approach allows one to overcome the issues described above. The experiments show that in most cases the approach outperforms the existing GCN solutions, sometimes with a large gap.

I have the following concerns about the paper:
-- My main concern is the learning time, which is an issue for a straightforward GCN implementation. There were multiple attempts to decrease it (GraphSAGE, FastGCN, etc.). Therefore, I would like to see running times on the presented graphs as well as on relatively large graphs (see e.g. https://arxiv.org/pdf/1902.07153.pdf for candidates). If some techniques were used to make the implementation faster, I would be good to include them in the paper (or, if they are standard, they should be referenced). At the very least, I believe it should be prioritized as a future direction.
-- It’s unclear why we should use the same latent space and the same τ for both N_g and N_s. I would expect that mapping into different spaces could provide better results: the two neighborhood types seem very different, and I don’t see why the neighbors should be aggregated in the same way. If using different spaces doesn’t provide an improvement, an explanation for this would be very useful.
-- α and β are defined and shown in Table 2, but they are never used (as it stands now, α and β can simply be removed). If the results in Table 3 correlate with them, then this dependence should be highlighted. In such case, it would also be better to move α and β to Table 3.
-- The paper uses 3 different node embedding strategies. These strategies can be combined in q with different weights (which can be learned as hyperparameters). Will it produce the best of 3 (or better) result?
-- “We use an embedding space of dimension 2 for ease of explanation” But what τ is used in the real implementation?
-- There are various GCN implementations; however, the comparison is performed with only 2 of them. I would like to see either comparison with more implementations, or the explanation why the comparison with the given two suffices.
-- Is it possible to make the implementation available?

While there are a lot of possible improvements, I believe that some of them can be addressed in a future research, and the paper’s novel approach is noteworthy in itself. My current verdict is 5/10, and I’ll be happy to improve it if the above issues are fixed.

Presentation issues:
-- The notation used in definition of m_v^l is unclear.
-- Why τ is a part of each node’s structural neighborhood? It’s a global function, isn’t it?
-- Introduction: I believe that the exact problems which GCNs solve (e.g. node classification) should be mentioned.
-- The flow in Section 2.1 is a bit weird. Namely, it says “To overcome the first weakness”, but the first wickness wasn’t stated in the previous paragraph (of course, one can deduce it, and it also was defined long ago, but it’s disturbing for a reader).
-- Figure 1B is confusing: it looks like the nodes from N_g(v) lie in a small region around v.
-- I think that splitting Figure 1C into 2 figures would make it clearer.

review_title: Official Blind Review #2

final_score: rating: 8: Accept
review_content: The work is based on the premise that existing MPNNs have two main weaknesses: (i) the loss function doesn't properly capture the spatial information during graph convolution, and (ii) the difficulty to manage the information encoded in the long range connections.

The main contribution of this work is a novel method called geometric aggregation. The proposed method is based on two elements: (i) a latent space mapping to capture spatial information using a new bi-level operator, (ii) an integration of geometric aggregation inside GCN, namely geom-GCN. More in detail the idea reported in this work is to map the input graph into an embedding where the geometric relations between nodes are preserved. The graph is embedded using a usual embedding function that guarantees to preserve some graph property of interest like the hierarchy of nodes. After the node embedding, the authors propose to create a structural neighbourhood both (i) in the latent space, taking the nodes within an arbitrary radius, and (ii) in the original space, by taking the adjacent nodes. The expectation here is that with the proper embedding the latent space can catch connections, which are long range in the original space. The message passing is actuated exploiting first the structural neighbourhood to do low-level aggregation, which aggregates nodes that have the same geometric relationship using permutation invariant operators, and then the result of these aggregations, which are virtual nodes, are aggregated again through high-level aggregation making use of operators like concatenation.       

The goal of this work is clearly formulated by posing the proper research questions. The topic is relevant and it is part of the research agenda of ICLR. A key point of the proposed method is the ortogonalithy of geometric aggregation with respect to other aggregators like GAT. The design of the structural neighboorhood allows the network to choose which neighbors are the most important for the learning task.

Some minor comments.
The strong dependency from the embedding fuction does not guarantee the discovery of long range connections. It may happen that the proposed embedding does not catch the relevant information for the task; in these cases the a-priori knowledge on the task becomes crucial. This potential issue is partially supported by the results presented in the mauscript, where there is a gain only when the correct embedding is chosen. 
A further critical point is the choice of the radius. Such a choice can be operated only with an empirical assessment. It is not clear whether it migth be meaningful to choose a radius thatwould encode the same neighbourhood as in the original sapce of data.
The authors claim that even if there are more hops between two nodes the relevant information would arrive from the far node to the target node. Nevertheless we may conceive a situation where the relevant information is washed out during the hops. It may happen when the information of the far node is relevant for the target node, but it is not relevant for the target neighbour nodes.
The use of concatenation as high level operator is critically dependent from the radius and from the number of edges in the graph. In cases of large values for radius or very dense graphs, the concatenation may increase the spatial complexity of the networks.
Concerning the Section on empirical analysis, it might be of interest to investigate whether with a proper number of layers a GCN would emulate a geom-GCN.
review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: 
This work proposes geometric aggregation scheme for GCNs, which aims to overcome the limitations in traditional GCNs; those are lacking long distance dependencies and structure information in nodes. In particular, each node is transformed into a latent space. To overcome the first limitation, some nodes that are not directly connected but fall in a near range are also used in aggregation. A relational operator is used to provide position information for each pair of nodes. In this way, the structure information in graph can be used.

The method proposed in this work is novel and interesting. However, I am confused how this method can overcome the two limitations faced by previous GCNs. To my understanding, GEOM-GCN maps all node in to a 2D latent space. This can be treated as a lower-dimension representation for each node. Based on this, some similar nodes are clustered together. The relational operator is a kind of ranking operator that can rank two nodes based on latent space representations. If my understanding is wrong, please correct me.

Based on this understanding, I didn't find this method can solve the two limitations.
 
1. To overcome the long-term dependency limitation, GEOM-GCN selects some nodes that are close but not directly connected for aggregation. However, the selected nodes in this way may not connect to the center node. This is a issue that if two nodes that are not connected should be aggregated. The authors should clarify this.

2. The relational operator is used to provide a ranking between two nodes. However, how such kind of operators can be used to aggregate the structure information as described in GIN. For example, how to distinguish those example graphs using this work. I think it would be a plus if authors can make this clear in the paper.

3. The experimental studies are quite weak. Some ablation studies should be done to evaluate the contribution of each proposed methods. For example, how N_{s}(v) contributes to the performance. This is very important for fully evaluating your methods.

4. More tasks and datasets can be added such as graph classification and social networks.

5. Some notations are quite confusing. Like in eq.(1), why m is bold but W is not.
review_title: Official Blind Review #1

Meta-review: This paper is consistently supported by all three reviewers and thus an accept is recommended.
Decision: Accept (Spotlight)