Research map / Graph learning / GNN architectures
Scalable and Certifiable Graph Unlearning: Overcoming the Approximation Error Barrier
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes ScaleGUN, which integrates approximate (Forward Push-based) graph propagation into certified graph unlearning for linear GNNs, proving bounded gradient-residual model error for node feature, edge, and node removals so certified (epsilon, delta) guarantees hold at billion-edge scale.
Problem
Certified graph unlearning requires re-computing graph propagation for each removal request, which is too costly for large graphs; scalable approximate propagation introduces embedding errors whose effect on certified guarantees was unclear.
Approach
A lazy local propagation framework extends dynamic PPR (InstantGNN) to Generalized PageRank so embeddings are updated locally per removal; theoretical bounds show the approximation error only adds a bounded term to the gradient residual, so the total model error can still be masked by noise perturbation for certified unlearning.
Key results
- On ogbn-papers100M, ScaleGUN removes 5,000 random edges with (epsilon,delta)=(1,1e-4) certification in about 20 seconds total (5 s embedding update) vs. 1.91 hours for retraining per the abstract.
- On ogbn-papers100M linear batch edge removal, ScaleGUN total cost 54.79 s vs. 6764.31 s for Retrain, with accuracy close to retraining (e.g., 59.82 vs 59.99 at N=0).
- On ogbn-products, ScaleGUN total cost 11.69 s vs. CGU 87.79 s and CEU 88.90 s, with propagation cost reduced to 10.81 s from 86.81-87.95 s.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ScaleGUN instead of retraining for batch edge removal | Linear model · ogbn-papers100M | total unlearning cost (s): 6764.31 -> 54.79 | Helped |
| Use ScaleGUN instead of retraining for node feature removal | Linear model · ogbn-papers100M | total unlearning cost (s): 5400.45 -> 45.29 | Helped |
| Use ScaleGUN instead of retraining for node removal | Linear model · ogbn-papers100M | total unlearning cost (s): 5201.88 -> 60.08 | Helped |
| Use ScaleGUN instead of retraining for batch edge removal | Linear model · ogbn-arxiv | test accuracy (%): 57.81 -> 57.81 | No clear effect |
| Use ScaleGUN instead of retraining for batch edge removal | Linear model · ogbn-products | test accuracy (%): 56.19 -> 56.17 | No clear effect |
| Use ScaleGUN instead of retraining for batch edge removal | Linear model · ogbn-papers100M | test accuracy (%): 59.26 -> 59.15 | No clear effect |
| Decrease r_max from 1e-5 to 1e-10 (ablation) | ScaleGUN linear model · ogbn-arxiv, initial model | test accuracy (%): 55.23 -> 57.84 | Helped |
| Decrease r_max from 1e-5 to 1e-10 (ablation) | ScaleGUN linear model · ogbn-arxiv, sequential edge removal | total unlearning cost (s): 3.30 -> 0.92 | Helped |
| Decrease r_max from 1e-5 to 1e-10 (ablation) | ScaleGUN linear model · ogbn-arxiv, sequential edge removal | propagation cost per edge removal (s): 0.72 -> 0.77 | No clear effect |
| Use ScaleGUN instead of retraining for edge removal | Decoupled model · ogbn-products | total unlearning cost (s): 174.23 -> 14.19 | Helped |
| Use ScaleGUN instead of retraining for edge removal | Decoupled model · ogbn-papers100M | total unlearning cost (s): 7958.83 -> 10.49 | Helped |
Surprising findings
- Approximation error only marginally increases the model error, so approximate propagation can be integrated into certified unlearning without breaking the guarantee.
- Setting r_max very small increases initial cost without improving accuracy; moderate r_max yields both high utility and fast unlearning.
Limitations
- Certification only for linear models with strongly convex losses; not applicable to deep GNNs without guarantees.
- Deep-model results are heuristic without certified guarantees.
- Worst-case bounds are loose compared to data-dependent bounds.
Experimental setup
Datasets: Cora Citeseer Photo ogbn-arxiv ogbn-products ogbn-papers100M
Benchmarks: Cora Citeseer Photo ogbn-arxiv ogbn-products ogbn-papers100M
Metrics: test accuracy total unlearning cost (s) propagation cost (s) Deleted Data Replay Test ratio adversarial edge accuracy
Baselines: Retrain CGU CEU GIF GNNDelete
Builds on: certified removal CGU InstantGNN SGC Generalized PageRank
Closest papers by meaning
- Erase Then Rectify: A Training-Free Parameter Editing Approach for Cost-Effective Graph Unlearning (AAAI 2025 · similarity 0.89)
- Community-Centric Graph Unlearning (AAAI 2025 · similarity 0.89)
- Towards Effective and General Graph Unlearning via Mutual Evolution (AAAI 2024 · similarity 0.86)
- Towards Scalable and Deep Graph Neural Networks via Noise Masking (AAAI 2025 · similarity 0.84)
- Bi-Directional Multi-Scale Graph Dataset Condensation via Information Bottleneck (AAAI 2025 · similarity 0.84)
- Cross-Domain Graph Data Scaling: A Showcase with Diffusion Models (NeurIPS 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.