Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper proposes a neural network based algorithm for edge rewiring. 
main_review: Strengths

a new approach based on neural networks. 

Weaknesses

The main motivation is to improve the robustness of infrastructure networks such as power networks.  While rewiring an edge sounds straightforward on a graph, it is tremendously difficult in a physical network, e.g. adding a new road or a new power line. Furthermore, the functionality of a physical network is beyond nodes and links. For example, for a power network, power flow is determined by power flow equations. So considering the graph structure alone, without the dynamics of the systems, is not sufficient. 
summary_of_the_review: The problem is not very motivated.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies how to improve network resilience by proposing a reinforcement learning-based framework named **ResiNet** and a new GNN architecture called **FireGNN**. The proposed framework is able to directly generalize to unseen graphs. The new GNN architecture applies the graph filtration process, which enhances the expressivity of GNN. The authors conduct experiments on synthetic and real datasets to compare the proposed framework with previous baseline methods.
main_review: Strengths:

1. The proposed reinforcement learning based framework is suitable for the rewiring task. Meanwhile, the framework can generalize to unseen graphs since the edge rewiring policy can be directly applied to other graphs.

Weaknesses:

1. My main concern is the empirical performance of the proposed framework. Specifically, the proposed framework performs much worse than baseline approaches on large graphs (BA-100 dataset, EU dataset) as shown in Table 1. Also, the improvements on BA-15 dataset and BA-50 dataset are not significant. 

Questions and suggestions:

1. I suggest the authors put the ablation study on the FireGNN and the new framework. For example, what is the performance of ResiNet using a standard GNN architecture (not using FireGNN)? What is the performance of replacing standard GNN with FireGNN in the previous method (not using the RL-based framework ResiNet)? These may help better understand the role of the architecture and the RL-based framework.

2. As mentioned in Section 4.2 (Page 8), 'Note that this comparable performance is under a much fewer number of rewiring operations.' Could the authors provide the number of rewiring operations of each method in Table 1? 

3. As mentioned in Section 3.3.1 (Page 6), 'where $G^{(k)}$ denotes the remaining graph after removing $N-k$ nodes in a particular task-dependent order'. Could the authors clarify how the task-dependent order is determined? 

Typo:

1. $d_i = \sum_{i=1}^{N}A_{ij}$ in Section 3.1 (Page 4).
summary_of_the_review: This paper proposes a new RL-based framework together with a new GNN architecture for improving network resilience. The new frameworks can generalize to unseen graphs. However, the empirical performance of the framework is not convincing on the tasks considered in this paper. 


=============================after response=============================

The updated results in the revision resolve some of my main concerns. I decide to raise my recommendation score from 5 to 6.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper proposes a neural approach that increases network resilience by edge wiring. The approach uses a combination of graph neural network (GNN) and policy gradient method to do so. The experiments use a few small networks and several non-neural baselines. 
main_review: Positives:

+ The problem is relevant. In particular, the idea of neural approaches to increase network resilience is interesting. 
+ The paper is easy to follow.

Negatives:

-  Method: The paper overclaims a bit. Among the three major points in the introduction (utility, local optimality, and transductivity); the last two are already addressed by previous methods that use reinforcement learning with graph neural networks (GNNs). Please refer to the survey [1] and especially [2]. It is also a little surprising to see the paper is not positioned in the context of those existing works that are very similar [1] in terms of frameworks. Given those, It is difficult to assess the additional technical novelty of the proposed method. The paper could be improved by focusing on specific challenges (such as scalability) that the rewiring problem has while working with this framework. The proposed method's efficiency is also unclear as there is no analysis of efficiency. 

[1] Mazyavkina, Nina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. "Reinforcement learning for combinatorial optimization: A survey." Computers & Operations Research (2021): 105400.
[2] Dai, Hanjun, Elias B. Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. "Learning combinatorial optimization algorithms over graphs." NeurIPS, 2017.


- Experiments: The experiments can be significantly improved.

a) The experiments have small datasets. Besides they are mostly synthetic. From Table 1, it is also difficult to say that the proposed method, ResiNet is a superior method.

b) There is no comparison with non-neural approaches in terms of efficiency. One of the major reasons for going to the neural version is to be able to test on big data while training on small ones. The neural approaches might be able to outperform the non-neural methods at least in terms of efficiency.

 c) There are no comparisons with other neural baselines that address graph combinatorial problems via neural approaches especially the ones which use reinforcement learning.

d) Why are the number of rewired edges not being compared among different methods? The paper claims that the proposed method uses a low number of edges to rewire to achieve high network resilience.



 - Motivation:
The motivation going into the neural version is not clear. Why will someone use a neural algorithm compared to the non-neural ones? The context where the algorithm needs to be used repetitively might motivate this in a better way (please refer to Khalil et al., NeurIPS, 2017). Could you provide other types of use cases?
summary_of_the_review: The novelty of the proposed method is unclear and the experiments need major improvement.
review_title: null

Meta-review: The paper proposes an RL technique for dealing with the problem of network (graph) rewiring for robustness against attacks. Graph rewiring has been studied in a variety of fields, including graph theory (graph abstraction), graph ML (adversarial robustness, performance of GNNs), and combinatorial optimization. Reviewers had concerns with novelty, the correctness of some of the statements, and empirical evalution (in particular, baselines and scalability). While the rebuttal addressed some of the concerns, the overall feel about the paper is lukewarm and the AC believes the paper is below the bar.
Decision: Reject