Abstract
Graphs with abundant attributes are essential in modeling interconnected entities and improving predictions in various real-world applications. Traditional Graph Neural Networks (GNNs) typically require re-training for each specific task and dataset. We propose MuseGraph, a framework that integrates GNNs and Large Language Models (LLMs) for effective and generic graph mining. MuseGraph employs adaptive input generation for compact graph descriptions, diverse instruction generation via Chain-of-Thought (CoT) distillation from GPT-4, and graph-aware instruction tuning with dynamic allocation. Experimental results show significant improvements across various tasks, demonstrating MuseGraph's potential as a foundation model for graphs.
Introduction
Traditional Graph Neural Networks (GNNs) are often "one-trick ponies," trained for a specific task on a specific dataset and requiring significant re-training to adapt to new scenarios. While Large Language Models (LLMs) offer a potential path toward more "generic" graph mining due to their vast pre-trained knowledge, they face three major hurdles: the Token Wall (the complexity of describing graphs in text), the Reasoning Gap (difficulty in understanding topology through text), and Catastrophic Forgetting during multi-task fine-tuning.
Methodology
MuseGraph addresses these challenges through three core components designed to bridge the gap between structural graph data and linguistic reasoning:
1. Compact Graph Descriptions (Node Energy)
To fit complex graph structures into limited token windows, we introduce a node energy metric, $H(v)$. This metric balances a node's semantic richness (attribute token count) with its structural importance (degree). By prioritizing the most informative neighbors and paths (random walks), MuseGraph ensures that the most relevant context is preserved within the LLM's prompt limits, effectively maximizing the utility of every token.
2. Diverse Instruction Generation via CoT Distillation
Rather than simple label-based tuning, we distill reasoning capabilities from high-capacity models like GPT-4. We generate "Chain-of-Thought" (CoT) instruction packages that provide step-by-step reasoning for various graph tasks. These packages are used to fine-tune smaller, open-source models (e.g., LLaMA-3), effectively transferring high-level reasoning skills to more efficient architectures.
3. Graph-aware Instruction Tuning
We employ a dynamic allocation strategy that assesses the complexity of different tasks and datasets, providing more training instructions to more challenging scenarios. The model is fine-tuned using Low-Rank Adaptation (LoRA), which is parameter-efficient and helps maintain the LLM's original generative capabilities while learning specialized graph-specific patterns.
Experimental Evaluation
We evaluated MuseGraph across five tasks and ten datasets, including heterogeneous node classification (IMDB, Freebase), link prediction (Yelp, MIMIC-III), and graph-to-text generation (AGENDA, WebNLG).
Key Results
- Superior Accuracy: MuseGraph achieved an average ranking of 2.17 across node classification and link prediction, consistently outperforming both traditional GNNs (GraphSAGE, GAT) and other LLM-based baselines.
- Reasoning Prowess: On the DyVal benchmark for dynamic reasoning, MuseGraph significantly outperformed other open-source LLMs and remained competitive with GPT-4, despite having a fraction of the parameters.
- Zero-Shot Generalization: The model demonstrated a remarkable ability to handle unseen graph structures and tasks it wasn't explicitly trained on, a capability lacking in traditional GNNs.
- Efficiency: On the IMDB dataset, Macro-F1 scores improved by up to 13.34% simply by optimizing how neighborhood information was integrated into the prompt.
Conclusion
MuseGraph demonstrates that specialized instruction tuning is more critical than raw model size for graph reasoning. A fine-tuned 8B parameter model can match or even outperform the 200B+ parameter GPT-4 on specific graph tasks. While currently most effective on graphs with rich textual attributes, future work will explore its application to structural-only graphs (e.g., molecular data) and the integration of expert human feedback to further refine reasoning in specialized domains.
Summary updated