Source-linked AI summary
Unlearning on Spatio-Temporal Graphs through Subgraph Virtual Edge Reconstruction
Qiming Guo, Wenbo Sun, Chen Pan, Ye Wang, Wenlu Wang
TL;DR
Stringent privacy requirements create a need to completely unlearn revoked data from spatio-temporal graph models, where simple deletion leaves residual influence and full retraining is costly. CallosumNet partitions graphs with virtual-edge reconstruction and reconnects subgraphs through a lightweight meta-graph, achieving exact unlearning with near-gold accuracy and substantially lower reported cost.
Problem
Spatio-temporal graph models must completely unlearn revoked data, but deleting records leaves latent influence and full retraining is costly while disrupting long-range dependencies.
Method
CallosumNet uses enhanced subgraph construction with virtual edges and global ganglion bridging through a lightweight meta-graph integration layer.
Results
CallosumNet achieves exact spatio-temporal graph unlearning with near-gold accuracy; its average MAE degradation is 3.7% versus 28.9% for SISA, and Mobility unlearning time falls from 12,640 s to 3,631 s at M=16.
Takeaways & Limitations
The framework confines node influence to subgraphs while recovering global context through integration, enabling targeted updates without retraining untouched subgraphs.
Takeaways & Limitations
The approach assumes static adjacency and incurs meta-graph overhead at large M; future work targets dynamic topologies and edge- or feature-level deletion.
Abstract
from arXiv · showhide
Spatio-temporal graphs are widely used in modeling complex dynamic processes such as temporal forecasting, molecular dynamics, and healthcare monitoring. Recently, stringent privacy regulations such as GDPR and CCPA have introduced significant new challenges for existing spatio-temporal graph models, requiring complete unlearning of unauthorized data. Since each node in a spatio-temporal graph diffuses information globally across both spatial and temporal dimensions, existing unlearning methods primarily designed for static graphs and localized data removal cannot efficiently erase a single node without incurring costs nearly equivalent to full model retraining. To address this, we propose CallosumNet, a spatio-temporal graph unlearning framework biologically inspired by the corpus callosum structure. CallosumNet makes two key technical contributions: (1) it reconstructs subgraphs using biologically-inspired virtual edges; and (2) it restores interlinked spatio-temporal dependencies among subgraphs via a lightweight meta-graph integration layer. Empirical results on four diverse real-world datasets show that CallosumNet achieves complete unlearning while maintaining accuracy very close to the gold model. The code is publicly available at https://github.com/wenlu-lab/STGraphUnlearning.
1 Introduction
Spatio-temporal graph models support dynamic-process applications but must completely unlearn revoked data under privacy regulations. Simple deletion leaves latent influence, while full retraining removes it at high cost and can damage remaining graph structure; CallosumNet addresses this with subgraph reconstruction and meta-graph integration.
- Privacy regulations such as GDPR and CCPA require complete removal or unlearning of sensitive user data from deployed spatio-temporal graph models.
- Deleting revoked users’ raw records does not eliminate their latent influence on the model.
- Full retraining purges revoked influence but fragments long-range spatial and temporal paths, degrades remaining-user accuracy and interpretability, and incurs prohibitive cost.
- CallosumNet partitions the graph into locally coherent subgraphs, reconstructs cross-partition dependencies with virtual edges, and integrates them through a lightweight meta-graph layer.
2 Related Work
Existing graph-unlearning methods either approximate removal or retrain affected partitions, but partitioning can disrupt spatio-temporal dependencies. CallosumNet preserves cross-partition context with virtual ganglion edges and a learnable bridging layer.
- Approximate methods avoid full retraining but provide only approximate removal and do not explicitly handle spatio-temporal dependencies.
- Partition-based methods enable efficient or exact unlearning by retraining affected partitions, but partition boundaries can break spatial and temporal dependencies.
- CallosumNet preserves cross-partition dependencies with virtual ganglion edges and restores global context through a learnable bridging layer.
3 Methodology
CallosumNet decomposes a spatio-temporal graph into locally coherent subgraphs, reconnects partition boundaries with virtual structures, and restores global coherence through a sparse meta-graph. On deletion, only affected subgraphs and integration components are updated while untouched subgraphs remain frozen.
- Overview: CallosumNet uses Enhanced Subgraph Construction and Global Ganglion Bridging in a partition-and-integrate pipeline for spatio-temporal graph unlearning.
- Enhanced Subgraph Construction: ESC partitions the graph along a correlation-driven backbone and inserts virtual ganglion edges to preserve high-order spatial-temporal paths.
- Enhanced Subgraph Construction: ESC reconnects boundary nodes within each subgraph using K-Ring augmentation and selects the partition count by balancing correlation loss against model parallelism.
- Enhanced Subgraph Construction: The partition objective is NP-hard, while the greedy backbone provides an approximation and ESC has stated time and storage complexity bounds.
- Theoretical Analysis: The methodology states prediction-error, unlearning-stability, parameter, and computational-cost bounds for the partitioned architecture.
- Global Ganglion Bridging: GGB builds a sparse meta-graph from key, boundary, and ganglion nodes to restore global spatio-temporal dependencies across subgraphs.
- Global Ganglion Bridging: Subgraph embeddings and ganglion representations are fused through a cross-attention Transformer before producing final predictions.
- Unlearning on Demand: Upon deletion, CallosumNet removes targets in their host subgraphs, reconstructs and retrains affected subgraphs, then fine-tunes GGB while untouched subgraphs remain frozen.
4 Evaluation
CallosumNet is evaluated on four spatio-temporal datasets against partition-based unlearning baselines and a gold model retrained after deletion. It achieves substantially lower MAE degradation and faster unlearning than the reported alternatives.
- Evaluation setup: Evaluation covers four datasets spanning 23–3,220 nodes, with SISA, STEPs, GraphEraser, GraphRevoker, and a post-deletion gold model.The gold model retrains the backbone from scratch on the post-deletion graph and has zero residual influence.
- Efficiency: 3,631 s unlearning time on Mobility with M=16 compares with 12,640 s for full retraining.The Mobility dataset contains 3,220 nodes.
5 Conclusion
CallosumNet provides exact spatio-temporal graph unlearning while retaining near-gold accuracy and sub-linear unlearning cost. Its current scope assumes static adjacency, and meta-graph overhead can become substantial at large M.
- Conclusion: CallosumNet delivers exact spatio-temporal graph unlearning with near-gold accuracy and sub-linear unlearning cost.The conclusion identifies static adjacency and large-M meta-graph overhead as limitations.
- Limitations and future work: The method is limited by a static-adjacency assumption and meta-graph overhead at large M.Future work targets dynamic topologies and edge- or feature-level deletion requests.