Elamur Research⌕
☰
home / papers / 2023 / GPT4Graph: Can Large Language Models Understand Graph Structured Data ? An Empirical Evaluation and Benchmarking

GPT4Graph: Can Large Language Models Understand Graph Structured Data ? An Empirical Evaluation and Benchmarking

Paper · 2023 · Jiayan Guo, Lun Du, Hengyu Liu et al.

Summary

Large language models perform well on text, but it is unclear how well they handle graphs, which are central to social network analysis, chemistry, recommendation and knowledge bases. The authors study this empirically. They propose a pipeline that first serializes a graph into a graph description language (edge list, adjacency list, GML or GraphML). A prompt handler then merges this serialization with the user's question, possibly over several rounds.

Two families of prompting are compared:

  • Manual prompting: role instructions, format explanations, reordering of question and input, in-context examples and chain-of-thought.
  • Self-prompting: the model first writes its own summary of the graph or its own explanation of the format, then answers.

The benchmark spans ten scenarios. Structural tasks include size, degree, diameter and clustering coefficient. Semantic tasks include knowledge graph QA, node classification and graph classification. The models can solve some graph problems, especially when given richer context or self-generated augmentation. Even so, they remain clearly behind specialized graph models, which motivates better graph-to-text encodings and tool use.

Key points

  • Graph formats: inputs are serialized as an edge list, adjacency list, GML or GraphML. Results are evaluated in zero-shot and few-shot settings.
  • Node classification on OGBN-ARXIV: adding neighbor text helps. Zero-shot accuracy rises from 48 (target node only) to 53 (1-hop) and 57 (2-hop). One-shot reaches 60 with 2-hop context.
  • Chain-of-thought on OGBN-ARXIV: CoT did not reliably help. Zero-shot-CoT scored only 40 with node-only or 1-hop context.
  • Graph classification: experiments use OGBG-MOLHIV and OGBG-MOLPCBA. On MOLHIV with GML, 1-shot-CoT scored about 67.65. Without self-format explanation the score fell to about 64.71, and without self-summarization to about 61.77.
  • Future directions: the authors suggest better graph encodings for LLMs, investigating why in-context examples help little, and letting LLMs call external graph tools.

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

🏢MicrosoftRedmond · United States378 works · 161,630 citations🎓Peking UniversityBeijing · China315 works · 43,267 citations🎓Xi'an Jiaotong UniversityXi'an · China42 works · 36,431 citations🎓University of Technology SydneySydney · Australia19 works · 12,908 citations🏢Microsoft (Finland)Espoo · Finland2 works · 360 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

Cite

Cite as 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. arXiv:2305.15066.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.2305.15066 · arXiv 2305.15066

@misc{guo2023gpt4graph,
  title = {{GPT4Graph: Can Large Language Models Understand Graph Structured Data ? An Empirical Evaluation and Benchmarking}},
  author = {Jiayan Guo, Lun Du, Hengyu Liu, Mengyu Zhou, Xinyi He and Shi Han},
  year = {2023},
  doi = {10.48550/arxiv.2305.15066},
  eprint = {2305.15066},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2305.15066}
}

References

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

  1. Marc Barthelemy. 2004. Betweenness centrality in large complex networks. The European physical journal B, 38(2):163–168. find
  2. Andreas D Baxevanis, Gary D Bader, and David S Wishart. 2020. Bioinformatics. John Wiley & Sons. find
  3. Smriti Bhagat, Graham Cormode, and S Muthukrishnan. 2011. Node classification in social networks. arXiv preprint arXiv:1101.3291. — [arXiv:1101.3291](https://arxiv.org/abs/1101.3291) find
  4. Richard J Bolton and David J Hand. 2002. Statistical fraud detection: A review. Statistical science, 17(3):235–255. find
  5. Ulrik Brandes. 2001. A faster algorithm for betweenness centrality. Journal of mathematical sociology, 25(2):163–177. find
  6. Ulrik Brandes, Markus Eiglsperger, Jürgen Lerner, and Christian Pich. 2013. Graph markup language (graphml). find
  7. Miao Chen, Xinjiang Lu, Tong Xu, Yanyan Li, Zhou Jingbo, Dejing Dou, and Hui Xiong. 2022. Towards table-to-text generation with pretrained language model: A table structure understanding and text deliberating approach. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Pr… find
  8. Fan RK Chung, Vance Faber, and Thomas A Manteuffel. 1994. An upper bound on the diameter of a graph from eigenvalues associated with its laplacian. SIAM Journal on Discrete Mathematics, 7(3):443–457. find
  9. Julian Martin Eisenschlos, Maharshi Gor, Thomas Müller, and William W Cohen. 2021. Mate: multi-view attention for table transformer efficiency. Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing". find
  10. Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. 2019. A fair comparison of graph neural networks for graph classification. arXiv preprint arXiv:1912.09893. — [arXiv:1912.09893](https://arxiv.org/abs/1912.09893) find
  11. Heng Gong, Yawei Sun, Xiaocheng Feng, Bing Qin, Wei Bi, Xiaojiang Liu, and Ting Liu. 2020. Tablegpt: Few-shot table-to-text generation with table structure reconstruction and content matching. In Proceedings of the 28th International Conference on Computational Linguistics, pages 1978–1988. find
  12. Michael Himsolt. 1997. Gml: Graph modelling language. University of Passau. find
  13. 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, 33:22118–22133. find
  14. Xiao Huang, Jingyuan Zhang, Dingcheng Li, and Ping Li. 2019. Knowledge graph embedding based question answering. In Proceedings of the twelfth ACM international conference on web search and data mining, pages 105–113. find
  15. Folasade Olubusola Isinkaye, Yetunde O Folajimi, and Bolande Adefowoke Ojokoh. 2015. Recommendation systems: Principles, methods and evaluation. Egyptian informatics journal, 16(3):261–273. find
  16. Shaoxiong Ji, Shirui Pan, Erik Cambria, Pekka Marttinen, and S Yu Philip. 2021. A survey on knowledge graphs: Representation, acquisition, and applications. IEEE transactions on neural networks and learning systems, 33(2):494–514. find
  17. Jinhao Jiang, Kun Zhou, Zican Dong, Keming Ye, Wayne Xin Zhao, and Ji-Rong Wen. 2023. Structgpt: A general framework for large language model to reason over structured data. arXiv preprint arXiv:2305.09645. find
  18. Thomas N Kipf and Max Welling. 2016. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations.
  19. Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. 2022. Large language models are zero-shot reasoners. In Advances in Neural Information Processing Systems.
  20. Ao Liu, Haoyu Dong, Naoaki Okazaki, Shi Han, and Dongmei Zhang. 2022. PLOG: Table-to-logic pre-training for logical table-to-text generation. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 5531– 5546, Abu Dhabi, United Arab Emirates. Association for… find
  21. Mark EJ Newman. 2005. A measure of betweenness centrality based on random walks. Social networks, 27(1):39–54. find
  22. Kazuya Okamoto, Wei Chen, and Xiang-Yang Li. 2008. Ranking of closeness centrality for large-scale social networks. Lecture Notes in Computer Science, 5059:186–195. find
  23. Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. 2022. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35:27730–27744.
  24. Shah Rukh Qasim, Hassan Mahmood, and Faisal Shafait. 2019. Rethinking table recognition using graph neural networks. In 2019 International Conference on Document Analysis and Recognition (IC-DAR), pages 142–147. IEEE. find
  25. Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. 2019. Dropedge: Towards deep graph convolutional networks on node classification. arXiv preprint arXiv:1907.10903. — [arXiv:1907.10903](https://arxiv.org/abs/1907.10903) find
  26. Timo Schick, Jane Dwivedi-Yu, Roberto Dessì, Roberta Raileanu, Maria Lomeli, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. 2023. Toolformer: Language models can teach themselves to use tools. arXiv preprint arXiv:2302.04761.
  27. Yuan Sui, Mengyu Zhou, Mingjie Zhou, Shi Han, and Dongmei Zhang. 2023. Evaluating and enhancing structural understanding capabilities of large language models on tables via input designs. arXiv preprint arXiv:2305.13062.
  28. Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. 2008. Arnetminer: extraction and mining of academic social networks. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 990– 998. find
  29. Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, Yoshua Bengio, et al. 2017. Graph attention networks. stat, 1050(20):10– 48550. find
  30. W Patrick Walters and Regina Barzilay. 2020. Applications of deep learning in molecule generation and molecular property prediction. Accounts of chemical research, 54(2):263–270. find
  31. Stanley Wasserman and Katherine Faust. 1994. Social network analysis: Methods and applications. find
  32. Jason Wei, Maarten Bosma, Vincent Zhao, Kelvin Guu, Adams Wei Yu, Brian Lester, Nan Du, Andrew M Dai, and Quoc V Le. 2021. Finetuned language models are zero-shot learners. In International Conference on Learning Representations.
  33. Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L Griffiths, Yuan Cao, and Karthik Narasimhan. 2023. Tree of thoughts: Deliberate problem solving with large language models. arXiv preprint arXiv:2305.10601. find
  34. Jiawei Zhang. 2023. Graph-toolformer: To empower llms with graph reasoning ability via prompt augmented by chatgpt. arXiv preprint arXiv:2304.11116. find
  35. Junlong Zhang and Yu Luo. 2017. Degree centrality, betweenness centrality, and closeness centrality in social network. In 2017 2nd international conference on modelling, simulation and applied mathematics (MSAM2017), pages 300–303. Atlantis press. find
  36. Yuyu Zhang, Hanjun Dai, Zornitsa Kozareva, Alexander Smola, and Le Song. 2018. Variational reasoning for question answering with knowledge graph. In Proceedings of the AAAI conference on artificial intelligence, volume 32. find
  37. Tong Zhao, Yozen Liu, Leonardo Neves, Oliver Woodford, Meng Jiang, and Neil Shah. 2021. Data augmentation for graph neural networks. In Proceedings of the aaai conference on artificial intelligence, volume 35, pages 11015–11023. find
  38. Wayne Xin Zhao, Kun Zhou, Junyi Li, Tianyi Tang, Xiaolei Wang, Yupeng Hou, Yingqian Min, Beichen Zhang, Junjie Zhang, Zican Dong, et al. 2023. A survey of large language models. arXiv preprint arXiv:2303.18223.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/guo-2023-gpt4graph-large-language-models-understand/