#  A Survey of Large Language Models on Generative Graph Analytics: Query,
Learning, and Applications

Wenbo Shang  Department of Computer Science
Hong Kong Baptist University
Hong Kong, China
<EMAIL_ADDRESS>Xin Huang  Department of Computer Science
Hong Kong Baptist University
Hong Kong, China
<EMAIL_ADDRESS>
###### Abstract

A graph is a fundamental data model to represent various entities and their
complex relationships in society and nature, such as social networks,
transportation networks, financial networks, and biomedical systems. Recently,
large language models (LLMs) have showcased a strong generalization ability to
handle various NLP and multi-mode tasks to answer users’ arbitrary questions
and specific-domain content generation. Compared with graph learning models,
LLMs enjoy superior advantages in addressing the challenges of generalizing
graph tasks by eliminating the need for training graph learning models and
reducing the cost of manual annotation. In this survey, we conduct a
comprehensive investigation of existing LLM studies on graph data, which
summarizes the relevant graph analytics tasks solved by advanced LLM models
and points out the existing remaining challenges and future directions.
Specifically, we study the key problems of LLM-based generative graph
analytics (LLM-GGA) with three categories: LLM-based graph query processing
(LLM-GQP), LLM-based graph inference and learning (LLM-GIL), and graph-LLM-
based applications. LLM-GQP focuses on an integration of graph analytics
techniques and LLM prompts, including _graph understanding_ and _knowledge
graph (KG) based augmented retrieval_ , while LLM-GIL focuses on learning and
reasoning over graphs, including _graph learning_ , _graph-formed reasoning_
and _graph representation_. We summarize the useful prompts incorporated into
LLM to handle different graph downstream tasks. Moreover, we give a summary of
LLM model evaluation, benchmark datasets/tasks, and a deep pro and cons
analysis of LLM models. We also explore open problems and future directions in
this exciting interdisciplinary research area of LLMs and graph analytics.

###### Index Terms:

Graph, LLMs, GNNs, Prompt, Survey

##  I Introduction

Figure 1: Illustration of the LLM-GGA domain. LLM-GGA domain includes three
principal components: LLM-based graph query processing (LLM-GQP), which
necessitates the melding of graph analytics techniques and LLM prompts for
query processing; LLM-based graph inference and learning (LLM-GIL), focusing
on learning and reasoning over graphs; Graph-LLM-based applications that
employ the graph-LLM framework to address non-graph tasks, such as
recommendation systems.

Large language models (LLMs) possess billions of parameters and have been
trained on extensive corpora using training strategies like instruction
tuning[1][2] and Direct Preference Optimization(DPO)[3], enabling them to
exhibit powerful reasoning and semantic representation capabilities, thereby
advancing AI intelligence closer to human levels. Undoubtedly, LLMs currently
serve as the foundation model for NLP tasks[4][5][6], showcasing strong
generalization abilities to handle various NLP tasks such as question
answering[7][8], machine translation[9], code generation[10][11], etc. LLMs
have demonstrated extensive common knowledge and robust semantic comprehension
abilities, fundamentally transforming existing text-processing workflows.
While initially designed for text data, LLMs are increasingly being utilized
for tasks beyond language processing, aiming to leverage the robust
capabilities of LLMs across different tasks, showcasing superior performance.

Graphs, as structured data, play a crucial role in various real-world
application scenarios, including the citation networks [12], social networks
[13], molecular graphs [14], web links [15], and to name a few. Various graph
analytics tasks have been studied to show their usefulness, e.g., node
classification, link prediction, subgraph mining, influence maximization, and
so on. Their versatility and ability to capture complex relationships have
made graphs indispensable tools in academic research and industry platforms.
Recently, one kind of graph-based learning model, graph neural network
(GNN)[16][17], has been widely studied and applied to solve challenging graph
tasks. The GNN models utilize recursive message passing[18] and aggregation
mechanisms[19] among nodes to derive representations of nodes, edges, or
entire graphs, which have been used for various downstream tasks. This is
thanks to the strong ability of GNN models to capture both graph structure and
node features. However, GNNs exhibit weak generalization
capabilities[20][21][22], requiring retraining for different graph tasks and
showing limited transfer ability. In other words, no universal graph
foundation model could be easily generalized to handle various types of graph
tasks.

Therefore, whether LLMs’ powerful reasoning, semantic representation, and
generalization capabilities can be applied to address graph tasks, leading to
the inspiration of a graph foundation model, is the core of current efforts in
leveraging existing large language models for graph-related tasks. In one
word, can LLMs solve graph data tasks? More specifically, we study three
detailed questions: (a) what specific graph tasks can LLMs answer? (b) How do
LLMs tackle these tasks? (c) What is the effectiveness of LLM-based methods in
solving these tasks compared with the existing graph-based approaches?

To address the above question, this survey conducts a comprehensive study of
existing relevant work on graph analytics and LLMs, focusing on exploring the
key issue of the LLM-based generative graph analytics (LLM-GGA) field. Drawing
from a thorough investigation of the LLM-GGA domain, we offer a structured and
methodical analysis that delineates the field into three principal components:
LLM-based graph query processing (LLM-GQP), which necessitates the melding of
graph analytics techniques and LLM prompts for query processing; LLM-based
graph inference and learning (LLM-GIL), focusing on learning and reasoning
over graphs; and lastly, graph-LLM-based applications that employ the graph-
LLM framework to address non-graph tasks, such as recommendation systems. The
framework is shown in Figure 1.

We categorize these three main components into a total of six directions to
provide a guideline for researchers to conduct more in-depth studies. LLM-GQP
includes graph understanding and KG-based augmented retrieval directions. LLM-
GIL covers graph learning, graph-formed reasoning, and graph representation
directions. The sixth direction is graph-LLM-based applications. The following
section details these six directions:

  * •

Graph understanding tasks. This research direction is studying whether LLMs
can solve graph algorithm problems, exploring whether LLMs can comprehend
graph structures to conduct graph mining and graph search. Current methods
have primarily explored LLMs’ understanding of graph structures, such as
shortest path, clustering coefficient computation[23][24], and more complex
problems like maximum flow and Hamilton path[25][26][27]. Two main methods are
introduced: prompting and supervised fine-tuning (SFT). The prompting methods
explore the LLM’s current structural understanding ability through query
processing. Meanwhile, SFT methods enhance LLMs’ structure understanding
capability by tuning it on specific graph datasets. However, many more tasks
are yet to be explored, such as the community search, keyword search, subgraph
pattern mining, and other NP-hard complex graph problems[28][29].

  * •

Graph learning tasks. This direction explores whether LLMs can combine graph
structure and attributes for learning, extracting features of nodes, edges,
and graphs, and understanding the semantic information of graphs, for example,
tasks like node classification, graph classification, and GQL
generation[30][31][32][33]. There are two main pipelines: LLM-GNN pipelines
and LLM pipelines. LLMs can leverage their powerful reasoning ability and vast
knowledge repository to enhance GNNs and also can predict results directly.

  * •

Graph-formed reasoning. This direction explores how LLMs use graph structures
to simulate human thinking during reasoning[34][35][36], enabling them to
solve more complex reasoning problems such as algorithmic, logical, and
mathematical tasks. Graph-formed reasoning involves two types of reasoning:
think on the graph and verify on the graph. _Think on the graph_ refers to
LLMs deriving the final conclusion through the graph structure. _Verify on the
graph_ refers to verifying the correctness of the LLMs’ intermediate or final
outputs through the graph structure.

  * •

Graph representation. This direction explores enhancing graph representation
with LLMs, particularly for Text Attribute Graphs (TAGs). LLMs’ strong text
representation capabilities allow text embeddings to capture deeper semantic
nuances. However, the key challenge in this area remains how to capture and
integrate graph structure into graph representation effectively[37][38][39].
There are three forms of graph representation: graph embedding, graph-enhanced
text embedding, and graph-encoded prompts. Graph embedding methods transform a
graph into a sequential format for LLM processing. Graph-enhanced text
embedding methods integrate structure into text embedding, where the
integration method can be concatenation. Graph-encoded prompts focus on the
way a graph is described within prompts.

  * •

Knowledge Graph (KG) based augmented retrieval. This direction investigates
the relationship between LLMs and Knowledge Graphs (KGs). With the emergence
of LLMs, discussions have arisen regarding the potential replacement of
KGs[40][41][42][43]. Consequently, this paper discusses the limitations of
LLMs in processing factual knowledge, evaluates strategies for improving LLM
efficacy via KG-based augmented retrieval, and investigates potential avenues
for future advancements in this field.

  * •

Graph-LLM-based applications. This part explores the tasks where graph-LLM-
based methods can be applied for useful downstream application[44][45][46],
such as recommendation systems, conversational understanding, and so on.

We comprehensively analyze these six research directions of LLM-GGA to provide
valuable definitions and highlighted methodologies. We also highlight the pros
and cons of these methods and showcase future directions. To further explore
the capabilities of LLMs reliably, this paper uses the prompting method to
test the effectiveness of LLMs in tasks such as graph structure understanding,
graph learning, and graph-formed reasoning. Details of the prompts and results
obtained during testing are also provided. Additionally, we refine and compile
commonly used and effective prompts for graph-related tasks, assisting
researchers in conducting experiments. Furthermore, this paper also organizes
and introduces the code for existing popular methods, benchmarks for LLM-GGA
tasks, and evaluations measuring LLM performance in graph tasks to facilitate
future research.

Our contributions and the identified challenges for future research. In this
paper, we provide a comprehensive survey of the state-of-the-art work on LLMs
applied to graph data. We begin by delineating six critical directions in the
field of LLM-GGA: graph structure understanding, graph learning, graph-formed
reasoning, graph representation, KG-based augmented retrieval, and graph-LLM-
based applications. This categorization clarifies the current work and offers
a guideline for future research endeavors. In each direction, we propose a
structured introduction and summarization using vivid examples and offer
suitable specific pipelines. We analyze the advantages and limitations of
current methodologies and suggest avenues for future research. Furthermore, we
organize resources related to benchmarks, evaluations, and code links within
the LLM-GGA domain to facilitate further investigation by researchers. Lastly,
we identify the fundamental challenges in the LLM-GGA field, which are the
primary obstacles to advancing LLM in solving graph tasks, including the
fundamental issue of how sequential LLM handles structural graph data, the
efficiency issue of large-scale graph data, and the NP-hard problems of
complex graph analytics. This clarification guides the research direction for
future work on LLM-GGA.

Roadmaps. The organization of this paper is as follows. We first present the
fundamental preliminaries and summarize the graph description language, which
converts graphs into sequences before inputting them into LLMs in Section II.
Then, we introduce six tasks of LLM-based graph analytics one by one. We
present the graph structure understanding direction in Section III, graph
learning direction in Section IV, graph-formed reasoning in Section V, graph
representation in Section VI, KG-based augmented retrieval in Section VII and
graph-LLM-based applications in Section VIII. In the above six directions, we
clarify the tasks that LLMs can perform, discuss the methodologies, conduct a
comparative analysis, and propose guidelines and principles in this direction.
Following this, Section IX introduces the popular datasets and new datasets
for solving the above tasks and also provides metrics for evaluating LLMs or
tasks in different directions. In Section X, we identify and discuss the
current and upcoming challenges that LLM-GGA faces and future directions.
Finally, our conclusions are presented in Section XI.

##  II Preliminary

In the subsequent section, we will initially introduce graph data, proceed to
discuss GNNs as a paradigm of graph-based learning models, then introduce LLMs
and distinguish LLMs and PLMs, and ultimately introduce graph description
language, which can transform the graph into sequential data as the input of
LLMs.

###  II-A Graph

Graph data represents complex relationships through nodes and edges, where
nodes represent entities and edges represent their interconnections. This
structure excels at modeling intricate networks such as social, biological,
and transportation systems. It enables analyses like community detection and
shortest path calculations, offering critical insights into the dynamics of
various systems. Formally, a general graph can be represented as
$\mathcal{G}=(\mathcal{V},\mathcal{E})$, where $\mathcal{V}$ and $\mathcal{E}$
denote the set of nodes and edges. $\mathcal{V}=\\{v_{1},v_{2},...,v_{n}\\}$
where the number of nodes is $|\mathcal{V}|$ and $|\mathcal{V}|=n$.
$\mathcal{E}=\\{e_{ij}\\}$ where the number of edges is $|\mathcal{E}|$ and
$e_{i}j$ is an edge from $v_{i}$ to $v_{j}$.

###  II-B Graph Neural Network

Graph Neural Networks (GNNs) [16][17] are a type of deep learning model that
can handle graph-structured data. The goal of these GNNs is to learn
representations for each node, which are computed based on the node’s own
features, the features of the edges connected to it, the representations of
its neighbors, and the features of its neighboring nodes,

$h_{v}^{l}=AGGR(h_{v}^{l-1},\\{h_{u}^{l}-1:u\in N_{v}\\};\theta^{l})$ (1)

where $h_{v}^{l}$ represents the representation of node $v$ in the $l$-th
layer. $AGGR$ denotes the aggregation function that aggregates the
representations of neighboring nodes from the previous layer. For the tasks
that focus on individual nodes, e.g., node classification, the learned
representations can be used directly to accomplish specific objectives.
However, for the tasks that consider the entire graph, e.g., graph
classification, a global representation can be obtained by pooling or applying
other methods to the representations of all nodes. This global representation
can then be used to perform the corresponding tasks.

###  II-C Large Language Models

Currently, there is no precise definition for Large Language Models (LLMs).
However, according to the pioneering surveys [47][48] on LLMs, a distinction
can be made between LLMs and Pre-trained Language Models (PLMs). LLMs are
large language models with billion-level parameters that are pre-trained on
massive amounts of data, such as Llama[5] and ChatGPT. Conversely, PLMs are
pre-trained language models with million-level parameters that can be more
easily fine-tuned on task-specific data. While LLMs and PLMs share
similarities in their pre-training process, the former is characterized by its
larger size and ability to generate human-like text. Thus, it is essential to
consider the potential implications of using LLMs in various applications.

Figure 2: Graph Structure Understanding tasks.

###  II-D Graph Description Language

Graphs are represented in the structured data in arbitrary shapes, while LLMs
typically process sequential data, such as the text as a sequence of words. To
bridge this gap, the graph description language (GDL) transforms the graph
into sequential data, which can be inputted into an LLM. Specifically, GDL
aims to convert graphs into sequential data while retaining the structure and
unique attributes of the graph. This conversion allows the graph’s information
to be fed into an LLM for processing. There are several graph description
languages:

  * •

Text description. Graph structure can be described using words such as ‘Node 1
is connected to Node 2’ and ‘There are three nodes connected to Node 1’.

  * •

Adjacency list. An adjacency list represents each vertex in the graph with the
collection of its neighbouring vertices or edges. Node A is connected with
node B and node C can be denoted as $\mathcal{N}(v)=\\{B,C\\}$.

  * •

Edge list. An edge list represents the edge connections between two nodes in
the graph. (A, B) indicates a connection between nodes A and B.

  * •

GML. Graph Modelling Language[49] consists of an unordered sequence of node
and edge elements enclosed within ‘[·]’.

  * •

GraphML. Graph Markup Language[50] consists of XML containing a graph element
and an unordered sequence of node and edge elements.

  * •

SQL. Several specialized SQL languages are designed specifically for working
with graph data. These languages are also capable of serving as graph
description languages. Some notable examples include Cypher[51], a query
language developed by Neo4j, and Gremlin[52], SPARQL[53], and GSQL[54]. They
combine SQL-like syntax with graph-specific constructs and algorithms, making
them suitable for complex graph analytics tasks.

  * •

Multi-modality encoding. Except for text description, graph structure can also
be represented using image description and motif description. The graph can be
visualized as an image and inputted into an LLM to process images.
Alternatively, motifs such as stars, triangles, or clique patterns can
represent the graph structure as input into an LLM.

  * •

Encode as a story. The graph can be encoded within a specific context, such as
a friendship, co-authorship, social network, politician, or expert. For
example, the connections between nodes can represent friendship relationships.
We can assign names to the nodes, such as ‘David’ and ‘Alice’.

Notably, (1) different graph description languages can yield different results
of LLMs. Therefore, it is suggested to test with multiple GDLs and select the
one with the best experimental results. (2) If needed, the LLM’s output form
can be specified along with GDLs in the prompt. LLMs often generate excessive
reasoning processes that may be unnecessary, so standardizing the LLM’s output
can be beneficial.

##  III Graph Structure Understanding Tasks

Graph structure understanding tasks evaluate whether LLMs can comprehend graph
structures. Simple tasks include the queries of neighbors, shortest paths,
connectivity, the calculation of graph radius, and the clustering coefficient.
More complex tasks include solving maximum flow problems and performing
topological sorting. These tasks need LLMs to comprehend graph structures
locally and globally, as shown in Figure 2. In this section, we present 21
graph understanding tasks along with their definitions. Subsequently, we
elaborate on the two main methods currently used to address graph structure
understanding tasks: prompting and supervised fine-tuning LLMs.

Task |  Prompts
---|---
Graph Data Loading |  The structure of the [file path] molecular graph of the benzene ring contains a hexagon.
Graph Size Detection |  Given [graph], what is the number of nodes and edges in this graph? Please answer with the number of nodes: X, number of edges: X.
Degree Detection |  Given [graph], what is the degree of node 4? Or, find the node degree of node [given node] in the given graph.
Connected Nodes |  Given [graph]. Is node 5 the 1-hop neighbor of node 4? List the answers after “Ans:” in the format of [Yes, No,].
Edge Detection |  Given [graph]. Is there an edge between node 1 and node 2?
Path |  Simple path: Given the undirected graph with the specified nodes and edges, nodes: [0, 1, 2, 3, 4], edges: [(0, 1), (1, 4), (1, 3), (4, 3), (3, 2)], find a single path from node 1 to node 2 connected by edges in the given graph. Shortest path: Given the directed graph with the specified nodes and edges, nodes: [0, 1, 2, 3, 4], edges: [(0, 1), (1, 4), (1, 3), (4, 3), (3, 2)], give the shortest path from node 0 to node 4.
Attribute Retrieval |  Given [graph]. What is the title of node 0?
Graph Density |  Given [graph]. What is the density of the given graph?
Eccentricity |  Given [graph]. What is the eccentricity of the given graph?
Graph Radius |  Given [graph]. What is the radius of the given graph?
Graph Diameter |  Given [graph]. What is the diameter of this graph?
Graph Periphery |  Given [graph]. What is the periphery of this graph? Or What are the nodes included by the periphery of the given graph?
Clustering Coefficient Computing |  Given [graph]. What is the clustering coefficient of [given node]?
TABLE I: Prompts for Graph Structure Understanding Tasks, where [graph] is the input of the data. Task |  Prompts
---|---
Graph Partition |  In the academic collaboration network dblp, scholar #355233 is involved in [TBR] local community formed by his/her collaborators.
Graph Searching |  According to the Freebase knowledge graph, the relation between entity /m/027rn and entity /m/06cx9 is [TBR].
Pattern matching |  Triangle: find a single triangle containing node X. Or in the given graph, the triangle must be connected by three edges, list the triangle after ”Ans:” in the format of [0-1-2]. Cliques: find all the cliques with N nodes in the given graph, list all the cliques after ”Ans:” in the format of [0-1-2] and separate the answers by a comma. Wedge Centering find a single wedge containing node X in the given graph, node X must be the center of this wedge, list the wedge after ”Ans:” in the format of [0-1-2].
Cycle Check |  In an undirected graph, (i,j) means that node i and node j are connected with an undirected edge. The nodes are numbered from 0 to 5, and the edges are: (3,4) (3,5) (1,0) (2,5) (2,0) Q: Is there a cycle in this graph?
Topological Sort |  In a directed graph with 5 nodes numbered from 0 to 4: node 0 should be visited before node 4, … Q: Can all the nodes be visited? Give the solution.
Maximum Flow |  In a directed graph with 5 nodes numbered from 0 to 4, and the edges are: an edge from node 0 to node 1 with capacity 10… Q: What is the maximum flow from node 0 to node 3?
Bipartite Graph Matching |  There are 2 job applicants numbered from 0 to 1, and 3 jobs numbered from 0 to 2. Each applicant is interested in some of the jobs. Each job can only accept one applicant and a job applicant can be appointed for only one job. Applicant 0 is interested in job 1, … Q: Find an assignment of jobs to applicants in such that the maximum number of applicants find the job they are interested in.
Hamilton Path |  Given [graph], is there a path in this graph that visits every node exactly once? If yes, give the path. Note that in a path, adjacent nodes must be connected with edges.
Graph Neural Networks |  Given [graph]. Embeddings: node 0: [1,1], … In a simple graph convolution layer, each node’s embedding is updated by the sum of its neighbors’ embeddings. Q: What’s the embedding of each node after one layer of simple graph convolution layer?
Dynamic Graph |  In an undirected dynamic graph, (u, v, t) means that node u and node v are linked with an undirected edge at time t. Your task is to answer when two nodes are first connected in the dynamic graph. Two nodes are connected if there exists a path between them. Given an undirected dynamic graph with the edges [(0, 1, 0), (1, 2, 1), (0, 2, 2)]. When are node 0 and node 2 first connected?
TABLE II: Prompts for Graph Structure Understanding Tasks, where [graph] is
the input of the data. [TBR] means to be reasoned by LLMs.

###  III-A Task Introduction

####  III-A1 Graph size calculation

Graph size refers to the number of nodes and edges in a graph. Given a general
graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, the graph size detection task
is to detect the $|\mathcal{V}|$ and $|\mathcal{E}|$ in $\mathcal{G}$. Through
this task, LLMs are expected to understand the fundamental structure of a
graph accurately. Given a prompt describing the graph and asking related
queries, LLMs are supposed to determine $|\mathcal{V}|$ and $|\mathcal{E}|$,
as shown in Figure 2 (a).

####  III-A2 Degree calculation

The degree detection task involves determining the degree of a specific node
in a graph. The neighbors of node $v$ can be denoted as
$\mathcal{N}(v)=\\{u|(u,v)\in\mathcal{E}(v)\\}$, where $\mathcal{E}(v)$ is the
edge set including edges connected to $v$. The degree of $v_{i}$ is the number
of its neighbors in $\mathcal{G}$, which can be denotes as
$deg_{\mathcal{G}}(v_{i})=|\mathcal{N}(v_{i})|$. Through this task, LLMs are
expected to comprehend the context surrounding $v_{i}$ and identify
$\mathcal{N}(v_{i})$ accurately. By inputting a prompt about $v_{i}$ and
$\mathcal{G}$, LLMs are expected to calculate the degree of the node. This
task is shown in Figure 2 (b).

####  III-A3 Connected nodes search

The connected nodes detection task involves finding all the nodes in
$\mathcal{N}_{\mathcal{G}}(v_{i})$ of $v_{i}$ in $\mathcal{G}$. Given the
prompt about $\mathcal{G}$, LLMs are expected to analyze the local structure
of the given node $v_{i}$ and determine $\mathcal{N}_{\mathcal{G}}(v_{i})$, as
shown in Figure 2 (c).

####  III-A4 Edge validation

The edge detection task refers to whether there exists an edge $e_{ij}$ or
$e_{ij}$ between $v_{i}$ and $v_{i}$. Through this task, LLMs are expected to
accurately identify the connectivity between nodes and understand the local
structure of nodes. Given the prompt about the neighbors of $v_{i}$ to the
LLMs, LLMs will likely indicate whether $e_{ij}$ or $e_{ij}$ exists, as shown
in Figure 2 (d).

####  III-A5 Path search

We consider two types of paths, including the simple path and the shortest
path, as shown in Figure 2 (e). Given a graph
$\mathcal{G}=\\{\mathcal{V},\mathcal{E}\\}$, the simple path task involves
detecting whether there exists a path $(v_{i},...,v_{j})$ between a source
node $v_{i}$ and a target node $v_{j}$ in $\mathcal{G}$. In other words, it is
about finding a simple path $(v_{i},...,v_{j})$ between $v_{i}$ and $v_{j}$
without specific requirements. This task evaluates the ability of LLMs to
traverse a graph and understand its structure. Given the prompt about
$\mathcal{G}$ to LLMs, the goal is to return a simple path from $v_{i}$ to
$v_{j}$.
Given a weighted directed acyclic graph
$\mathcal{G}=\\{\mathcal{V},\mathcal{E}\\}$ with each edge $e\in\mathcal{E}$
has a non-negative weight $w(e)$, the shortest paths task involve finding a
path $p=(e_{1},e_{2},…,e_{n})$ from a source node to a target node in
$\mathcal{G}$ such that the sum of the weights of edges
$w(p)=\sum^{n}_{i=1}w(e_{i})$ is minimized. LLMs can evaluate the length of
the shortest path and identify the qualified paths. This task can be further
divided into three objectives: 1. Finding the shortest path between two nodes.
2. Finding all the shortest paths for all paired nodes. 3. Finding the average
length of all the shortest paths. This task assesses whether the LLM can
effectively determine the shortest route between two specified nodes within
the graph.

####  III-A6 Attribute retrieval

The attribute retrieval task involves retrieving detailed information related
to nodes, such as the attributes of a node. For example, in a citation
network, LLMs are tasked with retrieving specific attributes of a node, such
as the title, abstract, or author of a paper. Given the prompt about
$\mathcal{G}$ and detailed attribute information, LLMs are expected to
retrieve the required information, as shown in Figure 2 (f).

####  III-A7 Graph density

Graph density represents the ratio between the number of edges present in a
graph and the maximum number of edges that the graph can have. For an
undirected simple graph $\mathcal{G}=\\{\mathcal{V},\mathcal{E}\\}$, the graph
density is defined as:

$\mathcal{D}=\frac{2|\mathcal{E}|}{|\mathcal{V}|(|\mathcal{V}|-1)}$ (2)

For a directed simple graph, the graph density is defined as:

$\mathcal{D}=\frac{|\mathcal{E}|}{|\mathcal{V}|(|\mathcal{V}|-1)}$ (3)

This task requires LLM to calculate the density of a given graph and assess
its understanding of the entire graph, as shown in Figure 2 (g).

####  III-A8 Eccentricity

The eccentricity of a node in a graph is defined as the length of the longest
shortest path starting at that node. The eccentricity of one node: this task
requires LLMs to answer the eccentricity of a given node. The eccentricity of
many nodes: this task requires LLMs to answer the eccentricity of a subset of
nodes or all the nodes in the graph, as shown in Figure 2 (h).

####  III-A9 Graph radius

Based on the eccentricity of nodes, the radius of a graph is the minimum
eccentricity of any vertex in the graph. LLMs can calculate the radius of the
given graph with the description of the graph.

Figure 3: Examples for Path Task with GPT3.5 - Graph Structure Understanding
Tasks. Figure 4: Examples for Maximum Flow Task with GPT3.5 - Graph Structure
Understanding Tasks. Figure 5: Examples for Bipartite Graph Matching Task with
GPT3.5 - Graph Structure Understanding Tasks.

####  III-A10 Graph center

The center of a graph is the set of vertices of graph eccentricity equal to
the graph radius. Based on the eccentricity task and graph radius task, LLMs
should be given the graph information and asked to calculate the graph center.

####  III-A11 Graph diameter

Based on the shortest path, the diameter of a graph is the length of the
shortest path between the most distant nodes. LLMs can calculate the graph’s
diameter with the given graph information, as shown in Figure 2 (i).

####  III-A12 Graph periphery

Based on the graph eccentricities and graph diameter, the graph periphery is a
set of vertices that have graph eccentricities equal to the graph diameter.
LLMs can answer questions related to the graph periphery using the given graph
information.

####  III-A13 Clustering coefficient computing

The clustering coefficient is a measure of how connected a vertex’s neighbors
are to one another. We define the edges among neighbors of $v_{i}$ as
$\\{e_{jk}:v_{j},v_{k}\in\mathcal{N}_{\mathcal{G}}(v_{i}),e_{jk}\in\mathcal{E}\\}$.
For directed graphs, the clustering coefficient is defined as:

$\mathcal{C}_{i}=\frac{|\\{e_{jk}:v_{j},v_{k}\in\mathcal{N}_{\mathcal{G}}(v_{i}),e_{jk}\in\mathcal{E}\\}|}{|\mathcal{N}_{\mathcal{G}}(v_{i})||\mathcal{N}_{\mathcal{G}}(v_{i})-1|}$
(4)

For undirected graphs, the clustering coefficient is defined as:

$\mathcal{C}_{i}=\frac{2|\\{e_{jk}:v_{j},v_{k}\in\mathcal{N}_{\mathcal{G}}(v_{i}),e_{jk}\in\mathcal{E}\\}|}{|\mathcal{N}_{\mathcal{G}}(v_{i})||\mathcal{N}_{\mathcal{G}}(v_{i})-1|}$
(5)

LLMs can calculate the clustering coefficient as a measure of the degree to
which nodes in a graph tend to cluster together.

####  III-A14 Graph partition

This task is an online social network reasoning task, which is to infer the
community structure of an online social network by partitioning users into
different clusters based on their interaction information. Each cluster
represents a social community formed by users who interact with each other
frequently. LLMs partition the users of the social network based on user
social interaction patterns and generate the resulting cluster assignments.

####  III-A15 Graph searching

This task is a knowledge graph reasoning task, which involves inferring
relationships between entities based on their information or inferring
connected entities based on the information of entities and relationships.
Specifically, LLM takes entities or relationships as input and searches for
relevant entities or relationships to generate output.

####  III-A16 Pattern matching

This task is to identify star, wedge, triangle, or clique patterns that
contain a target node. The target node can be defined as the center of the
pattern. Alternatively, the task can involve identifying whether these
patterns exist in a given graph and determining the number of occurrences.
Given a description of the LLM graph, the goal is for LLM to identify
different patterns and provide the corresponding answers, as shown in Figure 2
(j).

####  III-A17 Cycle validation

This task is to determine whether a graph contains a cycle. Given
$\mathcal{G}=\\{\mathcal{V},\mathcal{E}\\}$, a cycle is a non-empty trail with
a vertex sequence $(v_{1},v_{2},...,v_{n},v_{1})$. Given the graph
information, LLM is asked to determine whether this graph has a cycle.

####  III-A18 Topological sorting

Topological sorting of a directed graph
$\mathcal{G}=\\{\mathcal{V},\mathcal{E}\\}$ refers to a linear ordering of its
nodes, where each node comes before all the nodes it points to, for example,
there exists a directed edge $e_{ij}$ from $v_{i}$ to $v_{j}$, $v_{i}$ comes
before $v_{j}$ in the ordering. The resulting array of node ordering is called
topological ordering. LLM is required to generate a valid topological sorting
for the given directed graph, and there may be multiple valid solutions, as
shown in Figure 2 (k).

####  III-A19 Maximum flow

Given a capacity constraint, the maximum flow problem involves finding the
maximum flow that can be sent through pipes, channels, or other pathways in a
network. Define a flow as $f_{ij}$ from $v_{i}$ to $v_{j}$ and the capacity on
edge $e_{ij}$ as $c_{ij}$. Given the capability constraints, $f_{ij}\leq
c_{ij}$ for all $e_{ij}$. Meanwhile,
$\sum\limits_{f_{ij}>0}f_{ij}=\sum\limits_{f_{ji}>0}f_{ji}$ for $\forall
v_{i}$ except for the source and the target $\\{s,t\\}$ Given a network graph,
LLM generates a path that maximizes the flow from the source to the sink, as
shown in Figure 2 (l).

####  III-A20 Bipartite graph matching

A bipartite graph is a type of graph where the nodes can be divided into two
disjoint sets, $\mathcal{U}$ and $\mathcal{V}$, such that there are no
adjacent nodes within each set. A matching in a bipartite graph is a set of
edges where no two edges share an endpoint. In a maximum matching, if any edge
is added, it is no longer a matching. For a given bipartite graph, there can
be multiple maximum matchings. LLM can generate a solution that finds the
maximum matching, as shown in Figure 2 (m).

####  III-A21 Hamilton Path

In an undirected graph, a Hamiltonian path is a path in the graph that visits
each vertex exactly once. Given an undirected graph, the task is for LLM to
find a valid Hamiltonian path, as shown in Figure 2 (n).

###  III-B Graph Structure Understanding Methods

The rise of LLMs has sparked researchers’ interest in exploring their powerful
text processing and generalization capabilities for graph reasoning.
Therefore, existing efforts have introduced various benchmarks to test LLMs’
graph reasoning potential, aiming to explore their capacity to address graph-
related problems. Prompting methods have emerged as the primary approach to
assess LLMs’ understanding of graph structures, with some studies also
focusing on fine-tuning LLMs to enhance their graph reasoning abilities. Thus,
the following two main methods are introduced: _prompting method_ and _fine-
tuning LLMs_.

Figure 6: Promoting methods in graph structure understanding tasks. There are
three categories: manual prompts, self-prompting, and API call prompts.

####  III-B1 Prompting method

The prompting method[55] can be categorized into three main types: manual
prompt, self-prompting, and API call prompt, as shown in Figure 6. Most
studies utilize manual prompts, where carefully crafted prompts guide LLMs to
comprehend graph structures better and understand the objectives of graph
tasks, thereby leading to improved performance on graph-related tasks.

Manual prompts. NLGraph[27] introduces a benchmark aiming to assess the
understanding capabilities of LLMs in processing textual descriptions of
graphs and translating them into conceptual spaces. This benchmark covers
various graph reasoning tasks like connectivity, shortest path, maximum flow,
and graph neural network construction, with three difficulty levels (easy,
medium, hard) based on graph size and density. Meanwhile, the number of nodes
$n=|\mathcal{V}|$ and the probability $p$ control edge generation, allowing
manipulation of graph size and density for a more reliable evaluation of LLM
potential in graph comprehension.

Next, to guide LLMs in solving these graph tasks, two prompt methods are
proposed by NLGraph[27]: build-a-graph prompting and algorithmic prompting.

Prompt III-1: Build-a-Graph Prompting. Build-a-Graph prompting method is to
guide LLMs to conceptual grounding by adding one sentence shown as red words
below:

Prompt III-2: Algorithmic Prompting. The algorithmic prompting method is
designed to guide LLMs to engage in algorithmic reflection and thinking by
adding the details of the algorithm shown as red words below:

Compared with other advanced prompts and in-context learning techniques, the
two proposed prompts perform better on graph tasks. Based on the experiments,
LLMs indeed possess preliminary graph reasoning abilities. Also, the benefits
of advanced prompting and in-context learning diminish in complex graph
problems and may even have a negative impact. LLMs are also susceptible to
false correlations, performing poorly on graph structures such as chains and
cliques.

To explore whether LLMs can truly comprehend graph structures and reason on
graphs, meanwhile, enhance the performance of LLM-GQP tasks, [26] and [24]
test LLMs also using manual prompts, where [26] explores the conditions under
which LLMs can benefit from the inherent structural information in the data
and examines two potential factors influencing LLM’s performance: data leakage
and homogeneity.

In summary, the conclusions are as follows:

  * •

No evidence suggests that LLM’s performance is significantly attributed to
data leakage.

  * •

The performance of LLMs on target nodes is positively correlated with the
local homogeneity of the nodes.

[24] investigates the graph reasoning capabilities of LLMs and introduces new
evaluation metrics—comprehension, correctness, fidelity, and rectification—to
assess LLMs’ proficiency in understanding graph structures and performing
reasoning tasks. The findings reveal that LLMs can effectively understand
graph structures and perform reasoning tasks. However, LLMs still face
challenges in structural reasoning, particularly in multi-answer tasks where
GPT models demonstrate errors and overconfidence. In contrast, GPT-4 displays
improved self-correction abilities.

Beyond static graphs, LLMs’ ability to understand dynamic graph structures is
also assessed. Dynamic graphs change over time, capturing temporal network
evolution patterns. LLM4DyG [25] introduces the LLM4DyG benchmark, which uses
prompting methods to evaluate LLMs’ spatio-temporal understanding capabilities
on dynamic graphs.

Prompt III-3: DST2. The newly proposed Disentangled Spatial-Temporal Thoughts
(DST2) prompting technique enhances LLMs’ spatial and temporal understanding
of dynamic graphs. DST2 is shown below:

Results show that LLMs have preliminary spatio-temporal understanding
capabilities on dynamic graphs. Dynamic graph tasks become increasingly
challenging with larger graph sizes and densities while insensitive to periods
and data generation mechanisms.

We provide manual prompt examples for various graph structure understanding
tasks in Table I and Table II. Additionally, we test LLMs with GPT 3.5 for
path, max flow, and bipartite graph matching using manual prompts, as shown in
Figure 3, Figure 4 and Figure 5 respectively.

For self-prompting. Self-prompting refers to the process where an LLM
continuously updates the initial prompt to make it easier for LLMs to
understand and more beneficial for solving tasks. In other words, the LLM
designs prompts based on the original prompt. GPT4Graph[23] utilizes self-
prompting by continuously updating the prompt with descriptions related to the
graph. Specifically, first, the graph data is converted into graph description
languages, as shown in Section II-D. Then, together with queries, it is
inputted into the prompt handler to create a prompt, which is then inputted
into the LLM. Based on the output of the LLM, the prompt is updated and re-
input into the LLM, repeating multiple rounds of updates to obtain an
optimized graph description context, such as context summarization and format
explanation. This process can be seen as the LLM’s self-updating prompt
procedure. Finally, the optimized graph description context is input along
with the original input into the LLM to obtain the final result.

Prompt III-4: Self-prompting. The input original prompt is shown below:

This paper conducts experiments on the obgn-arxiv[56] and Aminer[57] datasets
and finds that:

  * •

The design of prompts significantly impacts the results. The choice of graph
description language, the organization of input data, and the position of in-
context knowledge, such as questions, statements, and examples, all affect the
model’s ability to understand the graph structure.

  * •

Role prompting techniques can improve the effectiveness of LLMs by guiding the
model to view the graph as roles and relationships between roles in a specific
context. Providing LLMs with more semantic information leads to more accurate
results.

  * •

Examples in prompts have mixed impacts on graph structure understanding.
Adding examples in prompts to guide LLMs in understanding graph structures may
not necessarily improve the results; in some graph structure learning tasks,
examples may introduce noise.

API call prompts LLMs exhibit limited ability to perform precise mathematical
calculations, multi-step logical reasoning, spatial topological structuring,
and temporal information processing. To bridge these gaps, taking inspiration
from recent models such as ChatGPT and Toolformer[58], Graph-ToolFormer[59] is
proposed to equip LLMs with graph reasoning capabilities by training them over
a prompt dataset that contains graph reasoning API annotated by ChatGPT. These
graph reasoning APIs are used to call external reasoning tools. Then, the
trained LLMs can solve graph tasks, from loading graph data and inferring
graph attributes to graph partition tasks.

The framework consists of three parts. First, it generates a prompt dataset by
providing ChatGPT with a regular prompt, guiding ChatGPT to add an API call to
the original prompt, and then creating a prompt with an API call.

Prompt III-5: API call prompts

Second, fine-tune existing LLMs such as GPT-J[60][61], LLaMA[5][62], etc.,
using technologies like LoRA[63] on the generated prompt dataset. Thirdly,
utilize the fine-tuned LLM for inference to add graph reasoning API calls into
statements. After generating API call statements, how can external graph tools
be invoked? Graph reasoning query processing comes in. Graph reasoning query
processing entails utilizing external graph reasoning tools based on API call
statements to obtain the final answer.

Figure 7: Supervised fine-tuning (SFT) method in graph structure understanding
tasks. Prefix tuning is shown above: combine graph structural and textual
information as prefixes in prefix tuning and input it into LLM with
instructions, like GraphLLM[64]. Instruction tuning can also be used.

####  III-B2 Supervised fine-tuning (SFT) method

Beyond leveraging prompts for graph-structured tasks with LLMs, certain
studies have also implemented supervised fine-tuning of LLMs, illustrated in
Figure 7. GraphLLM[64] is committed to addressing the obstacles in graph
reasoning by LLMs and introduces a hybrid model that inherits the capabilities
of both graph learning models and LLMs, enabling LLMs to interpret and reason
about graph data proficiently, utilizing the superior expressive power of
graph learning models.

Figure 8: Graph Learning tasks.

###  III-C Comparisons and Discussions

In the following part, we compare the prompting and SFT methods mentioned
above.

The prompting method can be divided into three categories: manual prompts,
self-prompting, and API call prompts. Most current methods primarily rely on
manual prompts, incorporating techniques like Chain of Thought (CoT)[65],
self-consistency[66], and in-context learning[67]. To obtain better prompt
representations, self-prompting methods are also widely used. However, the
exclusive use of manual prompts and self-prompting offers limited enhancement
to model performance, as they merely tap into the pre-existing capabilities of
LLMs. Additionally, due to the limited input window of LLM, the graph size
that can be input to LLM at once is also restricted, while graph sizes in the
real world are typically large.

For the prompting method, we also propose two feasible directions to better
leverage existing LLMs for handling structure understanding tasks. The first
direction is breaking down complex tasks into several sub-problems. While LLMs
can tackle simple graph tasks, they struggle with more challenging ones.
Breaking down complex graph understanding tasks into simpler components
enables LLMs to engage in multi-step reasoning processes, leading to the
resolution of complex issues, such as GoT[59], which can help address more
intricate graph tasks like generating GNN frameworks, k-truss tasks, kd-core
tasks, etc. The second direction is API call prompts. Inspired by
ToolFormer[58], LLMs can be trained as agents to utilize tools for graph tasks
that are hard to solve. However, current API call prompt methods[59] utilize
LLMs not as agents but solely to convert user queries into API command strings
for processing by subsequent programs, exemplified in Prompt III-5.

However, compared to prompting methods, fine-tuning LLMs with graph data seems
a better way to enhance their understanding of graph structures. There are two
mainstream methods for fine-tuning LLMs: Supervised Fine-Tuning (SFT) and
Reinforcement Learning with Human Feedback (RLHF)[6]. SFT helps LLMs
understand prompts and generate meaningful responses. However, SFT only offers
a single human-written response for each prompt, whereas RLHF provides
detailed human feedback through pairwise comparison labeling. Furthermore, to
address the instability issue in PPO[68] training, the Reward Ranked Fine-
Tuning (RAFT)[69] can also be attempted which requires online interaction. For
offline algorithms, methods like DPO[3] and Preference Ranking Optimization
(PRO)[70] can also be utilized for training LLMs.

Task |  Prompts
---|---
KGQA |  Given [knowledge graph], the director who directs Inception also direct what?
GQL Generation |  Given [graph], the director who directs Inception also direct what? Use Cypher to answer.
Node Classification |  Which arxiv CS subcategory does paper ”paper title” with abstract ”paper abstract” belongs to? use the abbreviation to answer.
Graph Classification |  Given [graph]. Is this molecule active with H3C4?
Node Feature Explanation |  Abstract: Text in curve orientation, despite being one of the common text orientations in real world environment… Title: Total Text A Comprehensive Dataset For Scene Text Detection And Recognition. Question: Which arXiv CS sub-category does this paper belong to? Give 5 likely arXiv CS sub-categories as a comma-separated list ordered from most to least likely, in the form ”cs.XX”, and provide your reasoning.
Edge classification |  learnable prompt
TABLE III: Prompts for Graph Learning Tasks, where [·] is the input of the
data.

##  IV Graph Learning Tasks

###  IV-A Tasks Introduction

Recently, LLMs have been shown to possess extensive common sense and powerful
semantic understanding capabilities, fundamentally transforming the existing
workflow for processing text. However, whether LLMs can effectively handle
graph learning tasks, transferring their generalization ability from text
tasks to graph learning tasks, such as node and graph classification, is still
a research subject that needs exploring. These tasks require the model to
learn and solve graph learning tasks, as shown in Figure 8. In this section,
we present seven graph learning tasks along with their definitions. Next, we
introduce graph learning methods, categorized into three types based on the
role of LLMs: LLMs act as enhancers, LLMs act as predictors, and graph
prompts.

####  IV-A1 Node classification

The node classification task requires LLM to learn based on the neighbors of a
node or the attributes of a node. It involves classifying unseen nodes in a
given graph, such as categorizing papers in an academic network into different
research directions, as shown in Figure 8 (a).

####  IV-A2 Graph classification

The graph classification task requires LLM to classify the entire graph. LLM
is given several labeled graphs and is expected to classify unseen graphs. For
example, a molecule can be viewed as a graph, and LLM can predict the
properties or functions of the molecule by classifying the graph, as shown in
Figure 8 (b).

####  IV-A3 Edge classification

The edge classification task involves classifying the edges in a graph.
Existing methods improve edge classification by training a learnable graph
prompt and combining it with a GNN or LLM, as shown in Figure 8 (c).

####  IV-A4 Node generation

The node generation task refers to providing requirements for an LLM to
generate nodes, allowing it to generate node attributes, which are then added
to the TAG to enhance it.

####  IV-A5 Knowledge graph question qnswering (KGQA)

Knowledge graph organizes data into a structured format, representing
entities, properties, and relationships. Knowledge graph question answering
(KGQA) aims to capture the most appropriate answers by querying the knowledge
graph (KG) using natural language questions. This task evaluates the ability
of LLM to reason and understand the underlying graph structure to provide
accurate answers, as shown in Figure 8 (d).

####  IV-A6 Graph query language (GQL) generation

The graph query language generation task involves generating graph query
languages, including GQL and Cypher, to perform operations on graph databases.
Evaluating LLM’s ability to generate GQL helps users extract information from
the database, as shown in Figure 8 (e).

####  IV-A7 Node feature explanation

Node feature explanation task involves extracting the attributes of nodes in a
text attribute graph. For example, in an academic paper network, the node
attributes may include abstracts, titles, etc. LLM is expected to provide
reasoning for the classification process of nodes based on their text
attributes and explain the features of the nodes, as shown in Figure 8 (f).

Figure 9: Encoding graph into embeddings, when LLMs act as enhancers. Input
the node text attribute into LM/LLM to obtain text embeddings, then combine
the text embeddings with the graph structure for training and learning in
GNNs. Figure 10: Generating graph pseudo labels, when LLMs act as enhancers.
Input unlabeled nodes into LLM for labeling, then use the labeled nodes with
pseudo-labels as input for training the GNNs for graph learning.

###  IV-B Graph Learning Methods

LLM-GIL studies focusing on graph learning tasks can be categorized into three
main groups: LLMs act as enhancers, LLMs act as predictors, and graph prompts.
When LLMs act as enhancers, they leverage their advanced semantic
understanding of the text, strong reasoning capabilities, and vast knowledge
repository to enhance the text attributes associated with nodes in the graph
to enhance GNNs. When LLMs act as predictors, LLMs are queried or fine-tuned
to predict task results. Inspired by NLP ideas, the Graph prompt aims to
create a unified framework capable of solving multiple graph learning tasks.
Although LLMs are not used, the concept aligns with LLM-based pipelines.

In summary, integrating LLMs in graph learning tasks presents a promising
avenue for advancing the field. By leveraging the strengths of LLMs as
enhancers and predictors, along with the strategic use of graph prompts,
researchers can explore new directions for enhanced performance and more
profound insights in LLM-GIL tasks.

####  IV-B1 LLMs act as enhancers

LLMs act as enhancers pertains to the LLMs-GNNs pipelines, where LLMs assume
an enhancer role. Within this framework, LLMs are tasked with processing text
attributes, while GNNs are responsible for handling graph structures,
capitalizing on the complementary strengths of both components to address
graph learning tasks effectively. LLMs bolster GNNs through three distinct
mechanisms: encoding the graph into embeddings (as shown in Figure 9),
generating graph pseudo labels (as shown in Figure 10), and providing external
knowledge or explanations (as shown in Figure 11). Subsequently, we will
provide a comprehensive elaboration on these three enhancement strategies.

Encoding graph into embeddings. LLMs possess significant semantic
comprehension capabilities to encode better node embeddings, as shown in
Figure 9. TAPE[30] integrates LM with LLM to generate node embeddings. The
process involves fine-tuning two LM models using original node text attributes
and LLM explanations for node prediction. The resulting embeddings are then
used as input to train a GNN model for node classification tasks. To unify
graph data and graph learning tasks, OFA[32] introduces a comprehensive
framework that unifies diverse graph data by describing nodes and edges using
natural language and encoding varied and potentially cross-domain text
attributes into feature vectors within the same embedding space. The obtained
feature vectors are then fed into a GNN to tackle various downstream tasks
effectively. Moreover, SIMTEG[71] and GLEM[31] involve training an LM with
Lora and subsequently generating embeddings as text representations, then a
GNN is trained on top of these text embeddings. On this basis, G-prompt[33]
introduces a graph adapter to extract node features, thereby obtaining
improved node representations.

Figure 11: Providing external knowledge/explanations, when LLMs act as
enhancers. Two pipelines are shown above. In the first pipeline, input node
text attributes into LLM for elaboration, enhancing the detail of the text
attributes. In the second pipeline, input node text attributes and designed
queries into LLM. LLM leverages the text attributes to answer queries and
explains the reasoning process.

Generating graph pseudo labels. Many existing pipelines utilize LLMs to
process text attributes as node features, then feed the embeddings produced by
LLM into a GNN model for learning, as shown in Figure 10. However, the
simultaneous training of LLM and GNN poses a significant computational
challenge. To bridge this gap, GLEM[31] suggests training the GNN and LM
separately in a variational Expectation-Maximization (EM) framework. In the
E-step, the LM predicts both gold labels and pseudo-labels from the GNN, while
in the M-step, the GNN predicts gold labels and LM-inferred pseudo labels
using the embeddings and pseudo-labels provided by the LM.

Moreover, due to the high cost of annotation and the necessity for GNN to
learn from a substantial amount of high-quality labeled data to ensure its
performance on graph tasks, leveraging the zero-shot learning capability of
LLM becomes advantageous. Therefore, employing LLM for graph annotation can
enhance GNN training even with limited labeled data. LLM-GNN[72] proposes to
select a candidate node set to be annotated. Subsequently, LLMs annotate the
candidate node set, and post-filtering is conducted to eliminate low-quality
annotations. Finally, the GNN is trained using the high-quality annotation set
and utilized for prediction. LLM-GNN[72] proposes to select a candidate node
set for annotation by LLMs, followed by post-filtering to remove low-quality
annotations. Then, GNN is trained using high-quality annotations for
prediction.

Providing external knowledge/explanations. LLMs possess a vast knowledge base,
enabling them to provide external knowledge or explanations related to node
features when encoding them, as shown in Figure 11. The additional knowledge
assists the model in better extracting and capturing node features. Graph-
LLM[73] utilizes LLMs, such as ChatGPT, to explain text attributes, enhancing
them and generating pseudo labels. These enhanced attributes are then fed into
a trainable LLM, like Llama, to produce node feature embeddings. The combined
pseudo labels and embeddings are input into a GNN, which delivers the final
prediction outcomes.

Similarly, TAPE[30] leverages LLMs to provide external explanations. In a
citation network where each node contains text attributes like title and
abstract, the text attribute of each node serves as input to an LLM. The LLM
categorizes the nodes and generates multiple predictions ranked in a list with
accompanying reasoning explanations. This approach aims to extract the LLM’s
reasoning capabilities while integrating external knowledge to aid in
understanding node text attributes and extracting node features.

Figure 12: LLMs act as predictors. For prompting LLMs, input designed manual
prompts into LLM, enabling it to predict nodes/links/graphs. For SFT LLMs,
input instructions into the LLM to generate multiple answers. Tuning the LLM
is then based on these multiple responses.

####  IV-B2 LLMs act as predictors.

When LLMs are predictors, they are usually directly employed as standalone
predictors. The critical aspect of integrating LLMs as predictors lies in
crafting a well-designed prompt that encompasses text attributes and graph
structures, enabling LLMs to comprehend the graph structure effectively and
enhance prediction accuracy. Additionally, there are other methodologies to
fine-tune LLMs, such as utilizing techniques like LoRA[63] and instruction
tuning, aiming to deepen the LLM’s understanding of the graph structure. Based
on whether LLMs undergo parameter training, they are categorized into
prompting LLMs and SFT LLMs, as shown in Figure 12.

Prompting LLMs. The prompting method can be divided into two categories. One
type is the manual prompts, which are manually written prompts.

Prompt IV-1: Manual Prompt Template with Slots. For instance, Beyond Text[74],
ENG [75], and Graph Agent[76] provide a manual prompt template with slots. By
filling these slots with different examples, various prompts can be
constructed. For example:

Compared to manual prompts, LPNL[77] generates prompts through sampling.
Specifically, it conducts a two-stage sampling process on the source node and
each candidate neighbor from the original candidate set to acquire anchor
nodes. Prompt generation is then based on these anchor nodes.

We provide manual prompt examples for various graph learning tasks in Table
III. Additionally, we test LLMs with GPT 3.5 for node classification and KGQA
using manual prompts, as shown in Figure 13 and Figure 14.

Figure 13: Examples for Node Classification Task with GPT4 - Graph Learning
Tasks. Figure 14: Examples for KGQA with GPT3.5 - Graph Learning Tasks.

Supervised fine-tuning (SFT) LLMs. IntructGLM[78] and GraphGPT[79] both employ
SFT to train LLM for the node classification task. IntructGLM[78] utilizes a
single LLM by prompting methods. The prompt includes the description of node
attributes and structure through text descriptions and corresponding queries.
LLMs are then tasked with answering questions and determining node categories,
leading to fine-tuning through supervised learning. On the other hand,
GraphGPT[79] feeds graph structural information and text into LLM via
embedding. Subsequently, two rounds of instruction tuning are conducted to
refine LLM and effectively address the node classification task.
IntructGLM[78] employs prompts to input subgraph structures into LLM, while
GraphGPT[79] inputs them into LLM through embedding.

Figure 15: Graph prompt for graph learning.Graph prompt methods first unify
prefix and downstream tasks, then pre-train GNN on the unified tasks. The pre-
trained GNN, when faced with different downstream tasks, combines with a
tunable prompt through tuning prompts to handle the downstream tasks better.

####  IV-B3 Graph prompt

In graph learning tasks, a wide array of tasks at the node, edge, and graph
levels creates a challenge in achieving compatibility between pre-training and
downstream tasks, potentially leading to negative transfer effects that can
harm the performance of downstream tasks and compromise the reliability of
transfer learning in graph data. Current methods aim to harmonize pre-training
and downstream tasks to facilitate more effective transfer learning of graph
information. Despite these efforts, it remains essential to identify task-
specific differences for optimal performance. Inspired by NLP, researchers
have started incorporating prompts in graph contexts to enable the reuse of
pre-trained models across various downstream tasks without the need for
repeated fine-tuning, as shown in Figure 15. The integration of prompts is
crucial in assisting downstream tasks in achieving task-specific optimal
outcomes, bridging the gap between pre-trained models and the diverse array of
graph tasks to enhance performance and transferability.

GPPT[80] and GraphPrompt[81] aim to unify pre-training and downstream tasks in
graph learning. GPPT transforms node classification tasks into edge prediction
tasks and employs masked edge prediction for GNN pre-training. Meanwhile,
GraphPrompt combines node and graph classification tasks into a subgraph
similarity prediction task and utilizes graph prompt functions, introducing
unified instances and task templates to enhance performance. Subsequent
research, like All in One[82], further consolidates edge, node, and graph
classification tasks into a single framework using multi-task prompting
approaches, standardizing graph prompts similar to language prompts and
enhancing initialization through meta-learning techniques for improved
reliability and generality across different tasks in graph data analysis.

###  IV-C Comparisons and Discussions

For addressing graph learning tasks, existing methods[30][79][82] categorize
based on the role of LLM into three types: LLMs act as enhancers (LLM-GNN
pipelines), LLMs act as predictors (LLM pipelines), and graph prompts. In the
part of graph prompts, we introduce the prompting engineering in GNNs without
utilizing LLMs. Graph prompts aim to unify downstream tasks and construct a
universal framework. Therefore, it is compared with LLM-GNN pipelines and LLM
pipelines to provide a comprehensive overview.

When LLMs act as enhancers, the most popular pipeline is the LLM-GNN pipeline.
There are three categories of LLM-GNN pipelines, depending on how LLM enhances
GNN: encoding the graph into embeddings, generating graph pseudo labels, and
providing external knowledge/explanations. However, the LLM-GNN pipelines that
are currently available are not end-to-end pipelines, meaning that LLM and GNN
cannot be trained together. LLM and GNN can be trained separately using
frameworks like EM framework[31] or by freezing LLM and using it as an
external knowledge base. Co-training LLM and GNN can lead to issues like
gradient vanishing, which is a significant obstacle in current LLM-GNN
pipelines due to the large number of parameters in LLM compared to GNN. To
solve this problem, methods like knowledge distillation can reduce the number
of LLM parameters while retaining the beneficial capabilities for downstream
tasks.

When LLMs act as predictors, two main methods are used: prompting LLMs and SFT
LLMs. All approaches for fine-tuning LLMs can be reviewed in the ”comparisons
and discussions” section of Section III. Currently, SFT and DPO are popular
methods for fine-tuning LLMs.

For graph prompt, the workflow involves unifying pre-training and downstream
tasks, followed by prompt tuning for different downstream tasks through prompt
engineering, as shown in Figure 15. Graph prompts require fewer tunable
parameters compared to LLM-GNN and LLM pipelines; however, they have a
shallower semantic understanding of graph attributes. In LLM pipelines, LLMs
need to undergo alignment tuning before they can be used for various
downstream tasks. In LLM-GNN pipelines, there is a general trend of training
GNNs. Combining LLM-GNN and graph prompts is possible because graph prompts
are designed for GNNs through prompt engineering and can be applied to LLM-GNN
pipelines. By leveraging LLM’s robust semantic representation capabilities and
the lightweight fine-tuning of graph prompts, similar results can be achieved.

Figure 16: Graph-formed Reasoning Tasks.

Classical graph tasks, such as node classification on attributed static
networks, have recently obtained the most attention. However, there is
potential for more complex tasks in the future, such as predicting graph
evolution on dynamic graphs. Leveraging LLM models that are suitable for
handling sequential data and can process time series data, along with GNNs
that are adept at capturing changes in graph structures, can help address a
broader range of problems effectively. By combining the strengths of LLM and
GNN, we can tackle more challenging tasks in the field of graph analysis.

Figure 17: Illustration of human logical derivation.[35]

##  V Graph-Formed Reasoning

###  V-A Tasks Introduction

Graph-formed reasoning refers to combining the graph form with LLMs to obtain
more accurate and reliable answers. LLMs have strong reasoning capabilities,
and many prompting methods are proposed to enhance LLMs’ reasoning abilities,
addressing algorithmic problems, mathematical issues, etc., such as chain of
thought, self-consistency, in-context learning, and more. However, these
methods diverge from the patterns of human thought. The human thought process
is typically non-linear rather than a simple chain of continuous thoughts,
like in Figure 17. Graphs can represent the thinking patterns of individuals
during the thought process. Suppose LLMs can also use graph-formed reasoning
for inference. In that case, they may be able to solve more complex problems,
such as algorithmic problems, logical reasoning problems, and mathematical
word problems, as shown in Figure 16. In this section, we present seven graph-
formed reasoning tasks along with their definitions. Next, we introduce graph-
formed reasoning methods involving two types of reasoning: think on the graph
and verify on the graph.

####  V-A1 Sorting

The problem of sorting involves arranging certain elements in a specific
order. For example, sorting a list of duplicate numbers from 0 to 9 can be
done using a merge-based sorting algorithm. First, the input sequence of
numbers is divided into subarrays. Then, these subarrays are sorted
individually and merged to form the final solution, as shown in Figure 16 (a).

####  V-A2 Set operations

Set operation task mainly focuses on set intersection. Specifically, the
second input set is split into subsets and the intersection of those subsets
with the first input set is determined with the help of the LLM, as shown in
Figure 16 (b).

####  V-A3 Keyword counting

The keyword counting task aims to determine the frequency of specific keywords
within a given category in the input text. The input text is divided into
multiple paragraphs, and the keywords are counted in each paragraph, with the
sub-results aggregated, as shown in Figure 16 (e).

####  V-A4 Document merging

Document merging is the process of generating a new document based on multiple
input documents that have overlapping content sections. The goal is to
minimize duplication as much as possible while preserving the maximum amount
of information, as shown in Figure 16 (c).

####  V-A5 Math word problems

Math word problems include single- and multi-step word problems with addition,
multiplication, subtraction, division and other math topics. LLM requires an
understanding of text and mathematical relationships and involves a multi-step
reasoning process where calculations are performed step by step to arrive at
an answer ultimately, as shown in Figure 16 (d).

####  V-A6 Multi-hop question qnswering

Multi-hop question answering requires LLM to retrieve and integrate
information from multiple text passages or multi-hop graphs to answer
questions. For a complex reasoning question, LLM uses a sophisticated thinking
process to perform reasoning and ultimately arrive at the correct answer, as
shown in Figure 16 (f).

####  V-A7 Logic reasoning

Logical reasoning is a process aimed at concluding rigorously. It occurs in
inference or argumentation, starting from a set of premises and reasoning
towards a conclusion supported by those premises. Propositional logic is the
most fundamental logical system, consisting of p, q, r, and various
operations, as shown in Figure 16 (g).

Task |  Prompts
---|---
Sorting |  <Instruction>Sort the following list of numbers in ascending order. Output only the sorted list of numbers, no additional text. </Instruction><Examples>like Input: [5, 1, 0, 1, 2, 0, 4, 8, 1, 9, 5, 1, 3, 3, 9, 7] Output: [0, 0, 1, 1, 1, 1, 2, 3, 3, 4, 5, 5, 7, 8, 9, 9]</Examples>Input: [input list]
Set Operations |  <Instruction>Find the intersection of two sets of numbers. Output only the set of numbers that are present in both sets, no additional text.</Instruction><Examples>like Input Set 1: [13, 16, 30, 6, 21, 7, 31, 15, 11, 1, 24, 10, 9, 3, 20, 8] Input Set 2: [25, 24, 10, 4, 27, 0, 14, 12, 8, 2, 29, 20, 17, 19, 26, 23] Output: [24, 10, 20, 8] </Examples>Input Set 1: set1 Input Set 2: set2
Keyword Counting |  <Instruction>Count the frequency of how many times each country is explicitly named in the input text. You can generate any intermediate lists and states, but the final output should only contain the frequency of each country that appears at least once in the following json format, prefixed with ”Output: ” (make sure to keep the same spelling for each country in the output as in the input text): {{ ”country1”: frequency1, ”country2”: frequency2, … }} </Instruction><Approach>To count the frequency for each country follow these steps: 1\. Split the input passage into four paragraphs of similar length. 2\. Count the frequency of each country in each paragraph. 3\. Combine the frequencies of each country from each paragraph by adding them together. </Approach><Examples>(Omitted) </Examples>Input: input text
Document Merging |  Merge the following 4 NDA documents <Doc1>\- <Doc4>into a single NDA, maximizing retained information and minimizing redundancy. Output only the created NDA between the tags <Merged>and </Merged>, without any additional text. Here are NDAs: [four documents]
Math word problems |  Q: Janet’s ducks lay 16 eggs per day. She eats three for breakfast every morning and bakes muffins for her friends every day with four. She sells the remainder at the farmers’ market daily for $2 per fresh duck egg. How much in dollars does she make every day at the farmers’ market?
Multi-hop Question Answering |  Question triplets: (’Hypocrite’, directed by, $1), ($1, death date, $2) Question: When did the director of film Hypocrite (Film) die? To answer this question, we answer the following subquestions: (1) Who directed Hypocrite (Film)? The film Hypocrite was directed by Miguel Morayta. (2) When did Miguel Morayta die? Miguel Morayta died on 19 June 2013. So the answer is 19 June 2013.
Logic reasoning |  • Premises: 1\. It is not true that some giant language models do not have good performance. 2\. All language models with good performance are used by some researchers. 3\. If a language model is used by some researchers, it is popular. 4\. If BERT is a giant language model, then GPT-3 is also a giant language model. 5\. BERT is a giant language model. • Hypothesis: GPT-3 is popular. • Label: [True]
TABLE IV: Prompts for Graph-formed Reasoning. Figure 18: Graph-formed
reasoning. Two directions: think on graphs and verify on graphs. Think on the
graph refers to using the graph structure to derive the final conclusion
during the LLMs’ reasoning process. Verify on the graph refers to using the
graph to verify the correctness of the LLMs’ intermediate and final output.

###  V-B Graph-formed Reasoning Methods

The graph form, with its inherent structural features, not only mimics human
reasoning patterns but also validates answers from LLM through the
relationships between nodes and local structure. Existing work can roughly be
divided into two categories: _think on the graph_ and _verify on the graph_ ,
as shown in Figure 18. Think on the graph refers to LLM thinking in the form
of a graph, where each node on the graph represents a step in the thinking
process or an intermediate conclusion during thinking, and the edges on the
graph indicate the direction of LLM inference or the relationships between
intermediate thinking steps. In this way, the LLM thinking process can be
visually represented in graph form. Verify on the graph means verifying the
consistency and correctness of answers by utilizing the graph’s structure. For
example, if the end node of different paths is the same, the results derived
from different paths should be the same. If contradictory conclusions arise,
then the obtained conclusion is incorrect.

####  V-B1 Think on the graph

The GoT* reasoning method [36] is proposed with a two-stage framework to
enable LLM to reason on a graph for answering multiple-choice questions.
Initially, the input query is converted into a graph form, and with the
incorporation of graph and multimodal features, LLM generates rationale. This
rationale updates the graph to a graph with rationales, which is then combined
with the original input and fed into the decoder to obtain the final answer.

However, GoT* allows LLM to enhance the graph using multimodal information but
does not reason step-by-step deduction in graph form. The Graph of Thought
(GoT) [34] represents LLM’s intermediate thinking as an arbitrary graph,
facilitating powerful prompting for solving algorithmic problems like sorting
and keyword counts. LLM thoughts are depicted as vertices in this approach,
with edges representing dependencies between them. By continuously adding LLM
responses to the graph, arbitrary thoughts can be aggregated, forming a
directed acyclic graph.

Multiple LLMs can also be collaboratively harnessed to tackle complex
mathematical challenges, extending beyond the capabilities of a single LLM.
Cumulative Reasoning (CR) [35] is proposed as a more human-like reasoning
process. CR utilizes three LLMs in different roles: the proposer, verifier,
and reporter. The proposer suggests the next step, the verifier checks the
accuracy of the steps, and the reporter decides when the reasoning process
should end. Three roles of LLMs collaborate to achieve more accurate reasoning
processes.

####  V-B2 Verify on the graph

Verify on the graph is to validate the intermediate reasoning results of LLM
to enhance its performance. The Reasoning Graph Verifier (RGV) [83] in this
study assumes a logical connection between the intermediate steps of different
inference paths created by LLM. This allows the multiple solutions generated
by LLM for a reasoning task to be structured into a reasoning graph, aiming to
improve the accuracy and reliability of the outcomes. By constructing
reasoning graphs from the various solutions provided by LLM, a verifier is
trained to determine the correctness of the resulting reasoning graph. During
the prediction phase, RGV assesses the solutions and selects the highest-
scoring one as the final answer.

However, this work trains an extra model to determine whether the graph formed
by the solutions generated by LLM is correct rather than utilizing the
knowledge within the graph and the relationships between the knowledge for
validation. The Graph-guided CoT [84] approach aims to improve the relevance
of rationales generated by CoT during multi-step reasoning. It starts by
extracting triplets from questions using LLM to build a question graph and
generates intermediate sub-questions from this graph. To ensure the rationale
from LLM is logical, Retrieval Augmented Generation (RAG) is used. In an open-
book scenario, knowledge retrieval is based on the sub-questions, providing
retrieved documents and sub-questions as input to LLMs. LLMs generate
rationales for the sub-questions, creating a rationale graph. Based on the
rationale graph, the study assesses whether the generated rationales aid in
solving the original question. By iteratively generating intermediate
rationales, the solution to the original question can be determined.

Finally, we provide manual prompt examples for various graph learning tasks in
Table IV. Additionally, we test LLMs with GPT-4 for sorting and logic
reasoning using manual prompts, as shown in Figure 19.

Figure 19: Examples for Logic Reasoning Task with GPT4 - Graph Reasoning
Tasks.

###  V-C Comparisons and Discussions

Graph-formed reasoning is categorized into think on the graph and verify on
the graph. Think on the graph refers to using the graph structure to derive
the final conclusion during the reasoning process with LLM. On the other hand,
verify on the graph involves treating the intermediate or final results
generated by LLM as nodes on the graph and using the graph to determine if
there are contradictions between the nodes, thus verifying the correctness of
the LLM output.

For “think on the graph”, a common issue with existing approaches is their
lack of convenience. Compared to CoT and SC, the reasoning processes in
current works are complex, requiring multiple stages of reasoning and
validation. Graph of thought methods are not plug and play, which contradicts
the original intent of prompts. Even though using more LLMs can simplify the
reasoning and validation process, it raises the cost and barrier to entry for
reasoning. Therefore, the current challenge is to find a plug-and-play, low-
barrier LLM graph reasoning method that improves LLM reasoning capabilities.

For “verify on the graph”, the current approaches have yet to utilize the
nature of the graph structure for validation. Existing methods either retrain
a model to determine correctness or use a KG for assessment without using the
relationships between nodes to infer whether the conclusions within each node
in the graph are correct.

Therefore, for the “think on the graph,” the future direction could focus on
developing a plug-and-play, low-barrier LLM graph reasoning method that
enhances LLM reasoning abilities, a pressing issue that needs to be addressed.
On the other hand, concerning the “verify on the graph” method, future
research could explore how to utilize the relationships between nodes in the
graph structure to verify the outputs of LLM or the reasoning process itself.

Figure 20: Graph representation. Three types of graph representation are
shown: graph embedding, graph-enhanced text embedding, and graph-encoded
prompts. Graph embedding methods use specific order sequences to represent the
graph. Graph-enhanced text embedding emphasizes incorporating structural
embedding into text embedding. Graph-encoded prompts concentrate on how to
describe a graph in prompts.

##  VI Graph Representation

###  VI-A Tasks Introduction

LLMs’ powerful text representation abilities empower text embeddings to
capture deeper semantic nuances, which also can enhance graph representations,
particularly for Text Attributed Graphs (TAGs). When dealing with structured
text data, the key challenge is integrating graph structures into text
embeddings produced by LLMs to enhance their informativeness or enable LLMs to
process text embeddings with graph structures within the text space. Moreover,
effectively incorporating the graph description within the prompt is essential
for LLMs, especially in closed-source models like ChatGPT, where the embedding
is invisible. How the graph is encoded within the prompt influences the
model’s comprehension of the graph. Thus, we summarize three types of graph
representation: _graph embedding_ , _graph-enhanced text embedding_ , and
_graph-encoded prompts_ , as shown in Figure 20. Next, we introduce graph-
formed reasoning methods corresponding to the above three types.

####  VI-A1 Graph embedding

Graph embedding focuses on transforming a graph into a specific ordered
sequence, which is then fed into an LLM to learn the sequence’s embedding
using their excellent semantic capturing ability and then derive the graph
embedding.

####  VI-A2 Graph-enhanced text embedding

Graph-enhanced text embedding emphasizes incorporating structural embedding
into text embedding. There are two types of embeddings: structural embedding,
which captures the local structure, and text embedding, which captures the
semantic meaning. How to combine these two types of embeddings is the core of
graph-enhanced text embedding.

####  VI-A3 Graph-encoded prompts

Graph-encoded prompts concentrate on how to describe a graph so that LLMs can
understand it more efficiently and then input it into LLMs. For instance, in a
regular graph, the graph can be placed in a story context by assuming that the
relationships between the nodes are friends or colleagues.

With the emergence of LLM, much work has been done on graph representation.
Three goals of the graph representation direction can be identified from the
above three categories: to obtain better graph embeddings as an input into
GNNs, to obtain better text embeddings as an input into LLMs/LMs, and to get
better prompts for graph description as an input into LLMs.

###  VI-B Graph Representation Methods

For the three categories of tasks mentioned above, each type of task has
specific focuses, technical characteristics, and objectives.

####  VI-B1 Graph embedding

Text data is sequential, while graph data is structural, posing a challenge
for LLMs, which excel at handling text but struggle with graphs. How do we
transform graphs into sequences? Graph embedding methods use specific order
sequences to represent the graph, where specific order represents graph
structure. WalkLM [38] aims to enhance graph representations in TAGs by
utilizing a language model. Initially, text sequences are generated on the TAG
through the random walk algorithm, capturing structural features and node
proximity. By incorporating text information from nodes and edges into these
sequences based on the graph structure, the texturing process preserves
component attributes. Subsequently, these sequences are input into a masked
language model for training, where each token represents a node or edge,
leading to improved graph representations and enhanced downstream task
efficiency. Notably, various masked language model options, including LLMs,
are available.

While WalkLM [38] focuses on superior graph embeddings for tasks like node
classification, GraphText [37] transforms graphs into the natural language to
enable LLMs to process graph data in the text domain, leveraging LLMs’
generalization capabilities for graph tasks. GraphText [37] reformulates graph
reasoning as text-to-text problems, establishing text input and output spaces.
GraphText first constructs grammar trees for graphs, then traverses them to
generate graph text sequences, and finally maps the graph to the text space.
The text input is then fed into an LLM, with the LLM results mapped to the
label space, effectively enabling LLMs to handle graph tasks.

####  VI-B2 Graph-enhanced text embedding

Current work focuses on simply passing graph structure information to the LLM
through prompts without deeply learning the graph structure, which can lead to
an LLM’s insufficient understanding of complex structural relationships.

DGTL [39] integrates graph information into text with LLMs for node
classification tasks. It begins by inputting text into a frozen LLM to create
text embeddings from the last layer. Then, a disentangled graph learning
method is employed to extract various structural details and generate
structure embeddings. These structure embeddings are combined with the text
embeddings and fed back into the frozen LLM for node classification. The
entire process is fine-tuned to optimize the disentangled graph learning for
better results.

While DGTL [39] concentrates on utilizing LLMs to integrate text and graph
structure for graph tasks, G2P2 [85] emphasizes merging graph structure with
text to address text classification tasks. Textual data commonly exhibit
network structures, such as hyperlinks in citation networks or purchase
networks, which encapsulate meaningful semantic relationships that can enhance
text classification performance.

G2P2 [85] is proposed to tackle low-resource text classification through a
dual approach. Three graph interaction-based contrastive strategies are
introduced during pre-training to jointly pre-train the graph-text model. In
the downstream classification process, efforts are made to facilitate the
joint pre-trained model in achieving low-resource classification.

####  VI-B3 Graph-encoded prompts

The prompting method is crucial for LLMs to solve tasks. For closed-source
LLMs, the prompt serves as instructions to guide the LLM in understanding and
solving problems. Therefore, effectively encoding graphs in the prompt is
vital for LLMs to comprehend graph structure and solve graph tasks. Graph
encoding refers to how graphs are represented in the prompt.

Talk Like A Graph [86] introduces diverse graph encoding techniques by placing
the same graph in multiple contexts. This strategy highlights how a node,
which may lack intrinsic meaning, can be interpreted differently based on the
context; for instance, a node could represent a person named David, with edges
indicating various relationships like co-authorships or friendships. When
asking LLM the degree of one node, in the given contexts, that equals how many
friendships David has.

In contrast, Talk Like A Graph[86] primarily emphasizes text modality graph
encoding, while Which Modality Should I Use [87] employs three encoding
modalities - text, image, and motif - to encode graphs. The latter method
utilizes different prompt techniques to evaluate the overall connectivity of a
graph, enabling LLMs to handle intricate graph structures more effectively.
Specifically, the text modality encoding provides insights into subgraphs and
their connections at a local level, while the motif modality encoding captures
essential graph patterns like stars, triangles, and cliques, offering a
balanced perspective on local and global information. Moreover, the image
modality encoding delivers a broader view of nodes with limited labels,
effectively utilizing the input context.

In comparing these two methods, Talk Like A Graph[86] focuses on diverse graph
encoding within text modality by constructing contexts, whereas Which Modality
Should I Use [87] utilizes multiple modalities to encode graphs
comprehensively, enhancing the LLMs’ ability to understand graph structures.

###  VI-C Comparisons and Discussions

Graph embedding focuses on transforming a graph into a specific ordered
sequence, which is then fed into an LLM to learn the sequence’s embedding and
derive the graph embedding. On the other hand, graph-enhanced text embedding
emphasizes incorporating structural embedding into text embedding. Lastly,
graph-encoded prompts concentrate on how to describe a graph and input it into
an LLM.

However, due to LLMs’ powerful text representation capabilities, the first two
methods exhibit a deep semantic understanding of graph attributes. However,
they still need suitable structural information capturing, which remains
rudimentary and inadequate. Additionally, aligning the graph structure
features with text features to better represent the graph’s features is a
current issue that needs to be addressed.

For graph-encoded prompts, most methods build a narrative context for the
graph or describe it multimodally before feeding it into an LLM. Both methods
enable the LLM to interpret the graph from various perspectives to improve
performance. The critical challenge currently lies in designing diverse and
easily understandable graph descriptions for LLMs, conveying essential graph
descriptions while enhancing the LLM’s comprehension of the input description.

Figure 21: KG-based augmented retrieval. Knowledge graphs can enhance LLMs to
provide more comprehensive answers.

##  VII Knowledge Graph based Augmented Retrieval

LLMs have shown remarkable reasoning capabilities in challenging tasks,
sparking debates on the potential replacement of Knowledge Graphs (KGs) in
triplet form (subject, predicate, object) by LLMs. Recent LLMs are seen as
viable alternatives to structured knowledge repositories such as KGs,
indicating a shift towards utilizing LLMs for processing real-world factual
knowledge [88][89].

###  VII-A LLMs limitations and comparison with KGs

LLMs, while powerful, face several significant challenges:

  * •

Hallucination is a common issue for LLMs due to a lack of domain-specific
knowledge and knowledge obsolescence, leading to incorrect reasoning and
reduced credibility in critical scenarios like medical diagnosis and legal
judgments [88] [90] [43]. Although some LLMs can explain predictions through
causal chains, they struggle to address hallucination effectively. Integrating
external KGs can help mitigate these problems[41].

  * •

Insufficient domain knowledge hampers LLM performance in specific areas,
including private datasets, necessitating the integration of domain-specific
knowledge graphs to enhance their ability to answer domain-specific questions
[40].

  * •

LLMs struggle with recalling facts when generating knowledge-based content,
despite excelling in learning language patterns and conversing with
humans[89].

  * •

LLMs have limitations in accurately capturing and retrieving foundational
knowledge, hindering their ability to access factual information
effectively[42].

In contrast, KGs like Wikipedia and DBpedia are structured repositories of
rich factual knowledge, providing a more explicit and reliable source of
information compared to the black-box nature of LLMs, as shown in Figure 21.
How do we measure the shortcomings of LLM relative to KG? KGLens is proposed
as an effective method to evaluate the factual accuracy and identify knowledge
gaps in LLMs by assessing the alignment between a KG and LLM[91].

###  VII-B Solutions to LLMs limitations

To address the limitations of LLMs, such as hallucination, insufficient domain
knowledge, etc., integrating LLMs with KGs is a potential way to allow LLMs to
learn knowledge from KGs and enhance their capabilities. The REASONING ON
GRAPHS (RoG) framework[43] synergizes LLMs with KGs for faithful and
interpretable reasoning. Specifically, RoG utilizes a planning retrieval-
reasoning framework where relation paths grounded by KGs are generated as
faithful plans. These plans are then used to retrieve valid reasoning paths
from KGs to facilitate LLMs’ faithful reasoning. Existing work has taken on
the challenges posed by the four main limitations of LLMs through distinct
perspectives, each offering unique solutions.

Addressing the first limitation concerning hallucination issues in LLMs, the
Head to Tail benchmark[88] is introduced to assess LLMs’ reliability in
answering factual questions and to evaluate the probability of hallucination
in generating KG triples. Additionally, it explores whether factors like model
size or instruction tuning can enhance LLM knowledge. Think-on-Graph (ToG)[41]
partially addresses hallucination by involving the LLM agent in iteratively
searching KGs, identifying promising reasoning paths, and providing likely
reasoning outcomes. The second limitation is LLM needs domain-specific
knowledge. To tackle this, GLaM[40] is developed to convert knowledge graphs
into text paired with labeled questions and answers, allowing LLMs to acquire
and respond to domain-specific knowledge. Regarding the third limitation
related to LLMs forgetting facts, integrating KGs with PLMs (KGPLMs)[89] is
introduced to enhance the model’s ability to recall facts compared to
standalone LLMs. This approach emphasizes the competitive and complementary
relationship between LLMs and KGs, where LLMs improve knowledge extraction
accuracy, and KGs guide LLM training to enhance memory and knowledge
application capabilities. Finally, the fourth limitation pertains to LLMs’
challenge in accurately retrieving and returning knowledge from KGs. KGs can
enhance LLM performance by incorporating them during pre-training and
inference stages or to deepen LLM’s understanding of acquired knowledge. Graph
Neural Prompting (GNP)[42] is proposed to augment pre-trained LLMs using
foundational knowledge, such as retrieval-augmented generation, to facilitate
effective learning from KGs. GNP[42] retrieves and encodes relevant, grounded
knowledge to generate Graph Neural Prompts, embedding vectors that provide
guidance and instructions for LLMs.

###  VII-C Other KG + LLMs works

####  VII-C1 KG tasks with LLMs

Moreover, LLMs can enhance KGs to tackle a broader array of challenges. By
leveraging LLMs, KGs can be fortified to perform various KG-related tasks such
as embedding, completion, construction, text generation from graphs, and
question answering[90]. An illustrative example is how LLMs can support KG
tasks such as knowledge graph alignment. In entity alignment tasks between
different knowledge graphs, the objective is to identify pairs of entities
representing the same entity. To address this, AutoAlign[92] facilitates
alignment without the need for expensive manual seed creation. Specifically,
AutoAlign[92] automatically identifies similarities between predicates across
different KGs with the assistance of LLMs.

####  VII-C2 Applications of KGs + LLMs

The combination of KGs and LLMs has other applications as well. For instance,
it can address tasks like multi-document question answering. Knowledge Graph
Prompting (KGP)[93] is introduced to design appropriate context by building
and exploring a knowledge graph. Subsequently, this context guides LLMs for
answering multi-document questions.

###  VII-D Summary

In conjunction with LLMs, the future directions for KGs focus on overcoming
challenges and seizing opportunities in this evolving field. Firstly,
leveraging KGs for Hallucination Detection in LLMs aims to address the issue
of generating inaccurate content. Secondly, utilizing KGs for Editing
Knowledge in LLMs will enable the swift adaptation of internal knowledge to
real-world changes. Moreover, the challenge of injecting knowledge into Black-
box LLMs due to restricted access to internal structures necessitates
innovative approaches. Lastly, integrating Multi-Modal LLMs with KGs can
enrich handling diverse data types within knowledge graphs[90].

Figure 22: Graph-LLM-based applications - Recommendation systems. This shows
LLM for graph data understanding in online job recommendations[46].

##  VIII Graph-LLM-based Applications

Graph-LLM-based applications refer to frameworks that integrate graphs with
LLMs. Apart from their applications in graph-related tasks, they are also
utilized in various other domains (as shown in Figure LABEL:graph-
application), such as conversational understanding and recommendation systems,
as shown in Figure 22. Common frameworks involve combining GNNs with LLMs,
merging graph data with LLMs, and exploring additional innovative approaches
that leverage the advantages between graph structures and language models for
diverse applications.

####  VIII-1 Conversational understanding

By combining LLM with graph traversal, collaborative query rewriting [94] is
proposed to improve the coverage of unseen interactions, addressing the flawed
queries users pose in dialogue systems. Flawed queries often arise due to
ambiguities or inaccuracies in automatic speech recognition and natural
language understanding. When integrated with graph traversal, LLM can
effectively navigate through the graph structure to retrieve relevant
information and provide more accurate responses.

####  VIII-2 Response forecasting

LLM can effectively handle social networks and extract latent personas from
users’ profiles and historical posts. SOCIALSENSE [95] is proposed to utilize
LLMs to extract information to predict the reactions of news media. By
analyzing individuals’ characteristics and behavior patterns within social
networks, LLM can effectively predict the impact of news releases and prevent
unintended adverse outcomes.

####  VIII-3 Multi-domain dialogue state tracking

LLM can learn from multi-domain dialogue history, query, and graph prompts,
enabling it to track dialogue states and generate dialogue content, like SHEGO
[96]. By incorporating information from various sources, such as previous
dialogue exchanges, user queries, and relevant graph prompts, LLM can
understand the conversation’s context and dynamics, allowing LLM to track the
current dialogue state effectively and generate appropriate responses or
dialogue content based on the inputs.

####  VIII-4 Recommendation systems

LLMs can also help address issues in recommendation systems[46], as many tasks
in recommendation systems require learning graph structures, such as user-item
interaction networks. LLMRec[44] aims to enhance recommendation systems by
tackling data sparsity by adopting three simple yet effective LLM-based graph-
enhancement strategies.

####  VIII-5 Graph neural architecture search

LLMs can help address Graph Neural Architecture Search (GNAS). GNAS requires
intensive human effort and rich domain knowledge to design search spaces and
strategies. Leveraging powerful knowledge and reasoning capabilities, LLMs can
identify suitable GNN frameworks within the search space of graph neural
network frameworks. GPT4GNAS[45] integrates GPT-4 into GNAS, introducing a new
set of prompts for GPT-4 to guide it towards generating graph neural
structures.

TABLE V: A summary of LLM-GGA methods with datasets and source links. Method |  Dataset |  LLM | Task | Link
---|---|---|---|---
InstrucGLM[78] |  ogbn-arxiv, Cora, PubMed |  Flan-T5 (instruction-finetune), Llama-v1-7b (LoRA) | Link, Node | code link
GPT4Graph[23] |  ogbn-arxiv,Aminer,Wiki,MetaQA |  InstructGPT-3(frozen) | Reasoning, Node, Graph | code link
LLMtoGraph[24] |  generated by GPTs |  GPT-3.5-turbo, GPT-4, Wizard-Vicuna-13B, 30B-Lazarus-Uncensored-HF | Multi-hop Reasoning | code link
Graph-LLM[73] |  ogbn-arxiv, Cora, PubMed, ogbn-products |  LLaMA, text-ada-embedding-002, Palm-Cortex-001 | Node | code link
TAPE[30] |  ogbn-arxiv, Cora, PubMed, ogbn-products |  GPT-3.5 | Node | code link
LLM4DyG[25] |  LLM4DyG |  GPT-3.5-turbo, Vicuna-7B, Vicuna-13B, Llama-2-13B, CodeLlama-2-13B | Graph | -
GraphGPT[79] |  ogbn-arxiv, Cora, PubMed |  vicuna-7B-v1.1, vicuna-7B-v1.5 | Node | code link
GPPT[80] |  Cora, Reddit, CoraFull, Amazon-CoBuy, ogbn-arxiv etc. |  - | Link, Node | code link
GraphPrompt[81] |  Flickr, PROTEINS, COX2, ENZYMES, BZR |  - | Link, Node, Graph | code link
All in one[82] |  Cora, CiteSeer, Reddit, Amazon, Pubmed |  - | Link, Edge, Node, Graph | code link
Graph-ToolFormer[59] |  GPR, Cora, Pubmed, Citeseer, PROTEINS, MUTAG, NCI1, PTC, Twitter, Foursquare |  GPT-J-6B | Q&A, Reasoning | code link
RGV [83] |  GSM8K, SVAMP, ASDiv-a |  GPT-3.5-turbo | math problems | -
LLM-GNN [72] |  CORA, CITESEER, PUBMED, WIKICS, OGBN-ARXIV, OGBN-PRODUCTS |  GPT-3.5-turbo | Node | code link
Which Modality should I use [87] |  Cora, Citeseer, Pubmed,GraphTMI |  GPT-4, GPT-4V | Representation, Node | -
WalkLM [38] |  PubMed, MIMIC-III, Freebase, FB15K-237 |  PLMs | Representation, Node, Link | code link
GraphText [37] |  Cora, Citeseer, Texas, Wisconsin, Cornell |  Llama-2-7B | Node | code link
TALK LIKE A GRAPH [86] |  GraphQA |  PaLM 2-XXS, PaLM 62B | Node, Link | -
Graph-guided CoT [84] |  2WikiMultihopQA, MusiQue, Bamboogle |  Llama-2-13B,Llama-2-70B | multi-hop question answering | -
NLGraph [27] |  NLGraph |  TEXT-DAVINCI-003, GPT-3.5-TURBO, CODE-DAVINCI-002, GPT-4 | Link,Node,Graph,Path,Pattern | code link
Collaborative Query Rewriting [94] |  opportunity test sets, guardrail test set |  Dolly V2 | Conversational Understanding | -
WHEN AND WHY [26] |  OGBN-ARXIV, CORA, PUBMED, OGBN-PRODUCT, ARXIV-2023 |  ChatGPT | Node | code link
CR [35] |  FOLIO, LogiQA, ProofWriter, LogicalDeduction |  GPT-3.5-turbo, GPT-4, LLaMA-13B, LLaMA-65B | Logic reasoning | code link
SOCIALSENSE [95] |  RFPN, Twitter |  PLMs | Response Forecasting | code link
DGTL [39] |  Cora, PubMed, Books-History |  Llama-2-13B | Node | -
SHEGO [96] |  SGD, MultiWOZ 2.1 |  T5-small | multi-domain DST | -
Graph of Thought(GoT) [34] |  individual data |  GPT3.5(frozen) | Graph-formed reasoning | code link
GLEM[31] |  ogbnarxiv, ogbn-products, ogbn-papers100M |  PLMs | Node | code link
LPNL[77] |  OAG |  T5-base | Link | -
SIMTEG[71] |  OGBN-Arxiv, OGBN-Products, OGBL-Citation2 |  PLMs | Node, link | code link
Llmrec [44] |  Netflix, MovieLens |  gpt-3.5-turbo-16k | Recommendation | code link
ENG[75] |  OGB |  gpt-3.5-turbo | Node generation | -
OFA [32] |  OGBN-ARXIV, CORA |  PLMs | Node, link, graph | code link
G-prompt[33] |  OGBN-ARXIV, Instagram, Reddit |  PLMs | Representation | -
Beyond Text [74] |  OGBN-ARXIV, CORA, PubMed |  GPT-3.5, GPT-4 | Node, link | -
GPT4GNAS[45] |  OGBN-ARXIV, CORA, PubMed, Citeseer |  GPT-4 | Graph neural architecture search | -
Graphllm[64] |  NLGraph |  Llama2-7B, Llama2-13B | Link, node, graph, path, pattern | code link
G2P2 [85] |  Cora, Amazon |  PLMs | Representation | code link
ChatGraph[97] |  Gradio |  GPT-4V, Next-GPT | Link, node, graph, application | -
Graph Agent[76] |  Cora, PubMed |  GPT-4 | Link, node, graph | -
GoT*[36] |  AQUA-RAT, ScienceQA |  T5-base | Graph-formed reasoning | code link
KGP[93] |  HotpotQA, IIRC, 2WikiMQA, MuSiQue, PDFTriage, Rank |  Llama | KG+LLM | code link
Head-to-Tail [88] |  DBpredia, Movie, Book, Academics |  GPT-4 | KG+LLM | -
GLaM[40] |  DBLP, UMLS |  Llama-7B | KG+LLM | -
ToG[41] |  CWQ, WebQSP, GrailQA, QALD10-en, etc. |  GPT-3.5, GPT-4, Llama-2 | KG+LLM | code link
Autoalign[92] |  DBpedia, Wikidata |  ChatGPT, Claude | KG+LLM | code link
GNP[42] |  ConceptNet, UMLS, OpenBookQA, etc. |  FLAN-T5 xlarge (3B), xxlarge (11B) | KG+LLM | code link
RoG[43] |  WebQSP, CWQ, Freebase |  LLaMA2-7B | KG+LLM | code link
KGLens[91] |  Wikidata |  GPT-3.5-turbo, GPT-4, Babbage-002, Davinci-002, Vicuna-33b-v1.3, Xwin-LM-13B-V0.2, Yi-34B-Chat | KG+LLM | -
TABLE VI:  A summary of new datasets. New Benchmark | Link
---|---
GPR [59] | https://github.com/jwzhanggy/Graph_Toolformer/tree/main/data
GraphTMI [87] | To be released
LLM4DyG [25] | To be released
GraphQA [86] | To be released
NLGraph [27] | https://github.com/Arthur-Heng/NLGraph/tree/main/NLGraph
GraphextQA [98] | https://huggingface.co/datasets/drt/graphext-qa
CS-TAG [99] | https://github.com/sktsherlock/TAG-Benchmark

##  IX Benchmark Datasets and Evaluations

In this section, we summarize benchmark datasets and evaluation metrics for
LLMs.

###  IX-A Datasets

This paper summarizes the popular and new datasets, the LLM employed, the
performed tasks, and the links to the open-source code in the LLM-GGA area, as
illustrated in Table V. Below, we introduce commonly used benchmarks and the
new benchmarks proposed for the LLM-GGA field.

####  IX-A1 Popular datasets

Popular benchmark refers to a graph benchmark that is widely and frequently
used. We have systematically categorized these popular benchmarks according to
six directions, detailing which benchmarks are used for each direction. Below
are listed popular benchmarks commonly used in the six directions.

  * •

Graph structure understanding: ogbn-arxiv[56], ogbn-products[56], Cora[100],
CiteSeer[101], Aminer(DBLP)[57], MetaQA[102], Wikidata5M[103], PROTEINS [104],
MUTAG[105], NCI1[106], PTC[107], Foursqure [108].

  * •

Graph learning: ogbn-arxiv[56], ogbn-products[56], ogb-papers110M[56], ogb-
citation2[56], Cora[100], CiteSeer[101], Amazon-items[109], PubMed[110],
Reddit[111], CoraFull [112], Amazon[113], PROTEINS [104], COX2 [114], BZR
[114], OAG [115]

  * •

Graph-formed reasoning: GSM8K [116], SVAMP[117], FOLIO[118]

  * •

Graph representation: Cora[100], CiteSeer[101], Goodreads-books[119],
PubMed[110], Amazon[113], MIMIIC-III [120], Freebase [121], FB15K-237 [122]

  * •

KG-based augmented retrieval: CWQ[123], WebQSP[124], Wikidata[103]

  * •

Graph-LLM-based applications: depending on specific applications.

####  IX-A2 New datasets

More than existing datasets are needed to explore LLMs’ ability to understand
graph structures and their potential to solve graph problems better. As a
result, many works have proposed new benchmarks to advance research in this
field, as shown in Table VI.

  * •

GPR [59] contains 37 particular connected graph instances generated by the
Networkx toolkit, which include the “bull graph,” “wheel graph,” “lollipop
graph,” etc. These generated graph instances are relatively small, with about
15 nodes and 28 links on average.

  * •

GraphTMI [87] is a graph benchmark featuring a hierarchy of graphs, associated
prompts, and encoding modalities. Different graph task difficulty depends on
the dual criteria of 1) count of motifs and 2) homophily in the graph, which
yields a dataset of EASY, MEDIUM, and HARD graph problems.

  * •

LLM4DyG [25] benchmark is to evaluate whether LLMs are capable of
understanding spatial-temporal information on the dynamic graph. Nine dynamic
graph tasks are designed to assess LLMs’ abilities considering spatial and
temporal dimensions.

  * •

GraphQA [86] comprises a set of diverse fundamental graph problems with more
varied and realistic graph structures compared to previous studies in LLM
research. GraphQA is designed to measure the performance of LLMs in graph data
reasoning.

  * •

NLGraph [27] benchmark is to examine whether language models can reason with
graphs and structures. NLGraph contains eight graph structure understanding
tasks with varying algorithmic difficulties. Depending on different network
sizes, graph sparsity, and more, NLGraph results in easy, medium, and hard
subsets in each graph reasoning task to enable difficulty scaling and fine-
grained analysis.

  * •

GraphextQA [98] benchmark is a dataset for open domain question answering. It
includes paired subgraphs used to develop and evaluate graph language models.
The subgraphs are retrieved from Wikidata and contain reasoning paths from
entities mentioned in the questions to the entities that the questions are
asking about.

  * •

CS-TAG [99] benchmark is a comprehensive and wide-ranging compilation of
benchmark datasets for TAGs. This dataset encompasses a variety of challenging
scenarios, ranging from citation networks to purchase graphs. The collection
consists of eight distinct TAGs sourced from diverse domains.

We also list which directions these new benchmarks are typically used for. For
graph structure understanding, GPR[59], GraphTMI[87], LLM4DyG[25],
NLGraph[27], and CS-TAG[99]can be used. For graph learning, CS-TAG[99] can be
used. For graph-formed reasoning, GraphextQA[98] can be used. For graph
representation, GraphTMI[87], GraphQA[86], and CS-TAG[99] can be used. For KG-
based augmented retrieval, GraphextQA[98] can be used.

TABLE VII:  Evaluations. Tasks |  Metrics
---|---
Graph structure understanding task |  Accuracy, ROUGE, BLEU, Time cost, Comprehension, Correctness, Fidelity, Rectification Comprehension
Graph learning task |  Accuracy, Macro-F1, Training Time, Tuned Parameters, GPU Occupy, Mismatch Rate, Denial Rate, Token Limit Fraction
Graph resoning task |  Accuracy, F1-score, Precision, Recall, The Latency-Volume Trade-off, Number of errors and cost
Graph representation |  depending on downstream tasks
KG-based augmented retrieval |  Accuracy, F1-score, Precision, Recall,
Graph-LLM-based applications |  depending on different tasks

###  IX-B Evaluations

Evaluating the results of different tasks related to LLM-GGA is also a
critical issue. Thus, selecting evaluation metrics to assess the results is
essential to determining how well LLMs perform their understanding of graphs
and how effectively models combining graphs and LLMs perform on various tasks
is vital. This section summarizes the metrics of different tasks, shown as
Table IX-B. Note that all test results related to LLMs in this paper are
conducted using GPT-3.5 turbo or GPT-4 turbo.

####  IX-B1 Graph structure understanding task.

Several metrics are usually used in graph structure understanding tasks:
accuracy, ROUGE[125], BLEU[126], Time cost, comprehension, correctness,
fidelity, and rectification comprehension. Accuracy, ROUGE, BLEU, and time
cost are viral metrics. Meanwhile, comprehension, correctness, fidelity, and
rectification comprehension are new metrics [24] used to evaluate the ability
of LLMs to understand graphs through natural language, the accuracy of solving
graph problems, and the level of confidence in the answers provided.

####  IX-B2 Graph learning task.

For graph learning tasks, when evaluating a model, various metrics are
considered to determine its effectiveness, efficiency, and computational
demands. When assessing the effectiveness of a model, metrics such as
accuracy, macro-F1, mismatch rate, and denial rate[87] are considered. In
terms of efficiency, metrics like training time and tuned parameters are
assessed. For computational costs, metrics such as GPU occupancy and token
limit fraction are examined. Notably, the token limit fraction indicates the
proportion of tokens used compared to the maximum allowed by the model’s
constraints and can be formed as follows:

$\mathrm{T}=\frac{\mathrm{Number\ of\ usage\ tokens}}{\mathrm{Token\ limit\
constraint\ for\ the\ model}}$ (6)

####  IX-B3 Graph reasoning task.

When it comes to graph reasoning tasks, two main factors that are taken into
consideration are effectiveness and efficiency. Several metrics are used to
assess effectiveness, including accuracy, number of errors and cost, F1-score,
precision, and recall[127]. On the other hand, efficiency is evaluated through
metrics such as the Latency-Volume Trade-off.

####  IX-B4 Graph representation.

The effectiveness of graph representation is typically judged based on the
performance of downstream tasks that use this graph representation.

####  IX-B5 Knowledge graph-based augmented retrieval.

Tasks in the KG-based augmented retrieval direction typically involve
question-answering tasks. Evaluation metrics commonly used include accuracy,
precision, recall, F1-score, Hits@k[128], EM[129], MSE, and for some
generative tasks, human evaluation may also be utilized.

##  X Future Directions

The above survey of the state-of-the-art LLM-GGA research reveals a promising
and young research field. The following section discusses exciting directions
for future work.

###  X-A More Complex Graph Problems

More complex graph tasks. Can LLMs solve graph algorithm problems? Existing
works on traditional graph tasks are based on fundamental graph problems such
as shortest path, clustering coefficient computing, maximum flow, etc.
However, can LLMs address NP problems such as community search, interactive
graph problems, or even NP-hard problems, and if so, how can they tackle them?
For graph learning tasks, current research primarily focuses on simple node,
edge, and graph classification. Future work can focus on more complex graph
learning problems, such as the diverse classification outcomes arising from
isomorphic and heterogeneous graphs.

More complex graph patterns. Graphs contain various graph patterns, each with
its explicit definition and unique characteristics, such as stars, triangles,
cliques, butterflies, and more. Therefore, recognizing graph patterns and
utilizing their characteristics to solve downstream tasks can be highly
advantageous. Currently, only limited works leverage the properties of stars,
triangles, and cliques to solve problems.

Furthermore, understanding graph data still remains a significant challenge
for existing LLMs, limiting their ability to tackle more complex graph
problems. Therefore, incorporating LLMs into the process is a promising
direction for solving more complex graph problems.

###  X-B LLM Exploration on Diverse Graphs

Most existing work mainly focuses on static graphs, while there exists a wide
range of different graphs, including undirected, directed, cyclic, acyclic,
isomorphic, heterogeneous, dynamic, etc. Different types of graphs have
significant structural differences, such as static graphs, dynamic graphs,
temporal graphs, uncertain graphs, heterogeneous graphs, etc. Specifically,
unlike static graphs, dynamic graphs can be represented as ordered lists or
asynchronous streams of timed events, capturing patterns of temporal network
evolution, such as the addition or removal of nodes and edges. Evaluating the
ability of LLMs to understand the spatio-temporal information of dynamic
graphs is crucial for web applications. Evaluating whether LLMs can determine
when nodes are connected, identify which nodes are connected to a given node
at a specific time, and find a chronological path by combining temporal and
spatial information is essential to assessing LLMs’ understanding of dynamic
graphs. Future work can further explore other types of graphs, such as dynamic
graphs and temporal graphs, address problems like maximum flow, and predict
the evolution of graphs.

Moreover, existing studies have conflicting views on the LLM graph reasoning
ability, with some presenting contradictory findings. This ambiguity could be
due to various factors, including dataset selection, diverse prompt
engineering techniques, the range of graph reasoning tasks, and the
utilization of different LLM models.

###  X-C Better LLM-GNN Pipelines

GNNs are designed to handle structural information by continuously learning
information from surrounding subgraphs through aggregation functions. On the
other hand, LLMs excel in processing textual information, text reasoning,
semantic understanding, and more. The challenge lies in leveraging both
advantages to enable a pipeline that can effectively handle both attributed
and pure graphs. If GNNs and LLMs are simply stacked, the parameter size of
GNNs is notably smaller than that of LLMs. This discrepancy may result in the
issue of vanishing gradients during training, as mentioned in [130], which can
impede the iterative updating process of GNNs. Additionally, GNNs need to
utilize the extensive knowledge contained within LLMs fully, and they cannot
effectively extract specific knowledge tailored for specific downstream tasks
in different graphs.

###  X-D Graph Foundation Model

LLM is undoubtedly the foundational model in NLP. Can we draw inspiration from
LLMs to train a graph foundation model? For example, can training strategies
like instruction tuning and DPO be applied to tasks involving graphs? The
current research has primarily introduced graph foundation models in the form
of LLM-GNN pipelines and graph-aware tuning LLMs. Future endeavors can focus
on exploring graph foundation models better suited for tasks involving graphs.

###  X-E Better Graph Prompts

Most graph prompts are currently designed based on GNNs, with only a few works
focusing on LLMs. Graph prompts for LLMs have yet to be sufficiently explored.

Graph Prompt for GNNs. The typical approach uses simple concatenation,
addition, or dot product operations with trainable parameters. Some existing
works have considered more complex fusion methods, such as [82], which assumes
the structural features of graph prompts. However, compared to the combination
of prompts and pretexts, the variety of graph prompts and pre-graphs is still
in the exploratory stage.

Graph-enhanced Prompts for LLMs. Relying solely on manual prompts and self-
prompting has limited capabilities in improving model performance, as they
only explore the existing abilities of LLM. As shown in Section III-C, LLMs
can be trained as agents to utilize tools for graph tasks that are hard to
solve, like API call prompt[59]. GoT [130] is also a graph reasoning paradigm
that enables LLMs to provide correct answers. Future work based on the graph
reasoning paradigm can consider cost-effective approaches for GoT, such as
pruning and tricks to reduce algorithm complexity. In the future, it would be
beneficial to explore simpler GoT paradigms that can improve the effectiveness
of LLMs.

###  X-F Modal Alignment

Modal alignment refers to the alignment between two modalities: text and
graph. The input for LLMs is typically sequential data, often text. Graph and
text are two different modalities, and studying the alignment between these
two modalities for LLMs involves finding a shared mapping feature space for
graphs and text. The shared mapping space allows LLMs to understand graph data
similarly to how they know textual information if they comprehend text.

###  X-G Explainabilily

GNNs are currently widely used for solving complex graph problems. However,
they need more interpretability, which hinders their practical application. On
the other hand, LLMs possess reasoning capabilities and have succeeded in
various natural language processing tasks. The combination of LLMs and GNNs
has the potential to offer a more transparent approach to solving graph
problems by leveraging the reasoning abilities of LLMs. If the combination of
LLMs and GNNs is interpretable, it can be utilized for various tasks.,
including recommendation systems, drug discovery, and fraud detection. This
combination can lead to the development of more reliable and efficient
decision-making systems across various domains.

###  X-H Efficiency on Large-scale Graphs

Due to the limited input length of LLM, the graph sizes inputted through
prompts typically consist of dozens of nodes. However, for large graphs with
tens of thousands of nodes and edges, how can LLMs with limited input length
solve such large graphs? A larger input window is required in the case of
attributed graphs, where both node and edge attributes need to be considered
along with the graph structure. How does LLM address this case? There are
currently few effective methods to enable LLM to handle them.

##  XI Conclusions

LLM-GGA has emerged as a promising field that has garnered significant
attention from researchers. This paper introduces a comprehensive structural
taxonomy based on recent research, which classifies LLM-GGA research into
three main directions: LLM-GQP, LLM-GIL, and graph-LLM-based applications.
LLM-GQP encompasses graph understanding and KG-based augmented retrieval,
while LLM-GIL involves graph learning, graph-formed reasoning, and graph
representation. The motivation, challenges, and mainstream methods of each
direction are thoroughly examined.

For the six mentioned directions, a comparison of various methods was
conducted to explore their potential in each area. It is observed that LLM
shows preliminary capabilities in structural understanding, addressing issues
like maximum flow and bipartite graph matching over small graphs. However, it
is susceptible to factors such as node degree and graph density, leading to
potential misjudgments in graph connectivity. Additionally, LLM proves
beneficial for graph learning tasks due to its strong semantic understanding
and reasoning abilities, coupled with learning from extensive corpora, which
can provide external knowledge to GNNs and aid in semantic information
comprehension, learning, and reasoning. Thanks to LLM’s semantic understanding
capabilities, graph representation can achieve deeper semantic embeddings. The
discussion also delves into KG-based augmented retrieval to enhance LLMs
retrieval and factual knowledge-answering abilities. The paper summarizes over
40 datasets, evaluation metrics for six directions, and source code for over
30 mainstream methods in these directions. It highlights the existing
challenges in current methods and proposes future directions to guide and
motivate further research in the LLM-GGA field.

## References

  * [1] J. Wei, M. Bosma, V. Y. Zhao, K. Guu, A. W. Yu, B. Lester, N. Du, A. M. Dai, and Q. V. Le, “Finetuned Language Models Are Zero-Shot Learners,” Feb. 2022, arXiv:2109.01652 [cs]. [Online]. Available: http://arxiv.org/abs/2109.01652
  * [2] B. Peng, C. Li, P. He, M. Galley, and J. Gao, “Instruction Tuning with GPT-4,” Apr. 2023, arXiv:2304.03277 [cs]. [Online]. Available: http://arxiv.org/abs/2304.03277
  * [3] R. Rafailov, A. Sharma, E. Mitchell, C. D. Manning, S. Ermon, and C. Finn, “Direct preference optimization: Your language model is secretly a reward model,” in _Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023_ , A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, Eds., 2023. [Online]. Available: http://papers.nips.cc/paper_files/paper/2023/hash/a85b405ed65c6477a4fe8302b5e06ce7-Abstract-Conference.html
  * [4] L. Sun, Y. Huang, H. Wang, S. Wu, Q. Zhang, Y. Li, C. Gao, Y. Huang, W. Lyu, Y. Zhang, X. Li, Z. Liu, Y. Liu, Y. Wang, Z. Zhang, B. Vidgen, B. Kailkhura, C. Xiong, C. Xiao, C. Li, E. Xing, F. Huang, H. Liu, H. Ji, H. Wang, H. Zhang, H. Yao, M. Kellis, M. Zitnik, M. Jiang, M. Bansal, J. Zou, J. Pei, J. Liu, J. Gao, J. Han, J. Zhao, J. Tang, J. Wang, J. Vanschoren, J. Mitchell, K. Shu, K. Xu, K.-W. Chang, L. He, L. Huang, M. Backes, N. Z. Gong, P. S. Yu, P.-Y. Chen, Q. Gu, R. Xu, R. Ying, S. Ji, S. Jana, T. Chen, T. Liu, T. Zhou, W. Wang, X. Li, X. Zhang, X. Wang, X. Xie, X. Chen, X. Wang, Y. Liu, Y. Ye, Y. Cao, Y. Chen, and Y. Zhao, “TrustLLM: Trustworthiness in Large Language Models,” Mar. 2024, arXiv:2401.05561 [cs]. [Online]. Available: http://arxiv.org/abs/2401.05561
  * [5] H. Touvron, L. Martin, K. Stone, P. Albert, A. Almahairi, Y. Babaei, N. Bashlykov, S. Batra, P. Bhargava, S. Bhosale, D. Bikel, L. Blecher, C. Canton-Ferrer, M. Chen, G. Cucurull, D. Esiobu, J. Fernandes, J. Fu, W. Fu, B. Fuller, C. Gao, V. Goswami, N. Goyal, A. Hartshorn, S. Hosseini, R. Hou, H. Inan, M. Kardas, V. Kerkez, M. Khabsa, I. Kloumann, A. Korenev, P. S. Koura, M. Lachaux, T. Lavril, J. Lee, D. Liskovich, Y. Lu, Y. Mao, X. Martinet, T. Mihaylov, P. Mishra, I. Molybog, Y. Nie, A. Poulton, J. Reizenstein, R. Rungta, K. Saladi, A. Schelten, R. Silva, E. M. Smith, R. Subramanian, X. E. Tan, B. Tang, R. Taylor, A. Williams, J. X. Kuan, P. Xu, Z. Yan, I. Zarov, Y. Zhang, A. Fan, M. Kambadur, S. Narang, A. Rodriguez, R. Stojnic, S. Edunov, and T. Scialom, “Llama 2: Open foundation and fine-tuned chat models,” _CoRR_ , vol. abs/2307.09288, 2023. [Online]. Available: https://doi.org/10.48550/arXiv.2307.09288
  * [6] L. Ouyang, J. Wu, X. Jiang, D. Almeida, C. L. Wainwright, P. Mishkin, C. Zhang, S. Agarwal, K. Slama, A. Ray, J. Schulman, J. Hilton, F. Kelton, L. Miller, M. Simens, A. Askell, P. Welinder, P. F. Christiano, J. Leike, and R. Lowe, “Training language models to follow instructions with human feedback,” in _Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022_ , S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, Eds., 2022. [Online]. Available: http://papers.nips.cc/paper_files/paper/2022/hash/b1efde53be364a73914f58805a001731-Abstract-Conference.html
  * [7] Y. Zhuang, Y. Yu, K. Wang, H. Sun, and C. Zhang, “Toolqa: A dataset for LLM question answering with external tools,” in _Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023_ , A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, Eds., 2023. [Online]. Available: http://papers.nips.cc/paper_files/paper/2023/hash/9cb2a7495900f8b602cb10159246a016-Abstract-Datasets_and_Benchmarks.html
  * [8] Z. Li, S. Fan, Y. Gu, X. Li, Z. Duan, B. Dong, N. Liu, and J. Wang, “Flexkbqa: A flexible llm-powered framework for few-shot knowledge base question answering,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 38, no. 17, 2024, pp. 18 608–18 616.
  * [9] B. Zhang, B. Haddow, and A. Birch, “Prompting large language model for machine translation: A case study,” in _International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA_ , ser. Proceedings of Machine Learning Research, A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett, Eds., vol. 202. PMLR, 2023, pp. 41 092–41 110. [Online]. Available: https://proceedings.mlr.press/v202/zhang23m.html
  * [10] J. Liu, C. S. Xia, Y. Wang, and L. Zhang, “Is your code generated by chatgpt really correct? rigorous evaluation of large language models for code generation,” in _Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023_ , A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, Eds., 2023. [Online]. Available: http://papers.nips.cc/paper_files/paper/2023/hash/43e9d647ccd3e4b7b5baab53f0368686-Abstract-Conference.html
  * [11] A. Ni, S. Iyer, D. Radev, V. Stoyanov, W. Yih, S. I. Wang, and X. V. Lin, “LEVER: learning to verify language-to-code generation with execution,” in _International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA_ , ser. Proceedings of Machine Learning Research, A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett, Eds., vol. 202. PMLR, 2023, pp. 26 106–26 128. [Online]. Available: https://proceedings.mlr.press/v202/ni23b.html
  * [12] P. Sen, G. Namata, M. Bilgic, L. Getoor, B. Gallagher, and T. Eliassi‐Rad, “Collective Classification in Network Data,” _AI Magazine_ , vol. 29, no. 3, pp. 93–106, Sep. 2008. [Online]. Available: https://onlinelibrary.wiley.com/doi/10.1609/aimag.v29i3.2157