Value at Adversarial Risk: A Graph Defense Strategy against Cost-Aware Attacks

Junlong Liao, Wenda Fu, Cong Wang, Zhongyu Wei, Jiarong Xu

Introduction

Adversarial attacks on Graph Neural Networks (GNNs) typically involve a reactive struggle where defenders attempt to sanitize graphs or enhance model robustness post-hoc. However, these approaches often overlook the economic reality of adversarial actions: attacking is not free. In the paper "Value at Adversarial Risk: A Graph Defense Strategy against Cost-Aware Attacks" (AAAI-24), researchers from Fudan and Peking University propose RisKeeper, a proactive defense strategy that shifts the paradigm from reactive filtering to strategic cost allocation.

The RisKeeper Framework

RisKeeper treats graph defense as a minimax bi-level optimization problem. The core philosophy is to make the "cost" of an attack prohibitively high for the adversary, effectively deterring them from attempting to degrade model performance.

  1. Cost-Aware Attack (Inner Loop): The model assumes a realistic attacker who seeks to maximize classification error while constrained by a specific budget. This attacker employs a gradient-based approach (Projected Gradient Descent) to identify the most damaging structural perturbations within their resource limits.
  2. Proactive Defense (Outer Loop): The defender aims to assign protection costs to nodes and edges such that the attacker's optimal strategy yields minimal damage.
  3. Learnable Cost Allocation: Unlike static heuristics (e.g., protecting high-degree nodes), RisKeeper utilizes a GNN and a Multi-Layer Perceptron (MLP) to learn optimal cost distributions based on local graph topology and node features.

Structural Vulnerability and Graphlets

A key insight of the research is identifying which local structures are most susceptible to attack. The authors analyzed various "graphlets"—small sub-structures within the larger network—to determine their inherent robustness.

Common graphlets used to analyze structural vulnerability and protection costs.

The study found that 3-star, 4-circle, and tailed-triangle structures are particularly fragile, requiring higher protection budgets. Conversely, more densely connected structures like triangles and 4-cliques exhibit natural resilience and lower adversarial risk.

Experimental Evaluation

The researchers evaluated RisKeeper across four benchmark datasets: citation networks (Cora, Citeseer) and co-purchase graphs (Amazon Computers, Amazon Photo). The defense was tested in both evasion (test-time) and poisoning (train-time) scenarios.

Key Results

RisKeeper consistently outperformed established defensive baselines, including GCN-SVD, GCN-Jaccard, and GNN-Median.

Performance comparison of RisKeeper against baseline defense strategies across four benchmark datasets under evasion attacks.

As shown in the table above, RisKeeper achieved an accuracy of 79.5% on the Cora dataset under cost-aware evasion attacks, a significant improvement over the raw GCN's 29.0% and the best heuristic defense (74.6%). Notably, RisKeeper maintains high performance on "clean" (unattacked) data, avoiding the accuracy trade-offs often seen with denoising-based defenses like GCN-SVD. This stability makes it a viable candidate for deployment in production environments.

Conclusion

By framing graph security as an economic problem of resource allocation, RisKeeper introduces a powerful deterrent against adversarial attacks. While the bi-level optimization presents scalability challenges for massive graphs, the strategy provides a robust blueprint for hardening critical networks—such as financial or communication systems—where attackers operate under real-world budget constraints.

Summary updated

Abstract

Deep learning methods on graph data have achieved remarkable efficacy across a variety of real-world applications, such as social network analysis and transaction risk detection. Nevertheless, recent studies have illuminated a concerning fact: even the most expressive Graph Neural Networks (GNNs) are vulnerable to graph adversarial attacks. While several methods have been proposed to enhance the robustness of GNN models against adversarial attacks, few have focused on a simple yet realistic approach: valuing the adversarial risks and focused safeguards at the node level. This empowers defenders to allocate heightened security level to vulnerable nodes, while lower to robust nodes. With this new perspective, we propose a novel graph defense strategy RisKeeper, such that the adversarial risk can be directly kept in the input graph. We start at valuing the adversarial risk, by introducing a cost-aware projected gradient descent attack that takes into account both cost avoidance and compliance with costs budgets. Subsequently, we present a learnable approach to ascertain the ideal security level for each individual node by solving a bi-level optimization problem. Through extensive experiments on four real-world datasets, we demonstrate that our method achieves superior performance surpassing state-of-the-art methods. Our in-depth case studies provide further insights into vulnerable and robust structural patterns, serving as inspiration for practitioners to exercise heightened vigilance.
BibTeX
@inproceedings{liao2024value,
  author = {Junlong Liao and Wenda Fu and Cong Wang and Zhongyu Wei and Jiarong Xu},
  title = {{Value at Adversarial Risk: A Graph Defense Strategy against Cost-Aware Attacks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i12.29282},
}
Figure