LSP : Acceleration and Regularization of Graph Neural Networks via Locality Sensitive Pruning of Graphs
Authors: Eitan Kosman
Dotan Di Castro
Joel Oren
Venue: ICLR 2022 Submitted (2022)
Keywords: Graph Sparsification
Graph Neural Networks
Pruning Neural Networks

Abstract: Graph Neural Networks (GNNs) have emerged as highly successful tools for graph-related tasks. However, real-world problems involve very large graphs, and the compute resources needed to fit GNNs to those problems grow rapidly. Moreover, the noisy nature and size of real-world graphs cause GNNs to over-fit if not regularized properly. Surprisingly, recent works show that large graphs often involve many redundant components that can be removed without compromising the performance too much. This includes node or edge removals during inference through GNNs layers or as a pre-processing step that sparsifies the input graph. This intriguing phenomenon enables the development of state-of-the-art GNNs that are both efficient and accurate. In this paper, we take a further step towards demystifying this phenomenon and propose a systematic method called Locality-Sensitive Pruning (LSP) for graph pruning based on Locality-Sensitive Hashing. We aim to sparsify a graph so that similar local environments of the original graph result in similar environments in the resulting sparsified graph, which is an essential feature for graph-related tasks. To justify the application of pruning based on local graph properties, we exemplify the advantage of applying pruning based on locality properties over other pruning strategies in various scenarios. Extensive experiments on synthetic and real-world datasets demonstrate the superiority of LSP, which removes a significant amount of edges from large graphs without compromising the performance, accompanied by a considerable acceleration.

Under review as a conference paper at ICLR 2021
LSP ACCELERATION AND REGULARIZATION OF GRAPH NEURAL NETWORKS VIA LOCALITY SENSI- TIVE PRUNING OF GRAPHS
Anonymous authors Paper under double-bling blind review
ABSTRACT
Graph Neural Networks (GNNs) have emerged highly successful tools for graph-related tasks. However, real-world problems involve very large graphs, and the compute resources needed to fit GNNs to those problems grow rapidly. More- over, the noisy nature and size real-world graphs cause GNNs to over-fit if not regularized properly. Surprisingly, recent works show that large graphs often in- volve many redundant components that can be removed without compromising the performance too much. This includes node edge removals during inference through GNNs layers or as a pre-processing step that sparsifies the input graph. This intriguing phenomenon enables the development of state-of-the-an GNNs that are both efficient and accurate. In this paper, we take further step towards demystifying this phenomenon and propose a systematic method called Locality- Sensitive Pruning (LSP) for graph pruning based on Socality-Sensitivy Hashing. We aim to sparsify a graph so that similar local environments of the original graph result in similar environments in the resulting sparsified graph, which is an es- sential feature for graph-related tasks. To justify the application pruning based local graph properties, exemplify the advantage of applying pruning based on locality properties over other pruning strategies in various scenarios. Exten- sive experiments on synthetic and real-world datasets demonstrate the superiority of LSP, which removes a significant amount of edges from large graphs without compromising the performance, accompanied by considerable acceleration.
INTRODUCTION
Graph neural networks have become extremely popular for tasks involving graph-data. The majority of architectures employ varieties of message-passings. such Graph Convolutional Networks (Kipi
Welling 2016), Graph Isomorphism Networks (Xu et al. 2018) and more (Wu et al. 2020). These architectures propagate belief information from nodes of graph through adjacencies in order to generate representations that depend on wide graph environments. This property makes them well suited for learning tasks such node classification (Bhagat et al., 2011 /hang et al. 2018), link
prediction (Kumar et al. (020)) and graph classification (Kriege et al. 2020 Cai et al. 2018).
Although the aforementioned architectures have demonstrated great success, recent research has shown considerable limitations of GNNs. First, more complex architectures tend to be computation- ally demanding. For instance, Graph Attention Networks (GATs) (Veličković al. 2017) whose neighborhood aggregation mechanism employ computations of self-attentions to assign weights for neighboring nodes. Second, this methodology of neighborhood aggregation leads to an exponen- tially growing amount of information originating from exponentially growing neighborhoods that needs to be encoded within fixed-size node representation vectors, a phenomenon referred as over- squashing (Alon & Yahav| 2020). Furthermore, the varying number of nodes participating in each node's neighborhood leads to highly varying amount of information that needs to be encoded within fixed-length code, a phenomenon that we call the varying neighborhoods. Note that many other architectures (c.g., CNNs, MLPs, and RNNs) do not encounter this since they only accept fixed-size inputs produce outputs with varying sizes that correspond to the input size. GNNs break this correspondence due to their neighborhood aggregation methodology. These phenomena become very prominent as the depth of the neighborhood grows, which limits our ability to develop

---

Under review as a conference paper at ICLR 2021
Pruning similar environments
Pruning dissimilar
environments
Prune consistently
Prune
Prune consistently
randomly
Input
Figure Illustration of consistent pruning versus non-consistent pruning. On the left, the input consists of a graph with two highlighted environments whose topology is similar because the cen- tral nodes have the same set of neighbors. this case, consistent pruning results with a graph that preserves the similarity between these environments while non-consistent pruning, e.g., ran- dom removal edges, results with dissimilar environments. On the right, the two highlighted environments have dissimilar topologies because the central nodes have different sets of neighbors. Consistent pruning is likely to preserve this dissimilarity, while random might bring the similarity between them closer.
deep GNNs. We further discuss these phenomena and provide explanations on how pruning edges could help mitigating them in Section 4.4.2
A popular approach for tackling these problems is to apply some transformation augmentation to the input graph. One prominent approach is Graph Sparsification (Hu Lau 2013 Spielman & Teng 2008 Spielman & Srivastaval 2008 Calandriello et al. 2018) in order to accelerate GNNs by removing nodes and edges from a graph under the constraint preserving the predictive perfor- mance (Rong al. 2019 Srinivasa et al. 2020 Ye & Ji 2021 Hamilton al. 2017). In fact, Faber ct al. (202I) showed that very often a significant amount of edges can be removed without degrading the performance of a model, which raises concern regarding the usage of popularly used bench- marks. They claimed that those tasks can be virtually solved through node features only, implying that the graph topology has limited contribution and edges can be safely disregarded.
Motivated by the above discussion, we argue that graph sparsification can greatly improve the per- formance of GNNs in tasks where the graph topology is significant. Moreover, we argue that sparsi- fication that is based on local properties of a graph is more in-line with the prevailing methodology of GCNs, as opposed to approaches that rely on global topologies, such as spectral methods. There- fore, we introduce Locality Sensitive Pruming, new algorithm for edges pruning based on locality sensitive hashing (L.H) (Shakhnarovich al., 2008). As a result, pruned graphs are qualified with structure dynamics that alleviate the ability to distinguish between different graphs and mitigate the computation burden. More importantly, similar environments of the input graph result similar en- vironments in the sparsified graph while dissimilar environments result in dissimilar environments in the sparsified graph with high probability, as depicted in Figure [ Consequently, we preserve the ability to distinguish between environments of the graph that were distinguishable prior to the sparsification process.
RELATED WORK
Graph Convolutional Networks (GCNs) were introduced by Kipf & Welling (016) and has been widely adopted for solving tasks involving graphs, such as node classification (Bhagat et al.) Zhang et al.) 2018), link prediction (Kumar et al.) 2020), graph classification (Kriege et al, Cai et al. 2018), and more. The most basic form uses simple aggregation functions to obtain a node representation as a function its neighbors, such as average and summation. Later, the model was extended more complex architectures which introduce more sophisticated aggregation functions. For instance, Graph attention Networks (GATs) /Veličkovi et al., 2017) use dot-products based attention calculate weights for each edge. Additionally, Corso al. (2020) argued that
2011
2020
2

---

Under review as a conference paper at ICLR 2021
the aggregation layers unable to extract enough information from the nodes' neighbourhoods in a single layer, resulting in a limited expressive power and learning abilities. To address this, they proposed Principal Neighbourhood Aggregation for Graph Nets (PNA) which combines multiple aggregators to improve the performance of the graph neural networks.
Graph Sparsification aims approximate a graph on the same set of vertices and edges (Benczur & Karger 2002). Much research has been done in this field and several algorithms were proposed,
including spectral sparsifiers (Spielman & Teng 2008; Calandriello al. [2018) Chu et al. 2020),
sampling via Metropolis algorithms (Hübler et al. 2008), and others (Sachanala et al. 2016). In the context of training graph neural networks, the motivation is twofold: 1. accelerate training by performing fewer crassage-passing operations, and 2. regularization. For the former, (Srinivaaa et al. (2020) propose FastGAT, spectral sparsifier based on infective-resistanee 2008) for acceleration of GATs. Specifically, they aim to accelerate GATs by constructing sampled graph with far fewer edges for each attention head within the network. Chen et al. (2018) proposed FastGCN which samples vertices and edges through importance sampling and thus reduces the graph
(Spielman Srivastava
size. Another line works (Rong et al.] [2019] Chen et al., 20200; Hasanzadeh et al. [2020] Zheng
jet al., 2020; Luo et al. 2021; Kim & Ohl 2020 Ye & Ji
2021 perform graph sparsification to
achieve regularization, with the aim to prevent over-smoothing and overfitting (Li et al. 2018).
Locality-sensitive hashing (LSH) is a widely used technique for finding pairs of similar items in a large set efficiently. It has been successfully applied for accelerating the Transformer model Vaswani al. 2017) by mitigating the burden of computing pair-wise attentions as demonstrated by the Reformer (Kitaev et al., 2000). This is done by approximation of attention computations based on Docality-sensitive hashing, which replaces the O(L) factor in attention layers with OL logL).
PRELIMINARIES
3.1 GRAPH CONVOLUTIONAL NETWORKS (GCNS)
A graph is a 2-tuple G = (V, E) where V is a set of nodes and E C V x V is a set of undirected edges connecting pairs of nodes. We consider the setting in which each node is associated with feature vector Fu R.d. The adjacency matrix of G, denoted by A E (0,1)IVixIV associates each edge eijj = (v), UU) E E with an entry Ai, indicating that ei E E. The number of edges connected
Ai.j We define D as a diagonal consider the Graph Convolutional Network (GCN) model from Kipf& & Welling (2016). This model is recursively defined as
node U2 (also known as the degree of v;)) is denoted by d: = E,Ar.. matrix where D,,; d; and 0 elsewhere. For what follows,
H = aD- AD- à (()).,
(1)
where A A+ is the adjacency matrix of the undirected graph G with additional self-loops, obtained by adding the identity matrix L, W((0) is a weight matrix associated with the (th layer of the model, and (-)) is some non-linear activation function. The notation H relates to the result of the 1th layer of the model, which is also the input to the + layer. The input to the first layer is E RVV We intend to accelerate the training and inference of this model by reducing the input size.
(0) = [xi,...,;pp1
3.2 LOCALITY SENSITIVE HASHING (LSH)
The Locality Sensitive Hashing algorithm is designed to approximate distances between vectors in high-dimensional space in lower dimensional space. It is widely applicable in fields like data mining and machine learning, and is particularly useful for tasks such as approximate nearest neighbors. This algorithm relies on the existence of family H of hash functions mapping E to some universe U. The definition of LSH is as follows.
Definition A family of hash functions H is called (R, c, P1, Pa) for any p, q E Rdd
d(p,g) S R = PREnT (h()) h(p)) 2 Pı.
d(p,g) 2 cR Phex h(p) Pz.
3

---

Under review as a conference paper at ICLR 2021
An interesting hash functions family satisfies the constraint that P1 > Pz. In work, utilize LSH by mapping feature vectors of graph edges into integers, namely "buckets", so that similar features mapped into the same buckets. Then, the hash of set of edges, consisting of edges in a neighborhood of node, is the bucket with the minimal hash value, which is referred as MinHash. When applied numerous sets, this process results with the same minimal buckets for similar edge sets. Consequently, by choosing to keep edges that correspond to the MinHash values, we aim to preserve the similarities of different graph regions.
LOCALITY SENSITIVE PRUNING
This section introduces the methodology of Locality Sensitive Pruning (LSP). Additionally, we pro- vide a complexity analysis of the algorithm and address its limitations. Finally, we discuss the advantages of pruning edges from graphs and the prominent advantages of LSP over other methods.
4.1 OVERVIEW
Our aim to modify the topology of a graph so that similar regions result in a similar, yet con- sistently sparsified structure. For this purpose, we base approach on locality sensitive hashing that assigns signatures to edges so that similar edges are assigned with the same signature. Then, specify MinHash as rule for choosing which edges to keep; that is, the edges that make up the sparsified graph. In MinHash, the selected edges correspond to signatures that are mapped to minimal hash values using pseudo-random hash functions. These psuedo-random hash functions used across all graph regions, and thus similar regions of the original graph result in similar regions in the resulting sparsified graph.
The procedure of sparsifying a graph using LSP is as follows. Given a graph -V,V, (V, LSP constructs new graph G' = (V, E') where E' C E. We assume every edge (i.j) E E is associated with an attribute Cij E Rd and the set of k rseudo-random functions H == (h E [k] h2 Rd - R} maps d-dimensional vectors into scalars under the locality- sensitive-hashing criteria (see Section 4.2 for more details on the choice of these functions). For each node E V. we compute the hash values for all the edges connecting u with its neighbors Nº - {o E V((uvv) E E}. Then, we base our choice edges using the MinIlash rule, that is, edges whose hashes are mapped to the minimal value among all the other edges. The overview of our sparsification method is described in Algorithm
Algorithm Locality Sensitive Pruning
Input: G 6=(V. -VV
The input graph H. [fh....,hhs) b A set of k sensitvve hashing (LSH) functions mapping edge
attributes scalars
Output: A sparsified graph G' = (V, F!)
F'
+ (
for V do
En + 0
for i [k] do
Umin + arg min h (2(Cu,))
Apply MinHash
E,, + E,, U {uu, Umin))
end for
E'
E' U En
end for
return G' (V,
Note that LSP assumes the existence of edge attributes. However, many real-world problems incor- porate only node attributes. In these cases, we construct edge attributes from the nodes connected to its ends, describe in Appendix A
4

---

Under review as a conference paper at ICLR 2021
4.2 THE CHOICE LSH FUNCTIONS
The description of LSP does not define a specific family of hash functions. This is because different datasets contain attributes with different nature. Consequently, this requires choosing appropriate hashing methodologies for each dataset. In the following, we present two common choices for hash functions that we use in our experiments (Section (5). We refer the readers (Paulevé et 2010) for review of other LSH function choices.
Binary signatures A LSH function that uses binary signatures is composition h = 1z2 o h1 of a binary signature mapping h1 R {0, 1]d and hashing functions h2 10 N that maps binary signatures to integers. Specifically. we define h1 as thresholding function which is associ- ated with a random vector w (with each w; ~ [0, 1)) that determines the threshold for each entry of an input vector z. Formally, the thresholding is performed by comparing the entries of z and w:
f1: 34 w/ 0. otherwise
h1 (z);
Then, h2 maps the result to integers using the well-known message-digest algorithm (Rivest 1992) and bin it into of m bins by finding the remainder of the division by m. In our experiments (which will be presented in Section 5), we refer to this method as LSP T
Random Projections LSH hashing function that uses random projections (Shakhnarovich et al. 2008) aims to project inputs that similar vectors result in proximate projections, and their quan- tization result the same values. Let w be some random vector with each w; ~ (N,0 1). This random projection divides input vectors into bins of length using the hash function defined by
(x, w) + b
1
Here, b is random variable sampled from the uniform distribution U J.. The inner-product (a, w) is the projected value of x onto the direction w, which is then shifted by the offset value b and quantized into length bins. In our experiments, we refer to this method as LSP P.
4.3 ANALYSIS
Complexity The procedure of LSP performed as preprocessing step prior the whole training phase due to its determinism. The pruned graph does not change between training episodes and thus should be performed only once, Assuming the dimensionality of each edge attribute is d, the complexity of computing each hash value is (dd given that the hash function families proposed in Section 4.2 are used (note that this statement is valid for other common hash function families). Each of the hash functions computers EE hash values, one for each edge. In total, the running time complexity of L.PP (k: E)d. The space complexity is ((1), because this only requires iterating over edges and keeping the minimal hash value, which requires constant amount of memory.
Limitations We base L.P on the assumption that the topology of the input graph plays signif- icant role in the learning procedure. For this reason, in problems where the graph topology less meaningful, we do not expect significant advantage of pruning using LSP over its rival, such as random removal of edges.
4.4 BENEFITS OF USING LSP
In the following, we present the beneficial reasons for pruning edges. While many claims are valid in general, that is, they are applied to other pruning methods other than LSP, we begin with advantages that are particular for LSP.
4.4.1 ADVANTAGES OF PRUNING USING LOCAL ENVIRONMENTAL CHARACTERISTICS
Several graph-related tasks, including code-classification among them, rely on the composition of the neighborhoods. This results from the core methodology of GCNs which aggregates information
5

---

Under review as a conference paper at ICLR 2021
from node's local environment. Consequently, want our pruned graph preserve local prop- erties of the original graph. For demystifying the necessity to specifically consider local properties for pruning, exemplify a node classification scenario in which consistent pruning that preserves similarities between neighborhoods is necessary for successfully predicting the node classes.
This example is illustrated in Figure 2 Consider node classification scenario sisting of classes. The criterion for a node to belong to class is being a neighhor of both nodes 1,4 E V. Similarly, the criterion for node to belong to class 2 is being neighhor of both nodes 2, E V. Notice that for each environment on the left, there's 's corresponding environment on the right which has least 2 common neighbors. For example, the top left environment contains nodes 8 and 20 as neighbors of F, while on the right we have nodes 8 and 20 as neighbors of B.
Example 2
Suppose that we want to reduce the degree of every node by 50%. When performing consistent pruming by choosing to keep the nodes corresponding to minimal identity (in our algorithm,, these are the hash values) we encounter the following situation: on the left, we are left with environments consisting of nodes F,, F, G, H, each of which has two neighbors and 4. On the right, we are left with environments consisting of nodes A, B, C, D, each of which has two neighbors 2 and These results will enable to train classifier that distinguish between the depicted components.
Meanwhile, suppose that we randomly prune 50% of the edges of each node, Since there are (2) = 6 possibilitiies the probability that we are left with environments consisting of nodes and 20 both on the left and the right is (t)²²
36 Consequently, a classifier trained on randomly pruned graphs
using the described settings would have an error rate of 2.7%.
Class EPE VIL4 Ni.)
Class (M VI2.3
20
Figure 2: Example scenario which we are tasked to classify nodes into 2 classes. Each of the nodes A, B, C, D belong class 2, while each of the nodes E, F, G, H belong to class Moreover, For each node among {E, F, H, G} there exists a node among {A, B, DJ that the intersection of the sets of their neighbors has size of least 2.
4.4.2 OTHER ADVANTAGES OF PRUNING EDGES OF A GRAPH
Accelerating GCN training and inference The outcome of pruning edges from a graph is an acceleration of each training iteration. To see this, recall the recursive definition of GCN (Equation mh from Kipf & Welling 2016). In this definition, the weights matrix W is of size C' x F where C. and F denote the number of input channels and filters respectively. Additionally, the matrix D is diagonal matrix of size [V| [V] with at most [V] non-zero elements, and the matrix A is of size [V] x [V] whose number of non-zero elements is at most FE.- Apparently, the complexity of this matrices multiplication does not depend on the number of edges, however from Kipf & Welling 2016) we know that in practice ÄH is efficiently implemented as product of a sparse matrix with a dense matrix whose complexity is linear in the number of edges FC). For GCNs that uses an attention mechanism, from Veličković et al. (2017) know that the time complexity of single attention head is O[VICF + FE.... With this, we claim that pruning edges from an input graph linearly accelerates GCNs and their variants.
Mitigating Squa-Shua LSP simplifies the graph structure by removing edges. In turn, reduces the amount of information needed to be encoded within the node representation vectors. Particularly, pruning of edges helps mitigating the over-squashing phenomenon in which informa- tion from the pnoonentially-growin receptive field is compressed into fixed-length node vectors

---

Under review as a conference paper at ICLR 2021
AAlon & Yahav 2020). Since removing edges reduces the degree of each node, it also reduces its receptive field exponentially, thus preventing this destructive phenomenon.
We further discuss the Neighborhood Variance issue in Appendix C
EXPERIMENTS
We validated LSP on 3 graph-related tasks: (1) Node classification; (2) Graph regression, and (3)
Graph classification. The objectives of this empirical study were twofold:
Assess the quality of the pruned graphs in terms of performance metries. We train and test several models on various datasets and configurations, and measure the achieved perfor- mance metric identified with each dataset as dependent of the pruning configurations.
As we target acceleration of GNNs, we assess the amount of acceleration obtained by train- ing and testing with pruned graphs. This is done by measuring the relative time required for training and testing on graphs that are pruned with various pruning configurations.
For all the experiments discussed in this section, for each dataset choose commonly used model that is identified with this dataset. For example, we use the GAT (Veličković et al. (017) architecture proposed for the PPI (Zitnik the-art performance at the time of writing this paper. We refer the readers to Appendix [B.3 for more information about the models that we use for experimenting with each dataset. Additional implementation details are given in Appendix[B. B.
Leskoved (017)) dataset because achieves state-of-
Evaluation Protocol To evaluate the quality of the pruned graphs, we train and test models with various pruning configurations and evaluate their performance in terms of the metric identified with each dataset. Additionally, we measure the running times order to demonstrate the relative ac- celeration achieved via pruning. These results are presented the relative time required for each iteration compared to the model trained on the unpruned graph. It is important to note the obser- vation that given a pruning ratio, the choice of pruning methodology does not impact the running times, thus we present single curve that describes the acceleration for all pruning methods.
Baselines We compare the performance of 2 LSP variants (see Section 4.2) with Random, that relates to the method which randomly removes edges from graph with certain probability p. We do not compare LSP with methods that sparsify the input graph during inference, such as FastGCN (Chen al. 2018) and DropEdge (Rong et al., 2019), which discussed in Section 2 This is because LSP does not modify the training and inference phases of GNNs, as opposed to the afore- mentioned methods. Additionally, in order demonstrate the advantage of using the combination of L.P with complex models over using simpler GNNs which are computationally cheaper in terms of acceleration, we compare the performance of these models with various pruning configurations against a basic GCN that is naturally computationally cheaper (described in Appendix B.3
5.1
NODE CLASSIFICATION BENCHMARKS
Data
We experimented with various publicly available datasets: GitHub (Rozemberczki et al.
2019).
Cora (Bojchevski & Günnemann 2017), CiteScer (Bojchevski & Günnemann [2017).
PubMed (Bojchevski & Günnemann (017)) and PPI (Zitnik & Leskovec 2017). Detailed descrip- tions and statistics of these datasets presented in Appendix B.2
Results Results for node classification benchmarks are shown in Figure 3 Additional results are provided in Appendix C.3] The superiority of LSP is demonstrated through the experiments conducted on Cora and PPI. For these benchmarks, the predictive performance drops significantly for aggressively pruned graphs via random, while is noticeable that LSP better preserves the accuracy of the model trained the original graphs. Moreover, the basic models used for these experiments demonstrate a significant decrease in performance while the acceleration achieved by their simplicity is negligible. Notice that for PubMed and CiteSeer, the accuracy ranges are narrow. For instance, the model trained on PubMed using 100% of the edges achieves an accuracy score of 0.882, while the same model that is trained with 30% of the edges using random pruning achieves

---

Under review as a conference paper at ICLR 2021
accuracy score of 0.859. Considering this relatively negligible difference. observe that random pruning performs well and consistent pruning via either LSP-P or LSP-T preserves this performance. Additionally, for this experiment the basic model demonstrates performance that is comparable to the original model while being substantially faster. The same holds for CiteSeer.
To that end, conclude that in where random pruning performs well, the graph topology has a negligible impact on the performance of the model. In these cases LSP performs marginally better than random. The superiority of LSP well-demonstrated in benchmarks where the topology of the graph is impactful. In such cases, the performance of the models reduces significantly via random pruning. while pruning via an LSP variant preserves the local properties of the graph. To conclude this experiments series, we observe that the achieved inference acceleration is linear in the number of preserved, result that matches our expectation as per our complexity expectations.
Cora
PubMed
Normalized Time
Normalized Time
Accuracy
Accuracy
0.88
0.85
0.8
0.8
0.87
0.8
0.6
0.6
0.86
0.75
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
% Edges (-100)
% Edges (-100)
CiteSeer
PPI
Nornalized Time
Normalized Time
Accuracy
0.78
micro-FI
0.8
0.8
0.8
0.76
0.6
0.6
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
1
% Edges (-100)
% Edges (-100)
Random
LSP-P
LSP-T ...... Relative Testing Time * Basic (Metrie) p Basic (RTT)
Test results for node classification problems. For each dataset, report the results in terms of the metric identified with that dataset (in solid lines), and the running time per iteration (in densely dotted lines) under the specified pruning configurations.
Figure 3:
5.2 GRAPH REGRESSION BENCIMARRS
Data We experimented with datasets from the chemical world with the goal predict chemical properties of molecules: QM9 (Wu et al. (017)) and ZINC (Sterling & Irwin 2013). In both datasets, each graph a molecule, consisting nodes and edges that represent atoms and different types of bonds between the atoms respectively. The goal is to regress each graph to its properties, quantum properties in QM9 and constrained solubility (a synthetic computed property) in ZINC. Refer to Appendix B. for more details of these datasets.
Results for the graph regression tasks are shown in Figure include additional results for other QM9 targets in Appendix [ Continuing the conclusions from the previous section, we observe that pruning via LSP perform better in terms of lower Mean Absolute Error (MAE) for both graph regression benchmarks.
Results
5.3 GRAPH CLASSIFICATION BENCHMARKS
Data In order to validate the effectiveness of LSP in extreme scenarios, we developed a generator for synthetic graph classification datasets. We provide the full list of parameters and their default values of this generator in Appendix(B.22) [.2. We refer to the default generator configurations as those which in the following experiments.
8

---

Under review as a conference paper at ICLR 2021
constrained solubility
Normalized Time
-10
Normalized Time
3.4
MAB
0.8
0.6
0.9
0.95
MAE (D)
3.2
3
0.8
2.8
0.85
0.2
2.6
0.2
0.4
0.6
0.8
0
0.2
0.4
0.6
0.8
% Edges (-100)
% Edges (-100)
(a) ZINC
(b) QM9
Random
1.SP-P + I.SP.T .....* Relative Testing Time
Figure 4: Mean Absolute Error (MAE) and normalized running times for graph regression problems. 44) results for regressing the constrained solubility for molecules in the ZINC database. (4b) results for regressing the Dipole moment (μ) for molecules in the QM9 database. Errors are presented as solid lines (Lower better). Normalized running times are presented dashed lines.
Results Results for graph classification the synthetic benchmark are shown in Figure 5
Normalized Time
This synthetic data generator enables us sim- ulate highly complex scenarios where the topol- ogy is impactful. This is well-demonstrated by the aggressive accuracy reduction when prun- ing with random. This yields the observa- tion that LSP outperforms the random pruning method by a large margin, especially for mid- range pruning ratios. Moreover, we use highly complex model in this section (as de- scribed in Appendix B.3) that performs com- plex calculations for neighborhood aggrega- tion, significant acceleration is observed when compared to the model trained on the original graphs. Additionally, this acceleration is depicted linear curve, which matches expectations. The basic model used for this experiment (described in Appendix (B.3.4) demonstrates significant acceleration due the lack of need compute 16 attention heads per layer. This acceleration also followed by a reduction of ~ 54% in accuracy: the original model trained on the original graphs achieves an accuracy score of 90.76% while the basic model achieves an accuracy score of 34%. For the sake of comparison, the original model trained on pruned graphs with the configuration that achieves comparable acceleration results in accuracy score of 76% for both LSP variants. In this configuration, nearly 45% of the graph edges are pruned. From this result, we conclude that we were able to train highly complex model that does not compensate for the performance while being accelerated via pruning its input.
0.8
0.8
Accuracy
0.6
0.6
0.1
0.4
Random
L.PPP
LSP-T Rosic (RTT)
0
RTT
Rosic (Metric)
0
0.2
0.4
0.6
0.8
% Edges (-100)
Figure 5: Accuracy and running time comparison for the synthetic graph classification dataset.
6 CONCLUSIONS
We have presented Locality Sensitive Pruning (LSP), systematic method for pruning graphs based on locality sensitive hashing. By relying on the local features of neighborhoods. LSP preserves local properties of the graph. Consequently, it does not impair the ability distinguishing between samples that were distinguishable prior to the pruning process with high probability. We evaluated LSP through extensive experimental study on graph-related tasks. For these experiments, trained several ad-hoe graph neural networks on diverse real-world datasets that went through the pruning process of 2 LSP variants. In all experiments, LSP demonstrates superior performance when compared to the baselines. At the same time, the reduction in the number of edges translates significant acceleration of the used models, which linear in the number of edges. possibly rewarding avenue of future research is the design of dedicated locality sensitive hash functions that capture informative features of the graph.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. arXiv preprint arXiv:2006.05200 2020.
Andras Benezur and David Karger. Randomized approximation schemes for cuts and flows in capacitated graphs. arXiv preprint cs/0207078, 2002.
Smriti Bhagat, Graham Cormode, and S Muthukrishnan, Node classification in social networks. In Social network data analylics, pp. 115-148. Springer, 2011.
Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsuper- vised inductive learning via ranking. arXiv preprint 1rXiv:1707.038155 2017.
Hongyun Cai, Vincent W Zheng, and Kevin Chen Chenn Chang. A comprehensive survey of graph embedding: Problems, techniques, and applications. IEEE' Transactions Knowledge and Data Engineering, 300))1616-1637, 2018.
Daniele Calandriello, Alessandro Lazaric, Ioannis Koutis, and Michal Valko. Improved large-scale graph learning through ridge spectral sparsification. In International Conference on Machine Learning. pp. 688-66 698. PMLR, 2018.
Hao Chen, Yue Xu, Feiran Huang, Zengde Deng, Wenbing Huang, Senzhang Wang. Peng He, and Zhoujun Li. Label-aware graph convolutional networks. Proceedings of the 29th ACM Inter- national Conference Information & Knowledge Management, pp. 1977-1980, 2020.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling. arXiv preprint
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 decom- positions. SIAM Journal on Computing, pp. FOCS18 2020.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. arXiv preprint arXiv:2004.05718, 2020.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.00982 2020.
Lukas Faber, Yifan Lu, and Roger Wattenhofer. Should graph neural networks use features, edges, or both? arXiv preprint S.3i::2033.0887: 2021.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. 2019.
arXiv preprint
Rafael GómezzBombarelli, Jennifer N Wei, David Duvenaud, José Miguel Hernández-Lobato, Benjamín Sánchez- Lennchei-Lengeling.. Dennis Sheberla, Jorge Aguilera-Iparraguirre Timothy Hirzel, Ryan P Adams, and Alán Aspuru-Guzik. Automatic chemical design using data-driven contin- uous representation of molecules. ACS central science, 4(2):268-276, 2018.
William I. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 1025-1035, 2017.
Arman Hasanzadeh, Ehsan Hajiramezanali, Shahin Boluki, Mingyuan Zhou, Nick Duffield, Krishna Narayanan, and Xiaoning Qian. Bayesian graph neural networks with adaptive connection sam- pling. In International conference on machine learning, pp. 4094-4104. PMLR, 2020.
Pili Hu and Wing Cheong Lau. A survey and taxonomy of graph sampling. arXiv preprint
arXiv: arXiv:/308.55 1308.38888600 2013.
Christian Hübler, Hans-Peter Kriegel, Karsten Borgwardt, and Zoubin Ghahramani. Metropolis algorithms for representative subgraph sampling. In 2008 Eighth IEEE International Conference Data Mining, pp. 283-292 2008. doi: 10.1 (09/CCDM.2000 124.
10

---

Under review as a conference paper at ICLR 2021
Dongkwan Kim and Alice Oh. How find your friendly neighborhood: Graph attention design with supersuuer In International Conference on Learning Representations, 2020.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net-
works. arXiv preprini arXiv: 1609.02907 2016.
Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. arXiv preprint arKiv:2001.0444 2020.
Johannes Klicpera, Janek GroB, and Stephan Günnemann. Directional message passing for molec- ular graphs. arXiv preprint arXiv:2003.031 2020.
Nils M Kriege, Fredrik D Johansson, and Christopher Morris, A survey on graph kernels. Applied Network Science, 5(1):1-42, 2020.
Ajay Kumar, Shashank Sheshar Singh, Kuldeep Singh, and Bhaskar Biswas. Link prediction tech- niques, applications, and performance: survey. Physica A: Statistical Mechanics and its Appli- cations, 124299,, 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.
Dongsheng Luo, Wei Cheng, Wenchao Yu, Bo Zong. Jingchao Ni, Haifeng Chen, and Xiang Zhang. Learning to drop: Robust graph neural network via topological denoising. In Proceedings of the 14th ACM International Conference Web Search and Data Mining, pp. 779-787, 2021.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32: 0026-8037, 2019.
Loic Paulevé, Hervé Jégou, and Laurent Amsaleg. Locality sensitive hashing: comparison hash function types and querying mechanisms. Puttern recognition letters, 31(11)11348-1358 2010.
Ronald Rivest, Rfc1321: The md5 message-digen digest algorithm, 1992.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. arXiv preprint 1rXiv: 2019.
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. (2019). arXiv preprint Ls.999 1101119/999.111, 2019.
Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Nenworks, 9())cnab011, 2021.
Veeru Sadhanala, Yu-Xiang Wang, and Ryan Tibshirani. Graph sparsification approaches for lapla- cian smoothing. In Artificial Intelligence and Statistics, pp. 1250-1259, PMLR, 2016.
Gregory Shakhnarovich, Trevor Darrell, and Piotr Indyk. Nearest-neighhor methods learning and vision. IEEE Trans. Neural Networks, 19(2):377, 2008
DA Spielman and N Srivastava. Graph sparsification by effective resistances. corr abs/0803.097 (2008), 2008
Daniel A Spielman and Shang-Hua Teng. Spectral sparsification of graphs. corr, abs/0808. 4134, 2008. arXiv preprint arXiv:0808.411 4134, 2008.
Rakshith Srinivasa, Cao Xiao, Lucas Glass, Justin Romberg, and Jimeng Sun. Fast graph attention networks using effective resistance hased graph sparsification. arXiv preprint arXiv:2006.088) 08796, 2020.
Teague Sterling and John J Irwin. Zinc 15 ligand discovery for everyone. Journal of chemical information and modeling, 55(11 (1:12))22--3333 2015.

---

Under review as a conference paper at ICLR 2021
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998--008, 2017.
Petar Veličkovié, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:/710. 1700//03300.003 2017.
Z Wu, B Ramsundar, EN Feinberg, J Gomes, C Geniesse, AS Pappu, K Leswing, and V Pande. Moleculenet: a benchmark for molecular machine learning. arxiv e-prints. arXiv preprint arXiv:1703.00564 2017.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 32(1))4-24, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanic Jegelka. How powerful graph neural 2018.
networks? arKiv preprint
Yang Ye and Shihao Ji. Sparse graph attention networks. IEEE Transactions on Knowledge and Data Engineering, 2021.
Daokun Zhang, Jie Yin, Xingquan Zhu, and Chengqi Zhang. Network representation learning: A survey. IEEE transactions on Big Data, 6(1):3 28, 2018.
Shuo Zhang, Yang Liu, and Lei Xie. Molecular mechanics-driven graph neural network with multi- plex graph for molecular structures. arXiv preprint arXiv:2011.077 1.07457, 2020.
Cheng Zheng, Bo Zong, Wei Cheng, Dongjin Song, Jingchao Ni, Wenchao Yu, Haifeng Chen, and Wei Wang. Robust graph representation learning via neural sparsification. In International Conference on Machine Learning, pp. 11458-1 1468. PMLR, 2020.
Marinka Zitnik and Jure Leskovec. Predicting multicellular function through multi-layer tissue networks. Bioinformatics, 33(1 33114)1190--1198 2017.
A CONSTRUCTION OF EDGE ATTRIBUTES
As discussed in Section LSP assumes the existence of edge attributes. However, many graph datasets do include such representation but include node attributes instead (or additionally). Additionally, some datasets have scalar values as edge and node representations (for instance, molecules with number of bonds as edge attributes and atomic number as node attribute). Those representations cannot be used as inputs to our hash functions because they expect vectors as input rather than scalars. Here we describe our choice of representation in each case.
Recall the definition of edge attributes from Section 4 an attribute of an edge (u, v) E F. is a d-dimensional vector denoted as Cu, E Rdd Similarly, an attribute of node u E V a q- dimensional vector. For convenience, we use the name of node itself as notation for its attribute. We denote the final representation of an edge attribute which serves as an input to the LSP algorithm LSP
as c,,e
Node attributes only -u,vv
[u,y]. v].
Both node and edge attributes - LSP = [u, Gu,0s v).
uu,
Scalar node/edge attributes -L.tt E N be an attribute of node or edge (for example, atomic number or number of bonds between atoms in graphs that represents molecule). Assume accepts possible values, {O...., the columns M as embeddings of the corresponding component; that is, the nh column of is the corresponding feature vector of the graph component associated with the attribute r.
1). We generate random matrix M mmmxm and use
Example 3 We finalize this section with complete example of constructing edge attributes from a graph G = (V, E) representing a molecule. We assume every node v V is associated with natural scalar r. E (0,... my 1} and every edge e. F. is associated with natural sealar mo,
12

---

Under review as a conference paper at ICLR 2021
[O....,m: 1}. Following explanation for generating embeddings for scalar attributes, we generate two random real matrices, My E Rm xmy and Mg E Rm Then, the columns of each matrix are used feature vectors of nodes and edges follow. Let M' denote the tth column of a matrix M. Then, following our explanation for constructing edge representations as imput for I.PP, given two nodes u, E V and edge connecting the two nodes e, obtain the following: LSPP
cu,0
MM ME M M
B EXPERIMENTS
B.I DETAILS
Implementation Details All experiments were run on Ubuntu 18.04 machine with Intel 19- 10920X CPU, 93GB of RAM and 2 GeForce RTX 3090 GPUs. Our implementation of L.P is in Python To generate graphs and perform training of graph neural models, we use Pytorch- Geometric (Fey & Lenssen 2019) and use Pytorch (Paszke et 2019). Moreover, we all datasets used this section are retrieved from the collection supplied by Pytorch-Geometric.
B.2 DATASETS
B.2.1
SYNTHETIC GRAPH DATASET GENERATOR
Here, we introduce the synthetic graph classification dataset generator. Table [ summarizes the parameters used for the synthetic data generation and their default values, which we use for our experiment described in Section 5.3
Table I:
Parameters of the synthetic dataset generator. For each parameter introduced in this table,
the default parameter denotes the value that we use for our experiments in Section 5.3
Parameter
Description
Default
Number of samples
The number of graph instances in the dataset
20,000
Number of classes
The number of classes in the dataset
100
Minimum nodes
Minimum number of nodes in each graph sample
40
Maximum nodes
Maximum number of nodes in each graph sample
60
Node dimension
Dimensionality of the node representation vectors
10
Edge dimension
Dimensionality the edge representation vectors
40
Connectivity rate
Degree of each node
0.2
Node centers std
Scatter of the node representation vectors
0.2
Edge centers std
Scatter the edge representation vectors
0.2
Node noise std
Amount of additive noise for node representation vectors
0.25
Edge noise std
Amount of additive noise for edge representation vectors
0.1
Is symmetric
Whether to enforce symmetry on each graph
False
Node removal probability
The probability of remove node from graph sample, after the graph is initally generated
0.1
B.2.2 REAL-WOO WORLD DATASETS
Here, we describe the various real-world datasets used in this paper for different tasks.
Node Classification
GitHub A social network where nodes correspond to developers who have starred at least 10 repositories and edges to mutual follower relationships. Node features are location, starred repositories, employer and e-mail address. The task is to classify nodes as web or machine learning developers.
13

---

Under review as a conference paper at ICLR 2021
Cora, CiteSeer and PubMed These citation network with labels of paper topic. Each node represents a publication corresponding to different class (seven classes for Cora, classes for CiteSeer and 3 classes for PubMed). The citation network consists of links representing citations. In Cora and CiteSeer, each publication in the dataset is described by 0/1-valued word vector indicating the absence/presence of the corresponding word from the dictionary. In PubMed, each publication in the dataset is described by a TF/IDF weighted word vector from dictionary which consists of 500 unique words.
This dataset is made up of 24 graphs, with each graph corresponding to different human tissue. Each node represents a protein and associated with features made up of motif gene sets and immunological signatures. The task is to classify each protein into gene ontology sets (121 in total).
PPI
Statistics for these datasets are shown in Table 2
Table 2: Node Classification Datasets Statistics
Dataset
Github
Cora
CiteSeer
PubMed
PPI
Number nodes
37700
2708
3327
19717
44906
Number of edges
578006
10556
9104
88648
1136460
Number of classes
2
6
3
121
Average degree
30
5
8
50
Graph Regression
QM9 The Quantum Mechanics 9 database contains around 130k small organic molecules with up to 9 heavy atoms and their physical properties in equilibrium, computed using den- sity functional theory calculations. Following previous works (Zhang et al. 2020 Klicpera et al., 2020), we randomly sample 1 10k molecules for training, 10k for validation and the rest for testing. Results are presented in terms of Mean Absolute Error (MAE).
ZINC A collection of chemical compounds prepared especially for virtual screening. In this collection, a graph represents a molecule, with node features indicating the atom type and edge features the type of chemical bond between two atoms. The goal to regress the molecule's penalised water-octanol partition coefficient. We use the original train/validation/test splits from Geometric (Fey & Lenssen 2019). In similar to Dwivedi et al. (2020). we randomly select 12K for efficiency.
et al. (2018) as provided in Pytoreh-
B.3 MODELS
As stated in Section 5 the state-of-the-art model identified with each dataset to compare performance of LSP with other baselines. In the following, we provide descriptions of these mod- els. After introducing these models, present the basic architectures used as baselines for experiments.
B.3.1 NODE CLASSIFICATION
GitHub GAT model used in the comparisons in (Rozemherczki et al. 2021). This model consists of attention layers that aggregate information up 2-hop neighbourhoods with 1 attention head. For non-linearities we used leaky rectified linear unit (Leaky ReLU) with negative slope of 0.2.
Cora, CiteSeer and PubMed We use the methodology introduced in GraphSage (Hamil- [on et al. 2017) in combination with GAT, which has 2 layers. Following GraphSage, we sample at most 10, 15 neighbors for the first and second hop respectively for training. For testing, we sample the whole neighborhood of node. The first layer has attention heads, where each attention result has hidden size of 8 and concatenated to the others. The sec- ond layer, which is used for calculating the output has attention head. We use exponential linear unit (ELU) activation between the layers.
14

---

Under review as a conference paper at ICLR 2021
PPI GAT model with 3 layers from Vaswani et al. (2017). The hidden dimension of each layer 256 and the number attention heads each layer is 4,4,6 for the first, second and third layer respectively. For non-linoenn con-lincarities we used exponential linear unit (ELU).
B.3.2 GRAPI REGRESSION
QM9 For all experiments,
the MXMNet architecture proposed in (Zhang al. with best performing configurations presented in the original paper.
2020
ZINC We use the PNA architecture (Corso et al. 2020) with its default settings.
B.3.3 GRAPH CLASSIFICATION
Synthetic dataset- We construct GAT model with 3 layers with 16 attention heads each. The hidden size of the intermediate layers is 40. The first layers concatenate the out- puts of the attention heads for output vector of size 40 - 16 = 640. For non-lincarities, we apply ReLU between every two consecutive layers. Then, order to perform the final clas- sification, we average the the result of the third attention layer and aggregate the obtained node representations using global mean pooling. The result is later fed into dropout layer which cancels 50% of the activations. Finally, we feed the result into linear layer which provides the final prediction the model.
B.3.4 BASIC MODELS
The basic models used baselines demonstrate the mene-eerformncee trade-off via training compu- tationally cheaper models that deliver less performance when compared to computationally exten- sive models trained on pruned graphs. As we use GATs (Veličković et al. 2017) all experiments of node-classification and graph classification, the basic models for these experiments are created by removing the attention mechanism while keeping all the accompanied configurations as is. As result, we obtain GCN (Kipf& & Welling 2016) variants variant of the original models that aggregate messages from neighboring nodes by averaging instead weights computed via attention heads.
C REDUCING THE NEIGHBORHOODS VARIANCE
The depth of node's neighborhood determines the maximal path length between node and other nodes contained in its neighborhood. A neighborhood of depth k is called k-hop neighborhood. As we increase the depth the neighborhoods, the number of nodes contained within the neighbor- hoods increases. However, not all neighborhoods increase in the same way, which in turn leads to variable size of neighhorhoods a phenomenon we call Neighborhood Variance, as exemplified in Figure 6 For the two given nodes U1, U22 their 3-hop neighhorhoods have different sizes, which in turn translates to a variable amount of information that has to be encoded within a fixed-length code.
To see this, measure the amount of nodes reachable within & hops for each node graph G, denoted as Ak. We claim the following:
Proposition 4 (Pruning edges for reducing prevents over-squashing) Let G (V,E) be graph and consider a sparsified version G' (V, E') so that E' C E. For each v E V, denote by No. sk.o the set of nodes reachable from within l hops in the graph G. Then, there exists kmaz E N so that for all & S kimaz the variance of the amount of neighboring nodes needed to be encoded into the representation vector of node satisfies:
Var(INa < Var(INaMM.
Suppose that a k-layer GCN (for h S kmmz)) is trained to solve task by aggregating information from k-hop neighborhoods into node representations. Then, from Proposition 4 we know that the neighborhood size of each node in the pruned graph has less variance and thus similar amount of information has to be encoded within the representation vector of each node. Consequently, over- squashing is avoided. To demonstrate the scope of this phenomenon, provide statistics about neighborhood size variance from popular real-world datasets in Appendix C.T Additionally, we justify Proposition 4 Appendix
15

---

Under review as a conference paper at ICLR 2021
C.1 NEIGHBORHOOD VARIANCE IN WWRLD GRAPHS
Figure 6 depicts this variance for various neighborhood depths and pruning settings for certain datasets. For all datasets, observe an exponential upward trend in the variance of the neigh- borhood sizes as more edges are incorporated in the graph for certain values of neighborhood depths (k). Additionally, an increase in the depth of the neighborhood (higher & values) leads signif- icant increase in this variance, which explains the performance degradation of deep GCNs due to over-squashing. This verifies our conclusion from Proposition for real-world scenarios.
CiteSeer
Cora
PubMed
Var( ))
220
220
Var( Var( (War
Var( (aak))
2
240
24
29
20
20
0
0.2 0.4
0.6 0.8
0
0.2 0.4
0.6 0.8
0.2 0.4 0.6 0.8
% Edges (-100)
% Edges (-100)
% Edges (-100)
k=5 - k=
k=9
Figure 6: Variance of neighborhood sizes function of edge percentage preserved from the orig- inal graph (Log scale).
C.2 JUSTIFICATION OF PROPOSITION 4
This claim is true for kmaz 1, thus proving its existence:
The size of the 1-hop neighborhood of equals the number of edges connected to it. Assuming the ratio of preserved edges in the pruned graph G' is 0 S p < 1, we have:
Var(W Var(der Eldo (v)
Eldo (v))²=
Elpp do(v)) (ip-da(v)]
"dp"'do(u) Elp do(u))²
x². (lda(v) - FF-(d(()))== = p2 -f -
Fldo(v))3)=
= p² VVr(dc(e)) s Var(da(v)) Var(WW
C.3 ADDITIONAL RESULTS
C.4 NODE CLASSIFICATION
Additional results for node classification benchmarks presented in Figure
7
Github
0.87
Normalized Time
Accuracy
0.87
0.8
0.86
0.6
0
0.2
0.4
0.6
0.8
% Edges (-100)
Random
LSP-P
LSP-T Relative Testing Time
Figure 7: Additional results for node classification problems. We report the results terms of the metric identified with the dataset (in solid lines), and the running time per iteration (in densely dotted lines) under the specified pruning configurations.
16

---

Under review as a conference paper at ICLR 2021
C.5
GRAPH REGRESSION
Prediction results for all QM9 targets are presented in Figure g
Normalized Time
a
Normalized Time
10
110 2
MAB (D)
3.2
3.4
MAE (ai)
4.9
0.9
2.8
2.0
0.6
4.7
0.85
0.8
0.2
0.6
0.2
0.6
% Edges (-100)
% Edges (-100)
Normalized Time
ELUMO
Normalized Time
MAE (meN
MAE (meV
24
19.6
0.8
19.4
0.8
23.5
19.2
23
0.6
19
0.2
0.4
0.6
0.8
1
0.2
0.4
0.6
0.8
% Edges (-100)
% Edges (-100)
(R²²)
Normalized Time
Normalized Time
MAE (meV
6.4
-10
2
MAE (a
0.12
6.2
0.11
0.9
0.1
5.8
0.6
0.7
5.6
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
% Edges (-100)
% Edges (-100)
ZPVE E
Normalized Time
Up
Normalized Time
MÁE (meV)
-10
MAE (meV)
G
0.9
0.9
8
0.8
0.8
0.7
3.5
0.6
0.6
0.2
0.4
0.6
0.8
1
0
0.2
0.4
0.6
0.8
%
Edges (-100)
% Edges (-100)
U
Normalized Time
Normalized Time
MAE (r
MAE (in)V)
1
10
0.9
0.8
0.8
0.7
OF
0.7
0.6
-1
0.6
0
0.2
0.4
0.6
0.8
1
0.2
0.4
0.6
0.8
Edges (-100)
%
Edges (-100)
G
Normalized Time
C.
Normalized Time
MAE (mee)
20
2
MAE col
0.9
0.8
10
0.7
0.6
0.6
0
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
1
Edges (-100)
% Edges (-100)
Random
LSP-
LSP-T sanena Relative Testing Time
Figure 8: MAE and normalized running times for additional QM9 targets. Errors are presented as solid lines (Lower is better). Normalized running times presented dotted lines.
17


Reviews:
[{"review_id": "iPJqcVXk74N", "reviewer": "Reviewer_HFfr", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "**Pros**:\n- Graph sparsification is an important and interesting problem due to the high computation complexity of GNNs.\n- Based on the discussion in the related work section, the proposed LSP is novel for graph sparsification. Besides, the idea of using  Locality-Sensitive Hashing makes sense to me.\n- The experiment section is well structured. It’s nice to see the authors evaluate the performance of the model on different underlying tasks.\n\n**Cons**:\n- **Novelty (main concern)**. Local Sensitive Hashing (LSH) has been used in Transformers to sparsify the fully connected self-attention computation graph in Transformer. LSP seems like a straightforward application from NLP to graph domain. From this paper, it is not clear why applying LSH to graph neural network is the challenge. \n- **Motivation**. The author motivates the LSP using two limitations of existing GNN models in Section 1: (1) computation complexity and (2) varying neighborhoods (i.e., varying number of nodes participating in the node’s neighborhood leads to varying amounts of information to encode within a fixed-length code). It is not clear why varying neighborhoods will hurt the performance of GNN. To support their claim, the authors provide a discussion on the importance of reducing the variance of the neighborhood size in Appendix C, which is not convincing. In particular, in Appendix C, the authors argue that “by reducing the variance of the neighborhood size of each node can avoid over-squashing” which is not true because “over-squashing” is only relevant to the neighborhood size but irrelevant to the neighborhood size variance. On the other hand, the relative difference in neighborhood size can be important information to distinguish two nodes when using the forward propagation rule as defined in Eq. 1 since the aggregation weight is 1/\\sqrt{deg(i)deg(j)}, which take the node degree information into considerations.\n- **Experiment**. This paper lack enough comparison to baseline methods to indicate the effectiveness. The authors only compare with Random sampling-based sparsification methods: FastGCN and DropEdges. However, there are existing neural network-based deterministic graph pruning/sparsification methods that need to be compared. For example [1,2] as already cited by the authors and missing related works [3]. Besides, even for random-based methods, a stronger/more recent baseline such as neighbor sampling (e.g., GraphSAGE [4]), layerwise sampling (e.g., LADIES [5]), and subgraph sampling (e.g., GraphSAINT [6]) are expected to be compared since they are reported with better accuracy than FastGCN and DropEdges. More importantly, from the experiments section, LSP is still sacrificing performance a lot. For example, in Figure 3 (Cora), even just removing 20% edges, there is already around a 2% performance drop, the number continuously increasing as fewer edges are used. The same also happens to other datasets.\n- **Clarification**. This paper is a Local Sensitive Hashing (LSH)-based sparsification algorithm, but LSH is not well introduced and is a little bit confusing. For example, in Section 3.2 Definition 1, the authors use notation d for both dimensions (e.g., p,q \\in \\mathbb{R}^d) and distance measure (e.g., d(p,q)). Besides, what are P1, P2? The authors are suggested to spend more effort on introducing the LSH algorithm before proceeding to their LSH-based algorithm.\n\n[1] Learning to drop: Robust graph neural network via topological denoising.\n\n[2] Fast graph attention networks using effective resistance-based graph sparsification. \n\n[3] Learning Discrete Structures for Graph Neural Networks.\n\n[4] Inductive Representation Learning on Large Graphs.\n\n[5] Layer-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networks.\n\n[6] GraphSAINT: Graph Sampling-Based Inductive Learning Method.\n\n**Minor comments**: \n- The proposed LSP is sparsifying the original graph by using the similarity between nodes. This requires an assumption on the homogeneity of the graph (i.e., nodes that are connected by edges are similar). What happens to other graph structures? For example in the user-item graph or heterogeneous graph (nodes that are connected by edges are dissimilar),  this type of similarity assumption does not hold.\n- The model configuration in the experiment sections can be improved. For example, weight decay ratio, dropout, number of layers, learning rate, to help reproduce the results.\n", "summary_of_the_paper": " Training GNNs on a large graph requires significant computation resources. Besides, the noisy nature of the real-world graphs might cause GNNs to overfit. To overcome the above limitations, this paper proposes a graph pruning algorithm Locality-Sensitive Pruning (LSP) to sparsify the original graph into a sparse graph. Empirical results show that LSP can remove a significant amount of edges from the original large graph, reduce the computation complexity and training time, but with some compromise on the model performance.\n\n", "summary_of_the_review": "Despite the pros summarized above, the paper lack enough novelty and requires more effort on experiments and clarification on several important aspects as mentioned above (e.g., clarification on the why neighborhood size variance and LSH).\n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "_e-gJRY0nrI", "reviewer": "Reviewer_bzRT", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "he problem studies in this paper is an important research direction and a proper solution to the problem can be quite valuable. However, I have the following reservations about the current work. \n\n[Experimental Results] For a paper that aims at accelerating GNNs, it is expected to provide results on larger-sized datasets. This is especially the case because as the authors mention, in 2 out of the 4 datasets in Figure 3 a random selection strategy seems to be on-par with the proposed approach. Why not use larger graphs from, e.g., the OGB? Also, why do the curves for the proposed approaches stop at around 0.45 in Fig 4?\n\n[Baselines] While there are several existing works that solve a similar problem as that of the current paper (as mentioned in the main text), the proposed approach has been compared only against a random baseline which is not convincing.\n\n[Intuition] One thing that is not clear to me after reading the paper is why selecting similar edges is a good pruning strategy. Example 2 of the paper is also too artificial and does not help much (with a slight modification of Fig 2, one can easily construct a counterexample where random selection has a 1/36 chance of selecting the right pair of points, whereas the proposed approach has a 0 chance).\n\n[Correctness of MinHash] It seems to me that Algorithm 1 and the hash functions in section 4.2 do not correspond to MinHashing (I might be missing something so this could be resolved during rebuttal). Here’s what I understand from the description. \nThere are k hashing functions h_1, … h_k.\nFor each node v, for each hash function h_i, the neighbour that minimizes h_i is added to the neighbours of v. \nLooking at Equation (3), the neighbouring node that minimizes h_i is the one minimizing floor((<x, w_i> + b_i) / l).\nThe neighbour that minimizes the above value is the one that is farthest away from w (assuming l is positive). \nSo the algorithm ends up selecting k neighbours that are farthest away from the random vectors, which does not seem like MinHashing.", "summary_of_the_paper": "For large-size graph structures, the neighborhood aggregation operation of GNNs makes their training and inference slow and expensive. To remedy this problem, one solution proposed in the literature is to increase the sparsity of the graph by selecting a subset of the edges and only running the neighborhood aggregation over those edges. This paper develops an LSH-based approach for edge selection which can be run as a pre-processing step.", "summary_of_the_review": "This paper studies an important problem, but the proposed solution is not well-motivated and the experimental results are inconclusive.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "RXL1rs3VDzs", "reviewer": "Reviewer_7NLP", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Sparsification of graph inputs is a valuable research direction as highlighted with the _over-squashing_ problem with GNNs. LSH is a popular approach for edge pruning in graph clustering and seems like a good choice here. Example 2 motivated the need for locality based reduction of edges, where a toy node classification example depends on 2 neighbours for correct classification, and showing that if each node has 4 edges, and are randomly reduced to 2, the error of misclassification is small; relevant when the topology of the graph is mainly important, over node attributes.\n\nThe experiments showed benefits of LSP over randomly removing edges, but no other methods were compared which I felt is missing. There are numerous other ways to prune (edge-prune) a graph, for example graphical lasso [1] and for efficient computation large scale precision matrix estimation [2], which can be applied to graph edge pruning [3] and there exists other related work not mentioned for sparsiyfing graphs in GNNS which could be directly compared for predictive performance of GNNs, for example [4,5], (with a wall-clock time to compare accuracy vs inference speed for example). Stronger motivation for LSH, over other methods of edge pruning, for example [2] (see [3] for example use of edge pruninig) and comparison with other edge-pruning methods would be beneficial here, and comparison with other GNN sparsification methods would strengthen the emprical evidence for the benefits of the proposed LSP. \n\n1. https://en.wikipedia.org/wiki/Graphical_lasso\n2. Zhang, Richard, Salar Fattahi, and Somayeh Sojoudi. \"Large-scale sparse inverse covariance estimation via thresholding and max-det matrix completion.\" International Conference on Machine Learning. PMLR, 2018.\n3. Strahl, Jonathan, et al. \"Scalable probabilistic matrix factorization with graph-based priors.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 34. No. 04. 2020.\n4. Wan, Guihong, and Harsha Kokel. \"Graph Sparsification via Meta-Learning.\" DLG@ AAAI (2021).\n5. Chiang, Wei-Lin, et al. \"Cluster-gcn: An efficient algorithm for training deep and large graph convolutional networks.\" Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2019.", "summary_of_the_paper": "A pre-processing algorithm is presented to prune (sparsify) an input graph for a graph neural network (GNN), aimed at preserving the local neighbourhood structure. The algorithm uses locality sensitive hashing (LSH) on the graph edge embeddings, placing each edge into an integer 'bucket', the selection of which edges to preserve uses MinHash. Two variants of the algorithm are presented; one uses binary thresholding and the other uses random projections. This pruning is referred to as locality sensitive pruning (LSP).\n\nAdvantages of LSP are explained and experiments focus on the gained inference speed vs preserved prediction performance of a GNN model, when pruning the graph. As a baseline they prune the graphs randomly and show how their approach is better at preserving the prediction performance than this simple baseline. Experiments use GNNs for node classifcation, graph regression and graph classification on numerous datasets, where the a good performing GNN, typically graph attention networks (GATs), are used.\n", "summary_of_the_review": "The main concern with the paper is the lack of comparison with any other methods that sparsify the graph. Firstly, the contribution here is a separate pre-processing step of the graph that uses edge pruning. There are numerous approaches to prune edges for example proabilistic methods that use the node attribute similarities to remove edges with negative correlations in the node attributes (a graphical lasso approach) and this shows to improve performance for then using the pruned graph as side information, in graph theory there are more methods for simply removing edges; It is not clear why LSH is a better choice. Secondly, there are other methods for sparsification of the graph for graph convolutional networks (GCNs) that not only sparsify but improve the performance. I think comparison with these existing GNN sparsification methods is important as the end goal of speeding up inference time while preserving predictive performance is the same.\n\nWith these comparisons, it will better position the paper. The area of sparsification of GNN is I believe an important one, so I feel this work has a lot of potential but there is already work on this that should be compared.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "F6nfkCL3gfX", "reviewer": "Reviewer_Amda", "summary": "", "questions": "", "limitations": "", "rating": 1, "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": "Pro:\n1. The paper is well written and clear for motivations. Easy to follow. \n\nCons:\n1. The designed method is too simple: just a preprocessing and not interact with learning. \n2. Baselines are limited. And result doesn't improve over non-sparsified version. \n3. The author keep emphasizing that the proposed method can help: 1) training efficiently 2) regularization. However the result doesn't support them. First, there is no large dataset to show the benefit over training time. Second, regularization should help improving over non-sparsified version but it loses imformation and does worse than non-sparsified version. \n", "summary_of_the_paper": "The paper proposes to prune graph structure based on hashing edge features with LSH. The proposed method is a deterministic preprocessing. The author evaluates the proposed method by comparing with other sparsification methods.", "summary_of_the_review": "I vote for clear rejection. The proposed method doesn't show any strength in training large dataset and help on overfitting with more regularization. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "9BdGgzElb-0", "reviewer": "Reviewer_WZGy", "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": "Strong points: \nS1. The problem is well motivated to alleviate the computational burden, over-squashing, and varying neighborhoods problems in GNN models. \nS2. Combing the LSH technique with GNN models for graph pruning is an interesting attempt. \nS3. The paper presents several empirical results to demonstrate the effectiveness of LSP. \nS4. The paper presents many insightful examples to illustrate the superiority of LSH-based pruning over the random pruning method. \n\nWeak points: \nW1. The paper employs a canonical hashing technique, LSH, to prune graphs for GNN acceleration and regularization. Although this idea is interesting, the primary contribution of this paper is a combination of existing techniques rather than a new method, insightful observation, or theoretical exploration. \n\nW2. As stated in the abstract, the paper is motivated by the increasing graph sizes and the computational costs of GNN models. However, the graphs used in the experiments are modest. Additionally, a line of literature devoted to the scalability of GNN is missing. For example: \n[SIGN] SIGN: Scalable Inception Graph Neural Networks. \n[GBP] Scalable Graph Neural Networks via Bidirectional Propagation. \n[PPRGo] Scaling Graph Neural Networks with Approximate PageRank. \n\nW3. The relative time of the baseline method, random pruning, is omitted from the experiments. In comparison to random pruning, how does LSP perform in terms of relative time and accuracy trade-offs?\n\nW3. The presentation of the paper needs some improvements. Please refer to the minor comments for details. \n\n\nMinor comments: \nM1. Citations should be added to support the two arguments in the last paragraph of Sec 1. \nM2. Page 6: Could you provide more explanations on the sentence: “Apparently, the complexity of this matrices multiplication does not depend on the number of edges, …”. \nM3. Page 8: to that end -> in the end. ", "summary_of_the_paper": "This paper proposes LSP, a graph pruning method based on Locality-Sensitive Hashing (LSH) for GNN acceleration and regularization. The paper shows that the LSP method can preserve the edge similarity after the pruning process. Additionally, the computational cost of GNN is reduced due to the graph sparsification. ", "summary_of_the_review": "The paper's idea is interesting, as evidenced by the experimental results. However, the theoretical depth and novelty may not be enough to meet ICLR's standards. Additionally, the concerns raised in W2 and W3 should be addressed.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper deals with the important practical problem of speeding up GNNs.
Although the proposed method based on LSH may be considered to be a rather too simple preprocessing, it would be worthwhile to share the practical idea with the community as far as the proposed method is shown effective enough.
However, as pointed out by several reviewers, it is concerned that the experimental validation of this paper is not sufficient.
Further and deeper validations will make this paper stronger.
Decision: Reject