Bayesian Optimization on Partially Observed Graphs

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 $d$-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.