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

Institution: Minnesota NLP, University of Minnesota

Authors: Debarati Das, Ishaan Gupta, Jaideep Srivastava, Dongyeop Kang

Arxiv Link: https://arxiv.org/abs/2311.09862

Code Link: None

Date: 2023.11.16

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 better integrate graph data with LLMs 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.

Introduction:

This paper explores the impact of encoding global and local graph structure in different modalities, with a particular focus on node classification.

Specifically, it compares three modalities: text, motif, and image.

Why the paper introduces the motif modality:

However, it becomes too verbose for large graphs, potentially exceeding the input context limits of large language models like GPT-4. To circumvent this, we suggest Motif modality encoding, which captures essential patterns within the node’s vicinity, offering a balanced local and global perspective.

Methodology

Text Encoder Modality

Encoding graphs as text can be separated into two key parts:

1. the mapping of nodes to their corresponding labels in the graph
   • {node ID: node label}
2. the encoding of edges between the nodes

We consider several factors that can influence the performance of text-modality encoding:

• Edge Encoding Function
• Graph Structure
• Sampling Strategy

Edge Encoding Function

• Edgelist
• Edgetext
• Adjacency List
• GML
• GraphML

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)]

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.

Adjacency List:

Node to Label Mapping : Node 2339: Label 3| Node 2340: Label ?|...
Adjacency list: 1558: [2339, 2340], 2339: [1558, 2340], 2340: [2339,1558]

GML:

A GML file consists of an unordered sequence of node and edge elements enclosed within [].

The node label information is embedded in the structure, so no separate node-label mapping is needed.

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
    	]
    ]

GraphML:

A GraphML file consists of an XML file containing a graph element, within which is an unordered sequence of node and edge elements.

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>

Graph Structure

We selected real-world citation datasets with differing network properties to explore the significance of graph structure on node classification.

• CORA
• Citeseer
• Pubmed

Sampling Strategy

• Ego graph
• Forest Fire sampling

Example

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: ?} ```

Motif Modality

Encoding graphs as motifs can be separated into two key parts:

1. the encoding of nodes to their corresponding labels in the graph
2. the motifs present around the ? (unlabeled) node.

Motif information

Example

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]| ```

Image Modality

We first render our sampled graphs with NetworkX and color each node according to its label.

We always color the unlabeled node red and mark it with a ‘?’ label.

Image representation

We examine how different changes to the image representation can improve an image’s human readability. We then use these image encodings to evaluate node classification performance.

Original NetworkX Graph	Node Size Increase Enlarging the nodes	Contrasting Text Color This subfigure contrasts the text labels against the node colors to improve the “human readability” of the labels.

Distinctive Node Colors Choosing a distinct color for nodes of each label makes the individual nodes easier to tell apart.	Node Size increase based on 1-Hop distance Enlarging the neighboring nodes	Aggregate all changes Applying all of the enhancements above

Result

Results Across All Modalities

⭐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 serve as a good foundation model for graphs.

⭐We also observe that the image modality has the lowest denial rate on the smaller CORA and Citeseer datasets, while the larger Pubmed dataset shows a higher denial rate. This may be because the subgraphs sampled there are bigger, which clutters the image modality and leads the LLM to deny a classification.

Qualitative analysis of denial of classification in the Image Modality

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. All the other nodes are colored according to their label, whereas the ? node is colored red, which confuses the LLM.	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. Heterophily is present in the graph: 3-?-4	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. Few-shot examples are needed

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, a confusion induced by the great amount of heterophily in the graph. Image (c) brings up the need for few-shot learning, that is, for showing the LLM other graph examples.

Insights from GraphTMI

Easy problems (high homophily, simple graph structure) have higher accuracy with the image modality encoding. Graphs categorized as medium or hard, because they are heterophilous or structurally complex, achieve higher accuracy with the text modality, though the image modality is not far behind.

Text Modality Results

Edge Encoding Function

The figure shows that the 🌟adjacency list, combined with node-label mapping, is the most informative edge encoding function: it strikes the best balance between high accuracy and a low token limit fraction.

• accuracy rate(↑)
• mismatch rate (↓)
• denial rate (↓)
• token limit fraction (↓)

Impact of graph structure and graph sampling:

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 - (↑) accuracy rate, (↓) mismatch rate, (↓) denial rate, and (↓) token limit fraction. The x-axis distinguishes between ego graph sampling (ego) and forest fire sampling (ff) through different bar textures.

• The impact on accuracy is small; what is mainly affected is the token limit fraction.

• Both sampling strategies perform best on CORA, probably because it is smaller, denser, and more clustered.

Motif Modality Results

We observe that the mean accuracy rate rises when the “triangle and star attached to ? node” motif is added, while the other metrics for the same setting stay low.

• This part contains almost no analysis; it merely mentions in passing that “triangle and star attached to ? node” works best.

Image Modality Results

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 the different node sizes and what they mean. It could be resolved by clarifying the text prompt or by using different shapes to represent nodes at different hop distances. Based on Figure 11, when “all the changes are applied”, the denial rate is at its minimum and the accuracy rate at its maximum (0.7).

1. Rendering changes do improve accuracy.
2. When “all the changes are applied”, the denial rate is at its minimum and the accuracy rate at its maximum (0.7).

Conclusion

• Representing graphs in the image and motif modalities as LLM input is something we had not seen before.
• Limited by compute and the token limit, the maximum hop count was set to 3.