SparRL: Graph Sparsification via Deep Reinforcement Learning
Authors: Ryan Wickman
Xiaofei Zhang
Weizi Li
Venue: ICLR 2022 Submitted (2022)
Keywords: graph sparsification
graph theory
machine learning
reinforcement learning

Abstract: Graph sparsification concerns data reduction where an edge-reduced graph of a similar structure is preferred. Existing methods are mostly sampling-based, which introduce high computation complexity in general and lack of flexibility for a different reduction objective. We present SparRL, the first general and effective reinforcement learning-based framework for graph sparsification. SparRL can easily adapt to different reduction goals and promise graph-size-independent complexity. Extensive experiments show that SparRL outperforms all prevailing sparsification methods in producing high-quality sparsified graphs concerning a variety of objectives. As graph representations are very versatile, SparRL carries the potential for a broad impact.

Under review as a conference paper at ICLR 2022
SPARRL: GRAPH SPARSIFICATION VIA DEEP REIN- FORCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Graph sparsification concerns data reduction where an edge-redueed graph of a similar structure is preferred. Existing methods are mostly sampling-base based, which introduce high computation complexity in general and lack of flexibility for a different reduction objective. We present SparRI, the first general and effective reinforcement learning- baased framework for graph sparsification. SparRL casily adapt to different reduction goals and promise graph-size craph-size-nngeee size-independent complexity. Extensive experiments show that SparRL outperforms all prevailing sparsification methods in producing high-quality spansified graphs concerning variety of objectives. As graph representations are very versatile, SparRL carries the potential for broad impact.
INTRODUCTION
Graphs are the natural abstraction of complex correlations found numerous application domains including social media, communications, transportation, and medicine discovery, and thus have been studied in many scientific disciplines such as computer science, mathematics, engineering, sociology, and economics. The interconnectedness of a graph can be leveraged to explore, infer, and learn latent structures as well as global and local information embedded in the graph. However, modern graphs can be very complex, causing their analysis, computing, and utilization inefficient. This has motivated the study of gruph sparsification in the past two decades (Batson et al., 2013; Teng, 2016), where the objective is to prune edges from graph to produce sparsified graph while preserving user-defined metrics in query evaluation or knowledge inferring. The most commonly adopted metrics include the graph spectrum and the effective resistance of edges (Spielman & Srivastava, 201 1; Spielman & Teng, 2011). Sparsification techniques developed w.r.t these metrics have been applied to domains such as power grid management (Zhao et al., 2014; Zhao & Feng. 2017), integrated circuit simulation (Zhao et al., 2015), and influence maximization (Shen et al., 2017; Mathioudakis et al., 2011).
So far, many graph sparsification techniques are sampling- based (Fung et al., 2019). While effective, they all introduce high computation complexity and lack the flexibility to preserve different graph properties in many applications, e.g., approximate graph analysis (Iyer al. 2018; Ahn et al., 2012: Satuluri et al., 201 la; Zhao, 2015), privacy preserving (Upadhyay. 2013; Arora & Upadhyay, 2019), and representation learning (Calandriello al., 2018). Thus, a general, flexible graph sparsification technique for various reduction objectives and application domains is highly desired.
We present SparRL, general graph sparsification framework empowered by deep reinforcement learning that can be applied to any edge sparsification task with a customized reduction goal. Consider the example shown Figure 1, by setting modularity preservation as the edge reduction objective function, SparRL prune user-defined amount of edges from the original graph and still preserve the substructure modularity. To improve learning efficiency and convergence rate of SparRL, we initialize the initial state by randomly sparsifying the graph before each training episode, use Double DQN (Van Hasselt et al., 2016) with Prioritized Replay (Schaul et al., 2015), and employ c-greedy exploration for searching for the optimal pruning strategy.
We test SparRL using a wide range of graph datasets and metrics including PageRank, community structure, and pairwise shortest-path distance. As result, SparRL outperforms all baselines on preserving PageRank, community structure, and single-pair shortest path (SPSP) preservation at a variety of edge-kept ratios.

---

Under review as a conference paper at ICLR 2022
(a) Original Karate
(b) Karate (80% edge kept)
(c) Karate (60% edge kept)
Figure 1: Applying SparRL Zachary's 's karate club (Zachary, 1977) graph by setting modularity preservation the edge reduction goal. Different colors denote different modularity-based partitions, while node size scales with its degree. Modularity partition computed and plotted with Gephi (Bastian et al., 2009)
In summary, the contributions of SparRL are the following:
A novel reinforcement learming-bsse general-purpose purpose graph sparsification framework with
modular, task-adaptive, and easily modifiable components;
Task flexibility because the plug-in reward function:
Task scalability as SparRL's time complexity is independent from the size of graph; and
Simple to use time v.s. performance trade-offs.
The source code of SparRL be found https:://annnyn scpenc SparRL-PyTorch. PyIorch-F545/
RELATED WORK
Originated from the cut problem (Benczúr & Karger, 1996), graph sparsification has drawn extensive research interests (Batson et al., 2012; Lee & Sun, 2015; 2017: Spielman & Srivastava, 201 1: Spielman & Teng, 2011). straightforward approach to this problem is remove edges from a graph with probabilities proportional to the edge weights. However, this approach may fail for highly structured graph, c.g., a graph with a small cut value where the sampling may exclude the cut edges, thus losing the connectivity of the original graph. An improved approach is to the k-neighbors sparsifier (Sadhanala et al., 2016), which performs local sparsification node-by by-node via retaining edges of nodes that have degree smaller than predefined threshold and removing edges of nodes (proportionally to their weights) that have degree greater than т. Another method is to remove edges proportionally their effective resistance, which measures the importance of edge in preserving the minimum distance between two nodes. This approach will result in only essential edges (on the order of (mpolyyognn) being kept. Although there have been advancement fast approximation of effective resistance (Koutis et al., 2012; 2016), the graph size remains dominating factor in computing complexity.
A related line of research in graph theory, namely graph spanner (Peleg & Ullman, 1989), aims to compute a subgraph that satisfies certain reachability or distance constraints, e.g., t-spanner (Fekete & Kremer, 2001; Dragan et al., 2011), where the geometric distance of every vertices pair in the subgraph is at most times of the real distance in the original graph. Therefore, is also named the stretch parameter, which needs be specified for spanner algorithm. However, spanner has no guarantee on the edge reduction ratio. In contrast, SparRL takes the edge reduction ratio as input and make edge pruning decision via learned model aiming to best preserve the desired graph structural property. Moreover, techniques developed for the spanner problem are subject to geometric distance preservation, which make them hard be generalized for the wide spectrum of graph sparsification objectives. More details on graph sparsification techniques can be found in survey papers (Batson al., 2013; Teng, 2016).
In recent years, learning-based algorithms have gained popularity as they allow for direct optimization on task's 'ss objective and have demonstrated superior performance compared traditional methods.

---

Under review as a conference paper at ICLR 2022
Surprisingly, little work has applied learning to graph sparsification. GSGAN (Wu & Chen, 2020) approaches graph sparsification using GAN (Goodfellow et al., 2014), whose goal is to preserve the community structure of a graph by learning to generale a new graph. While effective, GSGAN could introduce edges that are not in the original graph, thus compromising the graph sparsification objective on many real-world networks where establishing new edges/connections is resuuce-intenssve (e.g.. road network). RNet-DQN (Darvariu et al., 2020) uses RL to process graphs, where the focus is to enhance resilience of graph via adding edge instead of sparsification. GDPNet (Wang et al., 2019) also uses RL but the goal is graph representation learning instead of graph sparsification. The most relevant study to ours is NeuralSparse (Zheng et al., 2020), whose focus again is representation learning. The subgraphs are produced via supervised learning and need to go through graph neural networks for downstream classification. Due to these constraints, classical analytic benchmarks such as community detection shortest path computing from the traditional graph sparsification studies are missing in (Zheng et al., 2020). In comparison, SparRI outputs sparsified graph where existing graph analytic algorithms can be directly applied. To the best of our knowledge, SparkL. is the first task-adaptive and effective RL-based framework for graph sparsification.
3 PRELIMINARIES
Consider a T Tsstep episodic task. At each timestep t E [1, the RL agent uses its policy To(at (s)))s)))))))))){)) to choose action a, based on state 8, from the environment. Then, the environment responds with reward and next state $1+1- This sequential decision-making process is formulated as Partially- Observable Markov Decision Process (POMDP) defined by the tuple (S, A, P, R. Ω, 0,,,,), where S is the state space, A is the action space, P(s' s, a) is the transition probability function, R is the reward function, Q is the set of observations, O is the observation probability function, and y E [0, 1] is the discount factor. The objective of the RL agent is to find To that can maximize the sum of discounted rewards, or the return Rg 7
Related to (PO)MDP is the concept of Q-function Q" : A + R, which describes the total expected reward by taking action a in state and then following policy π thereafter. The element that we want to obtain is the optimal Q-function Q', from which we can trivially derive the optimal (s, a). One way learn Q" is through Q-learning (Watkins, 1989):
policy n² (s))) argmar, Q"
Qc+1 (st, at) + Qe(oe, ar) + on [re+1 + aymaaa Qt (1 - Qe((t; at)
where ar E (0, 1] is the step size. Accompanying the rise of deep learning, many variations of Q-learning have been developed, among which Deep Q-Network (DQN) (Mnih et al., 2015) has gained popularity due to its success in playing Atari games. There exist several major improvements of DQN, including Double DQN (Van Hasselt et al., 2016), Prioritized Replay (Schaul et al., 2015), and Dueling DQN (Wang et al., 2016). In this work, we choose Double DQN and Prioritized Replay as component of SparRL since it has significant improvement over DQN with small code changes.
SPARRL FRAMEWORK
In this section, we first provide an overview of our approach, then detail its components and design rationale.
4.1 FRAMEWORK OVERVIEW
The overall goal is to find an edge sparsified graph G' = (V'.E) that approximates the original graph G (V, F)) measured over some performance metric.
We treat this as an episodic task, where edges are sequentially pruned from G. Each timestep, a subgraph of edges are sampled from E' and SparRL's action consists of choosing edge to prune from the sampled batch of edges. This continues until T edges are pruned from the graph which will produce G We describe this process in Algorithm 1.
We exploit the simplicity of the environment, by allowing the initial state 8o to be sampled from any state the state space S. This is implemented as a preprocessing step, where before each episode.

---

Under review as a conference paper at ICLR 2022
Algorithm 1: SparRL Framework
for to num.episodes do
G' + clone
Sample T ~ (1,, (Tmaz))
Samplep (4(0,
T, mi] &p, (T)
Randomly prune T, edges from
for = to T do
H: <- Randomly sample H edges from G'
dx, Degrees of nodes in H;
g_values J8par u1, (H;, dw.. [Eol
<- Sumple action using e-greedy exploration from g-nolues Prune edge at from G'
Tt <- RR('))
Save timestep trajectory (8s, 81+1, az; rt; in prioritized replay buffer
Train fSparRL on batch of trajectories
end for
end for
randomly prune Tр edges from G to produce the initial sparsified graph at the first timestep, G The percentage of edges to prune is sampled from a continuous uniform distribution ~ (0, 1) and set Tp min p, [E| T). This allows for SparRL agent start in any part of the state space, without having to initially prune Tp edges to visit it. Thus, efficient exploration of the state space removed from the behavior of the trained policy.
4.2 MDP FORMULATION
We formalize the task of sparsification as an POMDP that solved using reinforcement learning; however, for ease of explanation, we will simplify it to MDP. The state 8, includes the subgraph H, the degrees of all the nodes in the subgraph dH,, and the percentage of edges left in the graph Ec; //Ecl, where |Eey is the number of edges in the sparsified graph and |Ecl is the number of edges in the original graph. The reward r is dependent on the properties of the graph that encouraged preserved, and thus will be discussed later in the experiments section. Each timestep we compute the reward after an edge is pruned to avoid sparse rewards. The action a, is the edge to prune. The probability transition function consists of randomly sampled edge subgraph from G', where each edge has an equal chance to be sampled. The episode goes on for I' timesteps until is terminated. For training, we keep T' small T 8. we want to encourage more time on exploration rather than an episodes initialized at a random initial state.
4.3 POLICY LEARNING
We use Double DQN (Van Hasselt et al., 2016) to represent the SparRL sparsification policy that is parameterized by a deep neural network. The policy trained over sampled batch of trajectories, sampled using prioritized replay (Schaul et al., 2015).
The model architecture, shown Figure 2, is composed of the node encoder, edge encoder, and action-value function head. The node encoder first looks up the initial node embedding for all the nodes in the graph, which are trained jointly with the model. Then, the node encoder uses a GAT (Veličković et al., 2017) that applies self-attention to the neighborhood of each node produce a new node embedding. Each node embeddings of the subgraph are then separately combined with its degrees, in-degree and dut-ee if the graph is directed, and the ratio of edges left in the graph, Fc; /1 Fcl- The edge encoder combines two nodes that represent an edge. Finally, the action-value head outputs the q-values, Q(+t. ag) Q(+,, an), for each edge in the subgraph. The GAT in the node-encoder uses single fully-comnected layer with unit for computing the attention coefficients, both the main part of the node-encodes and edge-encoded consists of two fully-connected layers with 128 units cach that are followed by Leaky ReLU activation, and the action-value head consists of single fully- cully-connected layer with one unit.
Thus, the model approximates the Q-value function:

---

Under review as a conference paper at ICLR 2022
Node Embeddings
Edge Embeddings
H
Q ao
Node Encoder
Edge Encoder
Value Function
du
( a,
//Gl
( a
Figure 2: The SparRL model architecture that consists of the node encoder, edge encoder, and action-value head. The imput the model includes the subgraph, the degrees of the node, and ratio of edges still in the graph. The node encoder combine output node embedding with degrees and the ratio edges each pair of nodes that represent an edge. The action-value function edge will produce the q q-value for each edge.
GAT the I-hop neighborhool of each node embedding and then combines the
the graph. edge encoder will combine
Table 1: Graph datasets used in the experiments.
Dataset
Twitter
Facebook
YouTube
Amazon (Top-500 Comm.)
Email
CiteSeer
(Top-100& Comm.)
V
81,306
4,039
4,890
4,259
1,005
3,264
E
1,768.149
88,234
20,787
13,474
16,064
4,536
Eag
fSpar BL (He, du
|El ) Q(+t, .o),..., Q(s,,
Each edge of the subgraph is independently ran through the network, so the subgraph length [ is not fixed by the network. Therefore, any number of edges can be considered to be pruned each timestep during test time.
5 EXPERIMENTS
We validate the effectiveness of SparRL using a variety of real-world datasets and test its components performance over several metries. The key observations include:
SparRL demonstrates superior performance existing sparsification methods representa- tive graph metrics over graphs of different scales;
SparRL can outperform the t-spanner method for preserving Single-Pair-s Pair-Shortest-Pui
(SPSP) distances at the same edge kept ratio; and
SparRI. allows for simple time vs. performance trade-off by modifying H
5.1 EXPERIMENT SETUP
Datasets. We test SparRL using graphs from a variety of domains: Twitter (Leskovec & Mcauley, 2012), Facebook (Leskovec Mcauley, 2012), YouTube (Mislove et al., 2007), Amazon (Yang & Leskovee, 2015), Email-Eu-Core (Yin et al., 2017), and CiteSeer (Sen et al., 2008). Table I summarizes the number nodes and edges of each graph.
Baseline Methods. We compare SparRL with wide range of sparsification methods: Random Edge (RE). Local Degree (LD) (Hamaan et al., 2016), Edge Forest Fire (EFF) (Hamann et al., 2016), Algebraic Distance (AD) (Chen & Safro, 2011) 20, L-Spar (LS) (Satuluri et al., 2011b), Simmelian Backbone (SB) (Nick et al., 2013), and Quadrilateral Simmelian Backbone (QSB) (Nocaj et al., 2014). The details of the baseline methods are provided in Appendix A.1.
Metrics. We assess the sparsification methods by examining how well they preserve the topological structure of the original graph w.r.t different metrics, namely PageRank, community structures, and pairwise shortest path distance (Hamann et al., 2016). For each metric, we evaluate the performance of sparsification method by running the method eight times independently and report the average.
SparRL Setup. Next, we detail our hyperparameter values and settings that are associated with the Double DQN algorithm used by our sparsifier agent. We update the target DQN network by apply a

---

Under review as a conference paper at ICLR 2022
Table 2: Comparison of PageRank preservation via the Spearman's 's index, where is the edge kept ratio.
Twitter
Facebook
Amazon (Top-500 Comm.)
Method
r=0.2
r=0.4
r=0.6
r=0.8
r=0.2
r=0.4
r=0.6
r=0.8
r=0.2
r=0.4
r=0.6
r=0.8
SparRL
0.846
0.944
0.984
0.995
0.942
0.982
0.996
0.998
0.779
0.907
0.944
0.988
LD
0.512
0.775
0.876
0.929
0.899
0.979
0.995
0.995
0.755
0.884
0.929
0.978
RE
0.763
0.864
0.924
0.967
0.802
0.905
0.955
0.982
0.549
0.749
0.871
0.948
EFF
0.628
0.725
0.811
0.892
0.629
0.801
0.919
0.980
0.669
0.728
0.888
0.969
AD
0.520
0.690
0.837
0.940
0.408
0.519
0.637
0.782
0.230
0.341
0.553
0.769
0.771
0.826
0.857
0.892
0.648
0.830
0.924
0.960
0.589
0.640
0.763
0.859
SB
0.581
0.689
0.761
0.811
0.379
0.582
0.681
0,740
0.247
0,348
0.397
0,399
QSB
0.642
0.746
0.794
0.821
0.512
0.585
0.671
0.737
0.280
0.354
0.399
0.399
Twitter
Facebook
Amazon (Top-500 Comm.)
1.0
1.0
Spearman's Rho
Spearman's Rho
0.8
0.8
0.8
Spearnan's
0.7
0.6
0.7
0.8
0.5
0.4
04
0.2
0.2
0.4
0.6
0.8
0.2
0.6
0.8
0.2
0.4
0.6
0.8
Ratio of Kept Edges
Ratio of Kept Edges
Ratio of Kept Edges
SparRL
LD
EFF
AD
RE
LS
QSB
SB
Figure 3: PageRank preservation measures over Spcarman's 's p. SparRL outperforms all other methods on all cases.
soft updates after training batch of trajectories each timestep: Blarget +- 40ttegget (1 (p) where Ozarget are the parameters of the target DQN network and 0 are the parameters of the current DQN network policy. We find that şp 0.001 corresponds
stable results. We use a 0.6 and 3 = 0.4 for Prioritized Replay, = 0.95 for the discounted return. and initially set = 0.99 for e-greedy exploration and decay it to 0.05 over the first 10k policy update steps. We keep the learning rate of the model fixed at 0.0002 during the entire training process.
When training the model for all experiments we set Tmaz [1. Tmar] before each episode, the maximum prepruning percent = 0.8, and train until negligible improvements are found over pruning 10% the edges. Training the SparRL networks typically takes 1h-4h for the smaller graphs and roughly 6h-12h for the larger graphs using Intel Core 19-1k CPU and RTX 3090 GPU. However, the run-time complexity when evaluating is simply O(H T) as we predicting over subgraph of length H for total of T times.
where we sample T between
When evaluating on various test datasets, we act greedily w.r.t the learned DQN policy and prune the edge that corresponds to the maximum q-value in the output.
5.2 EFFECTIVENESS OF SPARRL
PageRank Preservation. PageRank serves critical centrality metric for many ranking-based graph applications. We examine the sparsification methods by comparing the Spearman's p rank correlation coefficient (Myers & Well, 2003) between the PageRank score of the original graph and of the sparsified graph at multiple edge-kept ratios, defined as |/ where EE is the number of edges in the sparsified graph. We define the reward for PageRank as the difference of Spearman's 's rank correlation coefficients between G" and G:
Tpr PC PC
6

---

Under review as a conference paper at ICLR 2022
Table Comparison of community structure preservation over the ART index, where is the edge kept ratio.
YouTube (Top-100 Comm.)
Email-Fu-Core
Amazon (Top-500 Comm.)
Method
r=0.2
r=0.4
r=0.6
r=0.8
r=0.2
r=0.4
r=0.6
r=0.8
r=0.2
r=0.4
r=0.6
r=0.8
SparRL
0.084
0.230
0.323
0.253
0.651
0.705
0.527
0,429
0.248
0.285
0.257
0.269
LD
0.052
0.082
0.150
0.145
0.278
0.30
0.278
0.207
0.240
0.238
0.236
0.236
RE
0.048
0.144
0.157
0.152
0.226
0.318
0.348
0.312
0.141
0.224
0.236
0.235
EFF
0.029
0.092
0.117
0.134
0.407
0.385
0.347
0.334
0.109
0,180
0.223
0.232
AD
0.035
0.068
0.111
0.143
0.263
0.272
0.284
0.333
0.105
0.169
0.210
0.234
0.016
0.071
0.150
0.147
0.446
0.390
0.375
0.319
0.209
0.250
0.249
0.245
SB
0.039
0.127
0.161
0,166
0.274
0.326
0.365
0.358
0.225
0.225
0.235
0.249
QSB
0.045
0.095
0,132
0.166
0.408
0.435
0.349
0.291
0.123
0.206
0.233
0.248
YouTube (Top-100 Comm.)
Email-Eu-Core
Amazon (Top-500 Comm.)
0.7
0.25
0.8
0.20
0.5
ARI
0.20
0.15
0.4
0.15
0.3
0.06
Ratio Kept Edges
Ratio of Kept Edges
Ratio of Kept Edges
SparRL
LD
EFF
AD
RE
LS
QSB
SB
Figure 4: Community structure preservation measures ARI score. SparRL outperforms all other methods on all cases.
where Parr is the Spearman's for the sparsified graph G and PC is the Spearman's 's for the original graph G. The results in Figure 3 and Table 2 show that SparRL outperforms all other methods on the Twitter, Facebook, and Amazon (Top-500 Comm.) graphs.
Community Structure Preservation. We use the Adjusted Rand Index (ARI) (Hubert & Arabie, 1985) to measure the effectiveness of SparRL on preserving the community structure of graph by comparing non-overlapping ground truth communities those found using the Louvian method (Blon- del et al., 2008) at multiple edge-kept ratios. We define the reward function as the different between ARI scores for and G":
Teom = ARI -RR((G) + Flabel:
(2)
where ARI(G") is the Louvian ARI score on G' and ARI(G) is the original Louvian ARI score on G. The other reward, Plabel, is defined as:
Flabel {
bg = 1o else
where lay is the label of the source node pruned at timestep and lo3 is the label of the destination node. We add this auxiliary reward to encourage the agent to not prune edge if its two nodes belong to the same community.
The results in Figure and Table 3 show that SparRL consistently outperforms other methods on the YouTube (00p-100 Comm.), Email, and Amazon (Top-500 Comm.) graphs.
Shortest Path Distance Preservation. To the ability of various sparsification methods in preserving the pairwise shortest path distance, We define the reward function for single-pair shortest path (SPSP) as follows:
7

---

Under review as a conference paper at ICLR 2022
Table Comparison of SPSP preservation over the average increase of distance, where is the edge kept ratio.
Citeseer
Email-Fu-Core
Amazon (Top-500 Comm.)
Method
r=0.2
r=0.4
r=0.6
r=0.8
r=0.2
r=0.4
r=0.6
r=0.8
r=0.2
r=0.
r=0.6
r=0.8
SparRL
2773
2473
338
15
0.326
0.133
0.07
0.021
281
106
0.518
0.24
LD
2896
2898
2899
730
0.355
0.16
0.078
0.033
299
121
77
9
RE
3233
2997
2047
1081
309
170
2930
1077
364
117
EFF
3064
2645
1896
696
173
56
30
18
2042
1126
211
56
AD
3252
3237
3165
2995
728
382
240
106
3803
3188
2460
1396
3230
3232
3204
1191
54
2537
813
400
SB
3252
3192
3192
3191
891
531
321
250
2088
2084
1865
1400
QSB
3250
3192
3193
3193
970
465
364
292
3783
3022
2356
1319
CiteSeer
Email
Amazon (Top-500 Comm.)
1000
3000
Avg. SPSP Increase
Avg. SPSP Increase
800
Avg. SPSP Increase
3000
2000
600
2000
400
1000
1000
200
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
Ratio of Kept Edges
Ratio of Kept Edges
Ratio of Kept Edges
SparRL
LD
EFF
AD
RE
LS
QSB
SB
Figure Shortest Path Distance Preservation measured by the average increase of distance between 8196 randomly selected pairs. In this figure, as SparRL's line is below all the others, it increases the SPSP distance the least and thus outperforms all other methods on all cases.
T Теpap
1 PPI
Σ (u,U)E
dist(u, v)a - dist(u, u)a.
(4)
where P is the set of SPSP pairs, and dist(u, r)c. is the SPSP distance between and v in the sparsified graph G', and (u, v)c is the SPSP distance between node u and node e in the original graph G. In the case where u becomes unreachable from in G", set this difference equal [V]. as this is greater than the maximum path length by 1.
During training, the set of SPSPs P created at each timestep before edge is pruned. When the model chooses an edge to prune ag, we sample random nodes and compute their shortest paths from the source node and destination node of a, This design is to leverage the optimal substructure property of shortest paths. That is, the only way a SPSP, for example from u to v, will be affected by pruning edge a, is if contained in that path. This because composed of the SPSP from u to the source node in a, and the SPSP from the destination node in a, to v. Thus, when a is pruned, a new SPSP must be generated between u and that does not contain the edge d;.
SPSP between u and e must be
During test time, however, we run a maximum 8196 randomly sampled Single-Pair Shortest Path (SPSP) queries over the graph and keep them fixed for the entire episode. The results are given in Figure 5 and in Table 4 which show that SparRL consistently outperforms other methods on the CiteSeer, Email, and Amazon (Top-500 Comm.) graphs.
Comparing Sp and t-Spanner. As t-spanner provides a way to sparsify graph while preserving the geometric distance between a pair of nodes at most times of the original distance, we conduct an experiment study on comparing the performance of SparRL and a popular spanner algorithm given in (Baswana & Sen, 2007). Due the fact that spanner algorithms cannot guarantee the number of edges to prune, we run the NetworkX (Hagberg et al., 2008) spanner implementation on various values of stretches and record its edge kept ratio. As an approximate algorithm, the

---

Under review as a conference paper at ICLR 2022
Table SparRI. compared against (-spanner for various stretch values (a%6: edge kept ratio)
Method t=3 (99.65%)
1=4 (99.63%)
t=8 (97.82%)
(93.74%)
32 (90.78%)
t-spanner 0.0082
0.0054
0.0405
0.1187
0.191
SparRL
0.0031
0.0043
0.0350
0.0974
0.1820
0.8 Ratio of Kept Edges
0.2 Ratio of Kept Edges
0.70
0.42
ARI
0.80
0.38
0.56
0.50
2
32
64
8
32
64
100
30
25
40
10
[H]
Higure Subgraph length [H] affect on model perfomance measured over Spearman's 's on the Email graph.
spanner algorithm produces different sparsified graph each run. Therefore, we run the algorithm 16 times for each stretch value and compute the average number of edges and average performance over preserving randomly sampled SPSPs. We then run SparRL on the same average number of edges for each stretch value and display the Tspep (defined in Equation 4) results Table on the CiteSeer network. These results show that SparRL outperform the approximate t-spanner algorithm over various stretch values.
5.3 ANALYSIS OF SPARRL COMPONENTS
Impact of Subgraph Size. At each timestep. SparRL inputs subgraph which contains edges randomly sampled from Ecy Due to the flexibility of our model architecture, we can have variable length subgraphs as input at test time. Thus, in Figure we show results on applying the same trained model on varying subgraph lengths and measure their performance over Spearman's s on the Email-Eu-Core graph. While increasing the subgraph length up to certain point can improve model performance (c.g., for 0.8 edge-ratio |M|| 64 performance the best,
though SparRL was trained on |I| = 32), SparRL does increase the time to prune the edge. Thus, this is time vs performance trade-off that can be adjusted accordingly based on the user's need.
CONCLUSION
In this work, propose general graph sparsification framework based deep reinforcement learning, namely SparRL. SparRL can overcome the limitations of existing sparsification methods with relatively low computation complexity and the flexibility to adapt cation objectives. We evaluate SparRL using various experiments on many real-world datasets and representative graph metrics. The results show that SparRL effective and generalizable in producing high-qualin sparsified graphs. Further analysis on the components of SparRL have validated our design rationale. the future, we would like to extend SparRL to the dynamic graph setting, and investigate how SparRL could help improve the performance of graph learning tasks, e.g., link prediction, label classification,, and other graph related workloads.
wide range of sparsifi-

---

Under review as a conference paper at ICLR 2022
REFERENCES
Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Graph sketches: sparsification, spanners, and subgraphs. In Proceedings of the 31st ACM SEGMOD-SIGACT-SICE Symposium on Principles of Database Systems, PODS, pp. 5 3-14. ACM, 2012.
Raman Arora and Jalaj Upadhyay. On differentially private graph sparsification and applications. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems, NewrIPS, pp. 13378-13389 2019.
Mathieu Bastian, Sebastien Heymann, and Mathieu Jacomy. Gephi: An open source software for exploring and manipulating networks. In ICWSM. The AAAI Press, 2009.
Surender Baswana and Sandeep Sen. A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Struct. Algorithms, 30(4):532-563, 2007. 2007.
Joshua Batson, Daniel Spielman, and Nikhil Srivastava. Twice-ramanujan sparsifiers. SIAM J. Comput., 1146)117041171,, 2012.
Joshua D. Batson, Daniel A. Spiclman, Nikhil Srivastava, and Shang-Hua Teng. Spectral sparsification of graphs: theory and algorithms. Commun. ACM, 56(8):87-99 2013.
András A. Benczúr and David R. Karger. Approximating s-t minimum cuts in Ó(n2) time. In Proceedings of the 28th Anmual ACM Symposium on the Theory of Computing, pp. 47-55, ACM, 1996.
Vincent Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, 2008 (10):P10008, 2008
Daniele Calandriello, Ioannis Koutis, Alessandro Lazaric, and Michal Valko. Improved large-scale graph learning through ridge spectral sparsification. In Proceedings of the 35th International Conference on Machine Learning, ICML, volume 80, pp. 687-696, 2018.
Jie Chen and Ilya Safro. Algebraic distance on graphs. SIAM Journal on Scientific Computing, 33(6): 3468- -468-3490, 2011.
Darvariu, Stephen Hailes, and Mirco Musolesi. Improving the robustness of graphs through reinforcement learning and graph neural networks, 2020.
Feodor F. Dragan, Fedor V. Fomin, and Petr A. Golovach. Spanners in sparse graphs. J. Comput. Syst. Sci., 178) 2011.
Sándor P. Fekete and Jana Kremer. Tree spanners in planar graphs. Discret. Appl. Math., 108(1-2): 85-103, 2001.
Wai Shing Fung, Ramesh Hariharan, Nicholas A. Harvey, and Debmalya Panigrahi. A general framework for graph sparsification. SIAM Comput., 48(4):1196-122) 2019.
lan Goodfellow. Jean Pouget-Abadic, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. arXiv preprint arXiv:1406.260 1406.666,, 2014.
Aric A. Hagberg. Daniel A. Schult, and Pieter J. Swart. Exploring network structure, dynamics, and function using networkx. Gaël Varoquaux, Travis Vaught, and Jarrod Millman (eds.), Proceedings of the 7th Python in Science Conference, pp. 11 - 15, Pasadena, CA USA, 2008.
Michael Hamann, Gerd Lindner, Henning Meyerhenke, Christian L Staudt, and Dorothea Wagner. Structure senncture-preservinn preserving sparsification methods for social networks. Social Network Analysis and Mining, 6(1 6(1):22, 2016.
Lawrence Hubert and Phipps Arabie. Comparing partitions. Journal of classiftcation, 2(1):193-218, 1985.
10

---

Under review as a conference paper at ICLR 2022
Anand Padmanabha Iyer, Aurojit Panda, Shivaram Venkataraman, Mosharaf Chowdhury, Aditya Akella, Scott Shenker, and Ion Stoica. Bridging the gap: Towards approximate graph analytics. In Proceedings of the 1st ACM SIGMOD Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA), 2018.
Joannis Koutis, Alex Levin, and Richard Peng. Improved spectral sparsification and numerical algorithms for SDD matrices. In Christoph Dürr and Thomas Wilke (eds.), 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, February 29th March 3rd, 2012, Paris, France, volume 14 of LIPIcs, pp. 266-277. Schloss Dagstuhl Leiinizz-Zentrmm für Informatik, 2012.
Ioannis Koutis, Alex Levin, and Richard Peng. Faster spectral sparsification and numerical algorithms for SDD matrices. ACM Trans. Algorithms, 12(2):171-17111 2016.
Yin Tat Lee and He Sun. Constructing linear-sized spectral sparsification in almost-linear time. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS, pp. 250-269, IEEE Computer Society, 2015.
Yin Tat Lee and He Sun. An sdp-based algorithm for linear-sized spectral sparsification. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC, pp. 678-687. ACM, 2017.
Jure Leskovec and Christos Faloutsos. Sampling from large graphs. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 631-636, 2006.
Jure Leskovec and Julian Mcauley. Learning to discover social circles in ego networks. In F. Pereira, C. C. Burges, L. Bottou, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 25. Curran Associates, Inc., 2012.
Michael Mathioudakis, Francesco Bonchi, Carlos Castillo, Aristides Gionis, and Antti Ukkonen. Sparsification of influence networks. In Proceedings of the 17th ACM SIGKDD International 2011.
Conference on Knowledge Discovery and Data Mining, pp.
Alan Mislove, Massimiliano Marcon, Krishna P. Gummadi, Peter Druschel, and Bobby Bhattacharjee. Measurement and Analysis of Online Social Networks. In Proceedings of the 5th ACM/Usenix Internet Measurement Conference (IMC'07), San Diego, CA, October 2007.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski. et al. Human-level control through deep reinforcement learning. nature, 518(7540):529-533 2015.
Jerome L. Myers and Amold D. Well. Research Design and Statistical Analysis (2nd ed.). Lawrence Erlbaum, 2003.
Bobo Nick, Conrad Lee, Pádraig Cunningham, and Ulrik Brandes. Simmelian backbones: Amplifying hidden homophily in facebook networks. In Proceedings of the 2013 IEEE/ACM international conference on advances in social networks analysis and mining, pp. 525-532, 2013.
Arlind Nocaj. Mark Ortmann, and Ulrik Brandes. Untangling hairballs. In International Symposium on Graph Drawing, pp. 101-112. Springer, 2014.
David Peleg and Jeffrey D. Ullman. An optimal synchronizer for the hypereube. SIAM J. Comput., 18(4):740-747, 1989.
Veeranjaneyulu Sadhanala, Yu-Xiang Wang, and Ryan J. Tibshirani. Graph sparsification approaches for laplacian smoothing. In Proceedings of the 19th International Conference on Artificial Intelli- gence and Statistics, AISTATS, volume 51 of JMLR Workshop and Conference Proceedings, pp. 1250-1259, 2016.
Venu Satuluri, Srinivasan Parthasarathy, and Yiye Ruan. Local graph sparsification for scalable clustering. In Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 721-732, ACM, 201 la.
11

---

Under review as a conference paper at ICLR 2022
Venu Satuluri, Srinivasan Parthasarathy, and Yiye Ruan. Local graph sparsification for scalable clustering. SIGMOD '1, pp. 721-732, New York, NY, USA, 201 1b. Association for Computing Machinery.
Tom Schaul, John Quan, loannis Antonoglou, and David Silver. Prioritized experience replay. arXiv preprint arXiv:1511.05952, 2015.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification network data. Al magazine, 29(3):93 93, 2008.
Xiao Shen, Fu-Lai Chung, and Sitong Mao. Leveraging cross-network information for graph sparsification in influence maximization. In Proceedings of the 40th International ACM SIGIR Conference on Research and Development Information Retrieval, pp. 801-804, 2017.
Daniel A. Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM J.
Comput.,
2011.
Daniel A. Spielman and Shang-Hua Teng. Spectral sparsification of graphs. SIAM J. Comput., 40(4): 981-1025, 2011.
Christian L. Staudt, Aleksejs Sazonovs, and Henning Meyerhenke. Networkit: A tool suite for large-scale complex network analysis, 2015.
Shang- Hua Teng. Scalable algorithms for data and network analysis. Found. Trends Theor. Comput. Sci., 12(1-2):1-274, 2016.
Jalaj Upadhyay. Random projections, graph sparsification, and differential privacy. In Advances in Cryptology -SSACCYPTT 2013 19th International Conference the Theory and Application of Cryptology and Information Security, volume 8269, pp. 276-295. Springer, 2013.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. In Proceedings of the AAAI conference on artificial intelligence, volume 30, 2016.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks, arXiv preprint arXiv:1710. 2017.
Lu Wang, Wenchao Yu, Wei Wang. Wei Cheng, Wei Zhang, Hongyuan Zha, Xiaofeng He, and Haifeng Chen. Learning robust representations with graph denoising policy network. In 2019 IEEE International Conference on Data Mining (ICDM), pp. 1378- 1383. IEEE, 2019.
Ziyu Wang, Tom Schaul, Matteo Hessel. Hado Hasselt, Mare Lanctot, and Nando Freitas. Dueling network architectures for deep reinforcement learning. In International conference on machine learning, pp. 1995-2003. PMIR, 2016
Christopher John Comish Hellaby Watkins. Learning from delayed rewards. 1989.
Hang-YYng Wu and Yi-Ling Chen. Graph sparsification with generative adversarial network, 2020,
Jaewon Yang and Jure Leskovec. Defining and evaluating network communities based on ground-truth Knowl. Inf. Syst., 42(1):181-25) January 2015. ISSN 0219-1377.
Hao Yin, Austin R. Benson, Jure Leskovec, and David F. Gleich. Local higher-order graph clustering. In Proceedings of the 23rd ACM SIGKDD International Conference Knowledge Discovery and Association for Computing Machinery, 2017.
Data Mining, pp.
Wayne W Zachary. An information flow model for conflict and fission in small groups. Journal of anthropological research, 3354):452-473, 1977.
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.
Xueqian Zhao, Zhuo Feng, and Cheng Zhuo An efficient spectral graph sparsification approach scalable reduction of large flip-chip power grids. In The IEFF/ACM International Conference on Computer-Aider Design, ICCAD, pp. 218-223. IEEE, 2014.
12

---

Under review as a conference paper at ICLR 2022
Xueqian Zhao, Lengfei Ian, and Zhuo Feng. A performance-guided graph sparsification approach scalable and robust spice-accurate integrated circuit simulations. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 34(10):1639--1)))
2015.
Zhiqiang Zhao and Zhuo Feng. spectral graph sparsification approach scalable vectorless power grid integrity verification. In Proceedings of the 54th Annual Design Automation Conference, DAC, pp. 68:1-68:66 ACM, 2017.
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 Leamiin, pp. 11458-18 1468. PMLR, 2020.
13

---

Under review as a conference paper at ICLR 2022
A APPENDIX
A. I
BASELINE METHODS
We use the following graph sparsification methods as baselines for our experiments. The implementa- tions are from Networkit (Staudt et al., 2015) with their default settings.
Random Edge (RE): RE randomly prunes a given percentage edges.
Local Degree (LD) (Hamann et al., 2016): For each node E V, the edges in the top
(c are kept in G', where a [0. 1].
Edge Forest Fire (EFF) (Hamann al., 2016): Based the Forest Fire node sampling algorithm (Leskovec & Faloutsos, 2006), a fire is started at a random node and burns approximately p/ p1-pp) neighbor, where is the probability threshold of burning neighbor. Any burnt neighbors are added to queue to also have a fire started on them. It prunes edges
based on the number of times each edge was visited.
A Algeraic Distance (AD) (Chen & Safro, 2011): Based on random walk distance, the algebraic distance a(u, v) between two nodes is low if there is a high probability that random walk starting from u will reach v using a small number of hops. It uses au, v) the edge score so that short-range edges are considered important.
I--ppar (LS) (Satuluri et al., 201 1by: L. applies the Jaccard similarity function to nodes u and v's adjacency lists to determine the score of edge (u, v). then ranks edges locally (w.rt each node) and prune edges according to their ranks.
Simmelian Backbone (SB) (Nick et al., 2013): SB mcasures each edge vu.v)'s Simmelian- ness weight via the shared neighbors of u and Then, for each u, it ranks its neighbors w.r.t the edge weights in descending order. During sparsification, SB will prune each node's s lower ranked edges according given edge-prune ratio.
Quadrilateral Simmelian Backbone (QSB) (Nocaj el al., 2014): QSB measures each edge (u, v)'s Simmeeiannness weight via the shared quadrangles of u and v. Then, follows the same pruning strategy as that of SB.
14


Reviews:
[{"review_id": "s7Naud7MYbY", "reviewer": "Reviewer_eytn", "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": "Strengths:\n\n- Graph sparsification is a useful technique to support efficient processing of big graphs for various applications that may depend on specific graph properties but may not require the presence of entire original graph structure. Further, the proposal of automated learning framework to perform sparsification aligns with recent advances in using reinforcement learning techniques for combinatorial optimization problems [1].  Hence this work will be of interest to the community.\n- Compared to baselines that are designed to focus on preserving specific properties, the proposed approach is able to support preserving arbitrary properties as long as they can be encoded in the form of a reward function.\n- The approach depends on the number of edges in the sampled subgraph of preprocessed sparsified graph, but does not depend on size of original graph which is a plus and may provide some gains over computationally expensive sampling methods \n- Empirically, the approach is shown to perform well compared  to all baselines across all settings \n- Authors present discussion on time vs performance tradeoff which is quite useful to discern some understanding on the time complexity.\n\n\nWeaknesses:\n\n- The overall approach of using reinforcement learning for optimization of transforming graphs or obtaining a substructure of graph while preserving some properties is not entirely novel. The authors are encouraged to refer to the approaches in [1] and compare and contrast how their approach is novel compared to other Q learning based approaches for performing optimization problems on graphs\n- The description of overall approach is not clear and misses some details due to which it is hard to discern whether the performance of the method is due to the pre-processing and other sparsification parameter choices (size of H, T_max, etc) or outcome of learning itself. Better description, ablation studies and hyper-parameter sensitivity analysis  can help with this. Also, the overall approach of pre-pruning and sampling subgraphs from pre-pruned graph to induce POMDP is very adhoc and the authors need to describe the rationale behind these choices and analyze how it affects the performance. \n- Following are some specific questions related to that: \n1. The effect of pre-pruning the graph is not clear and needs to be analyzed more. Also, as T is taken to be a very small number during training, it seems like the pre-pruning is almost always dominated by p and a significant number of edges are already pruned at the start of episode. Doesn’t this lead to situation where some edges are never part of the pre-pruned graph and hence not seen during training? Why is small T useful?\n2. How does node degree input contribute to the overall performance. Given that the three metric used to compare the performance are directly relevant to the node degree, is that most important factor for the performance?\n3. Could the authors elaborate more on what they mean by “allows agent to start in any part of state space without pruning T_p edges”. Doesn’t the approach pre-prune T_p edges?\n\n\n- The baselines are not particularly optimized for preserving the graph properties on which they are compared which is clear disadvantage for them.\n- It is important to compare with [2] and [3] even when they do not particularly perform edge removal. [2] performs representation learning but it has ability to sample sparse graph and also displays them in that paper. Comparing the performance of current approach agains such graph is important. For [3], while it allows edge generation, the overall performance need to be compared with this method as baseline as it will implicitly remove some edges and add others, thereby potentially better capturing the properties while reducing overall number of edges significantly. \n- It is important to show visualization of the original graph and sparse graphs (may be a useful subgraph) to illustrate property preservation such as communities.\n- From the tables, it is seen that some edge kept ratios (e.g. in Email datatset) have higher variance in performance across ratios compared to other settings. Can the authors elaborate on why this is the case?\n- As the experiments were done for 8 runs, it is useful to plot the error bars/ deviation across runs to get clear picture of performance.\n\nOther comments:\n\n- Two major claims of authors include better computational complexity than sampling methods and flexibility. For flexibility, I believe the authors limit to claim to the extent of being able to use same learning procedure with different reward function representing different properties. However, one would need to retrain from scratch for preserving each different property. Is that correct? For time complexity, while the authors provide some insights into the runtime of their own method, they need to provide rigorous comparison with complexity of other methods to support their claim.\n\n[1] Reinforcement Learning for Combinatorial Optimization: A Survey, Mazyavkina et. al., 2020\n\n[2] Robust Graph Representation Learning via Neural Sparsification, Zheng et. al. ICML 2020\n\n[3] Graph Sparsification with Generative Adversarial Network, Wu et. al. 2020\n", "summary_of_the_paper": "The paper focuses on the problem of graph sparsification - a problem of approximating an arbitrary graph with a sparse graph (specifically the one produced only by the  removal of edges in the context of this paper) while retaining the desired structural properties of the graph. Compared to previously proposed classical heuristics approaches or task specific learning approaches, the authors propose an automated learning framework for graph sparsification by considering edge removal as a sequential decision making process and solve it using Q learning. The learning procedure employs a preprocessing to sample initial state as a randomly sparsified subgraph to allow the agent to start at random parts of the state space. The state space is a subgraph and action is an edge that is to be removed. Within each  step of an episode, the action computation uses partial state information in the form of  sampled edges of the initial state graph and combination of degree of nodes and edge kept ratio (number of edges in sparse graph compared to original graph). Desirable properties that need to be retained are encoded in the form of reward function whose definition varies based on graph properties (page rank, shortest path and community structure in this paper). The architecture consists of node and edge encoders based on Graph Attention networks followed by a MLP based value function. Empirical evaluations are done on 6 different graphs with different characteristics and compared against representative classical baseline approaches for sparsification. Authors report performance based on correlation between the topological structure of sparsified and original graph with respect to the three properties mentioned above. The authors demonstrate that the proposed approach outperforms all baselines across different edge kept ratios and further discuss time vs performance tradeoff.", "summary_of_the_review": "The proposed work tackles an interesting problem and provides a useful technique to perform automated sparsification of graphs based on user required edge kept ratio and property specific objective. However, the overall  approach is not novel from previous works in reinforcement learning on graphs and the differing design choices are not discussed or analyzed adequately. Further some important comparisons are missing and it is not clear if this method can scale in performance critical applications as it is shown by the authors that time vs performance tradeoff is significant depending on size of sampled subgraph. Hence, this work is not ready for publication in its current form.", "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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "nhh1DfqGIK0", "reviewer": "Reviewer_zwSi", "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": "This paper is overall well-rounded and introduces a solid, novel technique for a problem which (to paraphrase the authors) has received surprisingly little attention in the machine learning community. This paper addresses graph sparsification as the primary problem of interest, which is in contrast to earlier works (e.g. GDPNet and NeuralSparse, cited in the paper) which successfully use graph sparsification as „means to an end“ for solving a downstream task more efficiently. The experimental evaluation does a great job at demonstrating superior performance to a wide range of baselines on a wide range of graph datasets. \n\nWhile I agree that using graph neural networks (GNNs) and reinforcement learning (RL) is novel for the particular task of graph sparsification as considered in this work, I wonder about the significance of this problem, given that other methods already successfully address graph sparsification to directly solve some kind of downstream task (e.g. GDPNet or NeuralSparse). I‘d recommend making a stronger argument for why this particular graph sparsification problem is important and why one cannot (or would not be advised to) directly optimize for the downstream task of interest. In its current form, I am unsure about the significance of this work — especially since an RL-based objective seems to be much more inefficient to train than the end-to-end differentiable graph sparsification technique (for a particular downstream task) introduced in NeuralSparse.\n\nWhile the paper is overall well-written, it requires some further improvements in clarity in order to meet the bar for acceptance. For example, the index „n“ in Q(s_t, a_n) on page 4 is never defined. The overall description of the model architecture and the information flow through the model/policy in section 4.3 is difficult to parse, and would benefit from a more explicit definition using mathematical notation and/or a model diagram that visualizes the technique on an example sub-graph. The visualization in figure 2 does not help much in understanding the information flow through the graph. I am also not sure how GAT is being applied on directed graphs (since it is a method for undirected graphs). The notation in Eq. 1, page 5 is also unclear: f_SparRL is called a Q-value function but seems to correspond to a list(?) of multiple individual Q-value functions. It is not clear what the notation „Q(s_t, a_0), …, Q(s+t, a_|H|)“ represents— a vector-valued output of dimension |H|? In algorithm 1, it is also unclear to me why T_p is chosen to be the minimum of |E|*p and |E|-T.\n\nExperimentally, I think the paper could be significantly improved by:\n1) considering a downstream task of interest (e.g. node classification, or one of the tasks mentioned in the introduction) and showing that the proposed sparsification technique is competitive with end-to-end techniques such as NeuralSparse\n2) ablating the choice of the GNN architecture: is attention necessary (e.g. what happens if we use a GCN [Kipf&Welling, ICLR2017] instead of GAT)? Is a GNN even necessary or does a single edge-based embedding function suffice?\n3) reporting variance in the results over multiple seeds. This is absolutely crucial for a technique that involves multiple levels of sampling and a reinforcement learning target.\n\nLastly, it should also be discussed that the presented technique has to be trained and tested on the same graph and would not generalize if new nodes were added to a graph (since embeddings are learned for every single node). \n", "summary_of_the_paper": "This paper introduces a method for graph sparsification using graph neural networks and reinforcement learning. The goal for graph sparsification considered in this work is to find edges so that certain global graph statistics are preserved upon removal of these edges from the graph. The authors use a single layer of a graph attention network to encode local graph structure and learn to predict an action-value function, following the framework of Q-learning, where actions correspond to the removal of a particular edge. The method is compared against several baseline heuristics and compares favorably on several small- to medium-scale network datasets (without node or edge features) in terms of preservation of graph statistics such as PageRank.", "summary_of_the_review": "In summary, while I think that this paper is well-rounded and introduces a novel technique that outperforms a wide range of baselines, I am unsure about the significance of the considered problem. The paper has lots of headroom for improvement in terms of clarity and in terms of the experimental evaluation, which would help clarify its significance, the reliability of the results, and the necessity of core architecture choices (by adding additional ablation studies). Overall, I think that this paper is not ready for publication in its current form, but I am positive that many of the described issues can be addressed in a (potentially major) revision.\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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "lfG6VudXC7J", "reviewer": "Reviewer_AdUd", "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": "Major comments:\n- As the submitted paper is application-oriented, the authors should explain more of implementation details. Elaboration of certain details are indispensable for the clarity and novelty of this work. Here are some examples:\n     -  page 4, section 4.2: \"Each time step ... ... to avoid sparse rewards\". Under what circumstances do sparse reward appear? Is not the experiment involved episodic? If the experiment is episodic, then why does evaluating reward at each time step contribute to the purpose of \"avoiding sparse rewards\"? \n     -  page 4, section 4.3: what particular neural network structure the authors use to represent sparsification policy?\n     -  page 8, equation (4): how do authors address the cases when $\\mathrm{dist}(u,v)_{\\mathrm{G}'} = \\infty$ due to the removal of an edge\n\n-  What is $|H|$ in algorithm 1? This particular notation is not defined.\n\n- One main advantage of the proposed method over $t-$spanner is the guarantee of edge reduction ratio in the output graph. I find the description of the edge sparsity control confusing in algorithm 1 on page 4. Say, the edge reduction ratio is $p=0.5$ and the sampling ratio is correspondingly $1-p$, why in algorithm 1 that $p$ is \"randomly sampled\"? Should not this be an input quantity? \n\n  Considering the size of network studied in this paper, the motivation of setting $T_{\\text{max}} = 8$ is not clear to me.\n\n- Table 5 on page 9: Now that ($x%$%) means edge kept ratio, why when comparing SparRL with $t-$spanner, the edge-kept ratio is set so high? On which dataset is this comparison carried out?\n\n- A few places where I find the description in accurate:\n     - page 6, definition of $r_{\\textrm{PR}}$: should not the expression in this definition the loss instead of the \"reward\"?\n     - page 8, equation (4), definition of $r_{\\textrm{SPSP}}$: should not the expression in this equation the loss for single-pair shortest distance preservation instead of 'reward'?\n\nMinor comments:\n  I recommend the author revise some notations (for example, maybe not use '$*$' to mean multiplication) and grammar errors in the writeup.", "summary_of_the_paper": "This paper discusses the protocol \"SparRL\", which is a reinforcement learning driven technique for sparsifying graphs to a given edge reduction ratio while preserving the graph structure. \n\nIn this RL-driven graph sparsifying protocol, the authors describe the edge reduction process as a Markov dynamic process and leverage the double deep Q-learning technique to represent the value function, thus conducting policy learning.\n\nFor evaluating the effectiveness of graph sparsification techniques, the authors investigate aspects of PageRank preservation, community structure preservation and shortest path distance preservation. The authors benchmark the proposed RL-driven methods with several methods in literature.", "summary_of_the_review": "The paper is not well written in terms of the lack of clarity in stating technical details and the unconvincing presentation of simulation results. Please refer to Main Review session for point-by-point questions.\n\nThe paper is not ready to be published.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "cUrdpWbqi_", "reviewer": "Reviewer_na7w", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Currently, learning based graph sparsification is still beyond the scope of this study area. The paper provides some new insights to graph sparsification and takes an initial step towards learning-based graph sparsification. Apparently, learning-based graph sparsification should be a promising direction for graph representation learning and graph neural network, where scalability is a bottleneck. \n\n1. The work is a novel application of deep reinforcement learning on graph sparsification and technically sound from the perspective of graph sparsification.\n\n2. Besides, the paper conducted a relatively thorough experiment to demonstrate the effectiveness and efficiency of the proposed SparRL framework. I like the empirical analysis of SparRL components, where gives different pruning strategy and expert control mechanisms are validated.\n\nA main constraint from my perspective:\n\nThe empirical validation (experiment section) was only performed on some toy datasets, where the largest dataset is Citeseer containing 3312 nodes and 4536 edges. The empirical validation don't conform to the motivation of graph sparsification and triggers a doubt on SparRL’s scalability on massive graphs, since graph sparsification usually servers as an approximation technique for massive graphs. Though authors claimed that the effectiveness of SparRL is independent from the size of graphs, it would be more convincing to demonstrate it on massive graphs, where #nodes should be more than millions.", "summary_of_the_paper": "This paper proposes a learning-based graph sparsification framework (SparRL) using reinforcement learning and imitation learning. The proposed framework is task-adaptive and performs well under several evaluation metrics like PageRank, community structure, and pairwise shortest-path distance. ", "summary_of_the_review": "The paper provides a novel RL framework for learning based graph sparsification. The work is technically sound and well-organized in writing, However, empirical validation on large-scale graphs is missing, which prevents me from an acceptance decision.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents an RL approach to the problem of graph sparsification. The reviewers expressed concerns about novelty, presentation, the correctness of some claims, and experimental validation. While the authors provided rebuttal and addressed some questions (leading to the increase of the score), some reviewers thought the authors focused on a justification of why suggested experiments were not done rather than doing them. We believe the paper in its current state is below the bar and recommend rejection.
Decision: Reject