Beyond Single-Granularity Prompts: A Multi-Scale Chain-of-Thought Prompt Learning for Graph

Ziyu Zheng, Yaming Yang, Ziyu Guan, Wei Zhao, Xinyan Huang, Weigang Lu

TL;DR

MSGCOT (Multi-Scale Graph Chain-of-Thought) introduces a novel prompting paradigm for Graph Neural Networks (GNNs) that breaks free from single-granularity constraints. By using a lightweight, low-rank coarsening network to build a hierarchical "thought pool," it progressively guides prompt generation from coarse to fine structural scales. This approach yields massive performance gains in few-shot graph and node classification while drastically reducing trainable parameters.

What Problem Does This Paper Address?

The "pre-train, prompt" paradigm has successfully migrated from NLP to the graph domain. Instead of fine-tuning an entire pre-trained GNN for downstream tasks—which is computationally expensive and prone to overfitting in low-data scenarios—graph prompt tuning modifies input or output features using lightweight learnable vectors.

However, existing graph prompting methods suffer from a major blind spot: singularity of granularity. They generate prompts strictly at one level (e.g., only node-level or only subgraph-level). Real-world graphs are inherently multi-scale; nodes form local communities, which embed into larger functional subgraphs, which finally form the global topology. By ignoring this hierarchical structure, current SOTA methods limit the semantic diversity of their prompts and struggle to capture the full context of the graph.

Figure 1: The comparison of graph prompt tuning methods in the existing studies.

Methods

To capture multi-scale graph features without blowing up the parameter budget, the authors propose MSGCOT, which consists of three main components:

  1. Multi-scale Thought Construction: Instead of using manually designed text templates (like NLP Chain-of-Thought), MSGCOT uses graph coarsening to progressively merge nodes and edges into smaller, high-level subgraphs. To keep this process parameter-efficient, they design a lightweight coarsening network using low-rank matrix decomposition, creating a hierarchical "thought pool" of structural granularities.
  2. Coarse-to-Fine Backtracking Prompts: Mimicking human cognitive refinement, MSGCOT generates prompts step-by-step. It starts with the most coarse-grained global topology and uses an attention mechanism to progressively inject finer, localized details into the node representations at each reasoning step.
  3. Cosine Reconstruction Loss: Introducing global, coarse-grained information can sometimes wash out a node's unique local identity. To prevent this, the authors introduce an external reconstruction loss that ensures the prompted embeddings maintain consistency with their original pre-trained features.
Figure 2: The framework of the proposed MSGCOT.

Datasets

The authors evaluated MSGCOT across eight standard benchmark datasets spanning multiple domains:

  • Node Classification: Cora, Citeseer, Pubmed (citation networks), and Photo (e-commerce co-purchase network).
  • Graph Classification: MUTAG, BZR, COX2 (molecular/biochemical graphs), and PROTEINS (protein structures).
  • Extended Evaluations (Appendix): Heterophilous graphs (Texas, Cornell, Wisconsin, Chameleon), social networks (IMDB-BINARY, IMDB-MULTI), and large-scale graphs (ogbn-arxiv).

Key Insights and Ideas

  • Hierarchies as "Structured Thoughts": The core conceptual leap is treating graph coarsening levels as the structural equivalent of textual reasoning steps in NLP. Global topology acts as the broad context, while local subgraphs act as specific details.
  • Low-Rank Efficiency: Prompt tuning is meant to be a low-resource alternative to fine-tuning. Standard multi-layer perceptrons (MLPs) for graph coarsening introduce too many parameters. Utilizing low-rank decomposition ($W_{down}$ and $W_{up}$) slashes the parameter footprint to a fraction of full-rank alternatives while maintaining strong generalization.
  • The Power of Backtracking: The authors found that a serial, coarse-to-fine prompt fusion strategy significantly outperforms parallel aggregation or fine-to-coarse strategies. Starting with the "big picture" and refining downward prevents feature interference.

Key Results

MSGCOT consistently outperformed state-of-the-art single-granularity methods (such as GCOT and GraphPrompt), particularly in data-scarce, few-shot scenarios:

  • Substantial Accuracy Gains: On graph classification, MSGCOT achieved a 5% to 20% absolute accuracy improvement over the strongest baselines. Notably, on the COX2 dataset, it outperformed the second-best method by 18.62%.
  • Extreme Parameter Efficiency: Thanks to its low-rank design, MSGCOT achieved a 47.1% to 68.3% reduction in trainable parameters for node classification, and up to an 85.7% reduction for graph classification compared to the previous multi-step SOTA method (GCOT).
  • Faster Runtimes: For graph classification, MSGCOT cut per-epoch training time by an average of 34.8% compared to GCOT, demonstrating that multi-scale reasoning does not have to come with a heavy computational tax.

Limitations and Future Work

While MSGCOT proves highly effective and agnostic to the underlying GNN encoder architecture, it exhibits sensitivity to structural hyperparameters. Specifically, choosing the optimal number of coarsening layers and coarsening rates is critical; too many layers can lead to over-smoothing in node-level tasks, where local details matter most.

The authors suggest that future work could focus on automating hyperparameter selection or extending this multi-scale Chain-of-Thought approach to more dynamic graph settings and link prediction tasks.

Summary updated

Abstract

The ``pre-train, prompt" paradigm, designed to bridge the gap between pre-training tasks and downstream objectives, has been extended from the NLP domain to the graph domain and has achieved remarkable progress. Current mainstream graph prompt-tuning methods modify input or output features using learnable prompt vectors. However, existing approaches are confined to single-granularity (e.g., node-level or subgraph-level) during prompt generation, overlooking the inherently multi-scale structural information in graph data, which limits the diversity of prompt semantics. To address this issue, we pioneer the integration of multi-scale information into graph prompt and propose a Multi-Scale Graph Chain-of-Thought (MSGCOT) prompting framework. Specifically, we design a lightweight, low-rank coarsening network to efficiently capture multi-scale structural features as hierarchical basis vectors for prompt generation. Subsequently, mimicking human cognition from coarse-to-fine granularity, we dynamically integrate multi-scale information at each reasoning step, forming a progressive coarse-to-fine prompt chain. Extensive experiments on eight benchmark datasets demonstrate that MSGCOT outperforms the state-of-the-art single-granularity graph prompt-tuning method, particularly in few-shot scenarios, showcasing superior performance. The code is available at: https://github.com/zhengziyu77/MSGCOT.
BibTeX
@misc{zheng2025beyond,
  author = {Ziyu Zheng and Yaming Yang and Ziyu Guan and Wei Zhao and Xinyan Huang and Weigang Lu},
  title = {{Beyond Single-Granularity Prompts: A Multi-Scale Chain-of-Thought Prompt Learning for Graph}},
  year = {2025},
  eprint = {2510.09394},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2510.09394},
}
Figure