MuseGraph: Graph-oriented Instruction Tuning of Large Language Models for Generic Graph Mining

Yanchao Tan, Hang Lv, Xinyi Huang, Jiawei Zhang, Shiping Wang, Carl YangarXiv 2024 · arXiv · OpenReview

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.

MuseGraph framework overview: bridging diverse tasks and datasets through a unified LLM-based approach.

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

Abstract

Graphs with abundant attributes are essential in modeling interconnected entities and improving predictions in various real-world applications. Traditional Graph Neural Networks (GNNs), which are commonly used for modeling attributed graphs, need to be re-trained every time when applied to different graph tasks and datasets. Although the emergence of Large Language Models (LLMs) has introduced a new paradigm in natural language processing, the generative potential of LLMs in graph mining remains largely under-explored. To this end, we propose a novel framework MuseGraph, which seamlessly integrates the strengths of GNNs and LLMs and facilitates a more effective and generic approach for graph mining across different tasks and datasets. Specifically, we first introduce a compact graph description via the proposed adaptive input generation to encapsulate key information from the graph under the constraints of language token limitations. Then, we propose a diverse instruction generation mechanism, which distills the reasoning capabilities from LLMs (e.g., GPT-4) to create task-specific Chain-of-Thought-based instruction packages for different graph tasks. Finally, we propose a graph-aware instruction tuning with a dynamic instruction package allocation strategy across tasks and datasets, ensuring the effectiveness and generalization of the training process. Our experimental results demonstrate significant improvements in different graph tasks, showcasing the potential of our MuseGraph in enhancing the accuracy of graph-oriented downstream tasks while keeping the generation powers of LLMs.
BibTeX
@misc{tan2024musegraph,
  author = {Yanchao Tan and Hang Lv and Xinyi Huang and Jiawei Zhang and Shiping Wang and Carl Yang},
  title = {{MuseGraph: Graph-oriented Instruction Tuning of Large Language Models for Generic Graph Mining}},
  year = {2024},
  eprint = {2403.04780},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2403.04780},
}
Figure