{'fraction_non_alphanumeric': 0.045287206496274504, 'fraction_numerical': 0.015130964753131, 'mean_word_length': 4.756641654836747, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 9, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
How does Heterophily Impact the Robustness of Graph Neural Networks? Theoretical Connections and Practical Implications

We bridge two research directions on graph neural networks (GNNs), by formalizing the relation between heterophily of node labels (i.e., connected nodes tend to have dissimilar labels) and the robustness of GNNs to adversarial attacks. Our theoretical and empirical analyses show that for homophilous graph data, impactful structural attacks always lead to reduced homophily, while for heterophilous graph data the change in the homophily level depends on the node degrees. These insights have practical implications for defending against attacks on real-world graphs: we deduce that separate aggregators for ego- and neighbor-embeddings, a design principle which has been identified to significantly improve prediction for heterophilous graph data, can also offer increased robustness to GNNs. Our comprehensive experiments show that GNNs merely adopting this design achieve improved empirical and certifiable robustness compared to the best-performing unvaccinated model. Additionally, combining this design with explicit defense mechanisms against adversarial attacks leads to an improved robustness with up to 18.33% performance increase under attacks 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-Euclidean domains, such as manifolds or graphs [6], 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 counterpartshave a high sensitivity to 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. [52] and Dai et al. [10], has triggered studies that investigated different attack scenarios [24,30,41,42].
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.e., the tendency of nodes with similar features or class labels to connect [35,47]. Such datasets are thus called homophilous (or assortative). While homophilous datasets dominate the study of networks, homophily is not a 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 [1,2,47]. Previous works have thus proposed architectures for heterophilous data.
While previous work has focused on naturally-occurring 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 if 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 attacks of graph structure, focusing on semi-supervised node classification. More specifically, our main contributions are: • 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-inspired Design: We show how the relation between attacks and heterophily can inspire more robust GNNs by arXiv:2106.07767v4 [cs.
LG] 23 Jul 2022 demonstrating that a key architectural feature in handling heterophily, separate aggregators for ego-and neighbor-embeddings, also improves the robustness of GNNs against attacks ( §3.2). • Extensive Empirical Analysis: We show the effectiveness of the heterophilous design in improving 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 design, which we refer to as heterophily-adjusted GNNs, to non-adjusted models, including state-of-the-art models designed with robustness in mind. We find that heterophily-adjusted GNNs are up to 11.1 times more certifiably robust and have stronger performance under attacks by up to 40.00% compared to non-adjusted, standard models. Moreover, this design can be combined with existing vaccination mechanisms, yielding up to 18.33% higher accuracy under attacks than the best non-adjusted vaccinated model. Our code is available at https://github.com/GemsLab/HeteRobust.

NOTATION AND PRELIMINARIES
Let G = (V, E, X) be a simple graph with node set V, edge set E and node attributes X. The one-hop neighborhood ( ) = { : ( , ) ∈ E} of a node ∈ V is the set of all nodes directly adjacent to ; the -hop neighborhood of ∈ V is the set of nodes reachable by a shortest path of length . We represent the graph G algebraically by an adjacency matrix A ∈ {0, 1} | V |× | V | and node feature matrix X ∈ R | V |× . We use A s = A + I to denote the adjacency matrix with self-loops added, and denote the corresponding row-stochastic matrices asĀ = D −1 A andĀ s = D −1 s A s , respectively, where D is a diagonal matrix with D = A (D s is defined analogously). We further assume that there exists a vector y, which contains a unique class label for each node . Given a training set T V = {( 1 , 1 ), ( 2 , 2 ), ...} of labeled nodes, the goal of semi-supervised node classification is to learn a mapping ℓ : 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 and continually updated by layers of learnable transformations. These layers first aggregate representations over neighboring nodes ( ) and then update the current representation via an encoder ENC. For prevailing GNN models like GCN [18] and GAT [40], each layer can be formalized as r ( ) = ENC AGGR r ( −1) : ∈ ( ) ∪ { } , where AGGR is the mean function weighted by node degrees (GCN) or an attention mechanism (GAT), and ENC is a learnable (nonlinear) mapping. Adversarial attacks on graphs. Given a graph G = (V, E, X) and a GNN that processes G, an adversarial attacker tries to create a perturbed graph G ′ = (V, E ′ , X) with a modified edge-set E ′ such that the performance of the GNN is maximally degraded. The information available to the attacker can vary under different scenarios [17,37]. Here, we follow the gray-box formalization by [52], where the attacker knows the training set T V , but not the trained GNN . The attacker thus considers a surrogate GNN and picks perturbations that maximize an attack loss L atk [49,52], assuming that attacks to the surrogate model are transferable to the attacked GNN. For node classification, the attack loss L atk quantifies how the predictions z ∈ [0, 1] | Y | made by the GNN differ from the true labels y. For a targeted attack of node with class label ∈ Y, we adopt the negative classification margin (CM-type) [42,52]: L atk = −Δ = −(z , − max ≠ z , ). The attacker usually has additional constraints, such as a limit on the size of the perturbations allowed [49,52]. Taxonomy of attacks. We follow the taxonomy of attacks introduced in [17,37]. For node classification, the attacker may aim to change the classification of a specific node ∈ V (targeted attack), or to decrease the overall classification accuracy (untargeted attack). Attacks can also happen at different stages of the training process: we refer to attacks introduced before training as (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 a graph contributing to its overall level of homophily/heterophily as follows: Definition 1 (Homo/Heterophilous path and edge). Ahop homophilous path from node to is a length-path between endpoint nodes with the same class label = . Otherwise, the path is called heterophilous. A homophilous or heterophilous edge is a special case with = 1.
When the edges in a graph are wired randomly, independent to the node labels, the expectation for ℎ is ℎ = 1/|Y| for balanced classes [27]. For simplicity, we informally refer to graphs with homophily ratio ℎ ≫ 1/|Y| as homophilous graphs (which have been the focus in most prior works), graphs with homophily ratio ℎ ≪ 1/|Y| as heterophilous graphs, and graphs with homophily ratio ℎ ≈ 1/|Y| as weakly heterophilous graphs.

RELATION BETWEEN GRAPH HETEROPHILY & MODEL ROBUSTNESS
In this section, we first show theoretical results on the relation between adversarial structural attacks and the change in the homophily level of the underlying graphs. Though empirical analyses from previous works have suggested this relation on homophilous graphs [17,41], to our knowledge, we are the first to 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.

How Do Structural Attacks Change Homophily in Graphs?
Homophilous graphs: structural attacks are mostly heterophilous attacks. Our first result shows that, for homophilous data, effective structural attacks on GNNs (as measured by loss L atk ) always result in a reduced level of homophily where either new heterophilous connections are added or existing homophilous connections are removed. It also states that direct perturbations on 1-hop neighbors of the target nodes are more effective than indirect perturbations (influencer attacks [52]) on multi-hop neighbors. For simplicity, akin to previous works [49,52] we establish our results for targeted evasion (post-training) attacks in a stylized learning setup with a linear GNN. However, our findings generalize to more general setups on real-world datasets as we show in our experiments ( §5.1). In the theorems below, we use the notion of gambit node: node is called a gambit if a perturbation that targets node ∈ V adjusts the connectivity of node ∈ V.
Theorem 1. Let G = (V, E, X) be a self-loop-free graph with adjacency matrix A and node features x = · onehot( ) + 1− |Y| · 1 for each node , where 1 is an all-1 vector, and is a parameter that regulates the signal to noise ratio. Assume that a fraction ℎ of each node's neighbors belong to the same class, while a fraction 1−ℎ |Y|−1 belongs uniformly to any other class. Consider a 2-layer linear GNN (2) (A, X) =Ā 2 s XW trained on a training set T V ⊆ D V , with at least one node from each class ∈ Y, and degree for all nodes with a distance less than 2 to any ∈ D V . For a unit structural perturbation that involves a target node ∈ D V , and a correctly classified gambit node with degree , the following statements hold if ℎ ≥ 1 |Y| : (1) the attack loss L atk ( §2) of the target increases only for actions increasing heterophily, i.e., when removing a homophilous edge or path, or adding a heterophilous edge or path to node ; (2) direct perturbations on edges (or 1-hop paths) incident to the target node lead to greater increase in L atk than indirect perturbations on multi-hop paths to target node . We give the proof in App. A. Intuitively, the relative inability of existing GNNs to make full use of heterophilous data [35,47] can be exploited by inserting heterophilous connections in graphs where homophilous ones are expected. Though the theorem shows that effective 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 [31]. 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 and the gambit node of the attack. Specifically, if the degree of either node is low, attacks increasing the heterophily are still effective; however, if the degrees and 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 2. Under the setup of Thm. 1, for a unit perturbation that involves a target node with degree , and a correctly classified gambit node with degree , the following statements hold: (1) (Low-degree target node) if 0 < ≤ |Y| − 2, for any ≥ 0 and ℎ ∈ [0, 1], the attack loss L atk ( §2) of increases only under actions increasing heterophily in the graph; (2) (High-degree target node) if > |Y| − 2, conditioning on the degree of the gambit node: − | Y |+2 , for any ℎ ∈ [0, 1], the attack loss L atk ( §2) of increases only under actions increasing heterophily in the graph; |Y | , L atk ( §2) of increases only under actions reducing heterophily. In the statements above, the actions increasing heterophily include removing a homophilous edge or adding a heterophilous edge to node , and the actions reducing heterophily include adding a homophilous edge or removing a 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 interpretation 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.

Boosting Robustness with A Simple Heterophilous 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-separate aggregators for ego-and neighborembeddings-can also boost the robustness of GNNs by enabling them to better cope with adversarial changes in heterophily.
Separate aggregators for ego-and neighbor-embeddings. This design uses separate GNN aggregators for ego-embedding r and neighbor-embeddings {r : ∈ ( )}. Formally, the representation learned for node in the -th layer is: , ..., r (0) ), AGGR2( {r where AGGR1 and AGGR2 are separate aggregators, such as averaging functions (GCN), attention mechanisms (GAT), or other pooling mechanisms [15]. This design has been utilized in existing GNN models (we show examples later in this section), and has been shown to significantly boost the representation power of GNNs under natural heterophily [47]. The ego-aggregator AGGR1 may also introduce skip connections [43] to the ego-embeddings aggregated in previous layers as shown in Eq. (1), which is another design that further improves the representation power under heterophily [47]. Intuition.
The key design changes, as compared to the GCN formulation in §2, allow for the ego-embedding r to be aggregated and weighted separately from the neighbor-embeddings {r : ∈ ( )}, 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 are 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 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. (1 − )Ā + I XW, which mixes the ego-and neighbor-embedding linearly under a predefined weight ∈ [0, 1]. Then, for ℎ > 1/|Y|, > 1/(1 + ), and a unit perturbation increasing L atk as in Thm. 1, outputs of layer lead to a strictly smaller increase in L atk than .
We provide the proof in App. A; note that for = 1/(1 + ), the two layers are the same: (A, X; ) = (A, X). Theorem 3 shows that an increase to the weights of ego-embedding (manually or through training) improves the robustness of the GNN for a homophily ratio ℎ > 1/|Y|. Though aggregators and encoders are stylized in this simple instantiation of the design in the theorem, the empirical analysis in §5.2 confirms that GNNs with more advanced aggregators and encoders, which we will discuss next, also benefit from separate aggregators. Specifically, we find that such GNNs outperform methods without this design by up to 40.00% and 48.88% on homophilous and heterophilous graphs, respectively, while performing comparably on clean datasets. Instantiations of the design on GNNs. We demonstrate how the heterophilous design outlined in Eq. (1) is instantiated in various GNN models, which are used in our empirical evaluation in §5. In particular, we highlight how these GNN architectures allow separate aggregations of the ego-and neighbor-embeddings. , r , ..., r ( ) ), where r , , and AGGR2 is the mean function.
• GPR-GNN [8] embeds each node feature vector separately with a fully connected layer to compute R : as in the original paper), similar to H 2 GCN, and then updates each node's hidden representations through a weighted sum of all -th hop layers around the ego-node, where ∈ (0, 1, ..., ). By interpreting the summation as the ENC operation, AGGR1(·) = 0 R (0) , and AGGR2(·) = =1Ã sym R ( −1) , where denotes the weights associated with each -hop ego network, the aggregation of the ego-and neighbor-embeddings is decoupled.
• FAGCN [2] follows a similar update function to GPR-GNN with in the original paper) represents the nonlinear ego-embedding and is a constant measuring the ratio of low and high frequency components. The heterophilous design can similarly be recovered by interpreting the sum as the ENC operation, AGGR1(·) = r (0) as a weighted skip connection to the ego-embedding of features, and the weighted sum of embeddings within the neighborhood ( ) of node ∈ V as AGGR2(·).
• APPNP [19] first generates predictions R : as in the original paper) of each node based on its own feature, then updates the predictions through power iterations of Personalized PageRank. More specifically, the -th iteration step is formulated as R ( ) = (1 − )Ã sym R ( −1) + R (0) . The heterophilous design can be recovered by letting AGGR1(·) = R (0) as a skip connection to the initial prediction, AGGR2(·) =Ã sym R ( −1) , and the summation weighted by as the ENC operation.

RELATED WORK
Adversarial attacks and defense strategies for graphs. Since Nettack [52] and RL-S2V [10] first demonstrated the vulnerabilities of GNNs against adversarial perturbations, a variety of attack strategies under different scenarios have been proposed, including adversarial attacks on the graph structure [3,7,10,24,42], node features [30,38], or combinations of both [41,49,52]. On the defense side, various techniques for improving the GNN robustness against adversarial attacks have been proposed, including: adversarial training [4,42,49]; RGCN [46], which adopts Gaussian-based embeddings and a variance-based attention mechanism; low-rank approximation of graph adjacency [12] against Nettack [52]; Pro-GNN [16], which estimates the unperturbed graph structure in training with the assumptions of low-rank, sparsity, and homophily of node features; GCN-Jaccard [41] and GNNGuard [45], which assume homophily of features (or structural embeddings) and train GNN models on a pruned graph with only strong homophilous links; and Soft Medoid [13], an aggregation 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 [4,50,51], including approaches based on model-agnostic randomized smoothing [5,9,21]. Interested readers can refer to the recent surveys [17,37] for a comprehensive review. GNNs & Heterophily. Recent works [28,31,35,47] have shown that heterophilous datasets can lead to significant performance loss for popular GNN architectures (e.g., GCN [18], GAT [40]). This issue is also known in classical semi-supervised learning [34]. To address this issue, several GNN designs for handling heterophilous connections have been proposed [1,2,11,25,35,47,48]. Yan et al. [44] recently discussed the connection between heterophily and oversmoothing for GNNs, and designs to address both issues; [29] studied how locally-occuring heterophily affects fairness of GNNs. However, the formal connection between heterophily and robustness of GNNs has received little attention. Here we focus on a simple yet powerful design that significantly improves performance under heterophily [47], and can be readily incorporated into GNNs.

EMPIRICAL EVALUATION
Our analysis seeks to answer the following questions: (Q1) Does our theoretical analysis on the relations between adversarial attacks and changes in heterophily level generalize to real-world datasets? (Q2) Do heterophily-adjusted GNNs, i.e., models with separate aggregators for ego-and neighbor-embeddings, show improved robustness against state-of-the-art attacks? (Q3) Does the identified design improve the certifiable robustness of GNNs?
First, we describe the experimental setup and datasets that we use to answer the above questions.
Attack Setup. We consider both targeted and untargeted attacks ( §2), generated by Nettack [52] and Metattack [49], respectively. For each attack method, we consider poison (pre-training) and evasion (post-training) attacks, yielding 4 attack 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. 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 [52]: the approach in [52] only selects nodes that are correctly classified by GCN [18] on clean data; this introduces unfair advantage towards GCN, especially on heterophilous datasets where GCN can exhibit significantly inferior accuracy to models like GraphSAGE [47]. For the experiments in §5.1, we use a budget of 1 perturbation per target node to match the setup of our theorems; for the benchmark study in §5.2, we use an attack budget equal to a 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 [49]. GNN Models. To show the effectiveness of our identified design, we evaluate four groups of models against adversarial attacks: (1) Baseline models without any vaccination, including some of the most popular methods: GCN [18], GAT [40], and the graphagnostic multilayer perceptron (MLP) which relies only on node features; (2) State-of-the-art "vaccinated" baselines designed with robustness in mind: ProGNN [16], GNNGuard [45], GCN-SVD [12] and GCN-SMGDC, which adopts the Soft Medoid aggregator [13] and GDC [20] on GCN [18] architecture; (3) Models with the heterophilous design only: GraphSAGE [15], H 2 GCN [47], CPGNN [48], GPR-GNN [8] FAGCN [2] and APPNP [19]; we discussed how these models instantiate this design in §3.2; (4) Models with both the heterophilous design and explicit robustness-enhancing mechanisms, where we adopt two existing mechanisms: (i) SVD-based lowrank approxmiation [12] (H 2 GCN-SVD and GraphSAGE-SVD), and (ii) Soft Medoid aggregator [13] with GDC [20] (H 2 GCN-SMGDC and GraphSAGE-SMGDC). We combine both these mechanisms with heterophily-adjusted GNNs instead of non-adjusted models (e.g., GCN)-detailed formulations are given on our repository. We set the number of layers as 2 and the size of hidden units per layer as 64 for all models to ensure a fair comparison between different architectures and designs. We provide more implementation details and hyperparameter settings on our repository (App. §B).
Datasets & Evaluation Setup. We consider three widely-used citation networks [33,36] with strong homophily-Cora [32], Pubmed, and Citeseer-along with one weakly and one strongly heterophilous graph, introduced by Lim et al. [27]: FB100 [39] and Snap Patents [22,23]. We report summary statistics in Table 1, and provide more details on our repository. For computational tractability, we subsample the Snap Patents data via snowball sampling [14], where we  [13,16]. We follow the evaluation procedure of [16,52] to split the nodes of each dataset into training (10%), validation (10%) and test (80%) data, and determine the model parameters on training and validation splits. We report the average performance and standard deviation on the 3 sets of generated perturbations. For targeted attacks with Nettack, we report the classification accuracy on the target nodes; for untargeted attacks with Metattack, we report it over the whole test data. Robustness Certificates. We adopt randomized smoothing for GNNs [5] to evaluate the certifiable robustness, with parameter choices detailed in our GitHub repository. We only consider structural perturbations in the randomization scheme. Following Geisler et al. [13], we measure the certifiable robustness of GNN models with the accumulated certifications (AC) and the average maximum certifiable radii for edge additions (¯) and deletions (¯) over all correctly predicted nodes. More specifically, AC is defined as is 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 ( , ). 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 (0, 0). We report the average and standard deviation of each statistic over the 3 different training, validation and test splits. Hardware Specifications. We use a workstation with a 12-core AMD Ryzen 9 3900X CPU, 64GB RAM, and a Quadro P6000 GPU with 24 GB GPU Memory. Code and Additional Details. Code and additional details on the setups and results are available on GitHub repository: https: //github.com/GemsLab/HeteRobust.

(Q1) Structural Attacks are Mostly Heterophilous: Empirical Validation
To show that our theoretical analysis in §3.1 generalizes to more complex settings beyond the assumptions 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 1 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 of Nettack (i.e., GCN) as described in §5. To validate the dependency between the degrees of the target/gambit nodes and the changes of heterophily predicted by Thm. 2, we also show the scatter plots of node degrees in Fig. 1.  Figure 1: Scatter plots of the degrees of the target nodes (xaxis) and gambit nodes (y-axis) involved in the targeted attacks ( §5.1). Attacks tend to leverage gambit nodes with low degrees, which makes attacks increasing heterophily effective for heterophilous graphs following Thm. 2.
Homophilous Networks. For the strongly homophilous Cora, Pubmed and Citeseer graphs, all changes introduced by effective attacks in the graph structure follow the conclusion of Thm. 1: they reduce homophily (increase heterophily) by adding heterophilous edges or removing homophilous edges. These results show that despite the simplified analysis, the takeaway of Thm. 1 can be generalized to real-world datasets. In addition, the attacks mostly introduce, rather than prune, edges, suggesting that attacks adding outlier edges to the graph are more powerful than attacks removing informative existing edges. These observations in our experiments are consistent with the observations from previous works [13,17]. Heterophilous Networks. For heterophilous graphs FB100 (ℎ ≈ 1/|Y|) and Snap (ℎ < 1/|Y|), Fig. 1 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 ∈ V with a different ground-truth class label ≠ to the target nodes ∈ V; attacks leveraging incorrectly classified gambit nodes are always connecting node with a different predicted class labelˆ≠ˆ= to the target node , even though some gambit nodes have the same ground-truth class label = ≠ˆas the target nodes. These results validate the conclusion of Thm. 2 on correctly classified gambit nodes, and demonstrate its generalizability under the heterophily definition based on predicted class labels. Note that the predicted class labelsˆfor each node ∈ V are based on GCN, which is the surrogate GNN used by Nettack.

(Q2) Benchmark Study of GNN Models:
Heterophilous Design Leads to Improved Empirical Robustness To answer (Q2) on whether heterophily-adjusted GNN models show improved performance against state-of-the-art attacks, we conduct a comprehensive benchmark study. We consider all four categories of GNN models mentioned in §5, and evaluate their robustness against both targeted and untargeted attacks. We report the hyperparameters for each method on our repository (App. §B.3). Table 3 shows the performance of each method under poison (pre-training) attacks and on clean (unperturbed) data, and Fig. 2 visualizes the corresponding performance changes relative to the clean datasets. For conciseness, we report additional results on Pubmed in Table 5, and under evasion (post-training) attacks on our GitHub repository (Table 7 and Table 3 (left) shows that GraphSAGE-SVD and H 2 GCN-SVD, which combine our identified design with a low-rank vaccination approach adopted in GCN-SVD [12], outperform stateof-the-art vaccinated methods across all datasets by up to 13.34% in homophilous settings and 18.33% in heterophilous settings. Furthermore, GraphSAGE-SMGDC and H 2 GCN-SMGDC, which combine our design with existing vaccinations based on Soft Medoid [13] and GDC [20], show better performance against attacks in all datasets compared to GCN-SMGDC, the corresponding baseline without our design, with up to 19.44% improvement on homophilous settings and 30.55% improvement on heterophilous settings. In summary, these observations show that the heterophilous design improves the robustness of GNNs alongside existing vaccination mechanisms.
Methods merely employing the identified design also show significantly improved robustness, though there are differences in the amount of robustness improvement due to architectural differences. Specifically, these methods outperform the best unvaccinated method (GAT) on all datasets by up to 33.75% in average, despite having mostly comparable performance on clean datasets; methods like APPNP and CPGNN also show comparable or even better robustness than state-of-the-art vaccinated GNNs. These observations also apply to the larger Pubmed dataset in Table 5. We also note that the graph-agnostic MLP, which is immune to structural attacks, outperforms all GNNs against attacks on Citeseer and Snap; this shows the challenges in defending against targeted attacks and calls for more effective defense strategies upon our discoveries.
2 ○ Evasion attacks. Under evasion attacks (detailed results are reported in App. Table 7 on our repository), we observe similar trends Table 3: Benchmark study: mean accuracy ± stdev against poison attacks, with accuracy on clean datasets in gray for reference. Accuracy is reported on target nodes for Nettack, and on full test splits for Metattack. Best GNN performance against attacks is highlighted in blue per dataset, and in gray per model group. MLP is immune to structural attacks and not considered as a GNN model. Accuracy against evasion attacks are listed on our GitHub repository (App. §C.1), and the setups in §5. Additional results on Pubmed are listed in App. Table 5. GNNs merely adopting this design achieve up to 40.00% improvement in accuracy against Nettack compared to the best-performing unvaccinated model (GCN). Additionally, methods combining this design alongside explicit defense mechanisms (e.g., GraphSAGE-SVD) achieve further robustness improvement to the corresponding base mechanism without the design (e.g., GCN-SVD), and outperform the best vaccinated baseline by up to 18 Table 3. As expected, MLP is not influenced by the adversarial structural attacks.
as in poison attacks: GraphSAGE-SVD and H 2 GCN-SVD are up to 20.55% more accurate than the GCN-SVD, the corresponding baseline without the heterophilous design, and GraphSAGE-SMGDC and H 2 GCN-SMGDC outperform GCN-SMGDC by up to 19.44%. Methods featuring the identified design alone achieve up to 38.89% gain in average performance against the best unvaccinated baseline, which we also observe on Pubmed. We note that two baselines, GN-NGuard and ProGNN, are designed specifically to defend against poison attacks, and are not capable of addressing evasion attacks.
Untargeted attacks by Metattack. 1 ○ Poison attacks. We also test the robustness of each method against untargeted attacks. Table 3 (right) shows the performance under poison attacks. Though our theoretical analysis in §3 focuses on the effect of the heterophilous design under targeted attacks, we observe similar improvements in robustness against untargeted attacks in the poison setup. GNNs with the identified design show mostly improved robustness compared to unvaccinated 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 up to 21.04% improvement in accuracy compared to GCN-SVD, which uses only low-rank approximation. Models combining the design with Soft Medoid and GDC show up to 37.29% improvement in accuracy compared to GCN-SMGDC. We also note that the most robust method for each dataset is among the ones with the identified design. These results again support the effectiveness of the heterophilous design in boosting the robustness of GNNs in addition to existing vaccination mechanisms.
2 ○ Evasion attacks. We present the performance under evasion attacks on our GitHub repository. Unlike the poison attacks, the evasion setup only leads to a slight decrease in average accuracy of less than 2% for most models. Moreover, there appears to be no clearly increased robustness for vaccinated models (with the identified design or other vaccination machanisms) 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. Table 4: Accumulated certifications (AC), average certifiable radii (¯and¯) and accuracy of GNNs with randomized smoothing enabled (i.e., ( (s))) on the test splits of the clean datasets, with ramdomization schemes allowing both addition and deletion (i.e., + = 0.001, − = 0.4), and additional only (i.e., + = 0.001, − = 0). 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. We provide results with the deletion only scheme on our repository (App. §C.2). APPNP, with the identified design, improves the accumulated certification (AC) by up to 5.3x on homophilous datasets and 10.1x on heterophilous ones compared to the best performing baseline without the design.

(Q3) Heterophily-adjusted GNNs are Certifiably More Robust
It is worth noting that robustness against specific attacks such as 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 a certain radius cannot change a model's predictions. Complementary to our evaluation on empirical robustness, we further demonstrate that heterophily-adjusted GNNs featuring our identified design are certifiably more robust than methods without it, thus answering (Q3). For GNN models and datasets, we exclude the larger Pubmed dataset and models that learn to rewrite the graph structure through the training process, or require recalculation of the low-rank approximation or inverse of matrices (as used by GDC [20]) for every randomized perturbation, as we find that sampling on these setups is computationally challenging. We use the same hyperparameters as the benchmark study in §5.2. Table 4 shows multiple metrics of certifiable robustness of each GNN model under edge randomization schemes allowing both addition and deletion, and allowing addition only; we additionally report results under a scheme allowing only deletion on our GitHub repository. For the scheme allowing both addition and deletion, we observe that all heterophily-adjusted 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 to 5.3 times relative improvement in accumulated certification. On heterophilous datasets (FB100 and Snap), they outperform the baselines by a factor of 11.1. In the more challenging case with the addition only scheme, methods with the design also show up to 2.9 times relative increase in AC on the homophilous datasets and 11.0 times relative increase in AC on the heterophilous datasets compared to the baselines. For the deletion only scheme, we find that unvaccinated models like GCN already have decent certifiable robustness in this scenario, commensurating with our discussions in §5.1 that deletions create less severe perturbations. Overall, our results show that models featuring our identified design achieve significantly improved certifiable robustness compared to models lacking this design. However, like in our empirical robustness evaluation, architectural differences lead to some variability of robustness; the results also show tradeoffs between accuracy and robustness. We also observe that the rankings under certifiable and empirical robustness are different, as in the previous results from [13]; we discuss more in our repository.

CONCLUSION
We formalized the relation between heterophily and adversarial structural attacks, and showed theoretically and empirically that effective attacks gravitate towards increasing heterophily in both homophilous and heterophilous graphs by leveraging low-degree (gambit) nodes. Using these insights, we showed that a key design addressing heterophily, namely separate aggregators for ego-and neighbor-embeddings, can lead to competitive improvement on empirical and certifiable robustness, with only small influence on clean performance. Finally, we compared the design with state-ofthe-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. We hope our analysis can inspire more effective defense strategies against adversarial attacks, especially designs that improve robustness by better addressing heterophily, such as heterophily in node features, or locally-occuring heterophily in homophilous graphs.

SUPPLEMENTARY MATERIAL ON REPRODUCIBILITY
For reproducibility, we describe main experimental setups at the beginning of §5, including the attack configurations, the depth and hidden unit size for GNNs, ratios for training, validation and test splits, and hardware specifications. We provide code and datasets on GitHub repository: https://github.com/GemsLab/HeteRobust, where we also include additional details on the setups and results, including the implementations and detailed hyperparameters for GNNs and randomized smoothing ( §B), and additional results for evasion attacks ( §C.1) and certifiable robustness ( §C.2). In addition, we report results for GNN models against Nettack on the larger Pubmed dataset in Table 5, with more details in §C.1; GCN-SVD and SMGDC-based vaccinations run out of memory on Pubmed.

A PROOFS AND DISCUSSIONS OF THEOREMS
For simplicity of mathematical expressions, we use C ( , ) to refer a matrix where all elements in the -th column are , with all remaining elements (not in the -th column) as ; we use c ( , ) when the matrix is a row vector. We further denote C * ( , ) as a circulant matrix with all diagonal elements as and all off-diagonal elements as , and B ( , ) as block matrix of the following form: T Proof for Thm. 1. We give the proof in three parts: first, we analyze the training process of the GNN (2) (A, X) =Ā 2 s XW on clean data and analytically derive the optimal weight matrix W * in a stylized learning setup; then, we construct a targeted evasion attack and calculate the attack loss for a unit structural attack; last, we summarize and validate the statements in the theorem. s X] T ,: = C * ( 1 , 1 ). Note that [Ā 2 s X] T ,: is a circulant matrix, and therefore its inverse exists. Using the Sherman-Morrison formula, we have s X] T ,: Now, let W * = [Ā 2 s X] T ,: Attack loss under evasion attacks. Now consider an arbitrary target node ∈ D V with class label ∈ Y, and a unit structural perturbation leveraging gambit node ∈ V with degree that affects the predictions z of node made by GNN (2) . Without loss of generality, we assume node has = 1. As (2) contains 2 GNN layers with each layer aggregating feature vectors within neighborhood ( ) of each node , the perturbation must take place in the direct (1-hop) neighborhood ( ) or 2-hop neighborhood 2 ( ) to affect the predictions z . For the unit perturbation, the attacker can add or remove a homophilous edge or path between nodes and , which we denote as 1 ( 1 = 1 for addition and 1 = −1 for removal); alternatively, the attacker can add or remove a heterophilous edge or path between nodes and , which we denote as 2 = ±1 analogously. We denote the perturbed graph adjacency matrix asĀ ′ s , and z ′ = [Ā ′2 s X] ,: W * 1 ○ Unit perturbation in direct neighborhood ( ). We first consider a unit perturbation in the direct (1-hop) neighborhood ( ) of node . For simplicity of derivation, we assume that the perturbation does not change the row-stochastic normalization ofĀ s , and only affects the aggregated feature vectors of the target node .
In s X] ,: by W * , we can get the predictions z ′ after perturbations; we omit the analytical expression of z ′ here due to its complexity.
In the case of 1 = 0 and 2 = ±1, following a similar derivation to that in the previous case, we can compute the change in the CM-type attack loss before and after attack as Solving the same system of inequalities as in the previous case for 2 , we have 2 = − 1 , where 1 is bounded by Eq. (4). Note that the above solution is again not applicable when ℎ = − | Y |+1 | Y | , and we always have with W * , we can get the predictions z ′ after perturbations. Following a similar derivation as before, we can get the change in the CM-type attack loss before and after attack as Solving for 1 as in previous cases, we get the valid range of 1 as Note that the above solution is not applicable when ℎ = −|Y |+1 |Y | , in which case (ℎ|Y| − 1) + |Y| − 1 = 0 and the solution of optimal weight matrix W * = [Ā 2 s X] T ,: −1 is undefined.
For the case 1 = 0 and 2 = ±1, following a similar derivation to that in the previous case, we can compute the change in the CM-type attack loss before and after attack as Solving the same system of inequalities as in the previous cases for 2 , we have 2 = − 1 , where 1 is bounded by Eq. (7). Note that the above solution is again not applicable when ℎ = − | Y |+1 | Y | , and we always have < 0 when |Y| ≥ 2. Summary and validation of theorem statements. Based on our discussions, we validate our statements in the theorem next.
1 ○ From Eq. (4), (7), we observe that for both direct attacks in 1hop neighborhood ( ) and indirect attacks in 2-hop neighborhood 2 ( ), when ℎ ≥ 1 | Y | , the attack loss increases only if 1 < 0 (i.e., removal of a homophilous edge or path to node ), or if 2 > 0 (i.e., addition of a heterophilous edge or path to node ). We first derive the optimal weight matrix W * in a stylized learning setup as in Proof A. Following a similar process, for this GNN layer we have . Now as in Proof for Thm. 1, we consider an arbitrary target node ∈ D V , and a unit structural perturbation leveraging gambit node ∈ V with degree that affects the predictions z of node made by layer (A, X; ). Note that we only discuss the case of direct structural perturbation to the 1-hop neighborhood ( ) of target node , as indirect perturbations do not affect the predictions z for node produced by a single GNN layer. Following a similar derivation as in Proof for Thm. 1, in the case of 1 = ±1 and 2 = 0, or 1 = 0 and 2 = ±1, the change in the CM-type attack loss ΔL CM atk for GNN layer (A, X; ) considering both 1 and 2 is Layer (A, X) =Ā s XW. This formulation is a special case of the previously discussed (A, X; ) formulation when = 1 1+ . We denote the change in the attack loss for this layer as ΔL CM,fs atk . Comparison of increase in attack loss ΔL CM atk . Solving the following system of inequalities for variable under constraints ΔL CM,fs atk > ΔL CM,f atk > 0, , ℎ ∈ [0, 1], |Y| ≥ 2, , |Y| ∈ Z + and 1 , 2 ∈ {−1, 0, 1}, we get the valid range of as |Y| and 0 < < 1−|Y| ℎ|Y|−1 and 1 < 2 0 ≤ < 1 +1 , when 0 ≤ ℎ < 1 |Y| and > 1−|Y| ℎ|Y|−1 and 1 > 2 1 +1 < < 1, when 1 |Y| ≤ ℎ ≤ 1 and 1 < 2 .
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 [12].
• Variant (I): Since the original authors' implementation is not publicly available, we consider the implementation provided in Deep-Robust [26] as variant (I): it first calculates the rank-approximationÃ of A, and then generates the preprocessed adjacency matrix , which is then processed by a GCN [18]. However, as the identity matrix I is added intoÃ after the low-rank approximation, the diagonal elements of the resultingÂ s 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 a result, this order of applying the preprocessing and low-rank approximation inadvertently adopts Design 1 which we identified; we have shown in Theorem 3 that even merely increasing the weights for the ego-embedding in the linear combination ENC in Eq. (1) can lead to reduced attack loss L atk under structural perturbations.
• 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Ã s to generate the preprocessedÂ s 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 = 5, the average magnitude of the diagonal elements of the resultingÂ s 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-diagonal elements.

B.2 Combining Heterophilous Design with Explicit Robustness-Enhancing Mechanisms
In this section, we provide more details on how we incorporate the low-rank approximation vaccination into the formulations of H 2 GCN [47] and GraphSAGE [15] in order to form the hybrid methods, H 2 GCN-SVD and GraphSAGE-SVD. H 2 GCN-SVD and H 2 GCN-SMGDC. From [47], each layer in the neighborhood aggregation stage of H 2 GCN is algebraically formulated as whereÂ = D −1/2 AD −1/2 is the symmetrically normalized adjacency matrix without self-loops;Â 2 = D −1/2 2 is the symmetrically normalized 2-hop graph adjacency matrix A 2 ∈ {0, 1} | V |×|V | , with [A 2 ] , = 1 if is in the 2-hop neighborhood 2 ( ) of node ; R ( ) are the node representations after the -th layer, and CONCAT is the column-wise concatenation function. For H 2 GCN-SVD, we replaceÂ andÂ 2 in Eq. (11) respectively with the corresponding low-rank approximated versionsÃ andÃ 2 , which are both postprocessed to be symmetrically normalized; For H 2 GCN-SMGDC, we replaceÂ andÂ 2 respectively with the corresponding GDC-preprocessed versions, and the aggregationsÂ 2 R ( −1) andÂR ( −1) in the 1-hop and 2-hop neighborhoods are calculated with the Soft Medoid aggregators instead. We give links to the GDC [20] and Soft Medoid [13] implementations that we used in our empirical evaluations in §B.1. GraphSAGE-SVD and GraphSAGE-SMGDC. From [15], each layer in GraphSAGE can be algebraically formulated as whereĀ is the row-stochastic graph adjacency matrix without self-loops; R ( ) are the node representations after the -th layer; CONCAT is the column-wise concatenation function; W ( ) is the learnable weight matrix for the -th layer, and is the non-linear activation function (ReLU). For GraphSAGE-SVD, we replaceĀ in Eq. (12) with the low-rank approximation of the adjacency matrixÃ, postprocessed by row-stochastic normalization; For GraphSAGE-SMGDC, similar to H 2 GCN-SMGDC, we replaceĀ with the corresponding GDC-preprocessed versions, and the aggregationĀR ( −1) is derived with the Soft Medoid aggregator. Note that we do not enable the neighborhood sampling function for the GraphSAGE and GraphSAGE-SVD models tested in this work, as noted in Appendix B.3.
• Heterophilous Datasets: FB100 [39] is a set of 100 university friendship network snapshots from Facebook in 2005 [27], from which we use one network. Each node is labeled with the reported gender, and the features encode education and accommodation. Data is sent to the original authors [27] 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 is found within the data. Snap Patents [22,23] 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 3 . Neither personally identifiable information nor offensive content is identified when we manually inspect the dataset. • Homophilous Datasets: Cora [32,33,36], Citeseer [33,36] and Pubmed [33,36] 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 is identified when we manually inspect both datasets.
Downsampling. For better computational tractability, we sample a subset of the Snap Patents data using a snowball sampling approach [14], where a random 20% of the neighbors for each traversed node are kept. We provide the pseudocode for the downsampling process in Algorithm 1.

Algorithm 1: Downsampling Algorithm For Snap Patents
Input: Graph to sample Number of nodes to sample Sampling ratio Output: Downsampled graph ′ 1 initialization /* Initialize a queue bfs quene for Breadth First Search, and a list nodes sampled for storing sampled nodes */ 2 bfs quene ← Queue() 3 nodes sampled ← List() /* Start BFS with a random node from the largest connected component in G; Random(array, n) returns n elements from an array with equal probability without replacement */ 4 node starting ← Random(LargestConnectedComponent( ), 1) 5 push node starting into bfs quene 6 while Length(nodes sampled ) < do 7 node ← bfs quene .pop() 8 neighbors ← one hop neighbors of node 9 neighbors drawn ← Random(neighbors, × Length(neighbors)) 10 for neighbor ∈ neighbors drawn do 11 if neighbor ∉ nodes sampled then 12 append neighbor to nodes sampled  Table 7: Detailed classification accuracy (and standard deviation) of each method for the target nodes attacked by Nettack, calculated across different sets of perturbation. Best GNN performance against attacks is highlighted in blue per dataset, and in gray per model group. OOM denotes experiment settings that run out of memory. MLP is immune to structural attacks and not considered as a GNN model. randomized smoothed models ( (s)) to measure certifiable robustness, in empirical robustness we are evaluating on the robustness of the base models ( ), which may differ from the robustness of the randomized smoothed models. Lastly, it is worth noting that the lack of certification for a model within certain radius does not imply a vulnerability to 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 perspectives to evaluations empirical robustness, at the current stage it cannot replace the evaluations on empirical robustness, and the relation between certifiable and empirical robustness remains as a question for future works.

C.4 Complexity and Runtime of Heterophilous Vaccination
Another benefit of adopting heterophily-inspired design for boosting robustness of GNNs is their smaller computational overhead compared to existing vaccination mechanisms, especially vaccinations based on low-rank approximation. As our identified design can be applied as simple architectural changes on top of an existing GNN, they usually maintain the same order of computational complexity as the base model. For example, adding the heterophilous design to GCN [18] results in an architecture similar to GraphSAGE [15]; both have the same order of computational complexity as (|V | + |E |) by leveraging the sparse connectivity of most real-world graphs. Low-rank approximation-based vaccination, on the other hand, approximates the adjacency matrix of a graph by an SVD, resulting in an adjusted low-rank adjacency matrix A based on which the GNN runs. However, not only is computing an SVD potentially costly ( (|V | 3 ) in general), but in most cases it also results in a denseÃ (in contrast to the sparse original adjacency matrix), thus increasing the complexity of each iteration of the GNN.  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 2 GCN and GraphSAGE are still 3-4 times faster than the corresponding H 2 GCN-SVD and GraphSAGE-SVD methods. For fair runtime measurements, we measure 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.