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

Introduction

Graph Neural Networks (GNNs) have emerged as powerful tools for modeling complex relational data, ranging from social networks to biological systems. However, their reliance on graph topology introduces a unique vulnerability: adversarial attacks that manipulate the connections between nodes. Unlike the continuous perturbations common in computer vision, graph topology is inherently discrete—an edge either exists or it does not. This binary nature has historically limited the application of efficient first-order optimization methods, forcing researchers to rely on sub-optimal greedy heuristics or computationally intensive reinforcement learning.

This paper addresses this gap by introducing a first-order optimization framework that bridges the divide between continuous gradient-based methods and discrete graph data. By relaxing edge perturbations into a continuous space, the authors develop potent "topology attacks" and the first optimization-based adversarial training defense for GNNs.

Methodology

PGD Topology Attack via Convex Relaxation

To circumvent the "discrete hurdle," the authors propose treating edge existence as a continuous variable $s \in [0, 1]$, representing the probability of an edge being modified. This relaxation allows for the use of Projected Gradient Descent (PGD) to find the optimal set of edge probabilities that maximize the model's loss.

The attack process follows two main steps:

  1. Continuous Optimization: PGD is employed to iteratively update the edge probabilities within a defined perturbation budget.
  2. Binary Recovery: Since physical graphs require discrete edges, a randomized sampling procedure is used to map the continuous probabilities back to a binary adjacency matrix while respecting the total budget of allowed changes.

Adversarial Training Defense

Building upon the attack framework, the authors formulate a robust defense mechanism as a min-max optimization problem. The inner loop identifies the most damaging topology perturbation (the attack), while the outer loop updates the GNN's weights to minimize the loss on these adversarially perturbed graphs. This approach represents the first instance of optimization-based adversarial training specifically designed to harden GNNs against topological attacks.

Experimental Evaluation

The proposed methods were evaluated on two benchmark citation networks:

  • Cora: Comprising 2,708 nodes and 5,429 edges across 7 classes.
  • Citeseer: Comprising 3,327 nodes and 4,732 edges across 6 classes.

These datasets serve as standard benchmarks for semi-supervised node classification, where the objective is to predict paper categories based on citation patterns and node features.

Results and Discussion

The experimental results highlight several key advantages of the optimization-based approach. First, the continuous relaxation proves highly effective; the gradient information derived from the relaxed space provides high-fidelity guidance for discovering potent discrete attacks. On the Cora dataset, the proposed CE-PGD attack achieved a misclassification rate of 28.0%, significantly outperforming previous state-of-the-art methods like Meta-Self (22.7%) and DICE (18.9%) under a 5% perturbation budget.

Furthermore, the adversarial training defense demonstrated remarkable efficacy. For a GNN subjected to a 5% edge perturbation on Cora, the misclassification rate was reduced from 28.0% in a naturally trained model to 22.0% in the robustly trained version. Crucially, this increase in robustness did not come at the cost of "clean" accuracy—a common trade-off in other domains. The authors also demonstrated that their PGD-based attacks converge smoothly over iterations, as shown in the figure above, indicating the stability of the optimization process compared to discrete search methods.

Conclusion

This work demonstrates that first-order optimization is a viable and powerful tool for both attacking and defending GNNs. By successfully relaxing the discrete graph topology problem, the authors have opened new avenues for developing robust graph-based models. Future research may extend these methods to targeted attacks, address the scalability challenges associated with massive graphs, and integrate topology defenses with protections against node feature perturbations for a more holistic security posture.

Summary updated

BibTeX
@inproceedings{xu2019topology,
  author = {Kaidi Xu and Hongge Chen and Sijia Liu and Pin-Yu Chen and Tsui-Wei Weng and Mingyi Hong and Xue Lin},
  title = {{Topology Attack and Defense for Graph Neural Networks: An Optimization Perspective}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/550},
}
Figure