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.
Code (1)
Tasks
Bayesian OptimizationCombinatorial OptimizationSimilar Papers 제목 키워드 기반
High-Dimensional Bayesian Optimization via Additive Models with Overlapping Groups
Bayesian optimization (BO) is a popular technique for sequential black-box function optimization, with applications including parameter tuning, robotics, environmental monitoring, and more. One of the most important chal…
Additive modelsBayesian OptimizationHyperparameter OptimizationVocal Bursts Intensity PredictionBayesian Optimization for Unknown Cost-Varying Variable Subsets with No-Regret Costs
Bayesian Optimization (BO) is a widely-used method for optimizing expensive-to-evaluate black-box functions. Traditional BO assumes that the learner has full control over all query variables without additional constraint…
Bayesian OptimizationBayesian Optimization of Function Networks with Partial Evaluations
Bayesian optimization is a powerful framework for optimizing functions that are expensive or time-consuming to evaluate. Recent work has considered Bayesian optimization of function networks (BOFN), where the objective f…
Bayesian OptimizationHigh-Dimensional Bayesian Optimization via Tree-Structured Additive Models
Bayesian Optimization (BO) has shown significant success in tackling expensive low-dimensional black-box optimization problems. Many optimization problems of interest are high-dimensional, and scaling BO to such settings…
Additive modelsBayesian OptimizationGraph LearningVocal Bursts Intensity PredictionGraph Bayesian Optimization: Algorithms, Evaluations and Applications
Network structure optimization is a fundamental task in complex network analysis. However, almost all the research on Bayesian optimization is aimed at optimizing the objective functions with vectorial inputs. In this wo…
Bayesian Optimization