On the Relationship between Heterophily and Robustness of Graph Neural Networks
Authors: Jiong Zhu
Junchen Jin
Donald Loveland
Michael T Schaub
Danai Koutra
Venue: ICLR 2022 Submitted (2022)
Keywords: graph neural networks
adversarial attacks
heterophily
structural perturbation
robustness
relation

Abstract: Empirical studies on the robustness of graph neural networks (GNNs) have suggested a relation between the vulnerabilities of GNNs to adversarial attacks and the increased presence of heterophily in perturbed graphs (where edges tend to connect nodes with dissimilar features and labels). In this work, we formalize the relation between heterophily and robustness, bridging two topics previously investigated by separate lines of research. We theoretically and empirically show that for graphs exhibiting homophily (low heterophily), impactful structural attacks always lead to increased levels of heterophily, while for graph with heterophily the change in the homophily level depends on the node degrees. By leveraging these insights, we deduce that a design principle identified to significantly improve predictive performance under heterophily—separate aggregators for ego- and neighbor-embeddings—can also inherently offer increased robustness to GNNs. Our extensive empirical analysis shows that GNNs adopting this design alone can achieve significantly improved empirical and certifiable robustness compared to the best-performing unvaccinated model. Furthermore, models with this design can be readily combined with explicit defense mechanisms to yield improved robustness with up to 18.33% increase in performance under attacks compared to the best-performing vaccinated model.

Under review as a conference paper at ICLR 2022
ON THE RELATIONSHIP BETWEEN HETEROPHILY AND ROBUSTNESS OF GRAPH NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Empirical studies the robustness of graph neural networks (GNNs) have sug- gested a relation between the vulnerabilities of GNNs to adversarial attacks and the increased presence of heterophily perturbed graphs (where edges tend connect nodes with dissimilar features and labels). In this work, we formalize the relation between heterophily and robustness, bridging two topics previously investigated by separate lines of research. We theoretically and empirically show that for graphs exhibiting homophily (low heterophily), impactful structural at- tacks always lead to increased levels of heterophily, while for graph with het- erophily the change in the homophily level depends on the node degrees. By leveraging these insights, we deduce that a design principle identified to signif- icantly improve predictive performance under heterophily- sspaaate aggregators for ego- and brighbor-embeddingss can also inherently offer increased robust- ness to GNNs. Our extensive empirical analysis shows that GNNs adopting this design alone can achieve significantly improved empirical and certifable robust- ness compared to the best-performing unvaccinated model. Furthermore, models with this design can be readily combined with explicit defense mechanisms yield improved robustness with up to 18. 8.33% increase in performance under at- tacks compared to the best-performing vaccinated model.
INTRODUCTION
Graph neural networks (GNNs) aim to translate the enormous empirical success of deep learning to data defined on non-Fuclidean domains, such as manifolds or graphs (Bronstein et al.] (017)) and have become important tools to solve a variety of learning problems for graph structured and geometrically embedded data. However, recent works show that GNNs-much like their "standard" deep learning counterparts have high sensitivity adversarial attacks: intentionally introduced minor changes in the graph structure can lead to significant changes in performance. This finding, first articulated by Zügner et al. (2018) and Dai al. (2018). has triggered studies that investigated different attack scenarios Xu et al.) 2019: Wu et al. 2019 Li et al. 2020a Ma et al., (020)).
A different aspect of GNNs that has been scrutinized recently is that most GNNs do not perform well with many heterophilous datasets. GNNs generally perform well under homophily (or assortativity), i... the tendency of nodes with similar features or class labels connect (Pei et al. 2020 Zhu al.) 2020). Such datasets are thus called homophilous (or assortative). While homophilous datasets dominate the study of networks, homophily is not universal principle; certain networks, such as romantic relationship networks or predator-prey networks in ecology, are mostly heterophilous (or disassortative). Employing a GNN which does not account for heterophily can lead to significant performance loss in heterophilous settings (Abu-El-Haija et al. 2019 Zhu et al. 2020: Bo et al. 2021). Previous works have thus proposed architectures for heterophilous data.
While previous work has focused on naturally-occurriag heterophily, heterophilous interactions may also be introduced as adversarial noise: as many GNNs exploit homophilous correlation, they can be sensitive to changes that render the data more heterophilous. A natural follow-up question is and how this observation manifests itself in previously proposed attacking strategies on GNNs. In this work, we thus investigate the relation between heterophily and robustness of GNNs against adversarial perturbations of graph structure, focusing on semi-supervised node classification tasks.
More specifically, main contributions are:

---

Under review as a conference paper at ICLR 2022
Formalization: We formalize the relation between adversarial structural attacks and the change of homophily level in the underlying graphs with theoretical ($3.1) and empirical ($5.1) analysis. Specifically, we show that on homophilous graphs, effective structural attacks lead to increased heterophily, while, on heterophilous graphs, they alter the homophily level contingent on node degrees. To our knowledge, this is the first formal analysis of such kind.
Heterophily-iisspree Design: We show how the relation between attacks and heterophily can in- spire more robust GNNs by demonstrating that key architectural feature in handling heterophily, separate aggregators for ego- and neighbor-embede embeddings, also improves the robustness of GNNs against attacks ($3.2).
Extensive Empirical Analysis: We show the effectiveness of the heterophilous design in im- proving empirical ($5.2) and certifiable ($5.3) robustness of GNNs with extensive experiments on real-world homophilous and heterophilous datasets. Specifically, we compare GNNs with this GNNs, to non-adjusted models, including state- of t--the-art models designed with robustness in mind. We find that beterophily-adjusse up to 5 times more certifiably robust and have stronger performance under attacks by up to 32.92% compared to non-adjusted, standard models. Moreover, this design can be combined with exist- ing vaccination mechanisms, yielding up to 18.33% higher accuracy under attacks than the best non-adjusted vaccinated model.
design, which we refer to as heterophily-adiissee
GNNs are
2 NOTATION AND PRELIMINARIES
Let G - EV,E, X) be simple graph with node set V. edge set & and node attributes X. The one-hop neighborhood (1) = {u (u, v) E E} of node v V is the set of all nodes directly adjacent to v; the k-hop neighborhood of v E V is the set of nodes reachable by shortest path of length k. We represent the graph & algebraically by an adjacency matrix A E {0, 13 V|x[V| and node feature matrix X E R 1 We use A, = A + I to denote the adjacency matrix with self-loops added, and denote the corresponding -toshtccasttic matrices as A D-1 A and A. D Ag. respectively, where D is diagonal matrix with D; = Σ, Aij (D, is defined analogously). We further assume that there exists a vector y. which contains a unique class label ye for each node v. Given a training set Ty {V11, 31), (U2: V2)...) of labeled nodes, the goal of semi-supervised node classification to learn a mapping E V - y from the nodes to the set Y of class labels.
Graph neural networks (GNNs). Most current GNNs operate according to a message passing paradigm where a representation vector r, is assigned to each node v E V and continually updated by K layers of learnable transformations. These layers first aggregate representations over neigh- boring nodes (1)) and then update the current representation via an encoder ENC. For prevailing GNN models like GCN (Kipf & Welling, 2017) and GAT (Veličković et al. 2018), each layer can be formalized as (M) ENC [AGGR
(k-1) E N(v) U (w) where AGGR is the mean func- tion weighted by node degrees (GCN) or an attention mechanism (GAT), and ENC is a learnable (nonlinear) mapping.
{r!!
Adversarial attacks on graphs. Given a graph g (V,E, and a GNN ʃ that processes G. an adversarial attacker tries to create a perturbed graph g' = (V,E', X. with modified edge-set gr such that the performance of the GNN f is maximally degraded. The information available to the attacker can vary under different scenarios (Jin et al.) 2020a; Sun et al. (020)). Here, we follow the gray-box formalization by Zügnnr et al. (2018), where the attacker knows the training set Ty, but not the trained GNN f. The attacker thus considers surrogate GNN and picks perturbations that maximize an attack loss Latk (Zügner et al. 2018 Zügner & Günnemann, 2019a),, assuming that attacks to the surrogate model are transferable to the attacked GNN. For node classification, the attack loss Latk quantifies how the predictions 2, < [0. 1} made by the GNN f differ from the true labels y. For a targeted attack of node e with class label y/2 E 3/ we adopt the negative classification margin (CM-type) (Zügner et al. 2018: Xu et al. 2019)): Latk -A. - -(Zr.y. max ). The attacker usually has additional constraints, such as a limit on the size of the perturbations allowed (Zügner al. 2018 Zügner& & Günnemann 2019a).
Taxonomy of attacks. We follow the taxonomy of attacks introduced in eJin al. 2020a Sun et al. 2020). For node classification, the attacker may aim to change the classification of specific node U E (targeted attack), or to decrease the overall classification accuracy (untargeted attack). Attacks can also happen different stages of the training process: we refer to attacks introduced
2

---

1. the attack loss Lask ($2) of the target vo increases only for actions increasing heterophily, i.e., when removing a homophilous edge or path, or adding a heterophilous edge or path to node v; Under review as a conference paper at ICLR 2022
before training (pre-training) poison attacks, and attacks introduced after the training process (and before potential retraining on perturbed data) as (post-training) evasion attacks. While our theoretical analysis ($3) mainly considers targeted evasion attacks, we consider other attacks in our empirical evaluation ($5)
Characterizing homophily and heterophily in graphs. Using class labels, we characterize the types of connections in graph contributing to its overall level of homophily/heetrrohhiy as follows: Definition (Homo/Heterophilonr path and edge) A k-hop homophilous path from node w to a length-k k path between endpoint nodes with the same class label yuu = yo- Otherwise, the path is called heterophilous. A homophilous or heterophilous edge is special case with k = 1.
Following (Zhu al. 2020 Lim et al. 2021). define the homophily ratio h as:
Definition (Homophily ratio) The homophily ratio the fraction of homophilous edges among all the edges in graph: h = K(u, v) E El 1/EE.
When the edges in graph are wired randomly, independent to the node labels, the expectation for h is h, = 1/|y/ for balanced classes (Lim et al.) (021). For simplicity, we informally refer to graphs with homophily ratio h > 1/ as homophilous graphs (which have been the focus in most prior works), graphs with homophily ratio h < 1/| as heterophilous graphs, and graphs with homophily ratio h 1/|2| as weakly heterophilous graphs.
3 RELATION BETWEEN GRAPH HETEROPHILY & MODEL ROBUSTNESS
In this section, we first show theoretical results on the relation between adversarial structural attacks and the change the homophily level of the underlying graphs. Though empirical analyses from previous works have suggested this relation on homophilous graphs (Wu et al., 2019; Jin et al.) 2020a), to our knowledge, we are the first formalize it with theoretical analysis and address the case of heterophilous graphs. As an implication of the relation, we then discuss how a key design that improves predictive performance of GNNs under heterophily can also help boost their robustness.
3.1 How Do STRUCTURAL ATTACKS CHANGE HOMOPHILY IN GRAPHS?
Homophilous Graphs: Structural Attacks are Mostly Heterophilous Attacks. Our first re- sult shows that, for homophilous data, effective structural attacks on GNNs (as measured by loss Catk) always result in reduced level of homophily where either new heterophilous connections are added or existing homophilous connections are removed. It also states that direct perturba- tions on 1-hop neighbors of the target nodes are more effective than indirect perturbations (influ- encer attacks (Zügner et al. 2018)) on multi-hop neighbors. For simplicity, akin to previous works Zügner et al. 2018 Zügner & Günnemann (2199) establish our results for targeted evasion (post-training) attacks in a stylized learning setup with a linear GNN. However, our findings gen- eralize to more general setups on real-world datasets as show in experiments ($5.1). In the theorems below, we use the notion of gambit node: node u is called a gambit if a perturbation that targets node V adjusts the connectivity of node u E V.
Theorem Ler = (V,E, X) ) be a self-loop-free graph with adjacency matrix A and node features 1-p 1 for each node v. where is an all-1 vector, and p is parameter that regulates the signal to noise ratio. Assume that a fraction h of each node's 's neighbors belong the same class, while a fraction a
X. = p. onehot(y..) Ty]
1h belongs uniformly to any other class. Consider a 2-layer linear GNN p! (A,X) = A. trained on a training set Ty S. Dy, with at least one node from each class y E y, and degree d for all nodes with a distance less than 2 to any v Dy. For unit structural perturbation that involves a target node Dvv and a correctly classified gambit node with degree duy the following statements hold if 2 1ST'
2. direct perturbations on edges (or 1-hop paths) incident to the target node v lead to greater increase in Latk than indirect perturbations on multi-hop paths to target node v.
We give the proof in App. C.I Intuitively, the relative inability of existing GNNs to make full use of heterophilous data (Pei et al. 2020 Zhu et al. 2020) can be exploited by inserting heterophilous
3

---

Under review as a conference paper at ICLR 2022
connections in graphs where homophilous ones are expected. Though the theorem shows that effec- tive attacks on homophilous graphs necessarily reduce the homophily level, the converse is not true: not all perturbations which reduce the homophily level are effective attacks (Ma et al. 202I).
Heterophilous Graphs: Structural Attacks Can Be Homophilous or Heterophilous, depending on Node Degrees. When a graph displays heterophily, our analysis shows a more complicated picture on how the level of homophily in the graph is changed by effective structural attacks: in heterophilous case, the direction of change is dependent on the degrees of both the target node v and the gambit node u of the attack. Specifically, if the degree of either node is low, attacks increasing the heterophily are still effective; however, if the degrees d and d, of both nodes are high, attacks decreasing the heterophily will be effective. Similar to the homophilous case, we formalize our results below for targeted evasion attacks in a stylized learning setup.
Theorem? Under the setup of Thm. 7 for a unit perturbation that involves a target node e with degree d, and correctly classified gambit node with degree da the following statements hold:
1. (Low-degree target node) if0 < S | 2, for any da 2 and h E [0. 1}, the attack loss fatk ($2) of increases only under actions increasing heterophily in the graph;
(High-degree target node) if > | 2, conditioning on the degree d, of the gambit node:
(a) (Low-degree gambit node) if d, < d 2-1
(d+2) for any h E [0, 11. the attack loss Luck
2 of v increases only under actions increasing heterophily in the graph;
(b) (High-degree gambit node) if 2 d-1>/+2
(d+2)(D)-1) .for 0 S h (u(d-I))+2)-(4+2MMMV (d+1)/V/d.
| Luck (5)) of increases only under actions reducing heterophily in the graph.
In the statements above, the actions increasing heterophily in the graph include removing a ho- mophilous edge or adding a heterophilous edge node v, and the actions reducing heterophily in the graph include when adding a homophilous edge removing heterophilous edge to node
The above theorems cover the situation when the gambit nodes are initially classified correctly (where attacks introducing heterophily can be unambiguously defined using the ground-truth class labels of the nodes involved). However, in $5.1 we show on real-world datasets that a relaxed in- terpretation of the theorems, where heterophily is instead defined by the predicted class labels of GNNs, can explain the behavior of the attacks regardless of the initial correctness of the gambits.
3.2 BOOSTING ROBUSTNESS WITH A SIMPLE HETEROPIILOUS DESIGN
A natural follow-up question is whether GNNs with better performance under heterophily are also more robust against structural attacks. We deduce that a key design for improving GNN performance for heterophilous data- data-separate aggregators for ego- and neighbor-embeeddins--ca also boost the robustness of GNNs by enabling them to better cope with adversarially-introouue changes in heterophily.
Separate Aggregators for Ego- and Neighbor-embeddings. This design uses separate GNN ag- gregators for ego-embedding r, and neighbor-embeddings (ra : u E N())). Formally, the repre- sentation learned for node u in the k-th layer is:
(1) ENC (AGGRI(r!*") 1(( re.... ((0) AGGR2((1!")) : E N())))
where AGGR1 and AGGR2 are separate aggregators, such as averaging functions (GCN), atten- tion mechanisms (GAT), or other pooling mechanisms (Hamilton et al. 2017). The ego-aggregator
AGGRI may also introduce skip connections (Xu al.. 2018) to the ego-embeddings aggregated in previous layers as shown in Eq. ① This design has been utilized in existing GNN models (see details), dettalls,, and has been shown to significantly boost the representation power of GNNs under natural heterophily (Zhu et al. 2020).
Intuition. The key design changes, as compared to the GCN formulation in $ allow for the ego- embedding r, to be aggregated and weighted separately from the neighbor-embeddingg (I,, : e (c)). as well as for the use of skip connections to ego-embeddings of previous layers. Intuitively, ego-embeddings of feature vectors at the first layer independent of the graph structure and thus unaffected by adversarial structural perturbations. Hence, a separate aggregator and skip connections can provide better access to unperturbed information, and helps mitigate the effects of the attacks.
Theoretical Analysis. We formalize the above intuition that shows how separate aggregators for ego- and neighbor-embeddings enable GNN layers to reduce the attack loss.
4

---

Under review as a conference paper at ICLR 2022
Theorem 3 Under the setup of Thm. [ consider two alternative layers from which a two-layer linear GNN is built: (1) a layer defined as fA = A,WW; and (2) a layer formulated as f(A,X; X; = ((1 a + aT) XW, which mixes the ego- and neighbor-embedding linearly un- der predefined weight a E [0, I. Then, for h 1/13), a 1/(1 [[++ du), and unit perturbation
increasing Latk as in Thm. 7 outputs of layer f lead to strictly smaller increase in Latk than fs-
We provide the proof in App. C-3 note that for a = 1/(1 + dg), the two layers are the same: (A,,;; fA, Theorem
3 shows that an increase the weights of ego-embedding improves the robustness of the GNN J for a homophily ratio > 1/12%. Though aggregators and encoders are stylized in the theorem, the empirical analysis in $5.2 confirms that GNNs with more advanced aggregators and encoders also benefit from separate aggregators. Specifically, we find that such GNNs outperform methods without this design by up 33.33% and 48.88% on homophilous and heterophilous graphs, respectively, while performing comparably on clean datasets.
4 RELATED WORK
Adversarial Attacks and Defense Strategies for Graphs Since NETTACK Zügner et al. 2018)
and RL-S2V (Dai et al. 2018) first demonstrated the vulnerabilities of GNNs against adversarial
perturbations, variety of attack strategies under different scenarios have been proposed, including
adversarial attacks on the graph structure (Dai et al., 2018 Xu et al. 2019 Bojchevski & Günne-
mann 2019a Li al.; 2020a Chang et al. 2020), node features (Takahashi, 2019: Ma al. [2020),
or combinations of both (Zügner et al.) 2018] Zügner & Günnemann] 2019a Wu et al. (2019). On
the defense side, various techniques for improving the GNN robustness against adversarial attacks
have been proposed, including: adversarial training (Xu et al. 2019 Zügner & Günnemann 2019a Bojchevski & Günnemann (019b): RGCN (Zhu et al. a 2019). which adopts Gaussian based embed- dings and variance- attention mechanism; low-rank approximation of graph adjacency (En-) tezari et al. 2020) against Nettack (Zügner et al. 2018); Pro-GNN (Jin et al. (020b), which es- timates the unperturbed graph structure in training with the assumptions of low-rank, sparsity, and homophily of node features; GCN-Jaccard (Wu et al.
allaa221111 2019) and GNNGuard (Zhang & Zitnik 2020), which assume homophily of features (or structural embeddings) and train GNN models on a pruned graph with only strong homophilous links; and Soft Medoid (Geisler et al. 2020). an aggrega- tion function with improved robustness. Other recent works have looked into the certification of nodes that are guaranteed to be robust against certain structural and feature perturbations (Zügner) & Günnemann 2019b Bojchevski & Günneeaan 2019b Zügner & Günnemann 2020), including approaches based on model-agnostic randomized smoothing (Cohen et al. [2019] Lee et al. 2019
Bojchevski et al.) 2020). Interested readers are referred to the recent surveys (Jin et al.) 2020a Sun et al. 2020) for a comprehensive review of the literature.
GNNs & Heterophily Recent works (Pei al., 2020 Liu al. 2020 Zhu et al. 2020 Ma al.
2021 have shown that heterophilous datasets can lead to sigmificant performance loss for popular
GNN architectures (e.g., GCN (Kipf & Welling 2017), GAT (Veličković al.) (018)). This issue is
also known in classical semi-supervised learning (Peel) 2017). To address this issue, several GNN designs for handling heterophilous connections have been proposed (Abu-Eil-Hajaa et al. 2019 Pei
et al., 2220; Zhu et al.) 2020 Dong et al.) 2021 Li ct al. 2021 Zhu et al.) 2021 Bo et al.) 1021)
Yan et al. (2021) recently discussed the connection between heterophily and oversmoothing for GNNs, and proposed designs to simultancously address both issues. However, the formal connection
between heterophily and robustness of GNNs has received little attention. Here we focus on simple
yet powerful design that significantly improves performance under heterophily (Zhu et al.) 2020).
and can be readily incorporated into GNNs.
5 EMPIRICAL EVALUATION
Our analysis seeks to answer the following questions: (Q1) Does our theoretical analysis on the rela- tions between adversarial attacks and changes in heterophily level generalize to real-world datasets? (Q2) Do heterophily addjusted GNNs, i..., models with separate aggregators for ego- and neighbor- embeddings, show improved robustness against state-of -fate-of-the-art attacks? (Q3) Does the identified design improve the certifiable robustness of GNNs?
5

---

Under review as a conference paper at ICLR 2022
First, we describe the experimental setup and datasets that we use to answer the above questions.
generated by NET- TACK Zügner et al. 2018) and Metattack (Zügner& & Günnemann 2019a). respectively. For each attack method, we consider poison (pre-training) and evasion (post-training attacks, yielding 4 at- tack scenarios in total. We focus on robustness against structural perturbations and keep the node features unchanged. We randomly generate 3 sets of perturbations per attack method and dataset, and consistently evaluate each GNN model on them. We provide more details in App. D.2
Attack Setup. We consider both targeted and untargeted attacks
GNN Models. To show the effectiveness of our identified design, we evaluate four groups of models against adversarial attacks: (1) Models with this heterophilous design only: GraphSAGE (Hamilton
et al. 2017). H2GCN (Zhu et al. 2020). CPGNN (Zhu et al. 2021). GPR-GNN (Chien et al. 1021 and FAGCN (Bo al., 2021): we discuss how these models instantiate this design in App. DD.1
(2) State-of-the-art "vaccinated" architectures designed with robustness in mind: ProGNN Jin et al., 2020b), GNNGuard (Zhang & Zitnik, 2020) and GCN-SVD (Entezari et al., 2020j: (3) Models with both the heterophilous design and explicit robustness-enhancinn mechanisms based on low- rank approximation: H₂GCN-SVD and GraphS (4) Models without any vaccination. including some of the most popular methods: GCN (Kipf & Welling 2017), GAT (Veličković et al.) 2018), and the graph-agnostic multilayer perceptron (MLP) which relies only on node features. We discuss the implementations and parameters used for the models in App.[D
Datasets & Evaluation Setup. We con- sider two standard datasets with strong ho- mophily, Cora (McCallum] (2000) and Cite-
Table 1: Dataset statistics.
Homophilous graphs
Heterophilous graphs
seer (Sen et al. 2008), complemented with one weakly and one strongly heterophilous graph, introduced by Lim al.] (202I): (2012) and Snap Patents (eskovee et al.) |005] Leskovec &
Cora
Citeseer
FB100
Snap
#Nodes [
2,485
2,110
2.032
4,562
#Edges [8]
5,069
3,668
78,733
12,103
100 (Traud et al.
#Classes [>]
7
6
2
5
#Features
1,433
3,703
1.193
Homophily h
0,804
0.736
0.531
0.134
Krevi 2014). We report summary statistics
in Table [ and provide more details in App. D.5] For computational tractability, we subsample the Snap Patents data via snowball sampling (Goodman 1961), where we keep 20% of the neighbors for each traversed node (see App. D.5 for details). We follow the evaluation procedure of Zügner et al. (2018) and Jin et al. (2020b). where split the nodes of each dataset into training (10%), validation (10%) and test (80%) data, and determine the model parameters using the training and validation splits. We report the average performance and standard deviation on the 3 sets of gener- ated perturbations. For targeted attacks with NETTACK, we report the classification accuracy on the target nodes; for untargeted attacks with Metattack, we report over the whole test data.
Robustness Certificates. We adopt randomized smoothing for GNNs (Bojchevski et al. 2020) to evaluate the certifiable robustness, with parameter choices detailed in App. D.2 We only consider structural perturbations in the randomization scheme. Following Geisler et al. (2020), we measure the certifiable robustness of GNN models with the accumulated certifications (AC) and the average maximum certifiable radii for edge additions (Fa) and deletions (Fa) over all correctly predicted nodes. More specifically, AC is defined as - R(0, 0) + Era.r.20 (R(rarra) where R(ra; ra) the certifiably correct ratio, i.e., the ratio of the nodes in the test splits that are both predicted correctly by the smoothed classifier and certifiably robust at radius (ra. In addition, we report the accuracy of each model with randomized smoothing enabled on the test splits of the clean datasets, which is equal to R(0 0). We report the average and standard deviation of each statistic over the 3 different training, validation and test splits.
5.1 (Q1) STRUCTURAL ATTACKS ARE MOSTLY HETEROPHILOUS: EMPIRICAL VALIDATION
To show that our theoretical analysis in $3. generalizes to more complex settings beyond the as- sumptions we made in the theorems, we look into effective targeted attacks made by NETTACK on real-world homophilous and heterophilous datasets, and present statistics of the attacks in Table 2 with a focus on the ratios of heterophilous attacks. We use a budget of perturbation per target node in this experiment, and the statistics are reported among all effective perturbations targeting nodes that are correctly classified on clean datasets by the surrogate GNN used by NETTACK (i.c., GCN) as described in $ To help validate the dependency between the degrees of the target/gambit nodes

---

Under review as a conference paper at ICLR 2022
and the changes of heterophily predicted by Thm. 2 we also show the scatter plots of target and gambit node degrees in Fig. in App. E.5
Homophilous Networks. For the strongly homophilous Cora and Citeseer graphs, all changes in the graph structure that are introduced by effectives attacks fol- low the conclusion of Thm. [ they re- duce homophily (increase heterophily) by adding heterophilous edges or removing homophilous edges. These results show that despite the simplified analysis, the takeaway of Thm. caan be generalized to real-world datasets. In addition, the at-
Table 2: Effective targeted attacks by NETTACK: ra- tios of edge additions, deletions and heterophilous at- tacks (i.e., attacks increasing heterophily). We consider two heterophily definitions, one based on ground class labels (Label), and the other on predicted class la- bels by GCN on clean datasets (Pred.). All attacks are direct perturbations on edges incident to the targets.
Sample Sizes
Attack Type
Hete, Atlacks
Dataset
Add.
Del.
Label
Pred.
NETTACK
Cora
150
99.33%
0.67%
100.00%
100.00%
Citeseer
100.00%
0.00%
100.00%
100.00%
tacks mostly introduce, rather than prune, edges, suggesting that attacks adding out-
100
112'
100.00%
0.00%
30.00%
100.00%
Snup
51
100.00%
0.00%G
64.71%
100.00%
lier edges to the graph are more powerful than attacks removing informative existing edges. These observations in our experiments are con-
sistent with the observations from previous works (Jin et al. 2020a Geisler al. 2020).
Heterophilous Networks. For heterophilous graphs FB100 (h R 1/13*) and Snap (h < 1/D", Fig. in in App. [E5 shows that almost all attacks leverage gambit nodes with low degrees (1 or 2); no node with degree higher than 5 is leveraged. All attacks leveraging correctly classified gambit nodes are connecting node u V with different ground-truth class label yv. * ye to the target nodes E V: attacks leveraging incorrectly classified gambit nodes are always connecting node u with a different predicted class label 9. * 9. = yv to the target node v, even though some gambit nodes have the same ground-truth class label Vn. = Yo * Th. as the target nodes. These results validate the conclusion of Thm. oon correctly classified gambit nodes, and demonstrate its generalizability under the heterophily definition based on predicted class labels. Note that the predicted class labels Iu for each node u E V are based on GCN, which is the surrogate GNN used by NETTACK.
5.2
(Q2) BENCIMARK STUDY OF GNN MODELS: HETEROPHILOUS DESIGN LEADS TO IMPROVED EMPIRICAL ROBUSTNESS
To answer (Q2) on whether setroophily-adjussen GNN models show improved performance against state-of-the-art attacks, we conduct comprehensive benchmark study. We consider all four cat- egories of GNN models mentioned in [5] and evaluate their robustness against both targeted and untargeted attacks. We report the hyperparameters for each method in App. D.4 Table 3 shows the performance of each method under poison (pre-training) attacks, and Fig. visualizes the corre- sponding performance changes relative to the clean datasets. For conciseness, we report further re- sults under evasion (post-training) attacks and on clean (unperturbed) data in the Appendix (Table 7 for NETTACK; Table & for Metattack). Also, in App. E.4 we discuss how our simple heterophilous design leads only minor computational overhead compared to existing vaccination mechanisms.
Targeted attacks by NETTACK. 1 Poison attacks. Under targeted poison attacks, Table B (left) shows that GraphSAGE-SVD and GCN-SVD which combine our identified design with a low- rank vaccination approach adopted in GCN-SVD (Entezari et al. 2020) (details in App. D.3) out-
perform state-of-the-ar methods across all datasets by up to 13.34% in homophilous settings and 18.33% in heterophilous settings.
Methods merely employing the identified design also show significantly improved robustness, though there are differences in the amount of robustness improvement due to architectural differ- ences. Specifically, these methods outperform the best unvaccinated method (GAT) on all datasets by up to 32.92% in average, despite having comparable performance on clean datasets. On Citeseer and FB 100, methods with the heterophilous design also show comparable or even better robustness than ofate-of-the-art vaccinated GNNs like ProGNN and GCN-SVD.
2 Evasion attacks. Under evasion attacks (Table 7). we observe similar trends as in poison attacks: GraphSAGE-SVD and HyGCN- SVD are up 20.55% more accurate than the GCN-SVD baseline, and methods featuring the identified design alone achieve up to 24.45% gain in average performance against the best unvaccinated baseline. We note that GNNGuard and ProGNN are not capable of ad-
7

---

Under review as a conference paper at ICLR 2022
Table 3: Benchmark study: mean accuracy against poison attacks (aceuracy on clean datasets in paranthesis). Accuracy is reported on target nodes for NETTACK, and on full test splits for Metattack. Best GNN model is highlighted in blue per dataset, and in gray per model group. MLP is immune
to structural attacks and not considered as GNN model. Detailed results. including stdev and
accuracy against evasion attacks, are listed in Table 7 and S
and the setup in S
Heterts
Vaccin
Homophilous graphs
Heterophilonns graphs
Homoohhllous graphs
Heterophiloos graphs
Cora
Citeseer fu40.736
FB100 k=0.551
Snap
Cora
Citeserr A=00736
FB100
Snap 1=0. 134
A-00 804
iu00
hs00.804
h=0.531
H,GUNSVD GEEDASAGE-SYD
70 muse
65,00
59
28,
67.8 07.87
56.72
25
mm
yarm
68. 18.86.mm
10
55.76
26.
H,GCN
58 89
27.22
27. 78
12.78
57.75
54. 34
54,84
25. 34 cnui
GraphSAGE
36.67
16.67
54. 68.68
54.72
GPR-GNN
CPGNN
SESTAAKK
21 1. wa2t
24.44 wtTu
man
49:44
2.78 oxch
4.44 c177
1..67
48, s4
35.25 mo
61.58 am
59.94 xx:40
21 1..06 (oo
FAGON
26.11 nare
25.56 ouse
6.11 uara
8.33 (MN
60.11 .9
53.18 1z
55.97 94.0
24.04 caus)
GNNGmard
58. ma2
0.56 u812
74,20
68.
60.88 80.
23. 23.78 04.0
ProGNN
nMM
32.78 wizz
17.78 2220
45. as
53.40 mm.
24
GCN-SVD
53.3 (dde
28.89 dam
41:67 0ads
25. 25.00 actt
47.82 (0.0
$1 $1.20 us
55,00 40
25 (aua)
"ATT
13 89
6.30
0.56
3,89
41:20
2% 40
50.37
25.
Hare
37,46 04.23
51.82
'MP
64 44
70.36
57.78
30,00
64.35
67 .7
56.56
26 25
dressing evasion attacks. In summary, these observations show that the heterophily-inspired design orthogonal to existing vaccination mechanisms for improving the robustness of GNNs.
Untargeted attacks by Metattack. ! Poison attacks. We also test the robustness of each method against un-
P2Up44eV GmpnSAGE- SVD
HASAO
GHUNN
MAGOO
VL-
GrepnSAGE
2. UCNBVD
Citeseer (h- 0.736)
FB100
targeted attacks. Table 3 (right) shows the performance under poison attacks. Though our thcoretical analysis in $3 focuses the effect of the heterophilous design under targeted attacks, we ob-
Pulsos Pusos Assuney
60-
Polson Accuray
60
80
20
20
serve similar improvements in robustness against untargeted attacks in the poison setup. GNNs with the identified design show mostly improved robustness com- pared unvaceinated models, while having similar performance on the clean datasets. Specifically, CPGNN shows exceptional robustness, outperforming the best unvaccinated model by up to 32.85%. Moreover, models combining the identified design with low-rank approximation show more than 10% improvement accuracy compared to GCN-SVD, which uses only low-rank approximation, and ProGNN. We note that GNNGuard, which uses similarity-based defense strategy, also shows more competitive robustness under untargeted attacks. This is in line with existing works showing that low-rank based approach does not adapt well to untargeted attacks (Jin et al.) (0205)). Nevertheless, methods combining a heterophilous design and low-rank approximations still outperform GNNGuard on two datasets.
0
Accuroyy
CicanAccuracy
(Best viewed in color.) Classification aceu- racy on clean data and against poison attacks for target nodes attacked by NETTACK. Error bars show standard deviation across different sets of experiments. Detailed results are listed in Table 7 As expected, MLP is not influenced by the adversarial structural attacks.
Figure 1:
2 Evasion attacks. We present the performance under evasion attacks and on clean datasets in Ta- ble X in the Appendix. Unlike the poison attacks, the evasion setup only leads a slight decrease in average accuracy of less than 2% for most models. Moreover, there appears to be no clearly increased robustness for vaceinated models (with the identified design or other vaccination mach- anisms) compared to unvaccinated models. This can be attributed to the reduced effectiveness of evasion vs. poison attacks (as in NETTACK), and the increased challenges of untargeted attacks.
5.3 (Q3) HETEROPHIIL--DDIUSTTI GNNS ARE CERTIFIABLY MORE ROBUST
It is worth noting that robustness against specific attacks such NETTACK and Metattack does not guarantee robustness towards other possible attacks. To overcome this limitation, robustness certificates provide guarantees (in some cases probabilistically) that attacks within certain radius cannot change a model's 's predictions. Complementary to our evaluation on empirical robustness, we further demonstrate that helerophily-adjusted GNNs featuring our identified design are certifiably
8

---

Under review as a conference paper at ICLR 2022
Table 4: Accumulated certifications (AC), average certifiable radii (Fe and f.)) and accuracy of GNNs with randomized smoothing enabled (i.e., f()(s))) on the test splits of the clean datasets, with a ramdomization scheme & allowing both addition and deletion (i.e., p+ = 0.001, p- = 0.4). For each statistic, we report the mean and stdev across 3 runs. Best results highlighted in blue per dataset, and in gray per model group. For results with other randomization schemes, see Table 9
Addition & Delction
Addition Deletion
AC
Acc. 96
AC
Fd
Acc. %
H,GCN
3.91
0.46
3,88
79. 14.14
2.98:caa
0.34
3.29
71.43+a/
GraphSAGE
2.12
0.12
2.41
79.43
2.25
0.20
2.59
73. 23.34
CPGNN
L887a92
0.14
2.24
75.37
Citsser
2.03+cur>
0.11
2.52
73.48
GPR-GNN
Cora
4.42
0.63
4.35a
74.90
4.63
4.92
66.33
FAGCN
4.30
0,57
4.25
76.49
4.07=taa>
0.58
4,23
11782
GAT
1:60+a20
s.07
1.83
79.88
1.30
0.08
1.62
72.87
GCN
a.09
1.99
79.39
1.77
0.14
2.09:amom
73.48
HCG
8.12
1.76
8.14
17.38
1.44
0.59
3.79
26.97
GraphSAGE
6.
1,50
7.32go0
56.7221 16
0.70
0.19
2.16
26.84
CPGNN
a:80
1.4
7.05
59,001571
1.45
0.61
3.89
26.71 jas
GPR-GNN
5.8
1.1
5.95gm
0.52g
0.1
1.70
26.31 gios
FAGCN
a.45
1,53
7.40
59,76.14
1.4
0.56
3,81 102
27.07
GATT
4,30
0,77
4. 4.72.m0
61.56190
0.28
00044
0,95
27. 12
GCN
3.
0.64gmo
4.24
65.54gna
0.33
g.03
17
more robust than methods without it, thus answering (Q3). For GNN models, we include HGGCN, GraphSAGE, CPGNN, GNN, FAGCN, GAT and GCN in this analysis. We exclude other models that either learn to rewrite the graph structure through the training process or require a recalculation of the low-rank approximation for every randomized perturbation as sampling on these models is infeasible. We use the same hyperparameters as in the benchmark study in $5.2
Table shows multiple metrics of certifiable robustness of each GNN model under a randomiza- tion scheme allowing for both addition and deletion of edges; we additionally report results under randomization schemes allowing only addition or deletion in Table 9 For the scheme allowing both addition and deletion, we observe that all heterophily-adjiue adjjustd methods have better certifiable robustness compared to methods without the design. Specifically, on homophilous datasets (Cora and Citeseer), methods with the identified design achieve an up 1.6 times relative improvement in accumulated certification. On heterophilous datasets (FB 100 and Snap), they outperform the baselines by a factor of 4.4. In the more challenging case with the addition only scheme, methods with the design also show up to 1.2 times relative increase in AC on the homophilous datasets and 5.0 times relative increase in AC on the heterophilous datasets compared to the baselines. For the deletion only scheme, unvaccinated models like GCN already have decent certifiable robustness in this scenario. This is commensurate with our discussions in |5.1 that deletions create less severe perturbations. Overall, our results show that models featuring our identified design achieve signif- icantly improved certifiable robustness compared to models lacking this design. However, like in empirical robustness evaluation, architectural differences lead to some variability of robustness; the results also show tradcoffs between accuracy and robustness. We also observe that the robust- ness rankings for methods under certifiable and empirical robustness are different, in the previous results from Geisler et al. 2020); we discuss possible reasons in App. E.3
6 CONCLUSION
We formalized the relation between heterophily and adversarial structural attacks, and showed the- oretically and empirically that effective attacks gravitate towards increasing heterophily in both homophilous and heterophilous graphs by leveraging low-degree (gambit) nodes. Using these in- sights, we showed that key design addressing heterophily, namely separate aggregators for ego- and bigghbor-embedding can lead to competitive improvement on empirical and certifiable robustness, with only small influence on clean performance. Finally, we compared the design with state-of-the. art vaccination mechanisms under different attack scenarios for various datasets, and illustrated that they are complementary and that their combination can lead to more robust GNN models. We note that while we focus on the structural attacks, GNNs are also vulnerable to other types of attacks such as feature perturbations. In addition, the graph-agnostic MLP, which is immune to structural attacks, on some datasets outperforms all GNNs against attacks; this calls for further works in understanding of the nature of the attacks and also for effective defense strategies upon our discoveries.
9

---

Under review as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
For reproducibilityy we describe the experimental setups in $ with additional details in App. D.2 including the implementation and the hyperparameter settings used for each method, and the hard- ware specifications. We provide anonymized code and datasets in the supplementary material with instructions for replicating the experiments, and will make them publicly available upon acceptance.
REFERENCES
Sami Abu-El Nou-El-Haija, Bryan Perozzi, Amol Kapoor. Hrayr Harutyunyan. Nazanin Alipourfard, Kristina Lerman, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolu- tion architectures via sparsified neighborhood mixing. In International Conference on Machine Learning (ICML), 2019.
Deyu Bo, Xiao Wang. Chuan Shi, and Huawei Shen. Beyond low- uwwfrreuency information in graph convolutional networks. arXiv preprint urXiv:2101.00790 2021.
Alcksandar Bojchevski and Stephan Günnemann. Adversarial attacks on node embeddings via graph poisoning. Proceedings of the 36th International Conference on Machine Learning, ICML., Proceedings of Machine Learning Research. PMLR, 2019a.
Aleksandar Bojchevski and Stephan Günnemann. Certifiable robustness to graph perturbations. In Neural Information Processing Systems, NeurlPS, 2019b.
Aleksandar Bojchevski, Johannes Klicpera, and Stephan Günnemann. Efficient robustness certifi- cates for discrete data: Sparsity-aware randomized smoothing for graphs, images and more. In International Conference on Machine Learning, pp. 1003-1013. PMLR, 2020.
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geomet- ric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18 42, 2017.
Heng Chang, Yu Rong, Tingyang Xu, Wenbing Huang. Honglei Zhang, Peng Cui, Wenwu Zhu, and Junzhou Huang. A restricted black-box adversarial framework towards attacking graph embed- ding models. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp.
3389-333 0396, 2020.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovie. Adaptive universal generalized pagerank graph neural network. In International Conference Learning Representations, 2021. URL
net/ weteet/ooommmmddn1117661
Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In International Conference on Machine Learning, pp. 1310-131011 13200 PMLR, 2019.
Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. Adversarial attack on graph structured data. International conference on machine learning, pp. 1115-1124. PMLR, 2018.
Yushun Dong, Kaize Ding, Brian Jalaian, Shuiwang Ji, and Jundong Li. Graph neural networks with adaptive frequency response filter. arXiv preprint arXiv:2104.1 12840, 2021.
Negin Entezari, Saba A Al-Sayouri, Amirali Darvishzadeh, and Evangelos E Papalexakis. All you need is low (rank) defending against adversarial attacks graphs. In Proceedings of the 13th International Conference on Web Search and Data Mining, pp. 169-177, 2020.
Simon Geisler, Daniel Zügner, and Stephan Günnemann. Reliable graph neural networks via robust aggregation. Advances in Newral Information Processing Systems, 33, 2020.
Leo A. Goodman. Snowball Sampling. The Annals of Mathematical Statistics, 32(1):148 170. 1961. doi: 10.221/aamm/1177755144 URL https://aol.org/ 1214/ aoms/
1177705448
10

---

Under review as a conference paper at ICLR 2022
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In Advances in neural information processing systems (NeurIPS), pp. 1024-1034, 2017.
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.008 000000 2020a.
Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 66-74, 2020b.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations (ICLR), 2017.
Guang-He Lee, Yang Yuan, Shiyu Chang, and Tommi Jaakkola. Tight certificates of adversarial ro- bustness for randomly smoothed classifiers. Advances in Neural Information Processing Systems, 32:4910-4921, 2019.
Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. /
http:
edu/ data June 2014.
Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graphs over time: Densification laws, shrink-
ing diameters and possible explanations. 08 2005. doi: 10. 1111100818701001110
Jia Li, Honglei Zhang, Zhichao Han, Yu Rong, Hong Cheng, and Junzhou Huang. Adversarial attack on community detection by hiding individuals. In Proceedings of The Web Conference 2020, pp. 917-927, 2020a.
Sean Li, Dongwoo Kim, and Qing Wang. Beyond low-pass filters: Adaptive feature propagation on graphs. arXiv preprint 1 2021.
Yaxin Li, Wei Jin, Han Xu, and Jiliang Tang. Deeprobust: A pytorch library for adversarial attacks and defenses, 2020b.
Derek Lim, Xiuyu Li, Felix Hohne, and Ser-Nam Lim. New benchmarks for learning non- homophilous graphs arXiv preprint arXiv:2104.01404,222 2021.
Meng Liu, Zhengyang Wang, and Shuiwang Ji. Non-local graph neural networks. arXiv preprint arXiv:2005.14611 2020.
Jiaqi Ma, Shuangrui Ding, and Qiaozhu Mei. Towards more practical adversarial attacks on graph neural networks. Advances in neural information processing systems, 2020.
Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily necessity for graph neural networks? arXiv preprint urXiv:2106.066 36,44444, 2021.
A.K. McCallum. Automating the construction of internet portals with machine learning. Information Retrieval, 3:127-163, 01 2000.
Leto Peel. Graph-based semi-supereised learning for relational networks. In Proceedings of the 2017 SIAM International Conference on Data Mining, pp. 435 443. SIAM, 2017.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Yang. Geom-gen: Geometric graph convolutional networks. In International Conference on Learning Representations (ICLR), 2020. URRLAttpss//opeerevvieee n ott.rr/reeee.....ooooooooooeesee
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):93-95 2008
Lichao Sun, Yingtong Dou, Carl Yang, Ji Wang, Philip S Yu, Lifang He, and Bo Li. Adversarial attack and defense on graph data: A survey. arXiv preprint arXiv: 18/2. 10528, 2020.
Tsubasa Takahashi. Indirect adversarial attacks via poisoning neighbors for graph convolutional networks. In 2019 JEEE International Conference on Big Data (Big Data), pp. 1395-1400. IEEE, 2019.
11

---

Under review as a conference paper at ICLR 2022
Amanda L. Traud, Peter J. Mucha, and Mason A. Porter. Social structure of facebook net- works. Physica A: Statistical Mechanics and its Applications, 391(16)4415-4118 2012.
ISSN 0378-4371. doi: cttp:///csaaacceaa....aaa//////1
URL https: //mp:://www
sci rcieenediiectt com wttptttccc/cccccccecceecce
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua
Bengio. Graph Attention Networks. International Conference on Learning Representations
(ICLR), 2018. URL BtLLhttps://// /pwpr//eee/peeeeeeeeeeeee net www.:eeooooonii--ao.aaaeaa.a
Huijun Wu, Chen Wang. Yuriy Tyshetskiy, Andrew Docherty, Kai Lu, and Liming Zhu. Adver- sarial examples for graph data: Deep insights into attack and defense. In Proceedings of the Twenty-Eighth International Joint Conference Artificial Intelligence, IJCAI-19. pp. 4816- 4823. International Joint Conferences on Artificial Intelligence Organization, 2019. doi: 0.224663/jjaii.2119//6
httpsstt:://doi http://ooooorgg///// 2111:11...2231111 201 9/669
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:1906. 04214, 2019.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In Proceedings of the 35th International Conference on Machine Learning, ICML, volume 80, pp. 5449-5458 PMLR. 2018.
Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. arXiv preprint arXiv:2102.06446. 2021.
Xiang Zhang and Marinka Zitmik. Gunguard: Defending graph neural networks against adversarial attacks. Advances in Neural Information Processing Systems, 33, 2020.
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.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33, 2020.
Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra. Graph neural networks with heterophily. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pp. 11168-11176, 2021.
Daniel Zügner and Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning. In International Conference Learning Representations, 2019a.
Daniel Zügner and Stephan Günnemann. Certifiable robustness and robust training for graph con- volutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 246 256,225,,110 2019b.
Daniel Zügner and Stephan Günnemann. Certifiable robustness of graph convolutional networks under structure perturbations. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1656-1665, 2020.
Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks on neural networks for graph data. In Proceedings the 24th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 2847-2856, 2018.
12

---

Under review as a conference paper at ICLR 2022
A SOCIETAL IMPACTS
large number of popular GNN models are inherently based on homophily. Our work shows that such models may be less robust adversarial perturbations, and thus when employed for decision-making these models may lead to undesirable, erroneous or biased results. For exam- ple, an inherently homophilous GNN model may lead the so-called "filter bubble" phenomenon in recommendation system in which existing beliefs or preferences are reinforced. Similarly, as homophily- based GNNs typically average over node neighborhoods, this may result in less visibility of minority groups in the network, thus reinforcing disparities. Heterophilous network design may improve some of these aspects, and also benefit from some additional robustness as shown this work.
However, should be noted that heterophilous GNNs on their own cannot fully solve the aforemen- tioned issues. In particular, while heterophilous design improve robustness, it is not (in general) constructed to ensure other important aspects such as fairness. Better understanding of GNNs and tailored auditing tools are necessary in order to deploy these learning algorithms in the context of decision-making affecting humans.
B NOMENCLATURE
We summarize the main symbols used in this work and their definitions below:
Table 5: Major symbols and definitions.
Symbols
Definitions
g (V,E,))
graph 9 with nodeset V. edgeset E, and [V] node feature matrix X [V] x F node feature matrix of G. X ||V
X
A
[ x [V] adjacency matrix of G, A E {0, 1)1V X/M
A.
adjacency matrix with self-loops added, A. A+I
D
diagonal matrix of degrees, with D Σ, A.j
row-stochastic matrix for A. D-1A row-stochastic matrix for A,, A. D low-rank approximation the adjacency matrix learnable weight matrix for GNN models
A,
W
X
F-dimensional feature vector for node v direct (1-hop) neighbors of node in without self-loops (i.e., excluding of class labels
N(e)
ye
class lahel for node 0 E V
y
[V dimensiional vector class labels (for nodes)
Tv [11), v1). (12 v2).
training data for semi- eui-suupeeesed node classification
G 6V,E",
graph 9 with modified edgeset E
certain GNN model that processes the number of layers of GNN f
K
(R)
node representations learned by GNN at round layer function that aggregates node feature representations within a neighborhood
AGGR
ENC
learnable (nonlincar) mapping that generates latent representation
label prediction by GNN f for node a V. z, e [0. 1]00
z.
Latk
attack loss that quantifies the mismatch between and the true labels y attack loss defined with negative classification margin
DCM
atk
LCM A = (Zo.y. max y.. Reyy)
d
the degree of the nodes which have distance less than 2 to any Dy degree of gambit node leveraged by an attack
d
parameter regulating the signal strength of one-hot class label vs. uni noise
a predefined weight scalar Theorem 3 a [0 homophily ratio defined on node class labels, h [[(u, e) E Elyu. B- H>//
13

---

Under review as a conference paper at ICLR 2022
C PROOFS AND DISCUSSIONS OF THEOREMS
C.I DETAILED ANALYSIS OF THEOREM
Proof (for Thm. 1 We give the proof in three parts: first, we analyze the training process of the GNN (! (A. = X on clean data and analytically derive the optimal weight matrix W. in stylized learning setup; then, construct targeted evasion attack and calculate the attack loss for unit structural attack; last, we summarize and validate the statements in the theorem.
Stylized learning clean data. Given the 2-layer linearized GNN ! (A, A and the training set Tv C Dv. the goal of the training process to optimize the weight matrix W to min- imize the cross-entropy loss function [( correspond to the predicted class label distributions for each node u in the training set Tv, and [T] is the one-hot encoding of class labels provided in the training set.
Tu.:> [Y]Tu.), where predictions [z] Tu.: A Tv W
Without loss of generality, we reorder Tv accordingly such that the one-hot encoding of labels for nodes in the training set TTp is in increasing order of the class label yo:
0
0 0
0
1
0
0
Tv.
|7>|X|
Now we look at the term [A in [z] [A2X|Tu. To.. W, which are the feature vectors aggre- gated by the two GNN layers for nodes v in the training set Tv. As stated in the theorem, we assume Ty Dy. where node E Dy have degree d; proportion h of their neighbors belong the same class, while proportion
1-h 1 of them belong to any other class uniformly, and for each node E V
the node features are given as x,, p onehot(yv)) + bf for each node V. Then, after the first layer, we have:
(hd + 1)p
dp dp
h dp
1-h D
dp
D
(hd + +1p
1 dp
DJ dp
- dp
PT-1 dp
I-h
(hd + 1)p
DT-I dp
1-h
yyT1 dp
T.. d d+1
DP-1
1-h
(hd + 1)p
D1-1
1-h dp
M h dp
1 p
|
1--1 dp
1-h
D1-1 dp
1-h
D--1 dp
(hd 1)p
D dp
1-h
D
1-h dp
D dp
1-h
(hd 1)p
|Tv|x|D1
(3)
14

---

Under review as a conference paper at ICLR 2022
and after the second layer
S
T
T
Ti
S1
T1
T
T
T
S
T
Ti
[A Tv. =
T
S1
T
T
+
(4)
(d +
D
T1
T
T
S
T
T1
T
S1
ITv x|
where Si ((h)))) - 1)d + |D - -1)² and Ti ((N)) (141)-1)44422 1111-11-11 112p.
For (YTTE and [A] To. which we derived in Eq. 2 and 4 we can find the optimal weight
matrix W. such that (T.. W. 0.
(TTs making cross-entropy loss [((A)Tu [Y] =
To find W., we can proceed as follows. First, sample one node from each class to form a smaller
set Ts Tv. Therefore, we have;
0 0 0
0
|YTT.
1. :
and
Si T
Ti
7i
Ti
S
Ti
Ti
[ (d (d+1)11((111))
+
Pl
T T
T
Di
Note that [ Tex specific circulant matrix, and therefore its inverse exists. Using the Cherman-Morrisse formula, we can find its inverse as:
(d + ()+
V
1
( Tg.))
(5)
p(d(h))) - D/ 1
D
[D]
Now, let W. (IA Ts.:) then have [z) [AEX]TE.. W. = I | It is also easy to verify that [z) Tu. [A = -YT Since W., satisfies [(z]TT.. [YTT.))
O, we know W. = [(AXX]Ts.) is the optimal weight matrix that we can learn under Tv-
Attack loss under evasion attacks. Now consider an arbitrary target node v E Dy with class label Yo E Y. and a unit structural perturbation leveraging gambit node u with degree d, that af- fects the predictions zu of node u made by GNN f! Without loss of generality, we assume node has yo 1. As f!2) contains 2 GNN layers with each layer aggregating feature vectors within neighborhood (v) of each node v, the perturbation must take place in the direct (1-hop) neighbor- hood N (v) or 2-hop neighborhood N2(v) affect the predictions Zu- For the unit perturbation, the
15

---

Under review as a conference paper at ICLR 2022
attacker can add remove a homophilous edge or path between nodes and which we denote as 81 (61 = 1 for addition and 61 = -1 for removal); alternatively, the attacker can add or remove heterophilous edge path betveen nodes and which denote as 82 =1 analogously. We denote the perturbed graph adjacency matrix as A go and z, = [A, W.
① Unit perturbation in direct neighborhood ((v). We first consider unit perturbation in the direct (1-hop) neighborhood (u) node u. For simplicity of derivation, we assume that the perturbation does not change the row-stochastic normalization of As, and only affects the aggregated feature vectors of the target node v.
In the case ő1 +1 and 82
have
| - [ b. da +
81
+D)
81 (txF)
81
D
TDT
and
AA_ [ v3: (do + + 1)1y/ So
Ta
T
where S2 51 (da(p(d(h))) - -1)
+d-
(d++))
2) and
To = 61 (- (daa(pp(d()))
(d)+)))) 1) 1)))
-
By Multiplying [A?X] n. by W., we can get the predictions ti after perturbations; we omit the
analytical expression of dy here due to its complexity.
On the perturbed graph, the CM-type attack loss is calculated as
Cox = - -max (.yy)
Since clean data, Luc (2x) 1, the change in attack loss before and after attack is
CC CCM (z),) CCN((, (z,) L (2,) +1
(6)
(d ( 1) (d())))))))))))) - hDy - (d 2)(
1))
(da 1)²
V 1)2
Solving following system of inequalities for 6,,
A CCM > 0 atk h E [o, 1]
(8)
|D| 2 2
d, day | E Z+
we get the valid range of 61 as
81 < 0, when 0 < d < | -
81 0, when d >> [}] - 2 and de
(1+
d- 2-12
81 < 0, when d >> []] 2 and d, >
d (d+2)
and 1 > h >
(d+1))yld
81 > O, when d > |}] - 2 and de 2 d-12+2
(d+ and 0 < h <
d'
((+)))1-11
(d+1))''d
(9)
Note that the above solution is not applicable when d-1y++1 in which case di d|
1 0 and the solution of optimal weight matrix W, = (1A2X) is undefined.
In the case of o, O and 82 = +l, we have
A u. [A. u0 dg 1
82
1-p DV
52 (
(1 +p)
1-p
82 1- + +p)
and
[A p,: (A,X) n. = (da + ()
1
Si -ーー
T4 ... Ta ].
where S. = 5-
- -d) ()(p 1)))
[
and T4 8z (pd((()))) -1 +D+ + D/
+ -
By
16

---

Under review as a conference paper at ICLR 2022
with W., can get the predictions z., after the perturbations. Following similar derivation to that in the previous case, we can compute the change in the CM-type attack loss before and after attack
multiplying [|.
A (d+ 1>(D') 1)
+) DY 2) (d 2)(11 1))
(10)
(da + 1) (d(h))) -
1)²
Solving the same system of inequalities as Eq. (8) for 82, we obtain the valid range of ó2 as
82 0, when 0 < d S | -2
82 > 0, when d > [ - 2 and d, < (d+2)(1-11)
d-1y++2
82 > O, when d > [>]| 2 and da 2 1211+++2
(142) and 1 2 h >
da (((--))+2)-(44220000
(d+ 111
d. +2) (d+2)
82 < O, when d > | 2 and do 2 2-1-++2
and 0 S h <
(d+ d+Tii da
(11)
Note that the above solution is not applicable when h d- d-D+++ in which case d() 1
d/T
1 and the solution of optimal weight matrix W. (IA,X] ) undefined. We also note
that we always have da (dd=[)))2) ((4+))))(d2)())-111)
I -1 -d+2) < 0 when | 2 2.
(d+1),
[D]
(d- id)1)
2 Unit perturbation in 2-hop neighborhood N2(v). We now consider a unit perturbation in the h-hop neighborhood (v) of node v. In this case will have [A,X] [AgX]u.: v..-
In the case of +1 and 82 = O, we huve
AA
[o, (da + 1)3121 SB
T3
Ts
D--1
where
Ss = (da - 1) + 1) + (191 - 1)p + 1)
and
Ts = (aal-1111 + D1 - D'((-)) +
By multiplying x o. with W.. we can get the predictions z', after perturbations. Following a similar derivation as before, we can get the change in the CM-rype attack loss before and after attack as
CCMM- (d+ (de + 1)
(12)
-)
DD
Solving the same system of inequalities as Eq. (8) for 8j, we get the valid range of 81 as
61 < 0, when de < | -
61 < 0, when da 2 | 1 and da da-1V'+1 <
-Dlde do-1i+11
(13)
81 > O, when d, > |y] 1 and 0 S h
Di
Note that the above solution is not applicable when h d-1y++1 in which case d(h))l- +D11
1 = 0 and the solution of optimal weight matrix W. = (IA3X) is undefined.
For the case 51 = 0 and 82 = =1, we have
A x n.: x v.: (da + 1)2
S6
To
To
-
where
Ss 82 ( 1h1 + | 1- + 1D'1 (p)(-p) + 1> + 1)
and
To = 82 1)) -)p 1).
-
Multiplying [A 0. with W., can get the predictions z', after perturbations. As before we can compute the change in the CM-rype attack loss before and after attack as
(d + 11)((1))) (M))
1) | 1) 82
A CCMM-
(14)
(d, ()))(((())) 1)2
17

---

Under review as a conference paper at ICLR 2022
Finally, solving the same system of inequalities Eq. (8) for 82, get the valid range of 82
82 > O, when da < [}||
82 > when da 2 [ 1 and du d.-11+ < <h 5
(15)
82 O, when da > [ 1 and 0 1 h
du d--1y1+1
1
Note that the above solution is not applicable when d-14++1 in which d(h))1-1)
1 and the solution of optimal weight matrix W. = ([A[X]Ta..) undefined. We also note
that we always have d. -11
1- yl when | 2 2.
dd.
Dld
Summary and validation of theorem statements. Based on our derivations, we summarize and validate our statements in the theorem next.
! The attack losses Latk (CM-type, S increase only by removing a homophilous edge or path, or
adding a heterophilous edge or path to node v. From Eq. (2) (II,, (13), (15), we observe that for both direct attacks in 1-hop neighhorhood (vv) and indirect attacks 2-hop neighborhood N₂ (v), when h Z [yl' the attack loss increases only if ô1 < O, which represents removal of a homophilous edge or path to node if 62 O, which represents addition of heterophilous edge or path to node v.
2 Direct perturbations edges (or 1-hop paths) of the target node lead to greater increase in batk than indirect perturbations on multi-hop paths to target node v.
From Eq. 7 and Eq. (TO), the change in the CM-rype attack loss ACCM (z!,) for direct perturba- tions on 1-hop neighborhood (v) of the target node v considering both on and 82 can be written
as
10(2) - 1) (da (d(h)))) 1) |
+ 22)1 (62 (62-)619 61)
A A
dirdir ask
(d,, + 1) 1) DI 1)
(16)
From Eq.
12 and Eq. 14), the change in the CM-type attack loss A AL (z..) for indirect pertur-
butions on 2-hop neighborhood N2(w) of the target node v considering both dr and 82
(d + ()2 1) (da (1.)) | 1) (62 61)
A AL Cindirrect
(17)
(da + 1)
Note that when h 2 pip we have h|)l 2 1, and
1
dhlD1 d 2 - d(h)) 1) DJ = 1 da(d(h))) - 1) [ (d (d+1))
(18)
d, (h1) 1) D1
Therefore we will always have A CM,,diieect > AL CM,indirect for an effective unit perturbation that atk
increases attack loss LCM (i.e., 81 = and 82 or and 82 1) when h 2 1
C.2 DETAILED ANALYSIS OF THEOREM 2
Proof 2 (for Thm. 2) For a direct unit perturbation in the 1-hop neighborhood N of the target node v. from Eq. (9) and (II) of Proof[ we observe that the signs of 81 and 82 which increase the attack loss are contingent on the degree of the target node d, the degree of the gambit node da and the homophily ratio of the graph:
① i < d VI - 2 (i.e., when degree of the target node is low), regardless of d. and h, the attack loss increases only if 8n < O, which represents removal of a homophilous edge to node v, or 66 > 0, which represents addition of heterophilous edge v;
② if > | 2 (i.e when degree d of the target node is high), the increase of the attack loss will be dependent the degree of the gambit node da and the homophily ratio h of the graph:
18

---

Under review as a conference paper at ICLR 2022
(a) when da (d+2)(D)-1)
4-1:1+2 (i.e., when degree de of the gambit node is low), regardless of h. the attack loss increases only if O, which represents removal of homophilous edge to node or if 82 > O, which represents addition of heterophilous edge to c;
(d-2)(1))11) (i.e., when degree da of the gambit node high), for S h < (b) when da 2 d-1y++2
( < 1/'' the attack loss increases only if 01 < O, which represents
(d+1)))'de
removal of homophilous edge node v, or if 82 > O, which represents addition of het- erophilous edge to v.
We note that the above conclusions not applicable when h d- d-DV++1 in which case d(hl)]
d)3
1) + | 0 and the solution of optimal weight matrix W. ([AAX]Ts.)) is undefined.
C.3 DETAILED ANALYSIS OF THEOREM 3
Proof (for Thm. 3 In this proof. we mainly focus on analyzing the increase in Cask for the GNN layer defined SAA,X; a;))) ((1 a)A aT) XW. We follow similar process as in Proof | since the layer defined as (A, A,XW is a special case of the previous formulation when a
I+d
Layer f(A,X;a) (11-a)A + al) XW. We first derive the optimal weight matrix W. in stylized learning setup in Proof[ Following a similar process, for this GNN layer we have
S7
T7
T
T7
1 p
T
S7
T7
T7
[(1- aal) x x
To: =
|2/
+
T7
T7
T7
S7
|
where S7 = p(a + ah), and T7
(a- (a-1)(h-11) l)p
and
D-
0
0
0
0
:
Using the Shernan-Morrison formula, we find inverse:
(I(11-))A - a) aI) x Ts.
|D/|
p(a(h
1) h| T)DI
|/
1 |
+ |
|
Assuming W. ([((1-a) + al) x
we obtain
Ts
iz/T. [[(1 ((1-a)A al) X TG.: W. -Y|Ts Fòppi
Since W. satisfies L((Z]To.) ()T..) = O, we know W. is the optimal weight matrix that we can learn under Tv.
Now consider an arbitrary target node v E Dy with class label E V, and unit structural perturbation leveraging gambit node
with degree d, that affects the predictions zu of node made by GNN ((?) Without loss of generality, we assume node v has ye = 1. Note that we will only discuss the case of direct structural perturbation to the I-hop neighborhood N (1) of target node
19

---

Under review as a conference paper at ICLR 2022
indirect perturbations do affect the predictions Z. for node produced by single GNN as the change in the adjacency matrix A before and after the attack. Similar to Proof for simplicity of derivation, row-stochastic normalization of A, and we use 61 to denote addition (ő1 = 1) or removal (ő1 -1) of homophilous edge to node u, and use 02 to denote addition removal of heterophilous edge to node v.
layer. Denote A A
assume that the perturbation does not change the
In the case òi =1 and 82 we have
(1 a))1
((1-a)DA) aT) X os
dal 1110)11pp- (1-p)
(1 (1-p)
and the change in the CM-type attack loss LCM before and after the perturbation can be derived as
((1 - a]] + a 1)61 atk da(a(h - 1) // de
AC
(19)
In the case of 61 = and ó2 = 1,, we have
(1 11-aa 00
((1-a)AAA) al) x] u.
(1-p) (D) 1)p +
- 1)p-1)p+1
dalY
and the change in the CM-rype attack loss LCM before and after the perturbation can be derived as
ACCM (a 1)( 1)
(20)
da - 1) h + do
From Eq. 19 and Eq. (20). the change in the CM-type attack loss A for GNN layer f(A, X; considering both ôn and 02 can be written
((1- - a} + 1)81
(a- 1)(1 1)82
ACCME
(21)
di (a - h) da da(a(h - h-]3] da
Layer fa(A A.W.. This formulation a special case of the previously discussed S(A,X;o) formulation when 14da
In the case of 81 = 1 and d2 0, from Eq.
19
we have the change in the CM-lype alluck loss
LCM before and after the perturbation as
(1) - 1)81
CCM atk
(22)
d, -)
In the case of 82 = 0 and 82 = =1, from Eq. LCM before and after the perturbation
20 we have the change the CM-type attack loss
1D1-1)68
ACCM
(23)
d. (1))
1
From Eq. (22) and Eq. (23). the change in the CM-type attack loss ACCM for GNN layer fa(A, X) considering both 8n and dz can be written
-101-1)66 1)6;
(1>)
1)82
CMM
(24)
d. -)
dh(p D1-1
Comparison of increase in attack loss A.CM
Solving the following system of inequalities for variable
AC atk
ACCM, >
a, h E [0,
| 2
(25)
day | E Z
81, E 1-1,0,1)
20

---

Under review as a conference paper at ICLR 2022
get the valid range of a
d, < a 1, when S < [
and dg < F
1- and d1 <
<g2
05 a I when 0 < V and d,
hy1- and ó 82
1-
(26)
d,+1 < 1, when 1
31 -
and 81 < 82
From the solution in Eq. 26 observe that when h [i unit perturbation increasing Latk
discussed in Theorem (i.e. ò1 -1 and 82 0, or
and d2 will satisfy the condition
51 82, and thus lead a strictly smaller increase A A the attack loss for layer f(A, X; than the increase CMM for layer fA X) if d.
ask
21

---

Under review as a conference paper at ICLR 2022
D DETAILED EXPERIMENTAL SETUPS AND HYPERPARAMETERS
D.1 INSTANTIATIONS OF DESIGN ON GNNS
We explicitly demonstrate how the heterophilous design outlined in Eq. ( $3.2 are instanti- ated in various GNN models used in our experiments. In particular, we highlight how these GNN architectures allow separate aggregations of the ego- and seighboo-embbdddings
In H,GCN, final hidden representation is computed for each node V through re CONCAT(T!") (0) x ..."....!!!! r.k)), where ! the non-linear ego-embedding of node features and rv are the intermediate representations aggregated in the k-th layer, where k (1...., K). By interpreting the update rule's CONCAT as the ENC operation, AGGR1 as the skip connection to the ego-embedding of node features, and the concatenation of the intermediate representations as AGGR2, the ego- and neighbor-embeedding are separately aggregated and the identified het- erophilous design is recovered.
(Baal)
Similarly, GraphSAGE (with mean aggregator) utilizes concatenation- based encoding scheme through their update of
(CONCAT (I(K-1), MEAN (trl) ((r!k-1),vu Vu e N())) ())
where (GGR1()) - (k-1), AGGR2 is the mean function and (XNC(x).x)) (CCONCAT(X), W).
GPR-GNN embeds each node feature vector separately with a fully connected layer to compute r (or (0) in the original paper), similar HgGCN, and then updates each node's 's hidden representations through weighted sum of all k-th hop layers around the ego-node, where k E 1,., K). By interpreting the summation as the ENC operation as well as A.GRI(-) H) and (.) = Σx= A each k-hop ego network, the aggregation of the ego- and neighbor-embele
sym H where is vector denoting the weights associated with
can be decoupled
and thus GPR-GNN also satisfies the heterophilous design.
FAGCN follows a similar update function to GPR-GNN with
n h -eh(o)
Σ
h (-1)
JEN()) V d.d
where h()), equivalent to (0) in Eq. (.. represents the non-linear ego-embedding and a is proportionality constant measuring the ratio low and high frequency components. The relation- ship between FAGCN and the proposed heterophilous design
similarly be inferred by inter- preting the sum as the ENC operation, A.GR1()) = zh!" (") as a weighted skip connection to the ego-embedding of feature vectors, and the weighted sum of embeddings within the neighborhood (i) of node E V as AGGR2(().
CPGNN formulates the update function of belief vectors (A) after the k-th propagation layer as (k) ()) + AB (k-1) H, where (0) consists of prior belief vectors for each node (which can be seen as the ego-embedding r.()) in Eq. (L) and H is the linearized compatibility matrix. The heterophilous design be recovered by letting AGGR1()) (0)) skip connection to the prior belief, AGGR2(.) (k-))) H. and the ENC operation the summation.
22

---

Under review as a conference paper at ICLR 2022
D.2 MORE DETAILS ON THE EXPERIMENTAL SETUP
Benchmark Implementations. Our empirical framework is built on DeepRobust (Li et al. 2020b). Python Fire and signad We incorporated the following implementations of GNN models in our framework. For GNNGuard and GCN-SVD, there are some implementation ambiguities, which we discuss in the next paragraph.
H,GCN (2hu el 2020
bttps://
ccp/ http///n////eeeeeeeeeeee wttpc//////oeee.-e
GraphSAGr MAGGGGGiiiiiii Iion c al. 2017
Impkeeena up ht 1/ /01 hilb com Lee///eenaa///eeee
CPGNN Zan aran p021
beips:/ github.......................... 20B/
Laby GPNN
GNNGuard IZhng & Zinik.
2020
https:/ wwt.//t.h....oco........b con weapm//mnn-haaae haw.ard/ hww.aa/da-aaddalaaaaa.a. Calrdd
ProCNN [inerai M1210
nt 1957 aar.aaahaa hal 2008 Lier 1o
GRB
GCN-SVD pasaan & Mi. 2020
GAT (ilhkuvii et al
httos:/ /ttps/////tttttt con/ wcmpppg-Ms/ Deenkcburt bustt / http:///tttttttttcoooooooooooooo /grach/ /atonse/aar my
GCN Kapp & Welning 7017
IC sps 177 gachau coaaa...cc// w00// 385 Deeproeest DTOD www.aattoer.ooooooooo..o.oo....a wtwp:////eoppopoo/oo /gwpp/y da 201 qen. sy
Notes on the GNNGuard and GCN-SVD Implementations. We note that there are ambiguities in the implementations of GNNGuard (Zhang & Zitmik| 2020) and GCN-SVD (Entezari et al., [2020), which can lead to different variants with different performance and robustness, as we show in Ta- ble G
Table 6: Performance comparison between variants of GNNGuard and GCN-SVD: mean accuracy + stdev over multiple sets of experiments.
Homophilous graphs
Heterophilous graphs
Homophilous graphs
Heterophilons graphs
Cora 1=0.804
Citeseer 1=:0,736
FB100
Snap
Cora k=0.804
Citeseor
FB:00 A=0.531
Snap
h=0.531
1=0.134
A=0.134
Clean Datasets
Clean Datasets
GNNGuard (1)
75.56:
70.00
68. 68.89a2as
31.67
79 29058
71.68
63.31:114
26.37
GNNGmard (IT)
7
67.78
67.22
28.33
80. 15
72.61a
65 66.66
26.5
GCN:SVD (1)
66.67
63,89
$1.67.43
29.44
69.43
68.31
52.95
27 16.6
GCN-SVD (I))
52.78-130
35.00-12
50.56
25.00-133
53.05
41.47aam
52.40:eas
25.8 25.84
GCN-SVD (T)
10
66. 11
66
52.782
30
30.562284
Metatack
71 71.08
69. 19
54.47207
57.5
GCN-SVD (IT) h 10
66. 1 11
45 45.00
11.11
22.22
64.79
$2, 17
19.19
25.45
GCN-SVD (T) ===== 15"
72.78
63
89 2o
59.78
................................
72.74
66.31
59.67
GCN-SVD 15
69 44.
46.67 sass
52.78
21.67
63 65.61amn
60.55
53.24
26.631
GCN&&VD (1) 50"
78 29
66 67
66,562m
31.11
77 98
68 25
63.41
27
27.81
GCN-SVD (II) 50
75.5624s
24
55.00
27.78
26
66.90ssm
58.47
65.6220
Poison Attucks
Poison Attacks
GNNGuard (1)
60.00.a0
0.56
11.11
73.68 s00e
60.82 lea
23.
GNNGaard (II)
58.33amm
29.44
0.56
9.44
74.20
68, 13g
23.78 60.89.a.
GCN-SVD g
61.444.1
60.00:m
41.67
27.78
644.55 1227
66.35
33.14
25.64
GCN-SVD
44.44a25:
33.33
41.67
25.00
42.19
40.17a
51.87
24.824043
GCN-SVD (T) i 10
67.78
57.78
31.67
Mesitack
65.54g118
65.46259
58.68
25.93
GCN-SVD (I))
10
48.89
31.67
34.44.1M
26. lasas
49.92 49.92a55s
47.16
53.16
25. 25.30
GUN:SVD (1) 15"
52.78
23380"19
290 99:45
22 23.8310m
GCN-SVD (TT) A = 15
33.89_se
30.56
26. I Haaes
30.30
47.87am
54 20
25. 2505
GCN-SVD (1) A 50"
61.67g4
48.3
18.33.50
16.67_mm
.....
30.56.110
66006655
49. 49.3
62.07 seca
26.05 s00
GCN-SVD 50
53.33
28.89 20m
23.33
25.00
47.82
$1.20
55.00
28.18
Evasion Attacks
Evasion Attacks
GNNGuard (1)
GNNGuard (II
GCN.SVD E
64.44
59.44gim
41.11am
31.67259
68. 18.18
67.54gm
22.9
27. 47.00
GCN-SVD (II) 5
46.67
32.22
43.
52.01 1245
30.69.:.
25.87 52.32.e.a
GCN-SVD (T)=
10
65.56
"57,22200"
36.112
31.
61852m
544.11.0
227 30
GCN-SVD
10
S7.22
37.78
36.67
30.56
58 20.70a
45.62229
52.58
24 24.60
GCN-SVD (1) A 15"
67.22
54.44
24.44.100
30.00.1144
66.32
65.26
57.79.02
28 16:
GCN-SVD (ID)
15
65.56a4 i
38.33
23.89_
27.22
64.02a.1
$4.09
53.81
25 25.29
GVN (1)=== 50"
65:00
18.35
28,3661157
"75,0100
63053
27.7
GCN-SVD (II) = 50
60.00
47,78
25.00
30.56:3339
73.21s1
59,34
56.95
25.80
For GNNGuard, the ambiguity comes from different interpretations of Eq. (4) in the original pa-
per (Zhang & Zitnik| 2020): we consider the authors' original implementation as variant (I), and the model described in the original paper as variant (II), which we implement by building on the
authors' implementation.
fire
https://signac..1
23

---

Under review as a conference paper at ICLR 2022
Table 6 shows that the differences in accuracy between the two variants are in most cases less than 2%, while in many cases variant (II) shows better accuracy compared to variant (D, especially in experiments against Metattack. Thus, use variant (II) as the default implementation for the empirical evaluations in $
For GCN-SVD, the ambiguity comes from the order of applying the preprocessing and low-rank approximation for the adjacency matrix A, which is not discussed in the original paper (Entezari
al. 2020
Variant (I): Since the original authors' implementation is not publicly available, consider the implementation provided in DeepRobust (Li et al. 2020b) as variant (I): first calculates the rank-k approximation Å of A, and then generates the preprocessed adjacency matrix A. + (A
D. 1/2 (À 2017). However, the identity matrix I is added into A after the low-rank approximation, the diagonal elements of the resulting A, matrix (i.e., the weights for the self-loop edges in the graph) can become significantly larger than the off-diagonal elements, especially when the rank is low. As result, this order of applying the preprocessing and low-rank approximation inadvertently adopts Design which we identified; we have shown in Theorem 3 that even merely increasing the weights a for the ego-embedding the linear combination ENC in Eq. T can lead to reduced attack loss Latk under structural perturbations.
A,D,1/2 1/2 which is then processed by GCN (Kipf & Welling I)D 1// 1, A,D,
Variant (II) In variant (II), we consider the opposite order where we first add the identity matrix I (self-loops) into the original adjacency matrix A, then we perform the low-rank approximation, and finally we symmetrically normalize the low-rank matrix Ag to generate the preprocessed Åg used by a GCN model. This order allows the diagonal elements to be more on par in magnitude with the off-diagonal elements. As an example, on Citeseer, when using variant (I) with rank k 5. the average magnitude of the diagonal elements of the resulting A. can be 22.3 times the average magnitude of the off-diagonal elements; when using variant (II) instead, the average magnitude of the diagonal elements is only 9.0 times that of the off- dif-giagonal elements.
In Table 6 we report the performance of the two variants of GCN-SVD under the experimental set- tings considered in $ with rank E {5, 10, 15, 50}: Variant (I), with our first design implicitly built- in, has in most cases significantly higher performance than variant (II), especially on homophilous datasets and when rank & is low. These results further demonstrate the effectiveness of Design I that we identified. To enable clear perspective of the performance and robustness improvement brought by Design 1, in our empirical analysis in $5 on top of the low-rank approximation vaccination we adopt variant (II) as the default implementation.
Attack Implementations. We incorporate the following implementations of attacks from DeepRobust (Li et al. 2020b) to our empirical framework.
NETTACK
Zigaer al. 2018|
htspat//2ithcb.coo www.///eeeeeeeeeeeeeeeeeeeeeee /DS2-BBU /Deephabust /blob htt.:///waaae//aaaaaaaa/////o///
Motalfack
Zigne: Glroemann 20156
Itspos// wwc.cb..bbbooooooooooooo www.boo............//./...... /0/00005BBB Dasp///Dookuusssco /010b www/aaatttaaa dwwp:///oppppopooooooooo httppupt///pppppoooopop accacee www.aa///ttttacoc Lack..
More Details the Attack Setup. For NETTACK, we randomly select 60 nodes from the graph as the target nodes for each set of perturbations, instead of the GCN-based target selection approach as in (Zügner al. 2018): the approach in Zügner al. 2018) only selects nodes that are correctly
classified by GCN (Kipf & Welling (017) on clean data, thus introducing unfair advantages towards GCN, especially on heterophilous datasets where GCN can exhibit significantly inferior accuracy to models like GraphSAGE (Zhu et al.) 2020). For the experiments in $5.1 we use a budget of perturbation per target node to match the setups of our theorems; for the benchmark study in $5.2) we use an attack budget equal to node's degree and allow direct attacks on target nodes. For Metattack, we budget the attack as 20% of the number of edges in each dataset, and we use the Meta-Self variant as it shows the most destructiveness (Zügner & Günnemann 2019a).
More Details on Randomized Smoothing Setup. Following Bojchevski et al. (2000), we similarly 0.99), using
set the significance level a 0.01 (i.e., the certificates hold with probability 102 samples to estimate the predictions of the smoothed classifier f()(s)) for input s, and another 108 samples to obtain multi-class certificates. For the randomization scheme Φ, we only consider structural perturbations where with probability p+ an new edge is added, and with probability p. an existing edge is removed. We consider multiple sets of (p+,p- P-) in our experiments for finer-
24

---

Under review as a conference paper at ICLR 2022
grained evaluation: (1) p+ 0.001, p_ = 0.4, where both addition and deletion allowed: (2) p+ = 0.001, p- = 0, where only addition is allowed; and (3) p+ 0,p- p- = 0.4, where only deletion is allowed.
Hardware Specifications. We use a workstation with a 12-core AMD Ryzen 3900X CPU, 64GB RAM, and Quadro P6000 GPU with 24 GB GPU Memory.
D.3 COMBINING HETEROPHILOOUS DESIGN WITH LOW-RANK APPROXIMATION
In this section, we provide more details on how we incorporate the low-rank approximation vacci- nation into the formulations of H₂GCN (Zhu et al. 2020) and GraphSAGE (Hamilton et al. 2017) in order to form the hybrid methods, MLGGN-SVD and GraphSAGE-SVD
HcGCN-S From (Zhu al.) 2020), each layer in the neighborhood aggregation stage of H,GCN can be algebraically formulated as
R (k) CONCAT (A,R(K-1), AR R(I-1)),
(27)
where Å = D-1/2AD AD 112 1/2 is the symmetrically normalized adjacency matrix without self- loops; A D. A2D,, 1/2 is the symmetrically normalized 2-hop graph adjacency matrix A₂ E f0, 1 with [A2]u,e 1 if is in the 2-hop neighborhood N²(u) of node R(() are the node representations after the k-th layer, and CONCAT is the column- wise concatenation function. For H,GCN-SVD, we replace Å and Å2 in Eq. 27 respectively with the low-rank approximations of À and Åg which are both postprocessed to be symmetrically normalized.
GraphSAGE-SVD. From (Hamilton et al. 2017), each layer in GraphSAGE be algebraically formulated as
(k) (CONCAT (k-1) ,,((()))) w(k-1)).
(28)
where A is the row-stochastic graph adjacency matrix without self-loops; (k) are the node rep- resentations after the k-th layer; CONCAT is the column-wise concatenation function; W(k) is the learnable weight matrix for the k-th layer, and a is the non-linear activation function (ReLU). For GraphSAGE-SVD, we replace A in Eq. (28) with the low-rank approximation of the adjacency matrix A. postprocessed by row-stochastic normalization. Note that do enable the neighbor- hood sampling function for the GraphSAGE and GraphSAGE-SVD models tested in this work, as noted Appendix D.4
D.4 HYPERPARAMETERS
H,GCN-SVD
Initialization Parameters:
Training Parameters:
adj_svd_ree _svd_rank:
early.stopping: Yes
best chosen from (5, 50) for each dataset
train_iters: 200
patience: 100
GraphSAGE-SVD
Initialization Parameters:
Training Parameters:
- aadj nhood: ['1']
early.stopping Yes
network_setup: 1.r.:-6..v..11------1776000000.0
train iters: 200
patience; 100
aadj addinoom..typ:: rw
adj .ddj.ssd_rank:
best k chosen from (5, 50} for each dataset
25

---

Under review as a conference paper at ICLR 2022
H₂GCN
Initialization Parameters:
Training Parameters:
(default parameters)
eeaiyystoopinn:: Yes
trriinitees:: 200
patience: 100
1r: 0.01
GraphSAGE
Initialization Parameters:
Training Parameters:
addjdooood: ['1']
early.stopping: Yes
network.setup:
train.iters: 200
patience: 100
adj norm type: rw
1r: 0.01
CPGNN
Initialization Parameters:
Training Parameters:
network.setup: M64-R-MO-B-BP2
early_stopping: Yes
arain.iters: 400
patience: 100
1r: 0.01
GPR-GNN
Initialization Parameters:
Training Parameters:
-hhid: 64
train.iters: 200
alpha: 0.9, which is chosen from the best
1r: 0.01
(0.1, 0.5, 0.9) all datasets
FAGCN
Initialization Parameters:
Training Parameters:
-nhid: 64
early stopping: Yes
alpha: 0.9, which is chosen from the best
1r: 0.01
E (0.1, 0.2, 0.5, 0.9} on all datasets
dropout: 0.5
GNNGuard
Initialization Parameters:
Training Parameters: train_iters:: 81
-nhid: 64
-ropoou:: 0.5
1r: 0.01
-basemodel: GCN for variant (I); SCN-fixed for variant (II) (default).
26

---

Under review as a conference paper at ICLR 2022
ProGNN
Initialization Parameters:
Training Parameters:
-nhid: 64
epochs: 400
- -dropout: 0.5
1r: 0.01
1 adj: 0.01
weight.decayy 5e-4
alpha: 5e-4
beta: 1.5
gamma:
lambda.: 0
phi: 0
outer.steps: 1
innter steps: 2
GCN-SVD
Initialization Parameters:
Training Parameters:
nhid: 64
train iters: 200 weight .decay: .decaay 5e-4
k: best & chosen from {5. 10, 15, 50} for each dataset
1r: 0.01
ddropout: 0.5
svd_solver:
eye-svd (for variant (II) only)
GCN
Initialization Parameters (in class MultiLayerGCN);
Training Parameters:
trrin.iters: 200 1r: 0.01
nhid: 64
nlayer: 2
weight-decay: 5e-4
GAT
Initialization Parameters
Training Parameters:
-nhid: 8
-earlysstoppinn: Yes
heads:
trrin_iters: 1000
- dropout: 0.5
patience: 100
1r: 0.01
www wei.hhteecay: 5e-4
MLP
Initialization Parameters: (in class H2GCN):
Training Parameters:
early.stopping: Yes
network_setup:
train.iters: 200
464-R-DO.5-M
patience: 100
1r: 0.01
27

---

Under review as a conference paper at ICLR 2022
D.5 DATASETS
Dataset and Unidentifiability.
2012 is set of 100 university friendship network snapshots from Facebook in 2005 (Lm et al. 2021). from which we use one network. Each node is labeled with the reported gender, and the features encode education and accommodation. Data sent to the original authors (Lim et al. 202T) in an anonymized form. Though the dataset contains limited demographic (categorical) information volunteered by users on their individual Facebook pages, we manually inspect the dataset and confirm that the anonymized dataset is not recoverable and thus not identifiable. Also, no offensive content found within the data.
Heterophilous Datasets: FB000 (Traud
Snap Patents (Leskovec et al. 2003 Leskovec & Krevl 2014) is a utility patent citation network. Node labels reflect the time the patent was granted, and the features are derived from the patent's metadata. The dataset is maintained by the National Bureau of Economic Research, and is freely available for download Neither personally identifiable information nor offensive content is iden- tified when we manually inspect the dataset.
Homophilous Datasets: Cora (McCallum] 2000) and Citeseer (Sen et al. 2008 datasets are
scientific publication citation networks, whose labels categorize the research field, and features indicate the absence or presence of the corresponding word from the dictionary. No personally identifiable information or offensive content identified when we manually inspect both datasets.
Downsampling. For better computational tractability, we sample subset of the Snap Patents data using a snowball sampling approach (Goodman) 1961). where a random 20% of the neighbors for each traversed node are kept. We provide the pseudocode for the downsampling process in Algo- rithm
Algorithm 1: Downsampling Algorithm For Snap Patents
Input: Graph to sample
Number of nodes to sample N
Sampling ratio p
Output: Downsampled graph G"
initialization
/* Initialize queue bfSquene for Breadth First Search, and a 1ist nodessampled for storing sampledd nodes
bfsquene +- QUEUR)
nodeSsampled + LIST(
/* Start BFS with random node from the largest connected component
in G;
RANDON (array, n) returns n elements from an array with equal probabilits without replacement
nodestartnng f- RANDMILLAGSTCOOMRTTTCCCOOOMOYA, 1)
push nodestarting into biisquene
6 while LENGTH((ndeSssopped i N do
node +- blusquene. (
neighbors t one hop neighbors of node
neighbors <- RANDOMMnnighhorr, px LENGTH(neighbors) )
10
for neighbor E neighborsärown do if neighbor nodessampied then append neighbor to nodessampled
11
12
13
push neighbor into bfSquenne end end
end
17 G' +- subgraph induced by nopes
return G'
http:///www.eerrrr/////eeeeeroo t
28

---

Under review as a conference paper at ICLR 2022
E DETAILED EXPERIMENT RESULTS
E. DETAILED RESULTS EVALUATION ON EMPIRICAL ROBUSTNESS
Table 7: Detailed classification accuracy (and standard deviation) each method for the target nodes attacked by NETTACK, calculated across different sets of perturbation.
Homophilous graphs
Heterophilous graphs
Cora
Citeseer
FB100 1=0.531
Snap h=0. 134
h=0.8004
h=0.736
Clean
HzGCN-SVD
74.44
70.00
61.67+236
30.56-2008
GraDhSAGE-SVD
77.2244.8
70.00+136
60.00+4m
27.22
H2GCN
82.78
69.44-168
60.562157
30.00
GraphSAGE
82.2229956
70.562635
60.0012.2
24.44_4.16
CPGNN
81.67 48.28
73.33
66.11
28.89
GPRGNN
82.22
67.78
56.67
27.78=3.22
FAGCN
83.33
70.56
58.33+5.9
29.44_0799
GNNGuard
77.22 +6.29
67.78
67.22
28.33 3.60
ProGNN
79.44
67.22
51.11
27.22
GCN-SVD
75.562416
59.44
50.561437
27.78=6.71
GAT
84.44
70.00
60.561179
30.56=288
GCN
82.78
69.444774
63.3342m2
33.33=272
MLP
64.44 1342
70.561342
57.78
30.00
Poison (Pre-training)
H₂GCN-SVD
70.00
65.00
59.441342
28.89_3.4
GDDDhSAGE-SVD
71.67
67.78+342
60.00+136
26.67=6.81
H,GCN
38.89
27.22
27.78 +3442
12.78
GraphSAGE
36.67
31.67+10a9
33.894342
16.67=797
CPGNN
47.224614
40.56
10.44
21.67
GPRGNN
21.67:2272
24.44
2.78
4.44=2.08
FAGCN
26.111614
25.561643
6.11
8.33=3600
GNNGuard
58.33
59.44.3.14
0,56
9.44=1.77
ProGNN
48.89
32.78
33.89
17.78=9.26
GCN-SVD
53.33
28.89
41.67+236
25.00=5.44
GAT
13,89 40.29
8,894342
0.564409
3.89 4.57
GCN
1.67
4.44
0.56207
2.22-2008
"MLP
64. 1342
70.36+342
57.7842x3
30.00
Evasion (Post-training)
H,GCN-SVD
70.564342
66. 11478
60.00
28.89_3.44
GraphSAGE-SVD
70.56
68.334360
59.444281
26.11=685
H&GON
45.5643.42
33,89
32.781079
12.78-263
................................
GraphSAGE
44.4413.14
35.00
42.224283
15.56-671
CPGNN
52.22+a>h
46.67
15.56+233
22.78
GPRGNN
+9.44+311
32722
9,44
3.33
FAGCN
38.894671
37.78+478
12.78+2a3
10.00-236
GNNGuard
ProGNN
GCN-SVD
60.00
47.78
45.56
30.56
GAT
12.22 1416
23.33 1:541
w...............................
1.67 1136
w...............................
2.22
................................
GCN
5.56
8.89
0.56
0.56-0.79
MLP
64.4 64.441342
70.56+342
57.78
30.00
29

---

Under review as a conference paper at ICLR 2022
Table 8: Detailed classification accuracy (and standard deviation) for the unlabeled nodes of each method attacked by Metattack with budget as 20% of the total number of edges of each graph, calculated across different sets of perturbation.
Homophilous graphs
Heterophilous graphs
Cora
Citeseer
FB100 h=0.531
Snap
h=0.804
h=0.736
h=0.134
Clean
HCGNS-
76,89
73.42
56.81 1078
27.63_m.2
GraphSAGE-SVD
77.52+0.9
72.16=a17
57.38=0m6
H,GCN
83,94
75.34
56.95+0.13
27.49
GraphSAGE
82.2 +0.6
74.64=n98
56.60=140
27. 27.18
CPGNN
80.67 20.51
74.92=002
60. 277.00
27. 132063
GPRGNN
81.84
70.71
62.40
26.08
FAGCN
81.59
73.99=06s
59.64
27.15_003
GNNGuard
80. +0.1
=226
65.66=000
26.51
ProGNN
81.32
71.82
49.84
27.49=0.6
GCN-SVD
76.61
66.90.1.16
55.471023
26.63.1025
GAT
83.721004
73.40=100
61.691092
27.30=00s
GCN
84.32+0.2
74.27
64.86+079
27.30=043
MLP
64.55
67.67
56.56
26.25
Poison (Pre-training)
H₂GCN-SVD
67.87
70.422046
56.72
25.60=0.14
GraphSAGE-SVD
68.8611.3
69. 19.10
55.7620.3
26.58=030
H.GCN
$7.75166
54.34
54.8410.7
25.34_1059
GraphSAGE
54.68 12256
59.74
54.72
24714
CPGNN
4..5
68.07=198
61.58=1.50
26.76=0A1
GPRGNN
48.29
35.25
59.942000
21.06=129
FAGCN
60.11
53.18 1
55.97 1:181
24.04
GNNGuard
74.201055
68.
13114
60.89 10.48
23.781007
ProGNN
45.10+6.0
46.58
53.40
24.80=1.0
GCN-SVD
47.82+1.9
51.20+178
55,00=206
25.25=091
GAT
41.70+1.0
48.40=2.17
50.37
25.00=003
GCN
37 37.462135
45.812290
51.822141
25.03=008
MLP
64.55
67.67
56.561oss
26.25
Evasion (Post- (oott-rrainngg)
H,GCN-SVD
74.01
71.54
56.58
27.26-
GraphSAGE-SVD
74.3 40
70.22=n90
27.38
26.77-101
H₂GCN
82.86+1m
73.20=204
$7.05
27.10=000
GraphSAGE
80.57 1o55
72.8911.7
56.91 1.61
27.16
CPGNN
79.06
73.44_199
60.19 19..9
27.02
GPRGNN
80.80+167
69.77=n42
61.91 20.74
26. 16-025
FAGCN
80.70
73.14
59,39
27.25 L.30
GNNGuarrd
ProGNN
GCN-SVD
73.21 +1.6
59.34+342
56.95 +0.33
25.29 :041
GAT
81. $1.961031
70.70
61.44..04
27.45
GCN
23.03
73.06=a.5
64.80 64.86
27.15=00.9
MLP
64.55
67.67
56.56+0.58
26.25=1.05
30

---

Under review as a conference paper at ICLR 2022
E.2 DETAILED RESULTS FOR EVALUATION ON CERTIFIABLE ROBUSTNESS
Table 9: Accumulated certifications (AC), average certifiable radii (Fa and F.) and accuracy of
GNNs with randomized smoothing enabled (i.e., f(o(s))) on all nodes of the clean datasets, with
ramdomization scheme á allowing addition only (i.e., P- = 0.001, p- = 0) or deletion only (i.e.,
P+ 0, p- 0.4). For each statistic, we report the mean and stdev across 3 runs. Best results highlighted in blue per dataset, and in gray per model group. For results with randomization scheme allowing both addition and deletion, see Table 4
Addition Only
Deletion Only
Hete.
AC
Fa
Fa
Acc. %
AC
Fa
Acc. %
G&GNN
0,422001
0.52+00s
80.852195
5.41
6,44
84.04215s
GraphSAGE
0,28
0.34
81.05+134
5,05
6.12+006
82.49+1.s
CPGNN
0.17=000
0.21+00s
+8.34
4.92+003
6.
79.69+08:
GPR-GNN
Cora
0.43
0.55
76.96
5.37
6,58
81.561159
FAGCN
0.43==001
0.54
79.04
5.74+00s
7.03
81.56+a50
GAT
0.19 20.0e
0.23
81.622om
5.561a1
6.58
84,461108
GCN
29192
0.24
81,522310
5.71
6.76200s
84,49
H&GCN
0.29
0.40+006
72.93
1.
7.29
76. 17444
GraphSAGE
0,33
0.45
74.66
5,43
7.15
75.97
CPGNN
5
0.20
74.62
5,59
7.54
74.05
Citeseer
GPR-GNN
2.40
0.59
67.522049
5.05
7.21 2006
70.101015
FAGCN
0.38=0.22
0.53+082
72.41+103
5,46+am
7.42+012
73.56+015
GAT
0.09
0.13
74.077004
5.39
7.25
74.33214
GCN
0.18=0.01
0.25
74.07
5.55
7.42+016
74.76+072
H&GCN
0.5 0.54
0.94
$7.11
4.75+amm
8.32+003
57.15+023
GraphSAGE
0,52 0.52
0.92
56.702141
4,28
7,562010
56.58113:
CPGNN
2.04
0.90
60.39
4.22
6,6620n
63.301m29
GPR-GNN
FB100
0.46
0.73
62.26
4.04
6.51
62.05
FAGCN
0.55
0.90
60.60#0.6
4.58
7.71
49.45
GAT
0.46
0.74
61.97=111
3,33
5,.77
62.01
GCN
0.42
0.65
64.70
3.28
5.01
65.50
H&GCN
0. =:000
0.42+005
26.74
1.41
5.16
27.28 +
GraphSAGE
0.06
0,24
27.002063
1.10
4.04
27.21 100
CPGNN
0. 22:00
0.43
27.002041
1.69
6,39
26.45-1950
GPR-GNN
Snap
0.03
0.1 I +0,02
24.14
1.10
4.19
26.24
FAGCN
0.10 200001
0.36
27.13
1.77
6.48
27.25
GAT
0.02 =0.00
0.08 +0.02
27.00+0.59
1.10+am
4.06=0.1
27.18+nn4
GCN
0.02
2.07
27.45
1.38
5.01 2016
27.57
E.3
COMPARISON BETWEEN CERTIFIABLE AND EMPIRICAL ROBUSTNESS
While the evaluations both empirical and certifiable robustness have shown that methods fea- turing the design have shown largely improved robustness compared to the best-performing unvac- cinated method, we find that the robustness rankings for methods under certifiable and empirical robustness are different; previous results from Geisler et al. (202)) have also shown discrepancy in certifiable and empirical robustness rankings.
We think this discrepancy may be attributed to multiple factors. Firstly, the radius on which cer- tificates can be issued with randomized smoothing may not cover the radius of perturbations we allowed for NETTACK and Metattack in $5.2 which are more than tens of edges for Metattack and high-degree nodes in NETTACK (where we use an attack budget equal to the degree of the target node). Furthermore, even for low-degree nodes, attacks are much more inclined to introduce new edges instead of removing existing ones, as we have shown in $5.1 which can make much harder to obtain certificates (Bojchevski al. 2020). In our case, the methods we evaluated generally have Fa < 1, meaning that for most nodes there are no certificates to cover even the addition of a single edge. Thus, methods which display higher certifiable robustness under smaller perturbations may not keep their robustness under larger perturbations by empirical attacks. Moreover, while we are evaluating on randomized smoothed models f (0(()) measure certifiable robustness, in empirical
31

---

Under review as a conference paper at ICLR 2022
robustness evaluating on the robustness of the base models f(s), which may differ from the robustness of the randomized smoothed models. Lastly, it is worth noting that the lack of certifica- tion for model within certain radius does not imply vulnerability all adversarial attacks within that radius; the model may still be robust against many attacks within that radius. Similarly, it is also possible for existing certification approaches to miss some certifiable cases. Taking all these factors into account, we believe that while evaluations on certifiable robustness provide complementary per- spectives evaluations empirical robustness, the current stage cannot replace the evaluations on empirical robustness, and the relation between certifiable and empirical robustness remains as question for future works.
E.4 COMPLEXITY AND RUNTIME HETEROPHILOUS VACCINATION
Another benefit of adopting neterophill-inspiree design for boosting robustness of GNNs is their smaller computational overhead compared existing vaccination mechanisms, especially vaccina- tions based on low-rank approximation. As our identified design can be applied as simple archi- tectural changes on top of an existing GNN, they usually maintain the same order of computational complexity the base model. For example, adding the heterophilous design to GCN (Kipf & Welling, 2017) results in an architecture similar to GraphSAGE (Hamilton et al. 2017): both have the same order of computational complexity as O(I [E) by leveraging the sparse connectivity of most real-world graphs. Low-rank approximation- based vaccination, on the other hand, approx- imates the adjacency matrix of graph by SVD, resulting in adjusted low-rank adjacency matrix À based on which the GNN runs. However, not only is computing an SVD potentially costly (0( (V9) in general), but in most cases it also results in dense Á (in contrast to the sparse original adjacency matrix), thus increasing the complexity of each iteration of the GNN.
Table 10: Runtime (in seconds) of 200 training iterations on Cora. See App. D for the implementa- tion used for each method.
GCN
GAT
GNNGuard
ProGNN
GCN-SVD
H₂GCN
2.17
2.98
39.63
220.30
134.81
16.54
GraphSAGE
FAGCN
GRP-GNN
CPGNN
H,GCN-SVD GraphSAGE-SVD
17.24
1.91
2.66
24.08
62.33
55.45
Table 10 shows the runtime of 200 training iterations of each model. We observe that models with the heterophilous design have the smallest runtime among all vaccinated models. Even for methods based on the same implementation, H₂GCN and GraphSAGE are still 3-4 times faster than the cor- responding H₂GCN-SVD and GraphS sure the runtime of each model on an Amazon EC2 instance with instance type as p3. 2xlarge, which features an 8-core CPU, 61 GB Memory, and a Tesla V100 GPU with 16 GB GPU Memory.
methods. For fair runtime measurements, we mea-
E.5
ADDITIONAL RESULTS ON STRUCTURAL. ATTACKS ON HETEROPHILOUS GRAPHS
Cora (h = 0.804)
Citeseer (h = 0.736)
FB100 (h 0.531)
Snap (h 0.134)
10a
10
10a
10a
Gembit Degree
10'
10"
10'
10'
6 egp
8 Sog
O OXD 0D)
O OC
COC00I COOMED
000 CDO
10
о COMKED
10
O OXDO
10"
@ 000D
10"
CDo O
10
10'
10
10
10'
10
10
10
10"
10
10'
15'
Target Degree
Target Degree
Target Degree
Target Degree
Figure 2: Scatter plots of the degrees of the target nodes (x-axis) and gambit nodes (y-axis) involved in the targeted attacks studied in $5. Attacks tend to leverage gambit nodes with low degrees, especially on heterophious graphs, which makes attacks increasing heterophily effective following the conclusions of Thm.
32


Reviews:
[{"review_id": "vMbap5FNKFd", "reviewer": "Reviewer_Vyu4", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "### Strengths\n* The paper has a thorough and well-designed experimental study.\n* The paper studies empirical *and* certifiable robustness, which are both interesting and important.\n* The authors compare a broad range of different models.\n\n### Weaknesses\n* The paper does not propose a new method.\n* The authors only combine the SVD preprocessing with two of the models studied in this work.\n* The paper references [Geisler et al. 2020] but does not compare to their proposed model.\n\n### Detailed comments\nSome remarks and questions:\n\n**SVD preprocessing**\n* Why are only two GNNs combined with SVD? CPGNN is the most robust non-vaccinated GNN, so adding SVD to it might lead to more robustness than e.g., GraphSage-SVD. \n* The SVD preprocessing effectively acts as a low-pass filter and could \"destroy\" some of the high-frequency heterophily information in FB100 and Snap. Could this be a reason why the SVD-augmentation adds much less robustness on these datasets?\n* On a related note, the SVD preprocessing does in general not preserve sparsity of the graph. Thus, the 1- and 2-hop neighborhoods of the nodes might become very large and could lead to oversmoothing. Is this an issue in the present study? An alternative could be to use GDC [Klicpera et al. 2019] preprocessing, which is also a low-pass filter but preserves sparsity.\n\n**Robustness in homophily-based GNNs.** While the authors' arguments for increasing robustness via heterophily-adjusted GNNs makes sense to me, [Geisler et al. 2020] achieve comparable or larger certified performance (e.g., as measured by AC) on Cora and Citeseer, while not adhering to the heterophily design proposed in this work. Instead, the method \"doubles down\" on the homophily design by using GDC [Klicpera et al. 2019] preprocessing and an aggregation function designed to be not affected by outliers. Are the strategies in the present work and [Geisler et al. 2020] alternative solutions to increase robustness in homophily networks? A discussion on this would be very interesting in my view. \n\n**Benchmark results.** In my view the benchmark results section would benefit from also showing the clean performance of the models for the untargeted attacks. For example by having an analogous to Fig. 1 for untargeted attacks or by swapping the error bars in Table 3 with the change in accuracy compared to the clean performance (the error bars should then of course be provided in the appendix). \n\n**Heterophilic structure attacks (Q1) (side remark).** The results for the homophilic datasets in Table 2 seem to corroborate the findings presented in [[Zügner et al. 2020](https://dl.acm.org/doi/10.1145/3394520)]  and [[Zügner and Günnemann 2019](https://openreview.net/pdf?id=Bylnx209YX)] (which is good to see), and the results on heterophilic datasets are a valuable and interesting addition.", "summary_of_the_paper": "The authors present a study on the robustness on GNNs on homophilic and heterophilic datasets. The authors first show in a stylized theoretical setting that GNNs with a *heterophilic design* (separate aggregation of ego- and neighborhood representations) should show increased robustness against structure perturbations. Then, they follow up with an experimental study where they compare homophily-based GNNs with GNNs following a heterophilic design on both homophilic and heterophilic datasets. In addition, the authors augment three GNN models with the SVD preprocessing by [Entezari et al. 2020] in order to improve robustness. The authors study both empirical as well as certifiable robustness (via randomized smoothing). In general, GNNs with heterophilic design show higher empirical and certifiable robustness across datasets.", "summary_of_the_review": "In summary, I appreciate the thorough experimental study in the paper and believe that – even though the paper does not propose a new method – the findings have relevant implications for GNN design choices. There are some additional experiments and discussions I would be interested to see (see main review). Overall, I'm not opposed acceptance currently.\n\nAfter reading the authors' response to my review I increase my score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "uTfthOYKGGs", "reviewer": "Reviewer_aMbV", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "This work studies the relation between graph heterophily and the robustness of GNNs and theoretically show that effective structural attacks on GNNs for homophilious graphs lead to increased heterophily level, while for heterophilious graphs they alter the homophily level contingent on node degrees under some specific assumptions. \n\nDespite this, the paper is not particularly novel. The theoretical results are derived under some specific assumptions on graphs and GNN layers, which may not be appliable to real-world graphs. \nTheorem 3 cannot support the claims that the heterophily-inspired design (i.e. separate aggregators for ego- and neighbor-embeddings) could improve the robustness of GNNs because the GNN layer analyzed in the theorem is significantly different with the heterophily-inspired design. \nFurthermore, experiments are conducted on small datasets and the experimental results cannot validate whether the theoretical claims can be generalized to large real-world graphs, which is an important aspect given that the theoretical claims are based on specific assumptions about graphs.\n\n\n \n## Strength\n\n1. The paper is well written and is easy to follow.\n2. The authors have studied an important open problem in deep graph learning community.\n\n\n## Weakness\n\n1.  The paper is limited in novelty: while the paper investigates the relation between graph heterophily and the robustness of GNN and show that several heterophily-inspired GNNs work more robust to GCN and GAT, there is no new methodology proposed in the paper.\n2.  This paper is constrained to specific target attacks (i.e. CM-type attacks) and linear GNN layers, which may not be applicable to most GNN architectures with nonlinearity and other types of attacks. \nIn addition, they are derived for specific graphs with fixed degrees for every node and specific node features, which may not generalize to real-world graphs.\n3.   Theorem 3 does not support their claims on the effectiveness of the heterophily-inspired design (i.e. separate aggregator for ego- and neighbor embeddings). Theorem 3 shows that the GNN layer $f = ((1 - \\alpha)\\bar{\\mathbf A} + \\alpha\\mathbf {I})\\mathbf{X}\\mathbf {W}$ is more robust than the GNN layer $f_s = \\bar{\\mathbf  A_s}\\mathbf {X}\\mathbf {W}$ to CM-type attack on a node. The GNN layer f follows the message passing scheme of APPNP (with K=1) and GPRGNN (with K=1, $\\gamma_0=\\alpha$, $\\gamma_1=1-\\alpha$), which indicates that Theorem 3 is applicable to APPNP and GPRGNN under some assumptions. However, it is not clear whether it could work for the heterophily-inspired design since the architectures of ANNPN and GPRGNN are significantly different toi the heterophily-inspired design.\n4.  It would be nice to include APPNP in the experiments since the architecture of APPNP is very close to the GNN layer analyzed in Theorem 3.\n5.  The datasets used in the experiment are small, say, around 2k nodes, and it is not clear whether the results can be extended to large real-world graphs. It would be great to include experiments on larger datasets to validate their theoretical claims,  especially when their claims were made upon specific assumptions. Moreover, the homophily level h of FB100 is 0.531 (> 0.5), which does not meet the definition of heterophilious graphs ($h <<1/ |Y|$) in the paper. Other heterophilious benchmark datasets with lower homophily levels may be more helpful for validating the theoretical claims for heterophilious graphs.\n6.   There is no empirical study for validating the claim of Theorem 2 that the type (homophily or heterophily) of attack on a node for heterophilious graph depends on the node degree.\n\n## Minor comments:\n1. Table 7 in Appendix E.1 shows that GAT and GCN outperform most heterophily-inspired GNNs (e.g. H2GCN, GPRGNN, FAGCN) on the original (clean) FB100 and Snap datasets. Can you give some insights on why GAT and GCN worked better than heterophily-inspired GNNs on these heterophilious graphs?\n", "summary_of_the_paper": "This paper studies the relationship between graph heterophily and robustness of GNNs. The authors claim that effective structural attacks on GNNs for homophilious graphs lead to increased heterophily level, while for heterophilious graphs they alter the homophily level contingent on node degrees. The paper shows that a heterophily-inspired design for GNN, separate aggregators for ego- and neighbor-embeddings, could improve the robustness of several GNN architectures.", "summary_of_the_review": "This paper studies an interesting open problem in deep graph learning. However, it has limited novelty, and theoretical results do not support some of their claims.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "RNXnr8Yr5jU", "reviewer": "Reviewer_kkG8", "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": "Pros:\n- The writing of this paper is very clean and easy to read.\n- The paper focuses on a quite interesting problem, i.e., the connection between the adversarial attack on the graph and the change of heterophily.\nCons:\n- The major concern is the novelty and significance of this paper:\n    1. The main observation comes from previous work (Wu et al. 2019; Jin et al. 2020a) as mentioned in the paper. And the main contribution from the theoretical view, as the authors claimed, is the first formalization of the connection. However, the theory is rather weak as both the graph structure and the used model are simplified, i.e., regular graph with very simple node features plus linear GNN.\n    2. The design principle mentioned in the paper has already been proposed by previous works, e.g., GraphSAGE, and the connection between this principle and the aforementioned theory results is vague.\n\n", "summary_of_the_paper": "This paper investigates the change of the degree of homophily under adversarial perturbation of graphs from both theoretical and empirical points of view. In theory, this paper proves under simplified settings, for homophily graphs, the attack will increase the level of heterophily, and for heterophily graphs, this change will depend on the degree. In practice, this paper advocates a design principle of GNNs that separate aggregators for ego- and neighbor-embeddings.", "summary_of_the_review": "This paper aims to investigate an interesting question about the relationship between robustness and heterophily of graphs, however, the novelty and significance of both theory and empirical results are not clear.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "0q8j9QB16ri", "reviewer": "Reviewer_jMaA", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "In this paper, the authors analyze the relation between GNN robustness against attacks with heterophily and propose a method to improve GNN robustness by separating the aggregators of ego- and neighbor-embeddings. In general, the authors focus on an interesting and novel problem and the paper is of good structure. However, there are some issues the authors need to address.\n\nMy primary concern is with the evaluation. First, no baseline methods on improving GNN robustness or defending attacks are provided. The authors only show the performance gap between before- and after-attack on different GNNs that integrate the proposed technique. However, it is unclear how much the results are significant without comparing the baseline methods. I suggest the authors either add several baselines to compare or justify why no baseline is applicable. Meanwhile, I suggest the authors to compare the GNN models that integrate the proposed technique with the vanilla versions to examine the results without attacking so that the readers can understand how the general performance can be affected by separating the ego-aggregator.\n\nThe novelty of the proposed method also needs to be justified. Using stacked ego-embeddings for prediction has been applied before to solve issues like oversmoothing. I suggest the authors to further justify why the proposed approach is novel and significant.", "summary_of_the_paper": "In this paper, the authors analyze the relation between GNN robustness against attacks with heterophily and propose a method to improve GNN robustness by separating the aggregators of ego- and neighbor-embeddings.", "summary_of_the_review": "Strength:\n+ Focusing on an interesting problem\n+ The paper is of good structure\n\nWeakness:\n- Incompelete evaluation\n- The novelty needs to be further justified", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work studies the relation between graph heterophily and the robustness of GNNs and theoretically shows that effective structural attacks on GNNs for homophilous graphs lead to increased heterophily level, while for heterophils graphs they alter the homophily level contingent on node degrees under some specific assumptions.

Overall, the findings in the paper are interesting and can be useful for other researchers trying to improve GNNs' robustness on homophilic and heterophilic datasets. After the discussion and rebuttal, the main concerns are: 
- while the paper has shown some interesting observations, no new methodology was proposed based on these findings. 
- The authors have attempted to relax assumptions and justified their setup on experiments, however the explanations are still limited. For example, Theorem 1 does not allow attention mechanism, different choices of aggregator, skip-connection, and more GNN layers.
Decision: Reject