  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 .
