acceptodds
Under review as a conference paper at ICLR 2027

StructSeek: Learning to Acquire Structural Evidence for Zero-Shot Graph Learning

Abstract

Large language models (LLMs) have demonstrated strong semantic generalization, creating new opportunities for zero-shot graph learning. However, link prediction remains challenging because it depends critically on structural relations between node pairs. Existing Graph LLMs either require the LLM to recover such relations from serialized graph context or encode them implicitly in learned representations, while recent graph agents mainly retrieve graph observations rather than directly access task-relevant structural information. We propose StructSeek, an interactive graph agent that introduces a structure-as-tool paradigm for zero-shot graph learning. StructSeek actively seeks the semantic and structural evidence needed for each prediction through dedicated graph operators. The agent learns which operators to invoke, when to invoke them, and how to use the returned evidence for prediction. We train StructSeek with supervised fine-tuning on teacher trajectories followed by reinforcement learning. Experiments across multiple unseen graph domains show overall improvements on both node classification and link prediction. The gains are particularly pronounced for link prediction, where StructSeek-3B outperforms the strongest baseline by 12.9–25.8 percentage points across four unseen graphs. These results demonstrate the benefit of directly accessible structural evidence for zero-shot graph learning.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
LLM, Graph Learning, LLM Agents, Zero-Shot Graph Learning, Tool-Augmented Reasoning

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_X2UmOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies zero-shot graph learning with large language models, with a focus on link prediction. The authors argue that existing methods either serialize subgraphs into text and leave the model to recover structural relations such as common neighbors from that text, or encode structure into representations so that the structural evidence stays implicit, while existing graph agents mainly retrieve observations from the graph and the structural relations still have to be inferred by the model. They propose StructSeek, which treats structure as a tool: the agent acquires evidence on demand through six graph operators. Two semantic operators read one-hop and two-hop neighbor texts, and four structural operators return local statistics such as node degree and clustering coefficient, the number of common neighbors, the shortest-path distance, and the number of length-three paths. Training has two stages. DeepSeek-V4-Flash first generates trajectories in the same operator environment, and only the 4168 trajectories with correct predictions are kept for supervised fine-tuning. GRPO is then used for reinforcement learning, with a reward made of prediction correctness, whether operators are called, and output format. The policy is trained on OGB-Arxiv and OGB-Products and evaluated zero-shot on node classification and link prediction on PubMed, Amazon-Photo, Amazon-Computers, and Reddit, with 1000 instances per task and dataset and accuracy as the metric. Baseline numbers are taken from AgentGL. StructSeek is best in 13 of 16 settings. The 3B version outperforms the strongest baseline on link prediction by 12.9 to 25.8 percentage points and also surpasses the teacher model on three of the four graphs. The paper also includes an ablation of the structural operators, a split of SFT and RL, an analysis of operator-call patterns, and case studies.

Critical strengths
  1. The motivation is clear, the design is simple, and the controlled experiments are solid. Handing deterministic structural computation to operators and letting the language model decide only what to query and how to use it is a reasonable division of labor. The paper runs a step-by-step comparison on the same backbone: adding structural operators improves link prediction by 5.7 to 19.8 points, and training adds a further 23.6 to 34.4 points, and Appendix C.1 further separates the contributions of SFT and RL. Figures 1 and 2 and the complete case trajectories make the method easy to understand.
  2. The reproducibility information is complete and the results are presented fairly candidly. The appendix gives the data splits, the edge-masking protocol, the prompts, the reward definition, and all hyperparameters, and an anonymous code repository is provided. The paper does not hide unfavorable results: 7B is not best in three settings, and it also reports that the teacher model is clearly stronger on node classification.
Critical weaknesses
  1. The link prediction evaluation may be too easy and lacks classical heuristic baselines, so the large gains do not show the value of the structure-as-tool paradigm. How negative samples are drawn is not described, and random negatives usually differ greatly from true edges in degree, shortest distance, and number of common neighbors, which is exactly what the operators return, as the paper's own two cases show. The paper does not compare against classical methods such as common neighbors, a shortest-distance threshold, or SEAL, and the GNN baselines in Table 1 are close to random. I suspect that a simple rule would reach similar accuracy, and if so, the gain comes mainly from the evaluation protocol rather than from the agent's evidence acquisition policy.
  2. The sources of the gains are mixed together and the comparison is not under equal conditions. StructSeek uses structural operators, teacher trajectory distillation, and RL, while the baselines have neither the operators nor the teacher data, so I cannot see how much the paradigm itself contributes. In Appendix C.1, the RL-only variant that keeps the structural operators is on par with AgentGL-GRPO, which has no structural operators, suggesting that the improvement comes mainly from SFT on teacher trajectories. On node classification the policy hardly uses structural operators, so the improvement there has nothing to do with structural evidence, and the abstract's claim of improvement on both tasks is broader than what the experiments support.
Questions for authors
  1. How are the negative samples for link prediction drawn, and are they matched by degree or distance? What are the distributions of degree, shortest distance, and number of common neighbors for positive and negative pairs? On these four graphs, what accuracy does a threshold classifier reach using only degree, only common neighbors, or only shortest distance? What are the results for common neighbors, Adamic-Adar, and SEAL and NCNC trained on the same training graphs? How do the GNN baselines in Table 1 perform zero-shot link prediction, and why are they close to 50%?
  2. What are the results under harder negatives, for example two-hop negatives, degree-matched negatives, or a temporal split? Training and evaluation use the same negative sampling, so does the policy exploit regularities introduced by the sampling?
  3. Can you provide the results of AgentGL trained with the same six operators and the same teacher trajectories? The RL-only variant that keeps all operators is roughly on par with AgentGL-GRPO without structural operators, so how does the paper view the respective contributions of the paradigm itself and teacher distillation?
  4. Are all results from a single run? With 1000 instances, what are the confidence intervals or multi-seed variances for the comparison with the teacher, which differs by about 2 points, and for the RL gains of 2.4 to 2.7 points? Judging from Figure 4, the policy on link prediction almost always calls common_neighbors first and then path_between, and on node classification almost always calls read_one_hop_similar once. Please provide the distribution of calls per instance and the number of instances whose subsequent actions change according to the returned evidence.
4 comments

We thank the reviewer for the careful assessment and for recognizing the controlled comparisons and reproducibility details. We agree that the original LP protocol and the separate contributions of operators and training require careful qualification.

W1 / Q1. Negative Sampling and LP Baselines

Thank you for identifying the potential confounding effect of random negative sampling and for requesting stronger LP baselines.

Each unseen graph has 500 positive edges and 500 randomly sampled non-edges for LP; negatives are not degree- or distance-matched. Positive target edges are masked before tool interaction. The observed positive/negative pair statistics are:

Statistic (positive / negative)PubMedPhotoComputersReddit
Median endpoint degree11 / 237 / 830.5 / 6107 / 3
Median shortest distance3 / 62 / 52 / 52 / no path
No-path ratio (%)18.6 / 02.2 / 2.83.0 / 4.81.0 / 100
Pairs with common neighbors (%)32.8 / 0.690.0 / 0.890.0 / 1.299.0 / 0

These distributions confirm substantial structural separability under random negatives. We therefore add structural heuristics and source-trained LP methods (accuracy, %):

MethodPubMedPhotoComputersReddit
Degree-product threshold73.370.373.276.8
Common neighbors66.194.694.499.5
Shortest-distance threshold83.391.994.299.5
Adamic–Adar66.194.694.499.5
Logistic regression90.990.792.250.6
SEAL90.793.694.699.0
NCNC51.079.180.561.1
StructSeek-3B88.489.994.599.5

Heuristic thresholds and logistic regression use 6,400 source-domain instances from Arxiv/Products; SEAL and NCNC use 6,400 source training + 1,600 validation instances. We acknowledge that simple heuristics match or exceed StructSeek on some graphs. High accuracy under random negatives does not, by itself, establish sophisticated relational reasoning or superiority over classical LP predictors. Our contribution is instead a unified NC/LP agent that can request and integrate semantic and structural evidence. The current experiments establish its utility under the stated protocol, not its superiority to specialized structural heuristics. Matched-backbone ablations (Figure 3) show operator and training gains under the same protocol, but do not eliminate sampling bias.

GNN baselines in Table 1 follow AgentGL's source-trained, zero-shot cross-graph setting (OGB-Arxiv/OGB-Products to unseen target graphs, without target adaptation). Their near-50% LP accuracy in some cases should be interpreted in that transfer setting, not as a claim that GNNs are generally ineffective at LP.

Q2. Hard-Negative Evaluation

We appreciate the suggestion to evaluate more challenging negative samples.

We additionally evaluate degree-matched and two-hop negatives on PubMed and Amazon-Computers. For each setting, we retain 500 positive pairs and construct 500 negative pairs by matching both endpoint degrees in log₂ bins or sampling non-edges at shortest-path distance two. Target-edge masking remains active, and all models and source-fitted thresholds are kept fixed.

MethodPubMed DegreeAmazon-Computers DegreePubMed Two-hopAmazon-Computers Two-hop
Degree-product threshold49.950.053.052.3
Common neighbors65.292.816.445.0
Adamic–Adar65.292.816.445.0
Shortest-distance threshold79.082.034.548.0
Logistic regression88.189.644.048.9
SEAL81.077.643.451.2
NCNC50.057.551.470.0
RevGAT50.062.650.060.5
GraphICL-3B58.248.451.948.1
Search-o1-3B58.550.053.050.2
StructSeek-3B84.688.855.052.1

Accuracy (%). Bold indicates the best result in each column.

Degree matching reduces StructSeek accuracy from 88.4 → 84.6 (PubMed) and 94.5 → 88.8 (Amazon-Computers). It remains competitive with the tested transfer baselines, although logistic regression performs better on both degree-matched sets. This suggests that endpoint-degree differences alone do not explain all performance, without ruling out other sampling-related shortcuts. Two-hop negatives cause a larger drop (55.0/52.1), particularly on Amazon-Computers, where NCNC reaches 70.0%. This exposes a limitation: the current policy does not reliably distinguish structurally similar positive and negative pairs, and its performance is sensitive to the sampling distribution. We do not claim temporal generalization; temporal splits are outside our static-graph evaluation.

W2 / Q3. Structural Operators and Training Contributions

Thank you for asking for a more controlled assessment of the contributions of structural operators and teacher-guided training.

We agree that an AgentGL variant equipped with the same operators and teacher trajectories would provide an informative controlled comparison, even though it would modify AgentGL’s original interface and training setup. We have not performed that experiment and therefore cannot claim to isolate an advantage over such an augmented AgentGL. Instead, we report a matched-backbone ablation to assess operator availability across training configurations. Both operator pools use the same LP source examples and training procedures within each configuration:

Operator poolUntrainedRL-onlySFT-only
Semantic only52.0065.5880.25
All operators63.9072.6590.43
Structural-operator gain+11.90+7.07+10.18

Average LP accuracy (%) across four unseen graphs.

Structural operators improve LP accuracy across the evaluated untrained, RL-only, and SFT-only configurations (+11.90 without training, +7.07 with RL-only, and +10.18 with SFT-only), supporting a contribution beyond teacher distillation alone. Meanwhile, SFT transfers the teacher's task-solving knowledge through demonstrated acquisition and reasoning trajectories, and RL provides further improvements. For NC, the learned policy primarily relies on semantic operators. The revised analysis presents structural evidence and policy training as complementary contributors, with structural measurements playing a more direct role in LP than in NC (Section 3.3).

Q4. Statistical Reliability and Adaptive Tool Use

We appreciate the request for uncertainty estimates and a closer examination of adaptive tool use.

Results are from a single run on 1,000 LP instances per graph. 95% CIs use Bonferroni-combined Clopper–Pearson intervals for teacher comparisons and paired normal approximations on matched instances for RL gains. They reflect test-instance uncertainty, not training-seed variability.

DatasetTeacherStructSeekDifference vs teacher (95% CI)RL gain (95% CI)
PubMed75.088.4+13.4 [7.91, 18.78]+5.8 [3.87, 7.73]
Photo92.589.9−2.6 [−6.69, 1.51]+2.4 [0.22, 4.58]
Computers92.394.5+2.2 [−1.42, 5.80]+2.7 [0.97, 4.43]
Reddit97.799.5+1.8 [0.10, 3.47]−0.3 [−0.82, 0.22]

StructSeek has higher point estimates than the teacher on three graphs, but the displayed difference CIs exclude zero only on PubMed and Reddit. The displayed RL-gain CIs exclude zero on PubMed, Photo, and Computers, not Reddit.

Tool use. The operator-frequency figure summarizes aggregate usage, not a fixed call order. The recorded calls-per-instance distribution is:

CallsLP (n=4,000)NC (n=4,000)
17352,909
22,4181,081
383310
≥4140

On 414 PubMed instances where path_between returned one of the following outcomes, the next action differed markedly:

Returned evidenceInstancesNext: bridging_pathsStop
Distance = 216655 (33.1%)111
Distance = 3190177 (93.2%)13
No path581 (1.7%)57

Thus, subsequent tool choices vary with the returned evidence, consistent with evidence-conditioned acquisition rather than a single fixed calling sequence. These observational counts do not establish a causal advantage over a fixed-call policy.

Thank you for the detailed response. The proposed experiments and analyses address several of my concerns. I will retain my current rating.

Thank you for your follow-up and for reconsidering our responses. We sincerely appreciate your constructive feedback and careful assessment. Your comments have helped us further strengthen the paper.

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

This paper proposes StructSeek, an LLM‑based graph agent for zero‑shot node classification and link prediction. Motivated by the poor link‑prediction performance of existing graph‑LLM approaches, the authors put forward a structure‑as‑toolparadigm: instead of forcing LLMs to deduce topology from serialized text or relying on implicit graph embeddings, the agent invokes dedicated operators. Semantic operators retrieve node textual context; structural operators directly compute ground‑truth topological statistics (common neighbors, shortest‑path etc). The policy is trained via teacher trajectory SFT followed by GRPO reinforcement learning. Trained on two source graphs, it is zero‑shot evaluated across four unseen graphs over node classification and link prediction.

Critical strengths
  1. This paper has clear observation for motication: Existing graph‑LLMs struggle on link prediction because pairwise structural evidence cannot be reliably inferred by LLMs from text. The “structure‑as‑tool” separation of concern. LLM decides what evidence to fetch, environment computes graph structural quantities may be a possible step for graph agent research.
  2. Under the paper’s zero‑shot protocol, StructSeek outperforms prior interactive graph‑agent baselines. Ablations confirm both structural operators and policy training (SFT+GRPO) contribute to final performance; task‑adaptive operator usage is empirically observed.
Critical weaknesses
  1. Heavy idealized oracle assumption for structural operators (major realism limitation) Structural operators have full access to noise‑free, complete ground‑truth graph topology to return exact graph statistics. This is far from many real‑world graph agent deployments, where graphs are partial, noisy, contain missing edges or corrupted node connections. The paper provides zero ablation under graph corruption / partial observation. It remains unknown whether the demonstrated large performance gains will transfer to less‑ideal real‑world graph settings. Simply adding a discussion paragraph cannot fully substitute empirical evidence here.
  2. Evaluation heavily biased toward successful cases; failure analysis is missing All case studies show correct predictions. There is no systematic analysis of failure modes: we cannot tell whether errors stem from bad operator selection, misleading evidence returned by operators, or flawed high‑level reasoning after collecting evidence. Without representative failure trajectories or aggregated error statistics, readers only see the best‑behaved slices of agent behaviour. This weakens our understanding of when and why the method breaks.
  3. Strong dependency on high‑quality teacher trajectories from a closed‑source powerful LLM The core SFT stage relies on trajectories generated by DeepSeek‑V4‑Flash (proprietary large model). No experiments or ablations are provided for scenarios where such high‑quality teacher trajectories are unavailable. It is unclear whether cheaper self‑bootstrapping alternatives (e.g. STaR‑style iterative self‑improvement) can match the performance. This raises questions about the generality and practical deployability of the training pipeline.
  4. Agent inference cost is unquantified; reward design carries tangible risk of mis‑optimization
  • No reported metrics: average operator calls per sample, wall‑clock inference latency, sensitivity to maximum interaction turn budget. Agentic multi‑turn tool calling brings non‑negligible overhead; we have no idea how large the practical cost gap is compared to non‑agent graph‑LLM baselines.
  • The R_query reward component gives bonus for correct predictions after tool invocation and penalty for incorrect predictions without tools. This creates an incentive for redundant, unnecessary tool‑calls even when semantic evidence is already sufficient. The paper does not analyse whether over‑calling actually occurs.
  1. Limited out‑of‑distribution stress‑testing Zero‑shot test graphs are from domains already broadly similar to training‑set domains (citation, product co‑purchase, social post graphs, all text‑attributed homogeneous graphs). There is no stress‑test on substantially heterogeneous graphs (e.g. heterogeneous graphs, knowledge graphs). We cannot confirm how well the learned operator‑call policy generalizes to more drastically out‑of‑distribution graph scenarios.
Questions for authors

Please see my comments in weakness.

4 comments

We thank the reviewer for recognizing the motivation for structure-as-tool graph reasoning and the gains over prior interactive graph agents. We address the concerns below and distinguish our supported findings from remaining limitations.

W1. Robustness to Missing Edges

Thank you for highlighting the importance of robustness to incomplete graph observations.

Our operators compute exact statistics on the observed working graph, not on an assumed complete real-world topology. They access only observed edges, with the queried edge masked for LP, and have no access to hidden target labels or unobserved edges.

We additionally test random removal of 10%/20% of observed edges on the same 1,000 PubMed LP examples. We compare StructSeek with representative baselines under the same edge-removal settings.

MethodNo removal10% removal20% removal
RevGAT50.050.050.0
GraphICL-3B63.864.163.5
Search-o1-3B55.855.656.0
StructSeek-3B88.983.778.4

StructSeek retains the highest accuracy under both removal levels, exceeding the strongest baseline by 19.6 and 14.9 percentage points, respectively, but its accuracy falls by 10.5 points at 20% removal. While the baselines remain largely unchanged under edge removal, StructSeek exhibits greater sensitivity to missing edges, suggesting that its predictions make more direct use of graph topology. Nevertheless, it maintains a substantial performance advantage even with 20% of edges removed.

W2. Failure Analysis

We appreciate the request for a systematic analysis of failure cases.

We descriptively categorized all 277 failed LP trajectories (these categories are not causal attributions): 55.60% involved misleading but correctly computed structural signals, 15.52% exhibited identifiable high-level reasoning errors, and 28.88% remained ambiguous. The two cases below illustrate misleading structural evidence and potential limitations in how the model interprets and combines evidence:

Dataset and queryActual call sequence and returned evidencePrediction / Ground truth
PubMed (871, 18496)common_neighbors: 0 → path_between: distance 5 → final answerNo / Yes
Amazon-Photo (8571, 29998)common_neighbors: 0 → path_between: distance 5 → bridging_paths: 0 → final answerYes / No

In the PubMed case, the model treats weak structural connectivity as evidence against a true link, producing a false negative. This illustrates that the absence of strong local connectivity does not necessarily imply the absence of a relationship.

In the Photo case, the model favors its claimed semantic similarity despite weak structural support, producing a false positive. This suggests a potential reasoning failure, although the trace does not support an unambiguous attribution.

These examples illustrate the limits of interpreting or combining correctly computed structural measurements; they do not establish which alternative tool choices would have succeeded. We cannot uniquely attribute either failure to operator selection versus final reasoning from the reported statistics alone. The revised appendix includes these failure cases and the aggregate failure analysis (Appendix D.2).

W3. Teacher Supervision

Thank you for raising the concern about reliance on proprietary teacher supervision.

Teacher trajectories provide a useful foundation for tool learning. SFT familiarizes the small model with structural operators and their invocation patterns, while RL further optimizes its evidence acquisition policy. To examine whether teacher supervision is indispensable, we evaluate an RL-only variant initialized from Qwen2.5-3B-Instruct. It improves LP accuracy over the backbone by +9.5/+2.8/+7.7/+15.0 points on PubMed/Photo/Computers/Reddit, respectively (mean +8.75 points). These results show that teacher demonstrations are not strictly required to obtain improvements over the untrained backbone, but do not show that RL-only matches SFT followed by RL. Whether self-bootstrapping approaches such as STaR can achieve comparable performance remains an open question. The proprietary teacher is used only for offline demonstration generation, not inference.

W4. Inference Cost and Reward Design

We appreciate the concerns about inference overhead and possible incentives for unnecessary tool calls.

We report average accuracy and inference cost across representative baseline families and a matched untrained backbone with the same six operators:

MethodAvg. accuracy (%)Tokens / instanceCalls / instanceLatency (s)
RevGAT33.39——0.0017
GraphICL-3B50.69899—0.614
Search-o1-3B49.101,5770.651.313
Qwen2.5-3B-Instruct + six operators55.239,3192.513.53
StructSeek-3B77.115,7471.662.28

Accuracy and tool calls are averaged over eight task–dataset settings (four LP and four NC).

Relative to the matched untrained agent, StructSeek uses 38.3% fewer tokens, fewer calls (2.51 → 1.66), and less time (3.53 → 2.28 s), while improving accuracy. It remains more expensive than non-interactive baselines; our claim is an accuracy–cost trade-off, not universally faster inference.

We further evaluate the sensitivity to the maximum interaction budget on four unseen LP graphs, varying the maximum total interaction turns from 2 to 11:

Maximum total interaction turnsAccuracy (%)Avg. tool callsLatency (s/instance)
289.831.000.74
391.531.811.42
492.682.021.93
1193.082.032.09

The results show a measurable but diminishing accuracy–cost trade-off as the interaction budget increases. Even with only 3 turns, StructSeek achieves 91.53% accuracy. Increasing the budget to 11 turns further improves accuracy to 93.08%, suggesting that while most instances can be solved with limited interactions, a small fraction of more challenging instances benefit from additional evidence acquisition.

The query reward grants a one-time +0.2 for a correct prediction after tool use and −0.2 for an incorrect prediction without tool use; additional calls earn no additional bonus. It encourages evidence use but does not explicitly penalize tool-call cost and may incentivize an unnecessary first call. Empirically, RL reduces average calls from 2.20 to 2.03 (LP) and 1.41 to 1.28 (NC); this does not prove every call is necessary.

W5. Cross-Domain Generalization

Thank you for pointing out the limits of the current out-of-distribution evaluation.

Our current operators target homogeneous graphs; heterogeneous or knowledge graphs with typed relations require a relation-aware interface and are not validated by the present study. To broaden the application domains within our supported setting, we additionally test OpenFlights (airport routes) and STRING (protein associations), with 500 positive and 500 negative LP instances per graph:

MethodOpenFlightsSTRING
RevGAT59.452.4
GraphICL-3B50.277.0
Search-o1-3B53.265.8
StructSeek-3B95.480.4

These results support cross-application-domain transfer among homogeneous graphs, not generalization to heterogeneous graph schemas or robustness to arbitrary structural shifts.

After reading the authors's feedback, I plan to increase score to 3

Thank you again for your careful review and constructive suggestions. Your insightful comments have helped us identify areas for improvement and significantly enhance the quality of our paper. We sincerely appreciate your time, effort, and valuable feedback.

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

This paper proposes StructSeek, an interactive graph agent for zero-shot graph learning that actively acquires semantic and structural evidence through dedicated graph operators. The method enables LLMs to directly access structural information, such as common neighbors and shortest paths, rather than inferring it from serialized graph contexts. StructSeek learns when and which operators to invoke through supervised fine-tuning on teacher trajectories followed by reinforcement learning. Experiments on four unseen graphs covering node classification and link prediction show improvements over existing baselines, particularly for link prediction. Additional ablation studies and tool usage analysis demonstrate the effectiveness of structural operators and the learned evidence acquisition policy.

Critical strengths
  1. The paper provides a clear motivation and is well presented, with clear and visually appealing figures.

  2. Although the paper mainly focuses on link prediction (LP), it also evaluates node classification (NC), providing broader experimental coverage.

  3. The baselines cover several families of graph learning methods, including GNN-based methods, static-context Graph LLMs, and interactive graph agents.

Critical weaknesses
  1. The methodological novelty is limited in the agentic zero-shot graph learning setting. The agentic graph search pipeline has already been explored in prior works, such as GraphCoT and AgentGL mentioned in the paper, and another work GraphSearch (https://arxiv.org/pdf/2601.08621). The proposed framework largely follows these existing approaches, with the main difference being the introduction of several additional structural tools for link prediction. It remains unclear whether this constitutes a substantial methodological contribution.

  2. The necessity of semantic operators for link prediction is unclear. Figure 4 clearly presents the tool-calling distribution, but the trained model rarely selects 'read_one_hop_similar' or 'read_two_hop_similar' for link prediction. An additional ablation removing these two operators from the tool pool would help clarify their necessity and potential computational overhead.

  3. The efficiency is unclear. The paper does not provide a detailed comparison of training and inference efficiency against GNN-based and static-context LLM-based methods. Since the proposed agentic framework involves multiple rounds of tool calls, it would be useful to report the additional latency, computational cost, and token consumption.

Questions for authors
  1. The semantic operators return at most 5 neighboring nodes. How sensitive is the performance to the number of returned neighbors? Also, how are these neighbors selected?

  2. Although the paper emphasizes cross-domain generalization, most unseen test graphs belong to domains already represented during training, with only Reddit representing a different domain category. Could the authors provide experiments on additional unseen graph domains to further support the generalization claim?

  3. It remains unclear whether the performance gains mainly come from improved evidence acquisition (tool selection and guidance) or better final answer prediction after SFT and RL.

Comment: A vertical separator between the LP and NC columns in Table 1 would improve readability.

4 comments

We thank the reviewer for the constructive feedback and for recognizing the paper's motivation, presentation, and experimental coverage. We address the concerns below.

W1. Methodological Contribution

Thank you for raising the important question of methodological novelty.

Our contribution is not graph-agent interaction, tool calling, or the individual graph algorithms themselves, but the combination of directly queryable structural evidence with a learned acquisition policy. Existing graph agents such as AgentGL and GraphSearch already support topology-aware graph exploration and retrieval. StructSeek differs by exposing pair-specific structural computations as explicit operator outputs, such as common-neighbor counts, shortest-path distances, and length-three path counts, rather than relying primarily on topology-guided candidate retrieval and the LLM's interpretation of retrieved node contexts(Figures 1–2). The learned policy further determines which structural evidence to acquire based on previous observations and when to stop.

To further substantiate this contribution, we additionally conducted a matched operator-pool ablation in response to Q3, comparing semantic-only operators with the full operator pool under different training configurations. The results show that structural operators improve mean LP accuracy across four unseen graphs by 11.90 points without training, 7.07 points with RL-only training, and 10.18 points with SFT-only training. These results isolate the benefit of making structural measurements available under matched backbone and training configurations; they do not by themselves establish that the learned calling policy is better than a fixed policy.

The revised related-work discussion now makes this distinction explicit and cites GraphSearch (arXiv:2601.08621), while acknowledging earlier work on agentic graph exploration and graph tools (Section 4).

W2. Semantic-Operator Ablation

Thank you for suggesting this targeted ablation of the semantic operators.

StructSeek is designed to handle both LP and NC within a single model, selecting structural or semantic operators according to the task (Figure 4). We removed the two semantic operators from the trained StructSeek-3B model while keeping its weights and other inference settings fixed. The average LP accuracies are 93.23% and 93.50%, respectively, a difference of only 0.28 percentage points:

DatasetFull operator poolWithout semantic operators
PubMed88.3089.80
Amazon-Photo89.6089.80
Amazon-Computers95.4094.70
Reddit99.6099.70
Average93.2393.50

LP accuracy (%); 1,000 instances per graph.

Removing the operators reduces cumulative token usage by 413 tokens per instance, largely consistent with shorter tool descriptions. Average calls (2.03 → 2.02) and latency (4.53 → 4.56 s) remain nearly unchanged. These results indicate that semantic operators are not needed for strong LP performance in this setting. We retain them because the same policy also handles NC, where textual neighborhood evidence is relevant; the LP cost of including them is small in this measurement.

W3. Training and Inference Cost

We appreciate the request for a clearer account of training and inference costs.

We report average accuracy and inference cost across representative baseline families and a matched untrained backbone with the same six operators:

MethodAvg. accuracy (%)Tokens / instanceCalls / instanceLatency (s)
RevGAT33.39——0.0017
GraphICL-3B50.69899—0.614
Search-o1-3B49.101,5770.651.313
Qwen2.5-3B-Instruct + six operators55.239,3192.513.53
StructSeek-3B77.115,7471.662.28

Accuracy and tool calls are averaged over eight task–dataset settings (four LP and four NC).

Relative to the matched untrained agent, StructSeek uses 38.3% fewer tokens, fewer calls (2.51 → 1.66), and less time (3.53 → 2.28 s), while improving accuracy. It remains more expensive than non-interactive baselines; our claim is an accuracy–cost trade-off, not universally faster inference. Training uses teacher-trajectory SFT followed by GRPO, with four NVIDIA A100 GPUs for each model size. SFT takes approximately 0.5 hours, followed by approximately 4.5 hours of GRPO training. Latency figures are measured under the respective runs and should not be read as hardware-matched speedups across baseline families.

Q1. Semantic Neighbor Selection

Thank you for asking how semantic neighbors are selected and how sensitive the results are to their number. We evaluate the sensitivity to the maximum number of returned semantic neighbors (K) using StructSeek-3B on node classification:

DatasetK = 3K = 5K = 10
PubMed79.080.079.8
Amazon-Photo44.444.944.9

K = 5 performs best or ties for best, with no gain at K = 10. Eligible neighbors are ranked by TF-IDF cosine similarity between their descriptions and the target node's text, without labels; if fewer than K are available, all are returned.

Q2. Cross-Domain Generalization

We appreciate the suggestion to test transfer to additional application domains.

We add two application domains beyond the original citation/product/social graph coverage: OpenFlights (airport routes) and STRING (yeast protein physical associations). Each graph contains 500 positive and 500 negative LP instances.

MethodOpenFlightsSTRING
RevGAT59.452.4
GraphICL-3B50.277.0
Search-o1-3B53.265.8
StructSeek-3B95.480.4

StructSeek performs best among these representative baselines on both graphs, strengthening evidence for cross-domain transfer under the evaluated LP protocol. The revised paper describes the additional graph construction and evaluation protocol, including negative sampling and target-edge masking (Appendix A).

Q3. Sources of Performance Gains

Thank you for asking us to disentangle the contributions of structural evidence and training.

We compare semantic-only (two operators) and full (six operators) pools using the same Qwen2.5-3B-Instruct backbone and matched training configurations:

Operator poolUntrainedRL-onlySFT-only
Semantic only52.0065.5880.25
All operators63.9072.6590.43
Structural-operator gain+11.90+7.07+10.18

Average LP accuracy (%) across four unseen graphs.

Structural operators improve accuracy with and without training, while SFT and RL provide further gains. Figure 6 shows additional RL improvements of 5.8, 2.4, and 2.7 points on PubMed, Photo, and Computers, respectively. We also observe evidence-conditioned follow-up actions: after path_between returns distance 2, distance 3, or no path on PubMed, the agent invokes bridging_paths in 33.1%, 93.2%, and 1.7% of cases, respectively (414 instances). This supports non-fixed, observation-dependent behavior, although it is not a causal comparison with a fixed policy. These ablations demonstrate the contributions of structural evidence and policy training to end-to-end performance. However, they do not fully separate improvements in tool selection from those in final-answer reasoning, as training affects both. The revised experimental discussion distinguishes the contributions of operator availability and policy training, while acknowledging that the current ablations do not isolate tool selection from final-answer reasoning (Section 3.3).

C1. Table Formatting

Thank you for the helpful presentation suggestion.

We have added a vertical separator between the LP and NC column groups in Table 1.

Thank you for the detailed responses and substantial additional experiments, which have addressed most of my empirical concerns. However, my main concern for W1 remains. While the authors emphasize “the combination of directly queryable structural evidence with a learned acquisition policy,” GraphCoT already exposes direct structural queries such as NodeDegree and NeighbourCheck. StructSeek appears to primarily extend this existing paradigm with pairwise structural operators tailored to link prediction, rather than introducing a fundamentally new approach to structural evidence acquisition. As mentioned in Q3 reply, the ablations “do not fully separate improvements in tool selection from those in final-answer reasoning,” leaving the distinct performance contribution of the learned acquisition policy insufficiently isolated. Therefore, I will maintain my original score.

Thank you for the follow-up. We clarify both remaining concerns on W1 below.

GraphCoT's NodeDegree and NeighbourCheck return individual node statistics and neighbor lists, respectively. They do not directly provide structural relationships between node pairs. For link prediction, the LLM must still compare these observations to infer neighborhood overlap or reconstruct multi-hop connectivity, a difficulty highlighted by GraphCoT's failure analysis (Fig. 5). Consistently, its zero-shot LP performance remains near random across both 3B and 7B backbones (our Table 1).

StructSeek introduces a different approach to acquiring structural evidence: directly querying graph operators that compute relationships between target nodes. Operators such as common_neighbors, path_between, and bridging_paths return explicit pairwise structural measurements, rather than requiring the LLM to reconstruct them from node-level observations. This shifts structural computation from the LLM to the graph, allowing the LLM to reason directly over computed structural evidence.

StructSeek changes both how structural evidence is computed and acquired. The learned policy selects relevant structural evidence based on previous observations. As shown in Table 13, bridging_paths is invoked in 93.2% of cases when the shortest-path distance is 3, compared with 33.1% when it is 2 and only 1.7% when no path exists, demonstrating evidence-conditioned acquisition.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.