Bayesian Optimization of Functions over Node Subsets in Graphs
<|reference_start|>Bayesian Optimization of Functions over Node Subsets in Graphs: 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.<|reference_end|>
@article{liang2024bayesian,
    title={Bayesian Optimization of Functions over Node Subsets in Graphs},
    author={Huidong Liang, Xingchen Wan, Xiaowen Dong},
    journal={arXiv preprint arXiv:2405.15119},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.15119},
    primaryClass={cs.LG stat.ML}
}