TALK LIKE A GRAPH: ENCODING GRAPHS FOR LARGE LANGUAGE MODELS

- Google Research

- ICLR

Problem statement

- Study the effect of following on LLM performance:-

​

• Graph encoding

​

• Graph Structure

​

• Question(Prompt) encoding

​

- GraphQA: Dataset for edge existence, cycle check etc.

​

Contribution #1

- Study the effect of Graph encoding on LLM performance

​

​

Results

Contribution #2

- Study the effect of questions on LLM performance

​

​

Graph based questions:-

1. “Node degree”
2. “Edge existence”

​

Application based questions:-

1. “Number of friends?”
2. “Is Jack friends with Steve?”

Results

Important to translate any task into more contextually meaningful information

Contribution #3

- Does performance remain same when Graphs are disconnected?

​

​

NO

​

Zero-shot accuracy: 0.5%

​

Few-shot accuracy: 0%

​

COT accuracy: 0%

​

LLMs capture relationship between connected nodes but do not understand the absence of connections

​

​

​

​

​

​

​

​

WHY?

No explicit encoding about disconnected nodes

Contribution #4

- Study the effect of following Graph structures on LLM performance:-

• Star
• BA graphs
• ER graphs
• Path
• Complete
• SFN
• SBM

Star

BA

ER

SBM

Results

Conclusion

1. Graph encoding has a significant impact on the LLM’s performance

​

• LLMs understand the graph relatively better when:-
• number of edges are less and
• Graph is connected

​

• Graph structure has Significant Impact on LLM Reasoning

​

• Zero shot COT < Zero shot (for many basic tasks)

​

​

Takeaways

Make LLMs understand the structure of graph

1. LLMs Perform Poorly on Basic Graph Tasks

​

• LLMs do not understand structure of graph

(connected/disconnected)

Interesting claim: Fine-tuning does not improve LLM performance

​