Relative Entropy-based Regularized Non-negative Matrix Factorization for Attributed Graph Clustering

Attributed graph clustering is a fundamental task in network mining, essential for uncovering valuable insights in various applications. However, the heterogeneity of information from structural and attribute spaces poses significant challenges in achieving consistent and meaningful clustering. To address this, we propose Relative Entropy-based Regularized Non-negative Matrix Factorization (RENMF), a novel approach that integrates structural and attribute information through advanced matrix factorization techniques. RENMF employs Symmetric NMF and Projective NMF to extract community membership distributions from the structural and attribute spaces, respectively. By treating these distributions as homogeneous, RENMF preserves distinct, denoised information from both spaces while considering their heterogeneous complementary information. We introduce Relative Entropy (RE) as a novel regularization term to facilitate interaction between these spaces, aiming to maximize consistency between the discovered latent distributions. In this interaction, we leverage the asymmetric property of RE to emphasize attributes as essential complementary information for structural clustering. The RENMF model is solved using a new iterative multiplicative update rule, with convergence theoretically proven. We evaluate RENMF’s effectiveness through extensive experiments on 10 real-world networks, comparing it to 11 state-of-the-art clustering methods. The results demonstrate RENMF’s superiority in ground truth matching and key quality metrics, outperforming existing methods.