{"id":"6606a97f-722f-4592-8d12-4b35b8c4d83b","arxiv_id":"2501.11478","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"GDL4LLM pre-trains LLMs to predict random-walk sequences of node tokens, then fine-tunes on those sequences for node classification, outperforming description- and embedding-based baselines.","lead":"This paper proposes treating graphs as a new language for large language models: nodes become text tokens and random walks become sentences, and the model is pre-trained on these sentences before fine-tuning for node classification. The authors report strong token savings and small accuracy gains over several graph-LLM baselines on three datasets.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1 is not proven: the appendix's BCE replacement is unjustified and algebraically inconsistent, so the claim that pre-training provably learns graph structure is unsupported.","rationale":"The reader identified the same weakest assumption: Theorem 1 is not actually proven because the appendix substitutes BCE for cross-entropy, leaves P^A undefined, and does not connect the derived equation to the theorem's statement. My stress test confirms this with additional detail: the BCE loss in Eq. 7 is not a well-formed negative-sampling objective, the algebra from Eq. 9 to Eq. 10 is not demonstrated, and the independence assumption contradicts softmax normalization. This is load-bearing because the central contribution is framed as a proof that graph-language pre-training captures structure; without it, the contribution is an empirical framework with moderate accuracy gains and no error bars. The paper does have genuine strengths: the token-efficiency results in Tables 3–4 are concrete, the ablation consistently shows pre-training helps, and the framework is simple and plausible. These do not require rejecting the paper, but they do not rescue the unsupported theorem. The reader's CONDITIONAL verdict is appropriate: the theoretical claim should be corrected or softened, and the empirical claims would benefit from standard deviations and released code or data. My read does not change that verdict, so I mark UNCHANGED.","tokens_in":14022,"tokens_out":6234,"duration_ms":68270,"concrete_test":"Independently re-derive the optimal next-token inner products for the actual cross-entropy loss (Eq. 4) on a random-walk corpus without replacing it with binary cross-entropy and without the independent-pairs assumption. If the derivation cannot produce Eq. 10 with a well-defined P^A and a consistent denominator, then Theorem 1 is unproven as stated and the paper must either supply a correct proof or explicitly demote the claim to an empirical observation. A computational complement would be to train a small softmax language model on random-walk sentences from a synthetic graph with known degrees and compare measured dot products to the claimed logarithmic formula; failure to match would corroborate that the theorem is not valid as written.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central theoretical claim is Theorem 1 (Section 3.1.4): pre-training on graph sentences encodes graph structure through inner products Wh,q · tq ∝ log(I_{(si,q−1,si,q)∈E} · P^A / d_q). The proof in Appendix 7 does not establish this. First, it replaces the actual cross-entropy objective (Eq. 4) with a binary cross-entropy loss (Eq. 7) without justification. In Eq. 7, the 'negative' term is written as #(w,t)·|W|·E_t[log(1/(1+exp(w·t)))], which is not a valid negative-sampling term: it multiplies positive co-occurrence counts by vocabulary size and then samples t, so the loss is not normalized and the pair-specific form in Eq. 8 changes the coefficient to |W|·#(w)·k with k undefined. Second, solving the quadratic in Eq. 9 does not imply the logarithmic form in Eq. 10; the symbol P^A is never defined, and Theorem 1 in the main text has denominator d_q while Eq. 10 has d_q·d_{q−1}, an internal mismatch. Third, the premise that each inner product pair can be optimized independently is incompatible with the softmax normalization in the actual objective: all weight vectors compete through the shared denominator, so optimizing one pair necessarily affects the others. Because the paper explicitly claims 'we prove that the pre-training objective encodes graph structural information,' this proof gap is load-bearing: without a valid derivation, the theoretical foundation is absent, and the method rests only on the ablation in Figure 2, whose gains are modest (0.4–1.6 points).","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces GDL4LLM, a framework that converts a text-attributed graph into a corpus of random-walk 'graph sentences' over special graph tokens, pre-trains an LLM on next-token prediction over this corpus, and then fine-tunes the LLM for node classification. The main claimed contribution is twofold: a theoretical statement (Theorem 1) that pre-training on graph sentences encodes structural information such as node degree, and an empirical demonstration that GDL4LLM outperforms description-based and attribute-embedding baselines on ACM, Wiki, and Amazon while using far fewer tokens.","tokens_in":14453,"tokens_out":3578,"duration_ms":39157,"significance":"If the theoretical claim were valid, it would provide a novel justification for treating graph structure as a language for LLMs, and the concise random-walk representation is a practical contribution. The framework is simple, the efficiency numbers are concrete, and the empirical gains are consistent across three datasets. However, the proof presented for the central theorem is not valid as written, and the empirical margins over strong baselines are small and reported without variance, so the significance of the claimed contributions is currently not fully established.","major_comments":[{"comment":"The proof does not establish Theorem 1. The replacement of the cross-entropy loss (Eq. 4) with a binary cross-entropy loss (Eq. 7) is not justified; the negative-sampling term in Eq. 7 multiplies co-occurrence counts by |W| and then samples t, so it is not a properly normalized negative-sampling loss. Eq. 8 introduces a factor k that is not defined and changes the coefficient from |W| to |W|·#(w)·k. Solving the quadratic in Eq. 9 does not yield a logarithm as claimed in Eq. 10, and the symbol P^A is never defined. The theorem statement in the main text has denominator d_q while Eq. 10 has denominator d_q·d_{q−1}, an internal mismatch. Finally, the premise that each (Wh,q, tq) inner product can be optimized independently is incompatible with the softmax denominator in the actual cross-entropy objective (Eq. 4), where all logits compete. Because the paper explicitly claims to prove that pre-training encodes graph structural information, this proof gap is load-bearing and must be repaired or the claim withdrawn.","section":null},{"comment":"Results are reported as averages over ten runs with no standard deviations or significance tests. Several improvements over the strongest baselines are within one accuracy point (e.g., Wiki test 73.4 vs 73.2; ACM test 82.8 vs 81.3), so the headline claim of outperforming all baselines is not yet supported without variance estimates or statistical tests. Please add error bars, per-run values, or significance tests, and avoid ranking methods on differences that may be noise.","section":null},{"comment":"The ablation in Figure 2 shows pre-training gains of roughly 0.4–1.6 accuracy points, yet the text claims pre-training \"contributes notably\" and creates a \"synergistic effect.\" These statements are stronger than the visual gap warrants, and no error bars are provided. Please temper the claims or provide a statistical basis for them.","section":null}],"minor_comments":[{"comment":"Some citations are incomplete: \"SFGL (Lu et al.)\" and \"LLM-GNN (Chen et al.)\" lack years and are not fully listed in the references. Please complete these entries.","section":null},{"comment":"The first author is listed as \"Huachi Zhou\" in the author block but as \"Huanchi Zhou\" in the footnote. Please correct the inconsistency.","section":null},{"comment":"Table 3's header \"Token/(order)\" is ambiguous, and the repeated \"LLMs -\" label is confusing. Figure 4 uses \"Number k\" and \"Length l\" as axis labels without clarifying that these are the hyperparameters from Section 4.3; please make the notation consistent.","section":null}],"recommendation":"major_revision","confidential_remarks":"The central theoretical claim is currently unsupported by the appendix proof. If the proof cannot be repaired, the authors should explicitly downgrade Theorem 1 to an empirical observation or a conjecture. The empirical pipeline and efficiency results are otherwise of interest, and the paper could be acceptable after the proof claim is corrected or removed and statistical rigor is added."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a useful empirical paper with a broken theory section. The core idea—treat random-walk graph sentences as a 'language' for LLM pre-training, then fine-tune with LoRA—is new as a recipe, and the token/time efficiency numbers in Tables 3 and 4 are concrete and compelling. The ablation in Figure 2 shows pre-training buys a consistent 1–2 points, which is modest but real. If you work on text-attributed graph LLMs, this is worth reading for the method.\n\nThe soft spots, in order of severity. First, Theorem 1 is not proven. The appendix replaces the softmax cross-entropy with a binary cross-entropy objective without justification, defines P^A nowhere, and the algebraic step from Equation 9 to 10 does not follow. The main text says d_q while the appendix has d_q * d_{q−1}. The claim that pairs optimize independently contradicts the shared softmax denominator. So the paper's statement that pre-training 'provably encodes graph structure' is unsupported. This matters because the paper leans on it as a theoretical contribution, but it is not load-bearing for the empirical result—the method could still work even if the theorem is dropped.\n\nSecond, the main accuracy table has no error bars or variance, and the wins over the strongest baselines are often within one point. Ten-run averages are reported, but without spread it is hard to know if the gains are meaningful. This is a standard fix.\n\nThird, the random-walk-as-sentence idea dates back to DeepWalk and node2vec, which are not cited. The framing as 'a new language' is fair enough for the LLM context, but the novelty is in the combination, not the sampling idea.\n\nFourth, no code or data artifacts. For a method paper, that hurts reproducibility.\n\nThe central empirical claim—outperforming description-based and embedding-based baselines—is not circular; it is tested against external baselines. I would send this to serious peer review: the method is solid enough, the issues are addressable, and the efficiency results are worth taking seriously. The authors should either fix or heavily qualify the theorem, add error bars, and cite the older walk-based work.","headline":"The empirical recipe is new and the efficiency gains are real, but the Theorem 1 proof does not hold up—treat the method as plausible and the theory as unsupported.","tokens_in":14929,"tokens_out":2100,"would_cite":true,"duration_ms":21670,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Pre-training an LLM on random-walk graph sentences lets it learn graph structure directly, and the resulting node classifier beats description-based and embedding-based baselines.","keywords":["graph-defined language","LLM pre-training","node classification","text-attributed graphs","random walk","graph tokens","LoRA","graph structure learning"],"falsifier":"Recompute the optimal inner product from the appendix's binary-cross-entropy loss and check whether it equals $\\log\\left(I_{(s_{i,q-1},s_{i,q}) \\in E} P^A / (d_q d_{q-1})\\right)$; if the formula does not emerge, Theorem 1's proof fails, and a separate ablation that replaces random walks with shuffled node sequences of identical token frequencies would show whether structural information is actually what drives the reported gains.","tokens_in":13836,"feed_emoji":"🕸️","tokens_out":8766,"duration_ms":82493,"temperature":0.7,"pith_summary":"The paper proposes GDL4LLM, a framework that treats a graph as if it were a new language. It assigns each node a unique token and samples random-walk paths as graph sentences, then pre-trains a large language model to predict the next token in those sentences. The authors argue that this next-token objective teaches the model graph structure such as node degree and connectivity, and they report that the resulting node-classification model beats graph-description and attribute-embedding baselines on ACM, Wiki, and Amazon. The payoff is that high-order neighborhoods can be represented in a handful of tokens instead of a verbose natural-language description.","feed_headline":"Random-walk sentences teach LLMs graph structure","feed_subtitle":"Pre-training on graph paths beats verbose descriptions for node classification, cutting token use by up to 63 percent.","key_machinery":"The load-bearing mechanism is the graph language corpus built from random walks. Each node is a graph token, and each graph sentence is a path such as `<node_8><node_3><node_10><node_12><node_9>`, so a sentence of length $l$ reaches up to $(l-1)$-hop structure. Pre-training uses next-token likelihood with LoRA adapters and a learned linear projector that turns summaries of node attributes into token embeddings; the theorem is meant to show that this objective stores degree and edge information in the hidden-state/output-weight inner products. During fine-tuning, a second LoRA is learned while the pre-trained LoRA stays frozen, and $k$ sampled sentences starting at the target node supply the structural prompt; appending textual attributes to these sentences adds semantic information.","core_discovery":"The central claim is that graph structure can be transferred into an LLM by treating the graph as a language: nodes become graph tokens, random walks become graph sentences, and next-token prediction on a corpus of such sentences constitutes graph pre-training. The paper's Theorem 1 asserts that, for a sufficiently large model that can optimize each next-token inner product independently, the optimal inner product satisfies $W_{h,q} \\cdot t_q \\propto \\log\\left(\\frac{I_{(s_{i,q-1},s_{i,q}) \\in E} \\cdot P^A}{d_q d_{q-1}}\\right)$, which the authors read as evidence that degree and edge occurrence shape what the model learns. After pre-training, a target node's subgraph is represented by a few sampled graph sentences, so fine-tuning prompts stay short; on ACM, Wiki, and Amazon, GDL4LLM with attributes reaches 82.8, 73.4, and 95.5 test accuracy, respectively, above the compared description-based and embedding-based baselines. The paper also reports lower token counts and faster inference than description-based frameworks.","pith_inferences":["Going beyond the paper, the graph-as-language interface could be pointed at link prediction, edge classification, or graph-level tasks by framing the target as next-token prediction over graph sentences, replacing task-specific heads.","The paper leaves the choice of sentence length $l$ and count $k$ to grid search; a principled rule tied to graph diameter or degree distribution would make the method less tuning-dependent.","A direct test of Theorem 1 on real hidden states, measuring inner products for nodes of different degrees, would connect the idealized proof to the empirical pipeline, which the paper does not attempt."],"forward_implications":["If the theorem's idealization is accepted, pre-training an LLM on any graph's random-walk corpus should endow it with structural knowledge that transfers to downstream node classification on that graph.","The compact graph-sentence prompt means high-order structure can be included without blowing up the context window, which is exactly where description-based methods become verbose.","Because the structure knowledge is stored in LoRA weights and a projector rather than in the base model, the framework should transfer across LLM backbones; the paper demonstrates this on Llama-2 and Llama-3.","The same pre-trained model can be fine-tuned with or without node attributes, so structural and semantic signals can be mixed flexibly depending on the data available."],"supporting_citations":[{"why":"Supplies the LoRA method that keeps pre-training and fine-tuning parameter-efficient.","marker":"Hu et al. 2021"},{"why":"Provides the cross-lingual transfer observation that motivates treating graphs as a new language.","marker":"Zhao et al. 2023"},{"why":"Supplies the argument that natural-language graph descriptions become convoluted, the problem GDL4LLM avoids.","marker":"Fatemi et al. 2024"},{"why":"LLAGA is a description-based baseline whose performance and verbose prompts GDL4LLM is compared against.","marker":"Chen et al. 2024a"},{"why":"GraphAdapter is the LLM-plus-GNN baseline representing the attribute-embedding approach the paper aims to improve.","marker":"Huang et al. 2024"},{"why":"InstructGLM provides the instruction-based description baseline used in the token-efficiency comparison.","marker":"Ye et al. 2024"},{"why":"Supplies the Llama-2-7B backbone on which the main results are measured.","marker":"Touvron et al. 2023"},{"why":"Source of the ACM citation-network dataset used in the experiments.","marker":"Tang et al. 2008"},{"why":"Source of the Amazon product dataset used in the experiments.","marker":"Ni et al. 2019"}],"fun_headline_variants":["Graphs as a language: LLMs learn structure via random walks","Pre-train LLMs on graph sentences, not descriptions","GDL4LLM: Teaching LLMs to read graphs as a language","63% fewer tokens: LLMs learn graphs from random-walk text","From graph to sentence: a new language for LLMs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument rests on Theorem 1's idealization that the model can optimize every next-token inner product independently and that the appendix's binary-cross-entropy derivation yields the stated formula; the appendix substitutes binary cross-entropy without justification and leaves $P^A$ undefined, so if that derivation cannot be repaired the proof that pre-training encodes graph structure does not go through.","fun_headline_variants_meta":{"raw":{"variants":["Graphs as a language: LLMs learn structure via random walks","Pre-train LLMs on graph sentences, not descriptions","GDL4LLM: Teaching LLMs to read graphs as a language","63% fewer tokens: LLMs learn graphs from random-walk text","From graph to sentence: a new language for LLMs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000529,"raw_usage":{"total_tokens":2617,"prompt_tokens":1078,"completion_tokens":1539,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":694,"completion_tokens_details":{"reasoning_tokens":1463}},"tokens_in":694,"tokens_out":1539,"duration_ms":11558,"temperature":1.0,"reasoning_tokens":1463,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T18:13:38.623931+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Recompute the optimal inner product from the appendix's binary-cross-entropy loss and check whether it equals $\\log\\left(I_{(s_{i,q-1},s_{i,q}) \\in E} P^A / (d_q d_{q-1})\\right)$; if the formula does not emerge, Theorem 1's proof fails, and a separate ablation that replaces random walks with shuffled node sequences of identical token frequencies would show whether structural information is actually what drives the reported gains.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Source of the ACM citation-network dataset used in the experiments."}],"review_version":1}