通过子图虚拟边重构在时空图上的遗忘学习

# 通过子图虚拟边重构实现时空图遗忘
来源：https://arxiv.org/html/2608.29369
\\correspondingauthor

\\correspondingauthor

会议：第34届 ACM 地理信息系统进展国际会议；2026年11月3–6日；美国加利福尼亚州里弗赛德  
第34届 ACM 地理信息系统进展国际会议 \(SIGSPATIAL ’26\)，2026年11月3–6日，美国加利福尼亚州里弗赛德  
DOI:10\.1145/3841645\.3843433 (https://doi.org/10.1145/3841645.3843433)  
ISBN:979\-8\-4007\-2950\-8/2026/11  
CCS:计算方法学 机器学习  
CCS:信息系统 地理信息系统  
CCS:安全与隐私 安全服务  
Qiming Guo  
所属机构：德州农工大学科珀斯克里斯蒂分校，科珀斯克里斯蒂，德克萨斯州，美国  
邮箱：[qguo2@islander\.tamucc\.edu](mailto:[email protected])  
Wenbo Sun  
所属机构：代尔夫特理工大学，代尔夫特，荷兰  
邮箱：[w\.sun\-2@tudelft\.nl](mailto:[email protected])  
Chen Pan  
所属机构：德克萨斯大学圣安东尼奥分校，圣安东尼奥，德克萨斯州，美国  
邮箱：[chen\.pan@utsa\.edu](mailto:[email protected])  
Ye Wang  
所属机构：Biogen，剑桥，马萨诸塞州，美国  
邮箱：[ye\.wang@biogen\.com](mailto:[email protected])  
以及  
Wenlu Wang  
所属机构：德州农工大学科珀斯克里斯蒂分校，科珀斯克里斯蒂，德克萨斯州，美国  
邮箱：[wenlu\.wang@tamucc\.edu](mailto:[email protected])

© cc

###### 摘要

时空图被广泛用于建模复杂的动态过程，如时序预测、分子动力学和医疗健康监测。近年来，诸如GDPR和CCPA等严格的隐私法规为现有的时空图模型带来了重大新挑战，要求对未授权数据进行完全遗忘。由于时空图中的每个节点都会在空间和时间维度上全局扩散信息，现有主要为静态图和局部数据移除设计的遗忘方法无法在不产生与完全重新训练模型相近成本的情况下高效地擦除单个节点。为解决此问题，我们提出了CallosumNet，一个受胼胝体结构生物启发的时空图遗忘框架。CallosumNet做出了两项关键技术贡献：（1）它使用受生物启发的虚拟边重构子图；（2）它通过一个轻量级的元图集成层恢复子图间相互关联的时空依赖关系。在四个多样化真实世界数据集上的实证结果表明，CallosumNet在实现完全遗忘的同时，保持了非常接近黄金模型的准确性。代码已在https://github.com/wenlu-lab/STGraphUnlearning公开。

###### 关键词：

机器遗忘，时空图，图神经网络，隐私合规，GDPR

††cc\-license:by

四个面板展示了删除前的时空图，标记了待移除的节点，原始记录删除后残余影响的状态，以及完全重新训练后结构破碎、节点特征改变的状态。  
图 1\.时空图上的遗忘：\(a\)完整图；\(b\)标记同意被撤销的节点；\(c\)记录删除留下残余模型影响；\(d\)重新训练清除了影响但使图结构破碎并扭曲了剩余节点特征（\(v1v\_\{1\}–v3v\_\{3\}\)）。

四个面板展示了删除前的时空图，标记了待移除的节点，原始记录删除后残余影响的状态，以及完全重新训练后结构破碎、节点特征改变的状态。  
## 1\.引言

近期先进的时空图模型通过利用空间邻接性和时间连续性，有效捕捉了复杂动态过程，如城市交通流、分子相互作用和医疗健康监测。然而，这些强大模型的广泛部署日益面临严格的隐私法规，如《通用数据保护条例》（GDPR）和《加州消费者隐私法案》（CCPA），这些法规要求在用户请求时完全移除或遗忘敏感用户数据。

九步流程图展示了原始图如何通过ESC被划分为增强子图，节神经节和关键节点如何通过GGB形成元图和全局集成槽，以及子模型如何被训练、冻结、集成和部署。  
图 2\.CallosumNet系统构建。原始图\(a\)通过ESC转换为多个增强的局部子图\(d\)，然后GGB方法添加节神经节节点并识别关键节点以构建元图。

九步流程图展示了原始图如何通过ESC被划分为增强子图，节神经节和关键节点如何通过GGB形成元图和全局集成槽，以及子模型如何被训练、冻结、集成和部署。  
### 动机场景

以移动位置服务（例如，Google Maps）为例，图1 (https://arxiv.org/html/2608.29369#acmlabel1)\(a\)显示了智能手机（节点）形成一个具有丰富耦合关系的时空图流，包含带时间戳的GPS信号。假设部分用户撤销了对其位置数据的同意，需要删除这些设备及其所有关联边，如图1 (https://arxiv.org/html/2608.29369#acmlabel1)\(b\)所示。简单删除原始记录（图1 (https://arxiv.org/html/2608.29369#acmlabel1)\(c\)）并不能完全满足删除要求，因为它未能消除被撤销用户的潜在影响。相反，在清除这些记录后从头重新训练整个模型（图1 (https://arxiv.org/html/2608.29369#acmlabel1)\(d\)）虽然能清除影响，但会破坏长距离的空间和时间路径，严重降低剩余用户的准确性和可解释性，且重新训练成本高得令人望而却步。

本研究中，我们提出了CallosumNet，其灵感来源于胼胝体——一束约\(\\sim\)2\(\\times\)108条轴突纤维，使大脑两半球能够独立专门化同时保持同步（Aboitiz et al., 1992 (https://arxiv.org/html/2608.29369#bib.bib13)）。CallosumNet通过*子图虚拟边重构*镜像了这种组织方式：它将时空图划分为局部一致的子图，每个子图像独立的半球一样在其自身数据上进行独立训练，然后通过受生物启发的虚拟边和一个轻量级的元图集成层重构被切断的跨分区依赖——类似于连接两个半球的胼胝体。这种设计同时实现了精确遗忘（每个节点的影响仅限于一个子图）并保持了预测准确性（无需在子图间共享训练数据即可恢复全局上下文）。

## 2\.相关工作

图遗忘方法主要分为近似方法和基于分区的方法。近似方法，如影响函数（Koh and Liang, 2017 (https://arxiv.org/html/2608.29369#bib.bib12)）和GNNDelete（Cheng et al., 2023 (https://arxiv.org/html/2608.29369#bib.bib1)），避免了完全重新训练，但只提供近似移除，并且没有明确处理时空依赖关系。基于分区的方法，包括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)）和STEPs（Guo et al., 2025 (https://arxiv.org/html/2608.29369#bib.bib6)），通过仅重新训练受影响的分区来实现高效或精确遗忘，但分区边界可能会破坏空间和时间依赖性，而固定的聚合无法完全恢复丢失的上下文。CallosumNet通过使用虚拟节神经节边保留跨分区依赖，并通过一个可学习的桥接层恢复全局上下文，填补了这一空白。

## 3\.方法论

我们提出CallosumNet（图2 (https://arxiv.org/html/2608.29369#acmlabel2)），一个用于时空图遗忘的分区-集成框架。给定一个在图\(\\mathcal\{G\}^\{\\prime\}=\(\\mathcal\{V\}^\{\\prime\},\\mathcal\{E\}^\{\\prime\},\\mathbf\{X\}^\{\\prime\}\)上训练的ST-GNN，其中特征\(\\mathbf\{X\}^\{\\prime\}\\in\\mathbb\{R\}^\{T\\times N^\{\\prime\}\\times F\}\)持续\(T\)个时间步，以及一个待擦除的节点和边的删除请求\(\\mathcal\{U\}=\(\\mathcal\{U\}\_\{N\},\\mathcal\{U\}\_\{E\}\)，目标是获得一个行为等同于从未在\(\\mathcal\{U\}\)上训练过的模型。CallosumNet由两个组件组成：用于图分解的增强子图构建（ESC），以及用于恢复全局一致性的全局节神经节桥接（GGB），组织成一个三步流程。

1\. 划分（ESC）。增强子图构建（Enhanced Subgraph Construction）将原始时空图沿相关性驱动的骨干网络切割成\(M\)个局部一致的子图，并用虚拟节神经节边修补每个切口，以保持高阶空间-时间路径。
2\. 连接（GGB）。全局节神经节桥接（Global Ganglion Bridging）将子图组装成一个轻量级元图：它提升前\(K\)个关键节点、接口边界节点和新创建的节神经节节点为元图顶点，并将它们稀疏地连接在一起。每个子图被独立训练（之后可以冻结）。它们的嵌入通过一个位于元图层之上的跨融合Transformer进行路由，并输出最终预测。
3\. 按需遗忘。当收到删除请求时，仅重新训练包含目标节点/边的子图；元图参数进行微调，而未触及的子图保持冻结状态。

1\. 增强子图构建（ESC）将\(\\mathcal\{G\}^\{\\prime\}\)分解为\(M\)个局部化子图，同时通过虚拟节神经节边维持全局依赖关系。对于每个有向边\((u,v)\\in\\mathcal\{E\}^\{\\prime\}\)，我们计算一个\(W\)步的时间相关性\(\\rho\(u,v\)=\\frac\{1\}\{W\}\\sum_\{t=1\}^\{W\}\\text\{corr\}\\\!\\bigl\(X^\{\\prime\}\_\{t,u\},X^\{\\prime\}\_\{t\+1,v\}\\bigr\)\)，并提取骨干路径\(\\mathcal\{D\}=\\arg\\max_\{\\mathcal\{P\}\}\\sum_\{\(u,v\)\\in\\mathcal\{P\}\}\\rho\(u,v\)\)，其中\(\\mathcal\{P\}\)遍历\(\\mathcal\{V\}^\{\\prime\}\)上的所有哈密顿路径。由于此最大化是NP难问题，我们通过贪婪算法近似求解，该算法迭代地添加具有最高相关性的邻居。节点根据其骨干索引分配给子图：\(\\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\\\}\)，其中\(N^\{\\prime\}=|\\mathcal\{V\}^\{\\prime\}|\)。\(\\mathcal\{V\}\_\{i\}\)内部的边形成\(\\mathbf\{A\}\_\{i\}\)；其余的边构成切集\(\\mathcal\{E\}\_\{\\text\{cut\}\}\)。孤立的顶点被重新连接到它们在\(\\mathcal\{D\}\)上的两个最近邻，并且对于每个\((u,v)\\in\\mathcal\{E\}\_\{\\text\{cut\}\}\)，我们插入一个虚拟节神经节边以保持高阶依赖关系。

此外，ESC在每个子图内应用*K环*增强：边界节点（那些与切边关联的节点）根据其在弹簧布局嵌入中的角度位置排序，并按顺序连接成一个闭合环，因此受分区影响最大的边界节点保持相互连接。分区数的选择为\(M^\{\*\}\\;=\\;\\arg\\min_\{M\}\\Bigl\[\\,\\Delta_\{\\text\{cut\}\}\+\\gamma\\log M\\Bigr\]\)，其中\(\\Delta_\{\\text\{cut\}\}=\\\!\\\!\\sum_\{\(u,v\)\\in\\mathcal\{E\}\_\{\\text\{cut\}\}\}\\\!\\\!\\rho\(u,v\)\)，\(\\gamma\)平衡相关性损失与模型并行性。

定理 1\.在等大小约束下最小化\(\\Delta_\{\\text\{cut\}\}\)是NP难的，但贪婪骨干提供了\((1\-\\tfrac\{1\}\{e\})\)近似。

定理 2\.ESC的运行时间为\(O\\\!\\bigl\(T|\\mathcal\{E\}^\{\\prime\}|\+N^\{\\prime 2\}/M\\bigr\)，存储\(O\(N^\{\\prime 2\}/M\)\)条边，当\(M=\\Theta\(\\sqrt\{N^\{\\prime\}\}\)\)时，其存储关于\(N^\{\\prime\}\)是次线性的。此外，它保留了至少\(\text\{Info\}\_\{\\text\{intra\}\}\\geq\\bigl\(1\-\\frac\{\\Delta_\{\\text\{cut\}\}\}\{\\text\{TotalCorr\}\}\\bigr\)\\text\{TotalCorr\}的总时间相关性。

### 证明概要

虚拟节神经节边将每个孤立顶点重新连接到一个具有\(A^\{\\prime\}\[u,v\]\>0\)的邻居（这样的邻居存在，因为\(\\mathcal\{G\}^\{\\prime\}\)是连通的），并且由于\(\\mathcal\{E\}^\{\\prime\}=\\bigcup_\{i\}\\mathcal\{E\}\_\{i\}\\cup\\mathcal\{E\}\_\{\\text\{cut\}\}\)，保留的相关性正好是\(\text\{TotalCorr\}\-\\Delta_\{\\text\{cut\}\}\)；一个平衡切割下界\(\\Delta_\{\\text\{cut\}\}\\geq\\frac\{c\}\{M\}\\text\{diam\}\(\\mathcal\{G\}^\{\\prime\}\)\)表明贪婪骨干接近最优。

六步遗忘流程图：识别待遗忘的节点，从宿主子图中移除它们，使用虚拟节点、边和K环重构子图，替换冻结的子模型，重置和更新全局集成槽，以及重新部署CallosumNet。  
图 3\.CallosumNet遗忘过程

六步遗忘流程图：识别待遗忘的节点，从宿主子图中移除它们，使用虚拟节点、边和K环重构子图，替换冻结的子模型，重置和更新全局集成槽，以及重新部署CallosumNet。  
2\. 全局节神经节桥接（GGB）通过将\(M\)个子图拼接成一个轻量级元图\(\\mathcal\{M\}\=\(\\mathcal\{V\}\_\{\\text\{meta\}\},\\mathcal\{E\}\_\{\\text\{meta\}\}\)\)及其邻接矩阵\(\\mathbf\{A\}\_\{\\text\{meta\}\}\)来重构全局时空依赖关系。它集成了三种类型的顶点：（i）*关键节点*（每个子图的前\(K\)个PageRank值，\(K=\\lceil\\log|\\mathcal\{V\}\_\{i\}|\\rceil\)），（ii）与切边关联的*边界节点*，以及（iii）*节神经节节点*，每个节点由一个具有ReLU激活的两层MLP参数化。

令\(\\mathcal\{E\}\_\{\\text\{agg\}\}\)表示原始的跨分区边（即\(\\mathcal\{E\}\_\{\\text\{cut\}\}\)中现在连接跨子图边界的边），\(\\mathcal\{E\}\_\{\\text\{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\}\}\)，并被稀疏化直到\(|\\mathcal\{E\}\_\{\\text\{meta\}\}|\approx O\(M\\log M\)\)。每个子图由一个冻结的STGCN（Yu et al., 2018 (https://arxiv.org/html/2608.29369#bib.bib2)）编码\(h\_\{v\}=\\text\{STGCN\}\(X^\{\\prime\}\[:,v,:\],\\mathbf\{A\}\_\{i\}\)\)，并通过以下损失函数优化：

\(\\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\}\),

从而隔离\(\\mathcal\{U\}\)。Token级别的输出和节神经节嵌入通过一个