Clustering as Reasoning: A $k$-Means Interpretation of Chain-of-Thought Graph Learning

Chain-of-Thought (CoT) prompting has shown promise in enhancing the reasoning capabilities of large language models (LLMs) on text-attributed graphs (TAGs). This work reframes CoT-based graph learning through the principle of clustering as reasoning, offering a $k$-means interpretation of how iterative reasoning operates over graph-structured data. We observe that existing graph CoT methods rely on disjoint architectures and fixed graph representations, limiting step-by-step semantic-topological interaction and interpretability. To overcome this limitation, we propose a unified framework named KCoT that integrates CoT reasoning with graph representation learning. Our key theoretical result reveals a formal mathematical correspondence between a Transformer block and the $k$-means algorithm, allowing reasoning to be interpreted as iterative assignment and update steps. Based on this insight, we introduce a Semantic Discriminating Prompt that explicitly formulates these steps as structured CoT reasoning, together with a structure-grounded alignment strategy to fuse topological priors with evolving thought-conditioned representations. Experiments on standard benchmarks demonstrate consistent improvements over state-of-the-art methods, validating clustering as a principled mechanism for CoT-based graph learning.

Current AI models struggle to properly handle interconnected data that contains both text and network structures. Traditional methods usually process text descriptions and network shapes separately in isolated stages. This disconnect limits the model's step-by-step reasoning ability and treats its thinking process as "black box". We introduce a new framework called KCoT to bridge this gap. Mathematically, we discovered that the text-processing blocks in large language models actually operate similarly to how humans naturally group similar items together, a process known as clustering. Leveraging this insight, we designed a smart prompt that rigorously screening out irrelevant connections in the network and summarizing the most important shared features into a clean "knowledge centroid". KCoT consistently outperforms existing methods on graph tasks. More importantly, it opens up the "black box" of graph AI, proving that language-based reasoning can be grounded in a mathematically rigorous clustering mechanism that humans can easily interpret.