Source-linked AI summary
Spatial Entropy based Partitioning for Spatiotemporal Graph Unlearning
Qiming Guo, Wenbo Sun, Ye Wang, Wenlu Wang
TL;DR
ST-graph unlearning must remove a node’s influence exactly despite global spatial-temporal propagation, which otherwise makes full-graph retraining costly. IsleNet uses entropy-guided partitioning and decoupled virtual edges to localize retraining, reaching up to 94% of full-graph accuracy and up to 12× faster unlearning. Its exactness claim is defined relative to retraining from scratch under the same partition and training protocol.
Problem
ST-graph unlearning must completely remove deleted data’s influence while remaining fast and preserving post-unlearning accuracy despite global spatial-temporal message passing.
Method
IsleNet partitions graphs into entropy-verified subgraphs, independently trains their encoders, and connects them with lightweight virtual edges trained after the encoders are frozen.
Results
94% of full-graph accuracy is achieved while unlearning time is reduced by up to 12× across four real-world datasets and four ST-GNN backbones, outperforming five baselines.
Takeaways & Limitations
Localized retraining confines deletion to the affected subgraph encoder and virtual-edge layer while preserving global information flow.
Takeaways & Limitations
Exactness is defined relative to retraining from scratch under the same partition and training protocol on the graph with the requested data excluded.
Abstract
from arXiv · showhide
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.
1 Introduction.
ST-graph unlearning must remove deleted influence exactly despite global spatial-temporal propagation, while remaining efficient and accurate. IsleNet addresses this with entropy-balanced subgraphs and lightweight virtual edges, achieving strong accuracy and faster unlearning.
- Motivation: Global spatial and temporal message passing makes deleting one node’s influence costly because residual paths can leak deleted data.Exactness requires complete influence removal, while efficiency requires fast unlearning without sacrificing post-unlearning accuracy.
- Method: Spatial entropy verifies balanced, locally coherent partitions so subgraph encoders avoid degenerate clusters.Redistribution is triggered when normalized partition entropy indicates that balance fails.
- Method: IsleNet trains independent subgraph encoders, then optimizes lightweight virtual edges to restore severed cross-subgraph dependencies.The virtual-edge layer is structurally decoupled from the encoders, enabling localized retraining after deletion.
- Results: 94% of full-graph accuracy is achieved while unlearning time is reduced by up to 12× across four real-world datasets and four ST-GNN backbones.IsleNet outperforms five baselines.
2 Related Work.
Prior unlearning methods include exact shard retraining and approximate parameter modification, but spatiotemporal forecasting introduces temporal message passing that amplifies residual influence. IsleNet applies entropy-verified partitioning and decoupled virtual edges to this setting.
- General-purpose unlearning: Exact unlearning methods retrain affected data shards, whereas approximate methods modify trained parameters directly.Examples include SISA-style partitioning, deletion-efficient k-means, certified removal, and Fisher-information weight scrubbing.
- Spatiotemporal graph unlearning: Existing spatiotemporal approaches address forecasting unlearning but may lack formal deletion proofs or require preset partition scales.STEPS uses spectral partitioning and weighted aggregation, while Graph Revoke targets dynamic edges in continuous-time graphs.
- Spatial entropy: No prior work identified in the paper applies entropy-based criteria to verify partition quality in spatiotemporal graph unlearning.Spatial entropy had previously been used to measure the evenness of point distributions in geographic information science.
- IsleNet: IsleNet combines locally coherent subgraphs with decoupled virtual edges so unlearning retrains only the affected encoder and virtual-edge layer.Its two-stage protocol first trains encoders independently, then trains virtual edges for long-range dependencies.
3 Method.
IsleNet partitions a spatiotemporal graph into balanced, locally coherent subgraphs, trains independent encoders, and reconnects them with virtual edges. Spatial entropy verifies partition quality, while localized retraining and virtual-edge reconstruction support exact unlearning.
- Spatial-Entropy-Guided Partitioning: Spatial entropy measures node distribution across discretized spatial regions, with normalized partition entropy ranging from degenerate imbalance to comparable spatial extent.A partition is accepted when normalized entropy reaches 1 − ϵ; otherwise, nodes are redistributed.
- Spatial-Entropy-Guided Partitioning: IsleNet partitions the graph into disjoint subgraphs and minimizes inter-subgraph cuts subject to entropy-based balance constraints.Each subgraph retains dense internal connectivity while avoiding collapsed clusters.
- Efficient Unlearning Protocol: During unlearning, only affected subgraph encoders are retrained, while virtual edges are removed or re-optimized and unaffected encoders remain unchanged.The protocol bounds the post-unlearning loss increase by O(γ Σi∈Saffected Li) with at most M affected subgraphs.
- Spatial-Entropy-Guided Partitioning: When balance is insufficient, IsleNet moves distant nodes from the lowest-entropy subgraph to an eligible higher-entropy subgraph and recomputes the criterion.The procedure stops at ¯HP ≥ 1 − ϵ or after three iterations, then falls back to size-balanced random partitioning if needed.
- Subgraph-Independent Spatiotemporal Encoding: Each subgraph uses an independent spatiotemporal encoder with gradient-isolated optimizers, preventing parameters outside the affected subgraph from depending on deleted nodes.The encoder processes local features and edges, combining graph convolutions for spatial modeling with recurrent units for temporal modeling.
- Virtual Edge Construction: Virtual edges use influential PageRank-selected nodes to restore intra- and inter-subgraph information flow through attention-based aggregation and an MLP.The enhanced representation combines concatenated subgraph embeddings with projected virtual-edge features using residual scaling.
4 Experiments.
Across four datasets and four ST-GNN backbones, IsleNet remains close to full-graph performance while substantially reducing unlearning cost. Its entropy-verified partitioning, virtual edges, staged training, and localized retraining each contribute to the observed accuracy and efficiency.
- Experimental Setup: IsleNet evaluates four spatiotemporal datasets, ranging from 23 to 3,220 nodes, with metrics, runtime, memory, and CPU costs reported.The setup includes RWW, PeMS08, Global Weather, and Human Mobility Flow.
- Prediction Performance: At 0% unlearning, IsleNet reaches approximately 94% of full-graph performance on PeMS08 and nearly matches Scratch on Weather.On PeMS08 with STGCN, MAE is 30.532 ± 0.045 versus Scratch’s 28.751 ± 0.117; Weather reports 3.603 ± 0.016 versus 3.597 ± 0.014.
- Prediction Performance: At 10% unlearning, IsleNet remains comparable to Scratch-90%, with a ∼2.4% PeMS08 MAE gap and similarly modest increases on RWW and Weather.The PeMS08 comparison is 31.564 ± 0.121 versus 30.810 ± 0.147.
- Prediction Performance: Across datasets, backbones, and unlearning rates, IsleNet is closest to Scratch, scoring 95.4% bounded similarity and 95.7% ratio score.SISA follows at 86.2%/89.5%, while other baselines fall below 72% on both measures.
- Ablation Study: Ablations show that random partitioning raises MAE by 49.5%/58.2%, removing virtual edges costs 15.7%/26.2%, and joint training raises MAE by over 25%.These changes correspond to 0%/10% unlearning for partitioning and virtual-edge comparisons, while joint training is attributed to gradient interference.
- Efficiency and Capacity: On PeMS08 with 10% node unlearning, IsleNet reduces unlearning time from ∼60 seconds to ∼5 seconds at M=4, a ∼12× wall-clock speedup.At M=16, unlearning drops to ∼4 seconds while training is ∼380 seconds.