Subgraph Federated Unlearning

Subgraph federated learning aims to collaboratively train a global model over distributed subgraphs stored in multiple local clients with strict privacy constraints, which is crucial to a wide range of applications such as healthcare, recommendation systems, and financial crime detection. With the increasing emphasis on the "right to be forgotten," the issue of machine unlearning of subgraph federated models has gained significant importance. However, existing federated unlearning approaches largely focused on unstructured data, overlooking the impact of structural dependency and cross-client interferences in graph-based data. To this end, in this paper, we propose ReGEnUnlearn, a subgraph federated unlearning framework for efficient and comprehensive unlearning of multiple target clients. Specifically, we first propose the Reinforced Federated Policy Sampler (RFPS) to learn optimal sampling strategies that minimize the interference among cross-client subgraphs. By interacting with the federated graph sampling environment, the agent learns to selectively forget an optimal subgraph of target clients, thus preserving the global model utility. Moreover, we propose the Parameter-free Graph Prompt Knowledge Distillation (PGPKD) module, which retains the unique graph knowledge contributed by the target clients, thereby facilitating comprehensive unlearning via a tailored gradient ascent objective. Extensive experiments in various federated settings demonstrate ReGEnUnlearn's superiority over existing federated unlearning methods, offering a speedup of 3.6× to 9× compared to traditional retraining while maintaining model utility within a range of 100%-102%.