- 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
- 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.
- 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
- 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.
- 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
- 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%?
- 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?
- 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?
- 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
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 pool | Untrained | RL-only | SFT-only |
|---|---|---|---|
| Semantic only | 52.00 | 65.58 | 80.25 |
| All operators | 63.90 | 72.65 | 90.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.
| Dataset | Teacher | StructSeek | Difference vs teacher (95% CI) | RL gain (95% CI) |
|---|---|---|---|---|
| PubMed | 75.0 | 88.4 | +13.4 [7.91, 18.78] | +5.8 [3.87, 7.73] |
| Photo | 92.5 | 89.9 | −2.6 [−6.69, 1.51] | +2.4 [0.22, 4.58] |
| Computers | 92.3 | 94.5 | +2.2 [−1.42, 5.80] | +2.7 [0.97, 4.43] |
| 97.7 | 99.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:
| Calls | LP (n=4,000) | NC (n=4,000) |
|---|---|---|
| 1 | 735 | 2,909 |
| 2 | 2,418 | 1,081 |
| 3 | 833 | 10 |
| ≥4 | 14 | 0 |
On 414 PubMed instances where path_between returned one of the following outcomes, the next action differed markedly:
| Returned evidence | Instances | Next: bridging_paths | Stop |
|---|---|---|---|
| Distance = 2 | 166 | 55 (33.1%) | 111 |
| Distance = 3 | 190 | 177 (93.2%) | 13 |
| No path | 58 | 1 (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.
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:
These distributions confirm substantial structural separability under random negatives. We therefore add structural heuristics and source-trained LP methods (accuracy, %):
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.
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.