- 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
- The main idea is intuitive and reasonably novel: graph evidence is retrieved repeatedly using query states that evolve across intermediate Transformer layers.
- The Single-read / Static replay / REGRAPH comparison is a useful control and provides evidence that adaptive rereading is beneficial.
- The paper includes several useful diagnostic experiments, including graph perturbations, distractor robustness, and generalization tests.
- The presentation is generally clear and technically well organized.
Critical weaknesses
- 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.
- 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.
- 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).
- 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.
- 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
- 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?
- 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?
- 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)?
- How do latency and memory scale as the supplied graph grows?
9 comments
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 , retrieving evidence through semantic attention without topology diffusion. Uniform hop mixture retains and assigns an equal weight of , to each diffusion depth. Learned query-independent hop mixture also retains 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:
| Variant | SceneGraphs | NeighborhoodQA (Set-F1) | StructuralAnomaly. |
|---|---|---|---|
| Semantic-only reading () | 48.17 | 76.46 | 98.21 |
| Uniform hop mixture () | 52.92 | 81.03 | 97.94 |
| Learned query-independent hop mixture () | 51.32 | 82.04 | 98.53 |
| Direct residual addition (w/o evidence gate) | 49.84 | 82.06 | 98.45 |
| ReGraph | 53.24 | 83.83 | 99.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 . The first read stays after layer 7, as in ReGraph, and the remaining reads are spaced evenly over the remaining 21 layers. Since the reader and fusion parameters are shared across rounds, does not change the number of parameters.
| Reading rounds T | Reads after layers | SceneGraphs | NeighborhoodQA Set-F1 | StructuralAnomaly |
|---|---|---|---|---|
| 1 | 7 | 47.73 | 80.25 | 95.10 |
| 3 (default) | 7, 14, 21 | 53.24 | 83.83 | 99.15 |
| 6 | 7, 10, 14, 17, 21, 24 | 53.19 | 84.91 | 99.18 |
Increasing 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 as a reasonable balance between performance and reading overhead.
For the number of query tokens, we further vary the number of graph-query tokens on SceneGraphs, keeping the remaining settings fixed.
| 2 | 4 | 8 (Default) | 16 | 32 | |
|---|---|---|---|---|---|
| SceneGraphs. | 49.52 | 52.07 | 53.24 | 53.98 | 53.05 |
The results show that performance improves as 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.
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 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 with a sparse for propagations, which is linear in graph size with small constants ( and ).
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:
| Nodes | Set-F1 drop (%) ↓ | Exact drop (%) ↓ | Encoding (s) ↓ | Reading (ms) ↓ | Peak memory (GB) ↓ |
|---|---|---|---|---|---|
| 512 | 0.00 | 0.00 | 0.08 | 14.7 | 10.36 |
| 10K | 0.37 | 0.61 | 0.73 | 42.3 | 12.14 |
| 100K | 1.24 | 1.53 | 8.16 | 237.8 | 27.63 |
| 169K (Full) | 1.86 | 2.17 | 15.42 | 416.5 | 43.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.
| Method | Answerable arm Acc. | Control arm Acc. |
|---|---|---|
| GraphToken | 96.35 | 19.85 |
| G-Retriever | 97.05 | 20.10 |
| ReGraph | 99.15 | 20.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.
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:
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:
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.