# robognn_robustifying_node_classification_under_link_perturbation__0514f5e6.pdf

Robo GNN: Robustifying Node Classiﬁcation under Link Perturbation

Sheng Guan , Hanchao Ma , Yinghui Wu Case Western Reserve University {sxg967,hxm382,yxw1650}@case.edu

Graph neural networks (GNNs) have emerged as powerful approaches for graph representation learning and node classiﬁcation. Nevertheless, they can be vulnerable (sensitive) to link perturbations due to structural noise or adversarial attacks. This paper introduces Robo GNN, a novel framework that simultaneously robustiﬁes an input classiﬁer to a counterpart with certiﬁable robustness, and suggests desired graph representation with auxiliary links to ensure the robustness guarantee. (1) We introduce (p, θ)-robustness, which characterizes the robustness guarantee of a GNN-based classiﬁer if its performance is insensitive for at least θ fraction of a targeted set of nodes, under any perturbation of a set of vulnerable links up to a bounded size p. (2) We present a co-learning framework that interacts model learning with graph structural learning to robustify an input model M to a (p, θ)- robustness counterpart. The framework also outputs the desired graph structures that ensure the robustness. Using real-world benchmark graphs, we experimentally verify that Robo GNN can effectively robustify representative GNNs with guaranteed robustness, and desirable gains on accuracy.

1 Introduction

Graph neural networks (GNNs) [Gori et al., 2005] have shown good performance for graph representation learning and downstream tasks. GNNs adopt a label propagation architecture to learn discriminative node embeddings with graph convolutional layers. In each layer, the embedding of a node is updated by aggregating its counterparts from neighbors. GNNs learning assume and rely on complete and accurate link structures from an underlying graph G. Having this said, they are often sensitive and vulnerable to even small link perturbations (e.g., adding or removing edges) due to noisy links [Tran et al., 2017; Paulheim, 2017] or malicious adversarial attacks [Dai et al., 2018; Z ugner and G unnemann, 2019]. For example, a GNN-based classiﬁer M can be sensitive under a set of link perturbations posed to graph G where M is trained on, if its output label of a same node changes as

G is modiﬁed accordingly at training time. It is thus often desirable if (1) the robustness is ensured for designated targeted nodes of interests, (2) a small set of auxiliary links L that should be protected , are derived to suggest how to mitigate the negative impact of the perturbations. This calls for proper modeling to improve the robustness of pretrained GNNs. We consider a novel and practical problem as follows. Input: a (perturbed) graph G, an input model M, a set of targeted nodes VT , a set of vulnerable links Ep that may be perturbed, and a budget p; Output: a triple (G , M , L), such that M is insensitive to a desirable amount (θ fraction) of nodes in VT , for any perturbation of at most p links in Ep \ L. In a nutshell, the problem aims to (1) robustify M to a counterpart M such that M ensures robust performance for a desired amount of designated target nodes, and (2) also generate, in accordance, a proper graph representation G and a small set of links L Ep to be protected from attacks to ensure the robustness. In addition, the size | L| reﬂects defense effort (e.g., cost to the protection of social links or communication networks) and should be minimized. The above problem has its components in prior work and is of both theoretical and practical interest. (1) Certifying robustness over entire node set [Bojchevski and G unnemann, 2019] (which requires the predicated label is insensitive to perturbations) can be an overkill for models with desirable guarantees. We introduce a conﬁgurable robustness in terms of a threshold θ over designated target nodes, enabling ﬂexible robustiﬁcation scenarios. (2) The generated auxiliary structures L and graph representation G can be readily used to (explicitly) recover the graphs or directly applied to learn other GNN-based models.

Contribution. This paper introduces Robo GNN, a colearning framework to robustify GNN-based classiﬁcation with desirable, conﬁgurable robustness guarantees. (1) We introduce a notion of (p, θ)-robustness to characterize the robustness of GNNs (Section 2). Given graph G and classiﬁer M, a pair (G, M) is (p, θ)-robust w.r.t. Ep and VT , if the output of M is insensitive for at least θ% of VT under any manipulation of at most p links in Ep. We formalize (p, θ) veriﬁcation and robustiﬁcation problems, establish their hardness, and introduce an algorithm to verify the (p, θ)- robustness for a pair (G, M) w.r.t. Ep and VT . Our goal aims

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

to reﬁne G to G and robustify M to M w.r.t. Ep and VT , such that (G , M ) is (p, θ)-robust. (2) We investigate the impact of changes of Ep to the robustness, and establish a monotonicity property, which states that the (p, θ)-robustness of a model M w.r.t. Ep and VT remains intact on any subset of Ep. Based on the property, we study an optimization problem that aims to compute a smallest set of links L Ep such that (G, M) is (p, θ)-robust over Ep \ L (Section 3). While ﬁnding the smallest L remains intractable, we present a fast heuristic strategy to compute a small protection set L, which dynamically ranks VT based on the likelihood that the model is robust at one single node, and incrementally augment L following efﬁcient traversal. (3) Based on the veriﬁcation and minimality condition, we present Robo GNN, a framework to robustify an input model with guaranteed robustness. Robo GNN learns the graph representation and GNNs iteratively towards (p, θ) robustness with a goal to minimize | L|. The learning process is guided by minimizing a combination of robust hinge loss and the distance between perturbed and original adjacency matrix. Using real-world benchmark datasets, our results conﬁrm that Robo GNN effectively improves the robustness and accuracy of GNN-based classiﬁcation, provides conﬁgurable robustness guarantees, and can explicitly suggest only small amount of links to be protected.

Related Work. Certiﬁable robustness is introduced in [Bojchevski and G unnemann, 2019]. A node is certiﬁably robust if its label predicted by a model is not sensitive to perturbations to a set of fragile edges. Models can be improved by training that minimizes a hinge loss penalty. We study (p, θ)-robustness that extends certiﬁable robustness with conﬁgurable p and θ to support the need for robustiﬁcation. GCN-Jaccard [Wu et al., 2019] removes malicious links added to nodes with dissimilar features measured by Jaccard similarity. GCN-SVD [Entezari et al., 2020] assumes an attack model [Z ugner et al., 2018] that affects high-rank singular components of the graph and performs the low-rank approximation for graph reconstruction to mitigate the effects. Edge dithering [Ioannidis and Giannakis, 2019] generates auxiliary graphs with edge insertions and deletions against adversarial perturbations to facilitate robust learning. Graph sanitation [Xu et al., 2021] solves a bilevel optimization problem that aims to modify perturbed graphs to improve underlying semi-supervised learning. Pro-GNN [Jin et al., 2020] integrates graph properties e.g., sparsity, low rank, and feature smoothness to its loss function and learns to clean graph. In contrast to prior work, our approach takes a different strategy that aims to ﬁnd protection sets and jointly learns better graph representation to ensure (p, θ)-robustness of targeted nodes that can be speciﬁed by users. Robustifying node classiﬁcation with (a) a conﬁgurable robustness guarantee, and (b) both useful auxiliary structures and links that should be protected, is not discussed in prior work.

2 Model Robustness: A Characterization Graphs. A graph G = (V, E) has a ﬁnite set of nodes V and edges E. The representation of G is a pair (X, A), where X is a feature matrix (X R|V | d) that records a feature

vector xv Rd for each node v V (obtained by embedding functions [Harris and Harris, 2010]); and A is the adjacency matrix of G. A link in G is a node pair (v, v ) V V . A perturbation of a link (v, v ) in G is either a deletion of an edge (v, v ) E, or insertion of a link (v, v ) E. A vulnerable set Ep V V of G refers to a set of links to which an adversarial perturbation may occur. We remark that Ep records the original status of links: if (v, v ) Ep is an edge in E (resp. a node pair not in E), an (adversarial) perturbation ( a ﬂip ) removes (v, v ) from (resp. inserts (v, v ) to) G. We use (v, v ) to denote a perturbation of a link (v, v ). Node classiﬁcation. Given a graph G = (V, E) and a set of labeled training nodes VT V , node classiﬁcation is to learn a model M to infer the labels of a set of unlabeled test nodes. We consider GNN-based classiﬁers. A GNN [Wu et al., 2020] transforms (X, A) to proper representation (logits) for downstream tasks. A GNN with n layers iteratively gathers and aggregates information from neighbors of a node v to compute node embedding of v. Denote the output features hi v (with v ranges over V ) at layer i as hi. A GNN computes hi

as hi = δ( n j=c Ajhi 1Wi j), where denotes the horizontal concatenation operation, Wi j refers to the learnable weight matrix of order j in layer i, δ( ) is an activation, and A is a normalized adjacency matrix. Notable GNN variants are GCN and Graph Sage [Hamilton et al., 2017] that samples ﬁxed-size neighbors (c=0,n=1) and GAT [Veliˇckovi c et al., 2017] that incorporates self-attention for neighbors. Specifically, we make case for GNNs that leverages personalized Page Rank, which mitigates over-smoothing [Cai and Wang, 2020]. In such models, Z = Πhn, where Π is a Page Rank matrix, hn is the output from the last layer of the GNN. A GNN-based classiﬁer M outputs logits Z R|V | |L| that are fed to a softmax layer and transformed to Z that encodes the probabilities of assigning a class label to a node. The training of M minimizes a loss function LCE(Z, A) = P v VT Yv ln Z v, where Yv is the label of a training node v VT , and Z v is the embedding of a training node v in VT . L can also be speciﬁed to minimize a task-speciﬁc loss.

2.1 Robustness of GNN-based Classiﬁer We start with a characterization of robustness that extends certiﬁable robustness [Bojchevski and G unnemann, 2019], which veriﬁes if predicted labels can be changed by a perturbation of size up to p. (p,θ)-robustness. Given G = (V, E), a GNN-based classiﬁer M with logits Z, a set of targeted nodes VT V , a number p, and a vulnerable set Ep (V V ), a pair (G, M) is robust at a node v VT and Ep, if a worst-case margin m yt, (v) = minc =yt m yt,c(v) > 0, where yt is the true label of v, and c is any other label (c = yt). Here m yt,c(v) is deﬁned as: m yt,c(v) = min G G Ep myt,c(v)

= min G G Ep π G (v)T Z{:,yt} Z{:,c}

where G ranges over all the possible graphs obtained by applying perturbation of up to p links from the vulnerable

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

set Ep, and π G (v) = Πv,: is the Page Rank vector of node v in the Page Rank matrix Π = (1 α)(IN αD 1A) 1. Here D is the diagonal matrix of node out-degrees with Dii = P j Aij, IN is an identity matrix, and α is teleport probability. By verifying m yt, (v) > 0 (i.e., m yt,c(v) > 0 for any c L(v) other than the correct label of v), it indicates that under any links manipulation of size p over Ep, M always predicts the label of node v as yt w.r.t. the logits Z. We say (G, M) is (p, θ)-robust w.r.t. VT and Ep, if (G, M) is robust for at least θ fraction of VT (θ [0, 1]) under any perturbations of size at most p over Ep (p |Ep|). Veriﬁcation Given a pair (G, M), vulnerable set Ep, target nodes VT and p, the (p, θ)-veriﬁcation problem is to decide if (G, M) is (p, θ)-robust w.r.t. Ep and VT .

Lemma 1: The (p, θ)-veriﬁcation problem is NP-hard even for ﬁxed θ and Ep. 2

Proof sketch: We can show that it is already NP-hard to verify a special case when θ = 1 and p = |Ep|. The lower bound of the latter follows from a reduction from the link building problem [Bojchevski and G unnemann, 2019; Olsen et al., 2012], which maximizes the Page Rank of a given target node in a graph by adding k new links. 2

We outline an algorithm to verify the (p, θ)-robustness of a pair (G, M). The algorithm veriﬁes if (G, M) is robust at up to θ fraction of the nodes in VT given Ep. Speciﬁcally, it invokes a policy iteration [Bojchevski and G unnemann, 2019] to compute a set of optimal links Wk from Ep such that minimizes m yt, (v) if perturbed. Each policy induces a perturbed graph. For any pair of labels c1,c2 of node v and Ep, it greedily selects edges that improve the policy (lower the robustness of node v) and converge to Wk that forms G, such that min G G Epπ G (v)T Z{:,yt} Z{:,c} is obtained. Monotonicity property. We next show a monotonicity property of (p, θ)-robustness in terms of the vulnerable set Ep.

Theorem 2: A (p, θ)-robust pair (G, M) w.r.t. Ep and VT remains to be (p, θ)-robust for VT and any E p Ep. 2

Proof sketch: We prove the result by contradiction. Assume (G, M) is not robust at v over E p, then there is a speciﬁc label cv = yt (yt is the predicted label of v), and a perturbed graph G obtained by perturbing at most p links in E p, such that (a) m yt, (v) = m yt,cv(v) 0, and (b) πG (v)T Z{:,yt} Z{:,cv} 0. For each such G , we can construct a perturbed graph G which bear a perturbation that leads to the change of the label of v over Ep, which contradicts that (G, M) is robust at v w.r.t. Ep. As (G, M) is robust for at least θ fraction of VT w.r.t. Ep, it remains (p, θ)-robust w.r.t. VT and any E p Ep (detailed proof in [Guan et al., 2022]). 2

2.2 Robustiﬁcation Problem

Theorem 2 tells us that it is desirable to compute a smallest set of links L Ep that should be protected from the vulnerable set, up to a point that (G, M) becomes robust for

a desirable fraction of targeted nodes over Ep \ L. Indeed, (1) protecting any set larger than L will not be necessary (unless a new threshold θ > θ is required by user); and (2) ensuring robustness for entire VT can be an overkill for ﬁnding models that are robust enough , and may cause expensive defending cost, even if (p, 1)-robustness is achievable. We formalize a pragmatic optimization problem, called (p, θ)-robustiﬁcation as follows.

Input: a pair (G, M), target nodes VT V , vulnerable set Ep, constants p and θ (p |Ep|; θ [0, 1]). Output: a triple (G , M , L), such that (1) (G , M ) is (p, θ)-robust w.r.t. VT and Ep \ L; and (2) L is a smallest subset of Ep that ensures (1).

Although desirable, the problem is nontrivial (NP-hard) even when M and Ep are ﬁxed, given the hardness of the veriﬁcation problem. We next introduce (1) a feasible algorithm to compute a small protection set L such that (G, M) is (p, θ) robust w.r.t. Ep \ L, and (2) a co-learning framework that incorporates protection set computation, veriﬁcation, and robust learning to robustify (G, M) to (G , M ).

3 Computing Protection Set

We ﬁrst develop an algorithm with a goal to compute a smallest protection set L Ep such that (G, M) is (p, θ)-robust w.r.t. VT and Ep \ L. An exact algorithm that enumerates subsets of Ep and veriﬁes the model robustness (Section 2.1) is expensive when G is large. We introduce a fast heuristic optimized by a traversal-based greedy selection strategy.

Algorithm. The algorithm, denoted as min Protect and illustrated in Algorithm 1, keeps track of the following auxiliary structures: (1) a set Vu VT , which contains the target nodes at which (G, M) is currently not robust, (2) a vector M yt, , where each of its entry records m yt, (vu) for each node vu Vu, and (3) the current fraction θ = 1 |Vu|

|VT |. In addition, each node vu has a Boolean ﬂag that indicates whether it is inspected by Prioritize T. It initializes L and Vu (line 1), and iteratively performs three major steps.

Target prioritization (procedure Prioritize T) estimates and selects a next target node v in Vu at which (G, M) is most likely to be robust upon augmenting L with small amount of links (line 8);

Protection augmentation (procedure Update L) augments L with a set of new links in Ep, computed by traversing from the selected target node vu (line 9);

Veriﬁcation (procedure Verify M), that veriﬁes (p, θ) robustness of (G, M) (line 3).

The above process repeats until a protection set L is identiﬁed that enable a (p, θ)-robust pair (G, M) (Theorem 2), or L = Ep (line 2). As Update L may make (G, M) robust at multiple nodes in VT , min Protect early terminates once Verify M asserts the desired (p, θ) robustness (lines 5-6). We next introduce the three procedures. Procedure Verify M. Procedure Verify M nontrivially optimizes the policy iteration procedure [Bojchevski and

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

Algorithm 1 min Protect Input: pair (G, M), vulnerable set Ep, target nodes VT , constants p and θ; Output: a protection set L; 1: set L := ; θ := 0; list Vu:= ; 2: while θ < θ and L = Ep do 3: θ := Verify M ((G, M), Ep, p, L)); 4: Vu := {vu|vu VT and (G, M) is not robust at vu}; 5: if (θ θ) then 6: return L; 7: while there is an unvisited node in Vu do 8: v := Prioritize T (M yt, , Vu); 9: L := L Update L (v, (G, M), Ep, p, L); 10: return L;

Procedure: Update L (vu, (G, M), Ep, p, L) 1: set Nd(vu) := ; set L := ; heap vu.H := ; 2: while there is an unvisited link (u, u ) Nd(vu) {Ep \ L} do 3: initializes vu.H with (u, u ); 4: updates worst-case margin m yt, (vu); 5: set L as all links (u, u ) in vu.H that ensures a maximum worst-case margin. 6: return L ;

G unnemann, 2019] to test if (G, M) is (p, θ)-robust at current Ep\ L. (1) It ﬁrst computes a value m c1,c2(v) for each node v VT and derives a set of optimal links Wk (|Wk| p) over Ep \ L and for any pair of labels c1 and c2, such that Wk is most likely to minimize the worst-case margin of node v. It returns K K pairs of Wk, where K is the size of label set. (2) For each node vu Vu and its predicted label yt by M (often set as the true label), it computes m yt,c(vu) and updates the Page Rank vector π G(v) over G. Here G is obtained by ﬂipping all pairs (v, v ) Wk. If m yt, (vu) = minc =yt m yt,c(vu) 0, it asserts that (G, M) is not robust at vu. It then updates Vu, and returns θ = 1 |Vu|

|VT |. If θ θ, then (G, M) is (p, θ)-robust w.r.t. Ep \ L and VT . Procedure Prioritize T. Prioritize T consults the values m yt, ( ) (obtained from procedure Verify M) of each node vu Vu, dynamically reranks Vu following the descending order of m yt, ( ), and selects the next node v with the current largest m yt, (v) (m yt, (v) <0 for any v Vu). Intuitively, it indicates that v is likely to be the next node at which (G, M) becomes robust as more links are protected to the current L. Procedure Update L. Given a target node vu Vu, Update L augments L with new links to be protected , such that (G, M) is likely to be robust at vu. Our idea is to rehearse the protection of single links near vu, and greedily augment L with (u, u ) whose protection best mitigates the impact against a worst case perturbation (obtained by perturbing all Ep \ L but (u, u )). This can be achieved by ranking the links following a descending order of their resulting worst margin m yt, (v) of vus. Intuitively, protecting (u, u ) maximally improves the worst margin of vu (hence likely to make M robust at vu), thus (u, u ) should be selected.

We say a link (v, v ) is in d-hop neighborhood (d 1) of a node vu (denoted as (v, v ) Nd(vu)) if there is a sequence of d links (v0, v1),. ..(vd 1, vd), such that vu = v0, vd 1 = v, vd = v , and (vi, vi+1) Ep for i [0, d 1]. For each vu Vu, Update L maintains a heap vu.H. Each entry in vu.H contains (a) a link (v, v ) Nd(vu), (b) a graph GEp\(v,v ) L, obtained by perturbing all links in Ep \ L but (v, v ), and (c) the worst-case margin m yt, (v) determined by GEp\(v,v ) L (Section 2.1). Given a node vu Vu selected by Prioritize T, Update L starts a breadth ﬁrst traversal and explores up to Nd(vu) (d is set as the smallest integer value such that Nd(vu) {Ep \ L} = by default). During the traversal, it dynamically inserts unvisited link (v, v ) Nd(vu). For each visited (v, v ), it initializes the entry vu.H, and computes the worstcase margin. For all the links in Nd(vu), it selects the link (v, v ) with the largest worst-case margin in vu.H and adds it to L. This process repeats until no new links can be found. Analysis. Algorithm min Protect correctly returns a protect set L that either ensures (p, θ)-robust pair (G, M) w.r.t. Ep \ L and VT , or a counterpart that ensures a largest fraction θ of VT at which (G, M) is robust when terminates. This is ensured by several invariants below. (1) Verify M performs policy iteration [Bojchevski and G unnemann, 2019] that converges to optimal perturbations over Ep \ L and correctly computes m yt,c(v) to verify model robustness. (2) Update L augments L in a non-decreasing manner, which ensures the termination of min Protect (Theorem 2). (3) Prioritize T does not miss nodes at which (G, M) is not robust. Optimization. A main bottleneck is the computation of the matrix inverse operation [Ma et al., 2021]), for computing m c1,c2(v) (Verify M, line 3 of min Protect) and m yt, (v) (Update L). To reduce the cost, we leverage approximate computation [Bojchevski et al., 2020] to approximate the dynamically maintained adjacency matrix A with a sparse matrix Πε that approaches (1 α)(IN αD 1A ) 1 (see [Guan et al., 2022] for details).

4 Robo GNN: A Co-learning Framework We next present Robo GNN, a co-learning framework to robustify (G, M) towards (p, θ)-robustness. Robo GNN (illustrated in Algorithm 2) generates a triple (<S ,A >, M , L), where S is a learned graph structure representation of G and A is the recovered adjacency matrix of G . The framework Robo GNN iteratively improves (G, M) by interleaving two processes, consistently towards improved robustness: (1) For a ﬁxed graph A (initialized as A), computing L to reﬁne Ep (lines 5-8) as in ( invoking ) min Protect, and (2) Jointly improves structure representation <S ,A > (lines 9-11) and M (lines 12-13) in the context of current vulnerable set Ep \ L. Before ﬁxing graph structure and alternating updating model parameters, Robo GNN updates G in Update A (line 11) by ﬁxing the inconsistency between the adjacency matrix A of G and L (e.g., if (u, u ) is an edge in L but not in A , Robo GNN inserts (u, u ) to A ). It eventually veriﬁes the modiﬁed M over Ep \ L (line 14), and returns the triple (<S ,A >, M , L) whenever (p, θ)- robustness is achieved, or no link can be added to L (line 4).

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

Algorithm 2 Robo GNN Input: pair (G, M), vulnerable set Ep, target nodes VT , constants p and θ; Output: triple (<S ,A >, M , L); 1: Initialize <S ,A >:=<A,A>; θ :=0, M :=M, L:= ; 2: θ := Verify M ((G , M ), Ep, p, L)); 3: Vu := {vu|vu VT and (G , M ) is not robust at vu}; 4: while θ < θ and | L| < |Ep| do 5: update Vu and visiting status of nodes in Vu; 6: while there is an unvisited node in Vu do 7: v := Prioritize T (M yt, , Vu); 8: L := L Update L (v, (G , M ), Ep, p, L); 9: for i =1 to ς do 10: S := S η S ( S A 2 F + λL); 11: A := Update A(A , L); 12: for i =1 to τ do 13: M :=M η M L; 14: θ := Verify M ((G , M ), Ep, p, L)); 15: return (<S ,A >, M , L);

Cora Citeseer Pubmed # Nodes 2,708 3,327 19717 # Edges 5,429 4,732 44338 # Features per Node 1,433 3,703 500 # Classes 7 6 3 # Training Nodes 140 120 60 # Validation Nodes 500 500 500 # Test Nodes 1,000 1,000 1000 # |Ep| 1650 1200 376 (p, θ) (177,0.95) (848,0.95) (370,1.0)

Table 1: Settings: Datasets, training, and robustiﬁcation

Robust cross-entropy loss. Robo GNN co-learns S and M by consistently minimizing a hinge loss penalty, which aims to enforce (S , M ), w.r.t. current vulnerable set Ep \ L), to be robust at the nodes by ensuring a margin of at least positive threshold m. Speciﬁcally, the robust loss is deﬁned as:

v VT [LCE(y v, π G(v)T Z)+

c L(v),c =y v max(0, m m yv,c(v))].

It then learns S by minimizing a weighted combination of L and feature difference (lines 9-10), and M by minimizing L.

5 Experiments We next experimentally verify the effectiveness of Robo GNN on improving the robustness and accuracy of GNN-based classiﬁcation, the learning cost, and the impact of parameters. Experiment Setting. We use three real-world datasets: Cora [Mc Callum et al., 2000], Citeseer [Giles et al., 1998] and Pubmed [Sen et al., 2008]. Each node has features derived from a bag-of-words representation of the document it refers to, and a class label denoting topic area (see Table 1). Generation of graphs G. We adopt a mixture of adversarial strategies, including non-targeted attacks [Z ugner and G unnemann, 2019], random perturbation [Yuan et al., 2017],

and property-preserving link attacks(that aim to maintain degree distribution) [Z ugner et al., 2018]. These attacks are designed under the same principle to minimize the probability of correct class prediction. For each dataset, we manipulate at most 30% edges to produce a graph G as input graph for Robo GNN. This sufﬁces to cause performance degradation of GNNs if learned from G [Z ugner and G unnemann, 2019]. We generate vulnerable sets Ep with random-walk based sampling [Guan et al., 2022]. The generation of Ep and Robo GNN learning do not assume prior knowledge. Generate classiﬁers M. We use the following GNN-based classiﬁers as input. (1) GCN [Kipf and Welling, 2016], (2 ) GAT [Veliˇckovi c et al., 2017], and (3) π-PPNP, a class of GNNs that decouples feature transformation from feature aggregation to optimize classiﬁcation [Bojchevski and G unnemann, 2019]. We compare the accuracy and robustness of an input model M and its robustiﬁed counterpart M . We also evaluate Robo GNN as an end-to-end framework, which directly learns a robust model from scratch (i.e., generate (G , M ) given (G, )), with the following baselines. (1) cert PPNP [Bojchevski and G unnemann, 2019] learns a more robust counterpart of π-PPNP by robust training [Bojchevski and G unnemann, 2019]; and (2) Pro GNN [Jin et al., 2020], which learns graph representations and GNNs from scratch. In addition, we develop a variant as U Robo GNN, by removing the optimization on pagerank. Conﬁguration. We train a two-layer network for all the input models with the same set of hyper-parameters settings (e.g., dropout rate, number of hidden units). The training epoch number is set as 300. For each dataset, we ﬁx the learning rate for Pro-GNN, cert PPNP, and Robo GNN. The conﬁguration of input GCN, GAT and Pro-GNN are calibrated to yield consistent and best performance over benchmark metrics as in [Kipf and Welling, 2016; Veliˇckovi c et al., 2017; Jin et al., 2020]. we report the average accuracy (acc.) for multiclass classiﬁcation. All Experiments are executed on a Unix environment with GPU Nvidia P-100. The source code and datasets are available1.

Experimental Results. We next present our ﬁndings. Exp-1: Effectiveness of Robustiﬁcation. We ﬁrst evaluate Robo GNN on improving the accuracy of input models. Table 3 reports the results using GCN and π-PPNP. Here Robo GNN (GCN) and Robo GNN (π-PPNP) shows the counterparts M over G for the same set of test nodes. (1) During the co-learning, Robo GNN ensures an increasing robustness of the improved model compared with a previous counterpart, in all cases (not shown). (2) The improved robustness in turn signiﬁcantly improves the accuracy of input models over test nodes. For example, Robo GNN achieves on average 45.3% (resp. 31%) gains on F1 for GCN (resp. π-PPNP). We ﬁnd that the robustiﬁed M over G yields more consistent label prediction, and better approaches to the performance of yardstick models learned from original (unknown) graphs that are not perturbed. ([Guan et al., 2022] for more analysis). Impact of factors. We next evaluate the impact of perturbation size and conﬁgurations of robustness to the effectivenes. We

1https://github.com/CWRU-DB-Group/robognn

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

dataset Cora Citeseer Pubmed metrics acc. F1 acc. F1 acc. F1. GCN (A) 71.3% 71.42% 51.0% 48.80% 64.1% 63.19% GCN(A ) 73.1% 72.83% 56.1% 53.79% 65.0% 63.99% GAT (A) 74.8% 73.68% 65.0% 61.06% 63.7% 62.79% GAT(A ) 76.7% 76.69% 65.3% 62.05% 63.7% 62.79% Table 2: Improved graph structure A beneﬁts GNN learning. Bold: models learned with A from scratch.

dataset Cora Citeseer Pubmed metrics acc. F1 acc. F1 acc. F1. GCN 44.1% 44.89% 39.7% 38.80% 49.7% 48.49% Robo GNN(GCN) 76.7% 75.65% 54.0% 51.66% 65.4% 63.99% π-PPNP 43.0% 43.64% 50.0% 48.48% 40.8% 34.03% Robo GNN(π-PPNP) 75.9% 74.95% 56.9% 54.58% 43.9% 36.18% Table 3: Robustify GNN models with Robo GNN framework. Bold: robustiﬁed models.

50 51 52 53 54 55 56 57

20 40 60 80 100

Accuracy(%)

Robo(GCN) Robo(π-PPNP)

(a) Varying | L|

65% 70% 75% 80% 85%

Accuracy(%)

Robo(GCN) Robo(π-PPNP)

(b) Varying θ

1500 1600 1700 1800 1900

Accuracy(%)

Robo(GCN) Robo(π-PPNP)

(c) Varying |Ep|

10 20 30 40 50

Time (seconds)

Robo(GCN) U_Robo(GCN)

(d) Varying | L|

1500 1550 1600 1650 1700

Time (seconds)

Robo(GCN) U_Robo(GCN)

(e) Varying |Ep|

50 55 60 65 70 75 80

Pr=10% Pr=15% Pr=20%

Accuracy(%)

Pro-GNN cert PPNP

(f) Varying Pr (end-to-end)

Figure 1: Performance: accuracy and efﬁciency

report the results over Cora. The results from other datasets are consistent (see [Guan et al., 2022] for details). Impact of | L|. Using the default setting in Table 1, we vary the size of allowed protection set from 20 to 100, and terminate Robo GNN whenever L reaches a certain size. Fig. 1(a) tells us that Robo GNN (1) can effectively improve the accuracy of input models (from 51% to 57%) as more links are protected, (2) ensures a desirable (p, θ)-robustness, and to achieve these, (3) explicitly suggests only a small set ( 100, 10% of vulnerable set) of links to be protected. Impact of θ. Fixing other parameters as default, we vary θ from 65% to 85% (Fig. 1(b)). (1) Ensuring robustness at more target nodes improves the accuracy, which is consistent with our observation in Fig. 1(a). (2) Robo GNN effectively responses to different robustness requirements. It improves

the accuracy of π-PPNP from 45% to 65% by ensuring a (150, 85%)-robust model from a (150, 65%) counterpart. Impact of |Ep|.Fixing other parameters, we vary the size of vulnerable set from 1500 to 1900. Fig. 1(c) shows that it becomes more difﬁcult for Robo GNN to maintain the robustness. Indeed, larger Ep indicates more adversarial perturbations to prevent robustness for the target nodes. On the other hand, its performance is not very sensitive, due to its ability to co-learn both models and graph representations that better mitigate the impact of perturbations. Efﬁciency. Using the same default setting as Fig. 1(a) (resp. Fig. 1(c)), Fig. 1(d) (resp. Fig. 1(e)) veriﬁes that Robo GNN takes more time to learn robustiﬁed models and graph representation with larger | L| (resp. |Ep|). On the other hand, (1) optimization reduces the learning cost by 67% on average, and (2) the learning is less sensitive to |Ep| given the early termination of min Protect as it augments L (Theorem 2). Exp-2: End-to-end performance. Robo GNN supports endto-end learning of a robust model with desired robustness. When generating graph G, we vary the perturbation rate Pr, e.g., the ratio of changed edges, from 10% to 20%, Fig. 1(f) shows that Robo GNN achieves best performance improvement due to robustness guarantees, among all baselines. Exp-3: Usability of protection set. We also evaluate how L can be used to suggest corrections of adjacency matrix A to improve GNNs. Given an original graph G, we ﬁrst perform adversarial perturbation and derive a perturbed adjacency matrix A. We then use Robo GNN to obtain L over a robustiﬁed counterpart (G , M ). Table 2 veriﬁes that L can effectively suggest recovered adjacency matrix which directly leads to the training of more accurate models. This indicates the application of Robo GNN in explicit link correction.

6 Conclusion

We have proposed a novel framework, Robo GNN, that can improve the robustness of GNN-based classiﬁcation and also suggest desired graph structures under link perturbations. Our experimental study conﬁrms that Robo GNN achieves such effects. A future topic is to enable Robo GNN for link repairing to improve downstream GNN-based tasks.

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)

Acknowledgments

This work is supported by NSF under CNS-1932574, OIA1937143, ECCS-1933279, CNS-2028748, OAC-2104007 and Do E under DE-EE0009353.

[Bojchevski and G unnemann, 2019] Aleksandar Bojchevski and Stephan G unnemann. Certiﬁable robustness to graph perturbations. In Neur IPS, 2019.

[Bojchevski et al., 2020] Aleksandar Bojchevski, Johannes Klicpera, Bryan Perozzi, Amol Kapoor, Martin Blais, Benedek R ozemberczki, Michal Lukasik, and Stephan G unnemann. Scaling graph neural networks with approximate pagerank. In KDD, 2020.

[Cai and Wang, 2020] Chen Cai and Yusu Wang. A note on over-smoothing for graph neural networks. ar Xiv preprint ar Xiv:2006.13318, 2020.

[Dai et al., 2018] Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. Adversarial attack on graph structured data. ar Xiv preprint ar Xiv:1806.02371, 2018.

[Entezari et al., 2020] 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 WSDM, 2020.

[Giles et al., 1998] C. Lee Giles, Kurt D. Bollacker, and Steve Lawrence. Citeseer: An automatic citation indexing system. In Proceedings of the Third ACM Conference on Digital Libraries, 1998.

[Gori et al., 2005] 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, volume 2, pages 729 734, 2005.

[Guan et al., 2022] Sheng Guan, Hanchao Ma, and Yinghui Wu. Robognn: Robustifying node classiﬁcation under link perturbation, full version. https://github.com/ CWRU-DB-Group/robognn/blob/main/full.pdf, 2022. Accessed: 2022-06-08.

[Hamilton et al., 2017] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, 2017.

[Harris and Harris, 2010] David Harris and Sarah Harris. Digital design and computer architecture. Morgan Kaufmann, 2010.

[Ioannidis and Giannakis, 2019] Vassilis N Ioannidis and Georgios B Giannakis. Edge dithering for robust adaptive graph convolutional networks. ar Xiv preprint ar Xiv:1910.09590, 2019.

[Jin et al., 2020] Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. KDD, 2020.

[Kipf and Welling, 2016] Thomas N Kipf and Max Welling. Semi-supervised classiﬁcation with graph convolutional networks. ar Xiv preprint ar Xiv:1609.02907, 2016. [Ma et al., 2021] Yao Ma, Xiaorui Liu, Tong Zhao, Yozen Liu, Jiliang Tang, and Neil Shah. A uniﬁed view on graph neural networks as graph signal denoising. In CIKM, 2021. [Mc Callum et al., 2000] Andrew Kachites Mc Callum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 2000. [Olsen et al., 2012] Martin Olsen, Anastasios Viglas, and Ilia Zvedeniouk. An approximation algorithm for the link building problem. ar Xiv preprint ar Xiv:1204.1369, 2012. [Paulheim, 2017] Heiko Paulheim. Knowledge graph reﬁnement: A survey of approaches and evaluation methods. Semantic web, 2017. [Sen et al., 2008] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classiﬁcation in network data. AI magazine, 2008. [Tran et al., 2017] Cong Tran, Won-Yong Shin, and Andreas Spitz. Community detection in partially observable social networks. ar Xiv preprint ar Xiv:1801.00132, 2017. [Veliˇckovi c et al., 2017] Petar Veliˇckovi c, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. ar Xiv preprint ar Xiv:1710.10903, 2017. [Wu et al., 2019] Huijun Wu, Chen Wang, Yuriy Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu. Adversarial examples on graph data: Deep insights into attack and defense. IJCAI, 2019. [Wu et al., 2020] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. Neur IPS, 2020. [Xu et al., 2021] Zhe Xu, Boxin Du, and Hanghang Tong. Graph sanitation with application to node classiﬁcation. ar Xiv preprint ar Xiv:2105.09384, 2021. [Yuan et al., 2017] Xiaoyong Yuan, Pan He, Qile Zhu, Rajendra Rana Bhat, and Xiaolin Li. Adversarial examples: Attacks and defenses for deep learning. corr abs/1712.07107 (2017). ar Xiv preprint ar Xiv:1712.07107, 2017. [Z ugner and G unnemann, 2019] Daniel Z ugner and Stephan G unnemann. Adversarial attacks on graph neural networks via meta learning. ICLR, 2019. [Z ugner et al., 2018] Daniel Z ugner, Amir Akbarnejad, and Stephan G unnemann. Adversarial attacks on neural networks for graph data. In KDD, 2018.

Proceedings of the Thirty-First International Joint Conference on Artiﬁcial Intelligence (IJCAI-22)