Research map / Graph learning / Graph algorithms and clustering
Bayesian Optimization of Functions over Node Subsets in Graphs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes GraphComBO, a Bayesian optimization framework that maps k-node subsets of a graph to a combinatorial "combo-graph" and traverses it with recursively sampled local combo-subgraphs as trust regions, using graph GP surrogates with EI.
Problem
Black-box, expensive, combinatorial optimization of functions defined over k-node subsets of a graph, where the graph may be only partially observed and revealed incrementally by queries.
Approach
Build a combinatorial graph whose nodes are k-node subsets (adjacent if they differ by one neighboring node swap), sample local ego-subgraphs recursively around a focal combo-node as trust regions, and run graph-Laplacian (diffusion kernel) GP BO with Expected Improvement inside them.
Key results
- GraphComBO generally outperforms all baselines on both synthetic and real-world tasks, with the advantage diminishing as k increases.
- Performance gains are smaller on WS and SBM where graph structure is less informative, and on the molecule GNN attack task where the function is less smooth; there BO behaves similarly to local search.
- Experiments use 300 queries, 20 random seeds, subset sizes k=4,8,16,32, and Q=4000 with failtol=30.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use GraphComBO instead of the compared baselines | node-subset optimization on synthetic and real-world graph tasks · Synthetic and real-world tasks | optimization performance | Helped |
| increase the subset size k | GraphComBO · Synthetic and real-world tasks | performance advantage over baselines | Hurt |
| apply BO to less-smooth functions on WS, SBM, or molecule graphs | GraphComBO · WS, SBM, and molecule network tasks | optimization performance | No clear effect |
Surprising findings
- On WS, SBM and the molecule GNN attack, BO performs comparably to local search, a random-surrogate baseline, because the functions are weakly smooth on the graph.
Limitations
- Performance of BO deteriorates as subset size k grows due to combinatorial explosion of combo-graph neighborhoods.
- Subgraph size Q and max hop are fixed hyperparameters rather than adaptive.
- Relies on random or domain-guided initialization and a local Laplacian-based surrogate that does not inject global graph information.
Experimental setup
Datasets: BA synthetic graph WS synthetic graph SBM synthetic graph 2D-grid Proximity contact network (primary school) Coauthor CS network Manhattan road networks ENZYMES molecule graphs OGB-arXiv
Benchmarks: synthetic BA/WS/SBM/2D-grid tasks SIR flattening the curve patient-zero tracing influence maximization on Coauthor CS road network resilience GNN black-box attack on ENZYMES
Metrics: regret cumulative optima
Baselines: Random Search k-Random Walk k-Local Search BFS DFS Local Search COMBO
Builds on: Bayesian optimization COMBO BayesOptG diffusion kernel
Closest papers by meaning
- Bayesian Optimisation of Functions on Graphs (NeurIPS 2023 · similarity 0.94)
- Bayesian Optimization of Combinatorial Structures (ICML 2018 · similarity 0.91)
- Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information (ICML 2021 · similarity 0.90)
- Bayesian Optimization of Function Networks with Partial Evaluations (ICML 2024 · similarity 0.89)
- Omnipresent Yet Overlooked: Heat Kernels in Combinatorial Bayesian Optimization (NeurIPS 2025 · similarity 0.87)
- Relaxing the Additivity Constraints in Decentralized No-Regret High-Dimensional Bayesian Optimization (ICLR 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.