Frequency-Aware Unlearning for Federated Graph Clustering

Federated graph unlearning (FGU) is a distributed learning paradigm that enables clients, motivated by privacy concerns or other considerations, to request the removal of specified graph data and the elimination of their influence from federated graph models. Existing methods have achieved significant progress, but generally assume graph labels are available, which is often difficult to satisfy in real-world scenarios. Under this limitation, most existing methods struggle to accurately characterize the impact of the data to be forgotten on cluster structures and clustering models, often resulting in incomplete unlearning and residual knowledge—a problem that remains largely underexplored. To address this issue, we propose Frequency-Aware Unlearning for Federated Graph Clustering (FedFAU), which exploits frequency changes before and after unlearning to characterize the impact of forgotten data on local clustering structures and enable selective model updates. Specifically, we first partition each client graph into multiple blocks and perform local clustering, based on which block-level frequency information is constructed. Upon an unlearning request, we use the resulting frequency shifts to assess cluster reliability and selectively update affected global clusters, rather than retraining the entire global model. Extensive experiments on five benchmark datasets demonstrate the effectiveness and superiority of our method over competing approaches.