Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: 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.
main_review: Strengths:

- 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.
- 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.
- 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 
- Empirically, the approach is shown to perform well compared  to all baselines across all settings 
- Authors present discussion on time vs performance tradeoff which is quite useful to discern some understanding on the time complexity.


Weaknesses:

- 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
- 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. 
- Following are some specific questions related to that: 
1. 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?
2. 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?
3. 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?


- The baselines are not particularly optimized for preserving the graph properties on which they are compared which is clear disadvantage for them.
- 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. 
- 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.
- 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?
- 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.

Other comments:

- 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.

[1] Reinforcement Learning for Combinatorial Optimization: A Survey, Mazyavkina et. al., 2020

[2] Robust Graph Representation Learning via Neural Sparsification, Zheng et. al. ICML 2020

[3] Graph Sparsification with Generative Adversarial Network, Wu et. al. 2020

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.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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. 

In 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.

For 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.
main_review: Major comments:
- 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:
     -  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"? 
     -  page 4, section 4.3: what particular neural network structure the authors use to represent sparsification policy?
     -  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

-  What is $|H|$ in algorithm 1? This particular notation is not defined.

- 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? 

  Considering the size of network studied in this paper, the motivation of setting $T_{\text{max}} = 8$ is not clear to me.

- 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?

- A few places where I find the description in accurate:
     - page 6, definition of $r_{\textrm{PR}}$: should not the expression in this definition the loss instead of the "reward"?
     - 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'?

Minor comments:
  I recommend the author revise some notations (for example, maybe not use '$*$' to mean multiplication) and grammar errors in the writeup.
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.

The paper is not ready to be published.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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. 
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. 

1. The work is a novel application of deep reinforcement learning on graph sparsification and technically sound from the perspective of graph sparsification.

2. 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.

A main constraint from my perspective:

The 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_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.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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.
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. 

While 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.

While 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.

Experimentally, I think the paper could be significantly improved by:
1) 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
2) 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?
3) 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.

Lastly, 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). 

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.
review_title: null

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