Extracting fuzzy clusters from massive attributed graphs using Markov lumpability optimization

Attributed graph clustering plays a vital role in uncovering hidden network structures, but it presents significant challenges. In recent years, various models have been proposed to identify meaningful clusters by integrating both structural and attribute-based information. However, these models often emphasize node proximities without adequately balancing the efficiency of clustering based on both structural and attribute data. Furthermore, they tend to neglect the critical fuzzy information inherent in attributed graph clusters. To address these issues, we introduce a new framework, Markov lumpability optimization, for efficient clustering of large-scale attributed graphs. Specifically, we define a lumped Markov chain on an attribute-augmented graph and introduce a new metric, Markov lumpability, to quantify the differences between the original and lumped Markov transition probability matrices. To minimize this measure, we propose a conjugate gradient projection-based approach that ensures the partitioning closely aligns with the intrinsic structure of fuzzy clusters through conditional optimization. Extensive experiments on both synthetic and real-world datasets demonstrate the superior performance of the proposed framework compared to existing clustering algorithms. This framework has many potential applications, including dynamic community analysis of social networks, user profiling in recommendation systems, functional module identification in biological molecular networks, and financial risk control, offering a new paradigm for mining complex patterns in high-dimensional attributed graph data.