Elamur Research⌕
☰
home / papers / 2026 / Colorful Talks with Graphs: Human-Interpretable Graph Encodings for Large Language Models

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

Paper · 2026 · Angelo Zangari, Peyman Baghershahi and Sourav Medya

Summary

LLMs handle unstructured text well but struggle with graph problems. These tasks need explicit structure, permutation invariance and multi-hop reasoning. Earlier graph-to-text prompts often insert numeric IDs or continuous GNN embeddings, which carry no meaning for a language model. The authors propose a training-free encoding that keeps the graph serialization (nodes plus adjacency list) and adds a structural label to each node. The label comes from an ordered variant of Weisfeiler–Leman (WL) refinement. The resulting similarity classes are then expressed as ordinary color words, such as "red" or "orange," instead of opaque numbers. The method has three variants: labels only (L-OWL), colors only (C-OWL) and colors plus labels (CL-OWL). A theoretical analysis shows that, under mild assumptions, the ordered WL ranking agrees with a broad family of distance-weighted, centrality-like measures. Experiments covered graph algorithms and node classification on synthetic and real graphs. The colored encodings beat a plain text baseline (TLG-A), with the largest gains on tasks that need global structure. This suggests that cues grounded in natural language help LLMs reason over graphs.

Key points

  • On node classification (F1-Macro, 600 instances from 10–50-node subgraphs), C-OWL raised scores over TLG-A:
    • Cora: 11.35 to 22.30
    • Citeseer: 9.01 to 20.08
    • PubMed: 5.70 to 14.33
  • On OGBN-ArXiv, CL-OWL performed best, raising F1-Macro from 22.76 to 40.94. The authors link this to the dataset's larger scale and longer-range dependencies.
  • A color-palette ablation used 50-node Cora subgraphs, which produce about 32 WL labels each, and palettes of 3 to 45 colors (C3 to C9-5). Every color variant beat the baseline's 60% accuracy. The best result was 75%, reached at collision factors of about 1–5. Accuracy fell to 70% with the most fine-grained palette.
  • Replacing color words with opaque hue identifiers, while keeping the same WL classes, reduced node-classification performance. This points to the semantic grounding of the words as a source of the benefit.
  • The authors note two limitations: NP-hard tasks are not fully covered, and color encoding is a heuristic choice.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓University of Illinois ChicagoChicago · United States70 works · 20,363 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksArts and Humanities · 17,450 worksLanguage and Linguistics · 17,296 worksComputer Vision and Pattern Recognition · 3,486 works

🧭 Topics 1Research subjects and languages the work is about.Language models & pretraining · 3,894 works

Cite

Cite as Angelo Zangari, Peyman Baghershahi and Sourav Medya. 2026. Colorful Talks with Graphs: Human-Interpretable Graph Encodings for Large Language Models. Findings of the Association for Computational Linguistics: ACL 2026.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2026.findings-acl.2049

@inproceedings{zangari2026colorful,
  title = {{Colorful Talks with Graphs: Human-Interpretable Graph Encodings for Large Language Models}},
  author = {Angelo Zangari, Peyman Baghershahi and Sourav Medya},
  booktitle = {Findings of the Association for Computational Linguistics: ACL 2026},
  year = {2026},
  doi = {10.18653/v1/2026.findings-acl.2049},
  url = {https://doi.org/10.18653/v1/2026.findings-acl.2049}
}

References

34 references, 6 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Peyman Baghershahi, Gregoire Fournier, Pranav Nyati, and Sourav Medya. 2025. From nodes to narratives: Explaining graph neural networks with llms and graph context. Preprint, arXiv:2508.07117. find
  2. Runjin Chen, Tong Zhao, Ajay Kumar Jaiswal, Neil Shah, and Zhangyang Wang. 2024. Llaga: Large language and graph assistant. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net. find
  3. DeepSeek-AI. 2025. Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning. Preprint, arXiv:2501.12948.
  4. Bahare Fatemi, Jonathan Halcrow, and Bryan Perozzi. 2024. Talk like a graph: Encoding graphs for large language models. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net.
  5. Dongqi Fu, Liri Fang, Zihao Li, Zhe Xu, Hanghang Tong, Vetle I. Torvik, and Jingrui He. 2025. Bring Complex Geometric Information to LLMs: A Positional Survey of Graph Parametric Representation. In The Fourth Learning on Graphs Conference. find
  6. Jiayan Guo, Lun Du, Hengyu Liu, Mengyu Zhou, Xinyi He, and Shi Han. 2023. GPT4Graph: Can Large Language Models Understand Graph Structured Data ? An Empirical Evaluation and Benchmarking.
  7. Yufei He, Yuan Sui, Xiaoxin He, and Bryan Hooi. 2024. UniGraph: Learning a Unified Cross-Domain Foundation Model for Text-Attributed Graphs. find
  8. Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. 2020. Open graph benchmark: Datasets for machine learning on graphs. Advances in Neural Information Processing Systems (NeurIPS), 33. find
  9. Bowen Jin, Gang Liu, Chi Han, Meng Jiang, Heng Ji, and Jiawei Han. 2024a. Large Language Models on Graphs: A Comprehensive Survey. IEEE Transactions on Knowledge and Data Engineering, 36(12):8622–8642. find
  10. Bowen Jin, Chulin Xie, Jiawei Zhang, Kashob Kumar Roy, Yu Zhang, Zheng Li, Ruirui Li, Xianfeng Tang, Suhang Wang, Yu Meng, and Jiawei Han. 2024b. Graph Chain-of-Thought: Augmenting Large Language Models by Reasoning on Graphs.
  11. Jintang Li, Ruofan Wu, Yuchang Zhu, Huizhe Zhang, Liang Chen, and Zibin Zheng. 2025. Are Large Language Models In-Context Graph Learners? find
  12. Rui Li, Jiwei Li, Jiawei Han, and Guoyin Wang. 2024. Similarity-based Neighbor Selection for Graph LLMs. find
  13. Hao Liu, Jiarui Feng, Lecheng Kong, Ningyue Liang, Dacheng Tao, Yixin Chen, and Muhan Zhang. 2024a. One for all: Towards training one graph model for all classification tasks. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.… find
  14. Zheyuan Liu, Xiaoxin He, Yijun Tian, and Nitesh V. Chawla. 2024b. Can we Soft Prompt LLMs for Graph Learning Tasks? In Companion Proceedings of the ACM Web Conference 2024, pages 481–484. find
  15. Sahil Manchanda, Akash Mittal, Anuj Dhawan, Sourav Medya, Sayan Ranu, and Ambuj Singh. 2020. Gcomb: Learning budget-constrained combinatorial algorithms over billion-sized graphs. Advances in Neural Information Processing Systems, 33:20000– 20011. find
  16. Haitao Mao, Zhikai Chen, Wenzhuo Tang, Jianan Zhao, Yao Ma, Tong Zhao, Neil Shah, Mikhail Galkin, and Jiliang Tang. 2024. Position: graph foundation models are already here. In Proceedings of the 41st International Conference on Machine Learning, ICML’24. JMLR.org. find
  17. Yijian Qin, Xin Wang, Ziwei Zhang, and Wenwu Zhu. 2023. Disentangled Representation Learning with Large Language Models for Text-Attributed Graphs. find
  18. Rishabh Ranjan, Siddharth Grover, Sourav Medya, Venkatesan Chakaravarthy, Yogish Sabharwal, and Sayan Ranu. 2022. Greed: A neural framework for learning graph distance functions. Advances in Neural Information Processing Systems, 35:22518– 22530. find
  19. Xubin Ren, Jiabin Tang, Dawei Yin, Nitesh V. Chawla, and Chao Huang. 2024. A survey of large language models for graphs. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2024, Barcelona, Spain, August 25-29, 2024, pages 6616–6626. ACM. find
  20. Clayton Sanford, Bahare Fatemi, Ethan Hall, Anton Tsitsulin, Mehran Kazemi, Jonathan Halcrow, Bryan Perozzi, and Vahab Mirrokni. 2024. Understanding transformer reasoning capabilities via graph algorithms. In Advances in Neural Information Processing Systems 38: Annual Conference on Neural Informati… find
  21. Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt. 2011. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(77):2539–2561. find
  22. Shengyin Sun, Yuxiang Ren, Jiehao Chen, and Chen Ma. 2023. Large Language Models as Topological Structure Enhancers for Text-Attributed Graphs. find
  23. Yuanfu Sun, Zhengnan Ma, Yi Fang, Jing Ma, and Qiaoyu Tan. 2025. GraphICL: Unlocking Graph Learning Potential in LLMs through Structured Prompt Design. find
  24. Yanchao Tan, Hang Lv, Pengxiang Zhan, Shiping Wang, and Carl Yang. 2024. Graph-oriented Instruction Tuning of Large Language Models for Generic Graph Mining. find
  25. Jiabin Tang, Yuhao Yang, Wei Wei, Lei Shi, Lixin Su, Suqi Cheng, Dawei Yin, and Chao Huang. 2024. Graphgpt: Graph instruction tuning for large language models. In Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR 2024, Washington D…
  26. Xi Zhu, Haochen Xue, Ziwei Zhao, Wujiang Xu, Jingyuan Huang, Minghao Guo, Qifan Wang, Kaixiong Zhou, Imran Razzak, and Yongfeng Zhang. 2025. LLM as GNN: Graph Vocabulary Learning for Text-Attributed Graph Foundation Models. find
  27. Heng Wang, Shangbin Feng, Tianxing He, Zhaoxuan Tan, Xiaochuang Han, and Yulia Tsvetkov. 2023. Can language models solve graph problems in natural language? In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orl…
  28. Yanbang Wang, Hejie Cui, and Jon M. Kleinberg. 2024. Microstructures and accuracy of graph recall by large language models. In Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 - 15,… find
  29. Zhe Xu, Kaveh Hassani, Si Zhang, Hanqing Zeng, Michihiro Yasunaga, Limei Wang, Dongqi Fu, Ning Yao, Bo Long, and Hanghang Tong. 2024. How to Make LLMs Strong Node Classifiers? find
  30. Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. 2016. Revisiting semi-supervised learning with graph embeddings. In Proceedings of the 33rd International Conference on Machine Learning (ICML), pages 40–48. find
  31. Ruosong Ye, Caiqi Zhang, Runhui Wang, Shuyuan Xu, and Yongfeng Zhang. 2024. Language is all a graph needs. In Findings of the Association for Computational Linguistics: EACL 2024, pages 1955–1973, St. Julian’s, Malta. Association for Computational Linguistics. find
  32. Zeyang Zhang, Xin Wang, Ziwei Zhang, Haoyang Li, Yijian Qin, and Wenwu Zhu. 2024. Llm4dyg: Can large language models solve spatial-temporal problems on dynamic graphs? In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2024, Barcelona, Spain, August 25-29, 2… find
  33. Jianan Zhao, Le Zhuo, Yikang Shen, Meng Qu, Kai Liu, Michael Bronstein, Zhaocheng Zhu, and Jian Tang. 2023. GraphText: Graph Reasoning in Text Space. find
  34. Qi Zhu, Da Zheng, Xiang Song, Shichang Zhang, Bowen Jin, Yizhou Sun, and George Karypis. 2024. Parameter-Efficient Tuning Large Language Models for Graph Representation Learning. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/zangari-2026-colorful-talks-graphs-human-interpretable/