一、研究背景
1、隐私法规与被遗忘权
近年来，随着《通用数据保护条例》（GDPR）、《加州消费者隐私法案》（CCPA）等法律法规的颁布，数据隐私保护成为了全球关注的焦点。其中最重要且最具争议的条款之一是“被遗忘权”（Right to be Forgotten）。这意味着数据主体（用户）有权要求服务提供商删除其存储的个人数据。
2、机器遗忘
在机器学习（ML）背景下，仅仅从数据库中删除数据是不够的，因为模型在训练过程中已经“记住”了这些数据的信息。为了真正合规，模型提供者必须消除被撤销数据对模型参数的影响。这一过程被称为“机器遗忘”。
传统方法：最彻底的方法是删除数据后**从头重新训练（Retraining from scratch）**模型。但这在计算上非常昂贵，尤其是当数据集很大、模型很复杂时，频繁的重训是不现实的。
近似方法（SISA）：为了加速，学术界提出了近似算法。其中最先进的是SISA(Sharded, Isolated, Sliced, and Aggregated) 框架。它的核心思想是将训练数据随机划分成多个不重叠的碎片（Shards），每个碎片训练一个子模型。当需要删除某条数据时，只需要重新训练该数据所在的那个碎片对应的子模型即可，从而大大节省时间。
3、图神经网络的兴起
现实世界中有大量数据是以图（Graph）的形式存在的，如社交网络、金融网络、生物网络等。图神经网络（GNN）在处理这些非欧几里得数据方面表现出色。因此，如何在GNN中实现高效的“机器遗忘”成为了一个紧迫的问题。
二、研究动机
作者发现，直接将现有的 SISA 框架（主要针对图像和文本设计）应用到图数据上存在严重的问题。
1. 核心冲突：数据独立性 vs. 图结构依赖性
SISA的假设：图像或文本数据通常被视为独立同分布（I.I.D.）的。随机划分数据不会破坏数据的内在属性。
图数据的特性：图中的节点不是独立的，它们通过边（Edges）相互连接，共享特征和标签信息。图的结构信息（Structure Information）对 GNN 的性能至关重要。
2. 现有方法的缺陷
如果直接对图数据使用 SISA（即随机划分节点到不同的碎片中）：
破坏结构：会切断大量的边，破坏图的拓扑结构。
性能下降：导致子模型的预测准确率（Utility）大幅下降。
3. 潜在解决方案的挑战（社区发现的不平衡性）
为了保留图结构，一个直观的方法是使用社区发现（Community Detection）算法来划分图（将联系紧密的节点分在同一个碎片）。但是，真实世界的图通常具有幂律分布特性，导致社区大小极其不均匀（有的社区巨大，有的极小）。
不平衡的后果：如果按照社区划分，会导致碎片大小极度不平衡。根据木桶效应，遗忘效率取决于最大的那个碎片的重训时间。如果被删除的节点恰好在最大的碎片中，重训时间依然很长，导致遗忘效率低下。
总结动机：
我们需要一种专门针对 GNN 的遗忘框架，它既能像社区发现那样保留图结构（保证模型准确性），又能像随机划分那样保证碎片大小均衡（保证遗忘效率）。
三、核心方法
作者提出的GraphEraser框架主要包含三个阶段：均衡图划分、分片模型训练、基于学习的聚合。
阶段 1: 均衡图划分 (Balanced Graph Partition) ——这是论文最核心的创新点
作者提出了一个通用原则：将节点分配问题转化为排序与容量限制问题。设定每个碎片的容量上限 δ，并定义每个节点对于特定碎片的“偏好（Preference）”，优先满足高偏好的分配。
为了实现这一原则，作者提出了两种具体的算法：
基础：基于标签传播算法（Label Propagation Algorithm, LPA）。
改进逻辑：
初始化：随机将节点分配给 k个碎片。
偏好计算：计算每个节点 u 的邻居中有多少属于目标碎片 Cdst。邻居数越多，说明该节点越应该属于这个碎片（偏好越高）。
排序与分配：将所有 (节点, 目标碎片) 对按照邻居数量从高到低排序。
容量限制：按照排序顺序重新分配节点。关键点：如果目标碎片的当前节点数已经达到了上限 δ，则不允许该节点加入，必须寻找其他碎片或留在原处。
迭代：重复上述过程直到收敛或达到最大次数。
适用性：适用于高度依赖图拓扑结构的模型（如 GCN）。
基础：基于 K-Means 聚类算法。
改进逻辑：
预处理：先用一个预训练的 GNN 提取所有节点的 Embedding（这样 Embedding 既包含特征信息也包含结构信息）。
初始化：随机选择 k 个质心。
偏好计算：计算节点 Embedding 到各质心的欧几里得距离。距离越近，偏好越高。
排序与分配：将 (节点, 质心) 对按距离从小到大排序。
容量限制：同样强制执行容量上限 δ。如果一个簇满了，距离再近的节点也进不去。
更新质心：根据新分配的节点更新质心位置。
适用性：适用于对节点特征敏感的模型（如 GAT, GraphSAGE, GIN）。
阶段 2: 分片模型训练 (Shard Model Training)
在图被划分为 k个大小均衡的子图（碎片）后，作者在每个碎片上独立训练一个 GNN 子模型。
遗忘操作：当收到针对节点u的遗忘请求时，GraphEraser 只需要定位到 u 所在的那个碎片，从该碎片中删除 u，然后重新训练该碎片的子模型。其他 k-1 个子模型保持不变。
效率：由于碎片大小被强制均衡，任何一个碎片的重训时间都是可控且较短的。
阶段 3: 基于学习的聚合 (Learning-based Aggregation, LBAggr)
在推理阶段（预测未知节点的标签时），所有子模型都会给出一个预测结果。如何汇总这些结果？
现有问题：传统的 SISA 使用“多数投票”（Majority Voting）。但这假设所有子模型同等重要。实际上，某些子模型可能因为包含了与目标节点更相关的结构信息，预测更准确。
LBAggr 方案：
作者提出为每个子模型 i学习一个重要性权重
αi。优化目标：最小化加权聚合后的预测误差。公式如下：
minαEw∈G0[L(∑i=0mαi⋅Fi(Xw,Nw),y)]实现细节：从训练图中采样一小部分节点（例如 10%），用它们的真实标签来训练这个权重向量 a。
最终预测：最终输出是各子模型输出后验概率的加权和。
