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

arXiv:2511.07734v2 Announce Type: replace-cross Abstract: 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.

Abstract: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.

Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Social and Information Networks (cs.SI); Signal Processing (eess.SP)

arXiv:2511.07734 [cs.LG]

(or arXiv:2511.07734v2 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2511.07734 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

analiza aiqbench

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

Subiecte conexe