When a user invokes the "right to be forgotten" under modern privacy regulations, machine learning models must erase that user's influence from their learned parameters. In traditional machine learning settings, data points are assumed to be independent and identically distributed (i.i.d.). Unlearning an independent sample is conceptually straightforward: you estimate how that isolated point shifted the optimization landscape and adjust the model weights accordingly.
However, as Antonio Ginart et al. noted in Making AI Forget You: Data Deletion in Machine Learning, this independence assumption completely breaks down in relational domains like social networks, financial transaction logs, and recommender systems. In graph-structured data, entities are explicitly coupled. Deleting a node or an edge is not a local operation; it triggers a cascade of structural updates across the network topology.
The Mechanism of Relational Leakage
Why does simple data deletion fail in graphs? The answer lies in the core operational primitive of Graph Neural Networks (GNNs): message passing.
[Node A] (Target) ---> [Node B] (1-hop neighbor) ---> [Node C] (2-hop neighbor)
| | |
(Features baked (Representation (Representation
into parameters) altered via aggregation) altered via aggregation)
During training, a GNN updates a node's representation by recursively aggregating features from its local neighborhood. If you want to delete Node A, simply removing it from the input graph before inference does not suffice. Because Node A passed its features to Node B during training, and Node B passed its updated representation to Node C, Node A's identity is already baked into the learned weights of the neural layers.
Jiali Cheng et al. demonstrate in GNNDelete: A General Strategy for Unlearning in Graph Neural Networks that this recursive aggregation leaves a persistent footprint. Zherui Yang et al. describe this phenomenon in Erase Then Rectify: A Training-Free Parameter Editing Approach for Cost-Effective Graph Unlearning as a "ghost" influence. The target data is gone from the input matrix, but its historical interactions continue to haunt the embeddings of its multi-hop neighbors.
Tracing the Ripple Effect via Graph Influence Functions
To remove this structural footprint without the massive computational expense of retraining the model from scratch, we must trace exactly how a local perturbation ripples through the network.
Standard statistical influence functions calculate how a model's parameters shift when a single training point is upweighted or removed. They assume that changing sample $i$ does not alter the loss or state of sample $j$. To overcome this limitation, Jiancan Wu et al. introduced the Graph Influence Function (GIF) in GIF: A General Graph Unlearning Strategy via Influence Function.
GIF reformulates the influence calculation by treating the deletion of a graph element as a simultaneous perturbation across a multi-hop neighborhood. Instead of evaluating an isolated gradient, it computes a total derivative that captures the structural dependencies:
$$\Delta \theta \approx - H^{-1} \sum_{j \in \mathcal{N}(i)} \frac{\partial \mathcal{L}_j}{\partial \theta}$$
where $H$ is the Hessian of the global loss function, and $\mathcal{N}(i)$ represents the structural neighborhood affected by the deletion of element $i$. By aggregating the loss gradients of all connected neighbors, the update rule effectively counteracts the historical message-passing flow. In Characterizing the Influence of Graph Elements, Zizhang Chen et al. formalized this behavior for Simple Graph Convolutions (SGC), proving that the parameter shift required for exact unlearning can be mapped directly to the structural paths of the adjacency matrix.
The Topology Wall: Hubs vs. Peripheries
The complexity of removing a structural dependency is not uniform; it is governed by the graph's topology. Eli Chien et al. demonstrated in Efficient Model Updates for Approximate Unlearning of Graph-Structured Data that a node's degree determines its unlearning complexity and privacy cost.
- Peripheral Nodes: A node with few connections passes minimal information to the rest of the network. Its influence is highly localized, making it easy to isolate and erase.
- Hub Nodes: High-degree nodes act as structural anchors. Because they participate in thousands of message-passing paths, their features are distributed globally.
In a comprehensive empirical evaluation, Bowen Fan established in OpenGU: A Comprehensive Benchmark for Graph Unlearning that removing these highly connected hubs causes approximate unlearning models to hit a scalability wall. As Samyak Jain et al. observe in Is Graph Unlearning Ready for Practice? A Benchmark on Efficiency, Utility, and Forgetting, when a core structural anchor is excised, the remaining connectivity graph changes so radically that approximate parameter adjustments degrade global model utility, often forcing a full retrain.
Certified Unlearning and Inference-Time Bypassing
To guarantee complete erasure without full retraining, researchers have converged on two primary strategies: certified parameter updates and inference-time path blocking.
Certified Graph Unlearning
To provide provable privacy guarantees, frameworks like IDEA, developed by Yushun Dong et al. in IDEA: A Flexible Framework of Certified Unlearning for Graph Neural Networks, leverage certified removal. During the initial training phase, controlled noise is injected into the GNN's aggregations or gradients. When a deletion request arrives, the framework applies a generalized Newton-step update to shift the parameters. The added noise masks any residual traces, ensuring that the final unlearned model is statistically indistinguishable from a model that was never exposed to the deleted data in the first place.
Inference-Time Path Blocking
An alternative paradigm bypasses parameter optimization entirely by recognizing that a model's "memory" of a relationship is only active if a message-passing path exists during the forward pass.
In Unlink to Unlearn: Simplifying Edge Unlearning in GNNs, Jiajun Tan et al. introduce a zero-cost approach for edge deletion. They argue that instead of modifying weights to forget a relationship, the model can simply prune the target edges from the adjacency matrix during inference. Because the forward pass is structurally restricted from propagating information along that edge, the relationship's influence is instantly neutralized, preserving the model's utility on the rest of the graph without risking the over-forgetting that plagues gradient-based optimization.
Key Foundational Work
Making AI Forget You: Data Deletion in Machine Learning (2019) — contributed 1 concept elements to this direction.
Polynomial kernelization for removing induced claws and diamonds (2015) — contributed 1 concept elements to this direction.