AG2CD: Soft anchor graph based fast community detection in attributed graphs

Attributed graph community detection aims to identify node clusters that are cohesive in both network structure and node attributes. While deep learning approaches have achieved promising performance, they often suffer from limited interpretability and high computational costs. In contrast, model-driven methods offer better theoretical transparency but face scalability issues on large graphs. To bridge this gap, we propose a model-driven framework named Anchor Graph based Fast Attributed Graph Community Detection (AG2CD), which achieves a favorable trade-off among clustering accuracy, interpretability, and computational efficiency. Specifically, AG2CD first constructs a reduced anchor graph to approximate the original network by selecting a relatively much smaller set of representative anchors. Based on the anchor graph, a unified optimization objective is designed to jointly model structural and attribute information, and an efficient iterative optimization strategy is proposed. Furthermore, two fast anchor generation approaches, including balanced binary tree based hierarchical k-means (BKHK) and soft balanced ternary tree based hierarchical k-means (3KHK), are integrated into the algorithm to illustrate the efficacy of anchor selection on clustering quality. Finally, extensive experiments on six real-world attributed graphs demonstrate that AG2CD achieves competitive or superior clustering performance with significantly reduced computational cost, and the 3KHK-based AG2CD shows enhanced ability in handling ambiguous/overlapping structural patterns, enabled by its soft portioning mechanism facilitating more flexible and nuanced anchor formation.