Learning a Class-Balanced Consensus Graph for Federated Long-Tailed Graph Clustering

Federated graph clustering aims to collaboratively learn graph representations across multiple clients without sharing raw graph data and discover latent clusters among unlabeled nodes. Existing efforts typically assume that locally learned prototypes provide reliable clustering signals for global aggregation. However, long-tailed data distributions across clients lead to substantial variation in the number of samples among clusters, with nodes from minority classes often exhibiting high heterophily in local graphs and thus likely to receive biased neighboring information, which may result in underrepresented embeddings and unreliable clustering prototypes. Consequently, the global model may fail to sufficiently preserve representations from minority classes during aggregation, further degrading clustering performance. To address this issue, we propose a novel federated long-tailed graph clustering framework termed FedCBG, where clustering feedback guides class-balanced graph optimization, and the refined topology in turn facilitates better clustering. Specifically, to construct the class-balanced graph, we leverage the uploaded cluster-aware signals to derive reliable global prototypes, which are then used on the server to generate an equal number of nodes per cluster and establish their initial topology. Subsequently, we further develop a graph optimization mechanism that leverages global clustering representations to adaptively strengthen reliable connections and suppress unreliable ones for nodes in minority classes. Extensive empirical results on five benchmarks verify the effectiveness and superiority of FedCBG over existing competitors.