Research map / Graph learning / GNN architectures

Erase Then Rectify: A Training-Free Parameter Editing Approach for Cost-Effective Graph Unlearning

AAAI 2025 · Graph learning › GNN architectures · approach: Robustness, privacy, and fairness of GNNs · 5 citations (OpenAlex)

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 ETR, a training-free two-stage graph unlearning method that edits GNN parameters identified via Fisher information (Erase) and then takes one gradient step using an approximated remaining-data gradient (Rectify).

Problem

Graph unlearning removes the influence of nodes, edges, or features from a trained GNN while preserving utility, but existing methods typically require additional training on the remaining data, which is costly on large graphs.

Approach

Identify parameters critical to the unlearned set and its k-hop neighborhood using diagonal Fisher information, scale them down via a neighborhood-aware editing rule (Erase), then approximate the remaining-data gradient from stored full-data gradients and the induced subgraph of the unlearned nodes, and apply one gradient-descent step (Rectify), with no retraining.

Key results

• On node unlearning with GCN on PubMed, ETR achieves F1 89.48±0.34 vs. 89.74±0.27 for Retrain, at 0.02 s vs. 39.1 s runtime.
• ETR reports on average 4583.9x less time and 4.2x less memory than retraining from scratch (abstract claim).
• On ogbn-arxiv with GCN, ETR reaches F1 66.4 vs. 67.5 for Retrain at 0.08 s vs. 152 s, and it is the only method among those listed that completes ogbn-products with GCN at 73.8 F1 (Retrain 73.6).

Measured effects reported in the paper

Surprising findings

• ETR's model utility sometimes exceeds the Retrain baseline (e.g., Cora with GCN in edge unlearning and ogbn-products), attributed to the Rectify step.

Limitations

• Gradient on the remaining data is only approximated, with reported relative differences up to 0.36 on CS.
• Memory overhead advantage is limited on small datasets, where model parameters dominate.
• Hyperparameters (m, lambda, a, b) require tuning per dataset; the adaptive top-m% selection is a heuristic.

Experimental setup

Datasets: PubMed CiteSeer Cora CS Physics ogbn-arxiv ogbn-products

Benchmarks: PubMed CiteSeer Cora CS Physics ogbn-arxiv ogbn-products

Metrics: F1 score running time memory overhead parameter distance to Retrain attack-based unlearning utility

Baselines: Retrain GraphEraser-BEKM GraphEraser-BLPA GIF GUIDE-SR GUIDE-Fast GNNDelete MEGU

Builds on: SSD GIF MEGU GraphEraser

Closest papers by meaning

• Community-Centric Graph Unlearning (AAAI 2025 · similarity 0.92)
• Towards Effective and General Graph Unlearning via Mutual Evolution (AAAI 2024 · similarity 0.92)
• A Cognac Shot To Forget Bad Memories: Corrective Unlearning for Graph Neural Networks (ICML 2025 · similarity 0.90)
• Scalable and Certifiable Graph Unlearning: Overcoming the Approximation Error Barrier (ICLR 2025 · similarity 0.89)
• Efficient Unlearning for Spatio-temporal Graph (Student Abstract) (AAAI 2025 · similarity 0.87)
• Gradient Rewiring for Editable Graph Neural Network Training (NeurIPS 2024 · similarity 0.86)