Unlearning on Spatio-Temporal Graphs through Subgraph Virtual Edge Reconstruction

Spatio-temporal graphs are essential for modeling complex dynamic processes such as temporal forecasting, molecular dynamics, and healthcare monitoring. However, stringent privacy regulations like GDPR and CCPA mandate the complete removal of unauthorized data from trained models. In spatio-temporal graphs, each node diffuses information globally across both spatial and temporal dimensions, making unlearning particularly challenging. 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. This work addresses this gap by proposing CallosumNet, a novel framework that enables efficient and complete unlearning in spatio-temporal graphs.

CallosumNet is biologically inspired by the corpus callosum structure and makes two key technical contributions. First, it reconstructs subgraphs using biologically-inspired virtual edges. These virtual edges are introduced to capture the global diffusion patterns of spatio-temporal graphs, allowing the model to isolate and remove the influence of specific nodes. Second, it restores interlinked spatio-temporal dependencies among subgraphs via a lightweight meta-graph integration layer. This layer ensures that the unlearning process does not disrupt the overall graph structure. The framework can be formalized as follows: given a spatio-temporal graph $G=(V,E,T)$, where $V$ is the set of nodes, $E$ is the set of edges, and $T$ represents temporal dimensions, the unlearning of a node $v_u$ involves reconstructing subgraphs $G_s$ with virtual edges $E_v$ and integrating them using a meta-graph $M$. The unlearning objective is to minimize the difference between the unlearned model and a gold model trained without $v_u$, while ensuring that $v_u$'s information is completely erased. The architecture of CallosumNet is illustrated below: