GOttack: Universal Adversarial Attacks on Graph Neural Networks via Graph Orbits Learning ICLR 2025 Conference

Zulfikar Alom1, Tran Gia Bao Ngo1, Murat Kantarcioglu2, Cuneyt Gurcan Akcora3

1University of Manitoba, 2Virginia Tech, 3University of Central Florida

Code Dataset arXiv

Abstract

Graph Neural Networks (GNNs) have demonstrated superior performance in node classification tasks across diverse applications. However, their vulnerability to adversarial attacks, where minor perturbations can mislead model predictions, poses significant challenges. This study introduces GOttack, a novel adversarial attack framework that exploits the topological structure of graphs to undermine the integrity of GNN predictions systematically.

By defining a topology-aware method to manipulate graph orbits, our approach generates adversarial modifications that are both subtle and effective, posing a severe test to the robustness of GNNs. We evaluate the efficacy of GOttack across multiple prominent GNN architectures using standard benchmark datasets. Our results show that GOttack outperforms existing state-of-the-art adversarial techniques and completes training in approximately 55% of the time required by the fastest competing model, achieving the highest average misclassification rate in 155 tasks. This work not only sheds light on the susceptibility of GNNs to structured adversarial attacks but also shows that certain topological patterns may play a significant role in the underlying robustness of the GNNs.

Problem Statement

Consider an initial graph \( \mathcal{G} = (\mathcal{A}, \mathcal{X}) \), a target node \( v \), and its true class \( y_v \). Our goal is to modify the graph's structure such that the classification of \( v \) changes from \( y_v \) to \( y_{v^\prime} \), where \( y_v \neq y_{v^\prime} \), thereby maximizing the difference from its original classification. The proposed attacks can be mathematically formulated as a bi-level optimization problem:

\[ \arg \max_{(\mathcal{A}', \mathcal{X}) \in \mathcal{G'}} \max_{y_{v^\prime} \neq y_v} \ln Z^*_{v,y_{v^\prime}} - \ln Z^*_{v,y_v} \]

where \( \mathbf{Z}^* = f_{\theta^*}(\mathcal{A}', \mathcal{X}) \) and \( \theta^* = \arg \min_{\theta} \mathcal{L}(\theta; \mathcal{A}', \mathcal{X}) \) subject to the budget constraint. Specifically, we aim to find a modified graph \( \mathcal{G}' = (\mathcal{A}', \mathcal{X}) \) in which the target node \( v \) is assigned a label \( y_{v^\prime} \) that maximizes the difference from its original label \( y_v \) in terms of probability scores.

Graphlet and Orbits

We compute Graph Orbit Vectors from all graphlets to develop a multi-orbit based attack strategy.

Graphlet. A graphlet \(G_{gp}\) within a larger graph \(G = (V, E, X)\) is a connected induced subgraph \(Gs' = (V', E', X')\), where \( V' \subseteq V \), and E' includes all edges \(e_{uv} \in E\) with both u and v in V', and |V'| typically equals 5.

Orbits. Orbits are defined by automorphisms of the graphlet. An automorphism σ of a graphlet \( G_{gp} \) satisfies \( \sigma(G_{gp}) = G_{gp} \). Nodes \( v \) and \( w \) in \( V \) are considered similar if there exists an automorphism σ such that \( \sigma(v) = w \). The orbit of a node \( v \), denoted by \( \text{Orb}(G_{gp}, v) \), is the set of all nodes \( w \in V \) that can be mapped onto \( v \) by some automorphism of the graphlet.

Mathematically, orbit of a node \( v \), denoted by \( \text{Orb}(\mathcal{G}_{gp}, v) \), is defined as: \( \text{Orb}(\mathcal{G}_{gp}, v) = \left\{ w \in \mathcal{V} \,\middle|\, \sigma \in \text{Aut}(\mathcal{G}_{gp}) : \sigma(v) = w \right\}. \). Here, \( \text{Aut}(\mathcal{G}_{gp}) \) represents the group of automorphisms of the graphlet \( \mathcal{G}_{gp} \). Each orbit is denoted by \( \text{Orb}_j \), where \( j \) is a unique identifier corresponding to a specific orbit within the graphlet.

A node \( v \) is said to touch an orbit \( \text{Orb}_j \) if it is part of an induced subgraph in the graph and belongs to \( \text{Orb}_j \). A node may appear in multiple graphlets and therefore can belong to multiple orbits.

For example, in Figure 1, node \( x \) appears in graphlets with node sets \( \{x, v, k, l, w\} \) and \( \{x, v, k, y, l\} \), among others.

In total, the 30 distinct graphlets generate \(\mathbf{73}\) distinct orbits. The number of graphlets and corresponding orbits is uniquely determined by the choice of using 5-node graphlets.

Graph Orbit Vector. A numerical representation of a node’s participation across the 73 orbits in a graph. Consequently, \(GOV_v\) a node v is an n=73-dimensional vector, where each dimension corresponds to the count of a specific orbit touched by node v. This dimensionality reflects the full set of topological positions a node can occupy across all 5-node graphlets, making it a comprehensive description of a node’s structural embedding.

Motif
Figure 1. A toy graph where shared node colors imply similar orbit counts. Nodes u, z, and w have 15 and 18 orbits, respectively.
Glet
Figure 2. Graphlets where orbits 15 and 18 are defined.

Graph Structure Poisoning via Orbit Learning

Our topological observation is influenced by the Mapper philosophy:

  1. Orbit Proxy. Under the homophily assumption, node classification posits that graph neighbors are similar to a node in the label. Consequently, nodes in more distant positions, as can be identified by orbits, are less similar.
  2. Periphery Orbits. Orbits \(15\) and \(18\) indicate the topological periphery in a graph and provide a useful proxy for identifying distant nodes that differ in labels.

We claim that the path distance within the graph encodes a notion of remoteness, which in turn yields minimal information about a node's label. This indicates that physical proximity within the network strongly influences the predictive accuracy regarding node labels.

In Theorem, we formally state that nodes located in orbits \(15\) and \(18\), due to their peripheral placement, are particularly effective for establishing paths to remote parts of the graph. This has significant implications for designing network protocols and algorithms that rely on efficient data traversal and retrieval mechanisms.

Theorem 1 (Remote Connection Candidates). Let \( H(v, w) \) denote the expected random walk hitting time from node \( v \) to node \( w \) in \( \mathcal{G} \). For any target node \( v \in V \), nodes in orbits \(15\) and \(18\) are the most effective candidates of \( w \) for establishing paths to the most remote parts of \( \mathcal{G} \), due to their longer expected hitting times \( H(v, w) \) compared to other nodes not in these orbits.

The Periphery Orbits observation forms the backbone of our attack strategy. We identify nodes of periphery orbits (i.e., \(15\) and \(18\)) and affect the adjacency matrix (i.e., add or remove edges to these nodes) accordingly to confuse a GNN into misclassifying a target.

Consider the target node \( v \) in Figure 2. Our hypothesis posits that creating an edge from \( v \) (or any other node) to either of the orbit \(15\) or \(18\) nodes \( u \), \( z \), or \( w \) will yield the highest misclassification error in GCN. The selection among periphery nodes uses a gradient-based method, as we detail below in the surrogate loss section.

Orbits \( (15, 18) \). We define two ordered orbit categories based on the highest and second-highest orbit counts. The highest is given by: \( Orb^v_{\text{max}} = \arg\max(\text{GOV}_v) \). If multiple orbits share this count, one is chosen arbitrarily. The second-highest is: \( Orb^v_{\text{sec}} = \arg\max\left( \{ j \in \text{GOV}_v \mid j \neq Orb^v_{\text{max}} \} \right) \). Each node is then assigned an orbit category:\( Orb^v = Orb_{\text{max}} \Vert Orb_{\text{sec}} \), where order does not matter.

Experimental Setup

Datasets. We use three citation networks Cora, Citeseer, Pubmed and two blogs data Polblogs and BlogCatalog.

Models. We use four SOTA models (Nettack, FGA, SGA and PRBCD) and three backbone GNNs (GCN, GIN and GraphSAGE) to evaluate adversarial attacks.

Hardware. The experiments were conducted using Python (Version 3.8.19) and PyTorch Version 3.10.0. The computational environment was a Linux cluster equipped with an AMD Ryzen Threadripper 3960X 24-core processor, 2520GB RAM and NVIDIA RTX A6000 with 49GB RAM GPUs

Experimental Results


Table 1 shows the misclassification rate achieved with a single edge perturbation (addition or deletion). GOttack yields the highest misclassification rates in 7 out of 15 attack settings and ranks second in 5 other settings. SGAttack yields 4 best attacks, while PRBCD and Nettack each perform best in 2 attack settings. PRBCD, a widely used method adopted by PyTorch, yields surprisingly low rates in two datasets for GSAGE and GIN. GOttack yields the highest overall rate of 52.08, whereas the second best Nettack yields 47.02.


Motif
Table 1. Misclassification rate (in %) (↑) of target nodes in five datasets where three backbone GNNs are attacked in node classification with budget ∆ = 1.

Motif
Figure 3. Budgeted (∆ = 1 to 5) attack results on the Citeseer dataset.

In Figure 3, we gradually increase the attack budget and represent the corresponding misclassification rates on the Citeseer dataset. We observe that for GraphSAGE, GOttack yields better misclassification results, reaching a maximum misclassification score of 97% with 5 perturbations. Similarly, for the GCN and GIN models, the proposed approach attains misclassification scores of 77% and 76%, respectively, outperforming the SOTA models.

Motif
Table 2. Misclassification rate (in %) (↑) of target nodes in different datasets against four defense models are attacked in node classification.

Table 2 shows the misclassification rates of the top-3 attack models on defense models with a single edge perturbation. GOttack yields the highest misclassification rates in 7 out of 16 attack settings and ranks second in 7 other settings, while SGA achieves the best performance in 7 attack settings. GOttack achieves the highest overall rate of 33.07, whereas SGA has a rate of 32.5.


Motif
Figure 4. The computation graph for the targeted node 1978 from the CORA datasets, as identified by GNNExplainer. The edge (1978, 387) is added during the successful attack. Edge importances change considerably after the attack and negative class gains importance due to the newly added nodes.

Time Complexity. Orbit discovery is the primary computational cost of GOttack. The time complexity for computing all orbits for all nodes is O(|E| × d + |V| × d4), where O(|V| × d4) corresponds to the time required to enumerate all five-node graphlets, and d denotes the maximum degree in the graph. For instance, orbit discovery on the CORA dataset takes only 0.17 seconds.


Motif
Table 3. Time Experiment Results in Seconds (↓).

Conclusion

We have identified a key equivalence group for graph nodes based on their topological positions within the graph and demonstrated that gradient-based attack models frequently target this group in their attacks. Our approach, GOttack, introduces a seminal topological strategy in adversarial graph machine learning. By uncovering this previously unexplored vulnerability tied to graph topology, our work highlights the susceptibility of graph neural networks to topology-based attacks and paves the way for developing efficient attack models. GOttack not only enhances misclassification rates but does so in a scalable manner. For future work, we aim to study topological defenses against attack models.


For additional details and experimental results, please refer to our main paper. Thank you!



BibTeX

@article{zulfikar2025gottack,
title={GOttack: Universal Adversarial Attacks on Graph Neural Networks via Graph Orbits Learning},
author={Zulfikar Alom, Tran Gia Bao Ngo, Murat Kantarcioglu, Cuneyt Gurcan Akcora},
journal={The Thirteenth International Conference on Learning Representations, ICLR},
year={2025}
}