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

arXiv: https://arxiv.org/abs/2511.07734 · HTML: https://mlsanity.com/paper/2511.07734/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 65 references that are in the map.
- First posted on arXiv 11 Nov 2025.

## Builds on (most cited first, 23 of 23)

- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [BANANAS: Bayesian Optimization with Neural Architectures for Neural Architecture Search](https://mlsanity.com/paper/1910.11858/) (2019)
- [The Laplacian in RL: Learning Representations with Efficient Approximations](https://mlsanity.com/paper/1810.04586/) (2018)
- [Combinatorial Bayesian Optimization using the Graph Cartesian Product](https://mlsanity.com/paper/1902.00448/) (2019)
- [ChemBO: Bayesian Optimization of Small Organic Molecules with Synthesizable Recommendations](https://mlsanity.com/paper/1908.01425/) (2019)
- [Mat'ern Gaussian Processes on Graphs](https://mlsanity.com/paper/2010.15538/) (2020)
- [Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel](https://mlsanity.com/paper/1309.4111/) (2013)
- [Rates of Convergence of Spectral Methods for Graphon Estimation](https://mlsanity.com/paper/1709.03183/) (2017)
- [Concentration and regularization of random graphs](https://mlsanity.com/paper/1506.00669/) (2015)
- [Estimating Mixed Memberships with Sharp Eigenvector Deviations](https://mlsanity.com/paper/1709.00407/) (2017)
- [Low-Rank Matrix and Tensor Completion via Adaptive Sampling](https://mlsanity.com/paper/1304.4672/) (2013)
- [Bayesian optimisation under uncertain inputs](https://mlsanity.com/paper/1902.07908/) (2019)
- [A Bayesian Optimization Framework for Finding Local Optima in Expensive Multi-Modal Functions](https://mlsanity.com/paper/2210.06635/) (2022)
- [Bayesian Optimisation of Functions on Graphs](https://mlsanity.com/paper/2306.05304/) (2023)
- [BoGrape: Bayesian optimization over graphs with shortest-path encoded](https://mlsanity.com/paper/2503.05642/) (2025)
- [Bayesian Optimization through Gaussian Cox Process Models for Spatio-temporal Data](https://mlsanity.com/paper/2401.14544/) (2024)
- [Graph Bayesian Optimization for Multiplex Influence Maximization](https://mlsanity.com/paper/2403.18866/) (2024)
- [Graph Bayesian Optimization: Algorithms, Evaluations and Applications](https://mlsanity.com/paper/1805.01157/) (2018)
- [Deep Bayesian Optimization on Attributed Graphs](https://mlsanity.com/paper/1905.13403/) (2019)
- [Matrix Completion from General Deterministic Sampling Patterns](https://mlsanity.com/paper/2306.02283/) (2023)
- [Global optimization of graph acquisition functions for neural architecture search](https://mlsanity.com/paper/2505.23640/) (2025)
- [Bayesian Optimization of Functions over Node Subsets in Graphs](https://mlsanity.com/paper/2405.15119/) (2024)

## Abstract (arXiv)

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.