Research map / Graph learning / Knowledge and temporal graphs
Efficient Unlearning for Spatio-temporal Graph (Student Abstract)
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 STEPS, a sharded spatio-temporal graph unlearning framework using spectral partitioning and weighted-average aggregation of sub-models to cut unlearning time while limiting accuracy loss on STGCN.
Problem
Efficient machine unlearning for spatio-temporal graph neural networks, where removing nodes fragments the graph and naive retraining is costly, and graph unlearning for spatio-temporal data is largely unexplored.
Approach
STEPS partitions the graph (spectral partitioning by default) into shards, trains sub-models per shard, and aggregates them via weighted averaging to preserve spatio-temporal information, so only affected shard sub-models need updating when nodes are removed; a complexity formula guides the number of shards and sub-model scale.
Key results
- STEPS with spectral partitioning and weighted-average aggregation consistently achieves the best RMSE across node removal rates of 5%, 10%, and 15%, as reported in Table 1.
- Figure 2 shows STEPS significantly reduces sub-model update time versus full retraining for 4 and 10 shards.
- Aggregation time for weighted average is 1.642 ms, versus 1.469 ms for mean, 4.228 ms for median, and 2.06 ms for MLP.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use Spectral partitioning instead of Louvain or Metis (ablation) | STEPS with STGCN · RWW dataset and PEMS08 | RMSE | Helped |
| use Weighted Average aggregation instead of Mean, Median, or MLP (ablation) | STEPS with STGCN · RWW dataset and PEMS08 | RMSE | Helped |
| use STEPS sub-model updates instead of full model retraining | STGCN · RWW dataset and PEMS08 | unlearning time | Helped |
Surprising findings
- Aggregation method choice causes marked accuracy variation even though aggregation takes a minimal share of total unlearning time.
Limitations
- Complexity weights alpha, beta, gamma are determined by empirical testing rather than a principled rule.
- Only one spatio-temporal model (STGCN) and two datasets are evaluated.
- The paper itself notes that more advanced aggregation techniques could further improve accuracy.
Experimental setup
Datasets: PEMS08 RWW (real-world urban water system dataset, collected over four months)
Benchmarks: PEMS08 RWW
Metrics: RMSE unlearning time aggregation time
Baselines: full model retraining Louvain partitioning Metis partitioning Mean aggregation Median aggregation MLP aggregation
Builds on: SISA (Bourtoule et al. 2021) STGCN
Closest papers by meaning
- Towards Effective and General Graph Unlearning via Mutual Evolution (AAAI 2024 · similarity 0.88)
- Community-Centric Graph Unlearning (AAAI 2025 · similarity 0.88)
- Erase Then Rectify: A Training-Free Parameter Editing Approach for Cost-Effective Graph Unlearning (AAAI 2025 · similarity 0.87)
- A Cognac Shot To Forget Bad Memories: Corrective Unlearning for Graph Neural Networks (ICML 2025 · similarity 0.87)
- Over-squashing in Spatiotemporal Graph Neural Networks (NeurIPS 2025 · similarity 0.86)
- STRAP: Spatio-Temporal Pattern Retrieval for Out-of-Distribution Generalization (NeurIPS 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.