  The increasing availability of graph-structured data motivates the task of
optimising over functions defined on the node set of graphs. Traditional graph
search algorithms can be applied in this case, but they may be
sample-inefficient and do not make use of information about the function
values; on the other hand, Bayesian optimisation is a class of promising
black-box solvers with superior sample efficiency, but it has been scarcely
been applied to such novel setups. To fill this gap, we propose a novel
Bayesian optimisation framework that optimises over functions defined on
generic, large-scale and potentially unknown graphs. Through the learning of
suitable kernels on graphs, our framework has the advantage of adapting to the
behaviour of the target function. The local modelling approach further
guarantees the efficiency of our method. Extensive experiments on both
synthetic and real-world graphs demonstrate the effectiveness of the proposed
optimisation framework.
