FAST GRAPH ATTENTION NETWORKS USING EFFECTIVE RESISTANCE BASED GRAPH SPARSIFICATION
Authors: Rakshith Sharma Srinivasa
Cao Xiao
Lucas Glass
Justin Romberg
Jimeng Sun
Venue:  (2021)
Keywords: Graph neural networks
Graph attention networks
graph sparsification
spectral sparsification

Abstract: The attention mechanism has demonstrated superior performance for inference over nodes in graph neural networks (GNNs), however, they result in a high computational burden during both training and inference. We propose FastGAT, a method to make attention based GNNs lightweight by using spectral sparsification to generate an optimal pruning of the input graph. This results in a per-epoch time that is almost linear in the number of graph nodes as opposed to quadratic. Further, we provide a re-formulation of a specific attention based GNN, Graph Attention Network (GAT) that interprets it as a graph convolution method using the random walk normalized graph Laplacian. Using this framework, we theoretically prove that spectral sparsification preserves the features computed by the GAT model, thereby justifying our FastGAT algorithm. We experimentally evaluate FastGAT on several large real world graph datasets for node classification tasks, FastGAT can dramatically reduce (up to 10x) the computational time and memory requirements, allowing the usage of attention based GNNs on large graphs.

Under review as a conference paper at ICLR 2021
FAST GRAPH ATTENTION NETWORKS USING EFFEC- TIVE RESISTANCE BASED GRAPH SPARSIFICATION
Anonymous authors Paper under double-blind review
ABSTRACT
The attention mechanism has demonstrated superior performance for inference over nodes in graph neural networks (GNNs), however, they result in a high computational burden during both training and inference. We propose FastGAT, a method to make attention based GNNs lightweight by using spectral sparsification to generate an optimal pruning of the input graph. This results a per-epoch time that is almost linear in the number of graph nodes opposed to quadratic. We theoretically prove that spectral sparsification preserves the features computed by the GAT model, thereby justifying our FastGAT algorithm. We experimentally evaluate FastGAT on several large real world graph datasets for node classification tasks under both inductive and transductive settings. FastGAT can dramatically reduce (up to 10x) the computational time and memory requirements, allowing the usage of attention based GNNs large graphs.
INTRODUCTION
Graphs are efficient representations of pairwise relations, with many real-world applications including product co-purchasing network ((McAuley et al., 2015)), co-author network ((Hamilton et al., 2017b)), etc. Graph neural networks (GNN) have become popular as tool for inference from graph based data. By leveraging the geometric structure of the graph, GNNs learn improved representations of the graph nodes and edges that can lead to better performance in various inference tasks (Kippf & Welling, 2016; Hamilton et al., 2017a; Veličković et al., 2018)). More recently, the attention mechanism has demonstrated superior performance for inference over nodes GNNs ((Veličković al., 2018; Xinyi & Chen, 2019; Thekumparampil et al., 2018; Lee al., 2020; Bianchi et al., 2019; Knyazev et al., 2019)). However, attention based GNNs suffer from huge computational cost. This may hinder the applicability of the attention mechanism to large graphs.
GNNs generally rely on graph convolution operations. For a graph G with N nodes, graph convolution with kernel gw R + IR is defined
Tw h Ug (A)U h
where U is the matrix of eigenvectors and A is the diagonal matrix of the eigenvalues of the normalized graph Laplacian matrix defined as
L L I D 1/2 AD-1/1
with D and A being the degree matrix and the adjacency matrix of the graph, and Iw is applied elementwise. Since computing U and A can be very expensive (O(N*)), most GNNs use an approximation of the graph convolution operator. For example, in graph convolution networks (GCN) (Kipf & Welling, 2016), node features are updated by computing averages as a first order approximation of Eq.equation over the neighbors of the nodes. single neural network layer is defined as:
H (++) GCN = -
1/2 (1
(3)
where ( and (1) are the activations and the weight matrix at the /th layer respectively and À A + I and D is the degree matrix of Á.
Attention based GNNs add another layer of complexity: they compute pairwise attention coefficients between all connected nodes. This process significantly increase the computational burden,

---

Under review as a conference paper at ICLR 2021
especially on large graphs. Approaches to speed up GNNs were proposed in (Chen et al., 2018; Hamilton et al., 2017a). However, these sampling and aggregation based methods were designed for simple GCNs and are not applicable to attention based GNNs. There has also been works in inducing sparsity in attention based GNNs (Ye& & Ji, 2019; Zheng et al., 2020), but they focus on addressing potential overfitting of attention based models rather than scalability.
In this paper, we propose Fast Graph Attention ne work (FastGAT), an edge-sampling based method that leverages effective resistances of edges make attention based GNNs lightweight. The effective resistance measures importance of the edges in terms of preserving the graph connectivity. AT uses this measure to prune the input graph and generate a randomized subgraph with far fewer edges. Such procedure preserves the spectral features of a graph, hence retaining the information that the attention based GNNs need. At the same time, the graph is amenable to more complex but computationally intensive models such as attention GNNs. With the sampled subgraph as their inputs, the attention based GNNs enjoy much smaller computational complexity. Note that FastGAT is applicable to all attention based GNNs. In this paper, we mostly focus the Graph Attention NeTwork model (GAT) proposed by (Veličković et al., 2018). However we also show FasIGAT is generalizable to two other attention based GNNs, namely the cosine similarity based approach (Thekumparampil et al., 2018) and Gated Attention Networks (Zhang et al., 2018).
We note that Graph Attention Networks can be re-interpreted convolution based GNNs. We show this explicitly in the Appendix. Based on this re-interpretation, we theoretically prove that spectral sparsification preserves the feature representations computed by the GAT model. We believe this interpretation also opens up interesting connections between sparsifying state transition matrices of random walks and speeding up computations in GNNs.
The contributions of our paper are as outlined below:
We propose FastGAT, a method that uses effective resistance based spectral graph sparsification to accelcrate attention GNNs in both inductive and transductive learning tasks. The rapid subsampling and the spectrum preserving property of FastGAT help attention GNNs retain their accuracy advantages and become computationally light.
We provide theoretical justification for using spectral sparsification in the context of attention based GNNs by proving that spectral sparsification preserves the features computed by GNNs.
Fa outperforms state-of-the-arr algorithms across a variety of datasets under both transductive and inductive settings in terms of computation, achieving a speedup of up 10x in training and inference time. On larger datasets such as Reddit, the standard GAT model runs out of memory, whereas FastGAT achieves an F1 score 0.93 with 7.73 second per epoch time in training.
Further, FastGAT is generalizable other attention based GNNs such as the cosine similarity based attention (Thekumparampil et al., 2018) and the Gated Attention Network (Zhang et al., 2018).
2 RELATED WORK
Accelerating graph based inference has drawn increasing interest. Two methods proposed in (Chen al., 2018) (FastGCN) and (Huang al., 2018) speed up GCNs by using importance sampling to sample a subset of nodes per layer during training. Similarly, GraphSAGE (Hamilton et al., 2017a) also proposes an edge sampling and aggregation based method for inductive learning based tasks. All of the above works use simple aggregation and target simple GCNs, while our work focus on more recent attention based GNNs such (Veličković al., 2018). We are able to take advantage of the attention mechanism, while still being computationally efficient.
Graph sparsification aims to approximate a given graph by a graph with fewer edges for efficient computation. Depending on final goals, there are cut-sparsifiers ((eecczúr & Karger, 1996)), pair- wise distance preserving sparsifiers ((Althöfer et al., 1993)) and spectral sparsifiers ((Spielman & Teng, 2004; Spielman & Srivastava, 20)1)) among others (ZZaao 2015; Calandriello al., 2018; Hübler et al., 2008; Eden et al., 2018; Sadhanala et al., 2016)). In this work, we use spectral sparsification to choose randomized subgraph while preserving spectral properties. Apart form providing the strongest guarantees in preserving graph structure (CChu et al., 2018)), they align well with GNNs due their connection spectral graph convolutions.
2

---

Under review as a conference paper at ICLR 2021
Graph sparsification neural networks have been studied recently (Yee & Ji, 2019; Zheng et al., 2020; loannidis et al., 2020; Louizos et al., 2017)). However, their main goal is to alleviate overfitting in GNNs not reducing the training time. They still require learning attention coefficients and binary gate values for all edges in the graph, hence not leading to any computational or memory benefit. In contrast, FastGAT uses fast subsampling procedure, thus resulting in drastic improvement in training and inference time. It is also highly stable in terms of training and inference.
3. FASTGAT: ACCELERATING GRAPH ATTENTION NETWORKS VIA EDGE SAMPLING
3.1 THE FASTGAT ALGORITII
Let G V) be a graph with N nodes and M edges. An attention based GNN computes attention coefficients oijj for every pair of connected nodes j E V in every layer f. The di.j i are then used as averaging weights to compute the layer-wise feature updates. the original GAT formulation, the attention coefficients are
exp (Leaky T [Wh,l[Why) aij = Σ JEN, exp (LeakyReLU(a [Wh;]] Why]))
(4)
where h.'s are the input node features to the layer, W and are linear mappings that are learnt, NG; denotes the set of neighbors of node i, and denotes concatenation. With the 0xy 's as defined ahove, the node-i output embedding of a GAT layer is
h44 =a Σ JEN.
Oss osy Why
(5)
For multi-head attention, the coefficients are computed independently in each attention head with nead-depe matrices W and attention vector a. Note that the computational burden in GATs arises directly from computing the as in every layer, every attention head and every forward pass during training.
Goal: Our objective is to achieve performance equivalent to that of full graph attention networks (GAT), but with only fraction of the original computational complexity. This computational saving is achieved by reducing the number of attention computations.
Idea: We propose use edge-sampling functions that sparsify graphs by removing nonessential edges. This leads to direct reduction in the number of attention coefficients to be computed, hence reducing the burden. Choosing the sampling function is crucial for retaining the graph connectivity.
Let EdgeSample(& E, A, 9) denote a randomized sampling function that, given an edge set E, adja- cency matrix A and number of edges to be sampled q. returns a subset of the original edge set E, C E with FF, = q. Our algorithm then uses this function to sparsify the graph in every layer and attention head. Following this, the attention coefficients are computed only for the remaining edges. A more detailed description is given in Algorithm 1. In every layer and attention head, a randomized subgraph with q < M edges is generated and the attention coeffients computed only for this subset of edges. We use a specialized distribution that depends on the contribution of each edge to the graph connectivity. We provide further details in Section 3.2.
Note that in the general description below, the attention coefficients themselves are used as weights for sparsification and the reweighted attention coefficients are used to compute the feature update. Doing so helps in theoretical analysis of the algorithm. However in practice, we replace this expensive procedure with a one-time sampling of the graph with the original edge weights and compute the attention coefficients for only the remaining edges. In particular, of FastGAT include: i) PastGAT-const where the subgraph g is kept constant all the layers and attention heads and ii) MastGAT-layer where the subgraph is different in each layer (drawn stochastically from the original edge weights), but the same across all the attention heads within a layer.
use two simpler variations
3

---

Under review as a conference paper at ICLR 2021
Algorithm 1: The FastGAT Algorithm
Input:
Graph G(V, Num. layers = L, Num. Attention heads ((,) f = 1, L Initial Weight matrices W(O), Non-linearity o, Feature matrix H E RNxD Randomized edge sampling function EdgeSample()). Attention function ((-)
Num. edges sampled q
for each layer do
for each attention head k E 2,, ... K() } do
Compute attention matrix r(0)
k E ERNXN with r (i,j) do,, (h, (h))
Sample graph ((( Sampleel A.g)
Compute H. (++1) ( H w())
k
H
H // Concatenate the output of attention heads
Compute loss and update W/s// gradient based weight update
3.2 SAMPLING GRAPH EDGES USING EFFECTIVE RESISTANCES
We use a particular edge sampling function EdgeSample(() that motivated by the field spectral graph sparsification. Let L represent the graph Laplacian (defined as L = D - A where D is the degree matrix), (Z) denote the ith eigenvalue of L and let At denote the Moore-Penrose inverse of matrix.
Motivated by the fact that GNNs are approximations of spectral graph convolutions (defined in equation 1), we aim to preserve the spectrum (or eigenstructure) of the graph. Formally, let La and LH be the Laplacian matrices of the original graph G and the sparsified graph H. Then, spectral graph sparsification ensures that the spectral content of H is similar to that of G:
(1 (Lc)) (LH)) (1 c)), Vi
where is any desired threshold. (Spielman & Srivastava, 201 1) showed how to achieve this by using a distribution proportional to the effective resistances of the edges
Definition (Effectivve Resistance) (Spielman & Srivastava, 2011) The effective resistance between any two nodes of a graph can be defined as the potential difference induced across the two nodes, when unit current is induced at one node and extracted from the other node, Mathematically, it is defined as below.
Re, x) = - Leb
where be Xu Xo (Xi is a standard basis vector with in the 1th position) and Lt is the pseudo-inverse of the graph Laplacian matrix.
The effective resistance measures the importance of an edge to the graph structure. For example, the removal of an edge with high effective resistance can harm the graph connectivity. The particular function EdgeSample we use in FastGAT is described in Algorithm 2.
Algorithm 2: Effective resistance based EdgeSample function (Spielman & Srivastava, 2011)
Input: Graph G(EG, V), we is the edge weight for E E, <<1 For each edge e(u, v). compute (u, v) using fast algorithm in (Spielman & Srivastava, 2011) Set q = max (M, i0.10. log.N N/e)), H Graph(E Null, V) for i - 1 to y do
Sample an edge e; from the distribution Pe proportional to W.R. if En then
Add w./ qp. to its weight // Increase weight of an existing edge else Add e; to Eh with weight w./pp. /p.. // Add the edge for the first time
H Graph(EH, V)
4

---

Under review as a conference paper at ICLR 2021
The effectiiverrssistance based edge-samping function is described in Algorithm 2. For desired value of e, the algorithm sampled q = O(N log N/e²) number of edges such that equation is satisfied.
Choosing As shown in Algorithm. 2, it requires setting pruning parameter which determines the quality of approximation after sparsification and also determines the number of edges retained g. The choice of is design parameter at the discretion of the user. To remove the burden of choosing e, we also provide an adaptive algorithm in Section B.4 in the appendix.
Complexity. The sample complexity q in Algorithm. 2 directly determines the final complexity. If ON log 2/e²), then the spectral approximation in equation 6 can be achieved (Spielman & Srivastava, 2011). Note that this results in number of edges that is almost linear in the number of nodes, as compared to quadratic as in the case of dense graphs. The complexity of computing Rs for all edges (up to a constant factor approximation) of edges (Spielman & Srivastava, 201 1). While we describe the algorithm in detail in the appendix (Section B.3). it uses a combination of fast solutions to Laplacian based linear systems and the Sainson-Lindenstrauss Lemma This is almost linear in the number of edges, and hence much smaller than the complexity of computing attention coefficients in every layer and forward pass of GNNs. Another important point is that the computation of Rg 's is one-time cost. Unlike graph attention coefficients, we do not need to recompute the effective resistances in every training iteration. Hence, once sparsified, the same graph can be used in all subsequent experiments. Further, since each edge is sampled independently, the edge sampling process itself can be parallelized.
O(M log N) time, where M is the number
4 THEORETICAL ANALYSIS OF FASTGAT
In this section we provide the theoretical analysis of FastGAT. Although we used the sampling strategy provided in (Spielman & Srivastava, 201 1), their work address the preservation of only the eigenvalues of L. However, we are interested in the following question: Can preserving the spectral structure of the graph lead good performance under the GAT model? To answer this question, give an upper bound on the error between the feature updates computed by a single layer the GAT model using the full graph and sparsified graph produced by FastGAT.
Spectral sparsification preserves the spectrum of the underlying graph. This then hints that neural network computations that utilize spectral convolutions can be approximated by using sparser graphs We first show that this is true in a layer-wise sense for the GCN (Kipf & Welling, 2016) model and then show similar result for the GAT model well. Below, we use ReLU to denote the standard Rectified Linear Unit and ELU to denote the Exponential Linear Unit.
Theorem At any layer of a GCN model with inpul features (() E R.N weight matrix W E RDX,, if the element-wise non-linearity function is either the ReLU or the ELU function, the features H and H. computed using equation 3 with the full and layer dependent spectrally sparsified graph obey
H
S Sc HOW
where Lnorm is defined in equation 2 and
||-|| denotes the spectral norm.
In our next result, we show a similar upper bound on the features computed with the full and the sparsified graphs using the GAT model.
Theorem At any layer I of GAT with input features H E NRD weight matrix W E DxF and auj's 's be the attention coefficients in that layer. Let the non-linearity used by either ReLU or the ELU functon. Then, the features H, and H. computed using equation with the full and a layer dependent spectrally sparsified graph obey
H, H. S 12c (()((
(8)
F
where ||1|| denotes the spectral norm of the matrix.
lemma
5

---

Under review as a conference paper at ICLR 2021
Theorem 2 shows that our proposed layer-wise spectral sparsification leads to good approximations of latent embedding H for GAT model as well. The guarantees given above assume a layer-wise sparsification that is updated based on the attention coefficients. To circumvent the associated computational burden, we use the simpler versions such as I-const and always use the original weight matrix to sparsify the graph in each layer. In the experiment section, we show that such a relaxation by a one-time spectral sparsification does not lead to any degradation performance.
Approximation of weight matrices. Theorems 1 and 2 provide an upper bound on the feature updates obtained using the full and sparsified graphs. In practice, we observe an even stronger notion of approximation between GAT and FastGAT: the weight matrices of the two models post training are good approximations of each other. We report this observation in Section. A.4 in the appendix. We show that the error between the learned matrices is small and proportional to the value of itself.
EXPERIMENTS
Datasets We evaluated FastGAT on large graph datasets using semi-supervised node classification tasks. This is a standard task to evaluate GNNs, done in (Veličković et al., 2018; Hamilton et al., 2017a; Kipf & Welling, 2016). Datasets are sourced from the DGI.Graph library (DGL). Their statisties are provided in Table 1. We evaluate on both transductive and inductive tasks. The PPI dataset serves as a standard benchmark for inductive classification and the rest of the datasets for transductive classification. Further details about the datasets including details about train/validaton/ test split are given in the appendix (Section B.1). We also evaluated on smaller datasets including Cora, citeseer and Pubmed, but present their results in the appendix (Section B.2).
Table I: Dataset Statistics
Dataset
Reddit
Coauth-Phy
Github
Amaz. Comp
Coauth-es.
Amaz.Photos
PPI (Inductive tusk)
Nodes
232,965
34,493
37,700
13,752 287,209
18,333 163778
7,650
56944 (24 graphs)
Edges
57 mil
495.924
289,003
143,662
818716
Classes
41
10
8
121 (multilabel)
Transductive learning: We compare FastGAT with the following baseline methods. (1) The original graph attention networks (GAT) (Veličković et al., 2018), (2) SparseGAT (Ye Ji, 2019) that learns edge coefficients to sparsify the graph, (3) random subsampling of edges, and (4) FastGCN (Chen et al., 2018) that is also designed for GNN speedup. Note that we compare SparseGAT in transductive setting, whereas the original paper (Ye & Ji, 2019) uses an inductive setting. We thus demonstrate that FastGAT can handle the full input graph, unlike any previous attention based baseline method. Inductive learning: For this task, compare with both GAT (Veličković et al., 2018) and GrE (Hamilton et al., 2017a). More importantly, for both inductive and transductive tasks, show that a uniform random subsampling of edges results in drop in performance, where as FastGAT does not.
Baselines.
Evaluation setup and Model Implementation Details are provided in Section. B in the appendix.
Q1. FASTGAT PROVIDES FASTER TRAINING WITH STATE-OF-THE-ARR ACCURACY.
Our first experiment is to study FastGAT on the accuracy and time performance of attention based GNNs in node classification. We sample q = (0.16N log N/c2) number of edges from the distribution pe with replacement, as described Section 3.2.
Transductive learning: In this setting, we assume that the features of all the nodes in the graph, including train, validation and test nodes are available, but only the labels of training nodes are available during training, similar to (Veličković et al., 2018). First, provide direct comparison between FastGAT and the original GAT model and report the results in Table 2. As can be observed from the results, FastGAT achieves the same test accuracy the full GAT across all datasets, while being dramatically faster: we are able to achieve up to 5x on GPU (10x on CPU) speedup.
We then compare FastGAT with the following baselines: SparseGAT (Ye & Ji, 2019), random subsampling of edges and FastGCN (Chen et al., 2018) in Table 3. SparseGAT uses the attention mechanism to learn embeddings and a sparsifying mask on the edges. We compare the training

---

Under review as a conference paper at ICLR 2021
time per epoch for the baseline methods against FastGAT in Figure 1. The results shows that FastGAT matches state-of-the-art accuracy (F1-score), while being much faster. While random subsampling of edges leads to model that is as fast performance. FastGAT is also faster compared to FastGCN on some large datasets, even though FastGCN does not compute any attention coefficients. Overall the classification accuracy of FastGAT remains the same (or sometimes even improves) compared to standard GAT, while the training time reduces drastically. This is most evident in the case of the Reddit dataset, where the vanilla GAT model runs out of memory on machine with 128GB RAM and Tesla P100 GPU when computing attention coefficients over 57 million edges, while FastGAT can train with 10 seconds per epoch.
but with degradation in accuracy
Table 2: Comparison of FastGAT with GAT (Veličković et al., 2018).
Metric
Method
Reddit
Phy
Git
Comp
Photo
GAT
0OM
0.94=0.001
0.86=0.000
0.89=0.004
0.89=0.001
0.92:00001
F1-micro
PasGGAT-const0.5
0,93+0.000
0.94=0.001
0.86=0.001
0.88=0.004
0,88=0.001
0,91#0.002
FustGAT-comst-09
0.88+0.001
0.94=0.002
0.85=0.002
0.86=0.002
0.88=0.004
0.89=0.002
GAT
OOM
3.67
3.71
2.93
1.61
1.88
GPU Time (8)
7.73
1.96
2.06
0.83
1.14
0.66
FastGAT-comst-00
4.07
1.80
1.63
0.50
0.95
0.40
GAT
0OM
25.19
18.05
16.58
3.59
6.57
CPU Time (s)
FastGAAT-commt-0..
178.79
4.42
5.92
2.58
2.27
1.72
PastGAT-const-O0
41.42
2.70
3.44
1.22
1.48
0.77
PastG-AT-comst-l
97.0395
74.04%
55.6%
78.6%
67%
79.3%
Edges redu.
99.03%
88.48%
79.77%
91.99%
83.80%
91.86%
t(s)
Training time (s) per epoch
25
SparseGAT
FastGCNB00
FastGCNACO
Random
Random
20
FastGAT
15
10
Reddit
Physics
Git
Computers
CS
Photos
Figure I: Training time per epoch for our FastGAT model and baselines. FastGAT has significantly lower training time, while also preserving classification accuracy (in Table. 3). On the Reddit dataset, both GAT and sparseGAT models run out of memory in the transductive setting and hence we do not include bar graphs for them in the plot above.
Table 3: Transductive learning: While significantly lower training time (in Fig. 1), FastGAT still has comparable and sometimes better accuracy than other models. Computationally intensive model sparseGAT runs out of memory on the Reddit dataset.
Method
Reddit
Coauthor.PP Phy
Githuh
Amazon-Come
Coauthor-CS
Amazon Photos
FasGGCN-400 (Chen al., 2018)
0.77=0.001
0.95-0.001
0.86
0.8120.002
0.92:00001
0.86
FastGCN-800 (Chen et al., 2018)
0.81=0.001
0.95-0.001
0.86=0.001
0.80=0.009
0.92=00001
0.86:=0.00 007
GAT rand 0.5
0.87=0.002
0.94=0.001
0.85=0.001
0.86=0.003
0.88=0.002
0.90=00005
GAT rand 0.9
0,82-0.005
0.93-0.000
0.84=0.002
0.83:0.004
0.88=0.002
0.89:0.004
sparseGAT (Ye Ji, 2019)
0OM
0.94-0.004
0.84=0.002
0.85=0.001
0.88=0.002
0.91:00.003
FastGAT-layer-0055
0,93=0.001
0.95=0.001
0.86=0.002
0.88 =0.003
0. 088=0.002
0.90=0.005
BastGAT-layer-00
0.91=0.002
0.94-0.002
0.00000000
0.85=0.002
0. 0.88=00.022
0.90=0.002
FustGAT-const const-O..
0.93:0.000
0.94=0.001
0.86
0.88:4
0.88:0
0.91:0.002
FasGGAT const--.-
0.88=0.001
0.94-0.002
0.85=000022
0.86::0.022
0.8840.0004
0.89.0.0002
Inductive learning. FastGAT can also be applied to the inductive learning framework, where features of only the training nodes are available and training is performed using the subgraph consisting of
In Tables 2 and 3, FastGCN-400 4400 denotes that we sample 400 nodes in every forward pass, as described in (Chen et al., 2018) (similarly, in FastGCN-800, we sample 800 nodes). FastGAT--055 denotes we use 0.5. GAT rand 0.5 random subsampling of edges, but keeps the same number of edges FastGAT-0055
7

---

Under review as a conference paper at ICLR 2021
the Protein-Proteiis the training nodes. To show the utility of FastGAT in such setting,
interaction (PPI) dataset ((Zitnik & Leskovee, 2017)). Our model parameters are the same as in (Veličković et al., 2018), but sparsify each of the 20 training graphs before training them. The other 4 graphs are used for validation and testing (2 each). We use e = 0.25, 0.5 in our experiments, since the PPI dataset is smaller than the other datasets. We report the experimental results in Table 4. FastGAT clearly outperforms the baselines like GraphSAGE and uniform subsampling of edges. While it has the same accuracy performance the GAT model (which is expected), it has much smaler training time, as reported in Table 4.
Table 4: Inductive learning on PPI Dataset The training time per epoch for the full GAT method around 45.8s, whereas FastGAT requires only about 29.8s when = 0.25 and 20s when c < 0.5. FastGAT achieved the same accuracy GAT, and outperforms the other baselines, while also begin computatioanally efficient. The Fl score for GraphSAGE was obtained from what is reported in Veličković et al. (2018).
Method
score
GAT
0.974 10.002
GraphSAGE#
0.768 +0.000
GAT rand-0.25
0.95 =0.005
GAT rand-0.9
0.740.004
PastGAT-coonstO0
0.974 0.003
FastG/AT-cons-O0
0.800 + 0.005
Q2. FASTGAT CAN BE APPLIED TO OTHER ATTENTION BASED GRAPH INFERENCE METHODS.
Finally, we study if FastGAT is sensitive to the particular formulation of the attention function. There have been alternative formulations proposed to capture pairwise similarity. For example, (Thekumparampil et al., 2018) proposes cosine similarity based approach, where the attention coefficient of an edge is defined in equation 9,
( 0
softmax (I3 cos (h [n()) JEN.
where (0() is a layer-wise learnable parameter and cos(æ, y) = x: y/ |gl|- Another definition proposed in (Zhang al., 2018) Gated Attention Networks), which defines attention in equation 10,
softmax jEN;
FCas
(10)
where FC and FCast are 2-layered fully connected neural networks.
We performed similar experiments on these attention definitions. Tables. 5 confirmed that FasIGAT generalizes different attention functions. Note that the variability in accuracy performance across Ta- bles 2 and comes from the different definitions of the attention functions and not from FastGAT. Our goal is to show that given specific GAT model, FastGAT can achieve similar accuracy performance as that model, but in much faster time.
CONCLUSION
In this paper, introduced FastGAT, method to make attention based GNNs lightweight by using spectral sparsification. We theoretically justified our FastGAT algorithm. FastGAT can significantly reduce the computational time across multiple large real world graph datasets while attaining state-of- the-art performance.
REFERENCES
Deep graph library. https:/ /tte:://dooo /ttp//occsdooo dgl a /ww/e.//.../ x/indexx...xe html.
8

---

Under review as a conference paper at ICLR 2021
Table 5: Comparison of full and sparsified graphs.
FastGAT for Cosine Similarity
Reddit
Phy
Github
Comp
CS
Photo
Full graph
OOM
0.96=0.001
0.86+0.001
0.88+0.003
0.91=0.001
0,93=0.001
Fl-micro
0.5
0.93=0.000
0.95=0.001
0.86+00001
0.88+0.003
0.91=0.001
0,92=0.002
0.9
0.88=0.001
0.95=0.003
0.8620.002
0.87:0.004
0.89=0.002
0.90=0.002
Full graph
OOM
3.39
3,89
2.80
1.54
1.89
Time/epoch (s)
0.5
8.02
1.99
2.3
0.77
1.11
0.724
0.9
4.46
1.79
1.69
0.48
0.91
0.435
FastGAT for GaAN
Reddit
Phy
Github
Comp
CS
Photo
Full graph
OOM
0,94=0.001
0.86=0001
0.86+0.002
0.873#0.001
0.90=0.001
Fl-micro
0.5
0,92=0.001
0.94-0.002
0.86:1.000
0,8410.001
0.8710.002
0.89-00003
0.9
0.87=0.001
0,93=0.001
0.86=0.002
0.82+0.002
0.84 =0.001
0.88=0.002
Full graph
OOM
3.55
3.87
2.77
1.60
1.90
Time/epoch (S) == 0.5
8.10
1.93
2.10
0.84
1.10
0.67
0.9
4.47
1.54
0.50
0.90
0.41
Laplacians julia library. httph:tt////t http:::s/daasspiemmmma. github..hh.... io hto/aplacciass j1/v0. /v0. 1/.
Ingo Althöfer, Gautam Das, David Dobkin, Deborah Joseph, and José Soares. On sparse spanners of weighted graphs. Discrete Computational Geometry, 91):81--00,, 1993.
András A. Benczúr and David R. Karger. Approximating minimum cuts in Ó(n2) time. In Proceedings of the Twenty-Fighth Anmual ACM Symposium on Theory of Computing, STOC '96, pp. 47-55, New York, NY, USA, 1996. Association for Computing Machinery. ISBN 0897917855. doi: 144/277711.,377827, URL
/ooi. 111./1...1111//311111111
Filippo Maria Bianchi, Daniele Grattarola, Lorenzo Livi, and Cesare Alippi. Hierarchical rep- resentation learning graph neural networks with node decimation pooling, arXiv preprint arXiv: 1436, 2019.
Daniele Calandriello, Ioannis Koutis, Alessandro Lazaric, and Michal Valko. Improved large-scale graph learning through ridge spectral sparsification. 2018.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling. International Conference on Learning Representations (ICLR), 2018, Vancouver, Canada, 2018
Timothy Chu, Yu Gao, Richard Peng. Sushant Sachdeva, Saurabh Sawlani, and Junxing Wang. Graph sparsification, spectral sketches, and faster resistance computation, via short cycle decompositions. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 361-372. IEEE, 2018.
Talya Eden, Shweta Jain, Ali Pinar, Dana Ron, and C Seshadhri. Provable and practical approxima- tions for the degree distribution using sublinear graph samples. In Proceedings of the 2018 World Wide Web Conference, pp. 449-458, 2018.
Will Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning on large graphs In Advances in neural information processing systems, pp. 1024-1034, 2017a.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. CoRR, Abs//700.00216. 2017b.
Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. In Advances in neural information processing systems, pp. 4558-4567, 2018.
Christian Hübler, Hans- Peter Kriegel, Karsten Borgwardt, and Zoubin Ghahramani. Metropolis algorithms for representative subgraph sampling. In 2008 Eighth IEEE International Conference on Data Mining, pp. 283-292. IEEF, 2008.
Vassilis N. loannidis, Siheng Chen, and Georgios B. Giannakis. Pruned graph scattering transforms. In International Conference on Learning Representations, 2020. URL https: /ttp:///op/eeeee/eeeee net / forum? dey

---

Under review as a conference paper at ICLR 2021
Thomas N Kipf and Max Welling. Semi- Semi-supervised classification with graph convolutional networks. arxiv preprint 1609. 02907, 2016.
Boris Knyazev, Graham Taylor, and Mohamed Amer. Understanding attention and generalization in graph neural networks. In Advances in Neural Information Processing Systems, pp. 4204-4214, 2019.
Bohyun Lee, Shuo Zhang, Aleksandar Poleksic, and Lei Xie. Heterogeneous multi- network model for omics data integration and analysis. Frontiers in Genetics, 10:1381, 2020.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for
semi-supervised learning. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Christos Louizos, Max Welling, and Diederik P Kingma. Learning sparse neural networks through 1_0 regularization. arXiv preprint arXiv:1712.013/2. 2017.
Julian McAuley, Rahul Pandey, and Jure Leskovec. Inferring networks of substitutable and com- plementary products. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '15, pp. 785-794, New York, NY, USA, 2015. Association for Computing Machinery, ISBN 9781450336642.
doi: 10.1145/2783558877888388 27833381.
URL httph:tp////s.c / / org/10..//// 10411115//2 / 3258.22882 2783377833
Veeru Sadhanala, Yu-Xiang Wang, and Ryan Tibshirani. Graph sparsification approaches for lapla- cian smoothing. In Arthur Gretton and Christian C. Robert (eds.), Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, volume 51 of Proceedings of Machine Learning Research, pp. 1250-1259, Cadiz, Spain, 09-11 May 2016. PMLR. URL walr.presss /v51/ h05l/sadhanald. 1alll166...... html.
http:/ http:///ooceeedeeeeeee
Daniel A. Spielman and Nikhil. Srivastava. Graph sparsification by effective resistances. SIAM doi: 10.1137/08073402, URL https://ddo
Journal on Computing, 1016):1913-1926. 201
Stgg/1..1177/8001 0011113007330225
Daniel A Spielman and Shang-Hua Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pp. 81-90, 2004.
Daniel Spielman and Shang-Hua Teng. Spectral sparsification of graphs. SIAM Journal on Computing, 40(4):981-1025, 2011.
Gabriel Taubin. A signal processing approach to fair surface design. In Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, pp. 351-358, 1995.
Kiran K Thekumparampil, Chong Wang, Sewoong Oh, and Li-Jia Li. Attention- based graph neural network for supervised learning. arXiv preprint arXiv:1803.003 180.00333, 2018.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. International Conference on Learning Representations, 2018.
URL https:::: /ttp:////ppeeeeeee////ts//e net forum? id=rJXMpiKCZ.
Zhang Xinyi and Lihui Chen. Capsule graph neural network. In International Conference on Learning Representations, 2019. URL https::tp///cc http:/::////eeevveeeeeeee net. www.mfrrrmmooooooo fateet//oormmmmiBB/earaaa BBBRRcYm.
Yang Ye and Shihao Ji. Sparse graph attention networks. arXiv preprint arXiv:1912.0053: 2019.
Jiani Zhang, Xingjian Shi, Junyuan Xie, Hao Ma, Irwin King, and Dit-Yan Yeung. Gaan: Gated atten- tion networks for learning on large and spatiotemporal graphs. arXiv preprint 18Xvv:1803.0729. 2018.
Peixiang Zhao. gsparsify: Graph motif based sparsification for graph clustering, In Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, pp. 373-382, 2015.
Cheng Zheng, Bo Zong, Wei Cheng, Dongjin Song, Jingchao Ni, Wenchao Yu, Haifeng Chen, and Wei Wang. Robust graph representation learning via neural sparsification, 2020. URL https:://penreett net forum? dd d1 1=$1 emOTNKvS.
10

---

Under review as a conference paper at ICLR 2021
Marinka Zitnik and Jure Leskovec. Predicting multicellular function through multi-layer tissue networks. Bioinformatics, 33(44):110--1188 2017.


Reviews:
[{"review_id": "lO1KmwTAbuf", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Summary\nThis 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.\n\n## Reasons for Score\nThe 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.\n\n## Pros\nThe 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.\n\n## Cons\n1. 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. \n\n2. 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.\n\n3. 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]).\n\n[1] FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling\n[2] Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks\n\n## Post rebuttal\nThanks for providing detailed explanations.\n\nOverall, 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.\n\nHowever, 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.\n\nGiven 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.\n\nFor the current status, I would still lean towards a rejection.\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "gkTL9mWfbn1", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nThis 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.\n\n1. 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. \n\n2. 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. \n\n[1] Diffusion helps graph learning. NeurIPS'19. (and its references.)\n\n---post-discussion update---\nI 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. \n\nHowever, 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)?", "extra_scores": {}, "extra_text": {}}, {"review_id": "aznoRKJ68qt", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThe 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.\n\nIt 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:\n\n- 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.\n- Typos: \"Eq.equation 1\", \"We compar\"\n\n============= Post-rebuttal:\n\nI thank the authors for their careful responses. After discussing with other reviewers:\n- I agree that the sparsification method proposed here is also in principle applicable to GCN-like models;\n- 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.\"\n- 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.\n\nIn 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).", "extra_scores": {}, "extra_text": {}}, {"review_id": "RU_gTVQGF7-", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nComments:\nSection 3 - Clarification questions on your algorithm:\n1. Do you denote by A the weighted or unweighted adjacency matrix?\n2. Do you sparsify the original graph as a weighted or unweighted graph (and if weighted then with what weights)?\n3. 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. \n\nSection 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:\n1. The statements of theorems 1,2 are inconsistent in whether to use the superscript \"(l)\" for H and W.\n2. \"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.\n3. By the way, ||L_norm|| (spectral norm) is at most 2 for any graph.\n\nOverall: 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.\n\n=== Post-discussion update ===\n\nI thank the authors for engaging in the discussion.\n\nI 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).\n\nI 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.)\n\nNevertheless, 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.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

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