Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: ##########################################################################

Summary:
The paper proses a new adversarial (poisoning) defense based on a known graph reweighting scheme known as the ricci curvature. The ricci curvature assigns a weight to each edge that captures the graph structure, i.e. the value reflects whether the edge is an inter-community connection or an intracommunity connection. Empirically, the ricci curvature is known to be more robust w.r.t. random edge insertions/deletions. The authors propose a new sampling method based on the ricci curvature and use it within their novel training scheme. Empirically, the effectiveness of their approach is shown via experiments on synthetic SBM graphs. Moreover, the authors use a random attack and Metattack on various datasets. They show superior performance to multiple baseline architectures/defenses.
 
##########################################################################

Reasons for rating:

Overall it is an interesting work and the empirical performance seems to be good. However, neglecting the very weak random attack and the experiment on synthetic data, the authors effectively only evaluate against one strong attack. Hence, the question arises if the defense is solely effective against the characteristic of Metattack? I would recommend to add at least one further strong attack.

Furthermore, it is not clear if a transfer attack is used (a surrogate used for Metattack). It would be very interesting to see if the ricci curvature calculation itself is adversarially robust. In the chosen setup this fact is obfuscated.

Last, the authors cite but do not compare to the Curvature Graph Network which also uses ricci curvature instead of the widely used symmetric normalization of the adjacency matrix (e.g. as a GCN). Hence, it is not clear to the reader if the sampling scheme/training scheme or the ricci curvature is the major reason for adversarial robustness.
 
##########################################################################

Pros:
+ Interesting and promising approach
+ Consistently improved performance over the baselines
+ Interesting analysis of their defense via SBM graphs


Cons:
- Only one strong attack on real-world graphs is used to benchmark to other architectures.
- Is the ricci curvature itself robust w.r.t. adversarial attacks? The authors seem to use transfer attacks and the referenced literature claims only robustness against random attacks and this is also only evaluated empirically.
- Curvature Graph Network should be added as a baseline.
- The authors do not discuss the space and time complexity. Only the time cost for the ricci curvature is discussed. Moreover, the authors use the two-hop neighborhood for adding potential edges — this can still be very expensive specifically for power-law graphs. A discussion would be appreciated.

Further points:
- The proposed sampling based training scheme seems to be highly related to adversarial training. The authors should add a corresponding discussion.
- The paper lacks clarity at some points and has inconsistencies in notation. For example, in Section 2 "F" is not introduced. S denotes the geodesic distance (aka length of shortest path) which is denoted by d(x, y) in Section A.
- At some points the authors say that a graph is sampled in each "iteration" (epoch) and sometimes for every layer.
- Figure 2: What is H_0, H_1, L?
- Section 1.1: The authors should make clear that Figure 3 is an example and does not imply superior robustness in general.
- What are the limits of ricci curvature? Beyond some level of perturbation, there should be a tipping point (i.e. communities cannot be distinguished anymore).
- Related work: There are many more (relevant) attacks/defenses. Please add them and/or make clear that your discussion is not exhaustive. 

review_title: Official Review

final_score: rating: 5: Marginally below acceptance threshold
review_content: Strengths: 

The paper is well written and clean. 

Weaknesses: 

I have several concerns regarding this paper. 

•	Novelty. The authors propose to use Ricci flow to compute the distance between nodes so that to sample edges with respect to that distance. Using Ricci flow for distance computation is a well-studied area (as indicated in related work). The only novel part is that each layer gets a new graph; however, this choice is not motivated (why not to train all layers of GNN on different graphs instead?) and has problems (see next). 

•	Approach. Computing optimal transport distance is generally an expensive procedure. While authors indicated that it takes seconds to compute it on 36 cores machine, it’s not clear how scalable this method is. I would like to see whether it scales on normal machines with a couple of cores. Moreover, how do you compute exactly optimal transport, because the Sinkhorn method gives you a doubly stochastic matrix (how do you go from it to optimal transport?). 

•	Algorithm. This is the most obscure part of the paper. First, it’s not indicated how many layers do you use in experiments. This is a major part of your algorithm because you claim that if an edge appears in several layers it means that it’s not adversarial (or that it does not harm your algorithm). In most of the baselines, there are at most 2-3 layers. There are theoretical limitations why GNN with many layers may not work in practice (see, the literature on “GNN oversmoothing”). Considering that you didn’t provide the code (can you provide an anonymized version of the code?) and that your baselines (GCN, GAT, etc.) have similar (or the same) performance as in the original papers (where the number of layers is 2-3), I deduce that your model Ricci-GNN also has this number of layers. With that said, I doubt that it’s possible to make any conclusive results about whether an edge is adversarial or not with 2-3 graphs. Moreover, I would expect to see an experiment on how your approach varies depending on the number of layers. This is a crucial part of your algorithm and not seeing discussion of it in the paper, raises concerns about the validity of experiments. 

•	Design choices. Another potential problem of your algorithm is that the sampled graphs can become dense. There are hyperparameters \sigma and \beta that control the probabilities and also you limit the sampling only for 2-hop neighborhoods (“To keep graph sparsity, we only sample edges between pairs that are within k hops of each other in G (we always take k = 2 in the experiments).” This is arbitrary and the effect of it on the performance is not clear. How did you select parameters \sigma and \beta? Why k=2? How do you ensure that the sampled graphs are similar to the original one? Does it matter that sampled graphs should have similar statistics to the original graph? I guess, this crucially affects the performance of your algorithm, so I would like to see more experiments on this. 

•	Datasets. Since this paper is mostly experimental, I would like to see a comparison of this model on more datasets (5-7 in total). Verifying on realistic but small datasets such as Cora and Citeseer limits our intuition about performance. For example, Cora is a single graph of 2.7K nodes. As indicated in [1], “Although small datasets are useful as sanity checks for new ideas, they can become a liability in the long run as new GNN models will be designed to overfit the small test sets instead of searching for more generalizable architectures.” There are many sources of real graphs, you can consider OGB [2] or [3]. 

•	Weak baselines. Another major concern of the validity of the experiments is the choice of the baselines. Neither of GNN baselines (GCN, GAT, etc.) was designed for the defense of adversarial attacks, so choosing them for comparison is not fair. A comparison with previous works (indicated in “Adversarial attack on graphs.” in related work section) is necessary. Moreover, an experiment where you randomly sample edges (instead of using Ricci distance) is desirable to compare the performance against random sampling. 

•	Ablation. Since you use GCN, why the performance of Ricci-GCN is so different from GCN when there 0 perturbations? For Citeseer the absolute difference is 2% which is quite high for the same models. Also, an experiment with different choices of GNN is desirable. 

•	Training. Since experiments play important role in this paper, it’s important to give a fair setup for the models in comparison. You write “For each training procedure, we run 100 epochs and use the model trained at 100-th epoch.”. This can disadvantageous for many models. A better way would be to run each model setup until convergence on the training set, selecting the epoch using the validation set. Otherwise, your baselines could suffer from either underfitting or overfitting. 

[1] https://arxiv.org/pdf/2003.00982.pdf
[2] https://ogb.stanford.edu/
[3] https://paperswithcode.com/task/node-classification

==========

After reading the authors comments.

I applaud the authors for greatly improving their paper via the revision. Now the number of layers is specified and the explanation of having many sampled graphs during training is added, which was missing in the original text and was preventing a full understanding of the reasons why the proposed approach works. Overall, I am leaning toward increasing the score.

I still have several concerns about the practicality of Ricci-GNN. In simple words, the proposed approach uses some metric S (Ricci flow) that dictates how to sample graphs for training. The motivation for using Ricci flow is “that Ricci flow is a global process that tries to uncover the underlying metric space supported by the graph topology and thus embraces redundancy”. This claim cites previous papers, which in turn do not discuss what exactly is meant by “a global process that tries to uncover the underlying metric space”. Spectral embeddings also can be considered as a global metric, so some analysis on what properties of Ricci flow makes it more robust to attacks would be appreciated. Also including random sampling in comparison would confirm that the effect is coming not from the fact that you use more graphs during the training, but from how you sample those graphs. In addition, as the paper is empirical and relies on the properties of Ricci flow which was discussed in previous works and was not addressed in the context of adversarial attacks, having more datasets (especially larger ones) in the experiments would improve the paper.
review_title: The work presents a method to defend against the addition or removal of adversarial edges. The problem formulation is clear and the paper is easy to read; however, the current version of the paper has many weaknesses, so it requires revision. 

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary:
In Ricci-GCN new graphs are resampled in each iteration of the training phase based on the Ricci flow metric. The Ricci flow incorporates curvature information and captures the intrinsic geometry of the graph. Compared to e.g. spectral embedding it is more robust to structural perturbations. This leads to improved robustness against adversarial attacks on the graph structure.

Reasons for score: 
Overall, I vote for accepting. The idea is well motivated, the paper is well written, and the experiments show a clear increase in robustness on real data. My major concern is not using an adaptive attack to evaluate robustness (see weak points). 

Strong points:
* The main idea of using Ricci flow is interesting, well motivated and well executed.
* Evaluation on SBM graphs helps with better understanding why the proposed approach works.
* The comparison to other metrics (Spectral and HC) is appreciated.

Weak points:
* It is not clear whether META (the meta-learning attack) is computed w.r.t. the vanilla GCN or the Ricci-GCN. If META was run on the original GCN it is not clear whether the attack is not successful because Ricci-GCN is more robust or because the adversarial edges found for GCN are not transferable to Ricci-GCN. Since the proposed defense is only heuristic (not certifiable) in order to show robustness it has to be evaluated against an adaptive attacker that takes the defense into account [1]. Otherwise, an adaptive attacker may easily break the defense in the future. For example, META can be adapted to account for the Ricci flow. If META was indeed run on Ricci-GCN, the author should discuss the details, e.g. whether they use the reparametrization trick to compute the gradients through the sampling.
* The gain in robustness is only significant for large perturbation rates (>0.1) which might not correspond to realistic threat models in practice, e.g. for perturbation rates <0.1 GCN-SVD is on par with Ricci-GCN.
* One interpretation of the proposed approach is that Ricci-GCN is doing (a specific type of) data augmentation which is known to improve generalization and by extension the clean and the adversarial accuracy. For example, one augmentation in [2] is to randomly sample edges to add or remove, and in [3] edges are randomly dropped. Even though [2] and [3] are not motivated by robustness they are a relevant baselines since similar to Ricci-GCN they generated different graphs during training.
* A big drawback of the proposed approach is the large number of hyperparameters: \gamma=0.5, p=2, k=2, \sigma, \beta, etc. It this is not clear how sensitive is the method to these choices or to the definition of the "probability measure of each neighborhood".
* Ignoring the random attack which extremely weak, the evaluation is limited to a single attack (META).  Evaluating against other attacks (see [4] and [5]) would help to better evaluate the robustness of the model. 

Question for the authors:
1. How robust is Ricci-GCN to adaptive attacks? (see weak points) 
2. How does Ricci-GCN compare to other data augmentation techniques (see weak points) 
3. Is sampling performed only during training? If so are there any benefits to also sampling during inference (and aggregating the predictions)? Can sampling during inference help defend against evasion attacks such as Nettack?
4. Is there any improvement if we are willing to pay the price of decreased sparsity, take k larger than 2?
5. Why is the row for perturbation rate of 0 omitted from Table 3? Where the hyperparameters tuned separately for Spectral and HC?

Additional feedback that did not affect the decision:
* The related work should also discuss the difference between certifiable and heuristic defenses and how the proposed approach fits in this context.
* It would be nice to quantitatively show "The probability of edges in the original community
structure are higher than the attack edges"
* It would be beneficial to provide a reference or evidence for the claim "generally lacks descriptive power to provide desirable resolution and differentiation". While the results in Table 3 provide indirect evidence, it is not clear that this is due to "lack of descriptive power".
* It would be interesting to see whether Ricci-GCN is also more certifiably robust than vanilla GCN, e.g. by computing model agnostic certificates such as [6]. 

Typos:
* Figure 5 Captions: Purterbation Rate 

## After Rebuttal
The authors' response clarified some of the issues and partially addressed some of my concerns. Based on this and the remaining reviews I have decided to keep the score unchanged.

One additional comment regarding the evaluation: In the authors' response they state "Finally, we would like to point out that it is common practice to use GCN as a subroutine for Meta-attack against different defense methods. This was shown in the original Meta-Attack paper, as well as multiple follow-up defense papers." I would like to again point out that the fact that this is a common practice is not ideal, even though multiple follow-up defense papers use the same strategy. We have already learned the lesson in the computer vision literature that adaptive attacks are the least we can do to evaluate heuristic defenses (see [1]) and even that might not provide strong evidence.

References:
1. Tramer, Florian, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. "On adaptive attacks to adversarial example defenses."
2. Wang, Yiwei, Wei Wang, Yuxuan Liang, Yujun Cai, Juncheng Liu, and Bryan Hooi. "NodeAug: Semi-Supervised Node Classification with Data Augmentation."
3. Rong, Yu, Wenbing Huang, Tingyang Xu, and Junzhou Huang. "Dropedge: Towards deep graph convolutional networks on node classification."
4. https://github.com/gitgiter/Graph-Adversarial-Learning
5. https://github.com/safe-graph/graph-adversarial-learning-literature
6. Bojchevski, Aleksandar, Johannes Klicpera, and Stephan Günnemann. "Efficient robustness certificates for discrete data: Sparsity-aware randomized smoothing for graphs, images and more."
review_title: The robustness evaluation could be improved 

Meta-review: The paper proposes a new defense against adversarial attacks on graphs using a reweighting scheme based on Ricci-flow. Reviewers highlighted that the paper introduces interesting ideas and that the use of Ricci-curvature/flow is a novel and promising contribution. Reviewers also recognized that the paper has significantly improved after rebuttal and clarified some aspects of their initial reviews.

However, there exist still concerns around the current version of the manuscript. In particular, important aspects of the method and algorithm, as well as some design choices are currently unclear. This includes evaluating and discussing robustness, training method, and practicality/improvements in real-world scenarios. I agree with the majority of the reviewers that the current version requires an additional revision to iron out the aforementioned issues. However, I also agree with the reviewers that the overall idea is promising and I'd encourage the authors to revise and resubmit their work with considering the feedback from this round of reviews.
Decision: Reject