Generalized cluster formation game for explainable attributed graph clustering

The efficient clustering of attributed graphs is a critical and challenging problem that has attracted significant attention across various research fields. However, a few challenges still exist, particularly lack of explanations of the formation and evolution for attribute cluster configuration. Moreover, it is still difficult to achieve a balance between clustering quality and computational efficiency for massive attributed graphs. To solve these problems, in this paper, we explain the underlying mechanisms of the formation and evolution of potential clusters naturally by a Generalized Cluster Formation Game played by selfish node-agents. To effectively integrate both topological and attributive information, we propose both structural closeness and attribute closeness constraints on node-agents’ strategy selection. To be specific, each node-agent in the Generalized Cluster Formation Game can be selfish to improve her own utility under the pre-defined constraint mechanism, but can also maintain the status quo with a certain probability even she has a better choice. We further prove that if all node-agents synchronously repeat the above process, the game will finally converge to a weakly Pareto-Nash equilibrium almost surely. We propose a distributed learning algorithm based on Generalized Cluster Formation Game which controls the overlap rate for the cluster configuration by a single parameter. The algorithm is very fast and its computational time is nearly linear with the scale of sparse network. Finally, we conduct a set of simulation experiments on real-life and synthetic networks. Extensive experimental results demonstrate both the effectiveness and the scalability of the proposed approach through comparisons with the state-of-the-art community detection and attributed graph clustering methods.