Global Optimization on Graph-Structured Data via Gaussian Processes with Spectral Representations
This work addresses the problem of optimizing expensive black-box objectives on graphs for researchers and practitioners in machine learning, offering a novel method for a known bottleneck.
The paper tackles the challenge of extending Bayesian optimization to graph-structured domains by introducing a scalable framework that uses low-rank spectral representations to build Gaussian process surrogates from sparse observations, achieving faster convergence and improved optimization performance in experiments on synthetic and real-world datasets.
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 on either full graph topology-impractical for large or partially observed graphs-or incremental exploration, which can lead to slow convergence. We introduce a scalable framework for global optimization over graphs that employs low-rank spectral representations to build Gaussian process (GP) surrogates from sparse structural observations. The method jointly infers graph structure and node representations through learnable embeddings, enabling efficient global search and principled uncertainty estimation even with limited data. We also provide theoretical analysis establishing conditions for accurate recovery of underlying graph structure under different sampling regimes. Experiments on synthetic and real-world datasets demonstrate that our approach achieves faster convergence and improved optimization performance compared to prior methods.