MARK: Multi-agent Collaboration with Ranking Guidance for Text-attributed Graph Clustering

This paper studies the problem of textattributed graph clustering, which aims to cluster each node into different groups using both textual attributes and structural information.Although graph neural networks (GNNs) have been proposed to solve this problem, their performance is usually limited when uncertain nodes are near the cluster boundaries due to label scarcity.In this paper, we introduce a new perspective of leveraging large language models (LLMs) to enhance text-attributed graph clustering and develop a novel approach named Multi-agent Collaboration with Ranking Guidance (MARK).The core of our MARK is to generate reliable guidance using the collaboration of three LLM-based agents as rankingbased supervision signals.In particular, we first conduct the coarse graph clustering, and utilize a concept agent to induce the semantics of each cluster.Then, we infer the robustness under perturbations to identify uncertain nodes and use a generation agent to produce synthetic text that closely aligns with their topology.An inference agent is adopted to provide the ranking semantics for each uncertain node in comparison to its synthetic counterpart.The consistent feedback between uncertain and synthetic texts is identified as reliable guidance for fine-tuning the clustering model within a ranking-based supervision objective.Experimental results on various benchmark datasets validate the effectiveness of the proposed MARK compared with competing baselines.