# Which Modality should I use - Text, Motif, or Image? : Understanding Graphs
with Large Language Models

Debarati Das Ishaan Gupta Jaideep Srivastava Dongyeop Kang
Department of Computer Science, University of Minnesota
{das00015, gupta737, srivasta<EMAIL_ADDRESS>

###### Abstract

Large language models (LLMs) are revolutionizing various fields by leveraging
large text corpora for context-aware intelligence. Due to the context size,
however, encoding an entire graph with LLMs is fundamentally limited. This
paper explores how to integrate graph data with LLMs better and presents a
novel approach using various encoding modalities (e.g., text, image, and
motif) and approximation of global connectivity of a graph using different
prompting methods to enhance LLMs’ effectiveness in handling complex graph
structures. The study also introduces GraphTMI, a new benchmark for evaluating
LLMs in graph structure analysis, focusing on factors such as homophily, motif
presence, and graph difficulty. Key findings reveal that image modality,
supported by advanced vision-language models like GPT-4V, is more effective
than text in managing token limits while retaining critical information. The
research also examines the influence of different factors on each encoding
modality’s performance. This study highlights the current limitations and
charts future directions for LLMs in graph understanding and reasoning tasks.

##  1 Introduction

Large Language Models (LLMs) have expanded their utility beyond traditional
language processing, becoming increasingly valuable in robotics, planning, and
reasoning Huang and Chang (2022); Andreas (2022); Madaan et al. (2022). Their
versatility has extended to domains with inherent graph structures, such as
social network analysis Mislove et al. (2007), drug discovery Vishveshwara et
al. (2002), and recommendation systems Melville and Sindhwani (2010). However,
despite their success, LLMs are hindered by a dependence on unstructured text,
leading to issues like hallucination or logical oversights Zhang et al.
(2023). This limitation and the challenge of incorporating new, post-training
data Lewis et al. (2020) about the world’s changing state can be addressed
using graph-structured external data Pan et al. (2023).

Figure 1: Input modality encoding for graphs impacts node classification, with
text modality offering detailed information from a local point of view but
violating the input context limitations for LLMs due to verbosity. Motif
encoding provides local and global context, while image modality gives a
comprehensive global view, efficiently processed by GPT-4V, which integrates
capabilities from both vision and text.

While strides have been made in interpreting multi-modal information Yin et
al. (2023), integrating graph understanding in LLMs is still an emerging
exploration. Specifically, LLMs need help to handle complex graph-structured
data that cannot be directly ingested as an input. Therefore, designing an
efficient input encoding and appropriate prompts for different graph tasks is
an interesting problem explored by recent papers Fatemi et al. (2023); Chen et
al. (2023). However, these papers use a constrained experimental setup, where
the real-world graph size is either limited by heuristic constraints (e.g.,
number of nodes) Guo et al. (2023) or synthetic graphs are constructed Wang et
al. (2023) to verify their experiments. Real-world graphs are too large to be
fed as input because of the context window limitations of LLMs. This research
gap motivates us to think about other possible encoding modalities or
approximation methods that can provide graphs as input to LLMS.

In this paper, we explore the impact of encoding global and local graph
structures using different modalities, particularly focusing on node
classification tasks. In specific, we compare three modalities: Text, Motif,
and Image (See Figure 1). Text modality encoding provides a detailed local
perspective of the subgraph and its connections. However, it becomes too
verbose for large graphs, potentially exceeding the input context limits of
large language models like GPT-4 Bubeck et al. (2023). To circumvent this, we
suggest Motif modality encoding, which captures essential patterns within the
node’s vicinity, offering a balanced local and global perspective. Finally, we
propose image modality encoding as an alternative, potentially superior to
text, due to its ability to convey a more global view of the node’s
neighborhood with fewer tokens, making efficient use of the input context.
GPT-4V OpenAI (2023a), a recently released, vision-capable iteration of GPT-4,
facilitates this approach. We evaluate all three encoding modalities for the
task of node classification using a combination of four metrics (accuracy
rate, mismatch rate, denial rate, and token limit fraction), which together
capture the tradeoff between an informative yet not verbose prompt.

Main contributions:

  * •

We conduct a comprehensive breadth-first analysis of graph-structure prompting
in different modalities, including text, image, and motif, using large
language and vision-language models for node classification tasks.

  * •

We also conduct a depth-first analysis of how different factors influence the
performance of each encoding modality.

  * •

We introduce GraphTMI, a novel graph benchmark featuring a hierarchy of
graphs, associated prompts, and encoding modalities designed to further the
community’s understanding of graph structure effects using LLMs.

Some key findings: 1) The image modality is better suited than the text
modality for graphs when the need is to balance a token limit constraint while
retaining important information. 2) Graph task difficulty based on homophily
and motif counts is a factor in deciding which encoding modality to use for
classification. 3) Factors like edge encoding function, graph structure, and
graph sampling techniques impact the performance of node classification using
text modality. 4) Motif attachment information has a more significant impact
on node classification than motif count information. 5) Improving image
representation impacts the performance of node classification using image
modality.

Our empirical results show that, while LLMs are getting better at handling
graph data, they still have to improve to catch up with GNN models that work
with real-world graphs. Through our study, we uncover current limitations and
future directions of LLMs equipped with image understanding in comprehending
graphs and performing associated reasoning tasks.

Figure 2: Node Classification on a Graph using different input modality
encodings like Text, Motif, and Image.

##  2 Proposed Methods

Graph encoding is necessary for turning graph-structured information into a
sequence for consumption by language models. Figure 2 describes our experiment
setup, where the modality encoder inputs the graph structure and a graph query
(for node classification, the query would be “Predict the label of the node
marked with $?$”). Depending on the modality chosen (for text and motif
modality, we choose GPT-4; for image modality, we choose GPT-4V), we encode
the graph structure appropriately and pass it as a prompt to the LLM,
generating the desired label.

###  2.1 Text Encoding Modality

Encoding graphs as text can be separated into two key parts: First, the
mapping of nodes to their corresponding labels in the graph, and second, the
encoding of edges between the nodes. We encode the node-to-label mapping as a
dictionary of type {node ID: node label}. Edge encoding representations have
been explored in recent works Guo et al. (2023); Fatemi et al. (2023). Text
encodings of graphs provide the LLM, GPT-4 OpenAI (2023a), with the local
context of the labeled node in the form of individual edge connections and
node label information. As the size of the graph increases, these text
encodings can get quite verbose, add to confusion, and violate the input
context window of the LLMs. Therefore, finding a suitable, informative, yet
compressed representation of the graph structure or edge representation
becomes imperative. We consider the importance of some factors that can
influence the performance of text modality encoding:

Edge Encoding Function: Motivated by recent works Fatemi et al. (2023); Guo et
al. (2023) describing the importance of selecting the appropriate text
encoding for a graph, we experiment with different edge representations on
real-world datasets and evaluate the metrics for node classification. Graph
Structure: Recent work Yasir et al. (2023); Palowitch et al. (2022) explores
the impact of graph structure on graph reasoning tasks. We selected real-world
citation datasets with differing network properties to explore the
significance of graph structure on node classification.

Sampling Strategy: Graph sampling methods are crucial for graph reasoning with
Large Language Models (LLMs) due to context window limitations and the complex
nature of real-world graphs Wei and Hu (2022). Two methods, Ego graph Stolz
and Schlereth (2021) and Forest Fire sampling Leskovec and Faloutsos (2006),
offer distinct perspectives. Ego graph sampling focuses on a central node and
its immediate neighbors, creating a subgraph that reflects their connections.
On the other hand, Forest Fire sampling starts from a random node and expands
outwards, resulting in subgraphs that vary in size and local structure,
influenced by parameters like burning probabilities.

An example prompt generated after applying the text encoding modality looks
like:

Task: Node Label Prediction (Predict the label of the node marked with a ?)
given the adjacency list information as a dictionary of type “node:
neighborhood” and node-label mapping in the text enclosed in triple backticks.
Response should be in the format “Label of Node = <predicted label>”. If the
predicted label cannot be determined, return “Label of Node = -1”.
```AdjList: {1: [2,3], 2: [3,4], 3: [1,2]}
Node-Label Mapping: {1: A, 2: B, 3: ?} ```

###  2.2 Motif Modality

In networks, significant repeating patterns, or “motifs”, act as functional
building blocks, revealing local structures and group behaviors in social and
biological networks Milo et al. (2002); Carrington et al. (2005); Holland and
Leinhardt (1974). The intuition behind the motif modality encoding is to
provide the LLM with a local and global context of the graph structure by
giving it, as input, the significant patterns around the vicinity of the
unlabeled node, which could aid in its classification Yang et al. (2018).

Encoding graphs as motifs can be separated into two key parts: First, the
encoding of nodes to their corresponding labels in the graph, and second, the
motifs present around the $?$ (unlabeled) node. We encode the node-to-label
mapping as a dictionary of type {node ID: node label}. we calculate motifs in
the neighborhood of the $?$ nodes and pass this information to GPT-4 OpenAI
(2023a) as the graph-motif information. We consider the importance of
different network motifs, such as the count and presence of star motifs,
triangle motifs, and clique information Felmlee et al. (2021) that can
influence the performance of the motif modality encoding.

An example prompt generated after applying the motif encoding modality looks
like:

Task: Node Label Prediction (Predict the label of the node marked with a $?$)
given the node-label mapping and graph motif information in the text enclosed
in triple backticks. Response should be in the format “Label of Node =
<predicted label>”. If the predicted label cannot be determined, return “Label
of Node = -1”.
```Node-Label Mapping: {1: A, 2: A, 3: ?}
Graph-motif information: No of triangles: 1| Triangles attached to $?$ Node :
[1,2,3]| ```

###  2.3 Image Modality

This modality is inspired by the saying that “a picture is worth a thousand
words.” Images, offering a rich and complex data representation, can convey
intricate structures more efficiently than text. They can express complex
networks, labels, spatial relationships, and non-verbal cues (like visually
emphasizing key nodes) in fewer tokens than images. We use VLMs like GPT-4V
OpenAI (2023b) to process graph images to give LLMs a global perspective of
graph structural information. GPT-4V, a multimodal model, interprets various
visuals by leveraging its language skills. Enhancing a graph’s image
representation is crucial for improving its node classification performance in
the image modality.

An example prompt generated after applying the image encoding modality looks
like this:

Task: Node Label Prediction (Predict the label of the red node marked with a
?, given the graph structure information in the image). Response should be in
the format "Label of Node = <predicted label>." If the predicted label cannot
be determined, return "Label of Node = -1

##  3 Data and Experimental Setup

###  3.1 Seed Datasets

We experiment with three citation network datasets, which are popular node
classification benchmarks, CORA McCallum et al. (2000) with seven categories :
[0-Rule Learning, 1-Neural Networks, 2-Case-Based, 3-Genetic Algorithms,
4-Theory, 5-Reinforcement Learning, and 6-Probabilistic Methods], CITESEER
Giles et al. (1998) with six categories of areas in Computer Science:
[0-Agents, 1-ML, 2-IR, 3-DB, 4-HCI, 5-AI] and PUBMED Sen et al. (2008) that
consists of scientific journals collected from the PubMed database with the
following three categories: [0-Diabetes Mellitus, Experimental, 1-Diabetes
Mellitus Type 1, 2-Diabetes Mellitus Type 2]. In this paper, we are only
interested in the structural information of the graph toward node
classification. Therefore, we utilize only node and label IDs for our
experiments.

###  3.2 Evaluation Metrics

This paper uses four metrics to evaluate the performance of the downstream
task of node classification.

Accuracy Rate $A$: This metric indicates the LLM’s performance on the task of
node classification.

$A=\frac{\text{No. of correct predictions}}{\text{Total no. of samples}}$ (1)

Mismatch Rate $M$: This metric indicates the degree of misclassification by
LLM (when the ground truth value is not the same as the predicted value).

$M=\frac{\text{No. of incorrect predictions}}{\text{Total no. of samples}}$
(2)

Denial Rate $D$: When we craft our prompt, we instruct the LLM to return -1 if
it cannot predict the label of the $?$ node (node to be classified). The
denial rate metric describes the rate of failure of the LLM (when the
predicted value is -1).

$D=\frac{\text{No. of predictions = -1}}{\text{Total no. of samples}}$ (3)

$1-A=M+D$ (4)

Token Limit Fraction $T$: This metric measures how the encoding modality of an
LLM utilizes its input context window, assessing the impact of token
constraints linked to the model’s neural network architecture. In transformer-
based models like GPT-3, GPT-4, and GPT-4V, a fixed-size attention window
limits the number of tokens processed simultaneously, affecting computational
cost and performance.

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

We use these four metrics in combination to evaluate node classification using
different encoding modalities because we are trying to capture the tradeoff
between informativeness and verbosity of the encoding. Metrics like
accuracy($\uparrow$), denial ($\downarrow$), and mismatch ($\downarrow$)
capture the informativeness of the prompt, while the token limit fraction
($\downarrow$) captures the verbosity of the prompt. In the brackets, we
denote the desired trend from each metric.

###  3.3 Graph Encoder Baselines

We compare our LLM models, which use different encoding modalities, to
traditional graph learning models GCNKipf and Welling (2016),
GraphSageHamilton et al. (2017) and GAT Veličković et al. (2017) as a baseline
for node classification tasks. We provide the training details for each GNN
model in Appendix A.

###  3.4 Text Modality Setup

We explore multiple factors that could impact node classification in the text
modality setup, such as the edge encoding function used, underlying graph
structure, and graph sampling methods.

Impact of Edge encoding function: Fatemi et al. (2023) describe the
significant impact of graph encoding function on the performance of LLMs on
graph-related tasks on simulated graphs. Motivated by this work, we experiment
with different edge representations, shown in Table 2, on real-world datasets
and evaluate the metrics for node classification.

Impact of Graph Structure : We selected real-world citation datasets
(mentioned in section 3.1) with differing network properties to explore the
significance of graph structure on node classification. Table 1 describes the
difference between these datasets’ network properties. The definitions for
these properties are provided in the Appendix B. Table 1 shows that Pubmed is
the largest and most connected network, with a single connected component and
a higher average degree. However, it has the lowest clustering coefficient,
suggesting less local clustering among its nodes. Citeseer, while larger than
CORA in terms of nodes, is the most fragmented, with many disconnected
components and the lowest density. CORA has the highest density and clustering
coefficient despite being the smallest network, indicating more local
connectivity.

Properties | CORA | Citeseer | Pubmed
---|---|---|---
Classes | 7 | 6 | 3
Nodes | 2,708 | 3,327 | 19,717
Edges | 5,278 | 4,552 | 44,324
Density | 0.0014 | 0.0008 | 0.0002
Avg deg | 3.89 | 2.74 | 4.49
Clust coeff | 0.24 | 0.14 | 0.06
Diameter | $\infty$ | $\infty$ | 18
Components | 78 | 438 | 1
2-hop nodes | 36 | 15 | 60
Table 1: Comparison of network properties of popular citation network datasets
CORA, Citeseer and Pubmed.

Impact of Sampling Strategy: We experiment with two distinct graph sampling
strategies to understand the impact on node classification. We expect that
while Forest Fire sampling tends to provide a more representative view of the
entire network, particularly in large, single-component networks (Pubmed), Ego
graph sampling excels in analyzing local community structures around specific
nodes, proving more effective in networks where local structures are
interesting (CORA, Citeseer). Both methods, however, can skew perceptions of a
network’s overall structure, especially in diverse and expansive networks.

Edge Representation |  Text Encoding |  Description of Edge Representation
---|---|---
Edgelist |  Node to Label Mapping : Node 69025: Label 34| Node 17585: Label 10|… Edge list: [(69025, 96211), (69025, 17585), (17585, 104598), (17585, 18844), (17585, 96211), (96211, 34515)] |  An Edgelist is a graph data structure that represents a graph by listing the edge connections between two nodes. (A, B) indicates an connection between nodes A and B.
Edgetext |  Node to Label Mapping : Node 85328: Label 16| Node 158122: Label ?|… Edge connections (source node - target node): Node 85328 is connected to Node 158122. Node 158122 is connected to Node 167226. |  An Edgetext explicitly lists the connections between two nodes; for example, Node A is connected to Node B or Node A - Node B
Adjacency List |  Node to Label Mapping : Node 2339: Label 3| Node 2340: Label ?|… Adjacency list: 1558: [2339, 2340], 2339: [1558, 2340], 2340: [2339, 1558] |  An adjacency list represents a graph as an array of linked lists. The index of the array represents a vertex, and each element in its linked list represents the other vertices that form an edge with the vertex. For example, A: [B, C] shows that A is connected to B and C. This gives an idea of node-neighborhood
GML |  GraphML: graph [
node [
id 2339
label 3
]
node [
id 2340
label ?
]
node [
id 1558
label 3
]
edge [
source 2339
target 1558
]
edge [
source 2339
target 2340
]
]
|  A GraphML format consists of an unordered sequence of node and edge
elements enclosed within []. Each node element has a distinct id and label
attribute contained within []. Each edge element has source and target
attributes contained within [] that identify the endpoints of an edge by
having the same value as the node id attributes of those endpoints. The node
label information is embedded within the structure, meaning no node-label
mapping is notneeded.
GraphML |  GraphML: <graphml xmlns=http://graphml.graphdrawing.org/xmlns xmlns:xsi=http://www.w3.org/2001/XMLSchema-instance
xsi:schemaLocation=http://graphml.graphdrawing.org/xmlns
http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd> <graph
edgedefault=undirected>
<node id=2339 label=3 />
<node id=2340 label=? />
<node id=1558 label=3 />
<edge source=2339 target=1558 />
<edge source=2339 target=2340 />
</graph>
</graphml> |  A GraphML file consists of an XML file containing a graph element, within which is an unordered sequence of node and edge elements. Each node element should have a distinct id attribute as well as its label, and each edge element has source and target attributes that identify the endpoints of an edge by having the same value as the id attributes of those endpoints. The node label information is embedded within the structure meaning no node-label mapping is needed.
Table 2: Summary of edge representation passed as a part of the text modality
encoder with their associated examples and explanations. We find that the
Adjacency list representation provides a granular yet not too verbose view of
the graph being passed to the LLM.

###  3.5 Motif Modality Setup

We experiment with different network motifs as input to the modality encoder.
Table 3 describes the different types of motifs considered, a description of
the motif, and an example of the encoding generated as input to GPT-4.
Implementation details are in the Appendix.

We distinguish between providing the count of motifs in a graph and the
members of the motifs attached to the unlabeled node. We hypothesize that if
the unlabeled node is connected to an influential node (star motif) or an
influential community of nodes (triangle or clique), it could influence the
node’s label much more than the motif count Tu et al. (2018) information,
which merely provides the frequency of a motif in the provided graph.
Similarly, when a node is the center of a star motif, it implies that it is an
influential node with many nodes citing it (in a citation network). When a
node is part of a triangle motif or a bigger clique, it means that the node is
part of a tightly-knit community of highly connected nodes, therefore, all the
neighboring node labels influence the node’s label.

Type of Motif |  Motif Encoding |  Description of Motif
---|---|---
Node-Label Mapping |  Node to Label Mapping : Node 1889: Label 4 | … Node 1893: Label ?|… |  Only the node-label mapping is provided (this gives no connectivity information to LLM)
No. of Star Motifs |  Node to Label Mapping : Node 1889: Label 4 | … Node 1893: Label ?| … Graph motif information: Number of star motifs: 0| |  Star motifs signify centralized networks with influential central nodes, where a central node is connected to others that aren’t interlinked. We pass the count of the star motifs present in the graph.
No. of Triangle Motifs |  Node to Label Mapping : Node 1889: Label 4 | … Node 1893: Label ?| … Graph motif information: Number of triangle motifs: 6| |  Triangle motifs (triads connecting three nodes) are foundational in social networks, indicating transitive relationships, community structures, and strong social ties. We pass the count of the triads present in the graph.
No. of Triangle Motifs Attached |  Node to Label Mapping : Node 1889: Label 4 | … Node 1893: Label ?|… Graph motif information: Triangle motifs attached to $?$ node: [1893,2034,1531], [1893,1531,429]| |  We pass the triangle motifs attached to the $?$ label, which gives an idea of the influential triads connected to the $?$ node.
No. of Star Motifs Attached |  Node to Label Mapping : Node 1889: Label 4 | … Node 1893: Label ?|… Graph motif information: Star motifs connected to $?$ node: []| |  We pass the star motifs attached to the $?$ label, which gives an idea of the influential nodes connected to the $?$ node.
No. of Star and Triangle Motifs |  Node to Label Mapping : Node 1889: Label 4 | … Node 1893: Label ?|… Graph motif information: Number of star motifs: 0| Number of triangle motifs: 6| |  We pass the count of the triads and star motifs present in the graph, to give the LLM an idea of the graph structure.
Star and Triangle Motifs attached |  Node to Label Mapping : Node 1889: Label 4 | … Node 1893: Label ?|… Graph motif information: Triangle motifs attached to ? node: [1893,2034,1531], [1893,1531,429]| Star motifs connected to $?$ node: []| |  We pass the star motifs and triads attached to the $?$ label, which gives an idea of the influential nodes and triads connected to the $?$ node.
No of cliques $?$ Node is part of |  Node to Label Mapping : Node 1889: Label 4 | … Node 1893: Label ?|… Graph motif information: Number of cliques in graph: 0| $?$ Node is a part of these cliques: []| |  We pass the number of cliques in the network, which gives an idea of its clustered nature. We also pass the cliques the $?$ label is a part of, which gives an idea of the immediate community of the unlabelled node.
No of cliques $?$ Node is attached to |  Node to Label Mapping : Node 1889: Label 4 | … Node 1893: Label ?|…Graph motif information: $?$ Node is attached to these cliques: []| |  We pass the cliques the $?$ label is attached to, which gives an idea of the neighboring influential community of the unlabelled node.
Table 3: Summary of motif information passed as a part of the motif modality
encoder with their associated examples and explanations. The Aggregate of all
changes setup combines all of the above motif information to give the LLM a
local and global view of the graph being passed.

###  3.6 Image Modality Setup

Using the image modality, we experiment with multiple ways to represent the
graph structure. We first generate the graph rendering of our sampled graphs
using NetworkX Hagberg et al. (2008) and color the nodes per the label values
of each node. We set the unlabeled node always to be “red” and have a $?$ mark
as a label on the node. No other node except the unlabeled node can be red. We
intend to implicitly convey to the VLM (GPT-4V) that the node classification
should be based on the label corresponding to the node’s coloring. We then
observe that the classification performance could still use improvement and
hypothesize that the improvement could be a function of some image
representation changes. Figure 3 illustrates how applying different changes to
the image representation can enhance an image’s human readability. We then use
these image encodings to evaluate the performance of node classification.

(a) Original NetworkX Graph Hagberg et al. (2008) \- no image setting changes
made

(b) Node Size Increase \- changing the rendering using GraphViz Ellson et al.
(2002) and increasing the size of each node in the graph, increasing node and
label clarity

(c) Contrasting Text Color \- contrasting the textual labels with the node
color will make the labels more “human-readable”

(d) Distinctive Node Colors \- choosing distinct colors allows the VLM to
distinguish differently labeled nodes better

(e) Node Size increase based on 1-Hop-distance \- increasing the size of nodes
near the vicinity of the un-labeled node might allow the VLM to prioritize the
data of nodes of greater size as opposed to nodes further away

(f) Aggregate all changes \- all changes from b) to e) are applied to maximize
image clarity

Figure 3: Image representation changes were applied sequentially on a graph,
and we observed a distinct increase from (a) to (f) in human readability and
understanding of the graph structure.

###  3.7 Creating the GraphTMI Benchmark

We identify that not all graphs are equally easy for node classification with
all modalities. Depending on the “difficulty” of the graph, a particular
encoding modality (or combinations) might be better suited. We decide on graph
“difficulty” based on the dual criteria of 1) count of motifs and 2) homophily
in the graph.

The intuition behind the homophily criteria, in network theory McPherson et
al. (2001), is that nodes are likely to form connections with similar nodes
rather than dissimilar ones. Thus, a graph that has a higher degree of
homophily (multiple same labels present in the graph) would be much easier to
classify as compared to a graph with a higher degree of heterophily (multiple
different labels present in the graph), as the unlabeled node can be predicted
based on the similar labels of its neighbors. This is illustrated in Figure 4,
which shows examples from the CORA dataset (7 labels). Here, we see that the
label of the red node in (a) is much easier to infer than (b) or (c). We apply
a naive heuristic to decide homophily, i.e., the count of the distinct labels
in the graph. If the count of distinct labels $<3$, the graph is considered
easy. If the count is $\geq 3$ and $<5$, it is considered medium, and if the
count is $\geq 5$, it is considered hard.

The intuition behind the count of motifs criteria is that a graph with
multiple network motifs is more complex Tu et al. (2018) and, therefore, more
difficult to classify. We see this in Figure 4, where graphs (b) and (c) have
multiple kinds of motifs, and it is more difficult to infer the label of the
red node. To decide the motif criteria, we count the total number of motifs(
focusing on just triads, star motifs, and cliques) in a graph. For example, if
this count of motifs $\leq 10$ for the CORA dataset, the graph is considered
easy. If the count is $>10$ and $\leq 20$, it is regarded as medium; if the
count is $>20$, it is considered hard. Some graphs can have both the homophily
and motif criteria applicable to them; for instance, Figure 4 (b) can be
classified as medium based on homophily, hard based on the count of motifs.
This leads us to combine the homophily and the count of motif criteria to
define the “task difficulty”. Thus, we can have $2^{3}=8$ categories of
difficulty, and the final difficulty label is decided by choosing the higher
annotation between homophily and count of motif classification). So, a graph
with criteria {easy, hard} will be assigned the final task difficulty, hard.

Thus, we can classify graphs based on our “task difficulty” heuristic, and we
introduce GraphTMI (Graph Text-Motif-Image), a novel benchmark dataset of
input graph structures paired with their associated modality encodings (text,
motif, and image), associated prompts and resulting LLM classifications. This
benchmark will further the community’s understanding of distinct graphs on LLM
prompting.

(a) EASY \- ($\\#$distinct labels $<3$) and ($\\#$motifs $\leq 10$)

(b) MEDIUM \- ($3\leq\\#$ distinct labels $<5$) and ($10<\\#$ motifs $\leq
20$)

(c) HARD - ($\\#$distinct labels $\geq 5$) and ($\\#$ motifs $\geq 20$)

Figure 4: Classifying graph task difficulty based on the criteria of Homophily
and Number of Motifs yields a dataset of EASY, MEDIUM, and HARD graph problems
and their associated modality encodings and classifications. This benchmark is
called the GraphTMI dataset.

##  4 Results

###  4.1 Results Across All Modalities

Comparing Node Classification Performance across Encoding Modalities: Figure 5
shows the node classification performance using the accuracy rate($\uparrow$),
mismatch rate ($\downarrow$), denial rate ($\downarrow$), and token limit
fraction ($\downarrow$) across all encoding modalities. The desired trend is
shown in brackets. If we consider only accuracy, we see that the text modality
surpasses other modalities but on considering other metrics like denial rate
and token limit fraction, the limitations of the text modality become clear.
We observe that the text modality shows a high accuracy rate and token limit
fraction. This aligns with this modality’s tendency to provide specific yet
verbose local information. We also see a high denial rate with the text
modality, and this could be because the long input confuses the LLM, leading
it to predict $-1$. We observe the benefits associated with the image
modality, where it is quite comparable in accuracy rate while having a much
lower denial rate and token limit fraction. This shows that the global context
provided by the image modality reduces denial by the LLM and requires a much
lesser fraction of the context window. Hence, the image modality shows signs
of being an informative yet compressive modality.

Comparing Node Classification Accuracies between Graph baselines and LLM
models : Table 4 compares the node classification accuracy rates between graph
and LLM baselines to see if the LLM baselines are comparable to the
traditional graph methods for node classification across all datasets. We
consider a test sample of 50 ego graphs for this apple-to-apple analysis
because GPT-V has only released a preview version with a rate limit of 100 RPD
(requests per day), which constrains us from extending our analysis to a
larger sample. Appendix A shows the test accuracy of the graph baselines with
1000 samples.

From this table, we find that the text modality is comparable with graph
baselines in all three datasets, while the image modality comes a close
second. This shows the potential of LLMs to be a good foundational model for
graphs. We also observe that the lowest denial rate is for the image modality
in the smaller CORA and Citeseer datasets, while the bigger Pubmed dataset
shows a higher denial rate. This could be because of bigger subgraphs sampled,
leading to congestion in the image modality, causing the LLM to deny a
classification.

|  Model | Cora | Citeseer | Pubmed
---|---|---|---|---
GNN Baselines |  GCN | 0.7584 $\pm 0.121$ | 0.6102 $\pm 0.087$ | 0.7546 $\pm 0.076$
GAT |  0.7989 $\pm 0.092$ | 0.6583 $\pm 0.074$ | 0.7490 $\pm 0.060$
GraphSage | 0.7719 $\pm 0.124$ | 0.6017 $\pm 0.103$ | 0.7193 $\pm 0.076$
LLMs + Encoding Modality |  Text |  0.81 $\pm 0.04$ [0.07 $\pm 0.03$] |  0.75 $\pm 0.05$ [0.07 $\pm 0.01$] |  0.83 $\pm 0.01$ [0.08 $\pm 0.01$]*
Motif | 0.73 $\pm 0.06$ [0.06 $\pm 0.01$] | 0.59 $\pm 0.01$ [0.32 $\pm 0.02$] | 0.77 $\pm 0.006$ [0.13 $\pm 0.04$]
Image | 0.77 $\pm 0.05$ [0.04 $\pm 0.02$]* |  0.71 $\pm 0.09$ [0.06 $\pm 0.0$]* |  0.79 $\pm 0.03$ [0.19 $\pm 0.01$]
Table 4:  We report test accuracy rates of node classification across
different datasets and denial rates $D$ in [brackets] for LLM models. *
indicates the lowest denial rate for each modality. The highest accuracy rate
for the dataset is in bold, while the second highest is underlined. Figure 5:
We compare the Modality type (x-axis) with the value of the mean metrics
(y-axis). The desired trend is given in brackets for each metric. We observe
the accuracy rate (A $\uparrow$) is comparable between text and image
modalities. The motif modality shows the highest mismatch rate (M
$\downarrow$). The image modality shows the least denial rate (D
$\downarrow$). The image modality also shows the least token limit fraction (T
$\downarrow$).

Qualitative analysis of denial of classification in the Image Modality In
Figure 6, we give some examples of graphs sampled from multiple datasets for
which GPT-4V denied providing a label (returned $-1$) using the image modality
and the reasons provided by the LLM for denial. We observe that a) the LLM
requires context about how labels are assigned to each node. We left this
information implicit in our image modality encoder, where every node is
colored per its label. The red color is reserved for the $?$ node, which is
unlabeled. This information is not explicit to the LLM. With image (b), there
is no clear pattern associating the node’s color with its label, which is a
confusion induced by the great amount of heterophily in the graph. Image (c)
brings up the need for few-shot learning, where the LLM understands how to
infer red nodes given other graph examples.

Insights from GraphTMI We evaluate the accuracy of node classification across
multiple modalities, considering the different categories of task difficulty
from the GraphTMI benchmark. We observe in Figure 7 that easy problems (high
homophily, simple graph structure) have higher accuracy with the image
modality encoding. Graphs categorized as medium or hard, because of a
heterophyllous nature or complex graph structure, have a higher accuracy with
the text modality, though the image modality is not far behind. This is
probably because of precise local information provided by the text modality,
which is lost in the image modality. This figure illustrates the burgeoning
potential of the image modality encoder to solve graph reasoning tasks like
node classification with improved representation.

(a) (Ground = 0) Without additional context or rules for how labels are
assigned, it is not possible to accurately predict the label of the red node.

(b) (Ground = 4) The label cannot be determined with certainty due to the lack
of a discernible pattern or rule that associates a node’s color or its
connections with its label.

(c) (Ground = 2) The label cannot be determined with certainty due to the lack
of a clear pattern in the graph and no previous examples of red nodes to infer
from.

Figure 6: Examples of graphs where VLM (GPT-4V) returned -1 or denied to
predict a label and the reason for denial. The ground truth for this graph is
given in brackets.  Figure 7: Modality encoder trends with graph task
difficulty based on Homophily and Number of Motifs on CORA dataset

###  4.2 Modality Specific Results

These observations suggest that the choice of dataset and modality can
significantly impact the performance metrics

####  4.2.1 Text Modality Results

Impact of edge encoding function: Figure 8 shows that using the Adjacency List
as the mode of edge representation with node label mapping is the most
informative encoding function, which balances the trade-off between high
accuracy and low token limit fraction.

Figure 8:  We compare the edge representation type (x-axis) with the value of
the mean metrics (y-axis). The desired trend is given in brackets for each
metric. The highest performing edge representation is the “adjacency list”
representation with the highest accuracy (A $\uparrow$) and low mismatch rate
(M $\downarrow$)), denial rate (D $\downarrow$), and token limit fraction (T
$\downarrow$).

Impact of graph structure and graph sampling: In Figure 9, we observe the
variation of metrics with a chosen dataset (each having a different graph
structure) and sampling strategies. CORA displays similarly high accuracy with
both sampling techniques, probably because it is the smallest, most dense,
most clustered graph. Thus, both sampling strategies would work well with
CORA. The denial rate in CORA is lower with ff sampling than ego sampling.
Citeseer exhibits the highest denial rate with forest fire (ff) sampling,
probably because the local clustering nature is lost in this kind of sampling,
leading to an inconsistent sample. It also exhibits the lowest mean accuracy,
indicating more challenges in correctly predicting outcomes than the other
datasets. Pubmed is the largest dataset, with high connectivity and 1 single
component. Therefore, the samples generated via ego graph sampling with Pubmed
generally tend to be large - leading to an increased token limit fraction.
Citeseer, on the other hand, is a fragmented, disconnected dataset with more
local connectivity. Therefore, ego graph samples from Citeseer are smaller and
have a lower token limit fraction.

Figure 9: We compare the mean metrics (y-axis) for each dataset and sampling
type (x-axis). Green is the accuracy rate, Blue is the mismatch rate, Red is
the denial rate, and Pink is the token limit fraction. The desired trends for
each metric are given in brackets - ($\uparrow$) accuracy rate, ($\downarrow$)
mismatch rate, ($\downarrow$) denial rate, and ($\downarrow$) token limit
fraction. The x-axis distinguishes between ego graph sampling (ego) and forest
fire sampling (ff) through different bar textures.

Figure 10: We compare the motif information (x-axis) to the mean metrics
(y-axis). Desired trends are denoted in brackets. Metrics considered are
Accuracy Rate (A $\uparrow$), Mismatch Rate (M $\downarrow$), and Denial Rate
(D $\downarrow$). The highest performing motif information change “triangle
and star attached to $?$” has higher accuracy and lower mismatch and denial
rate.

Figure 11: We compare the image representations (x-axis) to the mean metrics
(y-axis). Desired trends are denoted in brackets. Metrics considered are
Accuracy Rate (A $\uparrow$), Mismatch Rate (M $\downarrow$), and Denial Rate
(D $\downarrow$). The highest performing image representation “all changes
applied” has a higher accuracy and lower mismatch rate

####  4.2.2 Motif Modality Results

Figure 11 illustrates the performance of GPT-4 on introducing different motif
information changes as a part of the motif modality encoder. Table 3 explains
the intuition behind these changes. We observe that the mean accuracy rate
goes up on adding the “triangle and star attached to $?$ node” motif, while
the other metrics for the same setting are low. The higher performance of this
motif information is likely because of the local and global context given to
the LLM through the node-label mapping and the actual nodes associated with
each other as part of triads or star motifs.

####  4.2.3 Image Modality Results

Figure 8 describes how we introduce multiple changes to represent an image,
and Figure 11 illustrates that the best setting can be determined by looking
at the highest mean accuracy, low mean denial rate, and mismatch rate of the
node classification. We observe that the “rendering change” offers the highest
bump in accuracy, which only goes down when “node size is changed on hop”.
This is probably because the LLM is confused by different node sizes and their
meaning. This could be resolved by clarifying the text prompt or using
different shapes to represent nodes at different hop distances. Based on
Figure 11, when “all the changes are applied”, the denial rate is minimum, and
the accuracy rate is highest (0.7).

##  5 Related Work

GNN-based methods GNNs are particularly effective for node classification and
link prediction Dwivedi et al. (2020), with applications across social
networks, computer vision, chemistry, and biology Hou et al. (2022). Their
reliance on complete network structures, often unavailable in real-world
settings Wei and Hu (2022), is mitigated through graph sampling techniques
Ahmed et al. (2013). Prominent GNN models include Graph Convolutional Networks
(GCN) Kipf and Welling (2016), GraphSage Hamilton et al. (2017), and Graph
Attention Networks (GAT) Veličković et al. (2017), each having unique features
and applications. A significant limitation of GNNs is their inability to
process non-numeric data directly, like text and images, which requires
preprocessing steps like feature engineering Wang et al. (2021).

LLMs for graph reasoning Recent research has delved into using Large Language
Models (LLMs) for tasks involving implicit graphical structures, revealing
their potential in various complex reasoning domains Huang et al. (2022).
Integrating LLMs with graph-based tasks have been explored by He et al.
(2023), where LLM explanations are used to train Message Passing Neural
Networks (MPNNs) in node category prediction. Chen et al. (2023) expanded the
use of LLMs to enhance features and predict node classifications. Wang et al.
(2023) introduced NLGraph, a benchmark for evaluating LLMs in traditional
graph tasks. Additionally, Guo et al. (2023) conducted an empirical study on
LLMs’ abilities in tasks requiring structural and semantic understanding. All
these studies use LLMs as a sub-component, such as a feature extractor, within
conventional graph learning frameworks.

Prompt Design for Graphs Different prompting approaches for querying large
language models (LLMs) primarily focus on optimizing the prompt’s text to
improve task performance. Zero-shot prompting presents the model with only a
task description, relying on the model’s pre-existing knowledge to generate
the correct output. Few-shot in-context learning Brown et al. (2020) goes a
step further by providing a few examples of the task with the desired outputs,
which the model then uses to learn and apply to new inputs. Chain-of-thought
prompting Wei et al. (2022) gives the model step-by-step examples detailing
the problem-solving process, encouraging it to generate its reasoning paths. A
variant of this, zero-shot CoT Kojima et al. (2022), skips prior examples and
prompts the model to produce its reasoning chains with a simple starter
phrase. Bag prompting Wang et al. (2023)is tailored for graph-related tasks,
suggesting the construction of a graph before attempting the task. Guo et al.
(2023) propose methods like format explanations and role prompting for clearer
task understanding and strategic input arrangement to exploit LLMs’ in-context
learning. Additionally, they highlight self-prompting, where the LLM refines
prompts through context summarization, addressing the challenges of inadequate
or overly complex graph information.

##  6 Future Work

Future research based on this study can advance in several directions. A
crucial development would be integrating multiple modalities for node
classification, enhancing accuracy, and providing comprehensive insights into
node characteristics across varying graph structures. Another promising avenue
is applying these findings to text-attributed graphs. This approach, focusing
on encoding rich textual node and behavioral information, can deepen the
understanding of complex networks.

Exploring heterogeneous graphs, which feature diverse node and edge types
unlike the homogenous graphs studied here, is another key area. Applying
different modalities, especially image modality, to represent the varied
entities in these graphs, prevalent in real-world applications like social
networks, can offer significant advancements.

Broadening the study to encompass other semantic graph reasoning tasks,
including link prediction, community detection, and graph classification, can
also extend its practical applicability. These tasks are essential for a
comprehensive grasp of complex network structures.

Lastly, applying these methodologies to directed graphs, which have unique
characteristics and challenges distinct from undirected graphs, represents a
valuable research opportunity. Tailoring and refining the study’s approaches
for directed graphs could provide critical insights and practical applications
across various domains.

##  7 Conclusion

This research delves into the application of Large Language Models (LLMs) in
tasks involving graph-structured data, a crucial step towards artificial
general intelligence (AGI). While LLMs have shown versatility in domains like
social network analysis, drug discovery, and recommendation systems, they face
challenges due to their reliance on unstructured text, leading to issues like
hallucination and logical oversights. This paper proposes addressing these
limitations through graph-structured data, exploring efficient input encoding
modalities, and prompt designing for graph tasks.

The study focuses on graph node classification, evaluating the effectiveness
of different encoding modalities - text, image, and motif - for LLMs. It
introduces innovative approaches like motif modality encoding, which balances
local and global perspectives, and image modality encoding, which leverages
vision-capable LLMs like GPT-4V for a more global view with efficient token
usage. Key contributions of this research include a comprehensive analysis of
graph-structure prompting in various modalities and the introduction of the
GraphTMI benchmark. The findings indicate that image modality is more
effective than text for balancing token limits and retaining essential
information. The study also highlights how graph task difficulty, edge
encoding functions, graph structure, graph sampling techniques, and motif
information impact node classification performance.

The empirical results reveal that while LLMs are improving in handling graph
data, they lag behind Graph Neural Network (GNN) models in real-world graph
applications. This study identifies current limitations and potential future
directions for LLMs, particularly in understanding graphs and performing
reasoning tasks with image capabilities.

## Limitations

Although innovative in applying Large Language Models (LLMs) to graph-
structured data, this research faces key limitations. The computational
demands of detecting network motifs, essential for understanding complex
network dynamics, pose a significant challenge. This process requires
extensive computational power and advanced algorithms, limiting scalability
and efficiency. We subvert these challenges by restricting our subgraph sample
size to 3 hops of an ego graph. Additionally, the study is constrained by the
current rate limitations of GPT-V, which affects its ability to process and
analyze data at scale efficiently. This limitation restricts the depth and
scope of the analysis, although future advancements in GPT-V may mitigate this
issue. A further limitation lies in the study’s simplistic approach to
estimating homophily, relying merely on label count and neglecting the
importance of hop distance. This overlooks critical network structure and node
similarity aspects, leading to a potentially oversimplified analysis.
Incorporating hop distance could provide a more accurate representation of
network homophily. These limitations underscore the need for further
advancements in computational techniques, model capabilities, and more nuanced
theoretical methods in network analysis.

## Acknowledgements

We thank the members of the MinnesotaNLP research group for their feedback on
our project and fruitful discussion. This was instrumental to our project and
helped us clarify our research.

## References

  * Ahmed et al. (2013) Nesreen K Ahmed, Jennifer Neville, and Ramana Kompella. 2013.  Network sampling: From static to streaming graphs.  _ACM Transactions on Knowledge Discovery from Data (TKDD)_ , 8(2):1–56.
  * Andreas (2022) Jacob Andreas. 2022.  Language models as agent models.  _arXiv preprint arXiv:2212.01681_.
  * Brown et al. (2020) Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901.
  * Bubeck et al. (2023) Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Kamar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott Lundberg, et al. 2023.  Sparks of artificial general intelligence: Early experiments with gpt-4.  _arXiv preprint arXiv:2303.12712_.
  * Carrington et al. (2005) Peter J Carrington, John Scott, and Stanley Wasserman. 2005.  _Models and methods in social network analysis_ , volume 28.  Cambridge university press.
  * Chen et al. (2023) Zhikai Chen, Haitao Mao, Hang Li, Wei Jin, Hongzhi Wen, Xiaochi Wei, Shuaiqiang Wang, Dawei Yin, Wenqi Fan, Hui Liu, et al. 2023.  Exploring the potential of large language models (llms) in learning on graphs.  _arXiv preprint arXiv:2307.03393_.
  * Dwivedi et al. (2020) Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. 2020.  Benchmarking graph neural networks.  _arXiv preprint arXiv:2003.00982_.
  * Ellson et al. (2002) John Ellson, Emden Gansner, Lefteris Koutsofios, Stephen C North, and Gordon Woodhull. 2002.  Graphviz—open source graph drawing tools.  In _Graph Drawing: 9th International Symposium, GD 2001 Vienna, Austria, September 23–26, 2001 Revised Papers 9_ , pages 483–484. Springer.
  * Fatemi et al. (2023) Bahare Fatemi, Jonathan Halcrow, and Bryan Perozzi. 2023.  Talk like a graph: Encoding graphs for large language models.  _arXiv preprint arXiv:2310.04560_.
  * Felmlee et al. (2021) Diane Felmlee, Cassie McMillan, and Roger Whitaker. 2021.  Dyads, triads, and tetrads: a multivariate simulation approach to uncovering network motifs in social graphs.  _Applied network science_ , 6(1):1–26.
  * Giles et al. (1998) C Lee Giles, Kurt D Bollacker, and Steve Lawrence. 1998.  Citeseer: An automatic citation indexing system.  In _Proceedings of the third ACM conference on Digital libraries_ , pages 89–98.
  * Guo et al. (2023) Jiayan Guo, Lun Du, and Hengyu Liu. 2023.  Gpt4graph: Can large language models understand graph structured data? an empirical evaluation and benchmarking.  _arXiv preprint arXiv:2305.15066_.
  * Hagberg et al. (2008) Aric Hagberg, Pieter Swart, and Daniel S Chult. 2008.  Exploring network structure, dynamics, and function using networkx.  Technical report, Los Alamos National Lab.(LANL), Los Alamos, NM (United States).
  * Hamilton et al. (2017) Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017.  Inductive representation learning on large graphs.  _Advances in neural information processing systems_ , 30.
  * He et al. (2023) Xiaoxin He, Xavier Bresson, Thomas Laurent, and Bryan Hooi. 2023.  Explanations as features: Llm-based features for text-attributed graphs.  _arXiv preprint arXiv:2305.19523_.
  * Holland and Leinhardt (1974) Paul W Holland and Samuel Leinhardt. 1974.  The statistical analysis of local structure in social networks.
  * Hou et al. (2022) Yifan Hou, Jian Zhang, James Cheng, Kaili Ma, Richard TB Ma, Hongzhi Chen, and Ming-Chang Yang. 2022.  Measuring and improving the use of graph information in graph neural networks.  _arXiv preprint arXiv:2206.13170_.
  * Huang and Chang (2022) Jie Huang and Kevin Chen-Chuan Chang. 2022.  Towards reasoning in large language models: A survey.  _arXiv preprint arXiv:2212.10403_.
  * Huang et al. (2022) Wenlong Huang, Pieter Abbeel, Deepak Pathak, and Igor Mordatch. 2022.  Language models as zero-shot planners: Extracting actionable knowledge for embodied agents.  In _International Conference on Machine Learning_ , pages 9118–9147. PMLR.
  * Kipf and Welling (2016) Thomas N Kipf and Max Welling. 2016.  Semi-supervised classification with graph convolutional networks.  _arXiv preprint arXiv:1609.02907_.
  * Kojima et al. (2022) Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. 2022.  Large language models are zero-shot reasoners.  _Advances in neural information processing systems_ , 35:22199–22213.
  * Leskovec and Faloutsos (2006) Jure Leskovec and Christos Faloutsos. 2006.  Sampling from large graphs.  In _Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 631–636.
  * Lewis et al. (2020) Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, et al. 2020.  Retrieval-augmented generation for knowledge-intensive nlp tasks.  _Advances in Neural Information Processing Systems_ , 33:9459–9474.
  * Madaan et al. (2022) Aman Madaan, Shuyan Zhou, Uri Alon, Yiming Yang, and Graham Neubig. 2022.  Language models of code are few-shot commonsense learners.  _arXiv preprint arXiv:2210.07128_.
  * McCallum et al. (2000) Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. 2000.  Automating the construction of internet portals with machine learning.  _Information Retrieval_ , 3:127–163.
  * McPherson et al. (2001) Miller McPherson, Lynn Smith-Lovin, and James M Cook. 2001.  Birds of a feather: Homophily in social networks.  _Annual review of sociology_ , 27(1):415–444.
  * Melville and Sindhwani (2010) Prem Melville and Vikas Sindhwani. 2010.  Recommender systems.  _Encyclopedia of machine learning_ , 1:829–838.
  * Milo et al. (2002) Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. 2002.  Network motifs: simple building blocks of complex networks.  _Science_ , 298(5594):824–827.
  * Mislove et al. (2007) Alan Mislove, Massimiliano Marcon, Krishna P Gummadi, Peter Druschel, and Bobby Bhattacharjee. 2007.  Measurement and analysis of online social networks.  In _Proceedings of the 7th ACM SIGCOMM conference on Internet measurement_ , pages 29–42.
  * OpenAI (2023a) OpenAI. 2023a.  Gpt-4 system card.  https://openai.com/research/gpt-4v-system-card.
  * OpenAI (2023b) OpenAI. 2023b.  Gpt-4v(ision) system card.  https://cdn.openai.com/papers/GPTV_System_Card.pdf.
  * Palowitch et al. (2022) John Palowitch, Anton Tsitsulin, Brandon Mayer, and Bryan Perozzi. 2022.  Graphworld: Fake graphs bring real insights for gnns.  In _Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_ , pages 3691–3701.
  * Pan et al. (2023) Shirui Pan, Linhao Luo, Yufei Wang, Chen Chen, Jiapu Wang, and Xindong Wu. 2023.  Unifying large language models and knowledge graphs: A roadmap.  _arXiv preprint arXiv:2306.08302_.
  * Sen et al. (2008) Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. 2008.  Collective classification in network data.  _AI magazine_ , 29(3):93–93.
  * Stolz and Schlereth (2021) Simon Stolz and Christian Schlereth. 2021.  Predicting tie strength with ego network structures.  _Journal of Interactive Marketing_ , 54(1):40–52.
  * Tu et al. (2018) Kun Tu, Jian Li, Don Towsley, Dave Braines, and Liam D Turner. 2018.  Network classification in temporal networks using motifs.  _arXiv preprint arXiv:1807.03733_.
  * Veličković et al. (2017) Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2017.  Graph attention networks.  _arXiv preprint arXiv:1710.10903_.
  * Vishveshwara et al. (2002) Saraswathi Vishveshwara, KV Brinda, and Natarajan Kannan. 2002.  Protein structure: insights from graph theory.  _Journal of Theoretical and Computational Chemistry_ , 1(01):187–211.
  * Wang et al. (2023) Heng Wang, Shangbin Feng, Tianxing He, Zhaoxuan Tan, Xiaochuang Han, and Yulia Tsvetkov. 2023.  Can language models solve graph problems in natural language?  _arXiv preprint arXiv:2305.10037_.
  * Wang et al. (2021) Yangkun Wang, Jiarui Jin, Weinan Zhang, Yong Yu, Zheng Zhang, and David Wipf. 2021.  Bag of tricks for node classification with graph neural networks.  _arXiv preprint arXiv:2103.13355_.
  * Wei et al. (2022) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. 2022.  Chain-of-thought prompting elicits reasoning in large language models.  _Advances in Neural Information Processing Systems_ , 35:24824–24837.
  * Wei and Hu (2022) Qiang Wei and Guangmin Hu. 2022.  Evaluating graph neural networks under graph sampling scenarios.  _PeerJ Computer Science_ , 8:e901.
  * Yang et al. (2018) Carl Yang, Mengxiong Liu, Vincent W Zheng, and Jiawei Han. 2018.  Node, motif and subgraph: Leveraging network functional blocks through structural convolution. in 2018 ieee.  In _ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM)_ , pages 47–52.
  * Yasir et al. (2023) Mustafa Yasir, John Palowitch, Anton Tsitsulin, Long Tran-Thanh, and Bryan Perozzi. 2023.  Examining the effects of degree distribution and homophily in graph learning models.  _arXiv preprint arXiv:2307.08881_.
  * Yin et al. (2023) Shukang Yin, Chaoyou Fu, Sirui Zhao, Ke Li, Xing Sun, Tong Xu, and Enhong Chen. 2023.  A survey on multimodal large language models.  _arXiv preprint arXiv:2306.13549_.
  * Zhang et al. (2023) Yue Zhang, Yafu Li, Leyang Cui, Deng Cai, Lemao Liu, Tingchen Fu, Xinting Huang, Enbo Zhao, Yu Zhang, Yulong Chen, et al. 2023.  Siren’s song in the ai ocean: A survey on hallucination in large language models.  _arXiv preprint arXiv:2309.01219_.

Table 5: Graph Properties and Their Descriptions Name of Property |  Description
---|---
Density |  Measures how connected the graph is. It’s the ratio of actual edges to possible edges.
Degree Distribution |  The distribution of node degrees. The histogram might follow a specific pattern (e.g., power-law distribution, Gaussian distribution).
Average Degree |  The average degree of nodes in the graph.
Connected Components |  A subgraph in which a path connects any two nodes.
Clustering Coefficient |  Measures the degree to which nodes tend to cluster together.
Graph Diameter |  The longest shortest path between any two nodes. It provides insight into the graph’s overall size.
2hop nodes |  Average number of nodes present in the subgraph at 2 hop distance from any node

##  Appendix A Training Details for GNN models

|  Model | Cora | Citeseer | Pubmed
---|---|---|---|---
GNN Baselines |  GCN | 0.7820 $\pm 0.133$ | 0.6540 $\pm 0.083$ | 0.7480 $\pm 0.077$
GAT |  0.8200 $\pm 0.084$ | 0.6680 $\pm 0.069$ | 0.7510 $\pm 0.050$
GraphSage | 0.7570 $\pm 0.137$ | 0.6300 $\pm 0.098$ | 0.7430 $\pm 0.078$
LLMs + Encoding Modality |  Text |  0.81 $\pm 0.04$ [0.07 $\pm 0.03$] |  0.75 $\pm 0.05$ [0.07 $\pm 0.01$] |  0.83 $\pm 0.01$ [0.08 $\pm 0.01$]*
Motif | 0.73 $\pm 0.06$ [0.06 $\pm 0.01$] | 0.59 $\pm 0.01$ [0.32 $\pm 0.02$] | 0.77 $\pm 0.006$ [0.13 $\pm 0.04$]
Image | 0.77 $\pm 0.05$ [0.04 $\pm 0.02$]* |  0.71 $\pm 0.09$ [0.06 $\pm 0.0$]* |  0.79 $\pm 0.03$ [0.19 $\pm 0.01$]
Table 6:  Test accuracy rates of node classification across different datasets
using the entire 1000 test data and denial rates $D$ in [brackets] for LLM
models. For LLMs, we chose a test sample of 50 graphs. * indicates the lowest
denial rate for each modality. The highest accuracy rate for the dataset is in
bold, while the second highest is underlined.

For training our GNN models, we used the following hyperparameters. The
training and test set details are given below. We also report the parameters
of each model. In the main paper, report the GNN test accuracy on 50 samples
due to API constraints by GPT-4, which do not allow us to conduct the apple-
to-apple comparison with 1000 test samples. However, Table 6 reports the test
accuracy for GNN reported on 1000 samples.

##  Appendix B Specifics of LLM Experiments

Token limits for each modality Due to their architecture, transformer-based
models like GPT-3 and GPT-4 have a fixed-size attention window. This
determines how many tokens the model can “remember” or pay attention to at
once. This limit also manages the computational cost of running the model and
the model’s performance. The token limit constraint for GPT-4 is 8192 tokens,
while for GPT-4V(vision), the limit is claimed to be 128000 tokens, but
currently, only the preview version has been released, and the actual limit is
10000 tokens.

Rate limits for each LLM For a tier 5 user, the rate limit for GPT-4 is 10K
RPM (requests per minute), and for GPT-4V, the rate limit is 100 RPD (requests
per day).

Modality Experiments For text and motif type, we sample 20 graphs, number of
hops considered = 3, no of runs = 3, and perform ego graph and forest fire
sampling. In the paper, we report the results from ego graph sampling because
node classification typically needs a Localized View Around Specific Nodes,
best provided by ego graph sampling. With Image Modality Experiments, we
sample 50 ego-graphs and no of runs = 2, as rate limitations constrain us.

Graph Structure Properties Table 5 provides definitions for network
properties. The average number of nodes and edges in a 2-hop subgraph is also
reported for CORA, Citeseer and Pubmed datasets.

| CORA | Citeseer | Pubmed
---|---|---|---
Avg no of edges in 2 hop subgraph | 62.70 ± 94.77 | 26.35 ± 61.70 | 129.36 ± 287.61
Avg no of nodes in 2 hop subgraph | 36.78 ± 48.12 | 15.11 ± 24.73 | 60.05 ± 85.12
Table 7: Subgraph Sampling Stats Details | GCN | GAT | GraphSAGE
---|---|---|---
Epochs | 100 | 100 | 100
Learning Rate | 0.005 | 0.005 | 0.005
Weight Decay | 5e-4 | 5e-4 | 5e-4
Table 8: List of GNN training hyperparameters Dataset | Cora | Citeseer | Pubmed
---|---|---|---
Training Set | 140 | 120 | 60
Testing Set | 1000 | 1000 | 1000
GCN Parameters | 23063 | 59366 | 8067
GAT Parameters | 92373 | 237586 | 32393
GraphSage Params | 46103 | 118710 | 16115
Table 9: GNN Training/Testing and Parameters per dataset