Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

G1: Teaching LLMs to Reason on Graphs with Reinforcement Learning

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Reinforcement learning on synthetic graph problems can turn a 3B LLM into a stronger graph reasoner than a 72B model, and the skill transfers zero-shot to larger graphs and real-world tasks.

desk verdict G1 is a well-executed first application of RLVR/GRPO to LLM graph reasoning with open-sourced code and a large synthetic benchmark, but the headline Erdős numbers rest on a train/test decontamination check that the paper never reports. read the letter →

arxiv 2505.18499 v3 pith:HVFBBWE6 submitted 2025-05-24 cs.LG cs.AIstat.ML

Xiaojun Guo , Ang Li , Yifei Wang , Stefanie Jegelka , Yisen Wang This is my paper
classification cs.LGcs.AIstat.ML
keywords graphreasoninglargelanguagemodelsreinforcementlearningfromverifiablerewardssyntheticdatazero-shotgeneralizationgraph-theoretictasksGRPO
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to establish that reinforcement learning with rule-based rewards on automatically generated graph-theoretic problems can turn an ordinary instruction-tuned LLM into a capable graph reasoner, without human-labeled graph data. To do this the authors build Erdős, a collection of 50 tasks and 100k training questions sampled as small subgraphs of real-world networks, and train G1 with GRPO and verifiable rewards. They report that G1-7B reaches 66.16% average accuracy on the benchmark, roughly matching o3-mini (64.90%), and that G1-3B outperforms Qwen2.5-72B-Instruct despite being about 24 times smaller. They also report zero-shot transfer to larger graphs, to the GraphWiz and GraphArena benchmarks, and to real-world node classification and link prediction. The significance, if true, is that synthetic graph-theoretic tasks suffice to elicit graph reasoning from pretrained LLMs, which is a cheaper and more scalable route than assembling real-world graph instruction data.

What carries the argument

The load-bearing object is the Erdős dataset combined with a rule-based reward model. Erdős contains 50 NetworkX graph-theoretic tasks with 2,000 training questions each, generated as random-walk-with-restart subgraphs of real-world graphs with 5 to 35 nodes, with answers produced by library solvers and by algorithmic verifiers. The reward is not a learned judge: it is strict value matching for unique answers, Jaccard index for set answers, and algorithmic verification for answers with multiple valid solutions. GRPO uses these rewards to compute group-relative advantages, which is what turns correct and incorrect rollouts into a training signal without human annotations.

What would settle it

Re-run the benchmark with train subgraphs and test subgraphs drawn from disjoint source graphs, or at least node-disjoint subgraphs, and recompute hard-task labels with independently verified exact solvers; if the accuracy gap over base models collapses or the labels differ, the claimed scaling is partly in-distribution alignment rather than learned graph reasoning.

Watch

Extended reading notes

Core claim

Reinforcement learning from verifiable rewards on synthetic graph-theoretic problems can elicit substantial graph reasoning ability from pretrained LLMs as small as 3B parameters, and the elicited ability transfers beyond the training distribution. The paper's central evidence is that RL-trained G1-7B reaches 66.16% average accuracy on the 50-task Erdős benchmark, close to o3-mini's 64.90%, while G1-3B reaches 59.76% and beats Qwen2.5-72B-Instruct (47.16%) with roughly 24x fewer parameters. RL also shifts solution strategy: on shortest path the models move from brittle Dijkstra-style bookkeeping toward BFS and heuristic tracing, and the authors show that CoT-SFT warm-up mainly helps the hardest tasks. The authors interpret these results as showing that LLMs already contain graph understanding from pretraining, and that RL is what activates it.

Load-bearing premise

The accuracy numbers assume the 100,000 training questions and the 5,000 test questions are independent, but both are downsampled from the same real-world source graphs by random walk with restart and the paper does not describe a disjoint split; they also assume the library's default solvers give correct labels for NP-hard tasks.

Editorial extensions

If this is right

  • A 3B model trained this way surpasses a 72B instruction model on graph reasoning, so model scale is not the binding constraint for graph tasks if suitable RL data is available.
  • Graph reasoning learned on 5-35 node subgraphs transfers zero-shot to 36-100 node graphs, suggesting the trained skill is structural rather than tied to a particular graph size.
  • Training on one edge-list encoding transfers to other encodings and to real-world node classification and link prediction, so the method does not overfit a single prompt format.
  • RL training on graph tasks did not degrade general math and language reasoning; on GSM8K, MATH, and MMLU-Pro, G1-7B slightly exceeds its base model.
  • Training only on Hard and Challenging tasks improves those categories and still helps easier ones, implying that hard-task RL confers transferable reasoning skills.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same recipe could be applied to other structured data with verifiable answers, such as tabular operations or temporal reasoning, making RL on synthetic rule-based tasks a general post-training strategy rather than a graph-specific trick.
  • The reward-weighting experiments point toward a simple improvement: explicitly down-weight easy tasks or schedule difficulty dynamically, which the paper leaves for future work but which the reported soft-scaling results already suggest raises challenging-task accuracy.
  • Because the shortest-path case study shows RL pushing models toward BFS-like execution, one could test directly whether prompting G1 to run a traversal algorithm rather than free-form reasoning narrows the remaining gap on hard tasks.
  • A direct probe of the learned skill is whether G1 can compose two graph operations in a single prompt, since the benchmark tasks are presented one at a time and the paper does not test multi-step graph reasoning chains.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper introduces Erdős, a 50-task graph-theoretic benchmark (100k training, 5k test questions) constructed from random-walk-with-restart subgraphs of Network Repository real-world graphs, and proposes G1, a GRPO-based reinforcement-learning recipe with an optional CoT-SFT warm-up. On the Erdős test set, G1-3B and G1-7B achieve 59.76% and 66.16% average accuracy, respectively, surpassing several larger open-source instruction models and roughly matching OpenAI o3-mini. The authors also report zero-shot transfer to larger graphs, to the GraphWiz and GraphArena benchmarks, and to real-world node classification and link prediction tasks, with preserved or improved general math/MMLU performance.

Significance. If the results hold, this is a meaningful contribution: it demonstrates that verifiable-reward RL on synthetic graph-theoretic tasks can substantially improve graph reasoning in small LLMs, and the open-sourced implementation, models, and dataset enable independent reproduction. The paper's strengths include 32-seed robustness runs, prompt-variant sensitivity checks, and a reward design that uses rule-based correctness rather than model-based judges; there is no equation-level circularity in the training objective. The main threats to the headline claims are the unresolved train/test decontamination of the primary Erdős split, the reliance on approximate NetworkX solvers for NP-hard ground truths, and an overstatement of 'unseen task' generalization.

major comments (3)
  1. [Section 3 (Graph Sources) and Appendix D] Section 3 states that both the 100k training questions and the 5k test questions are generated by random-walk-with-restart subgraphs sampled from the same Network Repository graphs, and it describes the test split only as containing 'different questions.' It never states that source graphs, sampled subgraphs, or node sets are disjoint between train and test. In contrast, Appendix D explicitly says the larger-graph test set 'ensures there is no overlap between training and test data,' which implies the main 5k split lacks such a guarantee. If test subgraphs share nodes or edges with training subgraphs, in-distribution accuracy can be inflated by memorization of answers or local graph structures, and every headline number in Table 2 (G1-3B above Qwen2.5-72B, G1-7B roughly matching o3-mini) depends on this test set. Please construct a node-disjoint or source-disjoint split, quantify the overlap between the current train and test subgraphs, and report the main results on a provably non-overlapping subset.
  2. [Section 3 (Answer Generation)] The golden answers for NP-hard tasks such as minimum vertex cover, dominating set, and TSP are generated by 'the default solvers of NetworkX.' NetworkX's default solvers for several of these problems are approximation algorithms rather than exact solvers (e.g., min_weighted_vertex_cover and dominating_set are approximate/greedy, and the default TSP method is a Christofides-style heuristic). If the labels are approximate, the RL reward and the reported accuracies measure alignment with a particular solver, not correctness on the true graph problem: a model producing a genuinely better solution than the approximate label would be scored wrong, while a worse but valid solution could be scored right. Please audit the labels for all small (5-35 node) instances with exact or brute-force solvers, or restrict the benchmark to tasks with exact labels and re-report the affected task-level numbers in Table 23.
  3. [Section 5.2.1, Abstract, and Contributions] The paper repeatedly claims zero-shot generalization to 'unseen tasks' via GraphWiz and GraphArena, but many of the tasks on those benchmarks are also present in Erdős: topological sort, shortest path, maximum flow, Hamiltonian path, common neighbor, connected components, diameter, min vertex cover, and TSP all appear in Table 1. The transfer results are still informative for shifts in graph distribution and encoding, but they do not support the 'unseen tasks' claim. Please either evaluate on genuinely held-out tasks (for example, an Erdős task-group holdout) or revise the claim to say that the model transfers to new graph distributions and encodings on partially overlapping task families.
minor comments (4)
  1. [Tables 21 and 22] In Table 21 the Qwen2.5-7B-Instruct row is labeled '(Ours)', which is confusing because this is the base model; Table 22 correctly labels the same row as '(base)'. Please make the labels consistent.
  2. [Appendix J] The reward scaling factors for G1-Soft-3B (0.2, 0.4, 0.6, 0.8) appear to have been selected using the same Erdős test set on which the final accuracy is reported. If so, this is a form of test-set tuning; please present it as a validation ablation or add a held-out selection procedure so that the 60.38% number is not interpreted as a fixed-configuration test result.
  3. [Table 8] The statement that G1 improves general reasoning 'without compromising' abilities should be qualified at the 3B scale: G1-3B is 1.1 points below the base model on MATH and 1.4 points below on MMLU-Pro, although G1-7B does improve on all three benchmarks.
  4. [Abstract and Table 23] There are several typographical errors, including 'drived' in the abstract, 'fintuned' in the contributions list, and 'isomophic_mapping' in Table 23; these should be corrected.

Circularity Check

0 steps flagged · score 0.0 of 10

No equation-level circularity; the central RL scaling claim is supported by external benchmarks, and the train/test overlap concern is a validity caveat, not a circular reduction.

full rationale

The paper's central claim is an empirical scaling result: RL with rule-based rewards on synthetic graph tasks improves LLM graph reasoning. The reward (Eqs. 1-2, Section 4.1) is a verifiable correctness signal computed by NetworkX; model outputs are not defined in terms of the evaluation metric, and the evaluation set is described as a separately reserved set of 5,000 different questions (Section 3). The strongest evidence is self-contained against external benchmarks: GraphWiz, GraphArena, Cora/PubMed, GSM8K, MATH, and MMLU-Pro (Tables 5-8), so the central 'elicited graph reasoning' claim does not reduce to a fitted parameter or to the training objective. The main caveats are validity concerns, not circularity: the 100k training and 5k test questions are both downsampled by random walk with restart from the same Network Repository graphs, and the paper explicitly guarantees no train/test overlap only for the larger-graph set in Appendix D, so possible subgraph overlap could inflate in-distribution accuracies; similarly, NetworkX default solvers define the ground truth for NP-hard tasks. These are benchmark-hygiene issues, not cases where a prediction is equivalent to its input by construction. The self-citation [48] in Section 5.4 is not load-bearing, and no equation-level circularity is present.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

The central claim rests on the correctness of program-generated labels, the independence of train/test graph samples, the representativeness of the base LLM, and the choice of edge-list encoding. None of these are derived in the paper; they are assumptions from external tools and design choices.

free parameters (3)
  • GRPO hyperparameters = epsilon=0.2, KL beta=1e-3, group size G=5, entropy coefficient 1e-3, temperature 1.0
    Hand-chosen standard RLVR settings (Appendix A.3); the central claim that RL improves graph reasoning depends on this configuration, though the paper does not test sensitivity to them.
  • Reward scaling factors for G1-Soft = 0.2 (Easy), 0.4 (Medium), 0.6 (Hard), 0.8 (Challenging)
    Chosen by hand in Appendix J to balance difficulty-level rewards; these are used for the G1-Soft variant, not the main G1 model, and were selected with knowledge of benchmark performance.
  • SFT warm-up data size = about 4,500 examples (about 90 per task)
    Obtained by rejection sampling from Qwen2.5-32B-Instruct with k=8; the volume is a choice that affects CoT-SFT results, though the main G1-Zero result does not use it.
assumptions (5)
  • ad hoc to paper NetworkX default solvers produce correct golden answers for all 50 tasks
    Invoked in Section 3 (Answer Generation). For NP-hard tasks such as minimum vertex cover, dominating set, and TSP, default NetworkX solvers may return approximate solutions, so labels may not be true optima.
  • domain assumption Train and test questions are independent despite being downsampled from the same real-world graph sources
    Invoked in Section 3 (Graph Sources) and Section 5.1. The paper does not describe a source-disjoint split or contamination check, so the 5k test pairs may share subgraph structure with the 100k training pairs.
  • domain assumption Qwen2.5-Instruct base models are representative pretrained LLMs whose latent graph abilities can be elicited
    All G1 models are fine-tuned from Qwen2.5-Instruct (Section 5.1); the claim that RL 'elicits' latent ability assumes the base model has some graph competence, supported by nonzero baseline accuracy.
  • ad hoc to paper Edge-list text encoding is a sufficient interface for graph reasoning
    Section 3 (Language Encoding) chooses a unified edge-list format; the paper shows positive transfer to other encodings, but the training interface itself is a design choice.
  • domain assumption Random-walk downsampled subgraphs of size 5-35 are representative of real-world graphs
    Section 3 (Graph Sources) uses these subgraphs for both training and evaluation; the paper does not validate that this downsampling preserves the properties relevant to each task.

how reviews work

0 comments
Cite this review

Pith. "Pith review of G1: Teaching LLMs to Reason on Graphs with Reinforcement Learning." pith.science (2026). https://pith.science/paper/HVFBBWE6

@misc{pith2026250518499,
  author       = {Pith},
  title        = {Pith review of: G1: Teaching LLMs to Reason on Graphs with Reinforcement Learning},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HVFBBWE6}},
  note         = {Machine review of arXiv:2505.18499}
}
read the original abstract

Although Large Language Models (LLMs) have demonstrated remarkable progress, their proficiency in graph-related tasks remains notably limited, hindering the development of truly general-purpose models. Previous attempts, including pretraining graph foundation models or employing supervised fine-tuning, often face challenges such as the scarcity of large-scale, universally represented graph data. We introduce G1, a simple yet effective approach demonstrating that Reinforcement Learning (RL) on synthetic graph-theoretic tasks can significantly scale LLMs' graph reasoning abilities. To enable RL training, we curate Erd\~os, the largest graph reasoning dataset to date comprising 50 diverse graph-theoretic tasks of varying difficulty levels, 100k training data and 5k test data, all drived from real-world graphs. With RL on Erd\~os, G1 obtains substantial improvements in graph reasoning, where our finetuned 3B model even outperforms Qwen2.5-72B-Instruct (24x size). RL-trained models also show strong zero-shot generalization to unseen tasks, domains, and graph encoding schemes, including other graph-theoretic benchmarks as well as real-world node classification and link prediction tasks, without compromising general reasoning abilities. Our findings offer an efficient, scalable path for building strong graph reasoners by finetuning LLMs with RL on graph-theoretic tasks, which combines the strengths of pretrained LLM capabilities with abundant, automatically generated synthetic data, suggesting that LLMs possess graph understanding abilities that RL can elicit successfully. Our implementation is open-sourced at https://github.com/PKU-ML/G1, with models and datasets hosted on Hugging Face collections https://huggingface.co/collections/PKU-ML/g1-683d659e992794fc99618cf2 for broader accessibility.

Figures

Figures reproduced from arXiv: 2505.18499 by the authors.

Figure 1
Figure 1. Test accuracy comparison of [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. An intuitive illustration of the differences in solution strategies employed by Qwen2.5-3B [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. Reasoning patterns for the shortest path task. [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Test accuracy comparison of G1-7B and G1-Zero-7B on our benchmark. In Section 5.3, we study the role of SFT as a cold-start mechanism for RL by comparing two variants: G1- Zero-3B that is directly trained from the base model Qwen2.5-3B-Instruct with RL, and G1-3B that …

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Lost in Serialization: Invariance and Generalization of LLM Graph Reasoners

    cs.LG 2025-11 conditional novelty 6.0 of 10

    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.

Reference graph

Works this paper leans on

56 extracted references · 36 canonical work pages · cited by 1 Pith paper

  1. [1]

    Llama3 foundation models

    AI, M. Llama3 foundation models. https://www.llama.com/models/llama-3/, 2024

    work page 2024

  2. [2]

    and Albert, R

    Barabási, A.-L. and Albert, R. Emergence of scaling in random networks. science, 286(5439): 509–512, 1999

    work page 1999

  3. [3]

    Brown, T. B., Mann, B., Ryder, N., Subbiah, M., Kaplan, J., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., Agarwal, S., Herbert-V oss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D. M., Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCandlish, S., Radford,...

    work page 2020

  4. [4]

    Graphwiz: An instruction-following language model for graph computational problems

    Chen, N., Li, Y ., Tang, J., and Li, J. Graphwiz: An instruction-following language model for graph computational problems. In SIGKDD, 2024

    work page 2024

  5. [5]

    V ., Levine, S., and Ma, Y

    Chu, T., Zhai, Y ., Yang, J., Tong, S., Xie, S., Schuurmans, D., Le, Q. V ., Levine, S., and Ma, Y . Sft memorizes, rl generalizes: A comparative study of foundation model post-training, 2025. URL https://arxiv.org/abs/2501.17161

    arXiv 2025

  6. [6]

    Graphsos: Graph sampling and order selection to help llms understand graphs better

    Chu, X., Xue, H., Tan, Z., Wang, B., Mo, T., and Li, W. Graphsos: Graph sampling and order selection to help llms understand graphs better. arXiv e-prints, pp. arXiv–2501, 2025

    work page 2025

  7. [8]

    Training verifiers to solve math word problems

    Cobbe, K., Kosaraju, V ., Bavarian, M., Chen, M., Jun, H., Kaiser, L., Plappert, M., Tworek, J., Hilton, J., Nakano, R., et al. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168, 2021

    arXiv 2021

  8. [9]

    How do large language models understand graph patterns? a benchmark for graph pattern comprehension

    Dai, X., Qu, H., Shen, Y ., Zhang, B., Wen, Q., Fan, W., Li, D., Tang, J., and Shan, C. How do large language models understand graph patterns? a benchmark for graph pattern comprehension. In ICLR, 2025

    work page 2025

Show all 56 references
  1. [10]

    Which modality should i use–text, motif, or image?: Understanding graphs with large language models

    Das, D., Gupta, I., Srivastava, J., and Kang, D. Which modality should i use–text, motif, or image?: Understanding graphs with large language models. In NAACL, 2024. 11

    2024

  2. [11]

    Erdös-rényi model

    Erdös, P. Erdös-rényi model. Publ. Math. Debrecen, pp. 290–297, 1959

    1959

  3. [12]

    Talk like a graph: Encoding graphs for large language models

    Fatemi, B., Halcrow, J., and Perozzi, B. Talk like a graph: Encoding graphs for large language models. arXiv preprint arXiv:2310.04560, 2023

    2023 arXiv

  4. [13]

    Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning

    Guo, D., Yang, D., Zhang, H., Song, J., Zhang, R., Xu, R., Zhu, Q., Ma, S., Wang, P., Bi, X., et al. Deepseek-r1: Incentivizing reasoning capability in llms via reinforcement learning. arXiv preprint arXiv:2501.12948, 2025

    2025 arXiv

  5. [14]

    A., Schult, D

    Hagberg, A. A., Schult, D. A., and Swart, P. J. Exploring network structure, dynamics, and function using networkx. In Proceedings of the 7th Python in Science Conference, 2008

    2008

  6. [15]

    Inductive representation learning on large graphs

    Hamilton, W., Ying, Z., and Leskovec, J. Inductive representation learning on large graphs. In NeurIPS, 2017

    2017

  7. [16]

    Measuring mathematical problem solving with the math dataset

    Hendrycks, D., Burns, C., Kadavath, S., Arora, A., Basart, S., Tang, E., Song, D., and Steinhardt, J. Measuring mathematical problem solving with the math dataset. In NeurIPS, 2021

    2021

  8. [17]

    Ruler: What’s the real context size of your long-context language models? arXiv preprint arXiv:2404.06654, 2024

    Hsieh, C.-P., Sun, S., Kriman, S., Acharya, S., Rekesh, D., Jia, F., Zhang, Y ., and Ginsburg, B. Ruler: What’s the real context size of your long-context language models? arXiv preprint arXiv:2404.06654, 2024

    2024 arXiv

  9. [18]

    Knowledge graph embedding based question answering

    Huang, X., Zhang, J., Li, D., and Li, P. Knowledge graph embedding based question answering. In WSDM, 2019

    2019

  10. [19]

    and Loukas, A

    Karalias, N. and Loukas, A. Erdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs. In NeurIPS, 2020

    2020

  11. [20]

    Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907, 2016

    2016 arXiv

  12. [21]

    Gofa: A generative one-for-all model for joint graph language modeling

    Kong, L., Feng, J., Liu, H., Huang, C., Huang, J., Chen, Y ., and Zhang, M. Gofa: A generative one-for-all model for joint graph language modeling. In ICLR, 2025

    2025

  13. [22]

    H., Gonzalez, J

    Kwon, W., Li, Z., Zhuang, S., Sheng, Y ., Zheng, L., Yu, C. H., Gonzalez, J. E., Zhang, H., and Stoica, I. Efficient memory management for large language model serving with pagedattention. In SIGOPS, 2023

    2023

  14. [23]

    Can large language models analyze graphs like professionals? a benchmark, datasets and models

    Li, X., Chen, W., Chu, Q., Li, H., Sun, Z., Li, R., Qian, C., Wei, Y ., Shi, C., Liu, Z., et al. Can large language models analyze graphs like professionals? a benchmark, datasets and models. In NeurIPS, 2024

    2024

  15. [24]

    Can one domain help others? a data-centric study on multi-domain reasoning via reinforcement learning

    Li, Y ., Pan, Z., Lin, H., Sun, M., He, C., and Wu, L. Can one domain help others? a data-centric study on multi-domain reasoning via reinforcement learning. arXiv preprint arXiv:2507.17512, 2025

    2025 arXiv

  16. [25]

    Let’s verify step by step

    Lightman, H., Kosaraju, V ., Burda, Y ., Edwards, H., Baker, B., Lee, T., Leike, J., Schulman, J., Sutskever, I., and Cobbe, K. Let’s verify step by step. arXiv preprint arXiv:2305.20050, 2023

    2023 arXiv

  17. [26]

    One for all: Towards training one graph model for all classification tasks

    Liu, H., Feng, J., Kong, L., Liang, N., Tao, D., Chen, Y ., and Zhang, M. One for all: Towards training one graph model for all classification tasks. In ICLR, 2024

    2024

  18. [27]

    Graphinstruct: Empowering large language models with graph understanding and reasoning capability

    Luo, Z., Song, X., Huang, H., Lian, J., Zhang, C., Jiang, J., and Xie, X. Graphinstruct: Empowering large language models with graph understanding and reasoning capability. arXiv preprint arXiv:2403.04483, 2024

    2024

  19. [28]

    Position: Graph foundation models are already here

    Mao, H., Chen, Z., Tang, W., Zhao, J., Ma, Y ., Zhao, T., Shah, N., Galkin, M., and Tang, J. Position: Graph foundation models are already here. In ICML, 2024

    2024

  20. [29]

    W., Songhori, E., Wang, S., Lee, Y .-J., Johnson, E., Pathak, O., Nova, A., et al

    Mirhoseini, A., Goldie, A., Yazgan, M., Jiang, J. W., Songhori, E., Wang, S., Lee, Y .-J., Johnson, E., Pathak, O., Nova, A., et al. A graph placement methodology for fast chip design. Nature, 594(7862):207–212, 2021. 12

    2021

  21. [30]

    OpenAI, :, Jaech, A., Kalai, A., Lerer, A., Richardson, A., El-Kishky, A., Low, A., Helyar, A., Madry, A., Beutel, A., Carney, A., Iftimie, A., Karpenko, A., Passos, A. T., Neitz, A., Prokofiev, A., Wei, A., Tam, A., Bennett, A., Kumar, A., Saraiva, A., Vallone, A., Duberstein...

    2024 arXiv

  22. [31]

    Let your graph do the talking: Encoding structured data for llms

    Perozzi, B., Fatemi, B., Zelle, D., Tsitsulin, A., Kazemi, M., Al-Rfou, R., and Halcrow, J. Let your graph do the talking: Encoding structured data for llms. arXiv preprint arXiv:2402.05862, 2024

    2024 arXiv

  23. [32]

    Qwen2.5 technical report, 2025

    Qwen, :, Yang, A., Yang, B., Zhang, B., Hui, B., Zheng, B., Yu, B., Li, C., Liu, D., Huang, F., Wei, H., Lin, H., Yang, J., Tu, J., Zhang, J., Yang, J., Yang, J., Zhou, J., Lin, J., Dang, K., Lu, K., Bao, K., Yang, K., Yu, L., Li, M., Xue, M., Zhang, P., Zhu, Q., Men, R., Lin,...

    2025

  24. [33]

    Rossi, R. A. and Ahmed, N. K. The network data repository with interactive graph analytics and visualization. In AAAI, 2015. URL http://networkrepository.com

    2015

  25. [34]

    Understanding transformer reasoning capabilities via graph algorithms

    Sanford, C., Fatemi, B., Hall, E., Tsitsulin, A., Kazemi, M., Halcrow, J., Perozzi, B., and Mirrokni, V . Understanding transformer reasoning capabilities via graph algorithms. In NeurIPS, 2024

    2024

  26. [35]

    Approximation ratios of graph neural networks for combinatorial problems

    Sato, R., Yamada, M., and Kashima, H. Approximation ratios of graph neural networks for combinatorial problems. In NeurIPS, 2019

    2019

  27. [36]

    Deepseekmath: Pushing the limits of mathematical reasoning in open language models

    Shao, Z., Wang, P., Zhu, Q., Xu, R., Song, J., Bi, X., Zhang, H., Zhang, M., Li, Y ., Wu, Y ., et al. Deepseekmath: Pushing the limits of mathematical reasoning in open language models. arXiv preprint arXiv:2402.03300, 2024

    2024 arXiv

  28. [37]

    Mastering the game of go without human knowledge

    Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A., Chen, Y ., Lillicrap, T., Hui, F., Sifre, L., van den Driessche, G., Graepel, T., and Hassabis, D. Mastering the game of go without human knowledge. Na...

    2017

  29. [38]

    Grapharena: Benchmarking large language models on graph computational problems

    Tang, J., Zhang, Q., Li, Y ., and Li, J. Grapharena: Benchmarking large language models on graph computational problems. In ICLR, 2025

    2025

  30. [39]

    Qwen2.5: A party of foundation models, September 2024

    Team, Q. Qwen2.5: A party of foundation models, September 2024. URL https://qwenlm. github.io/blog/qwen2.5/

    2024

  31. [40]

    Neural execution of graph algorithms

    Veliˇckovi´c, P., Ying, R., Padovano, M., Hadsell, R., and Blundell, C. Neural execution of graph algorithms. In ICLR, 2020

    2020

  32. [41]

    Gcn-rl circuit designer: Transferable transistor sizing with graph neural networks and reinforcement learning

    Wang, H., Wang, K., Yang, J., Shen, L., Sun, N., Lee, H.-S., and Han, S. Gcn-rl circuit designer: Transferable transistor sizing with graph neural networks and reinforcement learning. In 2020 57th ACM/IEEE Design Automation Conference (DAC), pp. 1–6. IEEE, 2020

    2020

  33. [42]

    Can language models solve graph problems in natural language? In NeurIPS, 2023

    Wang, H., Feng, S., He, T., Tan, Z., Han, X., and Tsvetkov, Y . Can language models solve graph problems in natural language? In NeurIPS, 2023

    2023

  34. [43]

    Instructgraph: Boosting large language models via graph-centric instruction tuning and preference alignment

    Wang, J., Wu, J., Hou, Y ., Liu, Y ., Gao, M., and McAuley, J. Instructgraph: Boosting large language models via graph-centric instruction tuning and preference alignment. In ACL, 2024

    2024

  35. [44]

    Mmlu-pro: A more robust and challenging multi-task language understanding benchmark, 2024

    Wang, Y ., Ma, X., Zhang, G., Ni, Y ., Chandra, A., Guo, S., Ren, W., Arulraj, A., He, X., Jiang, Z., Li, T., Ku, M., Wang, K., Zhuang, A., Fan, R., Yue, X., and Chen, W. Mmlu-pro: A more robust and challenging multi-task language understanding benchmark, 2024. URL https://arx...

    2024 arXiv

  36. [45]

    Exploring graph tasks with pure llms: A comprehensive benchmark and investigation

    Wang, Y ., Dai, X., Fan, W., and Ma, Y . Exploring graph tasks with pure llms: A comprehensive benchmark and investigation. arXiv preprint arXiv:2502.18771, 2025

    2025

  37. [46]

    V ., Zhou, D., et al

    Wei, J., Wang, X., Schuurmans, D., Bosma, M., Xia, F., Chi, E., Le, Q. V ., Zhou, D., et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824–24837, 2022

    2022

  38. [47]

    Wu, Q., Chen, Z., Corcoran, W., Sra, M., and Singh, A. K. Grapheval2000: Benchmarking and improving large language models on graph datasets. arXiv preprint arXiv:2406.16176, 2024

    2024 arXiv

  39. [48]

    When more is less: Understanding chain-of-thought length in llms

    Wu, Y ., Wang, Y ., Du, T., Jegelka, S., and Wang, Y . When more is less: Understanding chain-of-thought length in llms. arXiv preprint arXiv:2502.07266, 2025

    2025 arXiv

  40. [49]

    Graphomni: A comprehensive and extendable benchmark framework for large language models on graph-theoretic tasks

    Xu, H., Jian, X., Zhao, X., Pang, W., Zhang, C., Wang, S., Zhang, Q., Monteiro, J., Sun, Q., and Yu, T. Graphomni: A comprehensive and extendable benchmark framework for large language models on graph-theoretic tasks. arXiv preprint arXiv:2504.12764, 2025

    2025

  41. [50]

    How powerful are graph neural networks? arXiv preprint arXiv:1810.00826, 2018

    Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? arXiv preprint arXiv:1810.00826, 2018

    2018 arXiv

  42. [51]

    How powerful are graph neural networks? In ICLR, 2019

    Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? In ICLR, 2019

    2019

  43. [52]

    S., Kawarabayashi, K.-i., and Jegelka, S

    Xu, K., Li, J., Zhang, M., Du, S. S., Kawarabayashi, K.-i., and Jegelka, S. What can neural networks reason about? arXiv preprint arXiv:1905.13211, 2019

    1905 arXiv

  44. [53]

    Qwen2.5-math technical report: Toward mathematical expert model via self-improvement

    Yang, A., Zhang, B., Hui, B., Gao, B., Yu, B., Li, C., Liu, D., Tu, J., Zhou, J., Lin, J., Lu, K., Xue, M., Lin, R., Liu, T., Ren, X., and Zhang, Z. Qwen2.5-math technical report: Toward mathematical expert model via self-improvement. arXiv preprint arXiv:2409.12122, 2024

    2024 arXiv

  45. [54]

    Language is all a graph needs

    Ye, R., Zhang, C., Wang, R., Xu, S., and Zhang, Y . Language is all a graph needs. InECAL, 2024

    2024

  46. [55]

    Scaling relationship on learning mathematical reasoning with large language models

    Yuan, Z., Yuan, H., Li, C., Dong, G., Lu, K., Tan, C., Zhou, C., and Zhou, J. Scaling relationship on learning mathematical reasoning with large language models. arXiv preprint arXiv:2308.01825, 2023

    2023 arXiv

  47. [56]

    Gracore: Benchmarking graph comprehension and complex reasoning in large language models

    Yuan, Z., Liu, M., Wang, H., and Qin, B. Gracore: Benchmarking graph comprehension and complex reasoning in large language models. In COLING, 2025

    2025

  48. [57]

    c", C, N); dot(

    Zhang, M. and Chen, Y . Link prediction based on graph neural networks. In NeurIPS, 2018. 14 A Training Details A.1 Rejection Sampling We randomly extract a subset with 100 examples per task from the training dataset, and use Qwen2.5- 32B-Instruct to sample on the subset for k...

    2018

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.