Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: ## Summary
This paper proposes a paradigm which speeds up the training/inference time of GATs while not compromising too much performance. The method adopts a layerwise sampling procedure. In particular. The authors propose to sample a sub-portion of edges for each layer based on their effective resistance. Such sampling keeps the spectral similar to the original results theoretically and gives a guarantee to the performance drop.

## Reasons for Score
The paper discusses the important topic of fast training and inference and proposes a sampling strategy over edges that have not been discussed (e.g. previously mostly on nodes). My main concern is about the novelty (a direct application of sparsification) without too much discussion about the broader sparsification family and the whether this technique is universal enough on other GNN frameworks.

## Pros
The paper tackles the problem of fast GAT training/inference, which is an important problem when training large-scale networks. The proposed method shows good empirical results with a proper theoretical guarantee.

## Cons
1. Novelty. The overall framework seems to be a direct application of effective resistance-based edge sampling. The theorem followed-up seems a direct result which makes the novelty limited. With this being said, a more meaningful investigation (both in the related works or simple experiment justification) of the broader area of (weighted) spectral sparsifier may be discussed. 

2. Applicable to other GNN networks. While the resistance-sampling strategy seems a standalone strategy and not particularly bound to GAT, whether this paradigm can be a universal technique in other GNN networks (e.g. plain GCN) is worth investigating.

3. The comparison of FastGCN [1] w.r.t performance may not be that fair. The barebone framework of FastGCN and this work FastGAT differ, it might be meaningful to compare the metrics under the same setting (both GCN or GAT). Also, some other node-sampling procedures might be meaningful baselines (e.g. Cluster-GCN [2]).

[1] FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling
[2] Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks

## Post rebuttal
Thanks for providing detailed explanations.

Overall, I think the authors tried hard to prove the concept of “edge” sparsification helps for speedup of “attention” GNNs which I also think they explanations/rebuttals succeeded in doing this, though the established theory seems quite standard and is not the same as in the experiments.

However, pertaining the results I still do not see a claimed comparison of GCN, “FastGAT”-sparsified GCN in the revised work based on the replies to R3 (only FastGCN is reported. Note this is not a direct adaption of the authors’ method, but from the previous node-sampling literature). As is claimed by the authors, performing sparsification on GCN does not provide seminal speed boost. However, while GCN is a strong/simple baseline without heavy parameter tuning, it’s hard to make a clear justification on why a sparsified heavy-attention-computation network (FastGAT) would do any good if its final results are barely comparable/similar to a naive GCN baseline with a similar running time.

Given the idea of sparsification is not novel which I stand on a similar point with R3 and specifically with its linkage to GDC. I think the current paper may need to be improved with some more evidence on proving the “edge” sparsification method is superior to other “node” sparsification versions of attention networks e.g. empirically/theoretically better (“FastGCN”-sparsified, “ClusterGCN”-sparsified models) on a complete set of datasets; or with a more rigorous comparison to other simple GCN-versioned sparse methods that do not need the heavy attention computation in the first place.

For the current status, I would still lean towards a rejection.



review_title: Good empirical results, more discussions needed on sparsification family and transferrableness of this approach

final_score: rating: 6: Marginally above acceptance threshold
review_content: The authors propose FastGAT, a methodology for guided sparsification of graphs such that they will largely preserve performance of graph attention networks (GATs), while vastly improving on their computational performance.

The sparsification is based on the spectral properties of the input graphs, and seems to be backed by strong theorems that dictate the upper bound on the distance between the computed features and full-graph features. Results on many datasets seem to strongly back this, and demonstrate that such a sparsifier indeed performs better than purely randomised sparsifying.

It looks like an interesting and novel paper that could enable large-scale applications of attentional GNNs. I like that authors surveyed several attentional mechanisms (e.g. AGNN and GaAN) and confirmed their findings across them. I recommend acceptance, and would invite the authors to consider the following:

- The authors mention that GraphSAGE is not amenable to attentional models, but in principle, isn't GraphSAGE style update (node batching + subsampling neighbours with replacement) what GaANs already usefully applied to Reddit? If there are no clear reasons why GraphSAGE sampling + GAT is not applicable, maybe it should be included as a baseline.
- Typos: "Eq.equation 1", "We compar"

============= Post-rebuttal:

I thank the authors for their careful responses. After discussing with other reviewers:
- I agree that the sparsification method proposed here is also in principle applicable to GCN-like models;
- The authors should have provided results for "FastGAT"-style sparsification on GCN, rather than countering the reviewers using passages like "Hence, it is mainly the question of necessity rather than applicability which guided our choice of studying the GAT model in depth."
- If such a GCN model ends up competitive, the focus of the paper could switch to the sparsification method itself rather than the GNN model it is applied to.

In light of these discussions, I am decreasing my score to a weak accept, and I hope the authors will take this advice for the next iteration of their work (which otherwise, in my opinion, deserves being published in a strong venue).
review_title: Impressive results on scaling up GATs

final_score: rating: 4: Ok but not good enough - rejection
review_content: This work proposed to use graph-sparcification method to decrease the number of edges so as to support GAT training over large networks. The graph sparcification approach is based on resistance. Empirical results by comparing with standard GAT or randomly edge-dropping strategy demonstrate the effectiveness of their approach. 

This work is written very well. The logic flow is good. I also appreciate the experiments as the authors tend to demonstrate their method in a comprehensive way. However, I think that this work is only with limited novelty given some previous works and therefore cannot give a recommendation.

1. This work seems to simply combine two irrelevant techniques together to make it read novel. However, there two techniques seem to be contradictory in some sense: Obviously, the graph-sparsification method in this work is independent of the GAT building block. I believe that it can be also used to improve GCN, which also works well as long as the networks are homophilic as used in the evaluation sections. Moreover, as the graph sparsification capture the edges that emphasize more on network centralities, it will naturally reduce the advantage of GAT over GCN, when they are both combined with this graph sparsification. This is because the graph sparsification naturally performs some selection on effective edges just as GAT did. So in my mind, perhaps, graph sparsification + GCN have already done a very good job and have much less complexity, where attention is never needed. If we ignore the attention part, it is actually not novel to user graph diffusion (including resistance used in this work which is nothing but a more complex result of graph diffusion (commute time)) to revise graph topology and perform graph sparsification. Please check [1]. Given the above points, I did not see much novelty and rationality from this work. 

2. The theoretical analysis is not novel, which is just some easy analysis regarding spectral graph theory. Moreover, GCN has a tighter bound than GAT, which may also be related to my concern in the first bullet. I think the only valid theoretical results are to demonstrate the end-to-end performance instead of just one-layer distortion. 

[1] Diffusion helps graph learning. NeurIPS'19. (and its references.)

---post-discussion update---
I greatly appreciate the authors' effort to actively attend the discussion. In general, I like the idea to leverage the graph sparsification technique to accelerate GNN training. 

However, I think there are still several fundamental questions that should be well addressed before this paper get accepted.  First, I do not see clear reasons to emphasize a specific model GAT. One concern arises during the discussion, where the sparsification technique here only works for GAT instead of GCN or other GNN smoothing models, which brings me some concerns about the technique. Second, the fundamental difference between this method and GDC [1] is still not clear. Both methods emphasize the low-frequent section of the graph connection. Why does the sparsification method here work while GDC does not work, though the sparsification method here can also be viewed as a type of graph diffusion (GDC)?
review_title: Limited novelty

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary: This paper suggests speeding up attention in graph neural networks by computing a spectral sparsifier of the graph, and letting each node attend only to its neighbors in the sparsifier. Some theoretical justifications are presented. The experimental results show that the accuracy remains about the same while gaining computational efficiency.

Comments:
Section 3 - Clarification questions on your algorithm:
1. Do you denote by A the weighted or unweighted adjacency matrix?
2. Do you sparsify the original graph as a weighted or unweighted graph (and if weighted then with what weights)?
3. In section 3.1 you describe your algorithm as using an edge sampling procedure that returns a subset E_s of the input edges E. However. spectral sparsification returns a weighted graph (regardless of whether the original graph was weighted or unweighted), so in addition to E_s you get new edge weights. Where are those sparsifier weights used in the FastGAT algorithm (algorithm 1)? If they aren't used then the theoretical results would not hold. 

Section 4 - The novelty of the theoretical results is perhaps somewhat oversold, as they follow rather immediately from the definition of spectral sparsification. It is not quite true that Spielman-Srivastava "address the preservation of only theeigenvalues of L", as their result preserves the Laplacian quadratic form for any vector (which is indeed what you use in the proof of theorems 1 and 2). Small remarks on this section:
1. The statements of theorems 1,2 are inconsistent in whether to use the superscript "(l)" for H and W.
2. "The complexity of computing R_e for all edges is O(M log N) time" - such result is not known, what Spielman-Srivastava compute in that time complexity is a constant approximation of each R_e, which is sufficient for their importance-sampling spectral sparsification scheme as long as edges are oversampled accordingly.
3. By the way, ||L_norm|| (spectral norm) is at most 2 for any graph.

Overall: The approach generally makes sense and the experiments show benefit, so pending some clarifications about the algorithm requested above, I think the paper can be accepted.

=== Post-discussion update ===

I thank the authors for engaging in the discussion.

I am left somewhat divided on the paper. During the discussion phase, the statement of the main algorithm in the paper changed quite significantly: in the original version each node could attend only to its neighbors in the sparsifier, while in the current version each node attends to all its neighbors (i.e., full graph attention is computed), and the sparsifier is only used in the subsequent feature update. The authors eventually explained that their analysis holds for the latter algorithm (even though its running time is not faster than non-sparsified GAT), while the former algorithm is what they actually implement since it has better running time (albeit no formal guarantees).

I don't take issue with the divide between the theory and the implementation (as long as it is made clear in the paper). I do think, however, that perhaps the theoretical content ended up doing the paper more harm than good. Effective resistances measure the "importance" of edges to the connectivity of the graph - this is a general phenomenon, and the sparsification algorithm of Spielman-Srivastava is just one (beautiful and useful) manifestation of it. I can see why the practical algorithm would work even if it cannot be explained formally via spectral sparsification, and including the slow unimplemented algorithm just for the sake of its analysis feels a bit forced. What does it add to our understanding, and was it worth making the paper that much more confusing? Ultimately it's the author's choice, but even now the way the writeup deals with the two algorithms is still "evolving", and it is not clear how a final version would look. (I don't think the current form makes sense, since the algorithm now titled "FastGAT" is not faster than GAT, and section 3.1 zigzags between the two algorithms somewhat awkwardly.)

Nevertheless, in the end the authors were straightforward about all this in the discussion. As I said originally, I like the overall approach, so as long as the clarifications about the gap between the analysis and the implementation are included, and pending other reviewers' concerns about novelty and experimental validation (I am less versed in the empirical literature on GNNs so prefer to defer to them on those points), I think the paper could still be accepted.
review_title: Generally reasonable approach, some questions

Meta-review: Two reviewers recommend rejection, whereas two reviewers slightly lean towards acceptance. All reviewers agree that the paper tackles an important problem, and the proposed direction holds promise and is worth exploring. However, the reviewers raised concerns about the novelty of the proposed approach [R3,R4], the applicability of sparsification to GCN-based models [R3,R4], baseline experiments [R1,R3,R4] and the gap between the theoretical aspect of the paper and the implementation of the proposed approach [R2]. The authors engaged with the reviewers during the discussion period and succeeded in motivating the speedup gains of their method, and clarifying some of the reviewer's concerns. However, after discussion, the reviewers still think this is a borderline paper, which could be significantly strengthened by validating the applicability of the proposed sparsification to other GNNs [R1,R2,R3], and in particular, by including the suggested FastGAT-sparsified GCN experiment [R1,R3,R4]. The paper could also benefit from improving the presentation of both the analyzed approach and the practical one [R2]. I agree with reviewers' assessment and therefore must reject. However, I acknowledge that the paper does raise notable interest and I encourage the authors to consider the reviewers' suggestions in future iterations of their work.
Decision: Reject