RoboGNN: Robustifying Node Classification under Link Perturbation

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 classifier 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 modified 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| reflects "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 configurable robustness in terms of a threshold θ over designated target nodes, enabling flexible robustification 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 RoboGNN, a colearning framework to robustify GNN-based classification with desirable, configurable robustness guarantees.

(1) We introduce a notion of (p, θ)-robustness to characterize the robustness of GNNs (Section 2). Given graph G and classifier 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, θ) verification and robustification 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 to refine 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 finding 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 efficient traversal. (3) Based on the verification and minimality condition, we present RoboGNN, a framework to robustify an input model with guaranteed robustness. RoboGNN 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 confirm that RoboGNN effectively improves the robustness and accuracy of GNN-based classification, provides configurable robustness guarantees, and can explicitly suggest only small amount of links to be protected.

RelatedWork. Certifiable robustness is introduced in [Bojchevski and G¨unnemann, 2019]. A node is certifiably 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 certifiable robustness with configurable p and θ to support the need for robustification.

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 find protection sets and jointly learns better graph representation to ensure (p, θ)-robustness of targeted nodes that can be specified by users. Robustifying node classification with (a) a configurable robustness guarantee, and (b) both useful auxiliary structures and links that should be protected, is not discussed in prior work.

2 Model Robustness: ACharacterization

Graphs. A graph G = (V,E) has a finite 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 flip") removes (v, v′ ) from (resp. inserts (v, v′ ) to) G. We use (v, v′ ) to denote a perturbation of a link (v, v′ ).

Node classification. Given a graph G = (V,E) and a set of labeled training nodes VT ⊆ V , node classification is to learn a model M to infer the labels of a set of unlabeled test nodes.

We consider GNN-based classifiers. 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 hiv (with v ranges over V ) at layer i as hi . A GNN computes hi as hi = δ(‖nj=c ˜ Aj hi-1Wij ), where ‖ denotes the horizontal concatenation operation, Wij 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 GraphSage [Hamilton et al., 2017] that samples fixed-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 PageRank, which mitigates over-smoothing [Cai and Wang, 2020]. In such models, Z =Πhn , where Π is a PageRank matrix, hn is the output from the last layer of the GNN.

A GNN-based classifier 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) = - ∑v∈VT Yv lnZ ′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 specified to minimize a task-specific loss.

2.1 Robustness of GNN-based Classifier

We start with a characterization of robustness that extends certifiable robustness [Bojchevski and G¨unnemann, 2019], which verifies if predicted labels can be changed by a perturbation of size up to p.

(p,θ)-robustness. Given G = (V,E), a GNN-based classifier 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 defined as:

where ˜G ranges over all the possible graphs obtained by applying perturbation of up to p links from the vulnerable set Ep, and π ˜G (v) =Πv,: is the PageRank vector of node v in the PageRank matrix Π = (1 - α)(IN - αD-1A)-1 . Here D is the diagonal matrix of node out-degrees with Dii = ∑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|).

Verification Given a pair (G,M), vulnerable set Ep, target nodes VT and p, the (p, θ)-verification problem is to decide if (G,M) is (p, θ)-robust w.r.t. Ep and VT .

Lemma 1: The (p, θ)-verification problem is NP-hard even for fixed θ and Ep. ✷

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 PageRank of a given target node in a graph by adding k new links. ✷

We outline an algorithm to verify the (p, θ)-robustness of a pair (G,M). The algorithm verifies if (G,M) is robust at up to θ fraction of the nodes in VT given Ep. Specifically, 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. ✷

Proof sketch: We prove the result by contradiction. Assume (G,M) is not robust at v over E′p , then there is a specific 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 Robustification 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 finding 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, θ)-robustification 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 fixed, given the hardness of the verification 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, verification, and robust learning to robustify (G,M) to (G′ ,M ′ ).

3 Computing Protection Set

We first 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 verifies 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 minProtect 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 flag that indicates whether it is inspected by PrioritizeT. It initializes ∆L and Vu (line 1), and iteratively performs three major steps.

• Target prioritization (procedure PrioritizeT) 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 UpdateL) augments ∆L with a set of new links in Ep, computed by traversing from the selected target node vu (line 9);
• Verification (procedure VerifyM), that verifies (p, θ) robustness of (G,M) (line 3).

The above process repeats until a protection set ∆L is identified that enable a (p, θ)-robust pair (G,M) (Theorem 2), or ∆L = Ep (line 2). As UpdateL may make (G,M) robust at multiple nodes in VT , minProtect early terminates once VerifyM asserts the desired (p, θ) robustness (lines 5-6).

We next introduce the three procedures.

Procedure VerifyM. Procedure VerifyM nontrivially optimizes the policy iteration procedure [Bojchevski and

Algorithm 1 minProtect

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: θ′ := VerifyM ((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 := PrioritizeT (M ∗ yt,∗ , Vu);
• 9: ∆L := ∆L ∪ UpdateL (v, (G,M),Ep, p,∆L);
• 10: return ∆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′ ;

Procedure: UpdateL (vu, (G, M), Ep, p, ∆L)

G¨unnemann, 2019] to test if (G,M) is (p, θ)-robust at current Ep\∆L. (1) It first 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 PageRank vector π ˜G(v) over ˜G. Here ˜G is obtained by flipping 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 PrioritizeT. PrioritizeT consults the values m∗yt,∗ (·) (obtained from procedure VerifyM) 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 UpdateL. Given a target node vu ∈ Vu, UpdateL 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, UpdateL 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 PrioritizeT, UpdateL starts a breadth first 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. AlgorithmminProtect 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) VerifyM 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) UpdateL augments ∆L in a non-decreasing manner, which ensures the termination of minProtect (Theorem 2). (3) PrioritizeT does not miss nodes at which (G,M) is not robust.

Optimization. Amain bottleneck is the computation of the matrix inverse operation [Ma et al., 2021]), for computing m∗c1,c2 (v) (VerifyM, line 3 of minProtect) and m∗yt,∗ (v) (UpdateL). 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 RoboGNN: ACo-learning Framework

We next present RoboGNN, a co-learning framework to robustify (G,M) towards (p, θ)-robustness. RoboGNN (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 RoboGNN iteratively improves (G,M) by interleaving two processes, consistently towards improved robustness: (1) For a fixed graph A′ (initialized as A), computing ∆L to refine Ep (lines 5-8) as in ("invoking") minProtect, 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 fixing graph structure and alternating updating model parameters, RoboGNN updates G′ in UpdateA (line 11) by fixing 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′ , RoboGNN inserts (u, u′ ) to A′ ). It eventually verifies the modified 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).

Algorithm 2 RoboGNN

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: θ′ := VerifyM ((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 := PrioritizeT (M ∗ yt,∗ , Vu);
• 8: ∆L := ∆L∪ UpdateL (v, (G′ ,M ′ ),Ep, p,∆L);
• 9: for i =1 to ς do
• 10: S′ := S′ - η∇S′(‖ S′ -A‖2F +λL);
• 11: A′ := UpdateA(A′ ,∆L);
• 12: for i =1 to τ do
• 13: M ′ :=M ′ - η′∇M′L;
• 14: θ′ := VerifyM ((G′ ,M ′ ),Ep, p,∆L));
• 15: return (<S′ ,A′>, M ′ , ∆L);

Robust cross-entropy loss. RoboGNN 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. Specifically, the robust loss is defined as:

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 RoboGNN on improving the robustness and accuracy of GNN-based classification, the learning cost, and the impact of parameters.

Experiment Setting. We use three real-world datasets: Cora [McCallum 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 RoboGNN. This suffices 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 RoboGNN learning do not assume prior knowledge.

Generate classifiers M. We use the following GNN-based classifiers 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 classification [Bojchevski and G¨unnemann, 2019]. We compare the accuracy and robustness of an input model M and its robustified counterpart M ′ .

We also evaluate RoboGNN 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) certPPNP [Bojchevski and G¨unnemann, 2019] learns a more robust counterpart of π-PPNP by robust training [Bojchevski and G¨unnemann, 2019]; and (2) ProGNN [Jin et al., 2020], which learns graph representations and GNNs from scratch. In addition, we develop a variant as U RoboGNN, by removing the optimization on pagerank.

Configuration. 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 fix the learning rate for Pro-GNN, certPPNP, and RoboGNN. The configuration 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 classification. All Experiments are executed on a Unix environment with GPU Nvidia P-100.

The source code and datasets are available 1 .

Experimental Results. We next present our findings.

Exp-1: Effectiveness of Robustification. We first evaluate RoboGNN on improving the accuracy of input models. Table 3 reports the results using GCN and π-PPNP. Here RoboGNN (GCN) and RoboGNN (π-PPNP) shows the counterparts M ′ over G for the same set of test nodes. (1) During the co-learning, RoboGNN ensures an increasing robustness of the improved model compared with a previous counterpart, in all cases (not shown). (2) The improved robustness in turn significantly improves the accuracy of input models over test nodes. For example, RoboGNN achieves on average 45.3% (resp. 31%) gains on F1 for GCN (resp. π-PPNP). We find that the robustified 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 configurations of robustness to the effectivenes. We report the results over Cora. The results from other datasets are consistent (see [Guan et al., 2022] for details).

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

Impact of |∆L|. Using the default setting in Table 1, we vary the size of allowed protection set from 20 to 100, and terminate RoboGNN whenever ∆L reaches a certain size. Fig. 1(a) tells us that RoboGNN (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) RoboGNN 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 difficult for RoboGNN 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.

Efficiency. Using the same default setting as Fig. 1(a) (resp. Fig. 1(c)), Fig. 1(d) (resp. Fig. 1(e)) verifies that RoboGNN takes more time to learn robustified 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 minProtect as it augments ∆L (Theorem 2). Exp-2: End-to-end performance. RoboGNN supports "endto-end" learning of a robust model with desired robustness. shows that RoboGNN achieves best performance improve-

When generating graph G, we vary the perturbation rate Pr, e.g., the ratio of changed edges, from 10% to 20%, Fig. 1(f) ment 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 first perform adversarial perturbation and derive a perturbed adjacency matrix A. We then use RoboGNN to obtain ∆L over a robustified counterpart (G′ ,M ′ ). Table 2 verifies that ∆L can effectively suggest "recovered' adjacency matrix which directly leads to the training of more accurate models. This indicates the application of RoboGNN in explicit link correction.

6 Conclusion

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

Acknowledgments

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