Efficient Model Updates for Approximate Unlearning of Graph-Structured Data

Eli Chien, Chao Pan, Olgica MilenkovicICLR 2023 · OpenReview

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:

  1. 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.
  2. 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.
  3. 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.

Different types of unlearning requests in graph-structured data.

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

Abstract

With the adoption of recent laws ensuring the ``right to be forgotten'', the problem of machine unlearning has become of significant importance. This is particularly the case for graph-structured data, and learning tools specialized for such data, including graph neural networks (GNNs). This work introduces the first known approach for \emph{approximate graph unlearning} with provable theoretical guarantees. The challenges in addressing the problem are two-fold. First, there exist multiple different types of unlearning requests that need to be considered, including node feature, edge and node unlearning. Second, to establish provable performance guarantees, one needs to carefully evaluate the process of feature mixing during propagation. We focus on analyzing Simple Graph Convolutions (SGC) and their generalized PageRank (GPR) extensions, thereby laying the theoretical foundations for unlearning GNNs. Empirical evaluations of six benchmark datasets demonstrate excellent performance/complexity/privacy trade-offs of our approach compared to complete retraining and general methods that do not leverage graph information. For example, unlearning $200$ out of $1208$ training nodes of the Cora dataset only leads to a $0.1\%$ loss in test accuracy, but offers a $4$-fold speed-up compared to complete retraining with a $(\epsilon,\delta)=(1,10^{-4})$ ``privacy cost''. We also exhibit a $12\%$ increase in test accuracy for the same dataset when compared to unlearning methods that do not leverage graph information, with comparable time complexity and the same privacy guarantee.
BibTeX
@inproceedings{chien2023efficient,
  author = {Eli Chien and Chao Pan and Olgica Milenkovic},
  title = {{Efficient Model Updates for Approximate Unlearning of Graph-Structured Data}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=fhcu4FBLciL},
}
Figure