acceptodds
Under review as a conference paper at ICLR 2027

Bayesian Optimization on Partially Observed Graphs

Abstract

We address Bayesian optimization (BO) over graph nodes where the black-box objective is expensive to evaluate and the graph topology is partially observed. A central challenge is that BO shares information through a globally defined kernel, while incomplete graph topology makes it unavailable, limiting existing methods to local, neighborhood-based exploration. Effective global BO in this regime therefore requires inferring a coherent surrogate geometry from sparse edge observations. We reconstruct a graph-valid low-rank surrogate from revealed edges and extract its Laplacian spectrum to induce a Gaussian process kernel over all nodes. Under this kernel, the posterior is a linear model in -dimensional node features: function evaluations learn a shared coefficient, and edge queries learn the features. For budgeted queries of adjacency entries or rows, we further derive decision-aware acquisition rules, including a knowledge-gradient rule for pair queries. We provide guarantees for surrogate identification under row and pair query patterns and for the decision error under an estimated geometry, which is charged only at the selected node and the optimum and enters the simple regret only through the identification time. On protein interaction networks, a molecular similarity graph, a Wikipedia page graph, and synthetic graphs, our method attains lower final regret than structure-free search and local graph BO on all ten objectives at matched budgets, and decision-aware pair queries improve on uniform ones at every tested budget. Code is available at https://anonymous.4open.science/r/global-graph-bo-code.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Bayesian optimization, spectral drawing, large-scale graph, structure acquisition

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_xNprOpenReview ↗
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
  1. 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.
  2. 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
  1. 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?
  2. 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 d=8d=8. Do any necessary corrections change the corresponding conclusions?
Reviewer_d1DyOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies BO over graph nodes when the graph's topology is only partially observed by the user through visited nodes and edges. Unlike existing methods that only explore the revealed neighbourhood, the proposed framework keeps a model of every node in the graph and search for the "global" optimum over all nodes. The main assumption is the adjacency matrices of the weighted graph is low rank, the paper then is able to formulate a graph completion problem through a constraint nonconvex optimization, where the solution is treated as the original unknown graph adjacency matrix used in normalized graph Laplacian to build the kernel, where an additional uncertainty w.r.t the graph topology is handled via a local linearization approximation. Given the predictive model, the paper propose two acquisition for optimization, at each round, it first use UCB to search for most promising node, and use knowledge gradient to reveal the graph toplolgy with an ad-hoc model representing the topology uncertainty. The theoretical analysis showed that if the real adjacency matrix is low rank, it is proved to be identified among sufficient reveal of edges, and after this unique identification, the method can be treated as a standard UCB setting hence enjoy the regret guarantee. The empirical results has considered a wide variaty of tasks with different node number and edge reveal rule per iteration, and the method showed competitive performance across different problem settings compared with baselines.

Critical strengths
  • A workable algorithm in an emerging problem setting: While the optimization of nodes when the graph is partially known is not entirely new, compared with the earlier local method, this method demonstrate competitive empirical performance, espcially that the method works when the node number is large.
Critical weaknesses
  • Ad-hoc topology uncertainty model for KG One of my biggest concern is that, aside from that they have two strategies for edge and node, the topology uncertainty model for KG looks rather arbitary, I think this part looks rather practical for me as it is disconnected purely from the previous graph completion task.
  • The slightly unclear edge reveal motivation: Although the paper has compared with a wide variaty of problem scale and problem setting, it is slightly unclear for me at what circumstances, there needs a rule for edge reveal , and to the end this problem setting, at least from current experiments demonstrates, looks a little bit artificial to me, especially given that each iter can evaluate so many edges.
  • Theoretical property: minor, but if there is a huge graph with still descent amount of rank, then the method will not have any guarantee given if the eval time is not sufficient to reveal the rank, which in practice maybe the case (minor because whether there is better option is unknown to my perspective)

Happy to reconsider my evaluation if the author could provide justifiable rebuttal on the above points.

Questions for authors
  • At the very beginning stage, will there have many minimum for the graph completion optimization?
  • How sensitive the choice of dd in terms of the performance of the problem given the real rank is unknown?
  • The theorem 1: can the author clairfy why there is a 2kσb2k\sigma_b term in simple regret? as this seems to indicate that even one identified the whole graph structure, you still cannot make use of this to get a sublinear cummulative regret bound.
2 comments
AuthorsOpenReview ↗

Response to Questions (Part IV)

Question 3: The 2κσb2\kappa\sigma_b term in Theorem 1

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-dd part carries what the graph shares across nodes. The bulk part σb2I\sigma_b^2I 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 η\eta at a random node, every method, with any structural budget, has an expected simple regret of at least (1−(N0+T)/n)η(1-(N_0+T)/n) \eta, where N0N_0 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\eta = 0 in Assumption A.1), the confidence parameter is κ=Bs\kappa = B_s, the norm bound of the structured part, and does not depend on σb\sigma_b. Choosing σb2\sigma_b^2 of order 1/T1/T then gives, after identification, a bound of order dlog⁡T/T\sqrt{d\log T/T}, which decays to zero at the usual rate of a dd-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 dTlog⁡T\sqrt{dT\log T} 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.

I thank the authors for their detailed rebuttal, which has addressed most of my concerns on weakness points and questions. I believe the paper is generally sound. My remaining concern is that, while Theorem 1 provides a general regret bound accounting for geometry estimation errors, it does not establish how these errors decrease as an end-to-end regret convergence rate (before the fully identified scenario). I would appreciate it if the authors could acknowledge this limitation (or rebuttal if I have misunderstood their results). I will increase my rating to positive side.

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

The paper introduces a global Bayesian optimization method for functions defined on partially observed graphs. The proposed method first learns a low-rank surrogate graph from queried edges, then applies GP on graph nodes using a structured-plus-bulk kernel. The authors then use a decision-aware structural acquisition method to reveal structure within a given budget.

Critical strengths
  1. This paper is overall well-written and easy to follow.
  2. The task setting in this paper is new (to the best of my knowledge) in the graph BO literature.
  3. The technical methodology is sound to me.
  4. This low-rank estimation of the adjacency matrix seems computationally efficient (but I am not sure how accurate it will be compared to the ground-truth graph structure).
Critical weaknesses

The proposed framework did not consider node features or edge features. While I don't think it is difficult to include them in the modelling process, this paper uses only the graph structure to predict target values on nodes, which may not reflect the conditions of real-world tasks.

Questions for authors
  1. I think the authors may need to make the setting clear compared to the previous work: [1] assumes the underlying graph G=[V,E]G=[V, E] is not fully known a priori, where we can only observe a subgraph G~=[V~,E~]\tilde{G} = [ \tilde{V}, \tilde{E}], with V~∈V\tilde{V} \in V and ∣V~∣<∣V∣|\tilde{V}| < |V|. However, the current work assumes VV is fully known, but EE is not fully known. That means the tasks in these works are under different assumptions. In this case, I think it would be better if the authors could explain more about why the task settings in this work are important in real-world applications, which can further justify the necessity of the proposed method.

  2. Can you explain why we have a budget for revealing the graph sturcuture in the experiment task, that is, does the task prohibits us from acquiring all edges at once?

  3. Because of the task setting, the baselines using local information are at a disadvantage since they are not using all the available information. Can you provide a global baseline (not the full-graph structure oracle) for the BO? e.g. a simple global graph kernel using available edges.

  4. Can you explain why some of your results in Table 1 are even better than the full graph spectral baseline?

Reference

[1] Bayesian Optimisation of Functions on Graphs. NeurIPS-2023

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.