  We address the problem of optimizing over functions defined on node subsets
in a graph. The optimization of such functions is often a non-trivial task
given their combinatorial, black-box and expensive-to-evaluate nature. Although
various algorithms have been introduced in the literature, most are either
task-specific or computationally inefficient and only utilize information about
the graph structure without considering the characteristics of the function. To
address these limitations, we utilize Bayesian Optimization (BO), a
sample-efficient black-box solver, and propose a novel framework for
combinatorial optimization on graphs. More specifically, we map each $k$-node
subset in the original graph to a node in a new combinatorial graph and adopt a
local modeling approach to efficiently traverse the latter graph by
progressively sampling its subgraphs using a recursive algorithm. Extensive
experiments under both synthetic and real-world setups demonstrate the
effectiveness of the proposed BO framework on various types of graphs and
optimization tasks, where its behavior is analyzed in detail with ablation
studies.
