  This paper focuses on Bayesian Optimization (BO) for objectives on
combinatorial search spaces, including ordinal and categorical variables.
Despite the abundance of potential applications of Combinatorial BO, including
chipset configuration search and neural architecture search, only a handful of
methods have been proposed. We introduce COMBO, a new Gaussian Process (GP) BO.
COMBO quantifies "smoothness" of functions on combinatorial search spaces by
utilizing a combinatorial graph. The vertex set of the combinatorial graph
consists of all possible joint assignments of the variables, while edges are
constructed using the graph Cartesian product of the sub-graphs that represent
the individual variables. On this combinatorial graph, we propose an ARD
diffusion kernel with which the GP is able to model high-order interactions
between variables leading to better performance. Moreover, using the Horseshoe
prior for the scale parameter in the ARD diffusion kernel results in an
effective variable selection procedure, making COMBO suitable for high
dimensional problems. Computationally, in COMBO the graph Cartesian product
allows the Graph Fourier Transform calculation to scale linearly instead of
exponentially. We validate COMBO in a wide array of realistic benchmarks,
including weighted maximum satisfiability problems and neural architecture
search. COMBO outperforms consistently the latest state-of-the-art while
maintaining computational and statistical efficiency.
