Spatial Entropy based Partitioning for Spatiotemporal Graph Unlearning

# Spatial Entropy based Partitioning for Spatiotemporal Graph Unlearning
Source: [https://arxiv.org/html/2608.29360](https://arxiv.org/html/2608.29360)
###### 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](https://github.com/wenlu-lab/STGraphUnlearning)\.

Key words:machine unlearning, graph unlearning, spatiotemporal graph unlearning, spatial entropy, graph neural networks, privacy\-preserving learning\.

## 1Introduction\.

Privacy regulations such as the GDPR\[[9](https://arxiv.org/html/2608.29360#bib.bib13)\]and the CCPA\[[3](https://arxiv.org/html/2608.29360#bib.bib14)\]grant individuals the right to have their data erased from trained machine learning models\. For spatiotemporal graph neural networks \(ST\-GNNs\), which underpin applications from traffic forecasting to healthcare monitoring, honoring such requests is particularly difficult\. To fully erase the influence of a requested node, the standard recourse is to retrain the entire ST\-graph from scratch, because every node’s features propagate globally through both spatial and temporal message passing, and any residual path can leak the deleted data back into the model\. But full retraining has two severe consequences \(Figure[1\.1](https://arxiv.org/html/2608.29360#S1.F1)\): it breaks the information\-propagation walks that hold the ST\-graph together and can even structurally isolate nodes that were never requested for deletion, and it costs as much time and compute as training the original model\. Spatiotemporal graph unlearning therefore requires simultaneously meeting two goals: exactness, meaning the deleted data’s influence must be completely removed, and efficiency, meaning the process must be fast without sacrificing post\-unlearning accuracy\.

A natural remedy is to partition the graph into independent subgraphs, train each in isolation, and retrain only affected partitions upon deletion\. Spectral clustering\[[27](https://arxiv.org/html/2608.29360#bib.bib11)\]groups topologically tight nodes into locally coherent subgraphs \(Figure[3\.1](https://arxiv.org/html/2608.29360#S3.F1)\), letting each encoder exploit dense local message passing\. The remaining challenge is balance: if one subgraph collapses to a trivially small cluster its encoder degenerates\. We use spatial entropy as the verification criterion, since a well\-balanced partition produces subgraphs of comparable entropy, and our normalized partition entropyH¯𝒫\\bar\{H\}\_\{\\mathcal\{P\}\}triggers redistribution when balance fails\.

We propose IsleNet \(Island Network for Unlearning Spatiotemporal Graphs\)\. In Stage 1, the ST\-graph is partitioned intoMMentropy\-verified subgraphs using spatial\-entropy\-guided partitioning, each trained by an independent encoder with gradient\-isolated optimizers\. In Stage 2, encoders are frozen and lightweight virtual edges are optimized to compensate for severed cross\-subgraph dependencies\. Because the virtual edges are structurally decoupled from the encoders, an unlearning request only retrains the affected subgraph encoder and the virtual\-edge layer, achieving exact localized deletion\. This design simultaneously satisfies both exactness and efficiency on spatiotemporal graphs\. Our main contributions are:

![Refer to caption](https://arxiv.org/html/2608.29360v1/SDM_Figure1.png)Figure 1\.1:The challenge of unlearning on spatiotemporal graphs\.\(a\) In a complete ST\-graph, walks propagate node influence globally \(e\.g\.,v4v\_\{4\}reachesv5v\_\{5\}via Walk C;v3v\_\{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 reachesv1v\_\{1\}orv3v\_\{3\}, Walk B no longer reachesv2v\_\{2\}, and uninvolvedv4v\_\{4\}loses all outgoing paths, a structural cascade\. \(d\) Retraining the fragmented graph alters the remaining node features \(v1,v2,v3,v5v\_\{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\)\.1\. Spatial entropy as a partition balance criterion\.We propose a new concept “spatial entropy” as a principled measure for verifying that spectral partitioning produces balanced, non\-degenerate subgraphs, each preserving dense local connectivity so that its encoder can fully exploit local spatiotemporal correlations\.

2\. Virtual edges for decoupled global integration\.We design a two\-stage training protocol in which independently trained subgraph encoders are connected through lightweight virtual edges\. The strict gradient isolation between stages guarantees exact unlearning: retraining is confined to the affected subgraph and the virtual\-edge parameters\.

3\. Comprehensive empirical validation\.Across four real\-world datasets spanning 23 to 3,220 nodes and four ST\-GNN backbones, IsleNet attains up to 94% of full\-graph accuracy while reducing unlearning time by up to 12×\\times, outperforming five baselines\.

## 2Related Work\.

A Spatiotemporal Graph𝒢=\(𝒱,ℰ,𝐗\)\\mathcal\{G\}=\(\\mathcal\{V\},\\mathcal\{E\},\\mathbf\{X\}\)hasNNnodes with adjacency matrix𝐀∈ℝN×N\\mathbf\{A\}\\in\\mathbb\{R\}^\{N\\times N\}and features𝐗∈ℝT×N×F\\mathbf\{X\}\\in\\mathbb\{R\}^\{T\\times N\\times F\}spanningTTtimesteps\. ST\-GNNs such as STGCN\[[27](https://arxiv.org/html/2608.29360#bib.bib11)\], ST\-GAT\[[25](https://arxiv.org/html/2608.29360#bib.bib10)\], and DCRNN\[[21](https://arxiv.org/html/2608.29360#bib.bib12)\]couple spatial message passing with recurrent or convolutional temporal operators, producing per\-node forecasts\. This coupling is precisely what makes unlearning expensive: each node’s features propagate through both dimensions, so a single deletion can require full retraining\.

General\-purpose unlearning falls into two camps\. Exact methods retrain affected subsets of the model: SISA\[[2](https://arxiv.org/html/2608.29360#bib.bib19)\]partitions data into independent shards so only affected shards are retrained; Ginart et al\.\[[11](https://arxiv.org/html/2608.29360#bib.bib1)\]derive deletion\-efficientkk\-means variants\. Approximate methods modify trained parameters directly: certified removal\[[13](https://arxiv.org/html/2608.29360#bib.bib2)\]uses Newton updates with differential\-privacy noise, and weight scrubbing\[[12](https://arxiv.org/html/2608.29360#bib.bib3)\]perturbs weights along Fisher\-information directions\. Exact methods offer formal guarantees; approximate methods are faster but lack provable deletion\. GraphEraser\[[4](https://arxiv.org/html/2608.29360#bib.bib4)\]pioneered graph unlearning through balanced partitioning \(BLPA/BEKM\) with learned aggregation; GUIDE\[[26](https://arxiv.org/html/2608.29360#bib.bib5)\]extends this with fairness\-aware dynamic partitioning\. GNNDelete\[[5](https://arxiv.org/html/2608.29360#bib.bib6)\]avoids partitioning by learning layer\-wise deletion operators, while PROJECTOR\[[6](https://arxiv.org/html/2608.29360#bib.bib7)\]provides exact deletion for linear GNNs via orthogonal projection\. These methods target static graph node classification; none address spatiotemporal forecasting, where temporal message passing amplifies residual influence\. For spatiotemporal settings, STEPS\[[14](https://arxiv.org/html/2608.29360#bib.bib9)\]applies spectral partitioning with weighted aggregation to ST\-GNN forecasting, handling up to 15% node removal with order\-of\-magnitude speedups, but lacks formal deletion proofs and requires preset partition scales\. Graph Revoke\[[28](https://arxiv.org/html/2608.29360#bib.bib8)\]unlearns dynamic edges in continuous\-time graphs via ML\-Mixer gradient transformation, achieving 7\.23×\\timesspeedups on link prediction, but offers no theoretical deletion guarantees and may face scalability bottlenecks\.

Information\-theoretic measures have a long history in graph analysis\[[7](https://arxiv.org/html/2608.29360#bib.bib20),[18](https://arxiv.org/html/2608.29360#bib.bib22),[20](https://arxiv.org/html/2608.29360#bib.bib26)\]and in partition quality assessment\[[24](https://arxiv.org/html/2608.29360#bib.bib21),[8](https://arxiv.org/html/2608.29360#bib.bib23)\]\. Spatial entropy specifically has been used in geographic information science to measure the evenness of point distributions\[[1](https://arxiv.org/html/2608.29360#bib.bib24),[19](https://arxiv.org/html/2608.29360#bib.bib25)\]\. To our knowledge, no prior work applies entropy\-based criteria to verify partition quality in spatiotemporal graph unlearning\.

## 3Method\.

IsleNet partitions the ST\-graph into locally coherent subgraphs that preserve dense internal connectivity, with spatial entropy verifying that no subgraph degenerates\. Lightweight virtual edges, structurally decoupled from the encoders, compensate for severed long\-range dependencies\. A two\-stage protocol first trains each encoder in isolation, then freezes them and trains only the virtual edges, confining each node’s influence to one subgraph so that unlearning retrains only the affected encoder and the virtual\-edge layer\.

![Refer to caption](https://arxiv.org/html/2608.29360v1/SDM_Figure2_new.png)Figure 3\.1:Spatial entropy in IsleNet\.Top:Spatial entropyHsH\_\{s\}\(Eq\.[3\.2](https://arxiv.org/html/2608.29360#S3.E2)\) 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\.### 3\.1Problem Formulation\.

Consider a spatiotemporal graph𝒢=\(𝒱,ℰ,𝐗\)\\mathcal\{G\}=\(\\mathcal\{V\},\\mathcal\{E\},\\mathbf\{X\}\), where𝒱\\mathcal\{V\}is a set ofNNnodes,ℰ\\mathcal\{E\}encodes edges in a binary adjacency matrix𝐀∈\{0,1\}N×N\\mathbf\{A\}\\in\\\{0,1\\\}^\{N\\times N\}, and𝐗∈ℝT×N×F\\mathbf\{X\}\\in\\mathbb\{R\}^\{T\\times N\\times F\}contains temporal features of lengthTTwithFF\-dimensional features per node\. A GNN modelfθ:\(𝐗,𝐀\)↦𝐘f\_\{\\theta\}:\(\\mathbf\{X\},\\mathbf\{A\}\)\\mapsto\\mathbf\{Y\}predicts future node states𝐘∈ℝN×H\\mathbf\{Y\}\\in\\mathbb\{R\}^\{N\\times H\}over a horizonHH\. The unlearning task is to remove a subset of nodes𝒰N⊂𝒱\\mathcal\{U\}\_\{N\}\\subset\\mathcal\{V\}and their edges𝒰E=\{\(u,v\)∈ℰ:u∈𝒰N​or​v∈𝒰N\}\\mathcal\{U\}\_\{E\}=\\\{\(u,v\)\\in\\mathcal\{E\}:u\\in\\mathcal\{U\}\_\{N\}\\text\{ or \}v\\in\\mathcal\{U\}\_\{N\}\\\}, producing a new modelfθ′f\_\{\\theta^\{\\prime\}\}that approximates the performance of a model retrained from scratch on the remaining graph𝒢′=\(𝒱∖𝒰N,ℰ∖𝒰E,𝐗′\)\\mathcal\{G\}^\{\\prime\}=\(\\mathcal\{V\}\\setminus\\mathcal\{U\}\_\{N\},\\mathcal\{E\}\\setminus\\mathcal\{U\}\_\{E\},\\mathbf\{X\}^\{\\prime\}\)\.

Formally, given a loss functionℒ\\mathcal\{L\}\(e\.g\., L1 loss\), the unlearning objective is:

\(3\.1\)θ′≈arg⁡minθ​𝔼\(𝐗′,𝐘′\)​ℒ​\(fθ​\(𝐗′,𝐀′\),𝐘′\),\\theta^\{\\prime\}\\approx\\arg\\min\_\{\\theta\}\\mathbb\{E\}\_\{\(\\mathbf\{X\}^\{\\prime\},\\mathbf\{Y\}^\{\\prime\}\)\}\\mathcal\{L\}\(f\_\{\\theta\}\(\\mathbf\{X\}^\{\\prime\},\\mathbf\{A\}^\{\\prime\}\),\\mathbf\{Y\}^\{\\prime\}\),
where𝐀′\\mathbf\{A\}^\{\\prime\}is the adjacency matrix of𝒢′\\mathcal\{G\}^\{\\prime\}, and𝐗′,𝐘′\\mathbf\{X\}^\{\\prime\},\\mathbf\{Y\}^\{\\prime\}exclude data associated with𝒰N\\mathcal\{U\}\_\{N\}\. Following the SISA framework\[[2](https://arxiv.org/html/2608.29360#bib.bib19)\], we say that unlearning is exact if the post\-unlearning modelfθ′f\_\{\\theta^\{\\prime\}\}is statistically indistinguishable from a model retrained from scratch under the same partition and training protocol on𝒢′\\mathcal\{G\}^\{\\prime\}\. IsleNet satisfies this condition because gradient isolation \(Eq\.[3\.7](https://arxiv.org/html/2608.29360#S3.E7)\) ensures that no encoder parameter outside the affected subgraph was ever influenced by the deleted nodes, and the virtual\-edge layer is re\-initialized and re\-trained on the remaining data\.

### 3\.2IsleNet Architecture\.

IsleNet decomposes the graph intoMMindependent subgraphs and integrates them via a virtual edge mechanism to balance local isolation and global information flow\. The architecture comprises three components: spatial\-entropy\-guided partitioning, subgraph\-independent spatiotemporal encoding, and virtual edges\.

#### 3\.2\.1Spatial\-Entropy\-Guided Partitioning\.

We partition𝒢\\mathcal\{G\}intoMMdisjoint subgraphs\{𝒢1,…,𝒢M\}\\\{\\mathcal\{G\}\_\{1\},\\ldots,\\mathcal\{G\}\_\{M\}\\\}, where𝒢i=\(𝒱i,ℰi,𝐗i\)\\mathcal\{G\}\_\{i\}=\(\\mathcal\{V\}\_\{i\},\\mathcal\{E\}\_\{i\},\\mathbf\{X\}\_\{i\}\),𝒱i∩𝒱j=∅\\mathcal\{V\}\_\{i\}\\cap\\mathcal\{V\}\_\{j\}=\\emptysetfori≠ji\\neq j, and⋃i𝒱i=𝒱\\bigcup\_\{i\}\\mathcal\{V\}\_\{i\}=\\mathcal\{V\}\. A key insight of IsleNet is that locally coherent subgraphs with dense internal connectivity allow each encoder to fully exploit spatiotemporal correlations through GCN message passing\. However, the partition must also be balanced: no subgraph should degenerate to a trivially small or collapsed cluster\. We use spatial entropy to formalize and verify this balance property\.

We defineSpatial Entropyby discretizing the spatial domain of𝒢\\mathcal\{G\}intoRRnon\-overlapping regions \(e\.g\., grid cells based on node coordinates\)\. For any node subset𝒱′⊆𝒱\\mathcal\{V\}^\{\\prime\}\\subseteq\\mathcal\{V\}, letpr​\(𝒱′\)=\|\{v∈𝒱′:𝐬v∈region​r\}\|/\|𝒱′\|p\_\{r\}\(\\mathcal\{V\}^\{\\prime\}\)=\|\\\{v\\in\\mathcal\{V\}^\{\\prime\}:\\mathbf\{s\}\_\{v\}\\in\\text\{region \}r\\\}\|/\|\\mathcal\{V\}^\{\\prime\}\|denote the fraction of nodes falling in regionrr\. The spatial entropy of𝒱′\\mathcal\{V\}^\{\\prime\}is defined as:

\(3\.2\)Hs\(𝒱′\)=−∑r=1Rpr\(𝒱′\)logpr\(𝒱′\),H\_\{s\}\(\\mathcal\{V\}^\{\\prime\}\)=\-\\sum\_\{r=1\}^\{R\}p\_\{r\}\(\\mathcal\{V\}^\{\\prime\}\)\\log p\_\{r\}\(\\mathcal\{V\}^\{\\prime\}\),where0​log⁡0≜00\\log 0\\triangleq 0\. The maximum entropyHsmax=log⁡RH\_\{s\}^\{\\max\}=\\log Ris attained when nodes are uniformly distributed across all regions\.

For a partition𝒫=\{𝒱1,…,𝒱M\}\\mathcal\{P\}=\\\{\\mathcal\{V\}\_\{1\},\\ldots,\\mathcal\{V\}\_\{M\}\\\}, we define thepartitioning entropyas the minimum spatial entropy across all subgraphs, together with its normalized form:

\(3\.3\)H𝒫\\displaystyle H\_\{\\mathcal\{P\}\}=mini∈\{1,…,M\}⁡Hs​\(𝒱i\),\\displaystyle=\\min\_\{i\\in\\\{1,\\ldots,M\\\}\}H\_\{s\}\(\\mathcal\{V\}\_\{i\}\),\(3\.4\)H¯𝒫\\displaystyle\\bar\{H\}\_\{\\mathcal\{P\}\}=H𝒫Hs​\(𝒱\)\.\\displaystyle=\\frac\{H\_\{\\mathcal\{P\}\}\}\{H\_\{s\}\(\\mathcal\{V\}\)\}\.H¯𝒫\\bar\{H\}\_\{\\mathcal\{P\}\}ranges from 0 \(a degenerate partition where one subgraph has collapsed\) to 1 \(all subgraphs have comparable spatial extent\)\. We accept a partition whenH¯𝒫≥1−ϵ\\bar\{H\}\_\{\\mathcal\{P\}\}\\geq 1\-\\epsilon; otherwise balanced redistribution is triggered \(detailed below\)\.

IsleNet seeksa partition that minimizes inter\-subgraph edge cuts\(preserving local connectivity\) subject to balance constraints verified by partition entropy:

\(3\.5\)min𝒫∑i=1M∑u∈𝒱iv∉𝒱i𝐀u​vs\.t\.\|\|𝒱i\|−NM\|≤δ,H¯𝒫≥1−ϵ,\\min\_\{\\mathcal\{P\}\}\\sum\_\{i=1\}^\{M\}\\sum\_\{\\begin\{subarray\}\{c\}u\\in\\mathcal\{V\}\_\{i\}\\\\ v\\notin\\mathcal\{V\}\_\{i\}\\end\{subarray\}\}\\mathbf\{A\}\_\{uv\}\\quad\\text\{s\.t\.\}\\quad\\left\|\|\\mathcal\{V\}\_\{i\}\|\-\\frac\{N\}\{M\}\\right\|\\leq\\delta,\\;\\;\\bar\{H\}\_\{\\mathcal\{P\}\}\\geq 1\-\\epsilon,whereδ\\deltacontrols size tolerance andH¯𝒫\\bar\{H\}\_\{\\mathcal\{P\}\}\(defined in Eq\.[3\.4](https://arxiv.org/html/2608.29360#S3.E4)\) is the normalized partition entropy\. Algorithmically, we first run spectral clustering on the graph Laplacian𝐋=𝐃−𝐀\\mathbf\{L\}=\\mathbf\{D\}\-\\mathbf\{A\}with balance constraint\|𝒱i\|≈N/M\|\\mathcal\{V\}\_\{i\}\|\\approx N/M, producing an initial partition𝒫\(0\)\\mathcal\{P\}^\{\(0\)\}\. We then computeH¯𝒫\(0\)\\bar\{H\}\_\{\\mathcal\{P\}^\{\(0\)\}\}over a discretized grid on the node coordinates\. IfH¯𝒫\(0\)≥1−ϵ\\bar\{H\}\_\{\\mathcal\{P\}^\{\(0\)\}\}\\geq 1\-\\epsilonthe partition is accepted; otherwise, a balanced redistribution procedure \(below\) is invoked to produce a spatially non\-degenerate partition\. We useϵ=0\.1\\epsilon=0\.1throughout\.

WhenH¯𝒫\(0\)<1−ϵ\\bar\{H\}\_\{\\mathcal\{P\}^\{\(0\)\}\}<1\-\\epsilon, we iteratively rebalance: at each step, we identify the subgraph𝒱i∗\\mathcal\{V\}\_\{i^\{\*\}\}with the lowest spatial entropy, select the node farthest \(in Euclidean distance\) from its centroid, and reassign it to the subgraph with highest entropy among those with\|𝒱j\|<N/M\+δ\|\\mathcal\{V\}\_\{j\}\|<N/M\+\\delta; then recomputeH¯𝒫\\bar\{H\}\_\{\\mathcal\{P\}\}\. The procedure terminates whenH¯𝒫≥1−ϵ\\bar\{H\}\_\{\\mathcal\{P\}\}\\geq 1\-\\epsilonor after three iterations; on failure we fall back to a size\-balanced random partition\. To quantifybalance across subgraphsbeyond the minimum criterion, we also monitor the entropy varianceσH2=1M​∑i=1M\(Hs​\(𝒱i\)−H¯s\)2\\sigma^\{2\}\_\{H\}=\\tfrac\{1\}\{M\}\\sum\_\{i=1\}^\{M\}\(H\_\{s\}\(\\mathcal\{V\}\_\{i\}\)\-\\bar\{H\}\_\{s\}\)^\{2\}, whereH¯s=1M​∑iHs​\(𝒱i\)\\bar\{H\}\_\{s\}=\\tfrac\{1\}\{M\}\\sum\_\{i\}H\_\{s\}\(\\mathcal\{V\}\_\{i\}\)\. A partition is*spatially adequate*if bothH¯𝒫≥1−ϵ\\bar\{H\}\_\{\\mathcal\{P\}\}\\geq 1\-\\epsilon\(non\-degeneracy\) andσH2≤τ\\sigma^\{2\}\_\{H\}\\leq\\tau\(low imbalance\)\. IsleNet’s spectral clustering with balance constraints satisfies both on all benchmarks withϵ≤0\.1\\epsilon\\leq 0\.1andτ≤0\.01\\tau\\leq 0\.01\.

###### Proposition 3\.1\(Representational Fidelity\)\.

If a partition𝒫\\mathcal\{P\}satisfiesHs​\(𝒱i\)≥Hs​\(𝒱\)−ϵH\_\{s\}\(\\mathcal\{V\}\_\{i\}\)\\geq H\_\{s\}\(\\mathcal\{V\}\)\-\\epsilonfor allii, then each subgraph𝒢i\\mathcal\{G\}\_\{i\}occupies at least a fraction\(1−ϵ\)\(1\-\\epsilon\)of the spatial regions of𝒢\\mathcal\{G\}, so no subgraph is spatially degenerate and every encoder receives a non\-trivial portion of the graph’s extent\.

###### Proof 1\.

LetRi=\|\{r:pr​\(𝒱i\)\>0\}\|R\_\{i\}=\|\\\{r:p\_\{r\}\(\\mathcal\{V\}\_\{i\}\)\>0\\\}\|\. SinceHs​\(𝒱i\)≤log⁡RiH\_\{s\}\(\\mathcal\{V\}\_\{i\}\)\\leq\\log R\_\{i\}, we haveRi≥eHs​\(𝒱i\)≥eHs​\(𝒱\)−ϵR\_\{i\}\\geq e^\{H\_\{s\}\(\\mathcal\{V\}\_\{i\}\)\}\\geq e^\{H\_\{s\}\(\\mathcal\{V\}\)\-\\epsilon\}\. When𝒱\\mathcal\{V\}approximately uniformly coversR\+R^\{\+\}occupied regions,Hs​\(𝒱\)≈log⁡R\+H\_\{s\}\(\\mathcal\{V\}\)\\approx\\log R^\{\+\}, soRi/R\+≥e−ϵ≥1−ϵR\_\{i\}/R^\{\+\}\\geq e^\{\-\\epsilon\}\\geq 1\-\\epsilon\.

###### Theorem 3\.2\(Post\-Unlearning Entropy Bound\)\.

Under a spatially adequate partition𝒫\\mathcal\{P\}, removing a fractionγi=\|𝒰N∩𝒱i\|/\|𝒱i\|\\gamma\_\{i\}=\|\\mathcal\{U\}\_\{N\}\\cap\\mathcal\{V\}\_\{i\}\|/\|\\mathcal\{V\}\_\{i\}\|of nodes from𝒱i\\mathcal\{V\}\_\{i\}yieldsHs​\(𝒱i∖𝒰N\)≥Hs​\(𝒱i\)−γi​log⁡RH\_\{s\}\(\\mathcal\{V\}\_\{i\}\\setminus\\mathcal\{U\}\_\{N\}\)\\geq H\_\{s\}\(\\mathcal\{V\}\_\{i\}\)\-\\gamma\_\{i\}\\log R, so the retrained subgraph preserves enough spatial coverage for small\-fraction unlearning\.

###### Proof 2\.

Removingγi​\|𝒱i\|\\gamma\_\{i\}\|\\mathcal\{V\}\_\{i\}\|nodes reduces entropy by at mostγi​log⁡R\\gamma\_\{i\}\\log R\(the information content of uniformly\-distributed removed nodes\)\. Combined withHs​\(𝒱i\)≥\(1−ϵ\)​Hs​\(𝒱\)H\_\{s\}\(\\mathcal\{V\}\_\{i\}\)\\geq\(1\-\\epsilon\)H\_\{s\}\(\\mathcal\{V\}\), the post\-unlearning entropy remains close toHs​\(𝒱\)H\_\{s\}\(\\mathcal\{V\}\)for smallγi\\gamma\_\{i\}\.

#### 3\.2\.2Subgraph\-Independent Spatiotemporal Encoding\.

Each subgraph𝒢i\\mathcal\{G\}\_\{i\}is processed by a dedicated encoderfθif\_\{\\theta\_\{i\}\}\(e\.g\., STGCN\), taking features𝐗i∈ℝB×T×\|𝒱i\|×F\\mathbf\{X\}\_\{i\}\\in\\mathbb\{R\}^\{B\\times T\\times\|\\mathcal\{V\}\_\{i\}\|\\times F\}and edge index𝐄i⊆ℰi\\mathbf\{E\}\_\{i\}\\subseteq\\mathcal\{E\}\_\{i\}, producing embeddings𝐇i∈ℝB×\|𝒱i\|×H\\mathbf\{H\}\_\{i\}\\in\\mathbb\{R\}^\{B\\times\|\\mathcal\{V\}\_\{i\}\|\\times H\}:

\(3\.6\)𝐇i=fθi​\(𝐗i,𝐄i\)\.\\mathbf\{H\}\_\{i\}=f\_\{\\theta\_\{i\}\}\(\\mathbf\{X\}\_\{i\},\\mathbf\{E\}\_\{i\}\)\.The encoder applies graph convolutions for spatial modeling and recurrent units for temporal modeling, outputting per\-node predictions\. Independence is ensured by gradient isolation:

\(3\.7\)∂ℒi∂θj=0∀i≠j,\\frac\{\\partial\\mathcal\{L\}\_\{i\}\}\{\\partial\\theta\_\{j\}\}=0\\quad\\forall i\\neq j,whereℒi\\mathcal\{L\}\_\{i\}is the loss on subgraphii\. Isolation is enforced mechanically: each encoderfθif\_\{\\theta\_\{i\}\}has its own Adam optimizer operating on a disjoint parameter group, andℒi\\mathcal\{L\}\_\{i\}is computed only from\(𝐗i,𝐄i,𝐲i\)\(\\mathbf\{X\}\_\{i\},\\mathbf\{E\}\_\{i\},\\mathbf\{y\}\_\{i\}\), so the computation graph for encoderj≠ij\\neq iis never instantiated during a step that updates encoderii\. Consequently, no parameter inθj\\theta\_\{j\}can depend on any node in𝒱i\\mathcal\{V\}\_\{i\}, which is the prerequisite for exact localized unlearning\.

##### Gradient Isolation Bound\.

For a deletion fractionγ=\|𝒰N\|/N\\gamma=\|\\mathcal\{U\}\_\{N\}\|/N, the post\-unlearning loss satisfiesℒunlearn≤ℒorig\+O⁡\(γ​∑i∈𝒮affectedℒi\)\\mathcal\{L\}\_\{\\text\{unlearn\}\}\\leq\\mathcal\{L\}\_\{\\text\{orig\}\}\+O\(\\gamma\\sum\_\{i\\in\\mathcal\{S\}\_\{\\text\{affected\}\}\}\\mathcal\{L\}\_\{i\}\), ensuring minimal error increase since\|𝒮affected\|≤M\|\\mathcal\{S\}\_\{\\text\{affected\}\}\|\\leq M\.

#### 3\.2\.3Virtual Edge Construction\.

To restore global connectivity lost during partitioning, we introduce virtual edges comprising intra\-subgraph and inter\-subgraph connections, which aggregate information via attention\-based embeddings\. In principle, virtual edges can be parameterized by any network designed for information summarization; in this work, we adopt a multilayer perceptron\.

For each subgraph𝒢i\\mathcal\{G\}\_\{i\}, we select the topki=max⁡\(2,⌈0\.1⋅\|𝒱i\|⌉\)k\_\{i\}=\\max\(2,\\lceil 0\.1\\cdot\|\\mathcal\{V\}\_\{i\}\|\\rceil\)structurally influential nodes𝒦i\\mathcal\{K\}\_\{i\}using PageRank centrality\[[23](https://arxiv.org/html/2608.29360#bib.bib27)\]\. The PageRank vector𝐩∈ℝ\|𝒱i\|\\mathbf\{p\}\\in\\mathbb\{R\}^\{\|\\mathcal\{V\}\_\{i\}\|\}is computed via the standard power iteration with damping factorα\\alpha, and the key node set is:

\(3\.8\)𝒦i=TopK​\(𝐩,ki\)\.\\mathcal\{K\}\_\{i\}=\\text\{TopK\}\(\\mathbf\{p\},k\_\{i\}\)\.These key nodes serve asendpoints for the virtual edgesthat restore cross\-subgraph information flow\.

Each virtual edge aggregates embeddings from a set of key nodes𝒦src\\mathcal\{K\}\_\{\\text\{src\}\}via scaled dot\-product attention followed by an MLP\. Let𝐇𝒦∈ℝB×n×D\\mathbf\{H\}\_\{\\mathcal\{K\}\}\\in\\mathbb\{R\}^\{B\\times n\\times D\}collect the embeddings ofnnselected key nodes\. The virtual\-edge feature is computed as:

\(3\.9\)𝐖\\displaystyle\\mathbf\{W\}=softmax​\(𝐇𝒦​𝐇𝒦⊤D\),\\displaystyle=\\text\{softmax\}\\\!\\left\(\\frac\{\\mathbf\{H\}\_\{\\mathcal\{K\}\}\\mathbf\{H\}\_\{\\mathcal\{K\}\}^\{\\top\}\}\{D\}\\right\),\(3\.10\)𝐡b\\displaystyle\\mathbf\{h\}\_\{b\}=MLP​\(flatten​\(𝐖𝐇𝒦\)\),\\displaystyle=\\text\{MLP\}\(\\text\{flatten\}\(\\mathbf\{W\}\\mathbf\{H\}\_\{\\mathcal\{K\}\}\)\),whereMLP:ℝn​D→ℝDb\\text\{MLP\}:\\mathbb\{R\}^\{nD\}\\rightarrow\\mathbb\{R\}^\{D\_\{b\}\}is a two\-layer network with ReLU activation\. We instantiate two types of virtual edges: intra\-subgraph edges that connect the top\-2 key nodes within each subgraph \(n=2n\{=\}2, yieldingMMedges\), and inter\-subgraph edges that connect the top\-3 key nodes from each pair of subgraphs \(n=6n\{=\}6, yielding\(M2\)\\binom\{M\}\{2\}edges\)\. The total number of virtual edges isM\+\(M2\)M\+\\binom\{M\}\{2\}\. The top\-2/top\-3 choice is a parameter\-efficiency trade\-off: the\(M2\)\\binom\{M\}\{2\}inter\-subgraph edges dominate the parameter budget, so a larger receptive field there \(six key nodes\) is more impactful than widening theMMintra\-subgraph edges\.

Virtual\-edge features are aggregated residually:

\(3\.11\)𝐇enhanced=𝐇\+β​∑b∈ℬ𝐏b​Proj​\(𝐡b\),\\mathbf\{H\}^\{\\text\{enhanced\}\}=\\mathbf\{H\}\+\\beta\\sum\_\{b\\in\\mathcal\{B\}\}\\mathbf\{P\}\_\{b\}\\text\{Proj\}\(\\mathbf\{h\}\_\{b\}\),where𝐇=\[𝐇1;…;𝐇M\]∈ℝB×N×D\\mathbf\{H\}=\[\\mathbf\{H\}\_\{1\};\\ldots;\\mathbf\{H\}\_\{M\}\]\\in\\mathbb\{R\}^\{B\\times N\\times D\}concatenates subgraph embeddings,Proj:ℝDb→ℝD\\text\{Proj\}:\\mathbb\{R\}^\{D\_\{b\}\}\\rightarrow\\mathbb\{R\}^\{D\}is a linear layer,β\>0\\beta\>0is a residual scaling factor tuned on a validation set to balance local and global contributions \(we useβ=0\.1\\beta\{=\}0\.1throughout\), and𝐏b∈\{0,1\}N×1\\mathbf\{P\}\_\{b\}\\in\\\{0,1\\\}^\{N\\times 1\}maps virtual edgebbto its connected nodes\. This approximates𝐀\\mathbf\{A\}with a low\-rank structure, ensuring efficient global information flow\.

The attention weights𝐖\\mathbf\{W\}\(Eq\.[3\.9](https://arxiv.org/html/2608.29360#S3.E9)\) are row\-stochastic with‖𝐖‖2≤1\\\|\\mathbf\{W\}\\\|\_\{2\}\\leq 1, ensuringstable information propagation\. TheM\+\(M2\)M\+\\binom\{M\}\{2\}virtual edges approximate the full adjacency𝐀\\mathbf\{A\}with onlyO⁡\(M2\)O\(M^\{2\}\)parameters, maintaining global connectivity at low cost\.

### 3\.3Two\-Stage Training Protocol\.

Stage 1 trains each encoderfθif\_\{\\theta\_\{i\}\}independently to minimize anL1L\_\{1\}loss on its own subgraph:

\(3\.12\)ℒi=1B​∑b∑v∈𝒱i‖𝐲i,b,v−fθi​\(𝐗i,b,𝐄i\)v‖1\.\\mathcal\{L\}\_\{i\}=\\tfrac\{1\}\{B\}\\sum\_\{b\}\\sum\_\{v\\in\\mathcal\{V\}\_\{i\}\}\\\|\\mathbf\{y\}\_\{i,b,v\}\-f\_\{\\theta\_\{i\}\}\(\\mathbf\{X\}\_\{i,b\},\\mathbf\{E\}\_\{i\}\)\_\{v\}\\\|\_\{1\}\.Stage 2 freezes all encoders and trains only the virtual edges on a full\-graphL1L\_\{1\}loss withL2L\_\{2\}regularization:

\(3\.13\)ℒve=1B​∑b∑v∈𝒱‖𝐲b,v−IsleNet​\(𝐗b,𝐄\)v‖1\+λ​‖𝒲ve‖22\.\\mathcal\{L\}\_\{\\text\{ve\}\}=\\tfrac\{1\}\{B\}\\sum\_\{b\}\\sum\_\{v\\in\\mathcal\{V\}\}\\\|\\mathbf\{y\}\_\{b,v\}\-\\text\{IsleNet\}\(\\mathbf\{X\}\_\{b\},\\mathbf\{E\}\)\_\{v\}\\\|\_\{1\}\+\\lambda\\\|\\mathcal\{W\}\_\{\\text\{ve\}\}\\\|\_\{2\}^\{2\}\.Freezing preserves subgraph gradient isolation while virtual edges learn global connectivity\.

### 3\.4Efficient Unlearning Protocol\.

Unlearning localizes retraining to affected subgraphs\. Given𝒰N\\mathcal\{U\}\_\{N\}, we identify:

\(3\.14\)𝒮affected=\{i:𝒱i∩𝒰N≠∅\}\.\\mathcal\{S\}\_\{\\text\{affected\}\}=\\\{i:\\mathcal\{V\}\_\{i\}\\cap\\mathcal\{U\}\_\{N\}\\neq\\emptyset\\\}\.Virtual edges connected to𝒰N\\mathcal\{U\}\_\{N\}are removed:

\(3\.15\)ℬnew=\{b∈ℬ:𝒦b∩𝒰N=∅\},\\mathcal\{B\}^\{\\text\{new\}\}=\\\{b\\in\\mathcal\{B\}:\\mathcal\{K\}\_\{b\}\\cap\\mathcal\{U\}\_\{N\}=\\emptyset\\\},and rebuilt using Eq\. \([3\.9](https://arxiv.org/html/2608.29360#S3.E9)\)–\([3\.10](https://arxiv.org/html/2608.29360#S3.E10)\)\. For eachi∈𝒮affectedi\\in\\mathcal\{S\}\_\{\\text\{affected\}\}, retrainfθif\_\{\\theta\_\{i\}\}on𝒱i∖𝒰N\\mathcal\{V\}\_\{i\}\\setminus\\mathcal\{U\}\_\{N\}:

\(3\.16\)θinew=arg⁡minθ​ℒi​\(θ,𝐗i′,𝐄i′,𝐲i′\)\.\\theta\_\{i\}^\{\\text\{new\}\}=\\arg\\min\_\{\\theta\}\\mathcal\{L\}\_\{i\}\(\\theta,\\mathbf\{X\}\_\{i\}^\{\\prime\},\\mathbf\{E\}\_\{i\}^\{\\prime\},\\mathbf\{y\}\_\{i\}^\{\\prime\}\)\.Encoders are frozen, and virtual edges are re\-optimized using Eq\. \([3\.13](https://arxiv.org/html/2608.29360#S3.E13)\)\. Finally, encoders are unfrozen to enable future fine\-tuning, ensuring flexibility without compromising the unlearned state\.

Algorithm 1: IsleNet Training and Unlearning

1:Input:

𝒢=\(𝒱,ℰ,𝐗\)\\mathcal\{G\}=\(\\mathcal\{V\},\\mathcal\{E\},\\mathbf\{X\}\), partitions

MM, forget nodes

𝒰N\\mathcal\{U\}\_\{N\}
2:// Training

3:Partition

𝒢\\mathcal\{G\}into

\{𝒢i\}i=1M\\\{\\mathcal\{G\}\_\{i\}\\\}\_\{i=1\}^\{M\}via spectral clustering \(Eq\.[3\.5](https://arxiv.org/html/2608.29360#S3.E5)\)

4:If

H¯𝒫<1−ϵ\\bar\{H\}\_\{\\mathcal\{P\}\}<1\-\\epsilon, apply balanced redistribution

5:For each

ii: train

fθif\_\{\\theta\_\{i\}\}\(Eq\.[3\.12](https://arxiv.org/html/2608.29360#S3.E12)\); select

𝒦i\\mathcal\{K\}\_\{i\}via PageRank

6:Construct

ℬ\\mathcal\{B\}via attention \+ MLP \(Eq\.[3\.9](https://arxiv.org/html/2608.29360#S3.E9)–[3\.10](https://arxiv.org/html/2608.29360#S3.E10)\)

7:Freeze

\{fθi\}\\\{f\_\{\\theta\_\{i\}\}\\\}; optimize

ℬ\\mathcal\{B\}\(Eq\.[3\.13](https://arxiv.org/html/2608.29360#S3.E13)\)

8:// Unlearning

9:Identify

𝒮affected\\mathcal\{S\}\_\{\\text\{affected\}\}\(Eq\.[3\.14](https://arxiv.org/html/2608.29360#S3.E14)\)

10:Drop

ℬ\\mathcal\{B\}edges incident to

𝒰N\\mathcal\{U\}\_\{N\}
11:For each

i∈𝒮affectedi\\in\\mathcal\{S\}\_\{\\text\{affected\}\}: retrain

fθif\_\{\\theta\_\{i\}\}on

𝒱i∖𝒰N\\mathcal\{V\}\_\{i\}\\setminus\\mathcal\{U\}\_\{N\}
12:Re\-initialize and re\-train

ℬnew\\mathcal\{B\}^\{\\text\{new\}\}with frozen encoders \(Eq\.[3\.13](https://arxiv.org/html/2608.29360#S3.E13)\)

13:Output: Unlearned IsleNet

## 4Experiments\.

We assess IsleNet on: 1\)accuracy paritywith a full\-graph model \(Scratch\) before deletion; 2\)resilience after erasureof a chosen node/edge subset; and 3\)component and efficiency analysisvia ablations plus timing and memory profiling on large graphs\.

Table 4\.1:Prediction Performance of Different Methods Before Unlearning \(0% Unlearning\)\.Table 4\.2:Prediction Performance of Different Methods After Unlearning \(10% Unlearning\)\.### 4\.1Experimental Setup\.

Dataset:To evaluate the scalability of our method, we selected spatiotemporal graph data spanning a range of sizes, with up to 3,220 nodes\. These datasets include: RWW\[[15](https://arxiv.org/html/2608.29360#bib.bib15)\], a 23\-node network representing water depth in a sewage system; PeMS08\[[16](https://arxiv.org/html/2608.29360#bib.bib18)\], a 170\-node traffic flow network in California; Global Weather\[[22](https://arxiv.org/html/2608.29360#bib.bib17)\], a 1,000\-node global daily temperature network; and Human Mobility Flow\[[17](https://arxiv.org/html/2608.29360#bib.bib16)\], a 3,220\-node mobility network capturing daily population movement\. The datasets consist of time series ranging from 3,000 to 18,000 time steps, making them large\-scale\. We split the data temporally into training \(70%\), validation \(15%\), and test \(15%\) sets\.

Baselines:We compare our approach against several state\-of\-the\-art baselines: Scratch \(full graph training with no unlearning\), SISA\[[2](https://arxiv.org/html/2608.29360#bib.bib19)\], STEPS\[[14](https://arxiv.org/html/2608.29360#bib.bib9)\], GraphEraser\[[4](https://arxiv.org/html/2608.29360#bib.bib4)\], and GraphRevoker\[[28](https://arxiv.org/html/2608.29360#bib.bib8)\], evaluated on four spatiotemporal graph backbones: STGCN, ST\-SAGE, ST\-GAT, and ST\-GATV2\. We fix the number of subgraphsM=4M=4\. We note that GraphEraser and GraphRevoker were originally designed for recommender systems with static or discrete\-time dynamic graphs; we include them as general\-purpose graph\-unlearning baselines to provide context rather than as ST\-specific competitors\.

Metrics:We record evaluation metrics including MAE, MSE, RMSE, Trend F1, andR2R^\{2\}\. MAE are reported in the Results section on the original scale, with mean and standard deviation\. Runtime, memory, and CPU costs are also measured\.

Fair and Robust Setup:Model parameters are tuned to reachR2\>0\.9R^\{2\}\>0\.9on RWW, PeMS08, and Mobility; Weather caps atR2≈0\.67R^\{2\}\\approx 0\.67due to high per\-station stochasticity, so we report MAE as the primary metric on Weather\. To control capacity differences across partitions, the hidden dimension of each subgraph encoder is scaled to the unlearning proportion so that the non\-unlearned model matches full\-graphR2R^\{2\}\. We evaluate at 10% unlearning, a large proportion relative to typical real\-world requests, with 5 fixed random seeds for reproducibility\.

Implementation Details:For partitioning, we use spectral clustering withM=4M=4subgraphs and normalized entropy thresholdϵ=0\.1\\epsilon=0\.1\(Eq\.[3\.5](https://arxiv.org/html/2608.29360#S3.E5)\)\. The PageRank damping factor isα=0\.85\\alpha=0\.85\. For virtual edges, the residual scaling factor isβ=0\.1\\beta=0\.1\(Eq\.[3\.11](https://arxiv.org/html/2608.29360#S3.E11)\) and the regularization weight isλ=10−4\\lambda=10^\{\-4\}\(Eq\.[3\.13](https://arxiv.org/html/2608.29360#S3.E13)\)\. Stage 1 uses Adam with learning rate10−310^\{\-3\}; Stage 2 uses Adam with learning rate5×10−45\\times 10^\{\-4\}\. Early stopping patience is 10 epochs for both stages\. Batch size is 32\. For datasets without explicit node coordinates, we derive two\-dimensional topological coordinates via force\-directed graph layout on the adjacency matrix\[[10](https://arxiv.org/html/2608.29360#bib.bib28)\]; spatial entropy is then computed on a10×1010\\times 10grid over these coordinates\. All experiments are conducted on an NVIDIA A100 GPU with 5 fixed random seeds\.

### 4\.2Results\.

As shown in Table[4\.1](https://arxiv.org/html/2608.29360#S4.T1), at 0% unlearning IsleNet closely matches Scratch\-100%: on PeMS08 with STGCN its MAE is 30\.532±\\pm0\.045, only∼6\.2%\{\\sim\}6\.2\\%above Scratch \(28\.751±\\pm0\.117\), i\.e\.,∼94%\{\\sim\}94\\%of full\-graph performance, and on Weather it is nearly identical \(3\.603±\\pm0\.016 vs\. 3\.597±\\pm0\.014\)\. Baselines degrade sharply: GraphEraser and GraphRevoker, designed for recommender systems, reach MAEs up to∼208%\{\\sim\}208\\%worse than Scratch on PeMS08 \(e\.g\., 88\.685±\\pm5\.865 for GraphRevoker\); STEPS, using uniform partitioning and weighted averaging, is adequate only on Weather \(5\.449 vs\. 3\.597\) and fails on PeMS08 and Mobility \(82\.404±\\pm9\.043 on PeMS08\); SISA, relying on overlapping partitions, is the strongest baseline \(34\.271±\\pm0\.527 on PeMS08\) yet remains clearly inferior to IsleNet\.

At 10% unlearning \(Table[4\.2](https://arxiv.org/html/2608.29360#S4.T2)\), simulating extensive concurrent requests, all methods degrade, but IsleNet stays comparable to Scratch\-90%: on PeMS08 with STGCN, 31\.564±\\pm0\.121 vs\. 30\.810±\\pm0\.147 \(∼2\.4%\{\\sim\}2\.4\\%gap\), with similarly modest increases elsewhere \(∼8\.7%\{\\sim\}8\.7\\%on RWW: 0\.025 vs\. 0\.023;∼3\.4%\{\\sim\}3\.4\\%on Weather: 3\.703 vs\. 3\.581\)\. Baselines suffer far larger losses on PeMS08: STEPS \(99\.807±\\pm12\.190\) and GraphRevoker \(97\.568±\\pm3\.789\) degrade extremely, while GraphEraser \(61\.315±\\pm4\.643\) and SISA \(34\.332±\\pm0\.515\) perform better but remain inferior\.

To summarize proximity to the full\-graph baseline, we compute two measures between each method’s MAE and Scratch’s MAE: Bounded Similarity=max⁡\(0,1−\|MAEm−MAEs\|/MAEs\)=\\max\(0,1\-\|\\mathrm\{MAE\}\_\{m\}\-\\mathrm\{MAE\}\_\{s\}\|/\\mathrm\{MAE\}\_\{s\}\)and Ratio Score=min⁡\(MAEm,MAEs\)/max⁡\(MAEm,MAEs\)=\\min\(\\mathrm\{MAE\}\_\{m\},\\mathrm\{MAE\}\_\{s\}\)/\\max\(\\mathrm\{MAE\}\_\{m\},\\mathrm\{MAE\}\_\{s\}\), averaged across all datasets, backbones, and unlearning rates\. Table[4\.3](https://arxiv.org/html/2608.29360#S4.T3)confirms that IsleNet \(95\.4%/95\.7%\) is closest to Scratch; SISA follows at 86\.2%/89\.5%; other baselines fall below 72% on both measures\.

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

We ablate IsleNet’s four components on PeMS08 with STGCN \(Table[4\.4](https://arxiv.org/html/2608.29360#S4.T4)\)\. Replacing entropy\-verified spectral partitioning with random partitioning raises MAE by 49\.5%/58\.2% \(0%/10% unlearning\), confirming that locally coherent, balanced subgraphs are essential\. Removing virtual edges costs 15\.7%/26\.2%, showing global context via attention\-based key\-node communication matters\. Replacing two\-stage training with joint training raises MAE by over 25% due to gradient interference between structural modules\. Replacing localized unlearning with full retraining costs∼\\sim22% MAE and∼\\sim10×\\timesthroughput\. Together these confirm the combined value of entropy\-verified partitioning, virtual edges, staged optimization, and localized unlearning\.

Table 4\.4:Ablation study on PeMS08 with STGCN\.
### 4\.4Efficiency and Capacity\.

We evaluate scalability on PeMS08 \(STGCN backbone, 10% node unlearning, 5 seeds\)\. The monolithic ST\-GNN needs∼600\{\\sim\}600s to train and∼60\{\\sim\}60s to unlearn 17 nodes\. IsleNet withM=4M\{=\}4cuts training to∼360\{\\sim\}360s and unlearning to∼5\{\\sim\}5s \(a∼12×\{\\sim\}12\\timeswall\-clock speedup\) by retraining only affected subgraphs \(Eq\.[3\.14](https://arxiv.org/html/2608.29360#S3.E14)–[3\.16](https://arxiv.org/html/2608.29360#S3.E16)\)\. AtM=8M\{=\}8, total training stays∼360\{\\sim\}360s as the growing\(M2\)\\binom\{M\}\{2\}virtual\-edge cost \(Eq\.[3\.9](https://arxiv.org/html/2608.29360#S3.E9)\) offsets smaller per\-subgraph cost; unlearning remains∼4\.5\{\\sim\}4\.5s\. AtM=16M\{=\}16, training is∼380\{\\sim\}380s and unlearning drops to∼4\{\\sim\}4s with∼10\{\\sim\}10\-node subgraphs\. IsleNet is thus especially efficient under frequent unlearning \(see also Section[4\.3](https://arxiv.org/html/2608.29360#S4.SS3)\)\.

## 5Conclusion\.

We introduced IsleNet, a spatial\-entropy\-verified partitioning framework for spatiotemporal graph unlearning\. Its two components \(entropy\-verified spectral partitioning and decoupled virtual edges\) together enable exact localized unlearning with minimal accuracy loss\. Across four real\-world benchmarks IsleNet retains up to 94% of full\-graph accuracy while cutting unlearning time by an order of magnitude\. Validation on industry\-scale graphs with millions of nodes and a dedicated ablation isolating entropy verification from spectral clustering are natural next steps\.

## Acknowledgment\.

This work was partially supported by NSF Awards No\. 2318641 and No\. 2112631\.

## References

- \[1\]M\. Batty\(1974\)Spatial entropy\.Geographical Analysis6\(1\),pp\. 1–31\.External Links:[Document](https://dx.doi.org/10.1111/j.1538-4632.1974.tb01014.x)Cited by:[§2](https://arxiv.org/html/2608.29360#S2.p3.1)\.
- \[2\]L\. Bourtoule, V\. Chandrasekaran, C\. A\. Choquette\-Choo, H\. Jia, A\. Travers, B\. Zhang, D\. Lie, and N\. Papernot\(2021\)Machine unlearning\.In2021 IEEE symposium on security and privacy \(SP\),pp\. 141–159\.Cited by:[§2](https://arxiv.org/html/2608.29360#S2.p2.1),[§3\.1](https://arxiv.org/html/2608.29360#S3.SS1.p3.1),[§4\.1](https://arxiv.org/html/2608.29360#S4.SS1.p2.1)\.
- \[3\]California State Legislature\(2018\)California consumer privacy act \(CCPA\) of 2018, as amended by the california privacy rights act \(CPRA\)\.Note:[https://oag\.ca\.gov/privacy/ccpa](https://oag.ca.gov/privacy/ccpa)Updated March 13, 2024\. Accessed May 14, 2025Cited by:[§1](https://arxiv.org/html/2608.29360#S1.p1.1)\.
- \[4\]M\. Chen, Z\. Zhang, T\. Wang, M\. Backes, M\. Humbert, and Y\. Zhang\(2022\)Graph unlearning\.InProceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security,CCS ’22,pp\. 499–513\.External Links:ISBN 9781450394505,[Link](https://doi.org/10.1145/3548606.3559352)Cited by:[§2](https://arxiv.org/html/2608.29360#S2.p2.1),[§4\.1](https://arxiv.org/html/2608.29360#S4.SS1.p2.1)\.
- \[5\]J\. Cheng, G\. Dasoulas, H\. He, C\. Agarwal, and M\. Zitnik\(2023\)GNNDelete: a general strategy for unlearning in graph neural networks\.InInternational Conference on Learning Representations \(ICLR\),Cited by:[§2](https://arxiv.org/html/2608.29360#S2.p2.1)\.
- \[6\]W\. Cong and M\. Mahdavi\(2023\)Efficiently forgetting what you have learned in graph representation learning via projection\.InProceedings of The 26th International Conference on Artificial Intelligence and Statistics,Proceedings of Machine Learning Research, Vol\.206,pp\. 6674–6703\.External Links:[Link](https://proceedings.mlr.press/v206/cong23a.html)Cited by:[§2](https://arxiv.org/html/2608.29360#S2.p2.1)\.
- \[7\]M\. Dehmer and A\. Mowshowitz\(2011\)A history of graph entropy measures\.Information Sciences181\(1\),pp\. 57–78\.External Links:[Document](https://dx.doi.org/10.1016/j.ins.2010.08.041)Cited by:[§2](https://arxiv.org/html/2608.29360#S2.p3.1)\.
- \[8\]I\. S\. Dhillon, Y\. Guan, and B\. Kulis\(2004\)Kernel k\-means, spectral clustering and normalized cuts\.InProceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,pp\. 551–556\.External Links:[Document](https://dx.doi.org/10.1145/1014052.1014118)Cited by:[§2](https://arxiv.org/html/2608.29360#S2.p3.1)\.
- \[9\]European Union\(2016\)General data protection regulation \(GDPR\): regulation \(eu\) 2016/679\.Note:[https://gdpr\-info\.eu/](https://gdpr-info.eu/)Accessed May 14, 2025Cited by:[§1](https://arxiv.org/html/2608.29360#S1.p1.1)\.
- \[10\]T\. M\. J\. Fruchterman and E\. M\. Reingold\(1991\)Graph drawing by force\-directed placement\.Software: Practice and Experience21\(11\),pp\. 1129–1164\.External Links:[Document](https://dx.doi.org/10.1002/spe.4380211102)Cited by:[§4\.1](https://arxiv.org/html/2608.29360#S4.SS1.p5.1)\.
- \[11\]A\. A\. Ginart, M\. Y\. Guan, G\. Valiant, and J\. Zou\(2019\)Making ai forget you: data deletion in machine learning\.InProceedings of the 33rd International Conference on Neural Information Processing Systems,External Links:[Link](https://dl.acm.org/doi/pdf/10.5555/3454287.3454603)Cited by:[§2](https://arxiv.org/html/2608.29360#S2.p2.1)\.
- \[12\]A\. Golatkar, A\. Achille, and S\. Soatto\(2020\)Eternal sunshine of the spotless net: selective forgetting in deep networks\.In2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition \(CVPR\),Vol\.,pp\. 9301–9309\.External Links:[Link](https://arxiv.org/abs/1911.04933)Cited by:[§2](https://arxiv.org/html/2608.29360#S2.p2.1)\.
- \[13\]C\. Guo, T\. Goldstein, A\. Hannun, and L\. Van Der Maaten\(2020\)Certified data removal from machine learning models\.InProceedings of the 37th International Conference on Machine Learning \(ICML\),ICML’20\.External Links:[Link](https://arxiv.org/abs/1911.03030)Cited by:[§2](https://arxiv.org/html/2608.29360#S2.p2.1)\.
- \[14\]Q\. Guo, C\. Pan, H\. Zhang, and W\. Wang\(2025\)Efficient unlearning for spatio\-temporal graph \(student abstract\)\.Proceedings of the AAAI Conference on Artificial Intelligence39\(28\),pp\. 29382–29384\.External Links:[Link](https://ojs.aaai.org/index.php/AAAI/article/view/35259),[Document](https://dx.doi.org/10.1609/aaai.v39i28.35259)Cited by:[§2](https://arxiv.org/html/2608.29360#S2.p2.1),[§4\.1](https://arxiv.org/html/2608.29360#S4.SS1.p2.1)\.
- \[15\]Q\. Guo and W\. Wang\(2024\)HydroNet: a spatio\-temporal graph neural network for modeling hydraulic dependencies in urban wastewater systems\.InProceedings of the 32nd ACM International Conference on Advances in Geographic Information Systems,pp\. 717–718\.Cited by:[§4\.1](https://arxiv.org/html/2608.29360#S4.SS1.p1.1)\.
- \[16\]H\. He\(2025\)California traffic network datasets: metr\-la, pems\-bay, pems04 and pems08 for traffic speed and flow analysis\.IEEE Dataport\.External Links:[Document](https://dx.doi.org/10.21227/j49q-ch56),[Link](https://dx.doi.org/10.21227/j49q-ch56)Cited by:[§4\.1](https://arxiv.org/html/2608.29360#S4.SS1.p1.1)\.
- \[17\]Y\. Kang, S\. Gao, Y\. Liang, M\. Li, and J\. Kruse\(2020\)Multiscale dynamic human mobility flow dataset in the u\.s\. during the covid\-19 epidemic\.Scientific Data,pp\. 1–13\.Cited by:[§4\.1](https://arxiv.org/html/2608.29360#S4.SS1.p1.1)\.
- \[18\]J\. Körner\(1973\)Coding of an information source having ambiguous alphabet and the entropy of graphs\.InTransactions of the 6th Prague Conference on Information Theory,pp\. 411–425\.Cited by:[§2](https://arxiv.org/html/2608.29360#S2.p3.1)\.
- \[19\]D\. G\. Leibovici\(2009\)Defining spatial entropy from multivariate distributions of co\-occurrences\.InSpatial Information Theory,pp\. 392–404\.Cited by:[§2](https://arxiv.org/html/2608.29360#S2.p3.1)\.
- \[20\]A\. Li and Y\. Pan\(2016\)Structural information and dynamical complexity of networks\.IEEE Transactions on Information Theory62\(6\),pp\. 3290–3339\.External Links:[Document](https://dx.doi.org/10.1109/TIT.2016.2555904)Cited by:[§2](https://arxiv.org/html/2608.29360#S2.p3.1)\.
- \[21\]Y\. Li, R\. Yu, C\. Shahabi, and Y\. Liu\(2018\)Diffusion convolutional recurrent neural network: data\-driven traffic forecasting\.International Conference on Learning Representations\.Note:Available at[https://arxiv\.org/abs/1707\.01926](https://arxiv.org/abs/1707.01926)External Links:[Link](https://arxiv.org/abs/1707.01926)Cited by:[§2](https://arxiv.org/html/2608.29360#S2.p1.1)\.
- \[22\]NOAA Physical Sciences Laboratory\(2025\)CPC global temperature and precipitation datasets\.Note:Accessed: 2025\-05\-15External Links:[Link](https://downloads.psl.noaa.gov/Datasets/cpc_global_precip)Cited by:[§4\.1](https://arxiv.org/html/2608.29360#S4.SS1.p1.1)\.
- \[23\]L\. Page, S\. Brin, R\. Motwani, and T\. Winograd\(1999\)The PageRank citation ranking: bringing order to the Web\.Technical reportTechnical Report1999\-66,Stanford InfoLab\.Note:Previous number = SIDL\-WP\-1999\-0120Cited by:[§3\.2\.3](https://arxiv.org/html/2608.29360#S3.SS2.SSS3.p2.1)\.
- \[24\]M\. Rosvall and C\. T\. Bergstrom\(2008\)Maps of random walks on complex networks reveal community structure\.Proceedings of the National Academy of Sciences105\(4\),pp\. 1118–1123\.External Links:[Document](https://dx.doi.org/10.1073/pnas.0706851105)Cited by:[§2](https://arxiv.org/html/2608.29360#S2.p3.1)\.
- \[25\]P\. Veličković, G\. Cucurull, A\. Casanova, A\. Romero, P\. Liò, and Y\. Bengio\(2018\)Graph attention networks\.International Conference on Learning Representations\.External Links:[Link](https://arxiv.org/abs/1710.10903)Cited by:[§2](https://arxiv.org/html/2608.29360#S2.p1.1)\.
- \[26\]C\. Wang, M\. Huai, and D\. Wang\(2023\)Inductive graph unlearning\.InProceedings of the 32nd USENIX Conference on Security Symposium,SEC ’23\.External Links:ISBN 978\-1\-939133\-37\-3,[Link](https://arxiv.org/abs/2304.03093)Cited by:[§2](https://arxiv.org/html/2608.29360#S2.p2.1)\.
- \[27\]B\. Yu, H\. Yin, and Z\. Zhu\(2018\)Spatio\-temporal graph convolutional networks: a deep learning framework for traffic forecasting\.International Joint Conference on Artificial Intelligence,pp\. 3634–3640\.External Links:[Document](https://dx.doi.org/10.24963/ijcai.2018/505)Cited by:[§1](https://arxiv.org/html/2608.29360#S1.p2.1),[§2](https://arxiv.org/html/2608.29360#S2.p1.1)\.
- \[28\]H\. Zhang, B\. Wu, X\. Yang, X\. Yuan, X\. Liu, and X\. Yi\(2025\)Dynamic graph unlearning: a general and efficient post\-processing method via gradient transformation\.InProceedings of the ACM on Web Conference 2025,WWW ’25,New York, NY, USA,pp\. 931–944\.External Links:ISBN 9798400712746,[Link](https://doi.org/10.1145/3696410.3714911),[Document](https://dx.doi.org/10.1145/3696410.3714911)Cited by:[§2](https://arxiv.org/html/2608.29360#S2.p2.1),[§4\.1](https://arxiv.org/html/2608.29360#S4.SS1.p2.1)\.