Efficient Unlearning for Spatio-temporal Graph (Student Abstract)

Qiming Guo, Chen Pan, Hua Zhang, Wenlu WangAAAI 2025 · DOI

Introduction

As privacy regulations like the General Data Protection Regulation (GDPR) grant users the "right to be forgotten," machine unlearning has become a critical area of research. The goal is to remove the influence of specific training data points from a pre-trained model without the prohibitive computational cost of retraining from scratch. While unlearning techniques have matured for images and simple graphs, Spatio-temporal Graphs (STGs)—used in vital applications like traffic forecasting and urban water management—present unique structural challenges.

STGs rely on both spatial relationships (node connectivity) and temporal continuity (data evolution over time). Simply deleting a node can "fragment" the graph, destroying critical structural information and degrading model performance. To address this, we introduce STEPS, a framework designed for efficient machine unlearning in complex spatio-temporal systems.

The STEPS Framework

The STEPS framework (Spatio-Temporal graph complexity Evaluation, Partition-aggregation strategy, and Sub-model scale) operates in three distinct phases to preserve data integrity while enabling rapid updates:

  1. Complexity Evaluation: The system calculates a complexity score ($C$) based on nodes, edges, time steps, and features. This score dictates the optimal granularity for partitioning the graph into "shards."
  2. Spectral Partitioning: Unlike standard community detection, STEPS utilizes spectral partitioning. By leveraging the eigenstructure of the graph Laplacian, it splits the graph into subgraphs that preserve the most critical spatial and temporal dependencies.
  3. Weighted Aggregation: Sub-models are trained independently on these shards. When an unlearning request occurs, only the affected sub-model is retrained. The outputs are then recombined using a weighted average, which maintains higher accuracy than simple means or complex neural network aggregators.
The STEPS framework visualizes the transition from an original graph to a fragmented state after node removal, followed by a reconstructed state using sub-model aggregation.

Experimental Evaluation

The framework was evaluated using two real-world datasets: RWW (Real-world Water system) and PEMS08 (traffic flow forecasting). To simulate varying unlearning demands, researchers tested the removal of 5%, 10%, and 15% of the graph's nodes.

Key Insights

  • The Partitioning Paradox: There is a trade-off between speed and accuracy. High partitioning (more shards) accelerates unlearning but risks losing global structural information. STEPS uses its complexity formula to identify the "Goldilocks" zone for shard count.
  • Spectral Superiority: Comparing spectral partitioning against Louvain and Metis methods revealed that spectral partitioning is significantly more effective at capturing the mathematical eigenstructure inherent in spatio-temporal data.
  • Simplicity in Aggregation: While Multi-Layer Perceptron (MLP) aggregators are common, the study found that a simple weighted average provided the best balance of predictive accuracy and computational speed.

Results and Discussion

STEPS demonstrates a dramatic reduction in unlearning time compared to traditional retraining. As shown in the performance metrics, retraining from scratch requires approximately 92 seconds. In contrast, the STEPS framework using 10 shards and spectral partitioning completes the update in roughly 10 seconds—representing a nearly 9x speedup.

Unlearning time comparison showing that STEPS (particularly with 10 shards) significantly reduces processing time compared to retraining from scratch (red dashed line).

Crucially, this speed is achieved with minimal impact on accuracy. Using the Spectral + Weighted Average configuration, the Root Mean Square Error (RMSE) remained the lowest across all tested node removal rates (e.g., 0.585 on the RWW dataset). Furthermore, the overhead for the aggregation step itself is negligible, taking only 1.6 to 4.2 milliseconds.

Conclusion and Future Work

STEPS provides a robust solution for the "right to be forgotten" in spatio-temporal contexts, offering a scalable alternative to full model retraining. While the current framework utilizes the STGCN (Spatio-Temporal Graph Convolutional Network) architecture, future research will explore how STEPS generalizes across other architectures, such as Graph Transformers, and investigate even more advanced aggregation techniques to further refine accuracy.

Summary updated

BibTeX
@inproceedings{guo2025efficient,
  author = {Qiming Guo and Chen Pan and Hua Zhang and Wenlu Wang},
  title = {{Efficient Unlearning for Spatio-temporal Graph (Student Abstract)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i28.35259},
}
Figure