CoEvoT: Co-Evolving Chain-of-Thought Prompting for Graph-LLM Reasoning

• URL: http://arxiv.org/abs/2607.14114v1
• Date: Fri, 08 May 2026 08:31:18 GMT
• Title: CoEvoT: Co-Evolving Chain-of-Thought Prompting for Graph-LLM Reasoning
• Abstract summary: 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.
• Score: 28.466514163307295
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph learning under distribution shift presents a persistent challenge, where models adapt to new graphs with limited or even no supervision. Recent graph--LLM approaches move toward label-efficient prediction by linearizing graphs into prompts and using large language models (LLMs) as predictors, and can adopt Chain-of-Thought (CoT) prompting to exploit LLM's multi-step reasoning capability. However, existing CoT-based graph--LLM methods generate intermediate thoughts while conditioning on fixed graph tokens, limiting step-wise refinement of structural cues. In this paper, we propose CoEvoT, a simple yet effective co-evolving CoT prompting framework for graph--LLM reasoning. CoEvoT couples text-to-graph token rewriting and graph-to-text reasoning guidance in a closed loop: each intermediate textual thought is used to update the graph token evidence state via a lightweight condition network, and the updated tokens are fed back into the next-step instruction to guide subsequent LLM reasoning. This enables step-wise, state-aware evidence refinement, rather than reasoning over a fixed graph snapshot. Extensive experiments on eight datasets demonstrate that CoEvoT consistently outperforms state-of-the-art baselines.

Related papers

• Rethinking Message Passing as Retrieval for Text-Attributed Graph Learning [63.602658976990874]
  Graph neural networks (GNNs) are typically conceptualized as message-passing neural networks.<n>We present a retrieval-augmented view of GNNs: each layer makes predictions by applying anvariant to a node representation together with a permutation-in summary of retrieved graph context.<n>Motivated by this perspective, we propose RTA, a simple aggregation-based framework that replaces structural message passing with label-aware retrieval and propagation.
  arXiv  Detail & Related papers  (2026-08-27T07:25:44Z)
• Revisiting Graph-Tokenizing Large Language Models: A Systematic Evaluation of Graph Token Understanding [27.40991434448743]
  Graph-Tokenizing LLMs (GTokenLLMs) compress complex graph data into graph tokens and treat them as prefixes tokens for querying LLMs.<n>We propose an evaluation pipeline to assess graph-token understanding via instruction transformations at the format and content levels.
  arXiv  Detail & Related papers  (2026-05-05T08:50:28Z)
• Toward Graph-Tokenizing Large Language Models with Reconstructive Graph Instruction Tuning [17.712367049197212]
  Key challenge is to align graph data with language spaces so that large language models (LLMs) can better comprehend graphs.<n>GTokenLLMs encode complex structures and lengthy texts into a graph token sequence, and then align them with text tokens via language instructions tuning.<n>Despite their initial success, our information-theoretic analysis reveals that existing GTokenLLMs rely solely on text supervision from language instructions.
  arXiv  Detail & Related papers  (2026-03-02T02:26:54Z)
• Semi-supervised Instruction Tuning for Large Language Models on Text-Attributed Graphs [62.544129365882014]
  We propose a novel Semi-supervised Instruction Tuning pipeline for Graph Learning, named SIT-Graph.<n> SIT-Graph is model-agnostic and can be seamlessly integrated into any graph instruction tuning method that utilizes LLMs as the predictor.<n>Extensive experiments demonstrate that when incorporated into state-of-the-art graph instruction tuning methods, SIT-Graph significantly enhances their performance on text-attributed graph benchmarks.
  arXiv  Detail & Related papers  (2026-01-19T08:10:53Z)
• Graph-O1 : Monte Carlo Tree Search with Reinforcement Learning for Text-Attributed Graph Reasoning [7.792321858331646]
  Graph-O1 is an agentic GraphRAG framework that enables LLMs to conduct stepwise, interactive reasoning over graphs.<n>Our approach integrates Monte Carlo Tree Search (MCTS) with end-to-end reinforcement learning, allowing the model to explore and retrieve only the most informative subgraph components.
  arXiv  Detail & Related papers  (2025-11-26T21:32:04Z)
• GILT: An LLM-Free, Tuning-Free Graph Foundational Model for In-Context Learning [50.40400074353263]
  Graph Neural Networks (GNNs) are powerful tools for precessing relational data but often struggle to generalize to unseen graphs.<n>We introduce textbfGraph textbfIn-context textbfL textbfTransformer (GILT), a framework built on an LLM-free and tuning-free architecture.
  arXiv  Detail & Related papers  (2025-10-06T08:09:15Z)
• Graph-R1: Incentivizing the Zero-Shot Graph Learning Capability in LLMs via Explicit Reasoning [7.1931434571877375]
  Graph Neural Networks (GNNs) are limited by fixed label spaces, while Large Language Models (LLMs) lack structural inductive biases.<n>Recent advances in Large Reasoning Models (LRMs) provide a zero-shot alternative via explicit, long chain-of-thought reasoning.<n>We propose a GNN-free approach that reformulates graph tasks--node classification, link prediction, and graph classification--as textual reasoning problems solved by LRMs.
  arXiv  Detail & Related papers  (2025-08-24T14:49:02Z)
• Compile Scene Graphs with Reinforcement Learning [69.36723767339001]
  Next-token prediction is the fundamental principle for training large language models (LLMs)<n>We introduce R1-SGG, a multimodal LLM (M-LLM) initially trained via supervised fine-tuning (SFT) on the scene graph dataset.<n>We design a set of graph-centric rewards, including three recall-based variants -- Hard Recall, Hard Recall+Relax, and Soft Recall.
  arXiv  Detail & Related papers  (2025-04-18T10:46:22Z)
• GraphCLIP: Enhancing Transferability in Graph Foundation Models for Text-Attributed Graphs [27.169892145194638]
  GraphCLIP is a framework to learn graph foundation models with strong cross-domain zero/few-shot transferability.<n>We generate and curate large-scale graph-summary pair data with the assistance of LLMs.<n>For few-shot learning, we propose a novel graph prompt tuning technique aligned with our pretraining objective.
  arXiv  Detail & Related papers  (2024-10-14T09:40:52Z)
• Parameter-Efficient Tuning Large Language Models for Graph Representation Learning [62.26278815157628]
  We introduce Graph-aware. Efficient Fine-Tuning - GPEFT, a novel approach for efficient graph representation learning. We use a graph neural network (GNN) to encode structural information from neighboring nodes into a graph prompt. We validate our approach through comprehensive experiments conducted on 8 different text-rich graphs, observing an average improvement of 2% in hit@1 and Mean Reciprocal Rank (MRR) in link prediction evaluations.
  arXiv  Detail & Related papers  (2024-04-28T18:36:59Z)
• SimTeG: A Frustratingly Simple Approach Improves Textual Graph Learning [131.04781590452308]
  We present SimTeG, a frustratingly Simple approach for Textual Graph learning. We first perform supervised parameter-efficient fine-tuning (PEFT) on a pre-trained LM on the downstream task. We then generate node embeddings using the last hidden states of finetuned LM.
  arXiv  Detail & Related papers  (2023-08-03T07:00:04Z)

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.