Graph Unlearning System with Subgraph De-Isolation Measures

Graph unlearning system offers a promising solution for securely erasing specific data points and their associated influences from Graph Neural Networks (GNNs). However, existing approaches often treat the problem as multiple isolated and disjoint sub-problems by partitioning graph data into isolated subgraphs, which overlooks the native graph structure information between subgraphs. This results in biased representations that hinder the accurate modeling of key connections and relationships within the data, leading to a notable reduction in model utility due to this loss of information. To address these issues, we propose an innovative framework called N on- I solated G raph Eraser (NIGEraser) that decomposes the unlearning task into multiple non-isolated, intersecting sub-problems. Specifically, a novel non-isolated graph partitioning strategy is proposed for NIGEraser that mitigates isolation by replicating key nodes across multiple neighboring subgraphs, along with an attention-based sub-model aggregation technique in that global graph structure information is employed. By this design, a broader natural neighborhood is explored, capturing and effectively utilizing the critical graph structure features lost between subgraphs during partitioning, thereby reducing information loss during task decomposition and aggregation. Additionally, it is demonstrated that graph unlearning methods can overcome the limitations of traditional isolated partitioning strategies, providing an effective theoretical constraint on time consumption. Extensive experiments on four real-world graph-structured datasets show that NIGEraser consistently outperforms existing unlearning methods, offering superior model utility while ensuring efficient and deterministic data removal.