🤖 machine learning

Attack by Unlearning: Unlearning-Induced Adversarial Attacks on Graph Neural Networks

This paper introduces "unlearning corruption attacks," a novel adversarial strategy where malicious actors exploit the mandatory nature of data deletion requests to inject specific nodes that, once removed via approximate unlearning, cause significant and stealthy degradation in Graph Neural Network performance.

Original authors: Jiahao Zhang, Yilong Wang, Suhang Wang

Published 2026-03-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jiahao Zhang, Yilong Wang, Suhang Wang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Idea: The "Right to Be Forgotten" Weaponized

Imagine you have a very smart librarian (the AI Model) who has read millions of books to learn how to recommend stories to you. You trust this librarian.

Now, imagine a new law says: "If a customer asks to be forgotten, the librarian must erase all memory of them from their mind, instantly, without re-reading the whole library." This is called Machine Unlearning. It's meant to protect privacy.

The Paper's Discovery:
The researchers found a scary loophole. A clever hacker can trick the librarian into forgetting in a way that destroys their ability to do their job.

They call this an "Unlearning Corruption Attack." It's like a Trojan Horse, but instead of hiding inside a gift, the Trojan Horse is a request to delete a gift.

How the Attack Works (The Three-Step Trick)

The attack happens in three stages, like a heist movie:

Step 1: The "Trojan" Entry (Injection)

The hacker creates a fake user account (a "Trojan node") and joins the library.

The Trick: The hacker makes this fake user look completely normal. They read normal books, talk to normal people, and fit right in.
The Result: The librarian trains their brain on this new data. Everything looks perfect. The librarian is still smart and helpful. The hacker hasn't broken anything yet.

Step 2: The "Right to Be Forgotten" Request (The Trigger)

Later, the hacker exercises their legal right. They say, "I want to be deleted. Remove me from your memory."

The Constraint: The librarian must obey the law. They cannot say "No." They have to perform "Unlearning"—a quick mental surgery to remove the hacker's influence without retraining the whole brain.

Step 3: The Collapse (The Damage)

Here is the magic trick. Because the hacker planted the fake user specifically to be removed, the "mental surgery" goes wrong.

The Result: When the librarian tries to remove the fake user, they accidentally rip out the logic needed to understand real users. The librarian suddenly forgets how to recommend books to everyone else. Their accuracy crashes from 90% to 20%.

The scary part? The librarian looked perfect before the deletion. The damage only appears after the deletion.

The Three Rules of the Hacker

To pull this off, the hacker has to follow three strict rules (which the paper calls Goals G1, G2, and G3):

The "Sleeping Giant" Rule (Stealth): Before the deletion, the librarian must act normal. If the fake user makes the librarian act weird before they are deleted, the librarian will spot the intruder. The attack must be invisible until the moment of deletion.
The "Surgical Precision" Rule (Targeted Damage): The hacker wants to break the librarian's brain only when they delete the specific fake user. If the librarian deletes a different, innocent person, the brain should still work fine. This makes the attack look like a coincidence rather than a crime.
The "Nuclear Option" Rule (Maximum Damage): Once the deletion happens, the librarian's performance should crash hard.

How They Did It (The Technical Magic)

The researchers didn't just guess; they used math to find the perfect "Trojan user."

The Black Box Problem: The hacker doesn't know exactly how the librarian's brain works (it's a "black box"). They can't see the internal gears.
The Surrogate Trick: The hacker builds their own "dummy librarian" (a Surrogate Model) that acts like the real one. They train this dummy, test the deletion on it, and use the results to figure out how to break the real librarian.
The "Undo" Button: They treat the deletion process like a mathematical equation. They ask: "If I change the fake user's features just a tiny bit, how will the 'undo' button (unlearning) break the model?" They run this calculation thousands of times to find the perfect setup.

Why This Matters

This paper sounds like science fiction, but it's a real problem for the future of AI.

Privacy vs. Safety: We need laws like GDPR that let people delete their data. But this paper shows that if we force AI to "unlearn" data quickly, we might accidentally create a vulnerability where hackers can use those deletion requests to crash the system.
The Unavoidable Trap: You can't just tell the librarian, "Don't delete that person." The law says you must. This makes the attack surface unavoidable.

The Takeaway

The researchers are sounding an alarm: Just because a system is "privacy-compliant" doesn't mean it's "attack-proof."

They are showing us that the very mechanism designed to protect us (deleting data) can be turned into a weapon to destroy the system. They hope that by exposing this, developers can build "shields" so that when a user asks to be forgotten, the AI can say "Okay, I've deleted you," without accidentally forgetting how to do its job.

1. Problem Definition

The paper addresses a novel security vulnerability in Graph Neural Networks (GNNs) related to Machine Unlearning.

Context: To comply with privacy regulations (e.g., GDPR, CCPA), systems must support "right to be forgotten," requiring the removal of specific data points (nodes) from trained models without full retraining. This is typically achieved via approximate unlearning algorithms (e.g., influence functions, gradient ascent).
The Vulnerability: Approximate unlearning is known to cause subtle performance degradation. The authors hypothesize that an adversary can weaponize this degradation.
The Attack Scenario (Unlearning Corruption):
1. Injection: An adversary injects carefully crafted "poison" nodes into the training graph. These nodes are designed to appear benign during the initial training phase, maintaining normal model accuracy.
2. Trigger: The adversary later submits a legitimate deletion request (unlearning) for these specific injected nodes.
3. Exploitation: Because the unlearning process is an approximation, removing these specific nodes causes a catastrophic collapse in the model's accuracy on the remaining unlabeled data.
Key Constraints: The attack must be stealthy (no performance drop before unlearning), effective (large drop after unlearning), and specific (benign unlearning requests should not trigger the drop).

2. Methodology

The authors propose a bi-level optimization framework to solve the challenge of crafting these attacks under a black-box setting (where the attacker does not know the victim model's architecture or parameters) and label scarcity (no ground truth for test nodes).

A. Threat Model & Formalization

Attacker Capabilities: Can inject nodes and edges into the training graph but cannot access the target model's internals. The attacker knows a GNN and an unlearning algorithm are used.
Objective: Maximize the loss on unlabeled nodes after unlearning the injected nodes, while minimizing loss before unlearning and ensuring benign unlearning does not cause degradation.
Optimization Problem: Formulated as maximizing the classification loss on the target set $V_U$ after unlearning $\Delta V$ , subject to edge budget constraints and stealthiness constraints.

B. Technical Solutions

To overcome the difficulty of optimizing a black-box unlearning operator without ground-truth labels, the authors employ two key techniques:

Gradient-Based Unlearning Approximation:
- Since the unlearning operator is a black box, the authors approximate it using a one-step gradient ascent update.
- They define a surrogate objective function that balances retaining performance on clean data and "forgetting" the injected nodes.
- This allows the use of automatic differentiation (gradient-of-gradient) to compute how changes in injected features/edges affect the final unlearned parameters.
Surrogate Modeling with Pseudo-Labels:
- To handle the lack of ground-truth labels for the unlabeled test set ( $V_U$ ), the attacker trains a surrogate GNN on the injected graph.
- The surrogate model generates pseudo-labels for the unlabeled nodes. These pseudo-labels serve as a proxy for the victim model's behavior during the optimization process.
Optimization Strategy:
- Re-parameterization: Since edge existence is discrete (0 or 1), direct gradient descent is impossible. The authors re-parameterize edge variables using a sigmoid function to map them to a continuous range $[0, 1]$ .
- Projection: Optimization occurs in the continuous space. Only at the final step is a hard projection applied to satisfy the discrete edge budget (setting the top- $B$ edges to 1 and others to 0). This avoids the vanishing gradient problem associated with iterative discrete projection.
- Scalability: For large graphs, they restrict the optimization search space to the $k$ -hop neighborhoods of the target nodes, significantly reducing computational complexity.

3. Key Contributions

New Attack Paradigm: Introduction of "Unlearning Corruption Attacks," a novel threat surface distinct from traditional poisoning or backdoor attacks. It uniquely exploits the unlearning process itself as the trigger mechanism.
Formal Threat Model: Definition of three adversarial goals:
- G1 (Post-unlearning Damage): Maximize accuracy drop after deletion.
- G2 (Pre-unlearning Utility): Maintain normal performance before deletion.
- G3 (Benign Stealthiness): Ensure deleting other nodes does not trigger the attack.
Novel Framework: A bi-level optimization framework that successfully bridges the gap between black-box unlearning and adversarial optimization using gradient approximation and surrogate modeling.
Comprehensive Evaluation: Extensive experiments demonstrating the attack's effectiveness across multiple datasets (Cora, Citeseer, Pubmed, Flickr) and unlearning algorithms (GIF, CEU, Gradient Ascent).

4. Experimental Results

The authors evaluated their method (OptimAttack) against baselines (Random injection, Copy injection, and existing poisoning attacks like SBA, UGBA, TDGIA) across four datasets and three unlearning algorithms.

Effectiveness (G1): OptimAttack consistently caused the highest accuracy drops.
- Example: On the Pubmed dataset using the GIF unlearning algorithm, OptimAttack induced a ~59% accuracy drop (from ~83% to ~24%), whereas standard poisoning attacks caused negligible drops.
- On Citeseer, the drop reached ~53% under GIF.
Stealthiness (G2): The "Original Accuracy" (before unlearning) of models poisoned by OptimAttack remained comparable to clean models (e.g., ~73.8% vs. ~73.6% on Citeseer), proving the attack is latent until the deletion request is made.
Benign Stealthiness (G3): Ablation studies showed that without the specific regularization term for G3, the attack caused collateral damage (degrading performance even when benign nodes were deleted). With the regularization, the model remained robust to benign unlearning.
Transferability: The attack vectors generated using a GCN surrogate successfully transferred to other architectures (SGC, GAT), causing significant degradation across different model types.
Budget Efficiency: The attack achieved near-maximum damage with very small budgets (5% of nodes injected, 5 edges per node), indicating high resource efficiency.

5. Significance and Implications

Paradigm Shift: This work challenges the assumption that unlearning is a purely defensive mechanism for privacy. It demonstrates that the process of complying with privacy laws can be turned into an attack vector.
Regulatory Tension: The attack highlights a critical tension between compliance (the legal requirement to delete data) and robustness (the stability of the model). Defenders cannot simply refuse deletion requests due to legal mandates, making this attack surface unavoidable.
Stealthiness: Unlike traditional backdoors that require specific triggers at inference time, this attack is triggered by a standard administrative action (data deletion), making it extremely difficult to detect or mitigate without compromising the "right to be forgotten."
Future Directions: The paper suggests that current approximate unlearning methods are fundamentally vulnerable to such manipulation and calls for new research into robust unlearning algorithms that can resist "unlearning-induced" corruption.