Multiresolution Clustering on Massive Attributed Graphs by Means of Optimal Aggregated Markov Chains

The efficient clustering of attributed graphs is a critical and challenging problem that has attracted much attentions across various research fields. Despite recent advancements, many challenges still exist, particularly in achieving a balance between clustering quality and computational efficiency for massive attributed graphs. To address these problems, we propose a new graph clustering algorithm based on Optimal Aggregated Markov Chains (OAMC), designed to identify an optimal partition in which the aggregated Markov chain closely approximates the behavior of a network-induced random walker. We formalize the concept of lifted aggregated transition probability matrix and utilizes the Kullback-Leibler divergence to determine the optimal partition. Given that the initial and aggregated transition probability matrices reside on different state spaces, OAMC constructs a relaxed alternative space that contains partition information and employs a multiplicative optimization method to minimize the KL divergence. The proposed algorithm effectively uncovers hierarchical cluster structures at multiple resolutions, governed by a single resolution parameter. The aggregated transition probability matrix provides a natural representation of block coupling strengths, facilitating the tracing of relationships between clusters across hierarchical layers. Moreover, the number of clusters can be specified based on the resolution parameter, providing an meaningful interpretable metric of the significance of cluster configuration. We validate the performance of our framework through comprehensive experiments on synthetic and real-world benchmark graphs. The results demonstrate that OAMC outperforms state-of-the-art graph clustering methods in terms of both efficiency and effectiveness.