acceptodds
Under review as a conference paper at ICLR 2027

ReGraph: Iterative Graph Reading for Open-Ended Reasoning with Large Language Models

Abstract

Open-ended graph reasoning should allow Large Language Models (LLMs) to decide what to read from a graph as their reasoning unfolds. Yet existing approaches typically expose graph information either as retrieved text or as a fixed representation formed before reasoning begins, limiting how graph evidence can adapt to the evolving language-model state. We introduce ReGraph (**Re**ad **Graph**), an iterative graph-reading framework that interleaves graph access with intermediate LLM computation. ReGraph maintains a persistent graph memory and repeatedly queries it with graph-query states refined by preceding Transformer layers, enabling each read to depend on both the instruction and evidence acquired so far. A query-conditioned topology diffusion mechanism further couples semantic relevance with graph structure, while keeping the graph outside the LLM context and the pretrained LLM frozen. Experiments on six benchmarks, including two introduced in this work, demonstrate the effectiveness of ReGraph across open-ended graph reasoning settings. The source code is available [here](https://anonymous.4open.science/r/ReGraph-submit).

Primary area:
foundation or frontier models, including LLMs
Keywords:
Large language model, Open-ended graph reasoning

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_cbrwOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

Assessment: This paper proposes REGRAPH, an iterative graph-reading framework that uses evolving intermediate LLM states to repeatedly query a persistent graph memory. Its topology-diffused graph reader combines semantic relevance with graph structure, while the pretrained LLM remains frozen. The framework is evaluated on six benchmarks, including two newly introduced datasets.

AI use: use AI to polish and expand the texts for reviews below.

Critical strengths
  1. The main idea is intuitive and reasonably novel: graph evidence is retrieved repeatedly using query states that evolve across intermediate Transformer layers.
  2. The Single-read / Static replay / REGRAPH comparison is a useful control and provides evidence that adaptive rereading is beneficial.
  3. The paper includes several useful diagnostic experiments, including graph perturbations, distractor robustness, and generalization tests.
  4. The presentation is generally clear and technically well organized.
Critical weaknesses
  1. The main comparisons do not fully isolate iterative reading. Many baselines use different LLM backbones, graph encoders, and training protocols. A same-backbone, same-encoder static graph interface would provide a much cleaner comparison.
  2. Important components are insufficiently ablated. The paper would benefit from ablations on topology diffusion, learned hop mixtures, evidence gating, number of graph-reading rounds, and number of graph-query tokens.
  3. The “open-ended reasoning” claim feels somewhat overstated. Most benchmarks have constrained answer spaces, while on SceneGraphs—the most open-ended benchmark—REGRAPH substantially underperforms G-Retriever-based methods (53.24 vs. 81.31/86.83).
  4. Scalability remains unclear. Each read attends over the graph nodes, while most experiments involve relatively small graphs and the size extrapolation only reaches 512 nodes. It is unclear how the method would scale to genuinely large graphs.
  5. The paper describes StructuralAnomaly’s density-free control as important for detecting leakage, but the corresponding control result should be reported more explicitly.
Questions for authors
  1. Under the same backbone and graph encoder, how does REGRAPH compare with a strong static graph interface or retrieval baseline on representative tasks? Which entries in Tables 1–2 were rerun, and with which backbones, supervision, and splits?
  2. How does REGRAPH perform with the same graph memory and three-read schedule but no topology diffusion, and with a fixed rather than learned hop mixture? How stable are the adaptive-versus-static gains across repeated training runs?
  3. What accuracy does the StructuralAnomaly density-free control achieve, and how are unsupported-claim rate and required-fact recall computed (claim extraction, support matching, required-fact annotation, aggregation, and sample counts)?
  4. How do latency and memory scale as the supplied graph grows?
9 comments
AuthorsOpenReview ↗

Response to Reviewer cbrw (part 1)

Q1: The main comparisons do not fully isolate iterative reading. Many baselines use different LLM backbones, graph encoders, and training protocols. A same-backbone, same-encoder static graph interface would provide a much cleaner comparison.

A1: For the first concern, to isolate iterative reading itself, we compare the reading schedules of Table 5 in the paper, which share ReGraph’s backbone, encoder, parameters and training and differ only in how the graph is read: Single-read accesses the graph once, and static replay re-injects the first read’s evidence at all three reading boundaries. Results are as the the table below:

Reading schedule (shared backbone, encoder, training)SceneGraphsNeighborhoodQA
Single-read47.7380.25
Static replay51.0681.71
ReGraph: iterative reading53.2483.83

Our ReGraph outperforms Single-read by 5.51% on SceneGraphs and 3.58% on NeighborhoodQA. It also outperforms Static replay by more than 2%. These results demonstrate the effectiveness of iterative reading and highlight the importance of adaptively updating graph evidence based on evolving LLM hidden states.

For the second concern about model configurations, we acknowledge that most baseline entries follow the configurations reported in their original papers. However, this not favor ReGraph in model scale: ReGraph uses the smallest backbone among the compared LLM-based methods, Llama-3B, whereas the baselines use ChatGLM-6B (GraphTranslator), Vicuna-7B (LLaGA), Llama-7B (the GraphQA baselines reported by G-Retriever) or the closed-source GPT-3.5. Even when the LLM backbone is not particularly strong, our ReGraph can still achieve superior results. To make a perfectly fair comparison, we re-run representative baselines from the three interface families in Tables 1–2 with ReGraph’s frozen Llama-3.2-3B-Instruct and ReGraph’s graph encoder (the four-layer relation-aware Graph Transformer over all-roberta-large-v1 features, see Appendix C): GraphToken (a pooled graph token), LLaGA-ND (a structure-aware node sequence) and G-Retriever with a frozen LLM (a retrieved, textualized subgraph). Each baseline keeps its own interface, such as LLaGA’s neighborhood template and G-Retriever’s PCST retrieval, while its graph encoder is replaced by ours, and all methods share the data splits, answer-only objective and optimization schedule of Appendix C. In this setting, GraphToken and LLaGA-ND are exactly the same-backbone, same-encoder static graph interfaces you suggest: both form their graph tokens once, before the LLM, from the same encoder output. Because each baseline was originally developed and tuned with its own backbone and encoder, we train it with both its original learning rate and ours and keep the better one on the validation set, so that the unified setting is as favorable to the baselines as we can make it. We evaluate on two node-centric (ogbn-arxiv, NeighborhoodQA) and two graph-level (ExplaGraphs, StructuralAnomaly) benchmarks as follows:

Method (Llama-3.2-3B-Instruct, same graph encoder)Graph interfaceogbn-arxiv (Top-1)NeighborhoodQAExplaGraphsStructuralAnomaly
GraphTokenpooled graph token––84.3793.50
LLaGA-NDnode sequence64.3172.94––
G-Retriever (frozen LLM)retrieved subgraph––85.2994.92
ReGraph8 tokens, read iteratively72.2883.8390.4399.15

These results provide complementary evidence to the controlled reading-schedule ablations discussed above. The unified-baseline comparisons demonstrate that ReGraph’s advantages persist when the LLM backbone, graph encoder, and training conditions are matched, while the reading-schedule ablations further isolate the benefit of adaptive evidence acquisition over static or repeatedly injected evidence.

AuthorsOpenReview ↗

Response to Reviewer cbrw (part 2)

Q2: Important components are insufficiently ablated. The paper would benefit from ablations on topology diffusion, learned hop mixtures, evidence gating, number of graph-reading rounds, and number of graph-query tokens.

A2: Thanks for this valuable suggestion. Table 5 in the paper has provided some evidence, which compares one and three reading rounds. To further assess the contributions of topology diffusion, query-dependent hop selection, and evidence gating, we evaluate four ablation variants. Semantic-only reading sets K=0K=0, retrieving evidence through semantic attention without topology diffusion. Uniform hop mixture retains K=2K=2 and assigns an equal weight of 1/31/3, to each diffusion depth. Learned query-independent hop mixture also retains K=2K=2 but learns a separate hop distribution for each graph-query token and reading round, independently of the current query state. This replaces the state-conditioned hop prediction in Eq. (12) and examines the contribution of query-dependent hop selection. Finally, direct residual addition removes the evidence gate in Eq. (16) and adds retrieved evidence directly to the graph-query states. The results of average performance over five runs are summarized below:

VariantSceneGraphsNeighborhoodQA (Set-F1)StructuralAnomaly.
Semantic-only reading (K=0K = 0)48.1776.4698.21
Uniform hop mixture (K=2K = 2)52.9281.0397.94
Learned query-independent hop mixture (K=2K = 2)51.3282.0498.53
Direct residual addition (w/o evidence gate)49.8482.0698.45
ReGraph53.2483.8399.15

ReGraph consistently achieves the best performance across all three benchmarks, demonstrating the effectiveness of topology diffusion, query-dependent hop selection, and gated evidence fusion.

For the number of reading rounds, we vary T∈[1,3,6]T \in [1,3,6]. The first read stays after layer 7, as in ReGraph, and the remaining T−1T − 1 reads are spaced evenly over the remaining 21 layers. Since the reader and fusion parameters are shared across rounds, TT does not change the number of parameters.

Reading rounds TReads after layersSceneGraphsNeighborhoodQA Set-F1StructuralAnomaly
1747.7380.2595.10
3 (default)7, 14, 2153.2483.8399.15
67, 10, 14, 17, 21, 2453.1984.9199.18

Increasing TT from 1 to 3 consistently improves performance across all benchmarks, while six rounds yield further gains on NeighborhoodQA but largely saturate on SceneGraphs and StructuralAnomaly, supporting T=3T = 3 as a reasonable balance between performance and reading overhead.

For the number of query tokens, we further vary the number of graph-query tokens NB∈2,4,8,16,32N_B \in \\{2, 4, 8, 16, 32\\} on SceneGraphs, keeping the remaining settings fixed.

NBN_B248 (Default)1632
SceneGraphs.49.5252.0753.2453.9853.05

The results show that performance improves as NBN_B increases from 2 to 8, but largely saturates beyond the default setting.

Q3: The “open-ended reasoning” claim feels somewhat overstated. Most benchmarks have constrained answer spaces, while on SceneGraphs—the most open-ended benchmark—REGRAPH substantially underperforms G-Retriever-based methods (53.24 vs. 81.31/86.83).

A3: We would like to emphasize that open-ended graph reasoning is an exceptionally broad task, where both the questions and their answers can take almost any form (including nodes, edges, categories, subgraphs, paths, and free-form text), so no single model can be expected to perform best on every type of query. Our proposed ReGraph is therefore designed for breadth. With one architecture, it covers node-level inference, graph-level global understanding, structural localization, and community understanding. Compared to other models that also claim to be "open-ended" (e.g., GraphTranslator and LlaGA), our approach not only covers the application scenarios and benchmarks addressed by those models but also offers a significantly broader scope of applicability. We acknowledge that ReGraph underperforms specialized retrieval-based methods such as G-Retriever on SceneGraphs. However, ReGraph is more general-purpose, and retrieval-based methods can complement it on graphs whose answers can be retrieved from a small, question-specific subgraph. Therefore, we maintain that ReGraph is appropriately characterized as an "open-ended" graph reasoning framework, as it supports a broader range of reasoning tasks than prior methods that similarly claim open-ended capabilities.

AuthorsOpenReview ↗

Response to Reviewer cbrw (part 3)

Q4: Scalability remains unclear.

A4: In our work, scalability is not a bottleneck of ReGraph by design, because the LLM cost does not grow with the graph. The graph is never serialized in ReGraph. The LLM input stays at Nq+NB+1N_q + N_B + 1 tokens regardless of graph size (Eq. 3), and all graph reads run once during prefill and are KV-cached (Sec. 3.4). In contrast, serializing even a 19-node scene graph already takes 1396 tokens in G-retriever, so text-based interfaces reach the context limit long before graph-side cost matters. On the graph side of ReGraph (out of LLM), the encoder runs once per graph and is shared across reading rounds and questions, and each read costs O(NBNVdr+KNB∣E∣)O(N_BN_Vd_r + KN_B |E|) with a sparse PP for propagations, which is linear in graph size with small constants (NB=8N_B=8 and K=2K=2).

Our results already test robustness to graph growth: in Appendix E.5, models trained on graphs of 16–64 nodes are evaluated on up to 512 nodes without parameter updates, and ReGraph loses less accuracy than the controls as irrelevant regions accumulate (Fig. 4a–c). To evaluate larger-scale performance on real data, we propose extending NeighborhoodQA to the complete ogbn-arxiv network of 169,343 nodes. For a fixed set of held-out questions, we progressively enlarge the graph given to ReGraph while retaining all answer-determining neighbors, so the reference answers stay unchanged. ReGraph generates the set of subject areas among those neighbors, which we score against reference sets computed from labels withheld from its input. We report the drop in answer quality (in points) relative to the 512-node setting, together with encoding time, reading latency per question, and peak GPU memory:

NodesSet-F1 drop (%) ↓Exact drop (%) ↓Encoding (s) ↓Reading (ms) ↓Peak memory (GB) ↓
5120.000.000.0814.710.36
10K0.370.610.7342.312.14
100K1.241.538.16237.827.63
169K (Full)1.862.1715.42416.543.28

On the complete 169K-node graph, ReGraph retains answer quality within two percentage points of the 512-node setting while using a fixed eight-token graph interface, demonstrating scalability in both graph access and answer generation over the tested range.

Q5: The paper describes StructuralAnomaly’s density-free control as important for detecting leakage, but the corresponding control result should be reported more explicitly.

A5: Thank you for pointing this out. We now report the control results explicitly. The control arm keeps the graph size, themes, question, split sizes and target distribution of the answerable arm, but removes the density contrast and assigns the target uniformly at random (Appendix B.3.6). There is not input can therefore determine the answer, and accuracy above chance (20%) would reveal leakage through node text, graph statistics or the question. We train and test each method on the control arm with exactly the same protocol as on the answerable arm.

MethodAnswerable arm Acc.Control arm Acc.
GraphToken96.3519.85
G-Retriever97.0520.10
ReGraph99.1520.05

All three methods fall to chance on the control arm (19.85–20.10%), while they reach 96.35–99.15% on the answerable arm. With 2,000 test examples, the 95% interval around chance is 18.2–21.8%, and all control accuracies lie well within it. The StructuralAnomaly results therefore come from the density contrast rather than from leakage, which supports the structural interpretation of the benchmark.

Q6: Under the same backbone and graph encoder, how does REGRAPH compare with a strong static graph interface or retrieval baseline on representative tasks? Which entries in Tables 1–2 were rerun, and with which backbones, supervision, and splits?

A6: For the same-backbone and same-encoder comparisons with static graph interfaces and retrieval baselines, please refer to A1 under Q1, where we provide detailed experimental settings and results. To clarify the scope of the additional reruns, we evaluate LLaGA-ND on ogbn-arxiv and NeighborhoodQA (Table 1), using 20,000/2,000/4,000 and 19,902/1,999/3,993 training/validation/test examples, respectively. For the graph-level tasks (Table 2), we rerun GraphToken and G-Retriever (frozen LLM) on ExplaGraphs and StructuralAnomaly, using 1,659/553/554 and 8,000/1,000/2,000 examples, respectively. StructuralAnomaly uses the answerable arm. All reruns use the same frozen Llama-3.2-3B-Instruct backbone, four-layer relation-aware Graph Transformer with all-roberta-large-v1 features, and answer-only autoregressive supervision. Each baseline preserves its original graph interface and is independently trained using the same data splits as ReGraph.

Reviewer_WRrSOpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

ReGraph interleaves graph reading with intermediate layers of a frozen LLM. Learnable graph-query tokens retrieve evidence from persistent node memory through a topology-diffused reader and integrate it through gated residual fusion. Only the graph-side interface is trained using answer supervision. Experiments on six benchmarks, including NeighborhoodQA and StructuralAnomaly, assess predictive performance, graph dependence, adaptive reading, robustness, and generalization. Results support adaptive graph access, although performance remains limited on SceneGraphs.

Critical strengths
  1. Intermediate LLM states guide successive reads from graph memory. The static-replay comparison in the experiments directly supports renewed evidence selection.

  2. Perturbation, visibility, and distractor tests examine reliance on relevant graph evidence. The two proposed benchmarks further test neighborhood synthesis and anchor-free structure–semantics binding, strengthening the empirical case beyond aggregate accuracy.

Critical weaknesses
  1. The experiments do not isolate the contribution of topology diffusion. Comparing the full reader with semantic-only reading (K = 0) and fixed hop mixtures would help show whether graph propagation and query-dependent hop selection are both useful.

  2. The benefit of gated evidence fusion is not separately evaluated. An ablation that replaces the learned gate with direct residual addition would help establish whether adaptive control of the injected evidence improves performance.

  3. Appendix C reports overall runtimes, but a direct efficiency comparison with representative baselines is missing. Reporting inference latency and peak memory under the same hardware and LLM backbone would help clarify the computational benefits of the proposed interface.

Questions for authors

Please refer to the experimental suggestions in Critical Weaknesses.

2 comments
AuthorsOpenReview ↗

Response to Reviewer WRrS

Q1: The experiments do not isolate the contribution of topology diffusion.

A1: We thank the reviewer for this suggestion. To isolate the contributions of topology diffusion and query-dependent hop selection, we consider two ablation variants: Semantic-only (K=0K=0) which removes topology diffusion from the reader, uniform hop mixture (K=2K=2) which assigns equal weights to all propagation depths, and ReGraph (query-dependent mixture). All other model configurations remain unchanged.

Reader configurationSceneGraphs Acc.NeighborhoodQA Set-F1StructuralAnomaly Acc.
Semantic-only (K=0K=0)48.1776.4698.21
Uniform hop mixture (K=2K=2)52.9281.0397.94
ReGraph (query-dependent)53.2483.8399.15

The results demonstrate the benefits of both components. Topology diffusion substantially improves performance over semantic-only reading, particularly on SceneGraphs. Query-dependent hop selection provides further gains over uniform diffusion across all three benchmarks. These findings support our design: propagating semantic relevance through graph topology improves evidence acquisition, while adapting the propagation depth to the evolving query states further enhances graph reasoning.

**Q2: The benefit of gated evidence fusion is not separately evaluated. **

A2: As suggested, we replace the learned gate with direct residual addition, Bpostt=Bpret+RtB_{post}^{t}=B_{pre}^{t} + R^{t} (i.e., gt≡1g^{t} \equiv 1 in Eq.(16)), with all other components and the training recipe unchanged, and evaluate on the same three benchmarks. We report the results as the table below:

FusionSceneGraphsNeighborhoodQAStructuralAnomaly
Direct residual addition49.8482.0698.45
ReGraph (gated fusion)53.2483.8399.15

The results show that gated fusion consistently outperforms direct residual addition across all three benchmarks. These results demonstrate the benefit of adaptively controlling evidence injection. In particular, the gate allows each graph-query token to regulate how strongly new graph evidence updates its current state at each reading round (Sec. 3.3), preserving previously acquired information while selectively integrating new evidence. This provides direct empirical support for the gated fusion design.

Q3: Appendix C reports overall runtimes, but a direct efficiency comparison with representative baselines is missing. Reporting inference latency and peak memory under the same hardware and LLM backbone would help clarify the computational benefits of the proposed interface.

A3: We agree. By design, ReGraph adds only eight graph-query positions to the LLM input, regardless of graph size. To quantify this, we compare ReGraph with graph-as-text prompting, GraphToken and frozen G-Retriever on ExplaGraphs and StructuralAnomaly, using the same Llama-3.2-3B-Instruct backbone and GPU as in Appendix C, the same test questions, BF16, batch size one and greedy decoding. Timings include online graph encoding, retrieval where applicable, and generation, and reusable preprocessing is cached in the same way for all methods. We report time to first token (TTFT), total latency and peak GPU memory. Accuracy is reproduced from Table 2 for reference (see Appendix. A3 for the baselines' backbones). The results on ExplaGraphs are as follows:

MethodAccuracy (%) ↑TTFT (ms) ↓Total latency (ms) ↓Peak memory (GB) ↓
Graph-as-text (zero-shot)56.5022.836.17.18
GraphToken85.0814.328.57.09
G-Retriever (frozen LLM)85.1631.645.97.34
ReGraph90.4319.733.87.26

The results on StructuralAnomaly are as follows:

MethodAccuracy (%) ↑TTFT (ms) ↓Total latency (ms) ↓Peak memory (GB) ↓
Graph-as-text (zero-shot)41.8568.4101.77.83
GraphToken96.3515.846.27.12
G-Retriever (frozen LLM)97.0543.776.47.48
ReGraph99.1521.352.67.29

GraphToken, which compresses the graph into a single pooled token, is the fastest and lightest, while ReGraph adds a modest overhead over it in exchange for the highest accuracy. ReGraph is faster than graph-as-text prompting and G-Retriever on both benchmarks and uses less memory than G-Retriever. The speed gap widens on StructuralAnomaly's larger graphs, where text-based inputs grow with the graph while ReGraph's stays fixed.

AuthorsOpenReview ↗

We have revised the manuscript to address each of your comments.

We thank the reviewer for the helpful suggestions. All changes in the revised paper are marked in blue.

  • Q1 (Topology diffusion and query-dependent hop selection).
    • New Sec. 4.6, Table 7: compares the full reader with three variants on SceneGraphs, NeighborhoodQA, and StructuralAnomaly.
    • App. E.6: defines each variant precisely and discusses the results.
  • Q2 (Gated evidence fusion). Table 7 also includes direct residual addition (gt≡1g^t\equiv1 in Eq. 16), which lowers performance on all three benchmarks. See Sec. 4.6 and App. E.6.
  • Q3 (Efficiency comparison).
    • New App. C.1 (Table 11): compares ReGraph with graph-as-text prompting, GraphToken, and G-Retriever (frozen LLM) on ExplaGraphs and StructuralAnomaly. It reports TTFT, total latency, and peak memory.
    • Sec. 4.6: summarizes this comparison.
    • App. E.8 (Table 17): further reports how encoding time, reading latency, and peak memory scale up to the full 169,343-node ogbn-arxiv graph.

We hope that these updates fully address your concerns, and we would be glad to answer any further questions.

Reviewer_4UK7OpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The paper proposes ReGraph, an iterative graph-reading framework designed for open-ended graph reasoning with frozen LLMs. Addressing the core limitations of traditional GraphRAG (e.g., redundant text serialization, inflexible static soft prompts, or one-shot graph retrieval),it interleaves LLM layer-group computation with dynamic graph reads.

Critical strengths
  1. The paper correctly identifies a fundamental bottleneck in existing GraphRAG or Graph-enhanced LLM paradigms. Interleaving intermediate Transformer hidden states with graph memory updates is a well-motivated and elegant architectural shift.

  2. Injecting evidence via continuous graph-query tokens between layer groups while keeping the graph outside the raw input prompt preserves KV caching during answer generation.

  3. This paper effectively prove that the model genuinely grounds its intermediate reasoning on graph structure rather than relying purely on parametric memory shortcuts.

Critical weaknesses
  1. The paper candidly admits weaker performance on SceneGraphs compared to baseline methods like G-Retriever (53.24%53.24\% vs. 87.05%87.05\% with LoRA). This highlights a major trade-off in REGRAPH's design: compressing rich, fine-grained multi-modal/relational edge attributes into a small set of latent query tokens (NB=8N_B=8) inevitably causes a representation bottleneck. For tasks requiring precise local subgraph grounding, standard text serialization or explicit subgraph extraction still holds a noticeable edge over soft-vector interfaces.

  2. The evaluation focuses on small subgraphs. However, real-world knowledge graphs or massive web-scale agent search could be very big. The scalability is a concern.

  3. Missing many important baselines, e.g., GNN-RAG, GFM-RAG, G-Reasoner, HyperGraphRAG, etc.

Questions for authors

Please see above.

5 comments
AuthorsOpenReview ↗

Response to Reviewer 4UK7 (Part 1/2)

Q1: Weak performance on SceneGraphs. A small set of latent query tokens NB=8N_B=8 causes a representation bottleneck.

A1: SceneGraphs is indeed ReGraph's weakest benchmark, which we state as a limitation in Sec. 4.2. SceneGraphs‘ questions ask for an object or attribute name attached to a few local triples and are scored by exact match. This is precisely the setting G-Retriever is built for: it extracts a small question-specific subgraph and places it in the prompt as text, from which the LLM can copy the answer. However, we would like to emphasize that open-ended graph reasoning is an exceptionally broad task, where both the questions and their answers can take any form (e.g., nodes, edges, categories, paths, and free-form text), so no single model can perform best on every type of query. Our proposed ReGraph is designed for breadth. With one architecture, ReGraph covers node-level inference, graph-level global understanding, structural localization, and community understanding. Compared to other models that also claim to be "open-ended" (e.g., GraphTranslator, LlaGA, and G-Retriever), ReGraph addresses a wider range of graph reasoning scenarios.

Specifically, ogbn-arxiv, Cora and NeighborhoodQA offer no question-specific subgraph to retrieve: the answer depends on a global understanding of the neighborhood rather than on a few triples that match the question. Such tasks fall outside what RAG-based methods are designed for, which is why Table 1 compares ReGraph with text-based and graph–language alignment methods rather than RAG baselines such as G-Retriever. Thus, ReGraph and G-Retriever address complementary graph reasoning requirements: ReGraph targets general, open-ended graph reasoning, whereas G-Retriever is particularly effective when answers can be grounded in a specific, retrievable subgraph. The results in Table 1 and on SceneGraphs reflect this distinction.

Regarding the bottleneck of graph-query tokens, we clarify that ReGraph does not compress the graph into NB=8N_B = 8 tokens. Instead, it maintains a persistent graph memory HH which is repeatedly accessed between adjacent Transformer-layer groups (T=3T=3 reading rounds, Eq. 9) of the LLM. Thus, NBN_B sets how much evidence each read can acquire, not how much of the graph information is stored or accessible. Moreover, adaptive reading improves SceneGraph's accuracy from 47.73% with a single read to 53.24% (Table 5), demonstrating the benefit of repeatedly accessing graph memory. To directly investigate whether the limited number of query tokens causes the observed performance gap, we vary NBN_B while keeping all other settings fixed:

NBN_B248(Default)1632
SceneGraphs49.5252.0753.2453.9853.05

It shows that performance improves as NBN_B increases from 2 to 8, but largely saturates beyond the default, so the number of graph-query tokens is not the limiting factor on SceneGraphs.

Q2: The evaluation focuses on small subgraphs.

A2: We would like to clarify that scalability is not a bottleneck of ReGraph by design, because the LLM cost does not grow with the graph. The graph is never serialized in ReGraph. The LLM input stays at Nq+NB+1N_q + N_B + 1 tokens regardless of graph size (Eq. 3), and all graph reads run once during prefill and are KV-cached (Sec. 3.4). In contrast, textualizing even a 19-node scene graph takes 1396 tokens in G-Retriever, so text-based interfaces reach the context limit long before graph-side cost matters. On the graph side of ReGraph (out of LLM), the encoder runs once per graph and is shared across reading rounds and questions, and each read costs O(NBNVdr+KNB∣E∣)O(N_BN_Vd_r + KN_B |E|) with a sparse PP, which is linear in graph size with small constants (NB=8N_B=8 and K=2K=2).

Our results already test robustness to graph growth: in Appendix E.5, models trained on graphs of 16–64 nodes are evaluated on up to 512 nodes without parameter updates, and ReGraph loses less accuracy than the controls as irrelevant regions accumulate (Fig. 4a–c). To evaluate larger graphs on real data, we propose extending NeighborhoodQA to the complete ogbn-arxiv network of 169,343 nodes. For a fixed set of held-out questions, we progressively enlarge the graph given to ReGraph while retaining all answer-determining neighbors, so the reference answers stay unchanged. ReGraph generates the set of subject areas among those neighbors, which we score against reference sets computed from labels withheld from its input. We report the scalability as follows:

NodesSet-F1 drop (%)↓Exact drop (%)↓Encoding (s)↓Reading (ms)↓Peak memory (GB) ↓
512000.0814.710.36
10K0.370.610.7342.312.14
100K1.241.538.16237.827.63
169K1.862.1715.42416.543.28

On the complete 169K-node graph, ReGraph retains answer quality 2% of the 512-node setting while using a fixed eight-token graph interface, demonstrating scalability in both graph access and answer generation.

AuthorsOpenReview ↗

Response to Reviewer 4UK7 (Part 2/2)

Q3: Missing many important baselines, e.g., GNN-RAG, GFM-RAG, G-Reasoner, HyperGraphRAG, etc.

A3: We would first like to clarify that the omission of these baselines was not intended to avoid comparison. Rather, their original algorithmic formulations and application settings are not directly compatible with the open-ended graph reasoning tasks evaluated in our work. All four target retrieval-augmented, knowledge-intensive QA: they retrieve evidence from a knowledge source shared across many questions and pass it to the LLM as text, assuming the answer can be retrieved. In our benchmarks, each question comes with its own graph, and the answer is often neither a node nor text in that graph, so it must be inferred based on the global understanding of the graph rather than retrieved. Specifically, following their original papers:

  • GNN-RAG retrieves answer nodes, so it requires every answer to be a node in the graph. This fails on all six benchmarks: answers are subject areas (ogbn-arxiv, Cora, NeighborhoodQA), support/counter (ExplaGraphs) or community themes (StructuralAnomaly), and SceneGraphs includes attribute, yes/no and relation-word answers that are not nodes.
  • GFM-RAG starts retrieval from entities named in the question and keeps the top 20. Our node-level and StructuralAnomaly questions name no node, and on ExplaGraphs (5.17 nodes) and SceneGraphs (19.13 nodes) the top 20 cover essentially the whole graph, so it reduces to the serialized-graph baselines in Table 2.
  • HyperGraphRAG contributes building hyperedges from text corpora, which a given graph makes unnecessary. The remaining similarity retrieval is what KAPING already does in Table 2, and it cannot locate structure-defined evidence such as StructuralAnomaly's dense community.

Overall, these GraphRAG methods have a relatively narrow scope within open-ended graph reasoning, as their original formulations primarily address questions with explicitly retrievable evidence, while broader tasks requiring global graph understanding or anchor-free structural inference fall outside their directly supported settings.

G-Reasoner is the only one that runs on benchmarks ExplaGraphs, SceneGraphs, and StructuralAnomaly, since it scores every node against the question and accepts the queried paper as a query-related node. We evaluate G-Reasoner with its original retrieval procedure unchanged and the same Llama-3.2-3B-Instruct reader as ReGraph, reporting the average performance over five runs:

ExplaGraphsSceneGraphsStructuralAnomaly
G-Reasoner (Llama-3.2-3B)84.7664.3195.54
ReGraph (Llama-3.2-3B)90.4353.2499.15

ReGraph is stronger on ExplaGraphs and StructuralAnomaly, where the answer depends on reading the whole graph or its structure, while G-Reasoner is stronger on SceneGraphs, which rewards copying names from a small retrieved subgraph. This further confirms our response to Q1, i.e., ReGraph and GraphRAG-based approaches, such as G-Retriever and G-Reasoner, offer complementary strengths, with their relative effectiveness depending on the reasoning requirements of each task.

AuthorsOpenReview ↗

Looking forward to your response

Dear Reviewer 4UK7

Thanks again for your valuable suggestions for improving our paper. With the discussion period nearing its end, we would like to provide a summary of our responses to your concerns for your convenience:

  1. We clarify ReGraph’s complementary strengths to GraphRAG and conduct a graph-query token sensitivity analysis.
  2. We conduct large-scale experiments on graphs with up to 169K nodes, evaluating accuracy, latency, and memory.
  3. We discuss the applicability of missing GraphRAG baselines and provide additional comparisons with G-Reasoner under a matched LLM backbone.

We hope our responses have adequately addressed your concerns. If you have any further questions, please do not hesitate to let us know.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response

We thank all reviewers for their constructive feedback. In our responses, we provide additional controlled comparisons, component ablations, scalability measurements, and benchmark controls, while clarifying ReGraph’s scope and limitations. We summarize our responses to each reviewer below.

For Reviewer 4UK7:

  • We clarify ReGraph’s complementary strengths to retrieval-based methods, distinguish persistent graph memory from per-read token capacity, and conduct a query-token sensitivity study to investigate the SceneGraphs limitation.
  • We extend evaluation to the complete 169,343-node ogbn-arxiv graph.
  • We discuss the applicability of GNN-RAG, GFM-RAG, and HyperGraphRAG to our benchmarks and provide same-backbone comparisons with G-Reasoner, highlighting their task-dependent strengths.

For Reviewer WRrS:

  • We conduct semantic-only and uniform-hop ablations across three benchmarks to isolate the contributions of topology diffusion and query-dependent hop selection.
  • We compare learned gating with direct residual addition under otherwise identical settings to assess the benefit of adaptively controlling evidence injection.
  • We conduct additional experiments on efficiency comparisons.

For Reviewer cbrw:

  • We rerun GraphToken, LLaGA-ND, and G-Retriever with ReGraph’s frozen LLM backbone and graph encoder, specifying the training configurations, supervision, and data splits.
  • We compare Single-read, Static replay, and ReGraph under controlled settings.
  • We clarify the intended scope of open-ended graph reasoning and acknowledge ReGraph’s weaker fine-grained grounding on SceneGraphs relative to retrieval-based methods.
  • We analyze graph-side time and memory complexity.
  • We conduct experiments with density-free control.
  • We specify the StructuralAnomaly protocol for claim extraction, support matching, required-fact annotation, and aggregation, together with the planned evaluation of 2,000 test examples under clean and distractor conditions.

Thanks again for your efforts in reviewing our work, and we hope our responses can address any concerns about this work.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.