Source-linked AI summary
Topology Attack and Defense for Graph Neural Networks: An Optimization Perspective
Kaidi Xu, Hongge Chen, Sijia Liu, Pin-Yu Chen, Tsui-Wei Weng, Mingyi Hong, Xue Lin
TL;DR
GNNs perform well on semi-supervised node classification, but their adversarial robustness has received limited attention, especially because graph topology changes are discrete. The paper develops gradient-based topology attacks through convex relaxation and uses them for adversarial training, reporting stronger robustness against gradient-based and greedy attacks without degrading classification on the original graph.
Problem
Adversarial robustness of GNNs has received limited attention, and conventional first-order continuous optimization does not directly handle discrete edge manipulations.
Method
The paper develops first-order topology attacks for pre-defined and re-trainable GNNs using convex relaxation, then builds optimization-based adversarial training on those attacks.
Results
The proposed attacks outperform current state-of-the-art attacks, while adversarial training improves robustness against gradient-based and greedy topology attacks without classification performance drop on the original graph.
Takeaways & Limitations
Small edge perturbations can noticeably compromise GNN classification, while the proposed adversarial training improves robustness without sacrificing original-graph classification performance.
Abstract
from arXiv · showhide
Graph neural networks (GNNs) which apply the deep neural networks to graph data have achieved significant performance for the task of semi-supervised node classification. However, only few work has addressed the adversarial robustness of GNNs. In this paper, we first present a novel gradient-based attack method that facilitates the difficulty of tackling discrete graph data. When comparing to current adversarial attacks on GNNs, the results show that by only perturbing a small number of edge perturbations, including addition and deletion, our optimization-based attack can lead to a noticeable decrease in classification performance. Moreover, leveraging our gradient-based attack, we propose the first optimization-based adversarial training for GNNs. Our method yields higher robustness against both different gradient based and greedy attack methods without sacrificing classification accuracy on original graph.
1 Introduction
The paper studies adversarial robustness in GNNs by developing first-order topology attacks despite the discrete nature of graph edges, then uses those attacks for adversarial training. The proposed attacks outperform existing methods, while training improves robustness without sacrificing original-graph accuracy.
- Motivation and gap: First-order continuous optimization methods do not directly apply to topology attacks because graph edge manipulations are discrete.The paper addresses this gap through convex relaxation, making gradient-based attacks plausible for GNNs.
- Attack performance: The proposed attacks outperform current state-of-the-art attacks under the same topology perturbation budget.
- Approach: The attack framework is grounded in spectral graph theory, first-order optimization, and robust mini-max optimization.
- Contributions: The paper introduces first-order topology attacks for both pre-defined and re-trainable GNNs.These scenarios yield projected gradient descent and min-max topology attacks.
- Defense: The adversarial training method considerably improves GNN robustness against optimization-based and greedy-search-based topology attacks.
2 Related Works
Prior work had begun studying adversarial attacks on graph neural networks, including test-time non-targeted attacks constrained to discrete edge additions and deletions.
- Existing attacks: Prior studies examined adversarial attacks on neural networks for graph data.
- Existing attacks: Dai et al. studied test-time non-targeted attacks for graph classification and node classification.
- Threat model: Their attack model restricted modifications to adding or deleting edges from the graph.
3 Problem Statement
The paper formulates GNN inference and topology attacks on graphs through edge perturbations. It represents modified edges with a Boolean symmetric matrix and defines attacks as finding minimal perturbations that mislead the GNN.
- GNN preliminaries: A GNN performs transductive node classification using one graph topology, node features, and labels for only a subset of nodes.The graph is represented as G = (V, E) with a binary adjacency matrix A and node features xi.
- GNN preliminaries: A generic GNN layer propagates node representations using neighboring nodes, trainable weights, and an activation function.The neighborhood includes each node itself, and the transformed adjacency retains the graph's sparsity pattern.
- GCN formulation: GCNs are a special GNN form whose propagation uses graph convolution operations.The standard GCN normalization is based on ˆA = A + I and its degree matrix.
- Topology attack: The perturbation matrix S is Boolean and symmetric, marking edges that are added or removed in the perturbed topology A′.The supplement matrix distinguishes addable edges from removable edges through the sign of C = ¯A − A.
- Topology attack: A topology attack seeks the minimum edge perturbations that mislead a GNN.
4 Topology Attack Generation: A First-Order Optimization Perspective
This section develops topology attacks for GNNs using first-order optimization under fixed-parameter and re-trainable threat models. It relaxes discrete perturbations, optimizes the relaxed problem, and recovers binary edge changes.
- Attack formulations: The paper develops PGD topology attacks and min-max topology attacks for pre-defined and re-trainable GNNs, respectively.The fixed-parameter scenario assumes known W, while the re-trainable scenario jointly considers perturbations and model parameters.
- Attack formulations: Topology attacks minimize per-node CE-type or CW-type attack loss subject to a finite budget of edge perturbations.Targeted attacks additionally constrain perturbations to edges incident to targeted nodes.
- Convex relaxation and PGD: Boolean perturbation variables are relaxed from {0, 1}^n to [0, 1]^n, converting the combinatorial attack problem into a continuous optimization problem.The relaxed vector is optimized under the perturbation-budget constraint.
- Binary recovery: Random sampling converts the optimized probabilistic perturbation vector into binary candidates and selects the candidate with the smallest attack loss within the budget.Each binary variable is sampled as one with probability s_i and zero with probability 1 − s_i.
- Convex relaxation and PGD: PGD alternates a gradient-descent step on attack loss with projection onto the feasible perturbation set, using the learning rate and gradient defined for iteration t.The projection enforces the relaxed perturbation constraints.
- Min-max optimization: Min-max attack generation uses first-order alternating optimization, with gradient ascent for the inner maximization and PGD for the outer minimization.Multiple maximization steps may be used to balance computational efficiency and convergence accuracy.
5 Robust Training for GNNs
The paper formulates adversarial training for GNNs as robust optimization that minimizes training loss under topology perturbations. It relates this formulation to min-max attack problems while noting that the objectives lack the saddle-point property.
- Robust optimization: Adversarial training solves a min-max robust optimization problem for GNNs in the presence of topology perturbations.The formulation follows the adversarial-training setup used for image classifiers.
- Robust optimization: The training objective restricts f to a CE-type loss and minimizes training loss when topology perturbations are present.Here f denotes the attack loss specified in the robust-optimization formulation.
- Optimization relationship: Problems (21) and (7) have similar min-max forms but are not equivalent because f is neither convex in s nor concave in W.The paper identifies the resulting absence of the saddle-point property and establishes a connection through Proposition 2.
- Optimization relationship: The robust training algorithm uses alternating optimization with multiple inner minimization steps in s to improve convergence stability in practice.The algorithm is summarized as Algorithm 4 and follows the alternating structure described for the related optimization procedure.
6 Experiments
Experiments evaluate first-order topology attacks and robust GCN training on Cora and Citeseer. The attacks converge and outperform existing methods in several settings, while robust training improves attack resistance without harming clean test accuracy under 5% perturbations.
- Experimental setup: Experiments evaluate four proposed attacks—CE-PGD, CW-PGD, CE-min-max, and CW-min-max—against existing topology attacks on Cora and Citeseer.The evaluation uses GCNs, 140/120 labeled training nodes, and 1,000 labeled test nodes per dataset, repeating each experiment five times.
- 6.2 Attack Performance: The proposed attacks achieve better misclassification rates than existing methods against natural models, while min-max attacks remain competitive against retrained models.CE-PGD and CW-PGD perform better than min-max attacks against predefined GCNs; the retrained-model comparison is qualified because retrained weights may be suboptimal.
- 6.2 Attack Performance: PGD attack losses converge gracefully across iterations on Cora and Citeseer, supporting the effectiveness of first-order optimization for topology attack generation.Figure 1 reports CE-loss and CW-loss for the proposed attacks, using T = 200 and η_t = 200/t.
- 6.3 Defense Performance: At ϵ = 5%, robust training reduces the Cora attack success rate from 28.0% to 22.0% without harming test accuracy.Robust-training convergence is shown in Figure 2, and the defense evaluation uses at most 5% edge perturbations.
- 6.3 Defense Performance: Increasing the training perturbation bound from 5% to 20% increases the gap between clean and CE-PGD test accuracy, while larger bounds make robust models harder to obtain.The authors suggest training with ϵ = 0.1 to balance robustness and original-graph test performance; Figure 3 also evaluates CW-PGD and Greedy attacks.
7 Conclusion
The paper introduces first-order topology attacks for discrete graph structures and an adversarial training framework that improves GNN robustness without reducing performance on the original graph.
- The edge perturbation-based topology attack overcomes the difficulty of attacking discrete graph structures from a first-order optimization perspective.
- With only a fraction of edges changed, the attack noticeably compromises state-of-the-art GNN models.
- Adversarial training improves GNN robustness against both gradient-based and greedy-search-based topology attacks.
- Across different datasets, the proposed training method improves robustness without a classification performance drop on the original graph.