REVIEW 18 cited by
Talk like a Graph: Encoding Graphs for Large Language Models
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Talk like a Graph: Encoding Graphs for Large Language Models
read the original abstract
Graphs are a powerful tool for representing and analyzing complex relationships in real-world applications such as social networks, recommender systems, and computational finance. Reasoning on graphs is essential for drawing inferences about the relationships between entities in a complex system, and to identify hidden patterns and trends. Despite the remarkable progress in automated reasoning with natural text, reasoning on graphs with large language models (LLMs) remains an understudied problem. In this work, we perform the first comprehensive study of encoding graph-structured data as text for consumption by LLMs. We show that LLM performance on graph reasoning tasks varies on three fundamental levels: (1) the graph encoding method, (2) the nature of the graph task itself, and (3) interestingly, the very structure of the graph considered. These novel results provide valuable insight on strategies for encoding graphs as text. Using these insights we illustrate how the correct choice of encoders can boost performance on graph reasoning tasks inside LLMs by 4.8% to 61.8%, depending on the task.
Forward citations
Cited by 18 Pith papers
-
Lost in Tokenization: Fundamental Trade-offs in Graph Tokenization for Transformers
Graph tokenizations for Transformers induce distinct depth regimes with proven separations and impossibility results for converting between them at limited depth.
-
Fisher Markets with Approximately Optimal Bundles and the Need for a PCP Theorem for PPAD
Establishes PPAD-hardness for (1-δ)-optimal bundle competitive equilibria in SPLC Fisher markets assuming PCP-for-PPAD conjecture, and proves the conjecture is required for hardness in this market class.
-
Fisher Markets with Approximately Optimal Bundles and the Need for a PCP Theorem for PPAD
PPAD-hardness for constant-δ approximate competitive equilibria in SPLC Fisher markets requires the PCP-for-PPAD conjecture, which the paper proves is necessary to establish such hardness.
-
GraphInfer-Bench: Benchmarking LLM's Inference Capability on Graphs
Presents GraphInfer-Bench to demonstrate that no evaluated LLM-based method family closes the performance gap on graph inference tasks requiring multi-node reasoning, with plain GNNs matching or exceeding them.
-
Evaluating LLMs on Large-Scale Graph Property Estimation via Random Walks
EstGraph benchmark evaluates LLMs on estimating properties of very large graphs from random-walk samples that fit in context limits.
-
GraphScout: Empowering Large Language Models with Intrinsic Exploration Ability for Agentic Graph Reasoning
GraphScout trains LLMs to autonomously synthesize structured training data from knowledge graphs via flexible exploration tools, enabling a 4B model to outperform larger LLMs by 16.7% on average with fewer inference t...
-
GraphVec: Cross-Domain Graph Vectorization for Graph-Level Representation Learning
GraphVec produces transferable fixed-dimensional graph embeddings via spectral features from multi-scale global graphs and a convergent mean-alignment procedure, outperforming baselines on cross-domain few-shot classi...
-
C-RE-ACT: Causal RE-ACTing Agent for O-RAN Forensic Triage
An agentic O-RAN triage system that ranks root causes via SAM causal discovery and graph soft-prompting claims 89% top-3 accuracy on 140 testbed experiments.
-
The Sword, Shield, and Achilles' Heel: Characterizing the Linguistic Inductive Bias of Large Language Models for Spatial Reasoning in Navigation Planning
Experiments reveal that topological cues robustly support LLM navigation planning while incorrect semantic cues derail it, with linguistic format effects varying by model size and compression.
-
LARAG: Link-Aware Retrieval Strategy for RAG Systems in Hyperlinked Technical Documentation
LARAG improves RAG answer quality on hyperlinked technical documentation by using author-defined links for retrieval, achieving higher BERTScore while using fewer chunks and tokens than standard embedding-based RAG.
-
EHRAG: Bridging Semantic Gaps in Lightweight GraphRAG via Hybrid Hypergraph Construction and Retrieval
EHRAG constructs structural hyperedges from sentence co-occurrence and semantic hyperedges from entity embedding clusters, then applies hybrid diffusion plus topic-aware PPR to retrieve top-k documents, outperforming ...
-
GraphDC: A Divide-and-Conquer Multi-Agent System for Scalable Graph Algorithm Reasoning
GraphDC applies divide-and-conquer multi-agent LLM reasoning to graph algorithms by decomposing graphs into subgraphs for local agents and integrating via a master agent, outperforming direct methods especially on lar...
-
Lost in Serialization: Invariance and Generalization of LLM Graph Reasoners
Fine-tuned graph reasoners become more stable to node relabeling but more brittle to edge ordering and format, and they do not consistently beat base models on new spectral graph tasks.
-
Generalization Boundaries of Fine-Tuned Small Language Models for Graph Structural Inference
Fine-tuned small language models (3-4B parameters) preserve ordinal consistency in ranking graph structural properties for graphs larger than training data and from held-out families, showing architecture-specific deg...
-
Exploring the In-Context Learning Capabilities of LLMs for Money Laundering Detection in Financial Graphs
LLMs using few-shot in-context learning on serialized k-hop subgraphs from synthetic AML scenarios can assess suspiciousness and generate natural-language justifications.
-
Query-Aware Learnable Graph Pooling Tokens as Prompt for Large Language Models
LGPT and Early Query Fusion create flexible graph representations for LLMs, achieving 4.13% improvement on GraphQA without training the model.
-
Retrieval-Augmented Generation with Graphs (GraphRAG)
A survey proposing a holistic GraphRAG framework with components including query processor, retriever, organizer, generator, and data source, plus domain-tailored reviews, challenges, and future directions.
-
REBot: From RAG to CatRAG with Semantic Enrichment and Graph Routing
A category-routed hybrid of RAG and knowledge-graph retrieval answers Vietnamese university-regulation questions with F1 98.89% on the authors' own dataset — about 0.2 points above plain RAG.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.