Overview

Graph Neural Networks (GNNs) have become ubiquitous for learning on graph-structured data, particularly for link prediction tasks in social networks, recommendation systems, and knowledge graphs. However, their vulnerability to adversarial attacks—especially attacks involving node injection—remains understudied.

SAVAGE (Sparse Adversarial Attacks on Graph Neural Networks with Efficient Gradient Estimation) addresses this gap by developing a principled framework for injecting malicious nodes that manipulate link prediction systems while using minimal resources.

Why Node Injection Attacks Matter

Unlike perturbation attacks that modify existing graph structure, node injection attacks:

• Are more realistic: Attackers can create fake accounts but rarely modify existing relationships
• Are harder to detect: New nodes blend into network growth patterns
• Scale differently: The attack budget is the number of malicious nodes, not edge modifications

Method

Problem Formulation

Given a GNN-based link prediction model \(f_\theta\) trained on graph \(G = (V, E)\), the attacker wants to inject \(k\) malicious nodes \(V_{mal}\) with edges \(E_{mal}\) to maximize a target objective (e.g., promoting specific links).

The key challenge: The attacker has a limited budget of malicious nodes and edges. We must find the optimal allocation of edges among malicious nodes.

Sparsity-Constrained Optimization

We formulate node injection as a constrained optimization problem:

subject to: \(\|\mathbf{A}_{mal}\|_0 \leq B\)

SAVAGE Algorithm

1. Relaxation: Replace binary constraint with continuous optimization using sigmoid gates: \(\mathbf{A}_{mal} = \sigma(\mathbf{W})\)

2. Sparsity enforcement: Add \(L_1\) regularization to encourage few edges per malicious node: \(\mathcal{L}_{total} = \mathcal{L}_{attack} + \lambda \|\mathbf{A}_{mal}\|_1\)

3. Gradient-based optimization: Use first-order gradients through the GNN to optimize malicious node connections: \(\mathbf{W} \leftarrow \mathbf{W} + \alpha \nabla_{\mathbf{W}} \mathcal{L}_{total}\)

4. Projection: Project back to feasible set by keeping top-\(B\) edges by magnitude.

Attack Objectives

Link promotion: Maximize probability of target links \(\mathcal{L}_{promote} = \sum_{(u,v) \in E_{target}} \log f_\theta(u, v)\)

Link suppression: Minimize probability of existing links \(\mathcal{L}_{suppress} = -\sum_{(u,v) \in E_{target}} \log f_\theta(u, v)\)

Experiments

Datasets and Setup

GNN models tested:

• GCN (Graph Convolutional Network)
• GraphSAGE
• GAT (Graph Attention Network)

Attack Performance

Link Promotion Results (Attack Success Rate vs. Budget):

With just 5% malicious nodes, SAVAGE achieves ~75% attack success rate across datasets.

Comparison to Baselines

Attack Success Rate at 5% budget:

SAVAGE achieves comparable or better attack success with 4× fewer edges per malicious node than baseline methods.

Transferability Across Models

A critical question: Do attacks optimized for one GNN transfer to others?

Transfer Attack Results (rows = source model, columns = target model):

Attacks trained on one architecture transfer with 65-70% effectiveness to other black-box models, demonstrating robustness.

Sparse vs. Dense Attacks

Resource Efficiency:

SAVAGE achieves 4× better resource efficiency, critical for realistic attack scenarios where each edge requires effort to establish.

Key Findings

1. Sparsity improves both efficiency and effectiveness: Forcing attackers to use minimal edges per node paradoxically improves attack success by focusing resources on high-impact connections.

2. Node injection attacks are surprisingly effective: With just 5% malicious nodes, attackers can manipulate link predictions for 75% of target pairs, demonstrating significant vulnerability in GNN-based systems.

3. Attacks transfer across GNN architectures: Malicious nodes optimized for one GNN (e.g., GCN) remain 65-70% effective against different architectures (GAT, GraphSAGE), enabling black-box attacks without model access.

4. Defense mechanisms are urgently needed: Current GNN training procedures offer no protection against node injection attacks. The effectiveness and transferability of SAVAGE highlights the need for robust GNN architectures and anomaly detection.

5. Realistic threat model: Unlike edge perturbation attacks, node injection reflects real-world adversarial behavior (fake accounts, Sybil attacks), making these findings directly applicable to production systems.

Citation

@article{trappolini2023sparse,
  title   = {Sparse Vicious Attacks on Graph Neural Networks},
  author  = {Trappolini, Giovanni and Maiorca, Valentino and Severino, Silvio and
             Rodolà, Emanuele and Silvestri, Fabrizio and Tolomei, Gabriele},
  journal = {IEEE Transactions on Artificial Intelligence},
  year    = {2023}
}

Authors

Giovanni Trappolini¹ · Valentino Maiorca¹ · Silvio Severino¹ · Emanuele Rodol๠· Fabrizio Silvestri¹ · Gabriele Tolomei¹

¹Sapienza University of Rome