Research map / Graph learning / Graph self-supervised learning
Towards Effective and General Graph Unlearning via Mutual Evolution
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 MEGU, a graph unlearning framework where a predictive module (initialized from the original GNN) and a linear unlearning module co-evolve via mutual losses, with adaptive high-influence neighborhood selection and topology-aware unlearning propagation.
Problem
Graph unlearning must remove the influence of deleted features, nodes, or edges while preserving predictive accuracy on remaining nodes; existing methods are architecture-dependent, handcrafted, costly, or sacrifice performance.
Approach
Treats unlearning as two mutually evolving modules: a predictive module (the adjusted original GNN) trained with CE on high-influence nodes plus KL to the unlearning output, and a linear unlearning module that uses topology-aware propagation of the predictive module's outputs to make predictions and forget unlearning entities via reverse CE.
Key results
- MEGU outperforms GNNDelete by 2.8%-6.4% in predictive accuracy with 4.5x-7.2x training speedups (per paper's contribution statement).
- On Cora with GCN node unlearning, MEGU reaches 85.2% F1 versus 85.6% for Retrain, at 0.2 s vs 14.5 s training time.
- Abstract reports average time and space overhead reductions of 159.8x and 9.6x versus retraining from scratch.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add adaptive HIN selection (ablation) | MEGU · CiteSeer feature unlearning with GAT | F1 Score: 72.8±0.3 -> 74.3±0.2 | Helped |
| Add adaptive HIN selection (ablation) | MEGU · Cora feature and edge; CiteSeer feature and edge unlearning with GCN, GAT, and GIN | F1 Score | Mixed |
| Add topology-aware unlearning propagation (ablation) | MEGU · Cora and CiteSeer feature and edge unlearning with GCN, GAT, and GIN | F1 Score | Mixed |
| Use mutual evolution rather than independent predictive and unlearning modules (ablation) | MEGU · graph unlearning | convergence speed | Helped |
| Increase κ | MEGU · feature, node, and edge unlearning | predictive performance | Hurt |
| Increase κ | MEGU · Edge Attack | accuracy | Helped |
Surprising findings
- MEGU sometimes outperforms full retraining (Retrain), which the authors attribute to removed entities harming the retrained model.
Limitations
- Results on PPI omit the topology-aware propagation module because multi-label propagation was judged unsuitable.
- Hyperparameters (alpha, kappa) are tuned per dataset, and some reported gains are small relative to variance.
- CGU runs out of time on Flickr, so comparisons are incomplete for that baseline.
Experimental setup
Datasets: Cora CiteSeer PubMed Amazon Photo Amazon Computers Coauthor CS Coauthor Physics PPI Flickr
Benchmarks: Cora CiteSeer PubMed Amazon Photo Amazon Computers Coauthor CS Coauthor Physics PPI Flickr
Metrics: Micro-F1 training time edge attack robustness
Baselines: Retrain GraphEraser GUIDE CGU GIF Projector GNNDelete Eraser-LPA Eraser-KMeans
Builds on: GIF GNNDelete GraphEraser PPR-based label propagation
Closest papers by meaning
- Erase Then Rectify: A Training-Free Parameter Editing Approach for Cost-Effective Graph Unlearning (AAAI 2025 · similarity 0.92)
- Community-Centric Graph Unlearning (AAAI 2025 · similarity 0.89)
- A Cognac Shot To Forget Bad Memories: Corrective Unlearning for Graph Neural Networks (ICML 2025 · similarity 0.88)
- Efficient Unlearning for Spatio-temporal Graph (Student Abstract) (AAAI 2025 · similarity 0.88)
- Scalable and Certifiable Graph Unlearning: Overcoming the Approximation Error Barrier (ICLR 2025 · similarity 0.86)
- When to Forget? Complexity Trade-offs in Machine Unlearning (ICML 2025 · similarity 0.86)
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.