# Bayesian Optimisation of Functions on Graphs

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 48 references that are in the map.
- First posted on arXiv 8 Jun 2023.

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

- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Scalable Global Optimization via Local Bayesian Optimization](https://mlsanity.com/paper/1910.01739/) (2019)
- [Neural Architecture Search with Bayesian Optimisation and Optimal Transport](https://mlsanity.com/paper/1802.07191/) (2018)
- [Multi-Objective Bayesian Optimization over High-Dimensional Search Spaces](https://mlsanity.com/paper/2109.10964/) (2021)
- [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)
- [GEMSEC: Graph Embedding with Self Clustering](https://mlsanity.com/paper/1802.03997/) (2018)
- [Think Global and Act Local: Bayesian Optimisation over High-Dimensional Categorical and Mixed Search Spaces](https://mlsanity.com/paper/2102.07188/) (2021)
- [Bayesian Semi-supervised Learning with Graph Gaussian Processes](https://mlsanity.com/paper/1809.04379/) (2018)
- [Mercer Features for Efficient Combinatorial Bayesian Optimization](https://mlsanity.com/paper/2012.07762/) (2020)
- [Gaussian Processes on Graphs via Spectral Kernel Learning](https://mlsanity.com/paper/2006.07361/) (2020)
- [Graph Convolutional Gaussian Processes](https://mlsanity.com/paper/1905.05739/) (2019)
- [Bayesian Generational Population-Based Training](https://mlsanity.com/paper/2207.09405/) (2022)
- [Gaussian Processes Over Graphs](https://mlsanity.com/paper/1803.05776/) (2018)
- [Adaptive Gaussian Processes on Graphs via Spectral Graph Wavelets](https://mlsanity.com/paper/2110.12752/) (2021)
- [Graph Convolutional Gaussian Processes For Link Prediction](https://mlsanity.com/paper/2002.04337/) (2020)
- [Maximizing and Satisficing in Multi-armed Bandits with Graph Information](https://mlsanity.com/paper/2108.01152/) (2021)
- [Deep Bayesian Optimization on Attributed Graphs](https://mlsanity.com/paper/1905.13403/) (2019)

## Built on by (most cited first, 7 of 7)

- [Adaptive Batch Sizes for Active Learning A Probabilistic Numerics Approach](https://mlsanity.com/paper/2306.05843/) (2023)
- [Graph Random Features for Scalable Gaussian Processes](https://mlsanity.com/paper/2509.03691/) (2025)
- [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)
- [Conformalized Gaussian processes for online uncertainty quantification over graphs](https://mlsanity.com/paper/2510.06181/) (2025)
- [Omnipresent Yet Overlooked: Heat Kernels in Combinatorial Bayesian Optimization](https://mlsanity.com/paper/2510.26633/) (2025)
- [Global Optimization on Graph-Structured Data via Gaussian Processes with Spectral Representations](https://mlsanity.com/paper/2511.07734/) (2025)

## Abstract (arXiv)

The increasing availability of graph-structured data motivates the task of optimising over functions defined on the node set of graphs. Traditional graph search algorithms can be applied in this case, but they may be sample-inefficient and do not make use of information about the function values; on the other hand, Bayesian optimisation is a class of promising black-box solvers with superior sample efficiency, but it has been scarcely been applied to such novel setups. To fill this gap, we propose a novel Bayesian optimisation framework that optimises over functions defined on generic, large-scale and potentially unknown graphs. Through the learning of suitable kernels on graphs, our framework has the advantage of adapting to the behaviour of the target function. The local modelling approach further guarantees the efficiency of our method. Extensive experiments on both synthetic and real-world graphs demonstrate the effectiveness of the proposed optimisation framework.