Research map / Graph learning / GNN architectures
Community-Centric Graph Unlearning
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 GSMU, a graph structure mapping unlearning paradigm, and CGE, which maps Louvain/OSLOM community subgraphs to nodes of a reduced mapped graph so unlearning can be done at node level, evaluated on four datasets with GCN, GAT and GraphSAGE.
Problem
Deterministic graph unlearning methods based on balanced partition-submodel training-aggregation (BP-SM-TA) lose structural information between shards and incur high model complexity and unlearning parameter cost.
Approach
Map each detected community subgraph to a single mapped node (with PCA-based feature fusion and distance-filtered majority-vote labels) and connect mapped nodes by a robustness-scored edge, so unlearning requests only trigger recomputation of affected mapped nodes and edges rather than retraining many submodels.
Key results
- On Reddit, CGE reports average Macro F1 gains of 11.56% over GUIDE and 33.24% over GraphEraser (per the text).
- Unlearning time on CS drops to 9.33 s for CGE versus 62.56 s for GraphEraser and 71.60 s for GUIDE (Table 3).
- Membership inference AUC on CGE falls to roughly 48.8-52.1% across datasets and backbones, versus 63-79% on the original backbones.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use CGE instead of the strongest reported deterministic unlearning baseline | Node classification with SAGE, GAT, and GCN · Cora, Citeseer, CS, and Reddit | Macro F1 | Helped |
| Use CGE instead of GUIDE | CGE · Citeseer (SAGE) | Macro F1: 0.7271 ± 0.0022 -> 0.7170 ± 0.0103 | Hurt |
| Use CGE instead of GUIDE | CGE · CS (GCN) | model deployment time: 745.10 -> 747.82 | Hurt |
| Use CGE rather than the best baseline shown for each dataset | CGE · Cora, Citeseer, CS, and Reddit | unlearning time: 10.11 -> 8.12; 11.07 -> 9.58; 62.56 -> 9.33; 3128.22 -> 49.52 | Helped |
| Replace Louvain-OSLOM community partitioning with balanced K-means (BEKM) (ablation) | CGE · Four datasets | Macro F1 | Hurt |
| Use Louvain-OSLOM rather than BEKM for partitioning (ablation) | CGE · Community structure | conductance | Helped |
| Use Infomap rather than OSLOM for community detection (ablation) | CGE · Four datasets | Macro F1 | Hurt |
| Use SLPA rather than OSLOM for community detection (ablation) | CGE · Reddit | partition time | Hurt |
Surprising findings
- CGE sometimes outperforms Scratch (full retraining), e.g., on Cora with SAGE (0.8745 vs 0.7638) and Reddit with SAGE, which the authors attribute to pre-integration of similar data within communities.
Limitations
- Relies on traditional community detection (OSLOM), which the authors say struggles on large-scale graphs; Reddit model deployment is still slower than some baselines (18,144 s vs 39,065 s for GUIDE but slower than Scratch's 13,049 s).
- Evaluated only on node classification with four datasets and three GNN backbones.
- Efficiency and utility claims rest on a single hardware setup (NVIDIA Tesla A800).
Experimental setup
Datasets: Cora Citeseer CS Reddit
Benchmarks: Cora Citeseer CS Reddit
Metrics: Macro F1 time cost (s) membership inference AUC information retention conductance class imbalance entropy/IR/Gini
Baselines: Scratch SISA GraphEraser GUIDE
Builds on: SISA GraphEraser GUIDE Louvain OSLOM
Closest papers by meaning
- Erase Then Rectify: A Training-Free Parameter Editing Approach for Cost-Effective Graph Unlearning (AAAI 2025 · similarity 0.92)
- Towards Effective and General Graph Unlearning via Mutual Evolution (AAAI 2024 · similarity 0.89)
- Scalable and Certifiable Graph Unlearning: Overcoming the Approximation Error Barrier (ICLR 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)
- The Map Equation Goes Neural: Mapping Network Flows with Graph Neural Networks (NeurIPS 2024 · similarity 0.85)
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.