- Rating
- 3
- Confidence
- 3(+1)
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies Bayesian optimization over graph nodes when both objective evaluations and graph-structure queries have limited budgets. It fits a graph-valid low-rank model to observed adjacency entries and uses its Laplacian spectrum to build a global Gaussian process surrogate. The central idea is that objective evaluations learn shared coefficients, while structural queries improve node features. This motivates a knowledge-gradient (KG) rule for pair queries and a pin-then-uniform rule for row queries. The paper provides conditional identification guarantees and a regret bound that accounts for errors in the learned geometry. Experiments on synthetic, molecular, biological, and Wikipedia graphs show lower mean final regret than the compared baselines across ten objectives in the row-query study.
Critical strengths
- The distinction between learning shared coefficients and learning node features explains how objective evaluations and structural queries contribute to optimization. The global surrogate also allows the method to compare nodes beyond the currently revealed neighborhood. Together, these ideas provide a meaningful approach to graph optimization with limited structural access.
- The row-query experiments compare against random search, local search, and local graph BO under matched query budgets. Improvements on real objectives, particularly gene essentiality, provide evidence beyond synthetic objectives drawn from the assumed GP prior. These results support the practical value of the global surrogate, independently of the proposed KG rule.
Critical weaknesses
The pair-query experiments do not isolate the benefit of KG scoring. The KG arm uses landmark queries, pinning, and conditional membership updates, while the uniform-pair arm samples from all unobserved pairs and follows a different update procedure. As acknowledged in Appendices F.5 and G.3, this comparison changes more than the query-selection rule. The gains could therefore come from the observation pattern or membership updates. This limits the evidence for the decision-aware acquisition contribution, although it does not undermine the row-query results supporting the global surrogate.
Questions for authors
- Does KG still improve regret if you keep the landmarks, pinning budget, membership updates, and total query budget fixed, and replace only KG selection with random eligible landmark queries?
- Please verify the dense/latent and ESOL entries in Table 5 against the per-seed records, as requested by the note on page 28. Also clarify the mismatch between Table 6’s caption and its BioPlex results at . Do any necessary corrections change the corresponding conclusions?
Response to Questions (Part IV)
The term does not come from the graph structure. It is the part of the objective that no graph structure predicts, and the bound decays to zero when the objective has no such part.
Origin of the term. The kernel has two parts (Eq. 4). The structured rank-d part carries what the graph shares across nodes. The bulk part σb2I models variation that is specific to each node and independent across nodes. Identifying the whole graph removes the two geometry-error terms of the bound (Corollary A.1), but it says nothing about a node-specific component. Since each node is evaluated once, this component cannot be averaged out by repeated evaluations.
Lower bound. Remark A.1 makes this concrete. For an objective that is a single spike of height η at a random node, every method, with any structural budget, has an expected simple regret of at least (1−(N0+T)/n)η, where N0 is the number of initial evaluations. A term of this order is therefore unavoidable. It reflects the objective, not a loss of information in how the identified structure is used.
Objectives without node-specific variation. If the objective has no node-specific component (η=0 in Assumption A.1), the confidence parameter is κ=Bs, the norm bound of the structured part, and does not depend on σb. Choosing σb2 of order 1/T then gives, after identification, a bound of order dlogT/T, which decays to zero at the usual rate of a d-dimensional linear model.
Cumulative regret. The proof bounds the simple regret by the average of the per-round costs of Eq. 10 (Appendix C). The same argument therefore bounds the cumulative regret over the rounds before the optimum is evaluated, by a quantity of order dTlogT in the case above, which is sublinear. After the optimum is evaluated, a method that evaluates each node once has to evaluate worse nodes, which is why we state the result in simple regret.
We believe these responses address the three weaknesses and the three questions. We would be grateful if the reviewer would consider updating the score. If anything remains unclear, we are happy to address it before the discussion closes.