Introduction
With the adoption of privacy laws like GDPR and CCPA granting users the "right to be forgotten," machine learning models must be able to "unlearn" specific data points. While this is relatively straightforward for independent data (like images), it is incredibly difficult for graph-structured data.
In a graph, data points are interconnected. Because Graph Neural Networks (GNNs) use "message passing" to aggregate information from neighbors, the features of a single node can propagate across the entire network during training. Removing one node or edge doesn't just remove a row in a table; it potentially invalidates the embeddings of every other node in the graph. Naively retraining from scratch every time a user requests data removal is computationally prohibitive for large-scale applications like social networks or recommender systems.
This paper introduces the first framework for approximate graph unlearning with provable theoretical guarantees. By leveraging "certified removal" techniques, the authors enable the efficient removal of node features, edges, or entire nodes from GNNs without the need for costly full retraining, achieving significant speedups while maintaining high accuracy and privacy.
Methods
The authors focus on Simple Graph Convolutions (SGC) and their Generalized PageRank (GPR) extensions. These models are "linearized" versions of GNNs that remain highly competitive while being mathematically tractable for theoretical analysis.
The core approach is based on Certified Removal:
- Noisy Training: During initial training, a small amount of random noise is added to the loss function. This "masks" the specific influence of any single data point.
- Newton-like Update: When an unlearning request arrives, instead of retraining, the model weights are updated using a single step involving the Hessian (the matrix of second-order derivatives) and the gradient of the loss on the removed data.
- Privacy Budgeting: The authors derive theoretical bounds on the "gradient residual norm"—a measure of how much the updated model differs from a perfectly retrained one. If the accumulated "privacy cost" exceeds a certain budget, the model is finally retrained from scratch.
The paper specifically derives different update rules and bounds for three distinct scenarios: node feature unlearning, edge unlearning, and full node unlearning.
Key Insights
- The "Mixing" Challenge: The primary difficulty in graph unlearning is feature propagation. The authors show that the degree of the node being removed is the most critical factor; "hub" nodes with many connections are much harder (and "costlier" in terms of privacy) to unlearn than isolated nodes.
- Normalization Matters: The choice of graph normalization (e.g., using the degree matrix) is not just for performance; it's essential for unlearning. The authors prove that specific normalizations keep the influence of a single node from exploding across the graph.
- Independence from Depth: Surprisingly, for certain models, the unlearning bound is independent of the number of propagation steps ($K$), provided the right stochastic normalization is used.
- Graph Info is Essential: Methods that try to unlearn by treating graph data as independent points perform significantly worse, proving that unlearning algorithms must be graph-aware.
Evaluation and Results
The researchers evaluated their method on six widely used benchmark datasets, including citation networks (Cora, Citeseer, PubMed), large-scale graphs (ogbn-arxiv), and co-purchase networks (Amazon Computers, Amazon Photo).
- Efficiency: The proposed method offers a 4x speedup compared to complete retraining on the Cora dataset.
- Accuracy: Unlearning 200 out of 1208 training nodes on Cora resulted in only a 0.1% loss in test accuracy. Furthermore, it exhibited a 12% increase in test accuracy compared to unlearning methods that do not leverage graph information.
- Privacy: The method provides $(\epsilon, \delta)$-certified removal guarantees. In experiments, it achieved competitive performance even with a strict privacy cost of $\epsilon=1$ and $\delta=10^{-4}$.
- Robustness: The approach maintained high accuracy even when removing up to 50% of the training data in some citation networks.
Limitations and Future Work
- Model Architecture: The current theoretical proofs are limited to linear/simplified GNNs (SGC and GPR). Extending these provable guarantees to deep, non-linear GNNs with activations between every layer remains an open challenge.
- Batch Unlearning: While the paper touches on sequential requests, optimizing for large "batches" of unlearning requests simultaneously is an area for further optimization.
- Membership Inference: The authors note that even "perfect" retraining doesn't completely protect against Membership Inference (MI) attacks in graphs due to the inherent structural information, suggesting that the definition of "privacy" in graphs may need further refinement.
Summary updated