Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: This paper proposes a new graph Hierarchy representation named HAG. The HAG aiming at eliminating the redundancy during the aggregation stage In Graph Convolution networks. This strategy can speed up the training and inference time while keeping the GNN output unchanged, which means it can get the same predict result as before. The idea is clear and easy to follow. For the theory part, I do not thoroughly check the theoretical proof but the theorem statement sounds reasonable for me. The experiment shows the HAG performs faster in both training and inference.

Generally speaking, I think this paper has good theory analysis, the speed-up effect is also good from the experimental result.  However, I still have some concerns and comments.

1. The algorithm seems hard to apply on the attention-based Graph Neural network, which achieves good performance in several benchmarks these years. In other words, the redundancy of the node aggregate only exists in the Graph Convolution model with the fix node weight, which is replaced by a dynamic weight in many latest models with higher performance. That weakens the empirical use of this algorithm.

2. The authors state that the HAG can optimize various kinds of GNN models, but the experiment only shows the results on a small GCN model. More GNN results in different models and settings would make the algorithm more convincing.

In conclusion, I think this is a good paper. Regards the comments above, I prefer a grade around the borderline. 
review_title: Official Blind Review #4

final_score: rating: 3: Weak Reject
review_content: This paper aims to propose a speeding-up strategy to reduce the training time for existing GNN models by reducing the redundant neighbor pairs. The idea is simple and clear. The paper is well-written. However, major concerns are:

1. This strategy is only for equal contribution models (e.g., GCN, GraphSAGE), not for methods which consider distinct contribution weights for individual node neighbor (e.g. GAT). However, in my opinion, for one target node, different neighbors should be assigned with different contributions instead of equal contributions.

2. What kind of graphs can the proposed model be applied to? This paper seems to only consider unweighted undirected graphs. How about directed and weighted graphs? Even for an unweighted undirected graph, the symmetric information may also be redundant for further elimination. Then can HAG reduce this symmetric redundancy?

3. There is no effectiveness evaluation comparing the original GNN models with the versions with HAG. The authors claim that, with the HAG process, the efficiency could be improved without losing accuracy. But there are no experimental results verifying that the effectiveness of the HAG-versions which could obtain comparable performance with the original GNN models for some downstream applications (e.g., node classification).

--------------------------------------------------Update------------------------------------------------
Thanks very much for the authors' feedback. The revised version has clarified some of my concerns. However, the equal-contribution (in Comment 1) is still a big one that the authors should pay attention. I increase my score to 3.

review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: In this paper, authors propose a way to speed up the computation of GNN. More specifically, the hierarchically aggregate computation graphs are proposed to aggregate the intermediate node and utilize this to speed up a GNN computation. Authors proof that the computation based on HAGs are equivalent to the vanilla computation of GNN (Theorem1). Moreover, for sequential aggregation, it can find a HAG that is at least (1-1/e)-approximation of the globally optimal HAGs (Theorem 3). These theoretical results are nice. Through experiments, the authors demonstrate that the proposed method can get faster computation than vanilla algorithms.

The paper is clearly written and easy to follow. However, there are some missing piece needed to be addressed.
I put 6 (weak accept), since we cannot put 5. However, current my intention about the score is slightly above 5.

Detailed comments:
1. Experiments are only done for computational time comparison. In particular, for the sequential one, prediction accuracy can be changed due to the aggregation algorithm. Thus, it needs to report the prediction accuracy.

2. In GraphSAGE, what is the sampling rate? It would be nice to have the trade-off between the sampling rate and the speedup. I guess if we sample small number of points in GraphSAGE, the performance can be degraded. In contrast, the proposed algorithm can get similar performance with larger sampling rate? Related to the question 1, the performance comparison is needed. 

3. Equations are used without not explaining the meaning. For instance AGGREGATE function (1), there is no definition how to aggregate. 

review_title: Official Blind Review #32

Meta-review: This paper proposes a new graph Hierarchy representation (HAG) which eliminates the redundancy during the aggregation stage and improves computation efficiency. It achieves good speedup and also provide theoretical analysis. There has been several concerns from the reviewers; authors' response addressed them partially. Despite this, due to the large number of strong papers, we cannot accept the paper at this time. We encourage the authors to further improve the work for a future version.  



Decision: Reject