Unlearning on Spatio-Temporal Graphs through Subgraph Virtual Edge Reconstruction

# Unlearning on Spatio-Temporal Graphs through Subgraph Virtual Edge Reconstruction
Source: [https://arxiv.org/html/2608.29369](https://arxiv.org/html/2608.29369)
\\correspondingauthor

\\correspondingauthor

Conference:The 34th ACM International Conference on Advances in Geographic Information Systems; November 03–06, 2026; Riverside, CA, USAThe 34th ACM International Conference on Advances in Geographic Information Systems \(SIGSPATIAL ’26\), November 03–06, 2026, Riverside, CA, USADOI:[10\.1145/3841645\.3843433](https://doi.org/10.1145/3841645.3843433)ISBN:979\-8\-4007\-2950\-8/2026/11CCS:Computing methodologies Machine learningCCS:Information systems Geographic information systemsCCS:Security and privacy Security servicesQiming GuoAffiliation:Texas A&M University \- Corpus Christi,Corpus Christi,Texas,USAemail:[qguo2@islander\.tamucc\.edu](mailto:[email protected])Wenbo SunAffiliation:Delft University of Technology,Delft,Netherlandsemail:[w\.sun\-2@tudelft\.nl](mailto:[email protected]),Chen PanAffiliation:University of Texas at San Antonio,San Antonio,Texas,USAemail:[chen\.pan@utsa\.edu](mailto:[email protected]),Ye WangAffiliation:Biogen,Cambridge,Massachusetts,USAemail:[ye\.wang@biogen\.com](mailto:[email protected])andWenlu WangAffiliation:Texas A&M University \- Corpus Christi,Corpus Christi,Texas,USAemail:[wenlu\.wang@tamucc\.edu](mailto:[email protected])

© cc

###### Abstract\.

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 usingbiologically\-inspired virtual edges; and \(2\) it restoresinterlinked spatio\-temporal dependenciesamong 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](https://github.com/wenlu-lab/STGraphUnlearning)\.

###### Keywords:

Machine Unlearning, Spatio\-Temporal Graph, Graph Neural Networks, Privacy Compliance, GDPR

††cc\-license:by![Four panels showing a spatio-temporal graph before deletion, with nodes marked for removal, after raw record deletion with residual influence, and after full retraining with fragmented structure and altered node features.](https://arxiv.org/html/2608.29369v1/NIPS_Figure1.png)Figure 1\.Unlearning on an ST\-graph: \(a\) full graph; \(b\) consent\-revoked nodes marked; \(c\) record deletion leaves residual model influence; \(d\) retraining purges it but fragments the graph and distorts remaining features \(v1v\_\{1\}–v3v\_\{3\}\)\.Four panels showing a spatio\-temporal graph before deletion, with nodes marked for removal, after raw record deletion with residual influence, and after full retraining with fragmented structure and altered node features\.## 1\.Introduction

Recent advanced spatio\-temporal graph models effectively capture complex dynamic processes, such as urban traffic flows, molecular interactions, and healthcare monitoring, by harnessing both spatial adjacency and temporal continuity\. However, the broad deployment of these powerful models increasingly faces stringent privacy regulations, such as the General Data Protection Regulation \(GDPR\) and the California Consumer Privacy Act \(CCPA\), which necessitate the complete removal orunlearningof sensitive user data upon request\.

![Nine-step pipeline diagram showing how the original graph is partitioned into enhanced subgraphs via ESC, how ganglion and key nodes form the meta-graph and global integration slot via GGB, and how sub-models are trained, frozen, integrated, and deployed.](https://arxiv.org/html/2608.29369v1/NIPS_Figure2.png)Figure 2\.CallosumNet system construction\. The original graph \(a\) is transformed into multiple enhanced local subgraphs \(d\) through ESC, and then the GGB method adds ganglion nodes and identifies key nodes to construct the meta\-graph\.Nine\-step pipeline diagram showing how the original graph is partitioned into enhanced subgraphs via ESC, how ganglion and key nodes form the meta\-graph and global integration slot via GGB, and how sub\-models are trained, frozen, integrated, and deployed\.### Motivating scenario\.

Taking a mobile–location service \(e\.g\., Google Maps\) as an example, Figure[1](https://arxiv.org/html/2608.29369#acmlabel1)\(a\) shows smartphones \(nodes\) forming a richly coupled spatio\-temporal graph stream of time\-stamped GPS signals\. Suppose a subset of users revokes consent for their location data, necessitating the deletion of these devices and all incident edges, as shown in Figure[1](https://arxiv.org/html/2608.29369#acmlabel1)\(b\)\. Simply dropping the raw records \(Figure[1](https://arxiv.org/html/2608.29369#acmlabel1)\(c\)\) does not fully satisfy the deletion requirement, as it fails to eliminate the latent influence of the revoked users\. Conversely, retraining the entire model from scratch after purging those records \(Figure[1](https://arxiv.org/html/2608.29369#acmlabel1)\(d\)\) erases the influence but fragments long\-range spatial and temporal paths, severely degrading accuracy and interpretability for the remaining users, with a prohibitively high retraining cost\.

In this study, we propose CallosumNet, inspired by the corpus callosum, a bundle of∼\\sim2×\\times108axonal fibers that enables the two cerebral hemispheres to specialize independently while staying synchronized\([Aboitiz et al\., 1992](https://arxiv.org/html/2608.29369#bib.bib13)\)\. CallosumNet mirrors this organization through*subgraph virtual edge reconstruction*: it partitions the ST\-graph into locally coherent subgraphs, each trained exclusively on its own data like an independent hemisphere, and then reconstructs the severed cross\-partition dependencies through biologically\-inspired virtual edges and a lightweight meta\-graph integration layer—analogous to the corpus callosum bridging the two hemispheres\. This design simultaneously enables exact unlearning \(each node’s influence is confined to one subgraph\) and preserves predictive accuracy \(global context is recovered without sharing training data across subgraphs\)\.

## 2\.Related Work

Graph unlearning methods mainly fall into approximate and partition\-based approaches\. Approximate methods, such as influence functions\([Koh and Liang, 2017](https://arxiv.org/html/2608.29369#bib.bib12)\)and GNNDelete\([Cheng et al\., 2023](https://arxiv.org/html/2608.29369#bib.bib1)\), avoid full retraining but provide only approximate removal and do not explicitly handle spatio\-temporal dependencies\. Partition\-based methods, including SISA\([Bourtoule et al\., 2021](https://arxiv.org/html/2608.29369#bib.bib4)\), GraphEraser\([Chen et al\., 2022](https://arxiv.org/html/2608.29369#bib.bib5)\), GraphRevoker\([Zhang et al\., 2025](https://arxiv.org/html/2608.29369#bib.bib7)\), and STEPs\([Guo et al\., 2025](https://arxiv.org/html/2608.29369#bib.bib6)\), enable efficient or exact unlearning by retraining only affected partitions, but partition boundaries can break spatial and temporal dependencies, while fixed aggregation cannot fully recover the lost context\. CallosumNet addresses this gap by preserving cross\-partition dependencies with virtual ganglion edges and restoring global context through a learnable bridging layer\.

## 3\.Methodology

We proposeCallosumNet\(Figure[2](https://arxiv.org/html/2608.29369#acmlabel2)\), a partition\-and\-integrate framework for spatio\-temporal graph unlearning\. Given an ST\-GNN trained on a graph𝒢′=\(𝒱′,ℰ′,𝐗′\)\\mathcal\{G\}^\{\\prime\}=\(\\mathcal\{V\}^\{\\prime\},\\mathcal\{E\}^\{\\prime\},\\mathbf\{X\}^\{\\prime\}\)with features𝐗′∈ℝT×N′×F\\mathbf\{X\}^\{\\prime\}\\in\\mathbb\{R\}^\{T\\times N^\{\\prime\}\\times F\}overTTsteps, and a deletion request𝒰=\(𝒰N,𝒰E\)\\mathcal\{U\}=\(\\mathcal\{U\}\_\{N\},\\mathcal\{U\}\_\{E\}\)of nodes and edges to erase, the goal is a model that behaves as if𝒰\\mathcal\{U\}had never been trained on\. CallosumNet consists of two components:Enhanced Subgraph Construction \(ESC\)for graph decomposition, andGlobal Ganglion Bridging \(GGB\)to restore global coherence, organized in a three\-step pipeline\.

1\. Divide \(ESC\)\.Enhanced Sub\-graph Construction slices the original ST\-graph intoMMlocally coherent sub\-graphs along a correlation\-driven backbone and patches every cut with virtual ganglion edges so that high\-order spatial–temporal paths are preserved\.2\. Link \(GGB\)\.Global Ganglion Bridging then assembles the sub\-graphs into a lightweight meta\-graph: it promotes the top\-KKkey nodes, the interface boundary nodes, and the newly created ganglion nodes to meta\-graph vertices and sparsely wires them together\. Each sub\-graph is trained independently \(and can be frozen afterwards\)\. Their embeddings are routed through a cross\-fusion Transformer that sits on the meta\-graph layer and outputs the final prediction\.3\. Unlearning on demand\.When a deletion request arrives, only the sub\-graphs that contain the target nodes/edges are re\-trained; the meta\-graph parameters are fine\-tuned, while untouched sub\-graphs remain frozen\.

1\. Enhanced Subgraph Construction \(ESC\)decomposes𝒢′\\mathcal\{G\}^\{\\prime\}intoMMlocalized subgraphs while maintaining global dependencies through virtual ganglion edges\. For each directed edge\(u,v\)∈ℰ′\(u,v\)\\in\\mathcal\{E\}^\{\\prime\}, we compute aWW\-step temporal correlationρ⁡\(u,v\)=1W​∑t=1Wcorr​\(Xt,u′,Xt\+1,v′\),\\rho\(u,v\)\\;=\\;\\frac\{1\}\{W\}\\sum\_\{t=1\}^\{W\}\\text\{corr\}\\\!\\bigl\(X^\{\\prime\}\_\{t,u\},X^\{\\prime\}\_\{t\+1,v\}\\bigr\),and extract a backbone path𝒟=arg⁡max⁡∑\(u,v\)∈𝒫𝒫⁡ρ⁡\(u,v\)\\mathcal\{D\}=\\arg\\max\_\{\\mathcal\{P\}\}\\sum\_\{\(u,v\)\\in\\mathcal\{P\}\}\\rho\(u,v\), where𝒫\\mathcal\{P\}ranges over all Hamiltonian paths on𝒱′\\mathcal\{V\}^\{\\prime\}\. Since this maximization is NP\-hard, we solve it approximately via a greedy algorithm that iteratively appends the highest\-correlation neighbor\. Nodes are assigned to subgraphs according to their backbone index:𝒱i=\{v∈𝒟\|⌊\(i−1\)N′M⌋≤idx\(v\)<⌊iN′M⌋\},\\mathcal\{V\}\_\{i\}=\\bigl\\\{\\,v\\\!\\in\\\!\\mathcal\{D\}\\,\\bigl\\lvert\\,\\lfloor\(i\{\-\}1\)\\tfrac\{N^\{\\prime\}\}\{M\}\\rfloor\\leq\\text\{idx\}\(v\)<\\lfloor i\\tfrac\{N^\{\\prime\}\}\{M\}\\rfloor\\bigr\\\},whereN′=\|𝒱′\|N^\{\\prime\}=\|\\mathcal\{V\}^\{\\prime\}\|\. Edges internal to𝒱i\\mathcal\{V\}\_\{i\}form𝐀i\\mathbf\{A\}\_\{i\}; the remainder are the cut setℰcut\\mathcal\{E\}\_\{\\text\{cut\}\}\. Isolated vertices are re\-connected to their two nearest neighbours on𝒟\\mathcal\{D\}, and for every\(u,v\)∈ℰcut\(u,v\)\\in\\mathcal\{E\}\_\{\\text\{cut\}\}we insert a virtual ganglion edge to preserve high\-order dependencies\.

Additionally, ESC applies a*K\-Ring*augmentation within each subgraph: boundary nodes \(those incident to cut edges\) are sorted by their angular positions in a spring\-layout embedding and connected sequentially into a closed ring, so that boundary nodes—most affected by partitioning—stay mutually connected\. The number of partitions is chosen byM∗=arg⁡minM⁡\[Δcut\+γ​log⁡M\]M^\{\*\}\\;=\\;\\arg\\min\_\{M\}\\Bigl\[\\,\\Delta\_\{\\text\{cut\}\}\+\\gamma\\log M\\Bigr\],Δcut=∑\(u,v\)∈ℰcutρ⁡\(u,v\),\\Delta\_\{\\text\{cut\}\}=\\\!\\\!\\sum\_\{\(u,v\)\\in\\mathcal\{E\}\_\{\\text\{cut\}\}\}\\\!\\\!\\rho\(u,v\),withγ\\gammabalancing correlation loss against model parallelism\.

Theorem 1\.MinimisingΔcut\\Delta\_\{\\text\{cut\}\}under equal\-size constraints is NP\-hard, yet the greedy backbone yields a\(1−1e\)\(1\-\\tfrac\{1\}\{e\}\)approximation\.

Theorem 2\.ESC runs inO⁡\(T​\|ℰ′\|\+N′2/M\)O\\\!\\bigl\(T\|\\mathcal\{E\}^\{\\prime\}\|\+N^\{\\prime 2\}/M\\bigr\)time and storesO⁡\(N′2/M\)O\(N^\{\\prime 2\}/M\)edges, which is sub\-linear inN′N^\{\\prime\}whenM=Θ⁡\(N′\)M=\\Theta\(\\sqrt\{N^\{\\prime\}\}\)\. Moreover it retains at leastInfointra≥\(1−ΔcutTotalCorr\)​TotalCorr\\text\{Info\}\_\{\\text\{intra\}\}\\geq\\bigl\(1\-\\frac\{\\Delta\_\{\\text\{cut\}\}\}\{\\text\{TotalCorr\}\}\\bigr\)\\text\{TotalCorr\}of the total temporal correlation\.

### Proof sketch\.

Virtual ganglion edges reconnect every isolated vertex to a neighbor withA′​\[u,v\]\>0A^\{\\prime\}\[u,v\]\>0\(which exists since𝒢′\\mathcal\{G\}^\{\\prime\}is connected\), and sinceℰ′=⋃iℰi∪ℰcut\\mathcal\{E\}^\{\\prime\}=\\bigcup\_\{i\}\\mathcal\{E\}\_\{i\}\\cup\\mathcal\{E\}\_\{\\text\{cut\}\}, the retained correlation is exactlyTotalCorr−Δcut\\text\{TotalCorr\}\-\\Delta\_\{\\text\{cut\}\}; a balanced\-cut lower boundΔcut≥cM​diam​\(𝒢′\)\\Delta\_\{\\text\{cut\}\}\\geq\\frac\{c\}\{M\}\\text\{diam\}\(\\mathcal\{G\}^\{\\prime\}\)shows the greedy backbone is near\-optimal\.

![Six-step diagram of the unlearning process: identifying nodes to unlearn, removing them from the host subgraph, reconstructing the subgraph with virtual nodes, edges, and K-Ring, replacing the frozen sub-model, resetting and updating the global integration slot, and redeploying CallosumNet.](https://arxiv.org/html/2608.29369v1/NIPS_Figure3.png)Figure 3\.CallosumNet unlearning processSix\-step diagram of the unlearning process: identifying nodes to unlearn, removing them from the host subgraph, reconstructing the subgraph with virtual nodes, edges, and K\-Ring, replacing the frozen sub\-model, resetting and updating the global integration slot, and redeploying CallosumNet\.2\. Global Ganglion Bridging \(GGB\)reconstructs global spatio\-temporal dependencies by stitching theMMsub\-graphs into a lightweight meta\-graphℳ=\(𝒱meta,ℰmeta\)\\mathcal\{M\}=\(\\mathcal\{V\}\_\{\\text\{meta\}\},\\mathcal\{E\}\_\{\\text\{meta\}\}\)with adjacency matrix𝐀meta\\mathbf\{A\}\_\{\\text\{meta\}\}\. It integrates three types of vertices: \(i\)*key nodes*\(top\-KKPageRank per sub\-graph,K=⌈log⁡\|𝒱i\|⌉K=\\lceil\\log\|\\mathcal\{V\}\_\{i\}\|\\rceil\), \(ii\)*boundary nodes*incident to cut edges, and \(iii\)*ganglion nodes*, each parameterised by a two\-layer MLP with ReLU\.

Letℰagg\\mathcal\{E\}\_\{\\text\{agg\}\}denote the original cross\-partition edges \(i\.e\., edges inℰcut\\mathcal\{E\}\_\{\\text\{cut\}\}that now connect boundary nodes across subgraphs\), andℰkey\\mathcal\{E\}\_\{\\text\{key\}\}the edges among key nodes within the same subgraph\. The meta\-graph edges are then defined asℰmeta=ℰagg∪\{\(u,g\),\(g,v\)∣g∈𝒱ganglion,u,v∈𝒱key∪𝒱boundary\}∪ℰkey,\\mathcal\{E\}\_\{\\text\{meta\}\}=\\mathcal\{E\}\_\{\\text\{agg\}\}\\cup\\bigl\\\{\(u,g\),\(g,v\)\\mid g\\\!\\in\\\!\\mathcal\{V\}\_\{\\text\{ganglion\}\},u,v\\\!\\in\\\!\\mathcal\{V\}\_\{\\text\{key\}\}\\cup\\mathcal\{V\}\_\{\\text\{boundary\}\}\\bigr\\\}\\cup\\mathcal\{E\}\_\{\\text\{key\}\},and are sparsified until\|ℰmeta\|≈O⁡\(M​log⁡M\)\\lvert\\mathcal\{E\}\_\{\\text\{meta\}\}\\rvert\\approx O\(M\\log M\)\. Each sub\-graph is encoded by a frozen STGCN\([Yu et al\., 2018](https://arxiv.org/html/2608.29369#bib.bib2)\)hv=STGCN\(X′\[:,v,:\],𝐀i\)h\_\{v\}=\\text\{STGCN\}\(X^\{\\prime\}\[:,v,:\],\\mathbf\{A\}\_\{i\}\)optimised via

ℒsub=∑v∈𝒱i∖𝒰‖yv−predSi​\(v\)‖22\+λreg​∥θi∥22\\mathcal\{L\}\_\{\\text\{sub\}\}=\\sum\_\{v\\in\\mathcal\{V\}\_\{i\}\\setminus\\mathcal\{U\}\}\\bigl\\\|y\_\{v\}\-\\text\{pred\}\_\{S\_\{i\}\}\(v\)\\bigr\\\|\_\{2\}^\{2\}\+\\lambda\_\{\\text\{reg\}\}\\lVert\\theta\_\{i\}\\rVert\_\{2\}^\{2\},

thereby isolating𝒰\\mathcal\{U\}\. Token\-level outputs and ganglion embeddings are fused through a cross\-attention Transformer:hfinal=α​htok\+\(1−α\)​hgangh^\{\\text\{final\}\}=\\alpha h^\{\\text\{tok\}\}\+\(1\-\\alpha\)h^\{\\text\{gang\}\},

y^v=Transformer​\(\{hu′,hg\},𝐀meta\)\\hat\{y\}\_\{v\}=\\text\{Transformer\}\\bigl\(\\\{h^\{\\prime\}\_\{u\},h\_\{g\}\\\},\\,\\mathbf\{A\}\_\{\\text\{meta\}\}\\bigr\),

whereα\\alphais a learnable scalar initialised to0\.50\.5and clipped to\[0,1\]\[0,1\]\. The overall loss isℒggb=∑v∥yv−y^v∥22\+λ1​∥𝐀meta∥1\+λ2​∑g∥hg∥22,\\mathcal\{L\}\_\{\\text\{ggb\}\}=\\sum\_\{v\}\\lVert y\_\{v\}\-\\hat\{y\}\_\{v\}\\rVert\_\{2\}^\{2\}\+\\lambda\_\{1\}\\lVert\\mathbf\{A\}\_\{\\text\{meta\}\}\\rVert\_\{1\}\+\\lambda\_\{2\}\\sum\_\{g\}\\lVert h\_\{g\}\\rVert\_\{2\}^\{2\},whereλ1,λ2≥0\\lambda\_\{1\},\\lambda\_\{2\}\\geq 0control sparsity and embedding regularization, respectively\.

Theorem 3 \(Prediction error bound\)\.For a graph𝒢′\\mathcal\{G\}^\{\\prime\}partitioned intoMMsub\-graphs,

‖y^full−y^GGB‖2≤Capprox​Δcut​MH​L​Dg\\bigl\\\|\\hat\{y\}\_\{\\text\{full\}\}\-\\hat\{y\}\_\{\\text\{GGB\}\}\\bigr\\\|\_\{2\}\\;\\leq\\;C\_\{\\text\{approx\}\}\\,\\frac\{\\Delta\_\{\\text\{cut\}\}\\sqrt\{M\}\}\{H\\,L\\,D\_\{g\}\}whereHH,LL,DgD\_\{g\}are the fusion Transformer’s head count, depth, and ganglion width, andCapproxC\_\{\\text\{approx\}\}is an architecture\-dependent constant \(see proof sketch\)\. This bound stays below0\.050\.05wheneverM≤16M\\\!\\leq\\\!16andN′≤104N^\{\\prime\}\\\!\\leq\\\!10^\{4\}\.

Theorem 4 \(Unlearning stability\)\.After erasing an arbitrary set𝒰\\mathcal\{U\},

𝔼⁡\[∥y^v−y^vunlearn∥22\|v∉𝒰\]≤Δcut​\|𝒰\|\(\|𝒱′\|−\|𝒰\|\)​H​L​Dg\\mathbb\{E\}\\\!\\bigl\[\\lVert\\hat\{y\}\_\{v\}\-\\hat\{y\}\_\{v\}^\{\\text\{unlearn\}\}\\rVert\_\{2\}^\{2\}\\;\\bigl\|\\;v\\notin\\mathcal\{U\}\\bigr\]\\;\\leq\\;\\frac\{\\Delta\_\{\\text\{cut\}\}\\lvert\\mathcal\{U\}\\rvert\}\{\(\\lvert\\mathcal\{V\}^\{\\prime\}\\rvert\-\\lvert\\mathcal\{U\}\\rvert\)\\,H\\,L\\,D\_\{g\}\}and the fine\-tune converges to anε\\varepsilon\-accurate solution,ε=G2/\(2​η​Tep\)\\varepsilon=G^\{2\}/\(2\\eta\\sqrt\{T\_\{\\text\{ep\}\}\}\), for gradient boundGG, learning rateη\\eta, andTepT\_\{\\text\{ep\}\}fine\-tuning epochs\.

Theorem 5 \(Model complexity\)\.GGB contributes𝒪⁡\(M​log⁡M​Dg2\)\\mathcal\{O\}\(M\\log M\\,D\_\{g\}^\{2\}\)additional parameters on top of the𝒪⁡\(N​d2/M\)\\mathcal\{O\}\(Nd^\{2\}/M\)parameters of the sub\-graphs, and its per\-batch FLOPs are𝒪⁡\(B​T​\[\|ℰ\|/M\+M​log⁡M\]​d\)\\mathcal\{O\}\\\!\\bigl\(BT\\,\[\\,\|\\mathcal\{E\}\|/M\+M\\log M\\,\]\\,d\\bigr\)\. WithM=NM=\\sqrt\{N\}this yields a sub\-linear \(≈1/N\\approx 1/\\sqrt\{N\}\) speed\-up compared to a full\-graph ST\-GNN\.

### Proof sketch\.

Theorem 3 follows from the Transformer’s universal approximation property\([Yun et al\., 2020](https://arxiv.org/html/2608.29369#bib.bib3)\); Theorem 4’s rate is standard Adam analysis under bounded gradients; Theorem 5 countsO⁡\(d2​N/M\)O\(d^\{2\}N/M\)parameters per sub\-graph andO⁡\(M​log⁡M​Dg2\)O\(M\\log M\\,D\_\{g\}^\{2\}\)for the meta\-Transformer, soM=NM=\\sqrt\{N\}givesO⁡\(N​d2\)O\(\\sqrt\{N\}d^\{2\}\)total\.

3\. Unlearning On DemandAs shown in Figure[3](https://arxiv.org/html/2608.29369#acmlabel3), upon receiving a deletion request𝒰\\mathcal\{U\}, CallosumNet executes three steps:\(i\) Locate and remove\.The target nodes and edges are identified and zeroed out in their host subgraph\(s\); untouched subgraphs remain frozen\.\(ii\) Reconstruct and retrain\.ESC re\-enhances the affected subgraph\(s\) with virtual ganglion edges and K\-Ring connections, then retrains and freezes them\.\(iii\) Reset GGB\.The ganglion MLPs and cross\-fusion Transformer are reinitialized and fine\-tuned \(1–3 epochs\) on all subgraph outputs, completing the erasure\. Since each sub\-model trains*exclusively*on its own partition,𝒰\\mathcal\{U\}’s training signal resides only in its host subgraph\(s\) and the GGB layer; retraining both leaves the model identical in distribution to one retrained from scratch, i\.e\.,I⁡\(y^,𝒰\)=0I\(\\hat\{y\};\\mathcal\{U\}\)=0, by the same shard\-isolation argument as SISA\([Bourtoule et al\., 2021](https://arxiv.org/html/2608.29369#bib.bib4)\)\.

Table 1\.Average relative MAE degradation \(%\) versus the gold model, averaged over four backbones \(STGCN\([Yu et al\., 2018](https://arxiv.org/html/2608.29369#bib.bib2)\), ST\-GAT\([Veličković et al\., 2018](https://arxiv.org/html/2608.29369#bib.bib15)\), ST\-GATV2\([Brody et al\., 2022](https://arxiv.org/html/2608.29369#bib.bib16)\), ST\-SAGE\([Hamilton et al\., 2017](https://arxiv.org/html/2608.29369#bib.bib14)\)\)\. Negative values indicate that the method outperforms the gold model\.DatasetRateSISASTEPsGEGROursRWW0%\+65\.3%\+276\.4%\+734\.0%\+725\.8%\+0\.0%10%\+57\.1%\+302\.4%\+708\.9%\+664\.8%−\-3\.2%PeMS080%\+19\.1%\+183\.9%\+107\.5%\+216\.1%\+1\.1%10%\+13\.7%\+211\.6%\+99\.0%\+211\.2%\+1\.0%Weather0%\+9\.6%\+55\.1%\+47\.5%\+66\.8%\+4\.2%10%\+10\.6%\+55\.3%\+49\.3%\+66\.1%\+5\.1%Mobility0%\+27\.4%\+150\.5%\+75\.0%\+251\.8%\+7\.2%10%\+28\.2%\+152\.8%\+81\.3%\+231\.7%\+14\.4%Overall Avg\+28\.9%\+173\.5%\+237\.8%\+304\.3%\+3\.7%GE = GraphEraser, GR = GraphRevoker, Ours = CallosumNet\.

## 4\.Evaluation

We evaluate on four spatio\-temporal graph datasets \(23–3,220 nodes\): RWW\([Guo and Wang, 2024](https://arxiv.org/html/2608.29369#bib.bib8)\), PeMS08\([He, 2025](https://arxiv.org/html/2608.29369#bib.bib11)\), Global Weather\([NOAA Physical Sciences Laboratory, 2025](https://arxiv.org/html/2608.29369#bib.bib10)\), and Human Mobility Flow\([Kang et al\., 2020](https://arxiv.org/html/2608.29369#bib.bib9)\), against SISA\([Bourtoule et al\., 2021](https://arxiv.org/html/2608.29369#bib.bib4)\), STEPs\([Guo et al\., 2025](https://arxiv.org/html/2608.29369#bib.bib6)\), GraphEraser\([Chen et al\., 2022](https://arxiv.org/html/2608.29369#bib.bib5)\), and GraphRevoker\([Zhang et al\., 2025](https://arxiv.org/html/2608.29369#bib.bib7)\)\. The*gold model*retrains the backbone from scratch on the post\-deletion graph and thus carries zero residual influence;*Rate*rris the fraction of nodes deleted uniformly at random \(5 fixed seeds\), sor=0%r\{=\}0\\%isolates partitioning overhead andr=10%r\{=\}10\\%measures post\-unlearning accuracy\. As Table[1](https://arxiv.org/html/2608.29369#S3.T1)summarizes, CallosumNet degrades MAE by only 3\.7% on average, versus 28\.9% for the best baseline \(SISA\) and over 170% for the rest; on Mobility \(N=3,220N\{=\}3\{,\}220\) it also cuts unlearning time from 12,640 s \(full retraining\) to 3,631 s atM=16M\{=\}16\.

## 5\.Conclusion

CallosumNet delivers exact spatio\-temporal graph unlearning with near\-gold accuracy and sub\-linear unlearning cost\. Limitations include the static\-adjacency assumption and meta\-graph overhead at largeMM; future work targets dynamic topologies and edge\-/feature\-level deletion requests\.

###### Acknowledgements\.

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

## References

- Aboitizet al\.\(1992\)F\. Aboitiz, A\. B\. Scheibel, R\. S\. Fisher, and E\. ZaidelFiber composition of the human corpus callosum\.Brain Research598\(1–2\),pp\. 143–153\.Cited by:[§1](https://arxiv.org/html/2608.29369#S1.SS0.SSS0.Px1.p2.1)\.
- Bourtouleet al\.\(2021\)L\. Bourtoule, V\. Chandrasekaran, C\. A\. Choquette\-Choo, H\. Jia, A\. Travers, B\. Zhang, D\. Lie, and N\. PapernotMachine unlearning\.In2021 IEEE symposium on security and privacy \(SP\),pp\. 141–159\.Cited by:[§2](https://arxiv.org/html/2608.29369#S2.p1.1),[§3](https://arxiv.org/html/2608.29369#S3.SS0.SSS0.Px2.p2.1),[§4](https://arxiv.org/html/2608.29369#S4.p1.1)\.
- Brodyet al\.\(2022\)S\. Brody, U\. Alon, and E\. YahavHow attentive are graph attention networks?\.InInternational Conference on Learning Representations \(ICLR\),Cited by:[Table 1](https://arxiv.org/html/2608.29369#S3.T1)\.
- Chenet al\.\(2022\)M\. Chen, Z\. Zhang, T\. Wang, M\. Backes, M\. Humbert, and Y\. ZhangGraph unlearning\.InProceedings of the 2022 ACM SIGSAC conference on computer and communications security,pp\. 499–513\.Cited by:[§2](https://arxiv.org/html/2608.29369#S2.p1.1),[§4](https://arxiv.org/html/2608.29369#S4.p1.1)\.
- Chenget al\.\(2023\)J\. Cheng, G\. Dasoulas, H\. He, C\. Agarwal, and M\. ZitnikGNNDelete: a general strategy for unlearning in graph neural networks\.InInternational Conference on Learning Representations \(ICLR\),Cited by:[§2](https://arxiv.org/html/2608.29369#S2.p1.1)\.
- Guoet al\.\(2025\)Q\. Guo, C\. Pan, H\. Zhang, and W\. WangEfficient 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.29369#S2.p1.1),[§4](https://arxiv.org/html/2608.29369#S4.p1.1)\.
- Guo and Wang \(2024\)Q\. Guo and W\. WangHydroNet: 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](https://arxiv.org/html/2608.29369#S4.p1.1)\.
- Hamiltonet al\.\(2017\)W\. L\. Hamilton, R\. Ying, and J\. LeskovecInductive representation learning on large graphs\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Vol\.30\.Cited by:[Table 1](https://arxiv.org/html/2608.29369#S3.T1)\.
- He \(2025\)H\. HeCalifornia 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](https://arxiv.org/html/2608.29369#S4.p1.1)\.
- Kanget al\.\(2020\)Y\. Kang, S\. Gao, Y\. Liang, M\. Li, and J\. KruseMultiscale dynamic human mobility flow dataset in the u\.s\. during the covid\-19 epidemic\.Scientific Data,pp\. 1–13\.Cited by:[§4](https://arxiv.org/html/2608.29369#S4.p1.1)\.
- Koh and Liang \(2017\)P\. W\. Koh and P\. LiangUnderstanding black\-box predictions via influence functions\.InICML,Cited by:[§2](https://arxiv.org/html/2608.29369#S2.p1.1)\.
- NOAA Physical Sciences Laboratory \(2025\)NOAA Physical Sciences LaboratoryCPC global temperature and precipitation datasets\.Note:Accessed: 2025\-05\-15External Links:[Link](https://downloads.psl.noaa.gov/Datasets/cpc_global_temp/Summary,%20https://downloads.psl.noaa.gov/Datasets/cpc_global_precip)Cited by:[§4](https://arxiv.org/html/2608.29369#S4.p1.1)\.
- Veličkovićet al\.\(2018\)P\. Veličković, G\. Cucurull, A\. Casanova, A\. Romero, P\. Liò, and Y\. BengioGraph attention networks\.InInternational Conference on Learning Representations \(ICLR\),Cited by:[Table 1](https://arxiv.org/html/2608.29369#S3.T1)\.
- Yuet al\.\(2018\)B\. Yu, H\. Yin, and Z\. ZhuSpatio\-temporal graph convolutional networks: a deep learning framework for traffic forecasting\.International Joint Conference on Artificial Intelligence \(IJCAI\),pp\. 3634–3640\.External Links:[Document](https://dx.doi.org/10.24963/ijcai.2018/505)Cited by:[§3](https://arxiv.org/html/2608.29369#S3.SS0.SSS0.Px1.p3.1),[Table 1](https://arxiv.org/html/2608.29369#S3.T1)\.
- Yunet al\.\(2020\)C\. Yun, S\. Bhojanapalli, A\. S\. Rawat, S\. J\. Reddi, and S\. KumarAre transformers universal approximators of sequence\-to\-sequence functions?\.International Conference on Learning Representations\.External Links:[Link](https://openreview.net/pdf?id=ByxZX0KtDr)Cited by:[§3](https://arxiv.org/html/2608.29369#S3.SS0.SSS0.Px2.p1.1)\.
- Zhanget al\.\(2025\)H\. Zhang, B\. Wu, X\. Yang, X\. Yuan, X\. Liu, and X\. YiDynamic graph unlearning: a general and efficient post\-processing method via gradient transformation\.InProceedings of the ACM on Web Conference 2025,pp\. 931–944\.Cited by:[§2](https://arxiv.org/html/2608.29369#S2.p1.1),[§4](https://arxiv.org/html/2608.29369#S4.p1.1)\.