Ricci-GNN: Defending Against Structural Attacks Through a Geometric Approach
Authors: Ze Ye
Tengfei Ma
Chien-Chun Ni
Kin Sum Liu
Jie Gao
Chao Chen
Venue:  (2021)
Keywords: Deep Learning
Graph Convolution
Ricci Flow
Robustness

Abstract: Graph neural networks (GNNs) rely heavily on the underlying graph topology and thus can be vulnerable to malicious attacks targeting at graph structures. We propose a novel GNN defense algorithm against structural attacks that maliciously modify graph topology. In particular, we discover a robust representation of the input graph based on the advanced theory of graph Ricci flow, which captures the intrinsic geometry of graphs and is robust to structural perturbation. We propose an algorithm to train GNNs using re-sampled graphs based on such geometric representation. We show that this method can be effective to protect against adversarial structural attacks. Our method achieves state-of-the-art performance on synthetic and real datasets against different types of graph poisoning attacks.

Under review as a conference paper at ICLR 2021
RICCI-GNN: DEFENDING AGAINST STRUCTURAL AT- TACKS THROUGH A GEOMETRIC APPROACH
Anonymous authors Paper under double-blind review
ABSTRACT
Graph neural networks (GNNs) rely heavily the underlying graph topology and thus can be vulnerable to malicious attacks targeting at perturbing graph structures. We propose novel GNN defense algorithm against such attacks. In particular, we use a robust representation of the input graph based on the theory of graph Ricci flow, which captures the intrinsic geometry of graphs and is robust to structural perturbation. We propose an algorithm to train GNNs using re-sampled graphs based on such geometric representation. We show that this method substantially improves the robustness against various adversarial structural attacks, achieving state-of- of-the--thtthee performance on both synthetic and real worldworld datasets.
INTRODUCTION
Recent years have witnessed the success of graph neural networks (GNNs) many graph applications including graph classification (Xu et al. 2019b), node classification (Kipf & Welling 2016 Veličković et al. 2018). graph generation You et al. 2018) and recommendations (Ying et al. 2018) As GNNs have shown great potentials, their vulnerability to adversarial attacks (Szegedy al. 2014 Goodfellow et al., 2015) becomes serious concern that hinders their deployment real life critical applications. For example, GNN algorithm for fraud detection in financial transaction graphs (Wang et al., 2019a) needs be robust against attacks aiming at disguising fraud transactions as normal ones. In health informatics, prediction of polypharmacy side effects (Zitnik et al. 2018) must be robust against attacks that intend to endanger certain patients. a recommendation system, the developers need to consider potential attacks from spammers who may create fake followers to increase the influence scope of fake news (Zhou & Zafarani 2018).
One way attack GNN model is to modify the graph topology by inserting or deleting edges (Jin et al.) 2020a). A small perturbation of the network topology can significantly impair the graph neural network's ' performance (Dai al. 2018 Zügner & Günnemann 2019b). For example, Meta- Attack (Zügner & Günnemann 2019a) can increase the misclassification rate of GCN on a political blog data set by over 18% with only 5% perturbed edges. This is not surprising as graph topology is essential for GNNs, both as the backbone of a GNN architecture and as important structural features. In particular, the local neighborhood of each node commonly used define receptive fields for the convolution operator. The statistics of local neighborhood, e.g., node degrees, are important structural information used as additional node features (Veličković al. 2018) re-calibrate the convolutional operation (Kipf & Welling 2016).
In this paper, we focus on defending against global poisoning adversarial attacks which corrupt the graph topology in the training phase. Some existing approaches assume the graph is true and leverage known robust training techniques, e.g., enforcing priors on latent representation of data (Zhu et al. 2019). These solutions can still be limited by the corrupted graph, considering how critical the underlying graph is for a GNN model. Other methods assume prior knowledge on the graph topology, and perform graph restructuring, e.g., via low-rank filtering (Entezari et al. (020)) or graph specification (Wu et al.) 2019). hoping to remove abnormal edges from the attack. These strong priors, although proven useful, also limit the generality of the method.

---

Under review as a conference paper at ICLR 2021
Ricei Curvaturo
Ricci flow metric
0.
Sampling ng
Graph 2
Graph
Graph 1
(a) Before Ricci (b) After Ricci flow flow
H
H1
Figure I: An illustrative example of Ricci curvature and Ricci flow on graphs. [(a) The bridge edges (red) between communities have negative curvature while the edges inside communities (blue) have positive. [(b] The same graph after Ricci flow, which length of edges are propoctional to weights (Ricci flow met- ric). Nodes within one community are moved closer whereas the two communitics are moved further apart.
An overview of Rieci-GNN, We first compute the Ricci flow metric from the input (at- tacked) graph and re-sample edges by using Gaus- sian filter on each node. A newly sampled graph is used for the training phase in each iteration of a stan- dard GCN.
Figure 2:
1.1 A GEOMETRIC VIEW OF GRAPHS
We take novel direction to find a robust representation of the graph topology through a geometric lens. We view a discrete graph continuous framework, which nodes stay in an underlying metric space and the connectivity of two nodes has stochastic nature, depending the features of the two nodes, their respective neighborhoods and the entire node distribution. The input graph G is replaced by ensemble of graphs, considered (randomized) discrete realizations of the same underlying metric space in which G is taken. In order to do that, we recover the metric distance between two nodes in the underlying space through the Ricci flow metric the input graph G. Note that we are not trying to explicitly find an embedding which would involve choices (e.g, Euclidean vs Bunlducli,,,, dimensionalities) that introduce extra and unnecessary distortion. Instead, we represent the underlying metric space via pairwise geodesic distance between nodes.
Our geometrical approach inspired by the Riemmanian geometry in the continuous setting (Hamil ton 1982, Perelman (2002). On a Riemmanian manifold, one can define Ricci curvature to measure the amount of "bending' or 'curving' at each point. With Ricci curvature, one can define diffusion process by changing the Riemannian metric (stretching or shrinking locally) such that curvature is uniform everywhere. This uniformization process called Ricci flow. This theory can be extended to graph setting (Ollivier, 2009). Generally speaking, edges that are locally well connected have positive curvature while edges that are locally sparsely connected have negative curvature. In Ricci flow, edges of negative curvature stretched (with increased edge weight) and edges of positive curvature are condensed (with decreased edge weight). These new edge weights that uniformize the Ricci curvature of the graph called the Ricei flow metric. See Figure for illustration. Graph Ricci curvature and Ricci flow can be used to identify critical edges in a graph (Ni et al.) 2015) Sandhu et al., 2015) and identify community structures (Ni al. [019 Sia et al. 2019). We also note that graph Ricci curvature has been used in GNN for node classification task (Ye et al. 2020). but not for defending structural attacks GNN.
Robustness against topological perturbation. Ricci flow metric has been shown to be robust to random deletion and addition of edges (Ni et al. 2018). This attributes the fact that Ricci flow is a global process that tries to uncover the underlying metric space supported by the graph topology and thus embraces redundancy. Compared to other graph metrics such as the hop count metric and metric obtained by spectral embedding, Ricci flow metric provides better trade-off between robustness and representation power of the graph metric, as shown in Figure 3 When two edges are deleted, the
Ricci flow metric is rarely affected (Figure (a)), similar to the hop count metric (Figure 3 (c)); while the distance metric by spectral embedding is substantially more sensitive (Figure (b)). We note that
the hop count metric is also robust to dynamic edge deletions due to the small world phenomena and multiple shortest paths in the graph; however the hop count metric takes only integer values and generally lacks descriptive power provide desirable resolution and differentiation.
2

---

Under review as a conference paper at ICLR 2021
Root
Root
Root
Distance Metric Variations
-20
min-33311%
min-+0.00m avg-+13.62' 02%
min avg-+0.00%
avg-+1.711%
(a) Ricci flow
(b) Spectral embedding
(c) Hop count
Figure 3: Changes in distance between all nodes and fixed root in karate club graph for (a) Ricci flow metric, (b) spectral embedding, and (c) hop count, when two edges (shown in red) are removed from the network. Vertices are colored proportional to the magnitude variations in distance.
To train GNN using the Ricci flow metric, generate ensemble of sample graphs G1, G2. and use new sample each network layer of the GNN of every training epoch (Figure Z). Therefore the trained model is enforced focus the underlying metric information represented by the graph (which much more robust) and not on the particular input graph topology (which could be corrupted) per se.
Our method is agnostic to both models and attacks, thus can be applied to different GNNs and different structural attacks. We show in both synthetic and real-world datasets that the proposed algorithm effectively defends against various structural attacks, with improved performance compared other defense schemes.
We summarize our contributions as follows.
We are the first take geometric view of the GNN defense problem. We propose train GNNs with the Ricci flow representation of graph instead of its attacked topology.
We design a new algorithm to sample graphs based on the Ricci flow representation for training GNN. This effectively alleviate the impact of structural attacks by adversaries.
We demonstrate the efficacy of our method various synthetic and real-world datasets, against state-of-the-art graph topology poisoning methods.
1.2
RELATED WORK
The vulnerability deep neural network models w.r.t. adversarial attacks is well known. And graph neural networks are not exception (Dai et al. 2018 Zügner al., 2018 Zügner & Günnemann 2019a). Here we briefly review the methods for attacking and defending against GNNs.
Adversarial attack graphs. There two categories of attacks: evasion attacks and poisoning attacks. Evasion attacks generate fake samples for the trained model in the testing time, while poisoning attacks directly modify the training data. Dai al.) (2018) employs a reinforcement learning based framework for non-targeted test-time attacks (i.e. evasion) on graph classification and node classification. The focus on the modifications of graph structures, and the attackers are restricted to edge deletions only. Zügner et al. (2018) consider both training training-time time (i.e. poisoning) and testing-tinn attacks. The attacks, called nettack, are based on surrogate model with both edge insertion and deletion. Nettack is a local attack, where the goal is to lower the performance on target node. Later, a meta-learning poisoning attack is developed by Züggnr & Günnemann (2019a) which aims to decrease classification accuracy globally. It treats the the graph structure hyper-parameter and conducts training-tinn time attacks through meta learning. Last, Xuu et al. (2019a) proposes gradient-based based attack method that directly tackling the dicrete graph data. Since these two are the state-of-fe of-te-----h-ar the--rtet art non-targe targetd global attack method, we will mainly focus on developing defense schemes against them.
Robustness of GNNs. To defend against these graph attacks, Miller et al. 2019) seek to increase model robustness by decoupling structure from attributes in the classifier and re-selecting the training
3

---

Under review as a conference paper at ICLR 2021
data. But their method exhibits trade-off between robustness and performance, i.e. the performance drops on clean data. Wang et al. (2019b) proposed graph encoder refining and adversarial contrastive learning. They investigate the vulnerabilities in every aggregation layer and the perceptron layer of a GNN encoder, and apply dual-stage aggregation and bottleneck perceptron to address those vulnerabilities. They mainly focus targeted node attacks (e.g. Nettack) instead of global topology attacks. RGCN (Zhu et al.] (2019) treats node features as a Gaussian distribution and encode the hidden representation of nodes by mean and variance matrices. They apply self-attention on the variance matrix to aggregate messages from neighboring nodes. However, this method only focuses on defense against random noise on node features. GCN-Jaccard (Wu et al. 2019) pre- processes the network by eliminating edges that connect nodes with sufficientely small Jaccard similarity of features. GCN-SVD (Entezari et al. 2020) proposes to vaccinate GCN with the low-rank approximation of the perturbed graph. Most of these existing methods provide insight of robustness from the perspective of optimization or matrix ranks. DropEdge (Rong et al. 2019) randomly removes a certain amount of edges from the input graph each training epoch. It is designed to resolve the over- werr-fitingg and over-smoothing issue of developing deeep GCNs. However, it can also be used for improving the graphs robustness. Pro-GNN (Jin et al., (020b) jointly learns structural graph and robust graph neural network model from the perturbed graph guided by exploring the graph properties of sparsity, low rank and feature smoothness design robust graph neural networks. In this paper, we understand the graph robustness from geometric view and provide an efficient sampling based model.
2 GEOMETRIC RE-SAMPLING FOR ROBUST GNNS
Our method uses the robust geometric representation of the input graph to train a GNN by randomly sampling new graph based on the Rieci flow representation. Figure Figure[]shows the general framework. Our method is agnostic to both the GNN model and the attack strategy. We start by a brief review on graph neural networks and poisoning attacks against graphs.
2.1 BACKGROUND: GNNS AND POISONING ATTACKS
We focus on the semi-supervised node classification task. Consider graph G = (V, E) with node features H = (h1, f2. ... hy), ). h4 E RD, where N is the number of nodes and D is the feature dimension of each node. Only part of the graph nodes Vi S V are labeled and our main task is to predict the label of the remaining nodes Vn S V given the node features H, edges E and labels of Ve.
A GNN essentially learns the now-dimensional representation of the nodes given the node features and graph structure. There have been various types of GNNs (Bruna et al.) 2014; Gori et al., 2005), usually classified into two categories: the spectral ones and the spatial ones. Spectral graph neural networks extend CNNS to graphs by defining convolution filters in the spectral domain (Bruna et al., 2014 Defferrard et al., 2016 Kipf & Welling 2016). They utilize the concept of graph Fourier transformation, and define the spectral filters on the cigenvalues of the graph Laplacian matrix. Spatial graph neural networks, on the other hand, define graph filters in the spatial domain. They iteratively update graph nodes' representation by aggregating information from neighbors (Gilmer et al., (017). We can see both Laplacian matrix and the neighborhood relationship essentially represent the graph structure information, thus both types of GNNs highly rely on the graph topology and are sensitive to structural perturbations.
Take the well known graph convolutional network (GCN) as example (Kipf & Welling 2016). GCN consists of multiple layers. Layer t updates node representation from H² to H": H' of (AH'-W"") where H = H. W is the parameter for layer t, Å is a normalized version of adjacency matrix A: À = D- 1/2 A 11/1 with Ā = A A-1 and D as the degree matrix of A.
As introduced in Section introduce unnoticeable perturbations by imposing restrictions to ensure that the attack preserves the graph structure and node features. A non- nor-eteeeeed structural poisoning attack on graph G can be formulated as the following optimization problem:
GNN is vulnerable to adversarial attacks. Usually the attackers
arg arg Cattack (fe- (G'))
(2.1)
where fo is the GNN function for node embedding where f is the set of parameters, GG) is the constraint set for the perturbed graph, 0" arg ming Ltrain (fo))"). As indicated in (Zügner et al.
4

---

Under review as a conference paper at ICLR 2021
Zügner & Günnemann 2019a), by treating the graph structure matrix A as a parameter (or hyper- parameter) and solving this optimization problem, the attackers can significantly decrease classification performance.
2018
2.2
GEOMETRIC RESTRUCTURING OF GRAPHS
With the same insight as the wnsupervised manifold hypothesis (Cayton 2005 Narayanan & Mitter
2010: Rifai al., 2011) (real data in high dimensional spaces concentrate near low-dimensional manifolds) we view a graph as discretization of an underlying manifold. Any manifold can be described by a collection of (local) charts, where each chart is homeomorphic to an open set in a Euclidean space and charts that overlap are compatible (transition from one chart to another is differentiable) (Lee & Lee 2009). This will allow one to define the geodesic distance between two points on the manifold.
By using graph Ricci flow, we can recover this latent metric space that is intrinsic to the input graph which is robust to topological perturbations. Specifically, the discrete Ollivier Ricci curvature (Ollivier) 2009) Kay of the edge (r, y) involves the ratio between the Wasserstein distance (the optimal transport distance) W (m,, my) and their geodesic distance d(x, y)
W (mg. d(x,y)
Key 1
(2.2)
where May my are two distributions defined on the neighborhood of æ and neighborhood of y. respectively. The details are in the Appendix [A.]] The computation of Ricci flow metric involves multiple iterations until edge weights do not change much (Ni et al. 2015 2019 2018). In each
iteration, we calculate the Ricci curvature of each edge, and adjust the current edge weight with value proportional to the edge curvature. For the t-th iteration, all the new edge weights ((++1) are calculated
dd (I(+)) (I, = dx) (x. v) Kizg (
(2.3)
We re-nommalize all the edge weights to keep the total edge weight unchanged at the end of each iteration. To speed up the computation process, we use the Sinkhorn distance (Cuturi) (003)) (on a sampled neighborhood) than 1 sec to compute Ricci curvature for Cora and Citeseer data set (of 4732 edges), and 6.9 sees for Polblogs (with 16714 edges) on 36 cores machines. The detailed formulas of computing Ricci curvature and Ricci flow can be found in the Appendix A.2
an approximation of optimal transport distance. In practice, takes less
Robustness of Ricci flow metric One way to visualize this is to consider embedding the graph on manifold with uniform curvature. The edge weight on (u, v) describes the proximity of u, on the manifold. In other words, it would require lot of changes to the graph connectivity to create significant changes in this metric space and the underlying manifold. The benefit of the new metric, according to the curvature definition, is the following nice property that implies robustness to connectivity perturbation: the optimal transport distance from distribution
neighbors of u to distribution on neighbors of is (1 - k) k)d(u, v)), which is just d(u, v) when curvature K converges to zero. In other words, there paths connecting neighbors of and neighbors of v which bypass edge (u, v)) and have similar length (in an average sense). This suggests that the removal of edge (u, v) has small changes lengths of (shortest) paths in the graph. This is a good thing have, as opposed to a graph metric where the removal of an edge incurs substantial changes to the distances of certain pairs of nodes (often in the neighborhood)- and these edges are especially susceptible adversarial attacks. Depending on the graph topology, there are cases when the curvature upon convergence is not zero (for example, when the graph is sparse and tree-like the curvature converges to a negative value). Similarly the disturbance to the distances between nodes in the graph, upon the removal of a single edge, is disseminated in global manner so all pairs distances suffer similar (small) damage due to the adversarial attack.
Graph Re-sampling in GNN Instead of using the possibly poisoned input graph for training data, we sample family of graphs from the Ricci flow metric and use this ensemble of graphs as the training data. The edges of a graph are sampled by imposing a Gaussian filter on each node using the Ricci flow metric distance. The use of Gaussian kernel to convert the Euclidean distances between data points to a similarity measure is commonly used in settings that take a manifold viewpoint on input data.
5

---

Under review as a conference paper at ICLR 2021
Algorithm 1 One GNN epoch based on Ricci flow graph restructuring input Input adjacency matrix A, a, B Pre-computed Ricci flow metric F from A
Pre-computed all-pairs Ricci flow distance metric S of all nodes via F
S
Pre-computed edge probability matrix: p= a 2
exp
2 33
1: for t= to 7 do Sampling Ar from
3: An An V Ak
Ar An +
5: AR 1/2
A
A
Train and update weight parameter W*
7: end for
Specifically, we first calculate the edge weights F by running Ricci flow on the attacked graph G. Then the all-pairs Ricci flow distance metric S between any nodes are calculated the geodesic distance based on the weights assigned to all the edges. To keep graph sparsity, we only sample edges between pairs that are within hops of each other G' (we take I 2 in the experiments).
1
1 (80
Two nodes is connected by edge with probability: P(S)
exp
In each
2v
epoch, we sample a graph G, for each layer i the graph convolution method and apply classical GCN to learn weight parameter W for prediction. The pseudo code for one GNN epoch is shown in Algorithm
Intuition. Rumning Ricci flow provides us chance to recover edges that should exist but not formed yet (or removed by the attacker). Recall that a new graph is sampled at each layer in the graph convolution pipeline. If an edge is added from the attack and is not aligned with the main network structure (and the underlying metric space), it is unlikely to get consistent support in the re-sampling phase across multiple layers. If an edge from the attack is actually aligned well with the underlying metric space, it is not creating much damage in the performance. This observation is visualized in Figure 4 To show the benefit of Ricci flow metric in addition to the ensemble approach, we also compared with re-sampling using other graph metrics such as spectral embedding and hop count metric. See the experiment section.
3 EXPERIMENTS
Attack and defense baselines. We test methods against two poisoning attacks: RAND (ran- domly adding fake edges into the graph, provided by DeepRobust (Li et al., (020) library) and META (meta-learning attack (Zügner & Günnemann, (019a)), which treats the graph structure as and uses meta- gradderddsntss to solve the believe optimization problem in Eq, 2.1 We ran the meta-learning with self-training (using predicted labels on unlabeled nodes) and exact meta-gradients named as Meta-Self since it achieves state-of-the-ar performance in most datasets.
a
For defense methods, we also compare the performance of graph attention network (GAT) (Velickoić et al. 2018), RGCN (Zhu et al. 2 GCN- (Wu et al. 2019), GCN-SVD (Entezari et al. 2020 and Pro-GNN (Jin al. 20206). The detailed descriptions of these baseline methods can be found in the supplementary materials. In all experiments, for each graph, we run the training and inference tasks 20 times and take the average accuracy. For each training procedure, we run 100 epochs and use the best model based on validation performance.
Results on synthetic datasets. We evaluate our method on synthetic graphs generated from the Stochastic Block Model (SBM) (Holland al. 1983). We create 24 random graphs, each of which has 1000 nodes, equally partitioned into five communities. Within each community, two nodes connected with intra-class probability p E {0.07, 0.09, 0.11, 0.13). Nodes from different classes have a lower probability to connect with each other with inter-class edge probability q e (0.025, 0.03, 0.035, 0.4, 0.045, 0.05). Community 4 and only have edges to community 1. For

---

Under review as a conference paper at ICLR 2021
each generated graph, we randomly select 100 nodes the training set and the remaining 900 as testing set for attack and defense. We assign each node a node ID feature using the one-hot encoding.
We use 2- 2-layer GCN (Kipf & Welling 2016) the default graph neural network and meta-lcarning attacks Ziggner& & Günnemann 2019a) as the attacking method. 5% of the total edges are perturbed under the node degree distribution constraint in (Zügner et al. 2018). For attacking, we follow the setting in Zügner Günnemann 2019a). For Rieci-GNN, we also use 2 layers, and the hyperparameters are chosen from a E (0.2, 0.6, 0.8, 1.0] and 3 E 21,2,3,4,5)
The classification accuracy for the original graph, the attacked graph, and our Ricci-GNN method are 84%, 82%, and 87% respectively. Our proposed method successfully negates the impact of the attack and even improves classification accuracy. This is due to the power of the Ricci flow metric in terms of recovering the underlying community structure and the improved robustness and diversity with our re-sampling method. Figure 4(a) shows a graph from the SBM with inter-class probability q = 0.045 and intra-class probability p 0.09. The meta-learning attack injected additional edges (see the red dot in its adjacency matrix in Figure 4(b)). many of which are between different communities this will incur most damage to the performance. By sampling via a Gaussian filter on the Ricci flow metric (see probability in FigureFrcs
we can re-create graph topology that preserves the same connectivity pattern within communities and across communities. In addition, if we sample twice and obtain two graphs 11 and G2. Both graphs strongly preserve the community structure; but the nnter-communities edges in G1 and G2 are largely different - see the common edges in Figure F(d) Recall that we plug in freshly re-sampled graph in each layer of the GCN, the influence of inter-community edges introduced by the attack is gradually eliminated during training.
00
66
06
8A
00
(a)
(b)
(c)
(d)
Figure 4: The defense of meta-learning attack using Ricci-GNN on a Stochastic Block Model (SBM) graph with 5 communities. Ha) The clean SBM graph. (46) The adjacency matrix of the graph while the edges in the clean graph are shown in blue. Edges added by the meta-learming attack are shown in red. These edges appear disproportionately to the original edge density. Sparser blocks in the clean graph receive more edges in the attack; nearly all edges in the attack are between different communitics. [(c) The heat map of the probability of an edge being connected our re-structuring method. The probability edges in the original community structure are higher than the attack edges. [(d) The common edges of two randomly re-sampled graphs the influence of the edges in the meta-learning attack is essentially eliminated.
Results on real-world datasets. We evaluate our method on three real- world graph datasets: Cora. Citeseer, and Polblogs, that were often used in prior work (Zügner& & Günnemann, 2019a). Cora and Citeseer (Sen et al., 2008) are citation networks, where each node represents a document and each edge represents citation relationship. In Polblogs (Adamic & Glance (005), nodes are political blogs 2004 US president election and edges represent citations between blog. Note that Polblogs does not have node features so we create an N dimension one hot feature for each node.
We use the same training setup for the clean graph, poisoned graph and our method. This includes set- ting L2 regularization with À = 0.0005, initializing by Glorot initialization and training by minimizing cross-entropy loss using Adam optimizer with learning rate r 0.005.
For random attack, we randomly add 5% extra edges. The result is shown in Table I Our method is on par with other methods on Cora and achieve state-of-the-an for Citeseer and Polblogs dataset. We also ran the experiment with increasing perturbation ratio on Polblogs dataset. As shown in Figure [bb] by restructuring and sampling the graph based on the Ricci flow metric, our method can negate most of the effect of added random noise even when the noise ratio is large.
7

---

Under review as a conference paper at ICLR 2021
1.0
Accuracy
Accuracy
0.8
GAT
GAT
0.6
GCN
GGN
RGON
RGSGN
GCN-SVD
RIczI-GNN
RicoiGNN
0.4
0.1
0.1
0.2
Perturbation Rate
Perturbation Rate
(a) Meta-learning attack
(b) Random attack
Figure 5: Accuracy plot of different defense schemes with increasing perturbation rate under different attacks on Polblogs.
Table 1: Classification accuracy for various defense schemes after random attack of 5% extra edges
Dataset
GCN
GAT
RGCN
GCN-Jaccard
GCN-SVD
Pro-GNN
Ricci-GNN
Cora
03.54.1.33
83.27:1.225
83.51 24
83.09-0.36 71.34=0.59
72.94:10.45
83.24 10.76
83.1910.60
Citeseer
68.75:20.48
68.76:0..57
71.08 11.10
64.78:+1.11
70.78:1.002
71.47 #0.53
Polblogs
92.49 10.94
93.03 11.32
92.07 10.28
93.39 1.033
93.28.10.91
94.10 10.26
Table Classification accuracy for various defense schemes after meta-learning attack
Dataset
Pth rate %
GCN
GAT
RGCN
GCN-Jaccard
GCN-SVD
Pro-GNN
Ricci-GNN
83.50.0.44
83.97-0.65
83.09.10.4
82.05.0.511
80.63:10.45
82.98.10.33
83.03
10.59
5
76.55
80.44-0.74
77.42-00.3
79.13-40.59
78.3940.54
82.78 +-0.5
82,80
40.43
70.39+1.28
75.61=0.50
72.22440.35
76.16+0.76
71.47+0.83
77.9140.88
79.70
15
65.10:0.77
69.78.11.28
66.82.10.39
71.03.1064
66.69.1.18
76.01
1.1.2
77.28-0.550
10.50
20
59.56-42.72
99.94-0-.92
59.27440.37
65.71+00.89
58.94++1.13
68.78
+5.84
74.10
+0.63
25
1.95
54.78=0.74
50.51:00778
60.82+1.05
12.06=:1.19
+2.58
71.73=0.60
0
71.96=0.55
73.26-20.88 83
71 71,20++0.58 83
72. 10=00033
70.65=+0.32
73.26 01.26:25 +00.69
73.95=00.3
70.88 62
72.89
70.50:10.00
00.97
68.84:10772
73.09 10.34
73.39=00.2
Citeseer
10
67.55:10.80
70.63:10.44 48
67.71
69.6410.56
68.87:10.62
72.43 1:0.75
-2.61210.22
15
64.52.4.000 0.662
09.02-40.62
0..62
65.95 0.62
63.26-40.2
70.82 +-2.38
71.99
00.71
20
62.03-+3.40
61.04+1..52
62.49-+-1.2 1.22
59.30+1140
58.55=t 1.09
66. 4:2.57
68.40=0.51
25
56.94.12.0
1.185111.12
55.35
19.89
$7.18
66.40 1.2.57
68.84 10.51
0
00.38
95.35
95.22.10.14
95.31
93.20 1.0.44
95.72.10.24
5
73.0740..50
83.69--1.45
74.34-40.19
89.09--0.22
93.29 4-0.18
90.54
+-0.47
Polblogs
10
70. 70.72=0..2
76.32-0.48
71 71.04+00.0
81 81.24:1:.667
89 89.42 +1.09
86 88:20.85
15
64.96=1.91
07.28:00.0
68.10:233.73
12221
86.10=0096
20
51.27=1.22
51.50:11.63
59.8 59.89-10.08
$7.33:13.15
79.36 1:5.68
11.37-11.24
49.23-11.56
8

---

Under review as a conference paper at ICLR 2021
Table 2 shows the classification accuracy (the higher the better) of different defense schemes after attacked by meta-learning attack with different perturbation ratios. The first row of the table each dataset shows the accuracy of applying the defense method on the original clean graph. The result shows that directly using our method has no negative effect on GNN models. Specially for Citeseer and Polblog dataset, method achieve state-of-the-art accuracy. When the perturbation increases (the attacker is more powerful), the accuracy gap between our method and other methods widens, clearly demonstrating the advantage of method.
Table 3:
Classification accuracy for defense using Ricci flow metric (Ricci) vs. hop count metric (HC) and spectral embedding metric after meta-learning attack. Note that Citeseer dataset is by itself fairly robust to attacks (See Table 2
Cora
Citeseer
Polblogs
Ptb rate %
HC
Spectral
Ricci
HC
Spectral
Ricci
HC
Spectral
Ricci
82.0
78.4
83.0
73.4
72.1
74.0
94.9
93.4
95.7
5
81.4
76.1
82.8
73.0
71.3
73.4
85.6
88.2
90.5
10
77.5
73.1
79.7
71.0
69.3
72.5
85.6
88.0
86.9
15
75.5
65.1
77.3
70.7
67.6
72.0
70.6
80.3
86.1
20
72.8
60.2
74.1
67.9
67.8
68.4
65.8
79.4
81.3
25
65.4
54.7
71.7
65.4
65.6
68.8
62.0
74.6
79.5
Benefit of Ricci flow metric. To show the importance of Ricci flow metric, we also run the entire graph restructuring algorithm but with the hop count metric and the spectral embedding metric against meta-learning attacks. See Table In nearly all cases, using Ricci flow metric shows clear improvement on performance. On Cora, the one with spectral embedding is the worst, as graph relatively sparse and spectral embedding least stable. On Polblogs, the with hop count distance the worst, as the graph is very dense and diameter small (only 4). shows that the Ricci flow metric is important for the probabilistic sampling framework to achieve the full defense potential.
CONCLUSION
We propose novel approach to improve the robustness of GNNs against graph-topology focused attacks. The curvature and flow information can effectively capture the intrinsic geometry of the graph that is robust structural perturbation. Our algorithm restructures and resamples the graphs using the underlying geometry. This helps training robust graph neural network. Our method achieve superior performance both synthetic and real work benchmarks under various attacks.
REFERENCES
Lada A Adamic and Natalie Glance. The political blogosphere and the 2004 us election: Divided they blog. Proceedings of the 3rd International Workshop on Link Discovery, pp. 36-43, 2005.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann Lecun. Spectral networks and locally con- nected networks on graphs. International Conference on Learning Representations (ICLR2014), CBLS, April 2014, pp. http-openreview, 2014.
Lawrence Cayton. Algorithms for manifold learning. Univ. of California at San Diego Tech. Rep, 12 (1-17):1, 2005.
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. In Advances in neural information processing systems, pp. 2292-2300, 2013.
Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. Adversarial attack on graph structured data. arXiv preprint arXiv: 1806.02371, 2018.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. In Advances in neural information processing systems, pp. 3844-3852 2016.

---

Under review as a conference paper at ICLR 2021
Negin Entezari, Saba A Al-Sayouri, Amirali Darvishzadeh, and Evangelos E Papalexakis. All you need is low (rank) defending against adversarial attacks on graphs. In Proceedings of the 13th International Conference Web Search and Data Mining, pp. 169-177, 2020.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning- Volume 70. pp. 1263-1272. JMLR. org. 2017.
Srrnning-Volumme
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. ICLR, 2015.
Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., volume 2, pp. 729-734, IEEE, 2005.
Richard Hamilton. Three-manifolde with positive ricci curvature. J. Differential Geom., 17(2): 255-306, 1982.
Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2):109-137, 1983.
Wei Jin, Yaxin Li, Han Xu, Yiqi Wang, and Jiliang Tang. Adversarial attacks and defenses on graphs: A review and empirical study. arXiv preprint arXiv:2003.0065: 2020a.
Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. arXiv preprint arXiv:2005. 10203, 2020b.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: (00000000009...... 2016.
Jeffrey Lee and Jeffrey Mare Lee. Manifolds and Differential Geometry. American Mathematical Soc., 2009.
Yaxin Li, Wei Jin, Han Xu, and Jiliang Tang. Deeprobust: pytorch library for adversarial attacks and defenses. arXiv preprint arXiv:2005.06149, 2020.
Benjamin Miller, Mustafa Çamureu, Alexander J Gomez, Kevin Chan, and Tina Eliassi-Rad. Improving robustness to attacks against vertex classification. 2019.
Hariharan Narayanan and Sanjoy Mitter. Sample complexity of testing the manifold hypothesis. In JD Lafferty, C K Williams, Shaaw-TTylor. R Zemel, and A Culotta (eds.), Advances in Neural Information Processing Systems 23, pp. 1786-1794 Curran Associates, Inc., 2010.
Chien- Chhun Ni, Yu-Yao Lin, Jie Gao, Xianfeng Gu, and Emil Saucan. Ricci curvature of the internet topology. In Proceedings of the 34th Annual IEEE International Conference on Computer Communications (INFOCOM) 15), pp. 2758-2766, April-May 2015.
Chien-Chun Ni, Yu- Yao Lin, Xianfeng Gu, and Jie Gao. Network alignment by discrete ollivier- ricci flow. In Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (G)'18), pp. 447 462, September 2018
Chien-Chun Ni, Yu- Yao Lin, Feng Luo, and Jie Gao. Community detection on networks with ricci flow. Scientific Reports, 9(9944), July 2019.
Yann Ollivier. Ricci curvature of markov chains metric spaces. Journal of Functional Analysis, 256:810-864, 10-864, 2009.
Grisha Perelman. The entropy formula for the ricci flow and its geometric applications. November 2002.
Salah Rifai, Yann N Dauphin, Pascal Vincent, Yoshua Bengio, and Xavier Muller. The manifold Taylor, R S Zemel, P L Bartlett, F Pereira, and K Q Weinberger (eds.), Advances in Neural Information Processing Systems 24, pp. 2294-2302 Curran Associates, Inc., 201 1.
tangent classifier. In J Shawe- Shawe-Taylor,
10

---

Under review as a conference paper at ICLR 2021
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convo- lutional networks on node classification. In International Conference on Learning Representations, 2019.
Romeil Sandhu, Tryphon Georgiou, Ed Reznik, Liangjia Zhu, Ivan Kolesov, Yasin Senbabaoglu, and Allen Tannenbaum. Graph curvature for differentiating cancer networks. Scientific reports, 5(1): 1-13, 2015.
Prithviraj Sen, Galileo Namata. Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rae -aad.. Collective classification in network data, Al magazine, 29(3):93 2008
Jayson Sia, Edmond Jonckheere, and Paul Bogdan. Ollivier-rice' curvature based method to commu- nity detection in complex networks. Scientific reports, 9(1):1-12, 2019.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. ICLR, 2014.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. ICLR, 2018.
Daixin Wang, Jianbin Lin, Peng Cui, Quanhui Jia, Zhen Wang, Yanming Fang, Quan Yu, Jun Zhou, Shuang Yang, and Yuan Qi. A semi-supervised graph attentive network for financial fraud detection. In 2019 IEEE International Conference on Data Mining (ICDM), pp. 598-607. IEEE, 2019a.
Shen Wang, Zhengzhang Chen, Jingchao Ni, Xiao Yu, Zhichun Li, Haifeng Chen, and Philip Yu. Adversarial defense framework for graph neural network. arXiv preprint arXiv:190..03679, 2019b.
Huijun Wu, Chen Wang, Yuriy Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu. Adversarial examples for graph data: Deep insights into attack and defense. In International Joint Conference on Artificial Intelligence, IJCAI, pp. 4816-4823, 2019.
Kaidi Xu, Hongge Chen, Sijia Liu, Pin-Yu Chen, Tsui-Wei Weng, Mingyi Hong, and Xue Lin. Topology attack and defense for graph neural networks: An optimization perspective. arXiv preprint arXiv: 042/4,00 2019a.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? ICLR, 2019b.
Ze Ye, Kin Sum Liu, Tengfei Ma, Jie Gao, and Chao Chen. Curvature graph network. Proceedings of the 8th International Conference Learning Representations (ICLR 2020), April 2020.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovee. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pp- 974 983, 2018
Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. Graphrnn: Generating realistic graphs with deep auto-regressive models. In International Conference on Machine Learning, pp. 5708-5717, 2018.
Xinyi Zhou and Reza Zafarani. Fake news: A survey of research, detection methods, and opportunitics. arXiv preprint arXiv: /8/2.0031, 2018.
Dingyuan Zhu, Ziwei Zhang, Peng Cui, and Wenwu Zhu. Robust graph convolutional networks against adversarial attacks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1407, 2019.
Marinka Zitnik, Monica Agrawal, and Jure Leskovec. Modeling polypharmacy side effects with graph convolutional networks. Bioinformatics, 34(13)i447-i466, 2018
Daniel Zügner and Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning. The Seventh International Conference Learning Representations (ICLR), 2019a.
11

---

Under review as a conference paper at ICLR 2021
Daniel Zügner and Stephan Günnemann. Certifiable robustness and robust training for graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. pp. 246-256, 2019b.
Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks neural networks for graph data. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery Data Mining. pp. 2847-2856, 2018.
12

---

Under review as a conference paper at ICLR 2021
A APPENDIX
In this supplemental material, provide technical details Ricci curvature and flow. We also provide additional details on the experiments.
A TECHNICAL DETAILS OF RICCI CURVATURE AND FLOW
In this sub-section, we will establish the precise mathematical formulation of Ricci curvature and Ricci flow in the discrete setting and describe their computation on un-directed graphs. We first define Ricci curvature, which is computed for each edge. Next, we explain how Ricci flow re-weight the edges iteratively so that Ricci curvatures of all edges are smoothed. The final weighted graph induces the Ricci flow metric; the geodesic distance between any two nodes in this weighted graph is their distance in the Ricci flow metric space.
A.1 DISCRETE RICCI CURVATURE.
In Ollivier's definition Ollivier (0099) of Ricci curvature for discrete space, one aims measure the curvature Kay between nodes x and y. By comparing the Wasserstein distance (also called earth mover distance) between the neighborhoods of and y, we can determine the deviation of the edge (z. y) from being flat.
For an undirected and edge-weighted graph G EV, the neighborhood of node x is the collection of immediately adjacent nodes (one-hop neighbors) (xx) {æ; aat, E E} associated with some probability measure mz (2;) which sums 1. Similarly, we have a probability measure my the neighborhood of y. The Wasserstein distance between thew two probability measures, W (m,, my), is the minimum total weighted cost to move my to my using the optimal transportation plan M:
min M
Σ ((ar,u;)Ml(es Mj)
Σ M(ass U/)) mx)
s.t.
(A.1)
Σ M(x,, v,) = my
where Mi yý) is the quantity of probability mass transferred from 24 to My using the shortest path with graph geodesic d(r;; yj). Then the Ricci curvature Kay of the edge (xx, 3) takes the ratio between this Wasserstein distance and their geodesic:
W W(m,, my) Kay 1
(A.2)
d(z,y) y)
A negative curvature means the probability mass of the neighborhood m, is transported to my mostly through the edge (a., y/. This usually happens when (I, y) is a bridge joining two communities (red edges in Figure [(a)). Meanwhile, an edge within a community tend to have overlapping neighborhoods and y, resulting in positive curvature (blue edges in Figure I(b). Notice that the curvature value depends on the edge weights. Later in Ricci flow, we will illustrate how curvature morphs when edge weights change.
To define the probability measure of each neighborhood, adopt weight aware definition from Ni ct al. (2019) that discounts neighbors which are further away. With portion y E [0, 1] and discount factor 0.
if if o (xr) otherwise.
1-z (xp(-d((,xx;))
7-P (xx) m2
0
13

---

Under review as a conference paper at ICLR 2021
where C== (a))) exp(-d(22, 2)))) is the normalizing constant to assign probability measure 1 to the entire neighborhood. When p 0 (weight unaware), this definition of the probability measure reduces to the uniform distribution. We take 7 = 0.5 and following the heuristics in the literature.
A.2 RICCI FLOw
Recall the curvature describes the degree of surface being curved. Ricci flow is an iterative process restore the flatness everywhere such that Ricci curvature Key is constant for every edge. Starting with the original imput graph, the flow iteratively updates edge weights. For the t-th iteration, all the new edge weights (1++1) are calculated as
w (++ (x. (I, = (x.
( y)- Kizy
(A.3)
Each update moves the edge weight in the opposite direction of the curvature. Geometrically, negatively curved edges acting bridges will be extended while positively curved edges within the community will be shortened. We re-normalize edge weights after each iteration. When the process converges, the final set of edge weights induces a Ricci flow metric on the graph. Please see Figure I(b) for an illustration.
To speed up the computation of the Wasserstein distance, we use an approximate version called Sinkhorn distance from Cuturi (2013) that smooths the optimal transportation cost with regulariza- tion term and then can computed by Sinkhorn Sinkhorn-Koop'ss matrix scaling algorithm.
B ADDITIONAL EXPERIMENTAL DETAILS AND RESULTS
B. DATASETS DESCRIPTION
Table 4 provides details of the datasets.
Table Statistics of Real-World graph datasets.
Cora
CiteSeer
Polblogs
#Node
2708
3327
1222
#Edge
5429
4732
16714
AvgDeg
4.00
2.84
27.35
Diameter
19
28
4
#Feature
1433
3703
#Class
7
2
B.2
GRAPH HEATMAP
Figure shows prediction accuracy of all the 24 graphs generated in Section 4.1 of the main paper. We observe better accuracy by our method, compared with the GNN trained on the attacked graph.
B.3 ADDED BASELINES
B.3.1 NEW BASELINES RESULT DEFENDING META-LEARNING ATTACK DIFFERENT PERTURBATION RATE.
Tabel shows the two new baselines performance defending the meta learning attack under different perturbation rate. worth mentioning that CurvGN (Ye et al., 2020) is not designed for improving the robustness of GNN. Thus CurvGN performs relatively worse than DropEdge (Rong et al. 2019). We also move the performance of our Ricci-GNN to here to show that our method perform better than those two methods.
14

---

Under review as a conference paper at ICLR 2021
0.022
0.025
0.025
035
0.00
0.03
0.03
Communo
0.85
0.04
0.04
0.04
0.646
0.045
0.045
0.06
0.06
0.05
0.08 0.1
SBM www.ll.nta-Commnnly..
kntra-Communily...
Intra-Cormunily:
Figure 6: Defense accuracy heat maps for synthetic data of 24 SBM graphs constructed from different {p. q). From left right: attacked graph, clean graph, defense result by Ricci-GNN. For each heat map, x-axis the intra-community probability, p. y-axis is the inter-community probability,
Table 5: Classification accuracy for various defense schemes after meta-learning attack
Dataset
Pth rate %
CurvGN
DropEdge
Ricci-GNN
0
82.8
82.8
83.0
75.8
79.2
82.8
Cora
10
69.3
72.3
79.7
15
60.3
65.9
77.3
20
52.8
57.9
74.1
25
46.7
47.8
71.7
0
73.4
73.4
73.9
70.5
71.9
73.4
Citeseer
10
66.1
69.3
72.5
15
62.9
65.9
72.0
20
52.9
58.1
68.4
25
48.1
55.6
68.8
94.1
94.4
95.7
5
73.7
90.7
90.5
Polblogs
10
72.2
89.0
86.9
15
68.2
82.2
86.1
20
58.5
81.3
81.4
25
55.6
78.8
80.0
15

---

Under review as a conference paper at ICLR 2021
B.3.2 DEFENSE RESULT ON TOPOLOGICAL ATTACK MINEAXX
Besides the Table 6 shows the extra experiment results on defending the topological attack-MinMar (Xu et al. 2019a) under two different perturbation rate: 5% and 25%. Since the code of DropEdge programming error on citeseer under MinMax attack, we can report it's result. (For now) From the tabel, we can see that our methods out perform all other baselines. It confirms that our method improved the robustness of GNN on different attack methods.
Table Classification accuracy for various defense schemes after topological
Dataset
Ptb rate
GCN
RGCN
GCN-Jaccard
GCN-SVD
Pro-GNN DropEdge
curvGN
Ricci-GNN
Cora
82.8
83,8
81.9
71.3
83.5
83.4
80.3
82.3
83.8
74.2
73.5
77.3
63.5
75.9
77.2
44.5
72.6
78.6
Citeseer
71.6
73.3
67.8
71.7
72.3
73.7
25
58.7
59.3
63.5
56.0
$7.5
66.4
67.7
68.4
Polblogs
88.5
51.2
86.7
92.7
93.6
94.5
25
58.5
53.0
51.4
50,2
72.2
64.9
59.4
75.6
87,9
C DETAILED DESCRIPTION OF BASELINE METHODS
GAT. Graph attention network (Veličković et al. 2018) uses node feature learn self attention. The attention is used to re-weight each message passed to the node. Neighboring nodes with features that are more important will receive higher weights. Since the message is solely learned from node features, GAT is inherently robust to graph structure perturbation.
RGCN. RGCN (hu al. 2019) models hidden layer representation of nodes as Gaussian distribution to counter adversarial attacks. It also use attention mechanism from GAT to penalize nodes with high variance.
GCN-Jaccard. GCN-Jaccard (Wu et al. choose important messages measured by Jaccard similarity of features and delete edges that considered irrelevant.
2019) inherits the idea of feature importance from GAT.
GCN-SYD. GCN-SVD (Entezari et al. 2020) claims that most adversarial attacks will affect high- rank spectrum of the graph, thus taking a low-rank approximation of the graph to defend the adversarial attacks. Note that it's originally designed defend Nettack Nettack(Züigner al. 2018). However, it can be also used for meta-learning attack (Zügner & Günnemann 2019a) and random attack.
Pro-GNN. Pro-GNN jointly learn a structural graph and robust graph neural network model from the perturbed graph guided by exploring the graph properties of sparsity, low rank and feature smoothness to design robust graph neural networks.
Topological attack-MinMax. Topological attack provides two attacking methods. a) attacking pre-defined GNN (PGD) and b) attacking a re- re-trainable GNN (MinMax). We choose the MinMax because most recent work focus improve the robustness of re-trained GNN. The topological attack the problem as a loss optimization problem and use the MinMax method to solve the problem. The attacker seeks to minimize the per-node attack loss while the GNN tries defend the attack by retraining W so that attacking GNN is more difficult.
16


Reviews:
[{"review_id": "ZZFBlm9CjYH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Strengths: \n\nThe paper is well written and clean. \n\nWeaknesses: \n\nI have several concerns regarding this paper. \n\n•\tNovelty. 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). \n\n•\tApproach. 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?). \n\n•\tAlgorithm. 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. \n\n•\tDesign 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. \n\n•\tDatasets. 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]. \n\n•\tWeak 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. \n\n•\tAblation. 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. \n\n•\tTraining. 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. \n\n[1] https://arxiv.org/pdf/2003.00982.pdf\n[2] https://ogb.stanford.edu/\n[3] https://paperswithcode.com/task/node-classification\n\n==========\n\nAfter reading the authors comments.\n\nI 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.\n\nI 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.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Goam2hEXZCo", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nIn 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.\n\nReasons for score: \nOverall, 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). \n\nStrong points:\n* The main idea of using Ricci flow is interesting, well motivated and well executed.\n* Evaluation on SBM graphs helps with better understanding why the proposed approach works.\n* The comparison to other metrics (Spectral and HC) is appreciated.\n\nWeak points:\n* 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.\n* 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.\n* 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.\n* 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\".\n* 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. \n\nQuestion for the authors:\n1. How robust is Ricci-GCN to adaptive attacks? (see weak points) \n2. How does Ricci-GCN compare to other data augmentation techniques (see weak points) \n3. 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?\n4. Is there any improvement if we are willing to pay the price of decreased sparsity, take k larger than 2?\n5. Why is the row for perturbation rate of 0 omitted from Table 3? Where the hyperparameters tuned separately for Spectral and HC?\n\nAdditional feedback that did not affect the decision:\n* The related work should also discuss the difference between certifiable and heuristic defenses and how the proposed approach fits in this context.\n* It would be nice to quantitatively show \"The probability of edges in the original community\nstructure are higher than the attack edges\"\n* 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\".\n* 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]. \n\nTypos:\n* Figure 5 Captions: Purterbation Rate \n\n## After Rebuttal\nThe 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.\n\nOne 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.\n\nReferences:\n1. Tramer, Florian, Nicholas Carlini, Wieland Brendel, and Aleksander Madry. \"On adaptive attacks to adversarial example defenses.\"\n2. Wang, Yiwei, Wei Wang, Yuxuan Liang, Yujun Cai, Juncheng Liu, and Bryan Hooi. \"NodeAug: Semi-Supervised Node Classification with Data Augmentation.\"\n3. Rong, Yu, Wenbing Huang, Tingyang Xu, and Junzhou Huang. \"Dropedge: Towards deep graph convolutional networks on node classification.\"\n4. https://github.com/gitgiter/Graph-Adversarial-Learning\n5. https://github.com/safe-graph/graph-adversarial-learning-literature\n6. Bojchevski, Aleksandar, Johannes Klicpera, and Stephan Günnemann. \"Efficient robustness certificates for discrete data: Sparsity-aware randomized smoothing for graphs, images and more.\"", "extra_scores": {}, "extra_text": {}}, {"review_id": "1quoCf9GRn4", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\n\nSummary:\nThe 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.\n \n##########################################################################\n\nReasons for rating:\n\nOverall 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.\n\nFurthermore, 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.\n\nLast, 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.\n \n##########################################################################\n\nPros:\n+ Interesting and promising approach\n+ Consistently improved performance over the baselines\n+ Interesting analysis of their defense via SBM graphs\n\n\nCons:\n- Only one strong attack on real-world graphs is used to benchmark to other architectures.\n- 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.\n- Curvature Graph Network should be added as a baseline.\n- 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.\n\nFurther points:\n- The proposed sampling based training scheme seems to be highly related to adversarial training. The authors should add a corresponding discussion.\n- 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.\n- At some points the authors say that a graph is sampled in each \"iteration\" (epoch) and sometimes for every layer.\n- Figure 2: What is H_0, H_1, L?\n- Section 1.1: The authors should make clear that Figure 3 is an example and does not imply superior robustness in general.\n- 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).\n- Related work: There are many more (relevant) attacks/defenses. Please add them and/or make clear that your discussion is not exhaustive. \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

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