Bayesian Optimization of Functions over Node Subsets in Graphs
Authors: Huidong Liang
Xingchen Wan
Xiaowen Dong
Venue: NeurIPS 2024 poster (2024)
Keywords: Bayesian Optimization
Graphs
Primary area: optimization
TL;DR: This paper extends Bayesian optimization to a novel graph setting, where the search space consists of node subsets in a generic graph.

Abstract: 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.

Bayesian Optimization of Functions over Node Subsets in Graphs
Huidong Liang
Xingchen Wan" Xiaowen Dong
Department of Engineering Science, University of Oxford (huidong. liangg xiaowen dong)8eng, ox ac. uk, xingchenw@@gogle..co
Abstract
We address the problem of optimizing over functions defined on node subsets in graph. The optimization of such functions is often a non-trivial task given their combinatorial, black-box and expensive-to-evalur 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 limita- tions, we utilize Bayesian Optimization (BO), a sample-efficient black-box solver, and propose novel framework for combinatorial optimization 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. The experiment code can be found at iiigggihb.oooi
nature. Although various
graphs. More
Introduction
In the analysis and optimization of transportation, social, and epidemiological networks, one is often interested in finding a node subset that leads to the maximization of a utility. For example, incentivizing an initial set of users in a social network such that it leads the maximum adoption of certain products; protecting a set of key individuals in an epidemiological contact network such that maximally slows down the transmission of disease; identifying the most vulnerable junctions in power grid or road network such that interventions can be made to improve the resilience of these infrastructure networks.
The scenarios described above can be mathematically formulated as optimizing over a utility function defined node subsets in graph, which is non-trivial task for several reasons. First, most conventional optimization algorithms are designed for continuous space and are hence not directly applicable functions defined discrete domains such graphs. Second, optimizing over k-node subset leads to a large search space even for moderate graphs, which are not even fully observable in certain scenarios (e.g. offline social networks). Finally, the objective functions are usually black-box and expensive to evaluate in many applications, such as the outcome of diffusion process on the network (56] or the output of graph neural network [50], making sample-efficient queries necessary requirement.
Assuming the graph structure is fully available, the optimization task described above shares similari- ties with those encountered in the literature on network-based diffusion. In that literature, greedy
Now at Google.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

have been widely used to select a subset of nodes that maximizes utility func- tion, for example in the context of influence maximization [8] or source identification [25]. However, as the underlying functions often require calculating expectations over large number of simulations (e.g. the expected number of eventual infections from an epidemic process), such algorithms often become extremely time-consuming as the evaluation time for each diffusion process increases [2]. To relieve the inefficiency in computation, proxy-based methods, such as PageRank [6], generalized random walks [0)) and DomiRank [17], are often used in practice to rank the importance of nodes. However, such methods completely ignore the underlying function and require full knowledge of the graph structure beforehand. Finally, most methods mentioned above sask-specific, and the one designed for a specific diffusion process usually does not generalize well to another.
algorithms [28 32
In this paper, we consider the challenging optimization setting for black-box functions on node subsets, where the underlying graph structure is not fully observable and can only be incrementally revealed by queries on the fly. To facilitate this setting, we propose novel strategy to conduct the search in combinatorial graph space (termed "comboograph") in which each node corresponds to a k-node subset in the original (unknown) graph. The original problem is thus turned into optimization over a function on the combo-graph, where each node value is the utility of the corresponding subset. Traditional graph-traversing methods, such breadth-first search (BFS) or depth-first search (DFS), may not work well in this case due to the exceedingly large search space and their lack of capability to exploit the behavior of the underlying function. Bayesian optimization (BO), a sample- -ffice-fffiiennt black-box. solver for optimizing expensive functions via surrogate modeling of its behavior, presents an appealing alternative.
Contributions. We propose a novel Bayesian optimization framework for optimizing black-box functions defined on node subsets in generic and potentially unknown graph. Our main contributions are as follows. To the best of our knowledge, this is the first time BO has been applied to such challenging optimization setting. Our framework consists of constructing the aforementioned combo-graph, and traversing this combo-graph by moving around a combo-subee -subgah sampled by recursive algorithm. Notably, the proposed framework is function-agnostic and applies to any expensive combinatorial optimization problem on graphs. We validate the proposed framework on various graphs with different underlying functions under both synthetic and real-world settings, and demonstrate its superiority over a number of baselines. We further analyze its behavior with detailed ablation studies. Overall, this work opens new paths of research for important optimization problems in network-base settings with real-world implications.
2 Preliminaries
is gradient-free optimization algorithm that aims find the global optimal point x of a back-box function f X' - IR over the search space X, which, in the case of maximization, can be written as x* = arg x f(x). To efficiently search for the optimum of expensive-to-evalaate functions, BO first builds a surrogate model based on existing observations to predict the function values and their uncertainties over the search space X. then utilizes an acquisition function to decide the next location for evaluation.
BO 38 20
Surrogate model. One of the most common surrogates used in BO literature 44 the Gaussian Processes model: f(x) ~ GP(m(z), k(z,,")). in which m(x) is the mean function (often set to a constant 0 vector) and k(x, x²) is a pre-specified covariance function that measures the similarity between data point pairs. With a training set D; = {æ1:1 y1:1} of t observations, the posterior distribution of (2++11 for new location It+1 can be analytically computed from the Gaussian conditioning rule, where the mean is given by u(xx+1 (D:) = k( X1=) KT.yL: with covariance ((x--1, 2/41 (Dt)= k(
k( X ) T k ((Xi,tt L:t, 2(41). Note that the computational
cost for j:t is at ((S)) which largely restricts the efficiency of GP when training on large datasets and therefore often requires local modeling approach.
A Acquisiionn function. Based on the predictive posterior distribution, an acquisition function will be applied to balance the exploration-exploiatiee trade-off via optimizing under uncertainty. For example, the Expected Improvement (37, 26), defined as (l,r(x") = [[[[(=') [**++)]] with [ax] max(a, 0) and _ arg max fxx)), measures the expected improvement based on the
current best query. Then, the next query location is chosen I++1 arg xxx) El (z'),

---

(t-1)
g
(t)
(t+1)
Context combo-subgraph 9: iter t, centered at last queried combo-node 8
Ge+1 centered at last queried
Initial combu-node Pi-1 from restart or query
combo-node B7
112)
(1.2)
(0.2)
(0.2)
Next combo-node to query B2
(2,3)
(24)
2.3
(2
(0.3)
Next
12,3)
(0.3)
52
combo-node
5)
query Pi+1
(0/4)
go2
computed from arg maa a<()) D
max a
(D)
Pess
(0.5)
unexplored structure
explored structure
queried combo-node
surrogate prediction
next query
Figure 1: Demonstration of how the proposed framework traverses the combinatorial graph G<k> introduced in with
with an exemplar original graph & of 6 nodes and a subset size of k 2. At iteration t, we first construct a local combo-subgraph G. [V,, & of size Q=6 using Algorithm ($3.)).
which is centred at combo-node it_ from last iteration t-1 or initialization. Next, a GP surrogate
fitted on Ge with queried combo-node -odes inside G. being the training set. The next query location is then selected as the combo-node that maximizes the acquisition function 6 arg max (()).
queried values f(ūī)= > f(6 the next combo-subgraph G.+11 will be re-sampled at a new center if. or otherwise remain the same. Finally, we repeat the previous process to obtain a new query location for the next iteration t+1, and the search continues until stopping criteria are triggered.
and result (IZ+1, 1, M++1 } will be appended to visited set D,. The algorithm will repeat these steps until the stopping criteria triggered at a certain iteration T, and report 2. arg max fx;) as the final result.
BO of Functions over Node Subsets in Graphs
Settings and challenges. Following the notations in we formally introduce the proposed Bayesian optimization framework for black-box functions over node subsets in graphs, termed GraphComBO. The goal of the problem is to find the global optimal k-node subset S* of black-box function f(S) over the search space of all possible k-node subsets (%) generic graph G (V, which, in the case of maximization, can be expressed as S" = arg me) f(S). Under noisy
settings, may only observe y f(x) with N(0, o??) being the noise term. For simplicity, we focus on undirected and unweighted graphs where the adjacency matrix A is symmetric and contains binary elements. As is often expensive to evaluate in practice, we wish to optimize the objective a query-efficient manner within a limited number of evaluations T, and report the best configuration among them the final solution: St arg max f(S.).
Despite BO's appeals in optimizing such functions, we observe the following challenges when designing effective algorithms for combinatorial problems on graphs:
1. Structural combinatorial space. Unlike classical combinatorial optimization in the discrete space, the combination of nodes (a node subset) inherits structural information from the underly- ing graph, which needs to be properly encoded into the combinatorial search space. In addition, an appropriate similarity measure between node-subset pairs is also required to capture such inherent structural information when building the surrogate model.
2. Imperfect knowledge of graph structures. As the complete structure of real-world graphs may be expensive or even impossible to acquire (e.g. a gradually evolving social network), any prospectus optimization algorithm needs handle the situation where the graph structure is only revealed incrementally.
3. Local approach while combining distant nodes. As the massive size (I2)) of the combinatorial space often makes global optimization unattainable, effective local modeling approach is
3

---

needed to efficiently traverse the graph. However, as the optimal subset usually consists of nodes that are far away from each other (e.g., the optimal locations of hospitals in city network), is critical to maintain the flexibility of selecting distant nodes when considering a local context.
In the following sections, we will discuss how the proposed GraphComBO addresses these challenges, where an overview of the framework can be found in Figure I
3.1 The Combinatorial Graph for Node Subsets
Inspired by the graph Cartesian product that projects multiple "subgraphs" into combinatorial graph, we introduce a combinatorial graph (denoted as combo-graph) tailored for node subsets on a single generic graph with an intuitive example demonstrated in Figure _
Definition 3.1. The combinatorial operation for k-node subsets in an underlying graph g (V,E) given by:
is
gaks> = 1
(1)
which leads to a combo-graph Gak> = (D,E) of size | - - with each combo-node
& (uf of22) :...... (()) & being a k-node subset from the underlying graph 9 without re-
placement. The combo-edges & in the combo-graph are defined in the following way: assume i (u()), u03)) (,),,.,,( (()) and 02 (v22) 22 ... ((()) are two arbitrary combo-nodes in the combo-
(1) (2)
graph gak>, then (61, i2) E & iff j. such that V of j. vi 22 and (vl ,02
(1)) E
Intuitively, this means that in the combo-graph, two combo-nodes are adjacent if and only if they have exactly 1 element (i.e. node from the original graph) in difference and the two different elements are neighbors in the original graph. Note that as A shrinks to 1, the combo- graph reduces to the underlying graph.
Space of node subcets
(.2
1,3
Original space
0.4
center
hop
2 hop
3rd hop
Nevertheless, as the combo-graphe size (12) is often too large in practice, building the surro- gate and making predictions at global scale is usually unrealistic. A sensible alternative would be adopting a commonly used local modeling approach [19] and then gradually moving around the "winndww" guided by the surrogate predictions. Unlike classical continuous space, constructing local regions on the combo-grayy -rapp is not straightforward. Next, we will discuss two properties of the proposed combo- combo-graph, which enable us practically employ local modeling by sampling subgraphs for tractable optimization. Reads are also referred to for proofs of the following lemmas.
Figure 2: Illustration of combinatorial graph
G constructed by the recursive combo-
subgraph sampling (Algorithm [.
Lemma 3.2. In the proposed gombo-graph, at most elements in the subset will be changed between any two combo-noder that are E-hop away.
This implies that when considering an ε-hop ego-subgraph centered at an arbitrary combo-node é on the combo-graph, we are effectively exploring the f-hop neighbors of elements graph. Since such operation requires no prior knowledge of the other part of the original graph, we are then able gradually reveal its structure by moving around the focal combo-node, and hence handling the situation of optimizing over node subsets on an incomplete or even unknown graph.
in the original
Lemma 3.3. The degree of combo-node é; increases linearly with k and is maximized by the subset of nodes with top ie degrees: deg(
Therefore, the size of the above ggo-subgraph only needs to increase linearly with l to cover the first hop combo-neighhors These two properties together make the construction of local combo- combo-subgrann subgraphs feasible, and we introduce a sampling algorithm in the next section that recursively finds combo-nodes and combo-edges for a combo-subgraph (denoted 9) given a focal combo-node.
Recursive combo-subgraph sampling. As illustrated in Algorithm aad Figure 2 our goal is to construct ego-subgraph G of size Q from the underlying graph G. centered at given combo-node

---

8* with maximum hop mmax. The algorithm initializes 9 = (V.E} with only 8 and then loop through neighbors of each element node v 0*. If neighbor (1(1)) of e is not in 6* (i.e. ensuring no repetition in the subset), new comb if will be created by substituting N2(v) with v in 6*, and a combo-edge will be accordingly created by connecting 1' to 0* As a result, after finding the combo-neis nombo-neighbors neighbors of i at hop e 1. 9 becomes star-network at center 8*. We will then repeat the above procedures (i.e. star-sampling) for every newly found combo-node to find their combo-neighbors at hop E + 1 (which meanwhile also finds the edges among combo-nodes within the previous hop f), until the subgraph size limit Q or the maximum hop max is reached.
By constructing the combo-grapp -rrboo and sampling subgraphs from it, we can efficiently traverse the combinatorial space by progressively mov- ing around the combo-subgraph center while preserving diversified combinations of distant nodes under a local modeling approach, which will be discussed in the following section.
Algorithm 1 Recursive combo-subgraph sampling
Input: Original (unknown) graph G; The focal combo-node ;*; Combo-subgraph size Q: Max neighbor hop Laax.
Initialize: An combo-subgraph 9 = (V, with
V {6*} E Ø; Starting hop l < 1; Set of
newly found combo-nodes Vnew {0*)-
3.2 Graph Gaussian Processes Surrogate
Define: Recursive Saeaursiii_Salpe((ee 9, Vnews Q,0)
1: for in Vnew do
After constructing the combo-subgraph, we can build surrogate model for the expensive under-
2:
for v in do
lying function on this local region with graph Gaussian Processes (GP). Specifically, we consider the normalized graph Laplacian L: --I- D-- 1 AD 11/2 for a combo-subgraph subgraph G. where Á is the adjacency matrix and D is the degree matrix. Then, the eigendecomposi- tion of the graph Laplacian matrix is given by = UAUT, in which A = diag(A1. ... An) are the eigenvalues sorted in ascending order
3:
Reveal the neighbors (v)) of in G. for e' in in.(vv) n â parallelly do Generate new combo-node by CONCAT([V', A(D) and then create a combo-edge by connecting it to c. end for
4:
5:
6:
7:
Update ( in
8:
end for
9:
if [V] > Q o fmax then
10: Randomly drop the extra combo-nodes.
and U = [u.,.... un)] are their correspond- ing eigenvectors. Now let i,j E {1, n| be two indices of combo-nodes on G. the covari-
11: return The combo-subgraph 9 of size Q.
end if
13: end for
ance function (or kernel) 1e( 0; 02) between arbitrary combo-node pair 6g and 0g can be for- mulated in the form of regularization function r(Ap)) [46] defined on the eigenvalues (Ap)p-1:
Update Vnew - -iiinew - return Recursive Sampler(( SemplerrGG@ 9, Vnews Q,
k(0;, 02)
Σ (pp)
(2)
where up[i] and L.] are the i-th and j-th elements in the p-th cigenvector up and r(Ap) is some scalar-valued function for regularization. We refer readers Appendix $E for discussion collection of commonly used kernels on graphs under the form Equation
3.3 Bayesian Optimization on the Combo-graph
With the structural combinatorial space and techniques to sample and build surrogate models on the combo-subgraphs, we now introduce the proposed GraphComBO framework in detail. For simplicity, we consider maximization in the following paragraphs, where the overall structure can be found in
Figure I with key procedures summarized in Algorithm 2 and complexity discussed in Appendix C
Combo-subgraphs as trust regions. As discussed earlier, performing global modeling directly for combinatorial problems is usually impractical. Thus, inspired by the trust region method popularly used in continuous numerical optimization [8) reinforcement learning [3] and BO under other settings 11. 51), we take a local modeling approach on the combo-graph during the BO search. Starting with a random location (i.e. combo-node üp) reasonable guess from domain knowledge,
combo-subgraph Go will be constructed at center dg by Algorithm |
We will then move around
5

---

this combo- sombo-subgraph G. at each iteration t on the combo-gran by changing its focal combo-node guided by the surrogate model and acquisition function, which will be explained shortly.
In particular, we introduce a hyperparameter Q that caps the combo-subgraph size to control the computational cost for the surrogate gP. and then use the queried combo-node inside 9, as the training set D, fit the model (i.e. update the hyperparameters in its kernel). The acqui- sition function a a() is then applied on the rest of unvisited combo-nodes in Gr, and we select the combo-node é = arg ma a(θ) as the next location to query the underlying function. Here, any commonly used kernel and acquisi-
Algorithm 2 BO for node-subsets on graphs
Input: Original (unknown) graph G = (V, 8); un- derlying function f defined k- node subsets S (2)): combo-subgraph size Q: failures threshold failtol; # queries T. Objective: Find St = arg maxs;e(s.) S(S.). Initialize: Set initial training set Do - Ø and queried set Oo - Ø; Set restart sta- tus restart - True; Set counter of non- improvement tolerance F - O. Use initial start_locatie ún if applicable, and specify the restart_methor for restart.
tion function are compatible with our setting, and we adopt the popular diffusion kernel [40]
with Expected Improvement acquisition (26] in our experiments.
1: for / 1,,...... , do
2: if restart then
After querying the next location, we re-select the best-queried combo-node et in our training set Dr D.[ō] by choosing ,," arg m f()), and compare it to the previous best location ft-1 the best-queried value improves (i.e. f(o)) ((ūt_)) 1)), the combo-subgraph in the next iteration Ge+1 will be resampled at this new location ,, with Algorithm|] [
3: Re-initialize the starting location i using restart_metiee start_ loct_location; Query de and reset the training set Dj - (d): Ve); Set restart False.
and
4:
end if
5:
Sample combo-subgraph S. ( Ed} with | Q centered the best train- ing combo-node 0i=1 from D using Algorithm i $3.1
or otherwise re- mains the same as G.. The search algorithm then continues until a querying budget T' is reached, and we report the best-queried combo-node as
6:
Fit the GP surrogate defined in 3.2 on G. by maximum likelihood, with the queried combo-nodes inside Go being the training set (i.e. De = V. n (--1
the final result oz = arg max f(0).
Balancing exploration and exploitation. Similar to the continuous domain, the exploration-exploitation trade-off is also a fundamental concern when using BO on the proposed combo-graph, and we introduce two additional techniques strike a balance between these two matters.
7:
Optimize the acquisition function o; Select
6 = arg max a(t) from G. as the next query; Obtain the function value y 0z. Update query set O2 - O,-1 U (02, and training set D, < D. u (6.,y)); Select the best training combo-node of arg max (()).
8:
1. failtol that controls the tolerance of "fail- ures" by counting continuous non-improvemmet steps. Once reached, the algorithm will restart at a new location using restart restart_method. _eethod.
9: Update F - F 1 1
0 ; Set
restart < True if failtol = F or all combo-nodes in G, are queried.
10: end for
2. pestart_methor that either restarts at ran- dom combo-node, the hest-visited combo-node, or the initial starting location if specified.
11: return 0 arg max f(0).
In addition, the combo-subgraph size Q, which can be viewed as the "volume" of the trust region under graph setting, also controls the step size of exploration. These strategies together can cohesively assist GraphComBO in adapting to various tasks. For example, a small failtol will encourage exploration in the combinatorial space when restart restart_method methheh is set to random combo-node, which is useful when optimizing an underlying function with low graph signal smoothness [5]. By contrast, when increasing failtol and setting restart fostart_method __method to the best-queried combo-node, the algorithm will exploit more around the local optimal and is hence more suitable for smoother functions. K further provides an ablation study on these hyperparameters.
Impact of the underlying function / and the subset size k. It is natural to expect that the interaction between the underlying function f and graph structure, which relates to signal smoothness over the combo-graph, will exert a significant influence on the search performance. Specifically, the

---

BA elgen centrality; 4
BA cigen connality; 8
BA cigen centralit;; k 16
BA eigen centrality: k-
Regret
0.15
0.10
0.07
0.1
0.08
0.06
0.1-
0.06
100
300
200
300
200
300
100
<te
WS degnes centrillty; k
WS degrev centrality:
xcp1 degree centrality: k
Atr WS degreu centrality; k
2
Regret
2-
1.5
10-
100
200
300
100
200
300
100
200
300
10
100
200
300
SBM PageRank scores; k
SBM PageRank scores;
SBM PageRank scores; k= 16
SBM PageRRak scores; k 32
Regret
15-
2-
10-
100
300
200
300
100
200
300
10
100
Ackley function;
Grid Ackley function: K
Ackley function: km
Grid Ackley function; 32
3.25
3.25
Regret
3.0
3.00
3,00
25-
2.75
2.75
100
200
300
30
100
200
300
30
100
200
300
100
200
300
#Queries
&Queries
#Queries
#Queries
GraphCCoBBO
I-Rundam Walk
L-Local Scurch
Local Search
BPS
DES
Random
Figure Results for synthetic problems on BA, WS, SBM and 2D-Gric networks with A: [4, 8, 16, 32], where Regret indicates the difference between ground truth and the best query so far.
optimization is expected to be challenging either when f is less correlated to the graph structure even if the latter is informative (e.g. random noise on a BA network 44) as an extreme case), or when is correlated to the graph structure but the latter is non-informative (e.g. eigenvector centrality on a Bernoulli random graph [8] ). In the meantime, as the subset size k increases, exploration will become more expensive when using a combo- combo-subgraph of fixed size Q or fixed number of hops lmax- Recall that in Lemma 3.2 where we state that most l elements will be changed between two combo-nodes that are é-hops away, it implies that more queries are required to exhaust all possible modifications of the elements in the subset when its size h increases. Empirical findings from our experiments in $ further corroborate these hypotheses, where we also provide detailed discussions on model behavior
G and kernel performance under different levels of signal smoothness in $F
Relation to previous BO methods with graph settings. While BO has been combined with graph-related settings to find the optimal graph structures such in the literature of NAS (27 40 42
and graph adversarial attacks [50]. it remains largely under-explored for optimizing functions defined on the nodes node subsets in the graph. Although one recent work BayesOptG [52] considered such novel setups, it only considered functions defined on a single node, which can be viewed as a special case in our setting when & 1. The construction of the "combo-graph" in our approach shares similarity with the construction of the combinatorial graph in COMBO [40]; however, the problems being addressed there do not arise in natural graph setting, and we present a more detailed discussion of the related work in Appendix A together with an additional experiment for comparison in ş
Experiments
Setups. We conduct comprehensive experiments on four synthetic problems and five real-world tasks to validate our proposed framework, where readers are also referred to the appendix for discussions on: |B detailed experimental settings with task descriptions and visualizations; $ validation of common kernels on graphs under our settings; |G thorough analysis of GraphComBO's underlying behavior, and şK ablatioo studies on the -yper-parameters. We closely follow the standard
setups in BO literature 3 19 23). Specifically, query 300 times and repeat 20 times with different
7

---

Plattening the curve, 4
Flationing the curve: k
Flattening the curve: k 16
Plattening the curve: k=
Pop. infoc. time
0.45
0.45
0.46
0.48
0.500
0.44
11.44
0.46
0.475
100
200
300
100
200
300
10
100
200
300
10
1000
200
300
Paricut-acro tracing;
Patient-zero tracing: k=
Patient-zcre tracing:
Parient-2cro tracing;
0.5
Regret
0.50
0.50
0.4
0.4-
0.25
0.25
0.3
0.3
100
200
300
100
200
300
10
100
200
300
10
1000
2001
300
15 Network sctivated
Infloence maximisation; k =
Influence masimisation;
Influence maximisatinn:
16
Influence maximisation;
3.25
2.5
3.6
2.0
3,00
1.5
20-
2.75
3.4
1.5
200
100
180
100
[Queries
QQueries
AQueries
#Queries
GmohCCoBBO
I-Random Walk
L-Local Scarch
Local Scarch
BFS
DFS
Random
Figure 4: Results for flattening the curve, patient-zero tracing and influence maximization.
random seeds for each task, in which the mean and standard error of the cumulative optima are reported for all methods. For simplicity, we diffusion kernel [40] with automatic relevance determination and adopt Expected Improvement (26) as the acquisition function to investigate subset sizes of & [4, 8, 16, 32]. where also fix 4, 000 and failtol 30 across all experiments. In addition, we also initialize the algorithm with 10 queries using simple random walks when &: > 16.
Baselines. As the proposed framework is a first-ofitt-kknd BO method for optimizing expensive and black-box functions of node subsets generic graphs, we consider three graph-traversing algorithms that operate on the original graph: Random, k-Random Walk and k-Local Search; and three algorithms on the proposed combo-graph: BFS, DFS and Local Search the baseline methods, with their details described in Appendix $B Notably, the local search method, which randomly queries a neighbor of the best-queried combo-node each iteration, can be viewed BO method that "random" surrogate model, and hence serves as good indicator for GraphComBO's behavior.
Synthetic problems on random graphs. We first validate the proposed framework on four ubiq- uitous random graph types with commonly used analytical underlying functions. Concretely, consider Barabási-Albert (BA) 4 Watts-Strogatz (WS) [54). stochastic block model (SBM) [22) and 2D-grid networks, where their corresponding "base" underlying functions are eigenvector centrality, degree centrality, PageRank (6). and Ackley function []]. respectively. We then take the average over node values inside a subset obtain the final underlying function, which, given the analytical setting, enables us to compute the difference (Regret) between the queried-best value and ground truth. The search results are presented in Figure 3, where we also explained the problem settings detail in Appendix B..1 I and summarized the graph statistics in Table
Real-world optimization tasks. After validation under synthetic settings, we carry out five real- world experiments on epidemic contact networks, social networks, transportation networks, and molecule graphs, where their results are presented in Figure 4 and Figure 5 The statistics of the underlying functions and graphs are summarized in Table where the detailed setting for each scenario is explained and visualized in BB2 B.6 Specifically, we consider the following tasks:
Flattening the curve in epidemics ( B.2 We adopt the widely-used SIR simulations [29 on real-world contact network with goal of protecting k nodes in the network, such that the expected time of reaching 50% population infection will be maximally delayed.
Identifying patient-zero in communities (.B... We apply SIR on an SBM network to simulate disease contagion across multiple communities, where the goal is to identify individuals with the earliest infection time, given the complete transmission network not known a priori.
8

---

Rond resillence; k 4
Road resillence:; K-
Read resilience; k- 16
Rond resilience; k- 32
Network transiiivity
3.38
3.32
3.50
9.32
3.31
3.25
3:26
3.38-
3.30
3.24
30
100
200
300
30
100
200
300
30
100
200
300
30
100
200
300
GNN attack on melocules; k 2
GNN attack on molecules; =
CNN sttack on molecules; =
GNN atlack on molecules; k 16
Wassenttin dist.
0.15-
0.20-
0.10
0.15
0.25
0.10
10
30
100
10
30
100
10
50
100
10
30
100
#Queries
#Queries
*Queries
#Queries
GnybComBO
I-Random Walk
k-Local Scorch
Local Soarch
BFS
DFS
Rundom
Figure 5: Results for road resilience testing and GNN attacks on molecules with edge-masking.
Maximizing influence on social networks (sB4). We consider the influence maximization
problem on a social network [45] with independent cascading simulations (28). in which we aim to select the optimal & nodes as the seeds (i.e. source of influence) that maximize the expected number of final influenced individuals (represented as fraction of the network size).
Resilience testing on transportation networks (B5). The objective of this task is to identify the k most vulnerable roads (edges), such that their removal will lead to the maximal drop in certain utility function measuring the operation status (estimated by network transitivity).
Black-box attacks on graph neural networks (B.)). Considering a graph-level GNN pre-trained mreitriind for molecule classification [39 with a particular input graph, we conduct a challenging black box attack with no access to the model parameter but only a limited number of queries for its output. Our goal here is to mask & edges such that the output from the victim GNN (at softmax) will be maximally perturbed from the original output, as measured by the Wasserstein distance.
Discussion on results. We can observe that the proposed GraphComBO framework generally outperforms all the other baselines with a clear advantage on both synthetic and real-world tasks. is worth noting that such gain in performance seems to be diminishing as k increases and, in certain scenarios, BO also tends to perform similarly to local search. While these phenomena are generally consistent with our previous hypothesis in |3.3 we further provide the following explanations to attain a better understanding of the model's underlying behavior.
1. Given a combo-subgraph with a fixed size Q, we tend to capture structural information in a smaller neighborhood due to the increase of combo-note degrees. First, when & increases, the combo-node degree will increase linearly (as discussed in Lemma 3.3). Second, if the synthetic underlying function has strong positive correlation with node degree, such as eigenvector centrality, the degree of the center combo-node will increase as the search progresses. Both factors will lead to a smaller neighborhood around the focal node (in terms of shortest path distance) covered by the combo-subgraph, which in turn means more steps are required to explore beyond the current region, especially when the algorithm reaches local optimum.
2. As discussed in $3.3 underlying functions with low signal smoothness will negatively affect BO's performance, which partially explains the comparable results between BO and local search on WS and SBM where the graph structures are less informative, as well as on the molecule network where the underlying function involves graph neural network and is relatively non-smooth compared to other tasks. In addition, as the kernels used in GP ($3.2) come with an underlying assumption function smoothness, the surrogate model will capture less signal information when fitting a less-smooth function, thus making BO behave similarly to a random model (i.c. the local search). To better support this claim, we further conduct sensitivity analysis of the kernels to signal smoothness at different levels in Appendix
Further analysis on model behaviors. Readers are also referred to Appendix G for a more detailed behavior analysis that elaborates on the above explanations and Appendix k for a thor- ough ablation study on Q and failtol. In addition, Appendix H provides comparison with
9

---

COMBO 40 on small-scale networks, Appendix tests our framework on large social network OGB-arXiv with V 1.7 10,, and finally Appendix discusses the framework's performance under noisy setting where observations are corrupted at different noise levels.
5 Conclusion and Future Works
In this work, we introduce a novel Bayesian optimization framework to optimize black-boxed functions defined node subsets in a generie and potentially unknown graph. By constructing tailored combinatorial graph and sampling subgraphs progressively with a recursive algorithm, we able traverse the combinatorial space and optimize the objective function using BO in sample- efficient manner. Results on both synthetic and real-world experiments validate the effectiveness of the proposed framework, and we use detailed analysis to study its underlying behavior.
On the other hand, we have also identified the following limitations during our experiments, which can be explored as future directions for this line of work.
As discussed in the paper, the performance of BO gradually deteriorates when the subset size k increases. In this sense, some modifications are expected to better control the combinatorial explosion while preserving useful information from the underlying graph structure.
The proposed framework adopts a local modeling approach inspired by the trust region method to control the computational cost. However, we expect some improvement in BO's performance if we inject some global information (if available) into surrogate modeling, such using some self-supervised method with a graph neural network to replace the Laplacian embedding.
The current algorithm adopts fixed strategy for hyperparameters like subgraph size Q and maximum hop max.. where we believe the optimization would benefit from a more flexible design such as a self-adaptive Q and fmax as the search continues.
In all experiments, we assume no prior knowledge of the problem and adopt random initializa- tion method before the search. However, it is also an important direction to explore when good starting location or certain characteristics of the function are available from domain knowledge.
We believe the proposed combo-graph would bring new insights to a broader community machine learning research graphs. While there are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
Acknowledgment
H.L. is funded by the ESRC Grand Union Doctoral Training Partnership and the Oxford-Man Institute of Quantitative Finance. X.D. acknowledges support from the EPSRC (EP/T023333/I). The authors thank members of the Machine Learning Research Group and Oxford-Mar Institute of Quantitative Finance for discussing initial ideas and experiments.
References
[1] Ackley, D. A connectionist machine for genetic hillelimbing, volume 28. Springer science & business media, 2012.
[2] Arora, A., Galhotra, S., and Ranu, S. Debunking the myths of influence maximization: An in-depth benchmarking study. In Proceedings of the 2017 ACM international conference management of data, pp. 651 661-666, 2017.
[3] Baptista, R. and Poloczek, M. Bayesian optimization of combinatorial structures. In Interna- tional Conference on Machine Learning, pp. 462 471. PMLR, 2018.
[4] Barabási, A.-L. and Albert, R. Emergence of scaling in random networks. science, 286(5439); 509-512, 1999.
[5] Boeing, G. Osmnx: New methods for acquiring, constructing, analyzing, and visualizing complex street networks. Computers, environment and urban systems, 65:126-139) 2017.
10

---

[6] Brin, S. and Page, L. The anatomy of a large-scale hypertextual web search engine. Computer networks and ISDN systems, 30(1-7):107-117, 1998.
[7] Chen, W. Lin, T., Tan, Z., Zhao, M., and Zhou, X. Robust influence maximization. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 795-804, 2016.
[8] Conn, A. R., Gould, N. I., and Toint, P. L. Trust region methods. SIAM, 2000.
[9] Cui, J., Tan, Q., Zhang, C., and Yang. B. novel framework of graph bayesian optimization and its applications to real-world network analysis. Expert Systems with Applications, 170: 114524, 2021.
[10] De Arruda, G. F. Barbieri, A. L., Rodríguez, P. M., Rodrigues, F. A., Moreno, Y., and da Fon- toura Costa, L. Role of centrality for the identification of influential spreaders in complex networks. Physical Review E, 90(3):032812, 2014.
[11] de Ocáriz Borde, H. S., Arroyo, A., Morales, I., Posner, I,, and Dong. X. Neural latent geometry search: Product manifold inference via gromov-hausdorf caauudooff-inoommmt bayesian optimization. Advances in Neural Information Processing Systems, 2023.
[12] Defferrard, M., Bresson, X., and Vandergheynst, Convolutional neural networks on graphs with fast localized spectral filtering. Advances in Neural Information Processing Systems, 29: 3844 3852, 2016.
[13] Deshwal, A. and Doppa, J. Combining latent space and structured kernels for bayesian optimization over combinatorial spaces. Advances neural information processing systems, 34:8185-8200, 2021.
[14] Deshwal, A., Belakaria. S., and Doppa, J.R. Mercer features for efficient combinatorial bayesian optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 7210-7218, 2021.
[15] Dong, X., Thanou, D., Frossard, P., and Vandergheynst, P. Learning laplacian matrix in smooth graph signal representations. IEEE Transactions on Signal Processing, 64(23):6160- (6126666660-613, 2016.
[16] Dong, X., Thanou, D., Toni, L., Bronstein, M., and Frossard, P. Graph signal processing for machine learning: A review and new perspectives. IEEE Signal processing magazine, 37(6); 117-127, 2020.
[17] Engsig, M., Tejedor, A., Moreno, Y., Foufoula- Georgiou, E., and Kasmi, Domirank centrality reveals structural fragility of complex networks via node dominance. Nature Communications, 15(1):56, 2024.
[18] ERDOS, P. On the evolution of random graphs. Publ. Math. Inst. Hung, Acad. Sci., 5:17-60, 1959.
[19] Eriksson, D., Pearce, M., Gardner, J., Turner, R. D., and Poloczek, M. Scalable global optimization via local bayesian optimization. Advances in neural information processing systems, 32, 2019.
[20] Garnett, R. Bayesian optimization. Cambridge University Press, 2023.
[21] Haklay, M. and Weber, P. Openstreetmap: User-generated street maps. IEEE Pervasive computing, 124):12-18, 2008.
[22] Holland, P. W., Laskey, K. B., and Leinhardt, S. Stochastic blockmodels: First steps. Social networks, 5(2):109-137, 1983.
[23] Hvarfner, C., Stoll, D., Souza, A., Lindauer, M., Hutter, F., and Nardi, L. Tbo: Augmenting acquisition functions with user beliefs for bayesian optimization. In Tenth International Conference of Learning Representations, ICLR 2022, 2022.

---

[24] Imani, M. and Ghoreishi, S. F. Graph-based bayesian optimization for large-scale objective- based experimental design. IEEE transactions on neural networks and learning systems, 33 (10):5913-5925, 2021.
[25] Jiang, J., Wen, S., Yu, S., Xiang, Y., and Zhou, W. Identifying propagation sources in networks: State-of-the-an and comparative studies. IEEE Communications Surveys & Tutorials, 19(1): 465 481, 2016.
[26] Jones, D. R., Schonlau, M., and Welch, J. Efficient global optimization of expensive black-box functions. Journal of Global optimization, 13:455-492, 1998.
[27] Kandasamy, K., Neiswanger, W., Schneider, J., Poczos, B., and Xing, E. P. Neural architecture search with bayesian optimisation and optimal transport. Advances in neural information processing systems, 31, 2018.
[28) Kempe, D., Kleinberg, J., and Tardos, É. Maximizing the spread of influence through social network. Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 137-146, 2003.
[29] Kermack, W. O. and McKendrick, A. G. A contribution to the mathematical theory epidemics. Proceedings of the royal society of london. Series A, Containing papers of a mathematical and physical character, 115(772):700-221, 1927.
[30] Kingma, D. P. and Ba. J. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2014.
[31] Korovina, K., Xu, S., Kandasamy, K., Neiswanger, W., Poczos, B., Schneider, J., and Xing, E. Chembo: Bayesian optimization of small organic molecules with synthesizable recommen- dations. In International Conference on Artificial Intelligence and Statistics, pp. 3393-3403. PMLR, 2020.
[32] Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., VanBriesen, J., and Glance, N. Cost- effective outbreak detection in networks. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 420-4240999 2007.
[33] Li, Y., Fan, J., Wang, Y., and Tan, K.-L. Influence maximization on social graphs: A survey. IEEE Transactions on Knowledge and Data Engineering, 30(10)):852-1177 2018.
[34] Liu, W. and Song, Z. Review of studies on the resilience of urban critical infrastructure networks. Reliability Engineering System Safety, 193:106617, 2020.
[35] Maier, B. F. and Brockmann, D. Effective containment explains subexponential growth in recent confirmed covid-19 19 cases in china. Science, 368(6492):742-746, 2020.
[36] McKay, R. A. Patient Zero and the Making of the AIDS Epidemic. University of Chicago Press, 2017.
[37] Mockus, J. The application of bayesian methods for seeking the extremum. Towards global optimization, 2:117, 1998.
[38] Mockus, J. and Mockus, J. The Bayesian approach to local optimization. Springer, 1989.
[39] Morris, C., Kriege, N. M., Bause, F., Kersting, K., Mutzel, P., and Neumann, M. Tudataset: collection of benchmark datasets for learning with graphs. arXiv preprint arXiv:2007.086633 2020.
[40] Oh, C., Tomezak, J., Gavves, E., and Welling, M. Combinatorial bayesian optimization using the graph cartesian product. Advances Neural Information Processing Systems, 32, 2019.
[41] Ru, B., Alvi, A., Nguyen, V., Osborne, M. A., and Roberts, S. Baaesiaa optimisation over multiple continuous and categorical inputs. In International Conference on Machine Learning, pp. PMLR, 2020.
12

---

[42] Ru, B., Wan, X., Dong, X., and Osborne, M. Interpretable neural architecture search via bayesian optimisation with weisfeiler-lehmait kernels. International Conference on Learning Representations, 2021.
[43] Schulman, J., Levine, S., Abbeel, P., Jordan, M., and Moritz, P. Trust region policy optimization. In International conference on machine learning, pp. 1889-1897. PMLR, 2015.
[44] Shahriari, B., Swersky, K., Wang. Z., Adams, R. P., and De Freitas, N. Taking the human out of the loop: A review of bayesian optimization. Proceedings of the IEEE, 104(1):148-1 175, 2015.
[45] Shchur, O., Mumme, M., Bojchevski, A., and Günnemann, S. Pitfalls of graph neural network evaluation. Relational Representation Learning Workshop NeurlPS, 2018.
[46] Smola, A. and Kondor, R. Kernels and regularization on graphs In Learning Theory and Kernel Machines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003, Washington, DC, USA, August 24-27, 2003. Proceedings, pp. 144-158. Springer, 2003.
[47] Stehlé, J., Voirin, N., Barrat, A., Cattuto, C.,, Isella, L., Pinton, J.-F., Quaggiotto, M., Van den Broeck, W., Régis, C., Lina, B., et al. High-resolution measurements of face-to-face contact patterns primary school. PloS one, 6(8):c23176, 2011.
[48] Sun, J. and Tang, J. A survey of models and algorithms for social influence analysis. Social network data analytics, pp. 177-214, 2011.
[49] Sun, L., Dou, Y. Yang. C., Zhang, K., Wang, J., Philip. S. Y., He, L., and Li, Adversarial attack and defense on graph data: A survey. IEEE Transactions on Knowledge and Data Engineering. 2022.
[50] Wan, X., Kenlay, H., Ru, R., Blaas, A., Osbore,, M. A., and Dong, X. Adversarial attacks on graph classifiers via bayesian optimisation. Advances in Neural Information Processing Systems, 34:6983-6996, 2021.
[51] Wan, X., Nguyen, V., Ha, H., Ru, B., Lu, C., and Osborne, M. A. Think global and act local: Bayesian optimisation over high-dimensional categorical and mixed search spaces. In International Conference on Machine Learning, pp. 10663-10674. PMLR, 2021.
[52] Wan, X., Osselin, P., Kenlay, H., Ru, B., Osborne, M. A., and Dong. X. Bayesian optimisation of functions on graphs. Advances in Neural Information Processing Systems, 2023.
[53] Wang, X., Jin, Y., Schmitt, S., and Olhofer, M. Recent advances in bayesian optimization. ACM Computing Surveys, 55(13s) 13):: 2023.
[54] Watts, D. J. and Strogatz, S. H. Collective dynamics of 'small-world' networks. nature, 393 (6684):440-44) 442, 1998.
[55] Xu, K., Hu, W., Leskovec, J., and Jegelka, How powerful are graph neural networks? In International Conference Learning Representations, 2019.
[56] Zhang, Z.-K., Liu, C., Zhan, X.-X., Lu, X., Zhang, C.-X,, and Zhang, Y.-.. Dynamics of information diffusion and its applications on complex networks. Physics Reports, 651:1-34, 2016.
13

---

A Related Work
BO for combinatorial optimization. Bayesian optimization has been widely applied to solving combinatorial problems with black-box and expensive-to-evalue underlying functions [44 53 Notably, BOCS 3 handles the combinatorial explosion of the discrete search space by utilizing an approximate optimizer for the acquisition function, which addresses the limited scalability of common acquisition functions to large combinatorial domains; CoCaBo 4T further tackles the setting of mixed search space with multiple categorical variables by introducing a GP kernel to capture the interaction between continuous and categorical inputs; and LADDER [3] takes latent variable approach that first encodes the problem into a latent space via unsupervised learning and then adopts a structure-couple kernel, which integrates both decoded structures and the latent representation for better surrogate modeling. While BO has provided sample-efficies way for the above combinatorial optimization problems, its extension to settings with graph structures, especially when the search space itself is generic graph, still remains largely under-explored and will be discussed in the following section.
BO with graphs. Despite several works in the literature combining BO with graph settings, the majority of them focus on optimization over graph inputs (i.e. each configuration itself is a graph, and the goal is optimize for graph structures). In particular, NASBOT [27 treats the neural network architecture as a graph structure and uses BO to perform neural architecture search, while WAS-BOWL [42] approaches the same problem from different perspective by using Weisfeiler- Lehman kernels with BO. Other examples include using BO for molecular graph designs [31], graph adversarial attack (50), and a general framework for optimizing functions on graph structures [9] These works, however, are under a different setup compared to our current work, which aims to optimize functions defined on node subsets in a single generic and potentially unknown graph. Moreover, the above works typically seek for a global vector- eenttor-mbedding of the graph configuration, after which standard kernels will be applied to measure their similarity the Euclidean space.
On the other hand, BayesOptG 52
proposes a framework that employs BO to optimize functions defined on single node on graphs, where the search space is generic graph and the configurations are nodes on the graph. The similarity between two configurations is then measured between node pairs with kernels on graphs capturing structural information. As mentioned earlier, our paper is generalization of this previous work by considering a combinatorial setting, in which BayesUptG can be viewed special case under our framework when the number of nodes in the subset is k 1.
Lastly, another relevant line of works from the literature is COMBO 44) and its variants 24 where the underlying function is defined on a Cartesian product graph computed from i small graphs In particular, each node on this combinatorial graph represents a combination of & elements from the k graphs, after which kernels on graphs the combinatorial space. Nevertheless, the combinatorial graph introduced in our work differentiates substantially from that in COMBO, and we emphasize the differences in the following.
leveraged to measure the similarity between nodes in
1. From the problem setting, COMBO is designed for k-node combinations from k distinct graphs (G:) (i.e. one node from each graph, which corresponds to one variable in the combinatorial optimization). The structure of these graphs and the resulting combinatorial graph is therefore pre-defined and fully available. In contrast, our work is concerned with the combination of k nodes (a k-node subset) from a single and generic graph whose structure (and hence the structure of our combo-graph) is potentially unknown priori.
2. The resulting search space for COMBO is of dimension I N₂ with N; corresponding to the size of ith graph G, whereas in our work, the combinatorial space has dimension (X) with N being the size of G. Note that in COMBO, even if we have k identical graphs and naively calculate their Cartesian product, the resulting space N still not the same as our case. For instance, (u, b) and (b, a) are two distinct sets in COMBO, but they should be considered as one single set in our scenario. Besides, sets with duplicated elements (c.g.. (a, a) or (a, a, b)) are valid in COMBO but meaningless in our setting, which will introduce redundant computational costs.
3. One of the main contributions of COMBO is that the eigendecomposition of the large combinatorial graph can be performed on the k smaller graphs with Kronecker product operation. Nevertheless, it is limited to small k and N, as the memory is simply not large enough to fit in an eigenbasis of size (II.-- 22 even with moderate choices of k and N
14

---

B Experimental Details
Experimental setups. This section provides the details of our synthetic and real-world experimental settings, where we summarize the statistics of the underlying graphs and functions in Table I and then visualize them Figure for synthetic problems and Figure for real-world problems.
Table 1: Summary statistics of the underlying graphs used in our experiments.
Type
Underlying Function
Search Space
Underlying Graph
Nodes
Edges
Avg. Eigenvector centrality
Node subsets
BA (m 5)
10k
50k-
Avg. Degree centrality
Node subsets
WS (A = 10, 0.1)
1k
5k
Synthetic
Avg. PageRank scores
Node subsets
SBM (# clusters = 4)
1k
7k
Avg. Ackley function
Node subsets
2D-GRID
5k
10k
Population infection time
Node subsets
Proximity contact network
223
6k
Individual infection time
Node subsets
SBM (# clusters - 4)
1k:
7k
Real-world
Expected # nodes influenced
Node subsets
Coauthor network (CS)
18k
163k
Network transitivity
Edge subsets
Manhattan road networks
5k
8k
Change of GNN predictions
Edge subsets
Molecule graphs (ENZYMES)
37
84
We closely follow the standard setups in BO literature [3 19 23 and investigate subset sizes of k = [4. 8, 16, 32]. where we use Q = 4000, failtol = 30 and set restart_ ae to the best- queried combo-node for all experiments. Specifically. different random seeds for each task, in which the mean and standard error of the cumulative optima reported for all methods. For simplicity, we use diffusion kernel [40] with automatic relevance determination and adopt Expected Improvement (26) as the acquisition function.
query 300 times and repeat 20 times with
Similar to standard BO setups, we initialize our algorithm with 10 queries by simple random walks on the original graph when > 16, except for the influence maximization experiment where we use 30 initial queries at k 32 since the underlying graph is relatively large with |V] x 18k. In addition, we also use simple random initialization of 30 queries for Ackley on 2D-grid and road resilience testing experiments; and 10 queries for GNN attack on molecules, since their underlying graphs contain relatively weak structural information, which are not suitable for graph-related initialization methods such random walk. After evaluating the initial query locations, select the best query as the starting point for all baselines to ensure a fair comparison.
Hardware and running time. All the experiments are conducted on a computing cluster of 96 Intel-Xeon .0CHz CPU cores with 250 GB working memory. The running times for synthetic problems are typically under hour with parallel computing. For real-world problems, except for the simulation-basee based experiments that take around 12 hours due to the evaluation of large numbers of simulations, the rest experiments will normally be finished within hour with parallel computing.
Baselines.
We consider the following baselines in our experiments.
Random Search which randomly samples & nodes from the original graph at each iteration and performs well compared to other graph-based methods if the underlying function less smooth on the combinatorial graph or less correlated with the original graph structure.
k- R-Random Walk which maintains k independent random walks on the original graph that forms subset of & nodes each step, featuring fast-exploration characteristic from the starting nodes, and works particularly well for exploration- hhavy tasks.
k-Local Search takes similar approach with the k- k-Random Walk baseline on the original graph. However, will only proceed to the next neighbors if the current k-node subset a better query compared to the previous ones, otherwise, it will hold at the same nodes and re-execute the random walk until a better location found.
BFS and DFS which explore function values on graphs by starting with an initial node and then traveling the graph according to depth or breadth. Specifically, BFS exploits all nodes at the current depth before moving to the next depth, while DFS explores nodes as far as possible along each branch before backtracking, Both methods operate on the -mabo..raph.
15

---

Local Search which also travels on the the proposed cumbo-graphe by randomly selecting node from the neighbors of the best-visited node each iteration. If all neighbors of the best node have been queried, the algorithm will then restart from new a random location. Notably, this method can also viewed as a BO using random surrogate with no acquisition function and hence serves as good indicator for BO's behavior.
B.1 Synthetic Experiments
In this section, we introduce the random graphs and synthetic functions used in our synthetic experiments, where a visualization can be found in Figure
BA: Eigen-centrality
WS: Degroe-centralliy
SBM: PageRank
2D-Grid: Ackley
Figure 6: Visualization of random graphs and underlying functions used our synthetic experiments. Specifically, node color represents eigenvector centrality BA network, degree centrality on WS network, PageRtank on SBM network, and Ackley function on 2D-Grid. Note that under the synthetic settings, take the average over the k elements within node subset the underlying function.
Random graphs used in experiments. We consider the Barahási-Albert (BA) 4 network, Watts- Strogatz (WS) [54] network, stochastic block model (SBM) [22]. and 2D-grid as the underlying graphs in our synthetic experiments, which are explained in the following part.
Garabási-Alberr network is constructed using preferential attachment mechanism. Specif- ically, we start with my initial nodes and then gradually add new nodes one at a time, where each new node v; is connected to existing nodes with probability P(e:) proportional the number of links that the existing nodes already have, which can be mathematically expressed as:
P(k.)
ΣjKy'
where k; is the degree of node v; and the sum all pre-existing nodes.
Watts-Strogan network explains the "small-world" phenomena in variety of networks by interpolating between regular lattice and a random graph. In particular, the model first starts with regular ring lattice of N nodes where each node is connected to K nearest neighbors (i.c. N K//2 2 total edges), then rewires K/2 edges for each node with probability p E [0, 1] to random node in the network while avoiding self-loops and duplicate edges.
Stochastic Block Model divides N nodes into K communities where each community has predetermined size N.. Then, the probability of an edge between nodes in cluster and is defined by matrix P of size K x K, where Pi, represents the probability of an edge between nodes in cluster and cluster j. The adjacency matrix A of the network then generated from P such that entry Age for an arbitrary node-pair u and v is Bernoulli random variable:
Au Bernoulli( Sacilii(Peecc Pr.c.)s
where Cu and e, are the cluster memberships of nodes and v, respectively. In our experiment, for simplicity, we consider an SBM of 1 nodes with K clusters in equal size, and fix the inter-cluster probability Pi.. x 10-2 and intra-cluster probability Pout 10-3
Synthetic underlying functions used experiments. centrality, PageRank scores, and Ackley function the (base) underlying function the aforemen- tioned random graphs. Note that we first use these base functions to assign a scalar value to each node in the graph, and then take the average within the subset the final underlying function. Such
consider eigenvector centrality, degree
16

---

Proximity-come contact network
Couuhhor network (CS)
Manhattan road network
ENZYMES-O from TUDataset
Figure 7: Visualization of the real-world networks used in experiments.
synthetic setup will enable us track the difference between our current best query and the ground truth, which is denoted as Regret (to minimize) when we present the results.
Eigenvector centrality is measure of the influence of particular node in the network, which defined as the solution x to the following equation:
Ax Xx,
where is the largest eigenvalue of the adjacency matrix A. Note that the solution x is also the cigenvector corresponding to X, and hence the name eigenvector centrality.
Degree centrality measures the number of links incident particular node us which, for an undirected network of N nodes, can be expressed as:
deg(v:) N
DC(#;)
where deg(e; is the degree of node e;. The underlying intuition is normalize the degree of each node by the maximum possible degree
the network.
PageRank variant of eigenvector centrality originally developed by Google [6] rank web pages according to their "importance" scores. It incorporates random walks with a damping factor and can be mathematically formulated in the following form:
1- PR(v.) = N
PR(u,)
Σ
+
dog (1y)
ByEN((m)
where is the damping factor (typically set to 0.85), N is the total number of nodes, (N;;) denotes the in-neighbors of node v; and deg (u,) is the out-degree of node Vy.
Ackley function is non-convex function with multiple local optima and has been widely used for testing optimization algorithms, which can be expressed in the following 2-D form:
f(z, y) -0 exp
exp( 0.5(cos 2 + cos 2my)) + 20 exp(1).
Additionally, random Gaussian noise 0.5 is added to the original function alter the smoothness property of the graph signal defined over the 2D-grid:
Mz, v) [(x, v) +e, with N(
Note that as the underlying graph (2D-grid) in this experiment contains little structural in- formation compared to other graphs such as BA and WS, instead of using the random walk initialization, we adopt simple random initialization method of 30 queries before searching and use the best query as the starting location for all methods.
B.2 Flattening the curve in Epidemics
In this experiment, our goal to protect an optimal subset nodes (individuals) in a contact network to maximally slow down an epidemic process simulated by a diffusion model SIR (29]. The contact network [7 used this experiment is collected by proximity sensors from a primary school in France, which contains 236 nodes and 5, 899 edges.
17

---

The Suspicious, Infected, Recovered simulation model. In the SIR model based on a network {V,E), each node has three statuses: Suspicious, Infected and Recovered. Starting with a fraction of initial infectious nodes in the population, at time step / {I,..., 7). each infected node has probability to infect another node if they are neighbors, and meanwhile has probability to transit to Recovered status. Once node is at Recovered status, it can not be infected again (e.g. quarantined, immune, or vaccinated). More formally, let X E {1, S, Rt denote the node status (Infected, Susceptible, Recovered) and Sr,t,S5, SR, denote the set of nodes in each category at time f, the model can be mathematically formulated as:
P P[x,041 = R] =Y
VE S1,8
(3)
P Xo,tt+1 = 1--
-1--) P Xo,++1 1] 1- (1 (0) (1 3)I P [x,,+11 5]= (1 (1- (1 B) (w)
Yo E Sg,
(4)
VU SR.,, IP [x.,t+ = R| =
(5)
where [0, 1] is parameter representing a probability of spontaneous infection from unknown factors [52]. Since the above model implies a random simulation process, a large number of Monte
Carlo samples is typically required when estimating the expectation of certain functions based on SIR, which is often expensive to evaluate and optimize.
Flattening the curve with SIR. As healthcare resource is often limited (e.g. hospitals, vaccines, quarantine centers), one usually interested in slowing down the transmission speed of the epidemic process by protecting the most "important" individuals, which prevents the public health system from breaking down due the sudden shortage of its capacity BS). We demonstrate this idea with SIR in the above contact network with N 100 simulations in Figure in which each run has an initial fraction of p 0.1 population infected, an infection rate of 10-3 a recovery rate of 10-2, and no spontaneous infection 0. Note that the same settings have been used in the main experiments.
(+) Randomly protect 20 codes
(b) MC Samples for (a)
(c) 200
Nodes found by GraphiComBO
(d) MC Samples for (c)
200
Sus,
Individuals
fnf.
20
8 Indivviduals
150
D 622.7
Counts
Ind.
Counts
10
100-
10
0
100
200
300
75
100
0
100
200
300
10
66
80
Time
Samples of time C
Time
Samples time
Figure 8: Demonstration of SIR and its simulations the real-world proximity contact network.
To protect nodes from infection, we set the chosen k-node subset to the Recovered status at the beginning of each simulation. then record the time t* that 50% population infected. After obtaining the results from N = 100 simulations, we record the mean infection time E[t"] as our underlying function, which we aim to maximize (i.e. delay the time when reaching paof-population infection). From Figure g we can observe a clear surve-flattening effect when protecting 20 nodes selected by BO (plots & d) compared to randomly choosing 20 nodes (plots a & b) the network. Note that to make the surrogate fitting more numerically stable, we also map E [+ to the range [0, 1] by dividing a constant of the maximal number iteration T 120.
B.3 Tracing Patient-zero in the Community
In disease transmission analysis such as AIDS and COVID-19, one would be interested in identifying
the earliest individuals (patient-zero) infected the community [6] 52 Nevertheless, such process is often time-consuming since it requires interviewing patients to obtain their infection dates and then gradually revealing the transmission network by interviewing their close contacts (i.e., the graph
not known prior), illustrated in Figure 9
18

---

(tn)
(t1)
(t2) real neighbous
reval
niighbouss
explored nodes
amrently revealed neighbours
target node to query next
Figure 9: Demonstration of the patient-zero tracing setting, where the underlying contact network is not fully observed initially. To gradually reveal the graph structure, at each step t, we query l nodes (i.e. record the first times they are infected) and reveal their neighbors (e.g. interview the patients and obtain their contacts). The objective is to find the patients of the earliest infection time.
Individual infection time. In this task, we the aforementioned SIR model and SBM network simulate a disease contagion across multiple communities, where the goal is to identify the earliest individuals infected in the whole network. Specifically, a certain time step T during the epidemic (set to T = 100 in the experiment), for every node in Sy SR.T we denote as the time of infection for node and map into a scalar value f(v) E [0, 1] via the following transformation:
V V.EV. v.f(v) (1
0 (1-
if SS. if u ST, U SR.T
(6)
Then, we take the average within the k-node subset as the final underlying function this experiment, which is maximized when the subset corresponds to the earliest & nodes of infection.
Note that in this experiment only single SIR simulation is required, and we run 20 times with different random seeds to report the results. For reference, the parameters used in each run are: initial fraction of infected population p = 0.5%, infection rate recovery rate of 7 10-2 spontaneous infection rate of c = 0.5%, and simulation time step of T = 100.
B.4 Influence Maximization on Social Networks
The Influenc Maximization (IM) problem over social networks has been widely applied to marketing and recommendations [33, where the goal is to select the optimal nodes as the seeds (i.e. source of influence) that maximize the expected number of final influenced individuals, which is typically
estimated by Independent Cascading (IC) simulation [28] and its variants. this experiment, we
consider the vanilla IC simulations on an academic collaboration network (Coauthor CS (45) of 18, 333 nodes and 163, 788 edges, with detailed settings discussed in the following.
Random nodes
MC. Samples for
(c) Nodes found GraphComBo
(d) MC Samples for
750
Individunis
400-
4 Individuals
Counts
500-
Counts
20
11 Find 14583
Infucseod
Inclessodd
0-
0-
0
10
200
400
0
10
400
600
800
Time
Samples & Influenced
Timet
Samples of Influenced
Figure 10: Demonstration of Independent cascading with simulations the CS coauthor network.
Independent cascading. The IC model takes similar setup to the SIR model above, except that each node only takes one the two statuses: Activated and Inactivated. Starting with an initial subset of k activated nodes, at each time step & {1, "..,,,,,, the activated nodes will have one-shot probability of p to activate their neighbors. Once a node is activated, it will remain activated until the end of the process when there is expectation of functions based on IC also requires a large number Monte Carlo simulations, which hence computationally expensive in most cases.
node be activated. Likewise, calculating the
Influence maximization with IC. The task of IM select the optimal set of nodes as the seeds of influence, such that the expected number of activated nodes at the end of IC is maximized.
19

---

In our experiment, we set the activation rate to = 0.05 and used N = 1000 Monte Carlo samples to estimate the expected number of final influenced individuals. In particular, the underlying function that is, the fraction of activated nodes in the network. Figure 10
is set to be # #Attivated//1 demonstrates the simulation results from two different strategies of selecting k 20 initial seeds: random selection (plots & b) and GraphComBO (plots & d), and we can observe clear difference in their expected numbers of final activated nodes.
B.5 Road Resilience Testing on Transportation Networks
The resilience of an infrastructure network denotes its ability to maintain normal operations when facing certain disruptions [34]. and one is often interested in identifying and protecting the most important nodes or edges to avoid catastrophic failure. In this experiment, we investigate the resilience of Manhattan road networks in New York City using OSMnx [5), Python tool built on OpenStreetio [2I]. Figure 7
provides a visualization of the network, where each node denotes an
intersection and each edge represents a road (with network_typs _tppe set to "drive")
The objective here is to identify the most vulnerable roads, such that their removal will lead to the maximal drop in a certain utility function, which could be difficult to evaluate in practice if it involves simulations or real-world queries. For experimental purposes, we use network transitivity (global clustering coefficient) proxy estimation for this utility function (to minimize), which measures the global connectivity of the graph based on the number of triangles:
Transitivity(I) = #Triangles
#Triads
where Triad means two edges with shared vertex. Similar to the Ackley on 2D-grid experiment, as the underlying graph a grid-like road network, we utilize simple random initialization of 30 queries before searching and use the best query as the starting location for all baselines.
Line-graph for functions of edge subsets. Since the underlying function here is defined on edge (road) subsets, we will first change the original graph G into its line graph Güiee where each node on the line graph Gisee represents an edge in G, and two nodes on Gisne are adjacent if and only if their corresponding edges in G share common endpoint. Then, the line graph will be used as the underlying graph in our proposed framework. Note that this procedure is independent of the underlying function evaluation, which is still on the original graph with certain black-box processes.
B.6 Black-box Attacks on Graph Neural Networks
In this task, we conduct adversarial attacks on graph neural networks (GNN) under challenging black-box setting [49]. where the attacker has no access to model parameters but only a limited number of queries for the outputs. Considering GNN pre-trained for graph-level classification tasks, for particular target graph under attack, our goal is to mask lt edges on this input graph, such that the output from GNN (at softmax) will be maximally perturbed from the original output.
Perturbation via edge-masking, Concretely, we use GIN 555 as the victim GNN and pre-train it on the TUDataset ENZYMES [39] for small molecule classification, and measure the change in GNN prediction after perturbation by the Wasserstein distance, which can be formulated as follows:
S(S) Wi (i(9() ((((),)))
where S(S) is the underlying function defined on the k-edge subset S (to maximize). W, is the empirical Wasserstein-1 distance, I denotes the pre-trained GNN at softmax, and (G) is a perturbation on G by masking the k-edge subset S, which will lead to perturbed graph G',
For reference, the GIN model has 3 hidden layers with 64 hidden dimension and is trained for 200 epochs by Adam 30 with a learning rate of 10-3 The pre-trained model achieves 99.5% accuracy on the dataset, and we use the first graph (index=0) from the dataset the target graph under attack. Note that no training/testing split is needed here as we are conducting attacks on pre-trained GNN.
Since the underlying function is defined on edge subsets of small molecule graphs, we will use the above line graph operation again and only search for 100 queries, where simple random initialization is also adopted for 10 queries before searching.
20

---

C Algorithm Complexity
Overall, the computational complexity of the proposed method for optimizing function defined on nodes graph of size N mainly comes from (1) constructing a combo-subgraph of size Q and (2) fitting the surrogate model.
1. Suppose at recursion & E 31.2 we found Mr new combo-nodes (Ma = 1). We will first need kM dictionary lookup operations find the neighbors of nodes in the k-node subset for each M input combo-nodes, and then Mj concatenations to create Mr new combo-nodes. The recursion repeats until E k-- Mt e Q at & = L. which leads to total of k E Mr < kQ dictionary lookups at (I:)), plus around Q concatenations at ((Q) (the last recursion will
break before finish when we reach Q).
2. The computational cost consists of two parts: (a) the Graph Fourier Transformation (GFT) and (b) computing the predictive posterior in Gaussian Processes (GP) using the Gaussian conditioning rule.
(a) The GFT requires eigendecomposing the graph Laplacian matrix: L UAUT, which typically costs D(N5) for a graph of N nodes.
(b) To obtain the predictive posterior from a GP by Gaussian conditioning rules (explained in section line 105), we need to compute the inverse of the kernel matrix K1d for the observed & datapoints, which requires (tt)) Since <= N, the maximum complexity for this term also O(N)) for graph of N nodes.
However, since the surrogate model operates on a subgraph of size Q. we can limit the computational cost ((Q") and only need to re-construct the combo-subgrapp and re-compute its eigenbasis when the center changes (i.e. when finding a better query location). Note that the computational cost from (a) is at ((kk) which is insignificant compared to ((Q*) in practice. This also leads to efficient memory consumption where we only need to store a combo-subgraph of size Q with its cached eigenbasis (a Q Q matrix) during the search.
D Proofs of Lemmas in 33.1
In this section, we provide proofs for Lemma 3.2 and Lemma 3.3 in $3.1
Lemma 3.2. In the proposed combo- combo-graph,
graph, at most elements in the subset will be changed between any two combo-noded that are E-hop away.
of i elements as the center the proposed combinatorial graph ğ <>>>> According to Defini- tion 3.1 there will be strictly element in difference between two neighboring combo-nodes, which implies that the 1s ho- neighbors of û; will have one different element, the hopp neighbors will have one or two different element(s), the 3rd -hd-hop will have one, two, or three different element(s), and by induction, we can conclude that at hop-& there will be at most E elements in difference. n
Proof. Considering an arbitrary combo-node ú; = (v)
of an E-hop ego combo- combo-subgraph
Lemma 3.3. The degree of combo-node i, increases linearly with k and maximized by the subset of nodes with top k degrees: deg((:) = > (N G'
13
Proof. The degree deg( (z) of an arbitrary combo-node 6: (v. 04 ..... tion over i constant terms, where each term j {1,..., k} cquals the number of neighbors (((o(") of an element node vf that not inside the combination. As the maximum term is capped by | - which is the largest possible degree in the original graph of an arbitrary structure, we conclude that the combo-node degree will increase linearly with k.
1/ (k) is linear combina-
E Details of the Kernels on Graphs
Common choices of kernels on graphs. Following the discussion in $3.2 we analyze the per- formance of four kemelss on the combinatorial graph and their details are summarized in Table 2
21

---

Table 2: Summary of some common kernels on graphs.
Choice of Kemel
Regularization r(Ap)
Kernel Kn(V
Diffussio
exp(BnAp)
Eg- expl (3 u
Polynomial
2 B3G +E
-p (2,=1 2 +
Sum-of-Inverse
Σp-1 [E)-i (3,A3 e)- up
Polynomials
Specifically, we consider: Polynomial [12] that consists of polynomials of the eigenvalue order 7 E Z where the hyperparameters are the coefficient for each order; Sum-of-Inverse Polynomials [52] which is a variant of the polynomial kernel that takes scaled harmonic mean of different degrees; Diffusion [40] that penalizes the magnitude of the frequency (eigenvalue). and we also consider its implementation with the automatic relevance determination (ARD) strategy.
The polynomial and sum-of-inverse polynomials kernels have γ) hyperparameters | [So,... [,,,-..,39-11 -T] that are constrained to be non-negative to ensure a positive semi-defiiite covari- ance matrix. Meanwhile, we maintain the settings in the previous work [52) that set r) to be min di diameter). which strikes balance between expressiveness and regularisation. Whereas in the diffusion kernel, there are n hyperparameters B = [8,, .....,,n .B]] to be learned and are sometimes prone to over-fitiing when is large.
Poynonial
Sum of livers so yooiiaa
Difluiion
Difts with AAD
(a)
walsii prent buck
100
(b)
36-1
16-
26-3
36-2
Figure 11: Kernel validation on the combinatorial graph based on a BA network (n 20, m 2). To design the underlying function, we take the elements from the third eigenvector and average them over i = 3 nodes. Specifically, (a) shows the results on the testing data measured by Spearman's correlation coefficient p. and (b) shows the results when adding Gaussian noise to the ground truth.
Kernel validation. We consider synthetic setting on two 20-node networks with subset size k 3:
a BA network (m 2) and a WS network (k, p) = (5, 0.2), where the combinatorial graph in both networks contains (23) = 1140 combo-nodes. The underlying function is designed in the following
way: we first perform digen-decomposition on the graph Laplacian matrix: L UAU where - 1-1 AD- is the normalised graph Laplacian. The eigenvalues A diag(Aı, ... A.) are then sorted in ascending order and possess frequency information in the spectral domain [66.. where smaller eigenvalues indicate lower frequencies. As such, their corresponding eigenvectors U [u,," ... un.] can be used as signals of different smoothness and will be discussed in more detail in Appendix $ For the current experiment, we will take the elements from the eigenvector that corresponds to the 2nd non-zero eigenvalue (which is a smooth signal on the underlying graph), and use the average over l nodes as the underlying function in the combinatorial space.
After standardization, we use 25% combo-nodes as the training set to fit the models and validate their performance on the rest 75% conbo-nodes with Spearman's 's rank-based correlation coefficient p. addition, we also consider a noisy scenario where Gaussian noise of a added to the original function, where their results are summarized in Figure I1 for BA and Figure I2 for WS. We
22

---

Sum onerre ynoiisl
D Dimluden
Dificcon with ARD
(a)
50
Veleean pouectncs
Vetarter creandouus
viliiion grastuud
26-1
18-2
(b)
-2
30.3
Figure 12: Kernel validation on the combo-graph -rrooo based on a WS network (n = 20, 5, = 0.2).
observe that all kernels can capture the original signal except for Diffusion with ARD, which learns non-smooth transformation on the spectrum due to its over-paramettrization.. Nevertheless, we found the difference in performance is insignificant when using less-smooth underlying functions in $F
F Kernel Performance under Different Signal Smoothness
Following the setups in Appendix $ abovve now investigate how the inherited smoothness of the underlying function influences the performance of our kernels.
The smoothness of graph signals in the combinatorial space. The graph Fourier transform is given by f(A) = J" f. which transforms the original graph signal f to the frequency domain, as illustrated in the second plot from Figure 13 To change the smoothness of the underlying function in the combinatorial space, we consider j-th eigenvector with j E 12, 4, 8, 12, 16] as the underlying signals (from the original graph) and then use the same method in S that takes the average over the nodes in the subset as the underlying function in the combinatorial space. To compare the smoothness among different underlying functions (in the combinatorial space), first calculate the cumulative energy of Fourier coefficients; since we are modeling on random graphs, the process will be repeated 50 times with different random seeds, after which we plot the results the third plot in Figure 13 with mean and standard error. We can observe a clear trend that the underlying function in the combinatorial space becomes less smooth when using eigenvector that corresponds higher frequency (larger cigenvalue).
Cumulativ Sq, GFFT Coef
GFT Magnimdee
Eigenvalue
1.5
0.35
1.0-
0.50
Dipen Vec
0.5
12
16
0.0
0.00
500
1000
1000
Eigenvalue Index
Eigenvalue Index
Eigenvalue Index
Figure 13: Smoothness of different underlying functions (average of different eigensetor.............s
Kernel performance under different smoothness. With the same settings in Appendix S we validate the performance kernels on functions of different smoothness levels the combinatorial graph (as described above) and report their results by Spearman's correlation coefficient p box-plot Figure 14 For each kernel, we can see clear drop in validation performance as the function becomes less smooth, which will in turn negatively affect the performance of BO.
23

---

0.75
Spearnan's
0.50
Egtn Vec
0.25
0000
polynomial
polynomial suminverse
diffusion
diffusion and
Figure 14: Performance (Spearman's 's rank-based correlation coefficient p) of kernels for underlying functions with different smoothness, where darker shades use eigenvectors of the higher index and thus indicate less-smooth functions.
G Behavior Analysis of GraphComBO
In this section, we provide an in-depth behavior analysis of GraphComBO from two of the main experiments: synthetic task of maximizing the average eigenvector centrality BA networks, and real-world task flattening the curve on the contact network. The results are present in Figure [5] [5] and Figure T6 respectively, where also record additional information (1) the explored combo-gran graphp size and (2) the distance of the current combo-subgraph center to the starting location. Note that these recorders are only available for methods based the proposed combo-graph, where all of these methods start at the same location before searching.
BA: Conrrality: Kedd
Higen Centrality
Eigen Centrality: km16
Rigen Centrality:
Regret
1.5
1.0
7
0.8
6-
0.5
0.6
Distnnee from Sturt Explore ComboGrrph
70"-
100
100
10F
10
10a
10
10"
100
200
2000
1000
200
3000
10
100
200
300
10
100
200
300
102
10
10"
101
1n7
10
#Querres
+Queries
#Queries
#Queries
k-Local Scarch
k-Randen
GraphComBO
Figure 15: Behavior analysis of maximizing average eigenvector centrality on the BA network.
From both figures, it is straightforward to find that BFS and DFS behave differently given their exploration size and travel distance, in which BFS performs heavy exploitation and DFS performs large exploration. On the other hand, while BO explores more combinatorial space than local search in both experiments, we can notice the following distinctions in the source of its performance gain.
Considering the synthetic experiment results on BA network with a small k, we can observe that the subgraph center of GraphComBO is slightly more distant from the start location compared to the local search the beginning, but later saturates and caught up by local search. Such behavior also holds when A increases, especially at & = 32 where local search generally travels more distantly than GraphComBO. This implies that when & is small, the performance gain may mainly come from the exploration, whereas when increases, we are losing the relative advantage of exploration and the performance gain mainly from exploitation, which is consistent with our conjecture in $3.3 On the contrary, the result from flattening the curve experiment tells a different story, where GraphComBO takes a more cnploittaiio-oocusee strategy compared local search when small, but as & increases, it gradually shifts to an exploration-driven behavior.

---

Plattening the curve: k-4
Plittening the curve; k-8
Flartening the curve: k-16
Plattening the curve: k-32
Pop. Infect. Time
0.50
0.46
0.52
0.96
0.45
0.48
0.44
0.44
0.46
Distance Start Explored ConnhoGraph
100
200
2101
100
200
300
10
100
2001
300
10
100
200
300
10%
00
105
10
002
10
10a
10P
10
100
200
300
100
300
10
100
200
300
10
100
200
00
10a
10
101
10/
10a
100
100
#Queries
#Queries
#Queries
#Queries
Random
DPS
Local Search
k-Locol Search
Randoo Walk
GraphComBBO
Figure 16: Behavior analysis of flattening the curve experiment on the contact network with SIR.
H
Comparison with COMBO
In this section, compare our method with COMBO 40 (still much larger than the graphs used in COMBO's experiments), where the results in Figure 17 show clear advantage of framework over COMBO, and make the following explanations.
on small BA and WS graphs of [V] 500
avg PagoRank (maa)
HA; avg. Pageltank; km2
BA; avg. PageRank; kmd
BA; avg. PageRank; kmH
BA: avg. PageRank: k-16
12.5
16
10
1000
12
14
7.5
12
arg Papettank (max)
WS: PapeRank: km2
WSS: PageRank: kml
WSS: PageRank: k=8
WS: PagcRank: k=16
10
100
200
10
100
200
10
100
200
10
100
200
#Queries
#Queries
&Queries
@Queries
GmphiComlIO
Figure 17: Comparison with COMBO in maximizing avg. PageRank on small BA and WS networks.
To implement COMBO under our setting of k-node subsets from single graph G of size N, we generate identical copies of G and form the k-node subset by drawing one node from each of the copy. This leads to search space of N which is the key limitation of COMBO under this setting since it is supposed to be (N). As result, there are many repeated and invalid locations in the search space, for example, at k = 3, (1, 2, 3), (1. 3, 2), (2, 1,.). are different subsets in COMBO, but they all should be the same subset under the current single graph setting; meanwhile (1, 2), (1, 1, 2), (1, 1), are valid subsets in COMBO, but they are invalid k-node combinations on a single graph. This limitation makes COMBO highly inefficient under this new problem setting, and therefore leads to inferior performance compared to proposed method.
25

---

I Scalability on Large Graphs
Results on OGB-arXiv. Since our framework assumes no prior knowledge of the full graph and takes a local modeling approach that gradually reveals the graph structure, it can scale to large underlying graphs with a reasonable choice of k. To better support this claim, we further test GraphComBO on a large social network XGB-arXiv ([V) = 1.7 10") from the open graph benchmark with & up to 128, where the results in Figure 18 show clear advantage of our framework over the other baselines. Note that the local search methods underperform the random baseline under this setting, since exploration is relatively more important than exploitation.
OGiB-arXiv; Avg. PigeRank: kmd
OGB-arXXiv Avp. PageRank: km8
OGB--arXiv, Avp. PapeRank; km16
ave Pagettank (mnx)
20
20
10
5-
200
S00
200
400
são
1000
200
são
OGB arKiv; Avg. PageRank: k=32
OGB arKiv, Avg. PageRank: k-64
OGB arXiv, Avg. PageRank: k=128
(0gg PagoRack (eax)
7.5-
5.0-
2.5
100
200
400
600
S00
1000
100
200
400
600
500
1000
100
200
400
600
800
1000
#Queries
#Queries
QQueries
CruphComBO
Rundom
Local Search
Search
Random
Figure 18: Maximizing avg. PageRank on the OGB-arXiv network (V) = 1.77 x 10 |8|= = =
Choice of i in the experiments. The subset size k is set to 4,,4,8, 32] across the experiments, which is a common paradigm in the literature of subset selection on graphs 28 32 7 with k < 50 (<1% of the network), and the problem has been proven be NP-hard in many problems due the combinatorial explosion in search space (*). e.g. (1000) 2.3 1000 As such, the diminishing performance gain w.r.t. subset size k poses general challenge in the literature, and it becomes even more challenging in our setting, since the underlying function fully black-boxed and we assume no prior information of the graph structure.
Nevertheless, the proposed method still generally outperforms the other baselines across all experi- ments, and in the least favorable case, it performs comparably to the local search, which is also a novel baseline introduced in our paper since it needs to operate on the proposed combo- combo-graph.
J Settings under Noisy Observations
To show our framework's capability of handling noise, we further conduct noisy experiment at different noise levels on BA (V) = 10k) and WS (V) = 1k) networks with k = 8, where the goal is to maximize the average PageRank within node subset, i.e., f(S) - PageRank(S.). with being a subset of k nodes {V1, U2,..., v the underlying graph
standardized underlying function with noise. While is difficult to show the noise level to the signal variance in real-world experiments because of the combinatorial space, dardized signal under this synthetic setting with the following procedures. First, we standardized the PageRank scores over all nodes mean=0 and std=1 in the original space (denoted as PageRanksy To standardize the underlying function in the combinatorial space, we multiply V the average TageRanks as the final underlying function f(S). which is defined follows:
construct stan-
f(S) - Vkfa(S) =
1
PageRanks(S.) (St),
(9)
vk.
26

---

Original Signal
Original Signal
Noise 0=0).5
Noise C=0,5
Denity
Dansity
0.3
Noise 1.
0.2
0.1-
000
10
Underlying signal in the combinatorial space on BA network
Underlying signal in combinatorial space WS network
Figure 19: Density of underlying signals in the combinatorial space at different noise levels.
avg PagoRaak (max)
BA; PageRank; Noise d=0.1
BA; avg. PageRank: Noise 0=0.25
BA; PageRank: Noise a-0.5
BA: PageRank: Noise d-1
10
200
avg PugeRtakk (max)
WS: ovg. PageRank: Noise dwil.1
WS: avg. PageRank; Noise owll.2
WS: avg. PageRank; Nakee ow0.
avg. PageKank; Noise owl
100
200
30
200
200
#Querres
+Queries
aQueries
*Queries
GuplConBO
GrsptConBB Nokey
Runiom
Search
Local
DFS
Randon
Figure 20: Maximizing avg. PageRank (k:
BA and WS different noise levels.
where the expectation and variance of the transformed function F(S) are:
B[j(S)]
(10)
k
Var(f(8)) Var
Σ Page
(11)
x ls Var(Pageea (PageRanks((n)
(12)
(13)
Now, we can simply add random Gaussian noise to f(S). Specifically, we consider ~ N(0, o0) with a, [0.1, 0.25, 0.5, 1]. where the level of noise can be directly estimated since both the underlying function and noise now have a mean of O and a standard deviation of 1. addition, we further plot the estimated density of the original and noisy signals in Figure to to intuitively visualize the difference, which is done by randomly sampling 10 observed values in the combinatorial space (N)
GraphComBO-Noisy, To better tackle the noisy observations, we implement GraphComBO- Noisy, which uses the best posterior mean across both visited and non-visited combo-nodes within the original method which guided by the observation. The results in Figure show that the original method GraphComBO is robust to the noisy observations on both networks at different noise levels from a 0.1 to o = Compared with GraphComBO-NNosy, the observation-gui guidedd method performs comparably in most cases, except for a very noisy setting when o on WS networks, where we can observe clear advantage from the method guided by posterior mean, and it can be explained as follows.
combo-subgraph as new center, and then compare its performance
Unlike classical discrete combinatorial functions of independent variables, the underlying functions in our problems are highly related to the graph structure. For example, BA networks are known for rich structural information due to the scale-free characteristics (i.e. node degree exponentially distributed), which makes the distribution of the original signal heavily right-skewed with extreme values even after standardization (Figure 19 Left). By contrast, the WS small-world network (ran- domly rewired from ring) has more homogeneous node degrees, and thus the original signal will be
27

---

BA Bigen-Centraliiy k=
BA Eigon-Contrality k=8
BA Eigen-Centrality, k=16
BA Eigen-Contalliyy k=32
0.10
0.125
Regret
0.100
0.34
0.10
01175
0.05
0.05
300
200
300
100
100
Explored ComboGrrsp
10
107
101
104
107
10
10
107
200
300
Distance from Start
101-
101
101
107
105
10a
10
100
100
200
300
100
200
300
100
200
300
0
100
200
500
@Queries
#Queries
#Queries
*Queries
0:500
0:1000
Q:2000
Q:4000
Figure 21: Ablation study of Q = [500, 1k, 2k, 4k] with a fixed failtol = 30 on BA network.
more normally distributed after standardization (Figure 19 Right). Therefore, the noise level (even at 1) is less significant on BA networks when the algorithm finds the promising region, whereas on WS networks at a = 1. just as the reviewer described, we can see the algorithm is "misguided" by the observations compared to the posterior mean when the signal is highly corrupted.
K Ablation Studies on Hyperparameters
Lastly, we present the ablation study of BO's two hyperparameters: the combo-subgraph size Q and the tolerance of continuous failures failtol, and analyze their influence on BO's performance when using the best query location restart_metheee
over BA network and WS network.
Q To analyze the impact of Q on BO's results, we fix failtol 30 and vary Q at [500, 1000, 2000, 4000] and present the results in Figure 21 for BA and Figure 22 for WS. Overall, we can see that larger Q will lead to better performance in most situations, this is because we are starting with a random location in the combinatorial space and thus exploration is more important than exploitation. The explored combo-graph size and the distance of combo- subbo-subgraph center from the start also validate this interpretation, where a larger Q generally leads to larger exploration region that contains more distant nodes of higher querying values, therefore leading to better search performance. In addition, can also observe that as h increases, the performance gain from larger Q becomes salient, which further corroborates the statements in Section
failtol We analyze the influence of failtol BO's performance by using fixed 4000 and vary failtol at [10, 30, 50, 100), where the results are presented in Figure 23 for BA and Figure 24 for WS. We observe that despite small failtol is able to explore larger region in the combinatorial space, the performance gain from this behavior is limited. We make the following explanations. Since the underlying functions used on both graphs (average eigenvector centralities) are rather smooth, restarting with random location usually leads to worse overall search performance, and we adopt the best query location our reatart_methoor As a result, even if the algorithm restarts more frequently, it is still exploiting the regions around the same center. Nevertheless, we argue that with a different non- smoohh underlying function, or when having good initial location, small f failtol may have an advantage over the larger ones for its heavier exploitation behavior, and we leave this analysis to future work.
28

---

WS Eigen-Centraliye Centrality; k=
Crgenn-entrrltyy.. k=8
WS Eigen-Centrallie Centrality; k=16
WS Srgenn-entrality:: k=32
2x11
Regnt
10-2
12.0"
11
10a2
Explored CunbhoCraph
107
10
105
60'
100
10
104
80
10'
100
200
300
100
200
300
100
200
500
100
200
500
101-
10
101
Distncee
107
10P
10P
200
200
100
100
#Queries
&Queries
&Queries
&Queries
Q:500
0.000
Q:2000
Q:4000
Figure 22: Ablation study of Q [500, 14, 2k, 4k] with fixed failtol 30 on WS network.
BA
k=4
BA Figen-Centrality:: k=8
BA Figen-Centrality k=16
BA Figen-Centrality: k=32
0.125
0.15
Regret
0.100
0.08
0.10
0.075
2ó0
0.05
0.050
Explove ConboGruph
10
10
10*-
10
10"
10a
100
200
300
100
200
300
100
200
300
100
200
500
Distunce from Start
101-
101
107
10P
10F
100
/Queries
&Queries
#Queries
RQueries
fatol:10
futol:50
Figure 23: Ablation study of failtol [10, 30, 50, 100] with fixed Q 4000 BA network.
29

---

WS Figen-Cennrality Centrality; kmd
WS Figen-Centralie Centrality: k-8
WS Frigen-Centtliity:: k=16
WS Figen-Centrality: k=32
Regret
20-2
14
10
10
10
Exploned ComboGruph
102
100
10
10*
10'
10a
104
100
200
300
100
200
300
100
200
300
100
200
300
101
107:
10'
101
101
10P
10P
100
+Queries
+Queries
*Queries
#Queries
Gibol:10
6ital-30
Gito):50
fritn-100
Figure 24: Ablation study of failtol [10, 30, 50, 100] with fixed Q 4000 on WS network.
30

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We clearly state our contributions in the Abstract and the last paragraph of the introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discussed our limitations on the subset size k throughout the paper, and we also provide dedicated section $5 in the appendix for limitation and future work.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-specfiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
31

---

Answer: [Yes]
Justification:
We provide proofs for our Lemma in $D
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We provide detailed experimental settings as well as the hyper- pareer-prameeerss for reproducing our results in Appendix BB
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
32

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
We open-sourced our code in an anonymous [LIKK]
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
//nips //iiss.cc/pill wttpcccpppppppppeeeeeeeeeeeeeeee httpa///guddeee/eeeeabiiissssss /Cc////oddiiisssseeeeeee ssi.iiiiccyyyyyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification:
We specify all the detailed settings in Appendix $B for results reproduction.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We report results the mean and stand error from 20 runs with different random seeds for all experiments in $4
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
33

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out of range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We specify the hardware details and running time information in B
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
We confirm that this research work conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
We discuss the potential broader impact in 5
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
34

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification:
We believe this research work requires no safeguard.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We confirm that we have properly cited and credited the original owners the code in our implementation and do not violate their license and terms of use.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the Datasets.papersstt paperswi thcode. cww/ datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
35

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We have included instructions on how codes with detailed comments inside the code explaining their functions.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: There is no crowdsourcing nor experiment with human subject involved our research.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No crowdsourcing nor experiment with human subjects are involved our research.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such the institution conducting the review.
36


Reviews:
[{"review_id": "vBPeNTVlQK", "reviewer": "Reviewer_u7DA", "summary": "This paper proposes a Bayesian optimization (BO) method for optimizing black-box functions with costly evaluations over subsets of nodes in a graph. The central idea is to use the combo-graph associated with these node subsets from the original graph. This approach maintains the structural information of the original graph while enabling the use of existing techniques for BO of functions defined over graph nodes (e.g., BayesOptG). Additionally, to manage the large feasible space and better balance exploration and exploitation, a local search heuristic is introduced. The proposed method outperforms several standard baselines across various synthetic and realistic problems.", "questions": "1. Is it possible to extend the proposed approach to settings where the objective function is defined over sets of variable size?", "limitations": "The authors acknowledge the proposed approach's limitations, particularly in diminishing performance gains as $k$ increases. Additionally, I believe this approach is restricted to graphs significantly smaller than those typically encountered in real-world applications. Unfortunately, I believe these limitations are more concerning than suggested in the paper.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well-written overall, with sufficient technical details and figures that help build intuition. The proposed approach is technically sound, and the empirical evaluation shows significant improvements over the baselines in the problems considered.", "weaknesses": "1. (Minor) While the paper is generally well-written, some graph-theoretic concepts, such as the graph Laplacian, are not adequately defined.\n\n2. The technical novelty is somewhat limited, as the proposed approach mainly combines BayesOptG over the combo graph with a local search heuristic.\n\n3. My main concern is the practical utility of the proposed approach. Real-world application networks are typically much larger than those considered in the empirical evaluation. Additionally, larger values of $k$ are likely to be of interest in these applications. The current results suggest that the proposed approach may not offer improvements over some baselines in these more challenging scenarios.\n\n4. The empirical evaluation would benefit from including other BO baselines. Several methods for BO over discrete sets exist, and I believe that LADDER could be a particularly strong candidate.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed feedback that helped us improve our work. Please find our detailed response below.\n\n> The empirical evaluation would benefit from including other BO baselines. I believe that LADDER could be a particularly strong candidate.\n\nTo the best of our knowledge, this is the first attempt in the literature at extending BO to black-box optimization of functions over node subsets in a generic graph, which means we are addressing a new problem setup that has not been explored by existing works. \n\nFor LADDER, we argue that their setting is fundamentally different from ours, where their underlying function (from their experiments) is defined on **graph structures**, i.e., their search space consists of **different graphs** and the goal is to find the optimal graph, which requires **a graph kernel** to measure the similarity between two graphs. However, in our setting, the underlying function is defined on **node subsets** from **a single graph**. After mapping the subsets to nodes on the combo-graph, **a kernel on graph** is required to measure the similarity between two nodes.\n\nThe closest match to the current work is COMBO, where the search space consists of node subsets from **different (small) graphs** ($|V|<50$ in their experiments with $k<50$). Nevertheless, it can not scale to large graphs due to the infeasible computational cost from the eigendecomposition of the underlying graphs.\n\nWith that being said, we have added the comparison with COMBO in the general response on small BA and WS graphs of $|V|=500$ (still much larger than the graphs in their experiments), where the result (Fig.4 rebuttal PDF) shows a clear advantage of our framework over COMBO.\n\nWe will add the above discussion in the revised version and are happy to discuss more if the reviewer believes there are works in the literature that tackle the same problem as ours.\n\n> Real-world application networks are typically much larger than those considered in the empirical evaluation. I believe this approach is restricted to graphs significantly smaller than those typically encountered in real-world applications. \n\nFirstly, we validated our method across various real-world applications on contact networks, social networks, transportation networks, and molecule graphs that scale from order $10^2$ to $10^4$. This is consistent with the real-world graphs used in graph machine learning (e.g. graph neural networks: GCN, GAT, GIN) and graph data mining literature (e.g. influence maximization [1,2,3]), which are in the same order as ours -- based on this, we believe the graphs considered are comparable to the literature and not \"significantly smaller\" than realistic graphs.\n\nSecond, the graphs considered in other graph-related BO works, e.g. LADDER (mentioned by the reviewer), COMBO, NASBO, GRABNEL, are much smaller than ours, which are typically at order $10^1$ and $10^2$.\n\n### A new experiment on larger network with larger subset size $k$\n\nLastly, our framework can scale to large graphs, as it assumes no prior knowledge of the full graph and takes a local modeling approach that gradually reveals the graph structure. To better support our claim, we further test it on a large social network OGB-arXiv ($|V|=1.7\\times10^5$) from open graph benchmark with $k$ up to 128, where the results in Fig.1 (rebuttal PDF) show a clear advantage of our framework over the other baselines.\n\n> Additionally, larger values of k are likely to be of interest in these applications. The current results suggest that the proposed approach may not offer improvements over some baselines in these more challenging scenarios. \n\nWe argue that setting $k<50$ (<1% of the network) is very a common paradigm in the literature of subset selection on graphs [1,2,3], which has been proven to be NP-hard in many problems due to the combinatorial explosion in search space $\\binom{N}{k}$, e.g. $\\binom{1000}{32}\\approx2.3\\times10^{60}$. As such, the diminishing performance gain w.r.t. subset size $k$ poses a general challenge in the literature [4], and it becomes even more challenging in our setting, since the underlying function is fully black-boxed and we assume no prior information of the graph structure.\n\nHaving said that, the proposed method still generally outperforms the other baselines across all experiments, and in the least favorable case, it performs comparably to the local search, which is also a novel baseline introduced in our paper since it needs to operate on the proposed combo-graph.\n\n> The technical novelty is somewhat limited, as the proposed approach mainly combines BayesOptG over the combo graph with a local search heuristic.\n\nAs the prior work BayesOptG only considers $k=1$, which is limited for many real-world applications, we aim to generalize the framework to a combinatorial setting with the following technical contributions:\n\n1. A combinatorial graph tailored for node subsets in a generic graph.\n2. A recursive algorithm to sample subgraphs from the combinatorial space.\n3. To handle the combinatorial explosion problem, we use a local approach to traverse the combinatorial graph space by iteratively sampling its subgraphs.\n\nIn the early stage, we tried other localization methods such as selecting nodes inside a subgraph on the original graph as the subset. However, since we need to maintain the diversity of the subset to cover potentially distant nodes, none of them can fit into the problem as cohesively as the current method, which makes our design non-trivial.\n\nFor the variable size of the subset, we believe it belongs to a different but interesting setup, and leave it to future work for exploration. And for the graph-theoretic concepts, we will make sure they are clear in the revised version.\n\nWe believe that we have now addressed all the concerns from the original reviews, and hope the reviewer could kindly consider increasing the rating in light of this.\n\nPlease find the references in the comment chatbox below.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UBbMdcdEgG", "reviewer": "Reviewer_bfWL", "summary": "This paper introduces a framework for optimizing functions of subset of nodes in a graph with Bayesian Optimization (BO). The framework need not know the graph structure beforehand, but does require the knowledge of the cardinality of the considered subsets of nodes $1 \\leq k \\leq N$ for a graph $\\mathcal{G} = \\\\{V, E\\\\}$ where $|V| = N$. The framework works by iteratively building another graph, termed \"combo-graph\", where each \"combo-node\" is one of the $\\binom{N}{k}$ subsets of $k$ nodes. Two combo-nodes $\\tilde{v}_i = \\left\\\\{v^{(i)}_1, \\cdots, v^{(i)}_k\\right\\\\}$ and $\\tilde{v}_j = \\left\\\\{v^{(j)}_1, \\cdots, v^{(j)}_k\\right\\\\}$ are linked if $(\\tilde{v}_i \\cup \\tilde{v}_j) \\setminus (\\tilde{v}_i \\cap \\tilde{v}_j) = \\\\{v_l, v_m\\\\}$, and if $(v_l, v_m) \\in E$. BO is then conducted on this partial combo-graph (using graph kernels) to select a promising combo-node to sample the objective function with.", "questions": "Here are some questions to spark the discussion with the authors.\n\n(1) Do you account for noise in your framework?\n\n(1.1) If not, how do you expect your algorithm to react to noisy function values? I believe its behavior would be quite different, especially because the location of the combo-graph is selected according to the observed function value, which is not longer accurate.\n\n(1.2) If so, why does the framework apply the acquisition function to unvisited combo-nodes only? Why change the location of the combo-graph based on the observed function value instead of a more refined / optimistic estimate (e.g., the posterior mean of the surrogate model or the acquisition function value)?\n\n(1.3) If experiments are conducted in a noisy setting, can you provide an estimate of the noise level for each experiment as a proportion of the signal variance?\n\n(2) Do you have any insights on how the proposed algorithm compares to COMBO on experiments involving small graphs?", "limitations": "I believe the authors have addressed the limitations of their work, and I am looking forward to the discussion period for more details on the noisy setting.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "In spite of suffering from the drawbacks of local optimization, the presented framework is useful to tackle the combinatorial complexity involved in the optimization of functions over discrete structures. It opens an interesting avenue for extending BO to these problems.\n\nOverall, the article is clear and well-written.", "weaknesses": "**Noisy Setting**. Both the preliminaries (Section 2) and the described BO on Combo-Graphs (Section 3.3) seem to suggest that the framework has access to true function values. However, in Appendix B, it seems that many experiments do take place in a noisy setting, because the objective function is explicitely defined with an additional noise term (e.g., Ackley), or because it results from an average of Monte-Carlo samples (e.g., Influence Maximization, Flattening the Curve). As a result, it is unclear to me whether the described algorithm is fit for noisy problems. The notations $y_t$ and $f(v_t)$ do not help.\n\n**Comparison with COMBO**. I understand that COMBO does not address the same problem as the algorithm described in the paper. Nevertheless, given the lack of state-of-the-art baselines for this problem, it would be interesting to study how the algorithm compares to COMBO on problems involving small-enough graphs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the detailed feedback which helped us improve the current work. In summary, the reviewer's concerns are (1) If the framework can handle noisy observations, and (2) Comparison with COMBO on small networks. Please see below for our responses.\n\n> Do you account for noise in your framework? It is unclear to me whether the described algorithm is fit for noisy problems. \n\nYes, similar to other common BO methods, the proposed framework can handle noise. As pointed out by the reviewer, we used the Ackley function on a 2D grid with Gaussian noise as the underlying function in one of the synthetic experiments, meanwhile under real-world setups, we also used noisy results from simulations as the underlying functions. \n\nFor the notations, we intended to express the most standard setup in BO, that is $y = f(x) + \\epsilon$, with $\\epsilon \\sim N (0, \\sigma^2_{\\epsilon})$ being the noise term. We will make sure this is clear in the revised version.\n\n### A more comprehensive experiment under the noisy setting\n\nTo better answer the other questions from the reviewer and show our framework’s capability of handling noise, we further conduct a noisy experiment at different noise levels on BA ($|V|=10k$) and WS ($|V|=1k$) networks with $k=8$, where the goal is to maximize the average PageRank within a node subset, i.e., $f(\\mathcal{S}) = \\frac{1}{k}\\sum_{i=1}^k PageRank(\\mathcal{S}_i)$, with $\\mathcal{S}$ being a subset of $k$ nodes $\\\\{v_1, v_2, …, v_k\\\\}$ in the underlying graph.\n\n> Can you provide an estimate of the noise level to the signal variance?\n\nWhile it is difficult to show the noise level to the signal variance in real-world experiments because of the combinatorial space, we can construct a standardized signal under this synthetic setting with the following procedures:\n\nFirst, we standardized the PageRank scores over all nodes to mean=0 and std=1 in the original space (denoted as $PageRank_s$). To standardize the underlying function in the combinatorial space, we multiply $\\sqrt{k}$ to the avg. $PageRank_s$ as the final underlying function $\\tilde{f}(\\mathcal{S})$, that is, \n\n$\\tilde{f}(\\mathcal{S}) = \\sqrt{k} f_s({\\mathcal{S}}) = \\frac{1}{\\sqrt{k}} \\sum_{i=1}^k PageRank_s(\\mathcal{S}_i)$, \n\nin which $\\mathbb{E}[\\tilde{f}(\\mathcal{S})] = 0$, and $Var(\\tilde{f}(\\mathcal{S})) = \\frac{1}{k} Var(\\sum_{i=1}^k PageRank_s(S_i)) = \\frac{1}{k} \\times k \\times Var(PageRank_s(v)) = 1$. \n\nNow, we can simply add random Gaussian noise to $\\tilde{f}(\\mathcal{S})$. Specifically, we consider $\\epsilon \\sim N (0, \\sigma^2_{\\epsilon})$ with $\\sigma_{\\epsilon}$ at [0.1, 0.25, 0.5, 1], where the level of noise can be directly estimated since both the underlying function and noise are now of mean=0 and std=1. In addition, we further plot the estimated density of the original and noisy signals in Fig.2 (rebuttal PDF) to intuitively visualize the difference, which is done by randomly sampling $10^5$ observed values in the combinatorial space $\\binom{\\mathcal{V}}{k}$. \n\n> In the noisy setting, why does the framework apply the acquisition function to unvisited combo-nodes only? Why change the \nlocation of the combo-graph based on the observations instead of the posterior mean or the acquisition function?\n\nWe would like to thank the reviewer for this insightful question. As suggested, we implement **GraphComBO-Noisy**, which uses the best posterior mean across both visited and non-visited combo-nodes within the combo-subgraph as the new center. \n\n> How do you expect your algorithm to react to noisy function values? I believe its behavior would be quite different, especially because the location of the combo-graph is selected according to the observed function value, which is not longer accurate.\n\nThe results (Fig.3 rebuttal PDF) show that the original method GraphComBO is robust to the noisy observations on both networks at different noise levels from $\\sigma=0.1$ to $\\sigma=1$. Compared with GraphComBO-Noisy, the observation-guided method performs comparably in most cases, except for a very noisy setting when $\\sigma=1$ on WS networks, where we can observe a clear advantage from the method guided by posterior mean, and it can be explained as follows.\n\nUnlike classical discrete combinatorial functions of independent variables, the underlying functions in our problems are highly related to the graph structure. For example, BA networks are known for rich structural information due to the scale-free characteristics (i.e. node degree is exponentially distributed), which makes the distribution of the original signal heavily right-skewed with extreme values even after standardization (Fig.2 Left). By contrast, the WS small-world network (randomly rewired from a ring) has more homogeneous node degrees, and thus the original signal will be more normally distributed after standardization (Fig.2 Right).\n\nTherefore, the noise level (even at $\\sigma=1$) is less significant on BA networks when the algorithm finds the promising region, Whereas on WS networks at $\\sigma=1$, just as the reviewer described, we can see the algorithm is “misguided” by the observations compared to the posterior mean when the signal is highly corrupted.\n\n> Comparison with COMBO on small graphs\n\nWe thank the reviewer for acknowledging our different problem settings from COMBO. As suggested, we have implemented COMBO on smaller BA and WS networks of 500 nodes, which are still much larger than the ones used in their experiments ($|V|<50$). The results are presented in Fig. 4 in the rebuttal PDF, and we can see a clear advantage of our framework over COMBO. Please refer to the general response for a more detailed analysis.\n\nWe’d like to thank the reviewer again for the insightful comments, and we will make sure to include the above discussion in the revised version. We believe that we have now addressed all the concerns from the reviews, and hope the reviewer could kindly consider increasing the rating in light of this.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VTNDBRHbq6", "reviewer": "Reviewer_Y7Gf", "summary": "The present paper proposes an approach based on Bayesian optimization for optimizing a function over subsets of nodes of size $k$ in a graph. At each step of the algorithm, a local neighborhood is constructed and the best node with respect to an acquisition function is chosen as the center for the next step. The approach is evaluated against several other classical techniques on a variety of benchmarks, where it is competitive and often outperforms the other approaches.", "questions": "Are there other common baselines in the literature that are not based on Bayesian optimiazation? If one were to compare the present approach against a task-specific approach, do you have intuition on whether the present approach would perform significantly worse?\n\nOther:\n- ego-subgraph is not defined", "limitations": "Some future direction are discussed.", "rating": 5, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "I am unfamiliar with the topic and the related literature, so take my comments with a grain of salt. If applying Bayesian optimization to the problem is indeed novel, then I think it is an interesting contribution for the ML community, even if none of the ideas appears to be very involved in itself.\n\nThe strongest selling point of the paper to me are the empirical results, where the performance is consistent and tends to outperform the baselines.", "weaknesses": "It is not very surprising that an approach that makes informed decisions to guide the search outperforms simple baselines like BFS or local search, somewhat weakening the significance of the results to me.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for acknowledging the contribution of the proposed framework. Please see our response to the review comments below.\n\n> If applying Bayesian optimization to the problem is indeed novel, then I think it is an interesting contribution for the ML community, even if none of the ideas appears to be very involved in itself.\n\n> It is not very surprising that an approach that makes informed decisions to guide the search outperforms simple baselines like BFS or local search, somewhat weakening the significance of the results to me.\n\nAs discussed in the introduction, there are many optimization problems on graphs that involve expensive black-box functions defined on node subsets, e.g. outcomes from real-world implementation, results of large number simulations, and outputs from graph neural networks; at the same time, there are many applications where the underlying graph is not known a priori, e.g. offline social networks and contact networks. However, there is no general framework in the literature to optimize such black-box functions of node subsets in graphs, except for the classical graph traversal algorithms such as BFS/DFS and local search.\n\nWhile we agree with the reviewer that it is very intuitive and “expected” that BO will outperform these classical algorithms, the main contribution of our work is, as pointed out by the reviewer, extending BO to this novel setup via an effective approach and obtaining good results over the existing baselines. To design such a framework, we have made the following technical contributions: \n\n1. We proposed a combinatorial graph tailored for node subsets in a generic graph.\n\n2. We introduced a recursive algorithm to sample subgraphs from the combinatorial space.\n\n3. To handle the combinatorial explosion problem, we use a local approach to traverse the combinatorial graph space by iteratively sampling its subgraphs and moving around the subgraph center to more promising regions, which is guided by a surrogate model.\n\nIn the early stage, we tried other localization methods such as selecting nodes inside a subgraph on the original graph as the subset. However, since we need to maintain the diversity of the subset to cover potentially distant nodes, none of them can fit into the problem as cohesively as the current method, which makes our design non-trivial.\n\n> Are there other common baselines in the literature that are not based on Bayesian optimization? \n\nAs discussed above, to the best of our knowledge, the only existing baselines are those based on graph traversal algorithms, which have been modified to the current problem setting. In particular, we have proposed $k$-random walk and $k$-local search (Appendix B) as baselines that operate on the original graph, which have shown strong results in some of our experiments. We are more than happy to discuss with the reviewer if they believe there are works in the literature that tackle the same problem setups as ours.\n\nIn addition, we would like to mention that a new experiment has been added to the general response, in which we compare our method to COMBO (nevertheless, a BO baseline) on small-scale networks. The result (Fig. 4 rebuttal PDF) shows the proposed framework consistently outperforms this baseline, and we kindly refer the readers to the general response for more details if they find it relevant.\n\n> If one were to compare the present approach against a task-specific approach, do you have intuition on whether the present approach would perform significantly worse?\n\nWe thank the reviewer for this high-level question on the suitability of our framework to specific problems, to which we’d like to respond from the general Bayesian Optimization (BO) perspective in the following.\n\nFirst, BO is most suitable for optimizing functions that are black-box and expensive to evaluate. If we have access to the gradient of the function, or the function is easy to evaluate, then there are more appropriate alternatives such as gradient-based optimizers or Reinforcement Learning (RL) methods, and we believe BO, as a black-box solver, would not be an appealing approach in those settings.\n\nHowever, if the function is black-boxed and its values are costly to observe, then sample efficiency becomes an essential criterion to the optimizer, that is, we wish to obtain the best possible location within a limited number of queries. Note that RL usually requires a large number of samples to train the reward and policy models, which is infeasible under this setting.\n\nBased on the above discussion, if our goal is to optimize certain expensive black-box functions, where some “good guesses” can be obtained from domain knowledge or a task-specific approach, we can always incorporate that information into BO by either initializing the search at the promising locations identified by the task-specific method, or updating the prior in the surrogate with the domain knowledge. This implies that, in most cases, BO serves as a complement to the domain-specific methods rather than a complete substitute.\n\n> Other: ego-subgraph is not defined\n\nWe thank the reviewer for this reminder. In Lemma 3.2, an $\\ell$-hop ego-subgraph centered at an arbitrary combo-node $\\hat{v}$ on the combo-graph means that we create an ego-network around $\\hat{v}$ with its $\\ell$-hop neighbors, and the resulting ego-network is an ego-subgraph. We will make sure this concept is clear in the revised version.\n\nWe’d like to thank the reviewer again for the comments that helped us reflect on our work. We believe that we have now addressed the concerns from the original reviews, and hope the reviewer could kindly consider increasing the rating/confidence in light of this.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oQ5DAEDMvt", "reviewer": "Reviewer_yrTA", "summary": "This paper addresses the challenge of optimizing functions defined on node subsets in a graph. These functions are combinatorial, black-box, and expensive to evaluate. The proposed solution utilizes Bayesian Optimization (BO), mapping each k-node subset to a node in a new combinatorial graph, and traversing this graph efficiently through a recursive algorithm. Extensive experiments demonstrate the effectiveness of this approach on various graphs and optimization tasks.", "questions": "I have to say I am not very familiar with the field of black-box combinatorial optimization. I am willing to let the Area Chair focus more on the opinions of the other reviewers. However, I am personally curious about, how such approaches achieve provably good performance when we have no assumptions on function $f$ ? It is likely to fall into no-free-lunch theorem.", "limitations": "The performance scales poorly as $k$.\n\nThe choice of hyperparameter is ad-hoc.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The new framework proposed in this paper is innovative. It is function-agnostic and can be applied to various optimization problems, thus offering a wide range of applications. The experimental results also demonstrate its potential. The presentation of paper is clear and comprehensible.", "weaknesses": "The domain of the optimization problem is the set of all k-tuples of vertices on a graph. However, it seems the structure (in particular, the edges) of the graph is not mentioned. Is the graph structure not essential in this context?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for acknowledging the novelty and potential of our work! Please see our responses to the raised questions below.\n\n> How such approaches achieve provably good performance when we have no assumptions on function $f$? It is likely to fall into no-free-lunch theorem.\n\nWe’d like to respond from the general Bayesian Optimization (BO) perspective.\n\nFirst, BO is most suitable for optimizing functions that are black-box and expensive to evaluate. If we have access to the gradient of the function, or the function is easy to evaluate, then there are more appropriate alternatives such as gradient-based optimizers or Reinforcement Learning (RL) methods. However, if the function is black-boxed and its values are costly to observe, then sample efficiency becomes an essential criterion to the optimizer, that is, we wish to obtain the best possible location within a limited number of queries. Note that RL usually requires a large number of samples to train the reward/policy models, which is infeasible under this setting.\n\nThe performance gain in BO mainly comes from the surrogate modeling approach, where a tractable model (e.g. Gaussian Processes) is used to gradually approximate the underlying function based on the observations. At each iteration, the surrogate model is fitted with previous observations and generates predictions on the rest search space, which allows us to identify the most promising location based on past knowledge, and then query its function value. In the next iteration, this new observation will be used to re-fit the surrogate, and we repeat the process until hitting the evaluation budget.\n\nIt means that, even though we have no prior knowledge about $f$ at the beginning, the algorithm tries to adaptly learn the pattern in $f$ along the search, where the next move is always guided by past knowledge, and thus explaining the superior performance of BO over other random heuristic methods. \n\n> It seems the structure (in particular, the edges) of the graph is not mentioned. Is the graph structure not essential in this context?\n\nThe underlying graph structure is very critical to the problem from the following perspectives.\n\n1. Unlike classical combinatorial optimization over discrete space (e.g. searching for the optimal hyper-parameter combination), the configurations (i.e. node subsets) in our setting are not independent but linked via an underlying graph structure, which needs to be considered during optimization. This is why a graph GP is adopted as the surrogate model, where the similarity between configurations is measured by a kernel on graph (Equation 2), as discussed in Section 3.2. \n\n2. Specifically, the above kernel is defined as a function of the graph Laplacian matrix $L$, which is computed by $L = D - A$, with $D$ being the degree matrix and $A$ being the adjacency matrix. This is how the edges are incorporated into modeling.\n\n3. If the graph is sparse (e.g. a grid is sparser than a fully connected graph), the combinatorial graph will also be sparse. Then, with a fix-sized combo-subgraph of $Q$ combo-nodes, we can cover more hops (i.e. distant nodes) from the center combo-node at each iteration. Thus, the algorithm will traverse the comb-graph (i.e. substituting the elements in the subset) at a faster pace, as discussed in Lemma 3.2.\n\n4. If the underlying graph structure is informative (e.g. BA network is more uniquely structured with heterogeneous node degree distribution as opposed to the WS network, whose node degree is more homogeneous distributed), the combinatorial graph will also be informative. In this case, it means that the kernel in the graph GP surrogate will capture more structural information, which eventually helps the algorithm visit better locations during optimization, as explained in Sections 3.3 and 4.\n\n> The performance scales poorly as k.\n\nWe are glad that the reviewer noticed our discussion on the limitation about subset size $k$, and we would like to make some further clarification below.\n\nIn the literature of subset selection on graphs, setting $k<50$ (<1% of the network) is very a common paradigm [1,2,3], since many problems have been proven to be NP-hard due to the combinatorial explosion in the search space $\\binom{N}{k}$. As such, when the subset size $k$ increases, it poses a general challenge in the literature that the performance gain between heuristic optimization algorithms and random baselines is diminishing [4]. On top of this, the problem becomes even more challenging under our setting, since the underlying function is fully black-boxed and we assume no prior information about the graph structure.\n\nHaving said that, the proposed method still generally outperforms the other baselines across all experiments, and in the least favorable case, it performs comparably to the local search, which is also a novel baseline introduced in our paper since it needs to operate on the proposed combo-graph.\n\n> The choice of hyperparameter is ad-hoc.\n\nWe have conducted an ablation study in Appendix I to analyze the sensitivity of GraphComBO to the combo-subgraph size $Q$ and the non-improvement tolerance $\\texttt{failtol}$, where the results show that the proposed method is quite robust to the latter. However, we do agree with the reviewer that the algorithm would benefit from an automatic strategy for determining the combo-subgraph size $Q$ (e.g. an adaptive design of $Q$), which we will leave to future exploration.\n\nWe’d like to thank the reviewer again for the comments that helped us improve the current work. We believe that we have now addressed all the concerns from the original reviews, and hope the reviewer could kindly consider increasing the rating/confidence in light of this.\n\n[1] *Maximizing the Spread of Influence through a Social Network, KKD 2003*\n\n[2] *Cost-effective Outbreak Detection in Networks, KDD 2007*\n\n[3] *Robust Influence Maximization, KDD 2016*\n\n[4] *Influence Maximization on Social Graphs: A Survey, TKDE 2018*", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We want to first thank all the reviewers for their detailed and valuable feedback, which we find very helpful in improving our work. We are also glad to see they acknowledged the innovation and potential impact in the community (bfWL, Y7Gf, yrTA), the technical soundness (u7DA, Y7Gf), the significance in experiment results (u7DA, Y7Gf, yrTA), and the clarity of writing (u7DA, bfWL, yrTA) in our work. We address the common concerns below.

## Comparisons with the existing SOTA BO baselines (u7DA, bfWL)

We would like to emphasize that the current work is, to the best of our knowledge, the first attempt in the literature that extends Bayesian Optimization (BO) to black-box functions of node subsets in a generic graph. In particular, the local modeling approach in our framework enables the algorithm to handle situations when the underlying graph structure is not known a priori and can only be gradually revealed by queries on the fly.

The proposed optimizer has real-world applications across various domains and has been validated on contact networks, social networks, transportation networks, and molecule networks, with different underlying functions such as measures for network resilience, results from epidemic/social influence simulations, and outputs from graph neural networks.

We argue that this novel problem setting has been overlooked in the literature, where most graph-related BO methods (e.g. LADDER [1], NASBO [2], GRABNEL [3]) are designed for optimizing graph structures, i.e., their search space consists of different graphs and the goal is to find the optimal graph, in which a graph kernel is required to measure the similarity between two graphs. However, in our setting, the underlying function is defined on node subsets from a single graph, which, after being mapped to the combo-graph, requires a kernel on graph to measure the similarity between two nodes.

The closest match to the current work is COMBO [4], where the search space consists of $k$-node subsets from $k$ different (small) graphs respectively ($|V|<50$ in their experiments with $k<50$), and the goal is to find the most optimal subset. Nevertheless, it assumes the knowledge of full graph structure in advance, and can not scale to large graphs due to the infeasible computational cost from the eigendecomposition of the underlying graphs.

### Further experiment on the comparison with COMBO

With that being said, as suggested by reviewer bfWL, we have added the comparison with COMBO on small BA and WS graphs of $|V|=500$ (still much larger than the graphs used in COMBO’s experiments), where the result (Fig.4 rebuttal PDF) shows a clear advantage of our framework over COMBO, and we make the following explanations.

To implement COMBO under our setting of $k$-node subsets from a single graph $\mathcal{G}$ of size $N$, we generate $k$ identical copies of $\mathcal{G}$ and form the $k$-node subset by drawing one node from each of the copy. This leads to a search space of $N^k$, which is the key limitation of COMBO under this setting since it is supposed to be $\binom{N}{k}$. As a result, there are many repeated and invalid locations in the search space, for example, at $k=3$, (1,2,3), (1,3,2), (2,1,3), ... are different subsets in COMBO, but they all should be the same subset under the current single graph setting; meanwhile (1,2,2), (1,1,2), (1,2,1), … are valid subsets in COMBO, but they are invalid $k$-node combinations on a single graph. This limitation makes COMBO highly inefficient under this new problem setting, and therefore leads to inferior performance compared to our proposed method.

We are happy to discuss more if the reviewers believe there are works in the literature that tackle the same problem as the current one.

## Diminishing performance gain with increasing subset size $k$ (u7DA, yrTA)

In the literature of subset selection on graphs, setting $k<50$ (<1% of the network) is a very common paradigm [5,6,7], since many problems have been proven to be NP-hard due to the combinatorial explosion in the search space $\binom{N}{k}$. As such, when the subset size $k$ increases, it poses a general challenge in the literature that the performance gain between heuristic optimization algorithms and random baselines is diminishing [8]. On top of this, the problem becomes even more challenging under our setting, since the underlying function is fully black-boxed and we assume no prior information of the graph structure.

Having said that, the proposed method still generally outperforms the other baselines across all experiments, and in the least favorable case, it performs comparably to the local search, which is also a novel baseline introduced in our paper since it needs to operate on the proposed combo-graph.

### Additional experiment on larger network with larger subset size $k$

Lastly, we further test GraphComBO on a large social network OGB-arXiv ($|\mathcal{V}|=1.7\times10^5$) from open graph benchmark with $k$ up to 128, where the results in Fig.1 (rebuttal PDF) show a clear advantage of our framework over all the other baselines. In this case, the local search baseline even underperforms random selection and random walk, as it overly focuses on local exploitation rather than exploration, whereas the latter is more critical on large underlying graphs.

[1] *Combining latent space and structured kernels for Bayesian optimization over combinatorial spaces, NeurIPS 2021*

[2] *Interpretable Neural Architecture Search via Bayesian Optimisation with Weisfeiler-Lehman Kernels, ICLR 2021*

[3] *Adversarial Attacks on Graph Classification via Bayesian Optimisation, NeurIPS 2021*

[4] *Combinatorial Bayesian Optimization using the Graph Cartesian Product, NeurIPS 2019*

[5] *Maximizing the Spread of Influence through a Social Network, KKD 2003*

[6] *Cost-effective Outbreak Detection in Networks, KDD 2007*

[7] *Robust Influence Maximization, KDD 2016*

[8] *Influence Maximization on Social Graphs: A Survey, TKDE 2018*

Meta-review: This paper presents a clever approach to allow existing Bayesian Optimization methods for optimizing over nodes in a graph to support the task of optimizing over *subsets of* nodes in a graph by constructing an appropriate combinatorial graph coupled with a local search technique. Reviewers concur that the paper is clearly written and experiments are compelling.
Decision: Accept (poster)