# Mercer Features for Efficient Combinatorial Bayesian Optimization

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Dec 2020.

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

- [Recent Advances in Bayesian Optimization](https://mlsanity.com/paper/2206.03301/) (2022)
- [High-Dimensional Bayesian Optimisation with Variational Autoencoders and Deep Metric Learning](https://mlsanity.com/paper/2106.03609/) (2021)
- [GIBBON: General-purpose Information-Based Bayesian OptimisatioN](https://mlsanity.com/paper/2102.03324/) (2021)
- [Combining Latent Space and Structured Kernels for Bayesian Optimization over Combinatorial Spaces](https://mlsanity.com/paper/2111.01186/) (2021)
- [Bayesian Optimization over Discrete and Mixed Spaces via Probabilistic Reparameterization](https://mlsanity.com/paper/2210.10199/) (2022)
- [Bayesian Optimization over High-Dimensional Combinatorial Spaces via Dictionary-based Embeddings](https://mlsanity.com/paper/2303.01774/) (2023)
- [Bayesian Optimization over Hybrid Spaces](https://mlsanity.com/paper/2106.04682/) (2021)
- [A survey and benchmark of high-dimensional Bayesian optimization of discrete sequences](https://mlsanity.com/paper/2406.04739/) (2024)
- [SurCo: Learning Linear Surrogates For Combinatorial Nonlinear Optimization Problems](https://mlsanity.com/paper/2210.12547/) (2022)
- [Bayesian Optimization over Permutation Spaces](https://mlsanity.com/paper/2112.01049/) (2021)
- [Output Space Entropy Search Framework for Multi-Objective Bayesian Optimization](https://mlsanity.com/paper/2110.06980/) (2021)
- [Trieste: Efficiently Exploring The Depths of Black-box Functions with TensorFlow](https://mlsanity.com/paper/2302.08436/) (2023)
- [Global Optimization of Gaussian Process Acquisition Functions Using a Piecewise-Linear Kernel Approximation](https://mlsanity.com/paper/2410.16893/) (2024)
- [SOBER: Highly Parallel Bayesian Optimization and Bayesian Quadrature over Discrete and Mixed Spaces](https://mlsanity.com/paper/2301.11832/) (2023)
- [Bayesian Optimisation of Functions on Graphs](https://mlsanity.com/paper/2306.05304/) (2023)
- [Bayesian optimization for mixed variables using an adaptive dimension reduction process: applications to aircraft design](https://mlsanity.com/paper/2504.08682/) (2025)
- [MONGOOSE: Path-wise Smooth Bayesian Optimisation via Meta-learning](https://mlsanity.com/paper/2302.11533/) (2023)
- [Fourier Representations for Black-Box Optimization over Categorical Variables](https://mlsanity.com/paper/2202.03712/) (2022)
- [Optimistic Games for Combinatorial Bayesian Optimization with Application to Protein Design](https://mlsanity.com/paper/2409.18582/) (2024)
- [Random Postprocessing for Combinatorial Bayesian Optimization](https://mlsanity.com/paper/2309.02842/) (2023)
- [A Generative Neural Annealer for Black-Box Combinatorial Optimization](https://mlsanity.com/paper/2505.09742/) (2025)
- [Bayesian Optimization for Macro Placement](https://mlsanity.com/paper/2207.08398/) (2022)
- [Large-Batch, Iteration-Efficient Neural Bayesian Design Optimization](https://mlsanity.com/paper/2306.01095/) (2023)
- [Bayesian Optimization of Functions over Node Subsets in Graphs](https://mlsanity.com/paper/2405.15119/) (2024)
- [Discovery of Feasible 3D Printing Configurations for Metal Alloys via AI-driven Adaptive Experimental Design](https://mlsanity.com/paper/2601.17587/) (2026)
- [COM-BOM: Bayesian Exemplar Search for Efficiently Exploring the Accuracy-Calibration Pareto Frontier](https://mlsanity.com/paper/2510.01178/) (2025)
- [A reproducible comparative study of categorical kernels for Gaussian process regression, with new clustering-based nested kernels](https://mlsanity.com/paper/2510.01840/) (2025)

## Abstract (arXiv)

Bayesian optimization (BO) is an efficient framework for solving black-box optimization problems with expensive function evaluations. This paper addresses the BO problem setting for combinatorial spaces (e.g., sequences and graphs) that occurs naturally in science and engineering applications. A prototypical example is molecular optimization guided by expensive experiments. The key challenge is to balance the complexity of statistical models and tractability of search to select combinatorial structures for evaluation. In this paper, we propose an efficient approach referred as Mercer Features for Combinatorial Bayesian Optimization (MerCBO). The key idea behind MerCBO is to provide explicit feature maps for diffusion kernels over discrete objects by exploiting the structure of their combinatorial graph representation. These Mercer features combined with Thompson sampling as the acquisition function allows us to employ tractable solvers to find next structures for evaluation. Experiments on diverse real-world benchmarks demonstrate that MerCBO performs similarly or better than prior methods. The source code is available at https://github.com/aryandeshwal/MerCBO .