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.
Introduction
In the "pre-train, prompt" paradigm, researchers bridge the gap between general pre-training tasks (like link prediction) and specific downstream goals (like node classification) using learnable prompt vectors. However, most current graph prompting methods are "single-granularity"—they focus exclusively on one level, such as individual nodes or specific subgraphs.
This is a problem because graphs are inherently multi-scale. A node's identity is defined not just by its own features, but by its local neighborhood, its community, and its role in the global topology. Ignoring these multiple scales limits the semantic diversity of the prompts. Furthermore, while Chain-of-Thought (CoT) prompting has revolutionized NLP by breaking down reasoning into steps, applying it to non-textual graph data has remained a challenge.
Methodology: MSGCOT
The proposed MSGCOT (Multi-Scale Graph Chain-of-Thought) framework consists of three main components:
- Multi-scale Thought Construction: Instead of manual text templates, the model uses "hierarchical coarsened representations" as structured thoughts. A lightweight low-rank coarsening network progressively merges nodes to create a hierarchy of graph representations, from global topology down to local details.
- Coarse-to-Fine Backtracking Prompts: Mimicking human cognition, the model generates prompts in a progressive chain. It starts with coarse-grained information (the "big picture") and iteratively refines the prompt by integrating finer-grained details at each reasoning step. This "backtracking" ensures the final prompt captures both broad structural outlines and precise local features.
- Prompt Injection & Reconstruction: These multi-scale prompts are injected into the pre-trained embeddings. To ensure that the "unique" identity of a node isn't lost during this hierarchical merging, an external cosine reconstruction loss is used to maintain consistency with the original prompted embeddings.
Key Insights
- Graphs as "Thoughts": The most creative leap here is treating coarsened graph structures as the equivalent of "textual examples" in NLP CoT. This allows the model to "reason" about the graph's structure without needing natural language.
- Low-Rank Efficiency: Coarsening a graph can be computationally expensive. By using a low-rank matrix decomposition for the assignment matrices, the authors made the coarsening network extremely parameter-efficient, reducing trainable parameters by up to 68% compared to previous multi-step methods like GCOT.
- The Power of Backtracking: The "coarse-to-fine" approach is vital. Ablation studies showed that reversing this (fine-to-coarse) or using only the final prompt significantly degraded performance, especially in graph classification.
Experiments and Results
The framework was evaluated on eight benchmark datasets across two primary tasks: Node Classification (Cora, Citeseer, Pubmed, Photo) and Graph Classification (MUTAG, COX2, BZR, PROTEINS). The models were pre-trained using a standard link prediction task and evaluated primarily in one-shot and few-shot scenarios.
Performance Analysis
MSGCOT consistently outperformed state-of-the-art (SOTA) methods, particularly when labels were scarce:
- One-Shot Superiority: On the Cora dataset, MSGCOT achieved a 3.68% improvement over the previous best method. On the COX2 dataset, it outperformed the second-best method by 18.62%.
- Few-Shot Robustness: MSGCOT maintains a clear lead over GCOT and GraphPrompt as the number of training "shots" increases from 1 to 10, as shown in the accuracy trends for Cora and MUTAG.
- Parameter Efficiency: Despite the added complexity of multi-scale reasoning, the low-rank design allows MSGCOT to use significantly fewer parameters than GCOT (e.g., 1.20K vs 8.19K on MUTAG).
Conclusion
MSGCOT introduces a multi-scale "Chain-of-Thought" (CoT) framework for graph prompt learning, moving beyond the limitations of single-granularity prompts. By using a lightweight, low-rank coarsening network to generate hierarchical "thoughts" and a coarse-to-fine backtracking mechanism, it significantly boosts performance in few-shot graph and node classification tasks. While MSGCOT is highly effective, future work could investigate pre-training tasks specifically designed to complement multi-scale prompting and adapt the framework for dynamic graph structures.
Summary updated