This paper focuses on Bayesian Optimization - typically considered with continuous inputs - for discrete search input spaces, including integer, categorical or graph structured input variables. In Gaussian process-based Bayesian Optimization a problem arises, as it is not straightforward to define a proper kernel on discrete input structures, where no natural notion of smoothness or similarity could be provided. We propose COMBO, a method that represents values of discrete variables as vertices of a graph and then use the diffusion kernel on that graph. As the graph size explodes with the number of categorical variables and categories, we propose the graph Cartesian product to decompose the graph into smaller sub-graphs, enabling kernel computation in linear time with respect to the number of input variables. Moreover, in our formulation we learn a scale parameter per subgraph. In empirical studies on four discrete optimization problems we demonstrate that our method is on par or outperforms the state-of-the-art in discrete Bayesian optimization.

本文针对于组合搜索空间的优化问题，提出了一种基于高斯过程的贝叶斯优化算法，通过组合图的方法量化并且模拟变量之间的高阶交互，不仅能在可行性问题和神经架构搜索等方面取得比最先进的创新解决方案更好的结果，而且具有较好的计算效率和统计效率。

使用图笛卡尔积的组合贝叶斯优化