Abstract
The "pre-train, prompt" paradigm has successfully evolved in representation learning. While current prompt-tuning methods often introduce learnable prompts, they predominantly treat prompts as isolated, independent components across different network layers. This overlooks the complex and synergistic higher-order interactions that exist between prompts at various hierarchical depths, consequently limiting the expressive power and semantic richness of the prompted model. To address this fundamental gap, we propose a novel framework, MSGCOT (Multi-Scale Graph Chain-of-Thought), that explicitly models the Higher-order Interactions of Multi-layer Prompt. Our approach conceptualizes prompts from different layers not as separate entities, but as a cohesive system where their inter-relationships are critical. We design an innovative interaction module that captures these sophisticated, non-linear correlations among multi-layer prompts, effectively modeling their cooperative effects. Extensive experiments on eight benchmark datasets demonstrate that our method consistently surpasses state-of-the-art prompt-tuning baselines, particularly in few-shot scenarios.
Introduction
In the graph domain, the "pre-train, prompt" paradigm involves adapting a model pre-trained on massive unlabeled data to specific downstream tasks using small, learnable vectors called "prompts." However, existing methods often suffer from granularity blindness. They typically focus on a single scale—either the individual node level or a specific subgraph level. Real-world graphs are inherently multi-scale, containing hierarchical structures from individual nodes to communities. By ignoring these hierarchies, traditional prompts lack semantic diversity and fail to capture the full topological context of the graph.
Methodology: MSGCOT
To overcome these limitations, we introduce MSGCOT, which mimics human "Chain-of-Thought" (CoT) reasoning by processing information from the general to the specific. The framework consists of several key components:
- Node-Level Prompting: It begins by generating node-specific prompts using a conditional hypernetwork to adapt pre-trained embeddings to the downstream task.
- Multi-scale Thought Construction: To capture the hierarchy, we designed a lightweight, low-rank coarsening network. This network progressively merges nodes into coarser "super-nodes," creating a pool of hierarchical basis vectors, or "thoughts." Using low-rank decomposition ensures parameter efficiency.
- Coarse-to-Fine Backtracking: Instead of simple aggregation, MSGCOT uses a "backtracking" mechanism. It starts with the coarsest global information and iteratively refines the prompt by adding finer details at each reasoning step. This coarse-to-fine refinement is key to stable prompt learning.
- Consistency Constraint: To maintain the unique identity of individual nodes while adding coarse-grained information, we employ an external cosine reconstruction loss for feature consistency.
Experimental Results
We evaluated MSGCOT on eight diverse benchmark datasets across node classification (e.g., Cora, Citeseer) and graph classification (e.g., MUTAG, PROTEINS) tasks.
- State-of-the-Art Performance: MSGCOT consistently outperformed all baselines. On the COX2 dataset, it achieved a significant 18.62% improvement over the previous best method, DAGPrompt.
- Few-Shot Excellence: In one-shot classification scenarios, MSGCOT showed superior robustness, validating that capturing the intricate interplay between multi-layer prompts is essential for generalizable representation learning.
- Efficiency: The low-rank design keeps overhead manageable. On graph classification tasks, MSGCOT reduced training time per epoch by approximately 34% compared to GCOT, the previous multi-step leader.
Conclusion and Future Work
MSGCOT demonstrates that modeling higher-order interactions through a multi-scale chain-of-thought significantly enhances graph prompt tuning. While effective, the model's performance is sensitive to the coarsening rate, suggesting a need for automated hyperparameter tuning. Future research will explore extending this approach to dynamic graphs and integrating structural graph thoughts with natural language explanations in Graph-LLM frameworks.
Summary updated