Generalized cluster formation game for explainable attributed graph clustering

Hui-Jia Li, Jiajun Gao, Qiqi Wang, Chenyang Qiu and Guijun Li

Chaos, Solitons & Fractals, 2025, vol. 200, issue P1

Abstract: 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.

Keywords: Attributed graph clustering; Generalized cluster formation game; Multi-agent system; Distributed learning; Explainability (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0960077925009609
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:chsofr:v:200:y:2025:i:p1:s0960077925009609

DOI: 10.1016/j.chaos.2025.116947

Access Statistics for this article

Chaos, Solitons & Fractals is currently edited by Stefano Boccaletti and Stelios Bekiros

More articles in Chaos, Solitons & Fractals from Elsevier
Bibliographic data for series maintained by Thayer, Thomas R. ().