GraphWiz: An Instruction-Following Language Model for Graph Computational Problems
Open accessAbstract
Large language models (LLMs) have achieved impressive success across various domains, but their capability in understanding and resolving complex graph problems is less explored. To bridge this gap, we introduce GraphInstruct, a novel instruction-tuning dataset aimed at enabling language models to tackle a broad spectrum of graph problems through explicit reasoning paths. Utilizing GraphInstruct, we build GraphWiz, an open-source language model capable of solving various graph computational problems while generating clear reasoning processes. To further enhance the model's performance and reliability, we integrate the Direct Preference Optimization (DPO) framework within the graph problem-solving context. The improved model, GraphWiz-DPO, achieves an average accuracy of 65% across nine tasks with different complexity levels, surpassing GPT-4 which has an average accuracy of 43.8%. Our study also investigates the relationship between training data volume and model performance, emphasizing the risk of overfitting as data volume increases. Additionally, we explore the transferability of the proposed model across different tasks and datasets, demonstrating its robust zero-shot generalization capability. GraphWiz offers a new blueprint and valuable insights for developing LLMs specialized in graph reasoning and problem-solving.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
GraphWiz achieves 65% average accuracy across diverse graph tasks and significantly outperforms GPT-4's 43.8%.
“GraphWiz extends this approach by incorporating DPO to enhance reasoning reliability, achieving 65% average accuracy across diverse graph tasks and significantly outperforming GPT-4's 43.8%”
From A Survey of Context Engineering for Large Language Models (2025) · cites this paper as [145]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks
Reimers, N., & Gurevych, I. (2019) · Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP) · doi:10.18653/v1/d19-1410 · Cited by 12,778 · see citing works
Kirillov, A., Mintun, E., Ravi, N., Mao, H., Rolland, C., Gustafson, L., Xiao, T., Whitehead, S., Berg, A. C., Lo, W.-Y., et al. (2023) · 2023 IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv51070.2023.00371 · Cited by 11,953 · see citing works
Proximal Policy Optimization Algorithms
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., & Klimov, O. (2017) · arXiv · doi:10.48550/arxiv.1707.06347 · Cited by 10,625 · see citing works
Chain-of-Thought Prompting Elicits Reasoning in Large Language Models
Wei, J., Wang, X., Schuurmans, D., Bosma, M., Ichter, B., Xia, F., Chi, E., Le, Q., & Zhou, D. (2022) · arXiv · doi:10.48550/arxiv.2201.11903 · Cited by 4,263 · see citing works
Training language models to follow instructions with human feedback
Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C. L., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., et al. (2022) · arXiv · doi:10.48550/arxiv.2203.02155 · Cited by 4,208 · see citing works
Self-Instruct: Aligning Language Models with Self-Generated Instructions
Wang, Y., Kordi, Y., Mishra, S., Liu, A., Smith, N. A., Khashabi, D., & Hajishirzi, H. (2023) · Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · doi:10.18653/v1/2023.acl-long.754 · Cited by 1,243 · see citing works
Document clustering: TF-IDF approach
Bafna, P., Pramod, D., & Vaidya, A. (2016) · 2016 International Conference on Electrical, Electronics, and Optimization Techniques (ICEEOT) · doi:10.1109/iceeot.2016.7754750 · Cited by 290 · see citing works
A Fused Gromov-Wasserstein Framework for Unsupervised Knowledge Graph Entity Alignment
Tang, J., Zhao, K., & Li, J. (2023) · Findings of the Association for Computational Linguistics: ACL (Findings of ACL) · doi:10.18653/v1/2023.findings-acl.205 · Cited by 34 · see citing works
Self-citationOpenAI, Achiam, J., Adler, S., Agarwal, S., Ahmad, L., Akkaya, I., Aleman, F. L., Almeida, D., Altenschmidt, J., Altman, S., et al. (2023) · arXiv · doi:10.48550/arxiv.2303.08774
Self-citation
Flagged first, then by citations
Research works printed but not linked: 40
- Rohan Anil, Andrew M Dai, Orhan Firat, Melvin Johnson, Dmitry Lepikhin, Alexandre Passos, Siamak Shakeri, Emanuel Taropa, Paige Bailey, Zhifeng Chen, et al. 2023. Palm 2 technical report. arXiv:2305.10403 (2023). · arXiv
- Ziwei Chai, Tianjie Zhang, Liang Wu, Kaiqiao Han, Xiaohai Hu, Xuanwen Huang, and Yang Yang. 2023. Graphllm: Boosting graph reasoning ability of large lan- guage model. arXiv:2310.05845 (2023). · arXiv
- Nuo Chen, Hongguang Li, Junqing He, Yinan Bao, Xinshi Lin, Qi Yang, Jianfeng Liu, Ruyi Gan, Jiaxing Zhang, Baoyuan Wang, and Jia Li. 2023. Orca: A Few-shot Benchmark for Chinese Conversational Machine Reading Comprehension. In Findings of EMNLP. 15685-15699.
- Nuo Chen, Zinan Zheng, Ning Wu, Linjun Shou, Ming Gong, Yangqiu Song, Dongmei Zhang, and Jia Li. 2023. Breaking language barriers in multilingual mathematical reasoning: Insights and observations. arXiv:2310.20246 (2023). · arXiv
- Zhikai Chen, Haitao Mao, Hang Li, Wei Jin, Hongzhi Wen, Xiaochi Wei, Shuaiqiang Wang, Dawei Yin, Wenqi Fan, Hui Liu, et al. 2023. Exploring the potential of large language models (llms) in learning on graphs. arXiv:2307.03393 (2023). · arXiv
- Zhikai Chen, Haitao Mao, Hongzhi Wen, Haoyu Han, Wei Jin, Haiyang Zhang, Hui Liu, and Jiliang Tang. 2023. Label-free node classification on graphs with large language models (llms). arXiv:2310.04668 (2023). · arXiv
- Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. 2021. Training Verifiers to Solve Math Word Problems. CoRR abs/2110.14168 (2021). · arXiv
- Paul Erdős, Alfréd Rényi, et al. 1960. On the evolution of random graphs. Publ. math. inst. hung. acad. sci 5, 1 (1960), 17-60.
- Bahare Fatemi, Jonathan Halcrow, and Bryan Perozzi. 2023. Talk like a Graph: Encoding Graphs for Large Language Models. In NeurIPS 2023 Workshop.
- Luyu Gao, Aman Madaan, Shuyan Zhou, Uri Alon, Pengfei Liu, Yiming Yang, Jamie Callan, and Graham Neubig. 2023. Pal: Program-aided language models. In ICML. 10764-10799.
- Xiaoxin He, Xavier Bresson, Thomas Laurent, Adam Perold, Yann LeCun, and Bryan Hooi. 2023. Harnessing Explanations: LLM-to-LM Interpreter for Enhanced Text-Attributed Graph Representation Learning. arXiv:2305.19523 (2023). · arXiv
- Jin Huang, Xingjian Zhang, Qiaozhu Mei, and Jiaqi Ma. 2023. Can llms effectively leverage graph structural information: When and why. arXiv:2309.16595 (2023). · arXiv
- Albert Q Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, De- vendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, et al. 2023. Mistral 7B. arXiv:2310.06825 (2023). · arXiv
- Albert Q Jiang, Alexandre Sablayrolles, Antoine Roux, Arthur Mensch, Blanche Savary, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Emma Bou Hanna, Florian Bressand, et al. 2024. Mixtral of experts. arXiv:2401.04088 (2024). · arXiv
- Mingyu Jin, Qinkai Yu, Haiyan Zhao, Wenyue Hua, Yanda Meng, Yongfeng Zhang, Mengnan Du, et al. 2024. The Impact of Reasoning Step Length on Large Language Models. arXiv:2401.04925 (2024). · arXiv
- Thomas N. Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In ICLR.
- Trupti M Kodinariya, Prashant R Makwana, et al. 2013. Review on determining number of Cluster in K-Means Clustering. International Journal 1, 6 (2013), 90-95.
- Haotian Liu, Chunyuan Li, Qingyang Wu, and Yong Jae Lee. 2023. Visual instruc- tion tuning. arXiv:2304.08485 (2023). · arXiv
- Bryan Perozzi, Bahare Fatemi, Dustin Zelle, Anton Tsitsulin, Mehran Kazemi, Rami Al-Rfou, and Jonathan Halcrow. 2024. Let Your Graph Do the Talking: Encoding Structured Data for LLMs. arXiv:2402.05862 (2024). · arXiv
- Rafael Rafailov, Archit Sharma, Eric Mitchell, Stefano Ermon, Christopher D Manning, and Chelsea Finn. 2023. Direct preference optimization: Your language model is secretly a reward model. arXiv:2305.18290 (2023). · arXiv
- Teven Le Scao, Angela Fan, Christopher Akiki, Ellie Pavlick, Suzana Ilić, Daniel Hesslow, Roman Castagné, Alexandra Sasha Luccioni, François Yvon, Matthias Gallé, et al. 2022. Bloom: A 176b-parameter open-access multilingual language model. arXiv:2211.05100 (2022). · arXiv
- Yanchao Tan, Hang Lv, Xinyi Huang, Jiawei Zhang, Shiping Wang, and Carl Yang. 2024. MuseGraph: Graph-oriented Instruction Tuning of Large Language Models for Generic Graph Mining. arXiv:2403.04780 (2024). · arXiv
- Jiabin Tang, Yuhao Yang, Wei Wei, Lei Shi, Lixin Su, Suqi Cheng, Dawei Yin, and Chao Huang. 2023. Graphgpt: Graph instruction tuning for large language models. arXiv:2310.13023 (2023). · arXiv
- Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. 2023. Llama: Open and efficient foundation language models. arXiv:2302.13971 (2023). · arXiv
- Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. 2023. Llama 2: Open foundation and fine-tuned chat models. arXiv:2307.09288 (2023). · arXiv
- Trieu H Trinh, Yuhuai Wu, Quoc V Le, He He, and Thang Luong. 2024. Solving olympiad geometry without human demonstrations. Nature 625, 7995 (2024), 476-482.
- Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2017. Graph attention networks. In ICLR.
- Heng Wang, Shangbin Feng, Tianxing He, Zhaoxuan Tan, Xiaochuang Han, and Yulia Tsvetkov. 2023. Can Language Models Solve Graph Problems in Natural Language?. In NeurIPS.
- Jianing Wang, Junda Wu, Yupeng Hou, Yao Liu, Ming Gao, and Julian McAuley. 2024. InstructGraph: Boosting Large Language Models via Graph-centric Instruc- tion Tuning and Preference Alignment. arXiv:2402.08785 (2024). · arXiv
- Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. 2022. Self-consistency improves chain of thought reasoning in language models. arXiv:2203.11171 (2022). · arXiv
- Jason Wei, Maarten Bosma, Vincent Zhao, Kelvin Guu, Adams Wei Yu, Brian Lester, Nan Du, Andrew M. Dai, and Quoc V Le. 2022. Finetuned Language Models are Zero-Shot Learners. In ICLR.
- Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2019. How powerful are graph neural networks? ICLR (2019).
- Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. 2022. React: Synergizing reasoning and acting in language models. arXiv:2210.03629 (2022). · arXiv
- Ruosong Ye, Caiqi Zhang, Runhui Wang, Shuyuan Xu, and Yongfeng Zhang. 2023. Natural language is all a graph needs. arXiv:2308.07134 (2023). · arXiv
- Chenyu You, Nuo Chen, Fenglin Liu, Shen Ge, Xian Wu, and Yuexian Zou. 2022. End-to-end Spoken Conversational Question Answering: Task, Dataset and Model. In Findings of NAACL. 1219-1232.
- Chenyu You, Nuo Chen, and Yuexian Zou. 2021. Self-supervised Contrastive Cross-Modality Representation Learning for Spoken Question Answering. In Findings of EMNLP. 28-39.
- Xiang Yue, Xingwei Qu, Ge Zhang, Yao Fu, Wenhao Huang, Huan Sun, Yu Su, and Wenhu Chen. 2023. Mammoth: Building math generalist models through hybrid instruction tuning. arXiv:2309.05653 (2023). · arXiv
- Jianan Zhao, Le Zhuo, Yikang Shen, Meng Qu, Kai Liu, Michael Bronstein, Zhaocheng Zhu, and Jian Tang. 2023. Graphtext: Graph reasoning in text space. arXiv:2310.01089 (2023). · arXiv
- Rui Zheng, Shihan Dou, Songyang Gao, Yuan Hua, Wei Shen, Binghai Wang, Yan Liu, Senjie Jin, Qin Liu, Yuhao Zhou, et al. 2023. Secrets of rlhf in large language models part i: Ppo. arXiv:2307.04964 (2023). · arXiv
- Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc Le, et al. 2022. Least-to-most prompting enables complex reasoning in large language models. arXiv:2205.10625 (2022). · arXiv
Cited by
Sorted by citations
A Review on Edge Large Language Models: Design, Execution, and Applications
Zheng, Y., Chen, Y., Qian, B., Shi, X., Shu, Y., & Chen, J. (2025) · ACM Computing Surveys · doi:10.1145/3719664 · Cited by 169 · see citing works
Graph Foundation Models: Concepts, Opportunities and Challenges
Liu, J., Yang, C. H., Lu, Z., Chen, J., Li, Y., Zhang, M., Bai, T., Fang, Y., Sun, L., Yu, P. S., et al. (2025) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2025.3548729 · Cited by 111 · see citing works
Self-citationG-Refer: Graph Retrieval-Augmented Large Language Model for Explainable Recommendation
Li, Y., Zhang, X., Luo, L., Chang, H., Ren, Y., King, I., & Li, J. (2025) · International World Wide Web Conference (WWW) · doi:10.1145/3696410.3714727 · Cited by 38 · see citing works
Self-citationGraph Machine Learning in the Era of Large Language Models (LLMs)
Wang, S., Huang, J., Chen, Z., Song, Y., Tang, W., Mao, H., Fan, W., Liu, H., Liu, X., Yin, D., et al. (2025) · ACM Transactions on Intelligent Systems and Technology · doi:10.1145/3732786 · Cited by 39 · see citing works
A Survey of Context Engineering for Large Language Models
Mei, L., Yao, J., Ge, Y., Wang, Y., Bi, B., Cai, Y., Liu, J., Li, M., Li, Z.-Z., Zhang, D., et al. (2025) · arXiv · doi:10.48550/arxiv.2507.13334 · Cited by 13 · see citing works
Graph-Based Approaches and Functionalities in Retrieval-Augmented Generation: A Comprehensive Survey
Zhu, Z., Huang, T., Wang, K., Ye, J., Chen, X., & Luo, S. (2026) · ACM Computing Surveys · doi:10.1145/3795880 · Cited by 26 · see citing works
A Survey on Self-Supervised Graph Foundation Models: Knowledge-Based Perspective
Zhao, Z., Su, Y., Li, Y., Zou, Y., Li, R., & Zhang, R. (2025) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2025.3568147 · Cited by 11 · see citing works
Self-citationWang, R., Liang, S., Chen, Q., Zhang, J., & Qin, K. (2025) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/3690624.3709238 · Cited by 9 · see citing works
GraphGPT-o: Synergistic Multimodal Comprehension and Generation on Graphs
Fang, Y., Jin, B., Shen, J., Ding, S., Tan, Q., & Han, J. (2025) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr52734.2025.01813 · Cited by 5 · see citing works
Advancing Graph Foundation Models: A Data-Centric Perspective
Li, Y., Wang, Y., Tang, J., Chang, H., Ren, Y., & Li, J. (2025) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/3711896.3736833 · Cited by 1 · see citing works
Self-citationScalability Matters: Overcoming Challenges in InstructGLM with Similarity-Degree-Based Sampling
Lee, H.-W., Yi, C., Aritra, B. D. S., & Islam, M. (2025) · International Joint Conference on Neural Networks (IJCNN) · doi:10.1109/ijcnn64981.2025.11228376 · Cited by 1 · see citing works
Kurashkin, S. O., Тынченко, В. С., Бородулин, А. С., Hammoud, A., & Connie, T. (2026) · Machine Learning and Knowledge Extraction · doi:10.3390/make8070194 · Cited by 1 · see citing works
Joint Embeddings for Graph Instruction Tuning
HAAG, A. L., Argatu, V., & Lohse, O. (2024) · International Conference on Intelligent Computing in Data Sciences (ICDS) · doi:10.1109/icds62089.2024.10756351
RoutingLLM: Boosting LLM Performance for Network Routing
Wang, D., Zhu, J., Qin, S., Tao, G., Wang, L., Guo, A., & Yang, Y. (2026) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp55912.2026.11461033
Zhou, R., Li, Y., Yan, S., Ma, G., & Huang, Y. (2026) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp55912.2026.11463073
Self-citationComNetLLM: Empowering LLMs for Reliable Communication Network Planning
Zhang, Y., Shi, Q., Li, Z., & Peng, H. (2026) · International Conference on Software Engineering and Information Management (ICSIM) · doi:10.1145/3796315.3796355
Fusing Large Language Model Reasoning with Modularity Optimization for Community DetectionPreprint
He, Y., Liu, C., Zhang, J., Li, R., & Zhan, X. (2026) · SSRN Electronic Journal · doi:10.2139/ssrn.6905318
Think Like a Researcher: A Dataset for Scientific Ideation with Large Language Models
Moska, J., Piasecki, M., & Janz, A. (2026) · Lecture notes in computer science · doi:10.1007/978-3-032-29924-6_35
Collaborative Graph Agents for LLM-Based Graph Reasoning
Li, Z., Wang, J., Wang, F. B., Xing, M., Zhang, Q., Gong, D., & Wang, L. (2026) · Lecture notes in computer science · doi:10.1007/978-981-92-3438-7_25
Learning Hierarchical Knowledge in Text-Rich Networks with Taxonomy-Informed Representation Learning
Liu, Y.-H., Liu, Y., Chen, Y., Hong, C., Zheng, T., & He, T. (2026) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/3770854.3780260
The 1st International Workshop on AI Data Scientist
Liu, H., Žitnik, M., Li, Y., Han, J., Hu, X., & Xie, X. (2026) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/3770855.3818265
Self-citationWang, Z., Ji, Y., Zheng, Z., Zhou, S., Wen, W., Li, M., Gu, M., Zhou, Z., & Bu, J. (2026) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/3770855.3818177
Wang, F., Weng, C., Zhang, X., Hong, S., Liu, H., & Wang, S. (2026) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/3770855.3817637
Graphs Meet AI Agents: Taxonomy, Progress, and Future Opportunities
Bei, Y., Zhang, W., Wang, S., Chen, W., Zhou, S., Chen, H., Li, Y., Bu, J., Pan, S., Yu, Y., et al. (2025) · arXiv · doi:10.48550/arxiv.2506.18019
Self-citation
- Authors
- Chen, N., Li, Y., Tang, J., & Li, J.
- Affiliations
- The Hong Kong University of Science and Technology (Guangzhou) (CN)
- Hong Kong University of Science and Technology (HK)
- Venue
- Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining
- Publisher
- ACM
- Published
- 2024-08-24
- Pages
- 353-364
- OpenAlex
- W4401862897
- Cited by
- 22
- References
- 7
- Citations by year
- 2026: 12 · 2025: 9 · 2024: 1
- FWCI
- 6.35
- Type
- conference paper
- Language
- en
- Open access
- hybrid
- doi.org
- Locations
- ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) (publishedVersion, other-oa)
- Rare & Special e-Zone (The Hong Kong University of Science and Technology) (submittedVersion)
- Funders
- National Natural Science Foundation of China (62206067)
- Hong Kong University of Science and Technology
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Topic Modeling
- Physical Sciences › Computer Science › Artificial Intelligence › Advanced Graph Neural Networks
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Graph Theory and Algorithms
- Keywords
- instruction-tuning dataset, large language models, graph reasoning, direct preference optimization, overfitting, zero-shot transfer
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
