Global Optimization on Graph-Structured Data via Gaussian Processes with Spectral Representations

Bayesian optimization (BO) is a powerful framework for optimizing expensive black-box objectives, yet extending it to graph-structured domains remains challenging due to the discrete and combinatorial nature of graphs. Existing approaches often rely either on full graph topology, which is impractical for large or partially observed graphs, or on incremental local exploration, which can lead to slow convergence. We introduce a scalable framework for global optimization over graphs that builds Gaussian process (GP) surrogates from low-rank spectral representations inferred from sparse structural observations. The method fits a low-rank graph surrogate to the observed connections and uses its spectrum to define a kernel over all nodes, so that function evaluations and structural observations jointly refine a global model, enabling efficient global search and principled uncertainty estimation even with limited data. We further show how a limited budget of structural observations can be allocated according to its expected value for the optimization. We also provide theoretical analysis establishing conditions under which the surrogate geometry is identified under different sampling regimes, and bounding the optimization error incurred under an estimated geometry. Experiments on synthetic and real-world datasets demonstrate that our approach achieves lower regret and improved optimization performance compared to prior methods.