Spatial Entropy based Partitioning for Spatiotemporal Graph Unlearning

Qiming Guo; Wenbo Sun; Ye Wang; Wenlu Wang

cs.LGAug 29, 2026

Spatial Entropy based Partitioning for Spatiotemporal Graph Unlearning

Authors: Qiming Guo, Wenbo Sun, Ye Wang, Wenlu Wang

Organizations: Texas A&M University - Corpus Christi, Corpus Christi, TX, USA · Delft University of Technology, Netherlands · Biogen, Cambridge, MA, USA

Abstract

Spatiotemporal graphs underpin applications such as traffic forecasting, weather forecasting, and healthcare monitoring. Privacy regulations such as the GDPR and the CCPA require the complete removal of unauthorized data from trained models, but achieving this on a spatiotemporal graph is difficult: because information propagates globally through both spatial and temporal message passing, fully erasing a node's influence forces costly full-graph retraining. ST-graph unlearning requires both exactness and efficiency. We propose IsleNet, which uses spatial-entropy-guided partitioning to create balanced, locally coherent subgraphs and reconnects them with lightweight virtual edges. Upon an unlearning request, only the affected subgraph encoder and virtual-edge layer are retrained, ensuring exact removal with low cost. Experiments on four real-world benchmarks show that IsleNet attains up to 94% of full-graph accuracy while reducing unlearning time by up to an order of magnitude. Our code is publicly available at https://github.com/wenlu-lab/STGraphUnlearning.

Figures & tables

Figure 1.1: The challenge of unlearning on spatiotemporal graphs. (a) In a complete ST-graph, walks propagate node influence globally (e.g., $v_{4}$ reaches $v_{5}$ via Walk C; $v_{3}$ lies on Walks A and B). (b) Target nodes are marked for unlearning ( UN ), blocking every walk through them. (c) After removal, Walk A no longer reaches $v_{1}$ or $v_{3}$ , Walk B no longer reaches $v_{2}$ , and uninvolved $v_{4}$ loses all outgoing paths, a structural cascade. (d) Retraining the fragmented graph alters the remaining node features ( $v_{1},v_{2},v_{3},v_{5}$ ) and fades the walk halos that encode global context, while costing as much as full training. ST-graph unlearning must therefore be exact (deleted influence fully removed) and efficient (fast without sacrificing post-unlearning accuracy).

Figure 3.1: Spatial entropy in IsleNet. Top: Spatial entropy $H_{s}$ (Eq. 3.2 ) quantifies how a subgraph’s nodes are distributed across space. (a) Low: nodes concentrate in narrow regions. (b) High: nodes spread uniformly. Bottom: IsleNet uses spatial entropy to verify partition quality: blue and red halos mark the two subgraphs, and the dashed line separates them. (c) A degenerate partition: one subgraph shrinks to a small corner, so IsleNet detects the imbalance and redistributes nodes. (d) A balanced partition: both subgraphs cover comparable spatial extents.

Figure 3.2: Framework of IsleNet. (a) The original graph. (b) Split into smaller subgraphs, each with its own encoder. (c) Virtual edges (green) reconnect subgraphs; on a deletion request, edges touching the target are marked for removal (RM). (d) Only the affected subgraph is retrained and virtual edges are rebuilt; other subgraphs stay untouched. How it works: Spatial entropy guides the split so no subgraph degenerates. Each encoder trains in isolation, and virtual edges stitch subgraphs back together. To unlearn, IsleNet retrains only the affected encoder and rebuilds the virtual edges from scratch. Untouched subgraphs keep their weights, making unlearning fast and exact.

Dataset	Model	Scratch-100%	Baseline Methods				IsleNet
Dataset	Model	Scratch-100%	SISA	STEPS	GraphEraser	GraphRevoker	IsleNet
RWW	STGCN	0.020 $\pm$ 0.001	0.035 $\pm$ 0.007	0.082 $\pm$ 0.003	0.179 $\pm$ 0.060	0.177 $\pm$ 0.000	0.024 $\pm$ 0.001
	ST-GAT	0.022 $\pm$ 0.002	0.035 $\pm$ 0.013	0.075 $\pm$ 0.004	0.179 $\pm$ 0.059	0.177 $\pm$ 0.001	0.025 $\pm$ 0.001
	ST-GATV2	0.022 $\pm$ 0.002	0.036 $\pm$ 0.008	0.085 $\pm$ 0.008	0.179 $\pm$ 0.059	0.177 $\pm$ 0.001	0.024 $\pm$ 0.001
	ST-SAGE	0.022 $\pm$ 0.003	0.036 $\pm$ 0.010	0.081 $\pm$ 0.008	0.179 $\pm$ 0.059	0.178 $\pm$ 0.000	0.025 $\pm$ 0.001
PeMS08	STGCN	28.751 $\pm$ 0.117	34.271 $\pm$ 0.527	82.404 $\pm$ 9.043	58.994 $\pm$ 1.663	88.685 $\pm$ 5.865	30.532 $\pm$ 0.045

Table 4.1: Prediction Performance of Different Methods Before Unlearning (0% Unlearning).

Dataset	Model	Scratch-90%	Baseline Methods				IsleNet
Dataset	Model	Scratch-90%	SISA	STEPS	GraphEraser	GraphRevoker	IsleNet
RWW	STGCN	0.023 $\pm$ 0.001	0.036 $\pm$ 0.007	0.095 $\pm$ 0.022	0.188 $\pm$ 0.067	0.178 $\pm$ 0.006	0.025 $\pm$ 0.002
	ST-GAT	0.023 $\pm$ 0.001	0.038 $\pm$ 0.006	0.097 $\pm$ 0.025	0.188 $\pm$ 0.080	0.178 $\pm$ 0.005	0.026 $\pm$ 0.003
	ST-GATV2	0.024 $\pm$ 0.002	0.035 $\pm$ 0.003	0.090 $\pm$ 0.023	0.188 $\pm$ 0.081	0.177 $\pm$ 0.005	0.026 $\pm$ 0.002
	ST-SAGE	0.023 $\pm$ 0.002	0.037 $\pm$ 0.011	0.092 $\pm$ 0.023	0.188 $\pm$ 0.085	0.178 $\pm$ 0.005	0.026 $\pm$ 0.003
PeMS08	STGCN	30.810 $\pm$ 0.147	34.332 $\pm$ 0.515	99.807 $\pm$ 12.190	61.315 $\pm$ 4.643	97.568 $\pm$ 3.789	31.564 $\pm$ 0.121

Table 4.2: Prediction Performance of Different Methods After Unlearning (10% Unlearning).

Method	Bounded Sim (%)	Ratio Score (%)
SISA	86.22	89.51
STEPS	50.81	67.15
GraphEraser	58.26	71.35
GraphRevoker	52.39	65.16
IsleNet	95.35	95.65

Table 4.3: Average similarity to Scratch models (higher is better). Computed across 4 datasets, 4 backbones, and 2 unlearning rates (0% and 10%).

Baselines
Configuration	0% Unl. MAE	10% Unl. MAE
Full Graph (Scratch)	28.751	–
Retrained Graph (90%)	–	30.810
IsleNet Variants
Full IsleNet	30.532	31.564
Random Part.	45.635	49.938

Table 4.4: Ablation study on PeMS08 with STGCN.

Graph Partitioning

See all 12 papers

Unlearning on Spatio-Temporal Graphs through Subgraph Virtual Edge Reconstruction
Aug 29, 2026Qiming Guo, Wenbo Sun, Chen Pan +2Graph Unlearning Machine Unlearning
Texas A&M University - Corpus Christi Corpus Christi, Texas, USA · Delft University of Technology Delft, Netherlands · University of Texas at San Antonio San Antonio, Texas, USA +1
CUNO: Curriculum and Preference Optimization for Stable Graph Unlearning under Mass Deletion
Sep 8, 2026Chenhan Zhang, Ali Braytee, Madhushi Bandara +4Graph Unlearning Preference Optimization
University of Technology Sydney
Attack by Unlearning: Unlearning-Induced Adversarial Attacks on Graph Neural Networks
Mar 19, 2026Jiahao Zhang, Yilong Wang, Suhang WangGraph Unlearning Adversarial Attacks
The Pennsylvania State University University Park, PA, USA

Aug 29, 2026J/K move · Enter open · S save

Unlearning on Spatio-Temporal Graphs through Subgraph Virtual Edge Reconstruction

Qiming Guo, Wenbo Sun, Chen Pan, Ye Wang+1

Texas A&M University - Corpus Christi Corpus Christi, Texas, USA · Delft University of Technology Delft, Netherlands · University of Texas at San Antonio San Antonio, Texas, USA+1

Graph Unlearning Machine Unlearning Spatiotemporal GNNs

Open paper AskPDF arXiv

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.

Abstract

Graph Partitioning

Explore similar work

Unlearning on Spatio-Temporal Graphs through Subgraph Virtual Edge Reconstruction

CUNO: Curriculum and Preference Optimization for Stable Graph Unlearning under Mass Deletion

Attack by Unlearning: Unlearning-Induced Adversarial Attacks on Graph Neural Networks