Nettack

Nettack focuses on changing the prediction of a single target node from its correct class to a specific, incorrect target class. Unlike untargeted attacks that aim for any misclassification, Nettack's goal is precise: force the GNN to classify node v as class c_target rather than its true class c_orig. This targeted approach makes it particularly dangerous for critical applications like fraud detection or medical diagnosis, where an attacker may want a specific outcome.

Nettack enforces strict constraints to ensure modifications remain undetectable:

• Degree distribution preservation: The graph's overall degree distribution must remain statistically unchanged, preventing simple anomaly detection.
• Feature co-occurrence preservation: Modified node features must respect the observed co-occurrence patterns in the original feature matrix, ensuring new feature combinations appear plausible.
• Limited modification budget: The attacker can only modify a small number of edges and features, typically denoted as Δ edges and Δ features.

Nettack attacks a surrogate GNN model rather than directly attacking the target model, making it a gray-box attack. The surrogate is trained on the same graph data and approximates the target model's decision boundaries. This approach works because adversarial examples often transfer between models. The attacker uses a simplified 2-layer GCN as the surrogate, computing gradients with respect to both the adjacency matrix and feature matrix to identify the most impactful perturbations.

Nettack uses a greedy algorithm to select perturbations that maximize the attack's objective function. At each step, it evaluates all possible edge additions/deletions and feature flips within the constraint budget, choosing the single modification that most increases the target node's predicted probability for the adversary's desired class. This iterative process continues until the attack succeeds or the budget is exhausted. The scoring function combines the surrogate model's log-probabilities with a constraint penalty term.

Nettack can manipulate two attack surfaces simultaneously:

• Structural perturbations: Adding or removing edges in the target node's local neighborhood. Adding edges to nodes from the target class can inject malicious influence, while removing edges to nodes from the original class can isolate the target from correct signals.
• Feature perturbations: Flipping binary features of the target node to make it resemble nodes from the target class. This exploits the GNN's reliance on node attributes for classification.

A key property of Nettack is transferability—perturbations computed against the surrogate GCN often successfully fool the target GNN, even when the target uses a different architecture (e.g., GAT or GraphSAGE). This occurs because different GNN models learn similar decision boundaries when trained on the same data. Transferability makes Nettack practical for real-world attacks where the adversary lacks full access to the target model's architecture and parameters.