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

• URL: http://arxiv.org/abs/2605.24867v1
• Date: Sun, 24 May 2026 04:58:44 GMT
• Title: Clustering as Reasoning: A $k$-Means Interpretation of Chain-of-Thought Graph Learning
• Abstract summary: Chain-of-Thought (CoT) prompting has shown promise in enhancing the reasoning capabilities of large language models (LLMs) on text-attributed graphs (TAGs)<n>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.
• Score: 22.799865652941136
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Does Syntax Matter? A Graph-Augmented Variational Topic Model for Computational Social Sciences [51.56484100374058]
  This paper introduces the Structural Contextual Probabilistic Topic Model ( SCPTM), an architecture that incorporates syntactic dependency relations into topic inference.<n>We evaluate seven topic modeling techniques across four corpora differing in register and discourse structure.<n>Results show that SCPTM's neural architecture yields substantial gains in document-topic alignment over generative baselines.
  arXiv  Detail & Related papers  (2026-09-07T17:39:06Z)
• TopoFormer: Topology Meets Attention for Graph Learning [8.679678575739304]
  We introduce Topoformer, a framework for graph representation learning that encodes topological structure into attention-friendly sequences.<n>At the core of our method is Topo-Scan, a novel module that decomposes a graph into a short, ordered sequence of topological tokens.
  arXiv  Detail & Related papers  (2026-07-30T14:18:17Z)
• CoEvoT: Co-Evolving Chain-of-Thought Prompting for Graph-LLM Reasoning [28.466514163307295]
  Graph learning under distribution shift presents a persistent challenge.<n>Recent graph--LLM approaches move toward label-efficient prediction by linearizing graphs into prompts.<n>We propose CoEvoT, a simple yet effective co-evolving CoT prompting framework for graph--LLM reasoning.
  arXiv  Detail & Related papers  (2026-05-08T08:31:18Z)
• TDA-RC: Task-Driven Alignment for Knowledge-Based Reasoning Chains in Large Language Models [54.20787536978013]
  Chain-of-Thought (CoT) paradigm dominates practical applications for its single-round efficiency, yet its reasoning chains often exhibit logical gaps.<n>This paper proposes a topology-based method for optimizing reasoning chains.<n>We show that our approach offers a superior balance between reasoning accuracy and efficiency, showcasing a practical solution to single-round generation with multi-round intelligence''
  arXiv  Detail & Related papers  (2026-03-13T13:01:01Z)
• Benchmarking graph construction by large language models for coherence-driven inference [3.522062800701924]
  We benchmark the ability of large language models to reconstruct coherence graphs.<n>Coherence-driven inference on consistency evaluations by LLMs may advance machine cognition capabilities.
  arXiv  Detail & Related papers  (2025-02-19T18:53:16Z)
• Adaptive Graph of Thoughts: Test-Time Adaptive Reasoning Unifying Chain, Tree, and Graph Structures [0.0]
  We introduce Adaptive Graph of Thoughts (AGoT), a dynamic, graph-based inference framework.<n>AGoT enhances Large Language Models (LLMs) reasoning solely at test time.<n>We validate our approach on diverse benchmarks spanning multi-hop retrieval, scientific reasoning, and mathematical problem-solving.
  arXiv  Detail & Related papers  (2025-02-07T16:54:19Z)
• Graph Structure Refinement with Energy-based Contrastive Learning [56.957793274727514]
  We introduce an unsupervised method based on a joint of generative training and discriminative training to learn graph structure and representation.<n>We propose an Energy-based Contrastive Learning (ECL) guided Graph Structure Refinement (GSR) framework, denoted as ECL-GSR.<n>ECL-GSR achieves faster training with fewer samples and memories against the leading baseline, highlighting its simplicity and efficiency in downstream tasks.
  arXiv  Detail & Related papers  (2024-12-20T04:05:09Z)
• On the Diagram of Thought [20.805936414171892]
  Large Language Models (LLMs) excel at many tasks but often falter on complex problems that require structured, multi-step reasoning.<n>We introduce the Diagram of Thought (DoT), a new framework that enables a single LLM to build and navigate a mental map of its reasoning.
  arXiv  Detail & Related papers  (2024-09-16T07:01:41Z)
• Homomorphism Counts for Graph Neural Networks: All About That Basis [8.25219440625445]
  We argue for a more fine-grained approach, which incorporates the homomorphism counts of all structures in the basis'' of the target pattern. This yields strictly more expressive architectures without incurring any additional overhead in terms of computational complexity.
  arXiv  Detail & Related papers  (2024-02-13T16:57:06Z)
• Joint Graph Learning and Matching for Semantic Feature Correspondence [69.71998282148762]
  We propose a joint emphgraph learning and matching network, named GLAM, to explore reliable graph structures for boosting graph matching. The proposed method is evaluated on three popular visual matching benchmarks (Pascal VOC, Willow Object and SPair-71k) It outperforms previous state-of-the-art graph matching methods by significant margins on all benchmarks.
  arXiv  Detail & Related papers  (2021-09-01T08:24:02Z)
• Learning the Implicit Semantic Representation on Graph-Structured Data [57.670106959061634]
  Existing representation learning methods in graph convolutional networks are mainly designed by describing the neighborhood of each node as a perceptual whole. We propose a Semantic Graph Convolutional Networks (SGCN) that explores the implicit semantics by learning latent semantic-paths in graphs.
  arXiv  Detail & Related papers  (2021-01-16T16:18:43Z)
• Structured Graph Learning for Clustering and Semi-supervised Classification [74.35376212789132]
  We propose a graph learning framework to preserve both the local and global structure of data. Our method uses the self-expressiveness of samples to capture the global structure and adaptive neighbor approach to respect the local structure. Our model is equivalent to a combination of kernel k-means and k-means methods under certain condition.
  arXiv  Detail & Related papers  (2020-08-31T08:41:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.