GCoder: Improving Large Language Model for Generalized Graph Problem Solving

• URL: http://arxiv.org/abs/2410.19084v1
• Date: Thu, 24 Oct 2024 18:40:36 GMT
• Title: GCoder: Improving Large Language Model for Generalized Graph Problem Solving
• Authors: Qifan Zhang, Xiaobin Hong, Jianheng Tang, Nuo Chen, Yuhan Li, Wenzhong Li, Jing Tang, Jia Li,
• Abstract summary: Large Language Models (LLMs) have demonstrated strong reasoning abilities, making them suitable for complex tasks such as graph computation. We introduce GCoder, a code-based LLM designed to enhance problem-solving in generalized graph problems. Our method involves constructing an extensive training dataset, GraphWild, featuring diverse graph formats and algorithms.
• Score: 38.9131866084555
• License:
• Abstract: Large Language Models (LLMs) have demonstrated strong reasoning abilities, making them suitable for complex tasks such as graph computation. Traditional reasoning steps paradigm for graph problems is hindered by unverifiable steps, limited long-term reasoning, and poor generalization to graph variations. To overcome these limitations, we introduce GCoder, a code-based LLM designed to enhance problem-solving in generalized graph computation problems. Our method involves constructing an extensive training dataset, GraphWild, featuring diverse graph formats and algorithms. We employ a multi-stage training process, including Supervised Fine-Tuning (SFT) and Reinforcement Learning from Compiler Feedback (RLCF), to refine model capabilities. For unseen tasks, a hybrid retrieval technique is used to augment performance. Experiments demonstrate that GCoder outperforms GPT-4o, with an average accuracy improvement of 16.42% across various graph computational problems. Furthermore, GCoder efficiently manages large-scale graphs with millions of nodes and diverse input formats, overcoming the limitations of previous models focused on the reasoning steps paradigm. This advancement paves the way for more intuitive and effective graph problem-solving using LLMs. Code and data are available at here: https://github.com/Bklight999/WWW25-GCoder/tree/master.

Related papers

• Scalable and Accurate Graph Reasoning with LLM-based Multi-Agents [27.4884498301785]
  We introduce GraphAgent-Reasoner, a fine-tuning-free framework for explicit and precise graph reasoning. Inspired by distributed graph computation theory, our framework decomposes graph problems into smaller, node-centric tasks that are distributed among multiple agents. Our framework demonstrates the capability to handle real-world graph reasoning applications such as webpage importance analysis.
  arXiv  Detail & Related papers  (2024-10-07T15:34:14Z)
• GraphWiz: An Instruction-Following Language Model for Graph Problems [39.656196336071275]
  We introduce GraphInstruct, a dataset designed to equip language models with the ability to tackle a broad spectrum of graph problems using explicit reasoning paths. We build GraphWiz, an open-source language model capable of resolving various graph problem types while generating clear reasoning processes. The enhanced model, GraphWiz-DPO, achieves an average accuracy of 65% across nine tasks with different complexity levels, surpassing GPT-4 which has an average accuracy of 43.8%.
  arXiv  Detail & Related papers  (2024-02-25T08:41:32Z)
• InstructGraph: Boosting Large Language Models via Graph-centric Instruction Tuning and Preference Alignment [30.136514352238795]
  InstructGraph is a framework that empowers large language models with the abilities of graph reasoning and generation. We show that InstructGraph can achieve the best performance and outperform GPT-4 and LLaMA2 by more than 13% and 38%, respectively.
  arXiv  Detail & Related papers  (2024-02-13T20:47:17Z)
• Learning Cartesian Product Graphs with Laplacian Constraints [10.15283812819547]
  We study the problem of learning Cartesian product graphs under Laplacian constraints. We establish statistical consistency for the penalized maximum likelihood estimation. We also extend our method for efficient joint graph learning and imputation in the presence of structural missing values.
  arXiv  Detail & Related papers  (2024-02-12T22:48:30Z)
• GraphLLM: Boosting Graph Reasoning Ability of Large Language Model [7.218768686958888]
  GraphLLM is a pioneering end-to-end approach that integrates graph learning models with Large Language Models. Our empirical evaluations across four fundamental graph reasoning tasks validate the effectiveness of GraphLLM. The results exhibit a substantial average accuracy enhancement of 54.44%, alongside a noteworthy context reduction of 96.45%.
  arXiv  Detail & Related papers  (2023-10-09T16:42:00Z)
• GIF: A General Graph Unlearning Strategy via Influence Function [63.52038638220563]
  Graph Influence Function (GIF) is a model-agnostic unlearning method that can efficiently and accurately estimate parameter changes in response to a $epsilon$-mass perturbation in deleted data. We conduct extensive experiments on four representative GNN models and three benchmark datasets to justify GIF's superiority in terms of unlearning efficacy, model utility, and unlearning efficiency.
  arXiv  Detail & Related papers  (2023-04-06T03:02:54Z)
• Localized Contrastive Learning on Graphs [110.54606263711385]
  We introduce a simple yet effective contrastive model named Localized Graph Contrastive Learning (Local-GCL) In spite of its simplicity, Local-GCL achieves quite competitive performance in self-supervised node representation learning tasks on graphs with various scales and properties.
  arXiv  Detail & Related papers  (2022-12-08T23:36:00Z)
• Scaling R-GCN Training with Graph Summarization [71.06855946732296]
  Training of Relation Graph Convolutional Networks (R-GCN) does not scale well with the size of the graph. In this work, we experiment with the use of graph summarization techniques to compress the graph. We obtain reasonable results on the AIFB, MUTAG and AM datasets.
  arXiv  Detail & Related papers  (2022-03-05T00:28:43Z)
• Node Feature Extraction by Self-Supervised Multi-scale Neighborhood Prediction [123.20238648121445]
  We propose a new self-supervised learning framework, Graph Information Aided Node feature exTraction (GIANT) GIANT makes use of the eXtreme Multi-label Classification (XMC) formalism, which is crucial for fine-tuning the language model based on graph information. We demonstrate the superior performance of GIANT over the standard GNN pipeline on Open Graph Benchmark datasets.
  arXiv  Detail & Related papers  (2021-10-29T19:55:12Z)
• Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings [53.58077686470096]
  We propose an end-to-end graph learning framework, namely Iterative Deep Graph Learning (IDGL) for jointly and iteratively learning graph structure and graph embedding. Our experiments show that our proposed IDGL models can consistently outperform or match the state-of-the-art baselines.
  arXiv  Detail & Related papers  (2020-06-21T19:49:15Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.