Colorful Talks with Graphs: Human-Interpretable Graph Encodings for Large Language Models

AI summary

Overview

Research area: Applied machine learning at the intersection of large language models (LLMs) and graph-structured reasoning, specifically graph-to-text translation and prompt engineering.

Technical level: Intermediate. The method itself is simple to describe (relabel nodes by Weisfeiler–Leman refinement, then name them with colors), but the paper includes a formal treatment (ordered 1-WL refinement, a centrality-connection theorem) and a broad empirical study.

Scope in one sentence: The paper proposes CL-OWL, a training-free graph-to-text encoding that translates ordered Weisfeiler–Leman structural labels into natural-language color words inside LLM prompts, and evaluates it against text-serialization baselines on synthetic algorithmic tasks and real-world node-classification datasets.

What This Paper Is About

LLMs are sequence models trained on text, while graphs are unordered combinatorial objects requiring permutation invariance and multi-hop relational reasoning, so feeding graphs to an LLM requires translating structure into text. Existing graph-to-text encodings often inject numeric identifiers, node indices, or continuous embeddings that are structurally meaningful but linguistically opaque, and evaluations tend to be limited to small graphs and local or classification-style tasks. This paper asks whether expressing graph structure through human-interpretable cues — specifically color words derived from ordered Weisfeiler–Leman (WL) refinement — lets an LLM exploit its linguistic priors and reason better about graphs.

Key Contributions

1. Human-interpretable structural encoding: A graph-to-text encoding strategy (CL-OWL) that injects explicit structural information into LLM prompts using human-interpretable tokens derived from WL refinement, preserving permutation invariance and structural similarity while aligning structure with linguistic abstractions.
2. Structure-preserving representation with theory: A principled analysis connecting ordered WL refinement to distance-weighted notions of node connectivity. Theorem 1 shows (1) degree consistency — for any nodes v, w, deg(v) > deg(w) implies ℓ_v^(1) > ℓ_w^(1); (2) shell-dominance implies label dominance at depth T under a tree-unfolding condition; and (3) consequently, for any nonincreasing positive weights, the truncated distance-weighted connectivity C_T(v) > C_T(w). Ordered 1-WL therefore induces an ordering consistent with a class of distance-weighted connectivity functions on locally tree-like neighborhoods.
3. Three method variants for controlled comparison: L-OWL (pure WL-based labels), C-OWL (pure WL-based colors), and CL-OWL (labels + colors), plus a compressed-prompting option that retains only nodes within a hop budget k_n of the query nodes (k_n = −1 means no filtering).
4. Comprehensive empirical study: Experiments across diverse graph families and task types — triangle counting, cycle check, reachability, shortest path, maximum flow, and node classification — on synthetic Erdős–Rényi, Barabási–Albert, and Path graphs, and on real-world Cora, Citeseer, PubMed, and OGBN-ArXiv data.

Main Findings

• WL-enriched prompting beats standard text serialization on global-reasoning tasks. Using gpt-4o on 200 graphs per task of 10–30 nodes from Barabási–Albert and Erdős–Rényi types (ER edge probability p = 0.2, BA minimum four edges per node), CL-OWL achieved 93.00% accuracy on Cycle Check versus 91.50% for TLG-F and 89.50% for TLG-A; L-OWL reached 91.87% on Shortest Path versus 87.80% (TLG-A) and 83.74% (TLG-F).
• Color variants generally outperform pure-label variants. On Cycle Check, C-OWL reached 92.50% and CL-OWL 93.00%, above L-OWL at 92.00%. On Maximum Flow, all WL variants reached 36.59% accuracy, above TLG-A at 33.33%, with CL-OWL obtaining the lowest MAE (0.438).
• Triangle counting is the exception. With gpt-4o, TLG-A reached 16.00% and TLG-F 11.50%, above L-OWL and C-OWL at 14.00% and CL-OWL at 14.50%. The authors conjecture that exact global triangle counting behaves like exhaustive local pattern matching over triples, where extra descriptors lengthen the prompt without directly identifying the counted motifs; they report in Appendix E.4 that WL-based cues do help a separate localized triangle-membership task.
• Structural descriptors substitute for serialized graph context. On Cora node classification with 50-node subgraphs, TLG-A degraded to 45.0% accuracy with 3-hop context, 40.0% with 2-hop, and 30.0% with 1-hop, while C-OWL reached 75.0% and CL-OWL 70.0% using only 1-hop context; CL-OWL also had the best MAE (0.176) and RMSE (0.420).
• WL prompting drastically shortens prompts at scale. On Barabási–Albert graphs at n = 1000, the TLG-A prompt averaged 1,705,906 characters versus 364,108 for C-OWL, 362,409 for L-OWL, and 368,648 for CL-OWL — roughly 4× shorter. On Erdős–Rényi graphs at n = 1000, TLG-A averaged 29,020 characters versus 1,530 (C-OWL), 1,521 (L-OWL), and 2,002 (CL-OWL), nearly 15× shorter.
• The color words matter, not just the WL partition. On Cora node classification with over-sampled subgraphs of 10, 20, 30, 40, and 50 nodes, C-OWL reached 68.9% accuracy, while the same WL classes expressed as synthetic hue identifiers ("Hue i") reached only 15.2% and as human names 6.3%; TLG-A reached 49.0%. Since the variants preserve the same WL partition, the gap is attributed to semantic grounding rather than structural information alone.
• There is a sweet spot in palette size. On 50-node Cora subgraphs, WL refinement produces about 32 distinct labels per graph. All color variants beat the baseline (TLG-A 60.0%): C3 65.0%, C6 75.0%, C9-0 75.0%, C9-3 75.0%, C9-5 70.0%, with collision factors of 10.6, 5.3, 3.5, 1.2, and 0.7 respectively. Best results appeared at collision factors between roughly 1 and 5, and performance dropped when the palette became overly fine-grained.
• Node classification benefits depend on dataset scale and complexity. In F1-Macro (%), C-OWL was strongest on Cora (22.30), Citeseer (20.08), and PubMed (14.33) against TLG-A (11.35, 9.01, 5.70). On OGBN-ArXiv, CL-OWL was best at 40.94 versus TLG-A at 22.76, C-OWL at 26.87, and L-OWL at 22.61.
• Scaling limit observed during dataset construction. Synthetic graphs were generated from n = 5 to n = 100 because beyond that, even strong LLMs (e.g., GPT-4-class) maintained zero accuracy on the hardest tasks in this setup.

Methodology in Plain English

The approach has four steps.

1. Serialize the graph. The graph is written as nodes with adjacency lists inside a natural-language prompt, along with a task description, few-shot examples, and the query.
2. Compute ordered structural labels. Standard 1-WL refinement iteratively updates each node's label by combining its own label with the sorted multiset of its neighbors' labels, giving a summary of the node's k-hop neighborhood. The authors modify the canonicalization so that identifiers are assigned in a globally deterministic, sorted order, producing labels that carry an ordering — nodes with larger, more extended connectivity tend to receive larger labels. They prove this ordering is consistent with distance-weighted connectivity measures on locally tree-like neighborhoods.
3. Turn labels into colors. Labels are normalized to the interval [0, 1] and mapped to color words through a mapping Ψ: labels → RGB channels → natural-language color names (e.g., red, pink, yellow). Colors serve as a similarity space that LLMs already understand — "red is closer to orange than blue" — rather than opaque integers or hexadecimal codes, and restricting to a one-dimensional segment of the color spectrum keeps the ordering monotonic.
4. Assemble the prompt. The full prompt is a concatenation of a context descriptor, a Colorful-WL structure descriptor, a few-shot guidance descriptor, and a query descriptor. A compressed variant keeps only the induced subgraph within a hop budget around the query and emits descriptors only for retained nodes — this isolates how much of the gain comes from descriptor quality versus raw graph context.

Baselines are Talk-Like-a-Graph (TLG) variants TLG-A (node indices plus tuple edges) and TLG-F (Friends-series character names), and, for node classification, GraphText, LLaGA, and OFA (using the official pipelines/checkpoints; OFA used the paper-reported supervised setting of 100 epochs, learning rate 10⁻⁴, batch size 128). GPT-3.5 was the base LLM unless specified otherwise; the Table 2 reasoning results use gpt-4o. Code is available at https://github.com/angelozangari/CL-OWL.

Why This Matters

Impact on research. The paper isolates a specific design question — how structure is expressed in text, not how much structure is provided — and shows that lexical grounding (real color words versus arbitrary tokens) accounts for a large performance gap. It also provides a theoretical link between WL refinement and centrality-style connectivity, giving the encoding a principled justification rather than a purely heuristic one. Because the method is training-free, it is applicable to closed-source LLMs that cannot be retrained on graph data.

Real-world applications (implied by the tasks studied):

• Querying text-only LLMs about network structure in logistics or routing settings, where shortest-path and maximum-flow style questions arise.
• Citation-network and other text-attributed graph prediction tasks, such as the node classification performed on Cora, Citeseer, PubMed, and OGBN-ArXiv.
• Local motif and cycle detection in dependency graphs, knowledge graphs, or program-analysis pipelines, where cycle check and triangle-membership style queries matter.
• Cost- and context-window-sensitive deployments, since WL-based prompting cut prompt length by roughly 4× on Barabási–Albert and nearly 15× on Erdős–Rényi graphs at n = 1000 compared with full serialization.

Industry relevance. The method requires no model fine-tuning and reduces prompt length, which directly affects inference cost and the ability to fit larger graphs into context windows. That combination makes it attractive for teams that want graph-aware behavior from off-the-shelf LLM APIs, though the paper notes performance still collapses on the hardest tasks beyond 100 nodes.

Future Directions

1. Extending coverage to NP-hard problems. The authors list generalization to NP-hard problems as an explicit limitation: the evaluated task set does not exhaustively cover graph reasoning problems, especially NP-hard ones.
2. Pushing past the 100-node ceiling. Synthetic graphs stopped at n = 100 because strong LLMs (e.g., GPT-4-class) held zero accuracy on the hardest tasks beyond that; how to scale human-interpretable encodings further is open.
3. Understanding the palette–collision trade-off. Results with ~32 WL labels per graph showed a peak around collision factors of roughly 1 to 5 and degradation at 0.7; a principled rule for choosing palette granularity is not provided.
4. Robustness and model dependence. The paper's limitations section is truncated in the supplied content, but the risks section flags sensitivity to prompt design, lack of robustness to distribution shifts, and hallucination, and the base LLMs differ between experiments (GPT-3.5 generally, gpt-4o for Table 2), leaving open how stable the color effect is across models.

Target Audience

Researchers and practitioners working on LLM-based structured reasoning, graph-to-text translation, and prompt engineering; machine learning engineers who want graph-aware behavior from off-the-shelf LLMs without training; and readers interested in the theoretical connection between Weisfeiler–Leman refinement, structural equivalence, and node centrality. Familiarity with basic graph terminology and LLM prompting is assumed, but the paper does not require prior expertise in graph neural networks.

Authors’ abstract

Graph problems are fundamentally challenging for large language models (LLMs). While LLMs excel at processing unstructured text, graph tasks require reasoning over explicit structure, permutation invariance, and computationally complex relationships, creating a mismatch with the representations of text-based models. Our work investigates how LLMs can be effectively applied to graph problems despite these barriers. We introduce a human-interpretable structural encoding strategy for graph-to-text translation that injects graph structure directly into natural language prompts. Our method involves computing a variant of Weisfeiler-Lehman (WL) similarity classes and maps them to human-like color tokens rather than numeric labels. The key insight is that semantically meaningful and human-interpretable cues may be more effectively processed by LLMs than opaque symbolic encoding. Experimental results on multiple algorithmic and predictive graph tasks show the considerable improvements by our method on both synthetic and real-world datasets. By capturing both local and global-range dependencies, our method enhances LLM performance especially on graph tasks that require reasoning over global graph structure.