Bayesian Optimisation of Functions on Graphs
Authors: Xingchen Wan
Pierre Osselin
Henry Kenlay
Binxin Ru
Michael A Osborne
Xiaowen Dong
Venue: NeurIPS 2023 poster (2023)
Keywords: graphs
Bayesian optimisation
scalability
TL;DR: This paper considers the problem of optimising over functions defined on graphs and develops a Bayesian optimisation framework for this task.

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

Bayesian Optimisation of Functions on Graphs
Xingchen Wan', Pierre Osselin", Henry Kenlay Binxin Ru, Michael A. Osborne, Xiaowen Dong Department of Engineering Science, University of Oxford {xwan, osselinp, kenlay, robin, mosb, wtw.mm..songo... (raloonnrrrootssssoooooooossmsss ox ac.uk uk
Abstract
The increasing availability of graph-structure data motivates the task of optimising over functions defined on the node set of graphs. Traditional graph search algo- rithms can be applied in this case, but they may be sample-inefficiee make use of information about the function values; the other hand, Bayesian op- timisation a class of promising black-box solvers with superior sample efficiency, but it has scarcely been applied to such novel setups. To fill this gap, we propose a novel Bayesian optimisation framework that optimises over functions defined generic, large-scale and potentially unknown graphs Through the learning of suitable kernels on graphs, our framework has the advantage of adapting to the be- haviour of the target function. The local modelling approach further guarantees the efficiency of our method. Extensive experiments on both synthetic and real-world graphs demonstrate the effectiveness of the proposed optimisation framework.
and do not
Introduction
Data collected in network environment, such transportation, financial, social, and biological networks, have become pervasive in modern data analysis and processing tasks. Mathematically, such data can be modelled as functions defined on the node set of graphs that represent the networks. This then poses new type of optimisation problem over functions on graphs, i.e. searching for the node that possesses the most extreme value of the function. Real-world examples of such optimisation tasks are abundant. For instance, if the function measures the amount of delay at different locations measures
in an infrastructure network, one may think about identifying network bottlenecks; may be interested
the amount of influencing power users have in social network platform, in finding the most influential users; it measures the time when individuals were infected in an epidemiological contact network, an important task would be to identify "patient zero" of the disease.
Optimisation of functions on graphs challenging. Graphs are an example of discrete domains, and conventional algorithms, which are mainly designed for continuous spaces, do not apply straightfor- wardly. Real-workh graphs are often extremely large and sometimes may not even be fully observable. Finally, the target function, such as in the examples given above, is often black-box function that is expensive to evaluate at the node level and may exhibit complex behaviour on the graph.
Traditional methods to traverse the graph, such as breadth-firs search (BFS) or depth- fepth--frst search (DFS) [14], are heuristics that may be adopted in this setting for small-scale graphs, but inefficient to deal with large-scale real-world graphs and complex functions. Furthermore, these search methods only rely on the graph topology and ignore the function on the graph, which can be exploited make the search more efficient. On the other hand, Bayesian optimisation (BO) [16] is sample-efficien efficient sequential optimisation technique with proven successes in various domains and suitable for solving black-box, supensive-to-evalle with graph-related settings, e.g. optimising for graph structures (i.e. the individual configurations
optimisation problems. However, while BO has been combined
Equual contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

(a)
Current local
Current subgraph centre
(b)
(c)
subgraph
G
v
New
New
Next query
subgraph
local
location
centre
subgraph
MAX (1) WEVE
2241
G
Illustration of one iteration of BayesOpiG on an example graph. (a) At iteration t, we construct a local subgraph G, centred around vi whose nodes are marked in orange-red, with darker shade denoting a shorter distance to u/ the best node seen far (marked in black), and nodes outside G are marked in grey, The readers are referred to $3.2 for the details; (b) we place a GP surrogate with the covariance function defined in $3.1 on G2 and pick the maximiser of the acquisition function (the acquisition function values are marked in shades of blue, with a darker shade denoting a higher acquisition value) as the node to query for iteration + 1 (vt+1) ($3.2) and (c) if querying ut+1 leads to better objective function value (f(++1) < f(uf), ). assuming minimisation), the neighbourhood around it is selected as the new subgraph G1+1- The process continues until convergence pre-set number evaluations is reached.
Figure 1:
that we optimise for are graphs) in the context of neural architecture search [20, 34), graph adversarial examples [42] or molecule design [23], it has not been applied to the problem of optimising over functions on graphs (i.e. the search space is graph and the configurations we optimise for are nodes in the graph). The closest attempt was COMBO [27]. which is a framework designed for a specific purpose, i.e. combinatorial optimisation, where the search space is modelled as a synthetic graph restricted to one that can be expressed as Cartesian product of subgraphs. It also assumes that the graph structure is available and that the function values are smooth in the graph space to facilitate using diffusion kernel. All these assumptions may not hold in the case of optimisation over generic functions on real-world graphs.
We address these limitations in our work, and our main contributions are as follows: we consider the problem setting of optimising functions that are supported by the node set of a potentially generic, large-scale, and potentially unknown graph a setup that is by itself novel to the best of our knowledge in the BO literature. We then propose a novel BO framework that effectively optimises in such a problem domain with 1) appropriate kernels to handle the aforementioned graph search space derived by spectral learning on the local subgraph structure and is therefore flexible in terms of adapting to the behaviour of the target function, and 2) efficient local modelling to handle the challenges that the graphs in question can be large and/or not completely known a-priori. Finally, we deploy our method in various novel optimisation tasks on both synthetic and world graphs and demonstrate that it achieves very competitive results against baselines.
2 Preliminaries
BO is zeroth-order (i.e. gradient-free) and sample-efficient sequential optimisation algorithm that aims to find the global optimum x= of a black-box function defined over search space X: x² = arg minzex [xx) (we consider minimisation problem without loss of generality). BO uses statistical surrogate model to approximate the objective function and an acquisition function (xx)) to balance exploitation and exploration under the principle of optimism in the face of uncertainty. At the 1-th iteration of BO, the objective function is queried with a configuration I, and returns an output yr, a potentially noisy estimator of the objective function y/ f(x.) + e, NO0 o where of is the noise variance. The statistical surrogate is trained on the observed data up to t-th observation D.- = {1 B:) approximate the objective function. In this work, we use Gaussian process (GP) surrogate, which is query-efficient and gives analytic posterior mean and variance estimates on the unknown configurations. Formally, GP is denoted as f(x) ~ GP (m (z), k (z. z²)), where m (I) and i (x,x') are the mean function and the covariance function (or the kernel), respectively. While the mean function often set to zero or a simple function, the covariance function encodes our belief on the property of the function we would like to model, the choice of which is a crucial design decision when using GP. The covariance function typically has some kernel hyperparameters 0 and are typically optimised by maximising the -aggaaaaa

---

likelihood (the readers are referred to detailed derivations in Rasmussen [31]). With m(-) and k(--) defined, at iteration i, with X; = [_]] and the corresponding output vector Yı.-- = [Vi,-.. vrl" a GP gives analytic posterior mean ( (Dr) = ( X KT.y Le and variance k( 1 [Dr) = k( x1+11 - k( +1, X1:,) K
#(+1)) estimates on an unseen configuration 21++1, where [ (r)) is the (i, element of the Gram matrix induced on the (i, training samples by k(..)) :) the covariance function. With the posterior mean and variance predictions, the acquisition function is optimised at each iteration to recommend the configuration (or a batch of configurations for the case of batch BO) to be evaluated for the t + 1-th iteration. For
additional details of BO, the readers are referred to Frazier [15].
3 Bayesian Optimisation on Graphs
Problem setting. Formally, we consider a novel setup with graph G defined by (V, E), where V [w:} are the nodes and & fex 1h=1 are the edges where each edge eg (Uy, "g) connects nodes Uy and ty.. The topology G may be succinctly represented by an adjacency matrix A E {0. 1]"xx; in our case, and n are potentially large, and the overall topology is not necessarily fully revealed to the search algorithm at running time. It is worth noting that, for simplicity, we focus on the setup of undirected, unweighted graph where elements of A are binary and symmetrical (i.e. Aij = Aj:)². Specifically, we aim to optimise the black-box, typically expensive objective function that is defined over the nodes, i.c. it assigns a scalar value to each node in the graph. In other words, the search space (i.e. X' in $2) in our setup is the set of nodes V and the goal of the optimisation problem find the configuration(s) (i.e. æ in $2) that minimise the objective function
x² = arg mingev (v).
Promises and challenges of BO on graphs. We argue that BO is particularly appealing under the described setup as (1) it is known to be query-efficient, making it suitable for optimising expensive functions, and (2) is fully black-box and gradient- indeed, we often can only observe inputs and outputs of many real-world functions, and gradients may not even exist in a practical setup. However, there exist various challenges in our setup that make the adaptation of BO highly non-trivial, and despite the prevalence of problems that may be modelled as such and the successes of BO, it has not been extended to the optimisation of functions on graphs. Some examples of such challenges are:
(i) Exotic search space. BO is conventionally applied in continuous Euclidean spaces, whereas we focus on discrete graph search spaces. The differences in search space imply that key notions to BO, such as the similarity between two configurations and expected smoothness of objective functions (the latter is often used key criterion in selecting the covariance function to use), could differ significantly. For example, while comparing the similarity between two points in a Euclidean space requires only the computation of simple distance metrics (like f2 distance), careful thinking is required to achieve the same in comparing two nodes in a graph that additionally accounts for the topological properties of the graph.
(ii) Scalability, Real-world graphs such as citation and social networks can often feature a very large number of nodes while not presenting convenient properties such as the graph Cartesian product assumption in Oh et al. [27] accelerate computations. Therefore, it a technical challenge to adapt BO in this setting while still retaining computational tractability.
(iii Imperfect knowledge on the graph structure. Related to the previous point, it may also be prohibitively expensive or even impossible to obtain perfect, complete knowledge on roal-world graphs beforehand or at any point during optimisation (e.g. obtaining the full contact tracing graph for epidemiology modelling); as such, any prospective method should be able to handle the situation where the graph structure is only revealed incrementally, on-the-fly.
Overview of BayesOptG. To effectively address these challenges while retaining the desirable properties of BO, we propose to extend BÖ to this novel setup and are, to the best of our knowledge, the first to do so. To achieve that, we propose Bayesian Optimisation on Graphs, or BayesOptG in short, and illustration of the overall procedure is shown in Fig. 1, and an algorithmic description available in Algorithm I. For the rest of this section, we discuss in detail the key components of BayesOptG and how the method specifically addresses the challenges identified above.
"We note that it is possible to extend the proposed method to more complex cases by using the corresponding definitions of Laplacian matrix. We defer thorough analysis future work.
3

---

3.1
Kernels for BO on Graphs
Kernel design. Covariance functions are crucial to GP-based BO. To use BO in our setup, covariance function that gives a prin- cipled similarity measure between two nodes {v,, o S V is required to interpolate sig- nals the graph effectively. In this paper, we study several kernels, including both those proposed in the literature (e.g. the diffusion kernel on graphs and the graph Matérn ker- nel [4]) and two novel kernels designed by us. Following Smola & Kondor [37], all the kernels investigated can be considered in a general formulation. Formally, for generic graph G = (V, 8) with ñ nodes and m edges, we define L = D-D à AD $) where I AD-
Algorithm 1 Bayesian Optimisation
Graphs (BayesOprG)
1: Inputs: Number of random points at initialisa- tion/restart No. total number of iterations T, subgraph size Q, graph G = (V,E) (whose topology not necessarily fully known a-priori).
2: Objective: The node vyy that minimises the objective
function [(v), V.
3: Initialise restart_flas
True, visited nodes S + train data Du 0, h
4:
for I,..,, do do if ireatart_ffaa then Initialise the GP surrogate D, with randomly se- lected No points from V and their observations 6:
5:
D: (u.,
7:
end if
8:
Construct subgraph G. = (Vi, around eg (best node seen from the last restart) (See Algorithm 2 & $3.2).
is the identity matrix of order n, A and D are the adjacency matrix and the degree matrix known as
G, respectively (the term after the normalised Laplacian matrix with eigen-
9:
Fit a GP with kemel defined in Table 1 on G. with D, by optimising log- log-marginal likelihood. Select next query point 0i-1 by optimising the ac- quisition function.
10:
values in the range of [0, 2]: we scale it such that the eigenvalues are in the range of [0, 1).. is worth emphasising that here we use nota- tions with the tilde (e.g., G, ñ and m) to make the distinction that this graph is, in general, different from, and is typically a subgraph of, the overall graph G discussed at the start of this section, which might be too large or not be fully available at the start of the optimisation; we defer full discussion on this in $3.2. We further note that L UAUT with A diag( A1, .... Xa) and U = [ui,... unl. where {A1, Aa } are the eigenvalues of sorted in an ascending order and [u,,..., } are the corresponding (unit) eigenveetors.
11:
Query objective function f(-) ex-1 obtain (potentially noisy) estimate yt+11 update train data Di+1 + De U (V++1, Mc+1); )) seen nodes S + U vt+1: determine the state of aasart_ffag with
the criteria described in $3.2.
12: end for
13: return node that minimises f(.) from all restarts.
Let p, g E {.} be two indices over the nodes of G. we may express our covariance function to compute the covariance between an arbitrary pair of nodes Up Vy in terms of a regularisation function of eigenvalues r(,,)Vic (I,...,f,,,
jiJ, as described in Smola & Kondor [37]:
k(op, vz) = Σ r (A.)u
(I)
where u, [p[pp] and ug[g] are the p-th and q-th elements of the i-th eigenvector u, The specific functional form of r r(As) depends on the kernel choice, and the kernels considered in this work are listed in Table 1. We note that all kernels encode the smoothness of the function on the local subgraph G. In particular, the diffusion kernel has been adopted in Oh et al. [27]; the polynomial and Matérn kernels are inspired by recent work in the literature of graph signal processing 1, 46, 3]; finally, the sum-of-inverse polynomials kernel is designed as a variant of the polynomial kernel: in terms of the regularisation function, it can be interpreted as (while ignoring c) scaled harmonic mean of the different degree components of the polynomial kernel. We next discuss the behaviours of these kernels from the perspective of kernel hyperparameters.
Kernel hyperparameters. B := [Bu.... Sp-1]T E R%, (for polynomial and sum-of inverse polynomials) or [S1,..., BT]TT E R (for the diffusion kernel) define the characteristics of the kernel. We constrain /3 in both kernels to be non non-negative to ensure the positive semi-definiteness of the resulting covariance matrix and are learned jointly via GP log-marginal likelihood optimisation. The parameter v controls the mean-square differentiability in the classical GP literature with the Matérn kernel. The polynomial and the sum-of-inverse polynomials kernels in Table feature an additional hyperparameter of kernel order 17 E Ezo. We set it to be min diameter) where diameter is the
-um-of-inverse

---

Table 1: Kernels considered in terms of the regularisation function r(A.). We derive the semi- definiteness of polynomial and sum-of-inverse polynomial kernels in App. A.
Kernel
Regularisation function r(),) Kernel function ((V V)
Diffusion [37,27]
(xp(3,X,) Ex Pa +E
k- exp( - -3,1;) u
Polynomial"
Ei=1
Σ 1
Pads + i
-1
Sum-of-inverse
EaaD +r
E
EEa= Fu ?
polynomials
Matérn [4]
BB + 21
E
Bu + 21 y.u!
CCan be ARD or mon-ARD ARD: for ARD, {Be 12-1 cvefficients ure leurned; for non-ARD, a single, scalar 18 is learned.
*1 Ja-0 coelficients to be learned. small positive constant (e.g. 10-*). VE order of kernel.
length of the shortest path between the most distanced pair of nodes in G (a thorough ablation study on is presented in App. D.). We argue that this allows both kernels to strike a balance between expressiveness, as all eigenvalues contained in the graphs are used in full without truncation, and regularity, as fewer kernel hyperparameters need to be learned. This is in contrast to, for example, diffusion kernels on graphs in Table 1, which typically has to learn n hyperparameters for a graph of size î. whose optimisation can be prone to overfitting. To address this issue, previous works often had to resort to strong sparsity priors (e.g. horseshoe priors [6]) and approximately marginalising with Monte Carlo samplers that significantly increase the computational costs and reduce the scalability of the algorithm [27]. In contrast, by constraining the order of the polynomials to a smaller value, the resulting kernels may adapt to the behaviour of the target function and can be better regularised against overfitting in certain problems, as we will validate in $5.
3.2 Tractable Optimisation via Local Modelling
As discussed previously, it is technical chal- lenge to develop high-performing yet efficient methods in 1) large, real-world graphs (e.g. so- cial network graphs) and 2) graphs for which it is expensive, or even impossible, to obtain com- plete topological information beforehand (e.g. if model the interactions between individuals as a graph, the complete topology of the graph may only be obtained after exhaustive interviews and contact tracing with all people involved). The previous work in Oh et al. [27] cannot han- dle the second scenario and only addresses the first issue by assuming a certain structure of the graph (e.g. the Cartesian product of subgraphs), but these techniques are not applicable when we are dealing with a general graph G.
subgraph
Sutigaph
centro
subgrach
Suhgraph
contre
6,
of
Figure 2: Subgraphs G, determined by Algo- rithm 2, marked in red, with a darker shade de- noting closer distance to the central node uf = arg min f(u) in the figure, marked in black), for a high-degree node (Left) and a node far from high-degree node (Right). Note for the latter case, the local subgraph can include nodes that are much further away.
To address the dual challenges, and inspired by trust region-based BO methods [7, 13, 43, 10, 44), we adapt and simplify the techniques to our use case: we propose to leverage local modelling by focusing on a subset of nodes that evolves as the optimisation progresses. At iteration t {l,.... T]. assuming the collection of our observed configurations and outputs is D; = (vr, Ve } 11 we first find the node that leads to the best objective function so far of = arg min [v,
f()). We then use Algorithm 2 to select a neighbourhood around of that is a subgraph of the overall graph G: G C G with Q number of nodes (we will discuss how to choose Q in the next paragraph), in a procedure similar to the neighbourhood sampling in the GraphSAGE framework [18] as illustrated in Fig. 2: in particular, during sampling, the closer nodes to 2i takes precedence over further nodes we only sample the latter if the subgraph consisting of ef and the closer nodes has fewer than Q nodes; hence the local subgraph is a form of an ego-network of the central node vz. We then only impose the GP and compute the covariance matrix over this subgraph only: First, this effectively limits the computational cost note that the time complexity in our case depends on both the number of training examples N and the size of the graph ń we impose the GP on (O + N3)), assuming naive cigen-decomposition algorithm. Second, it also effectively addresses the setup where the
5

---

entire G' is not available a-prioni, as we only need to query and reveal the topological structure of the subgraph G, on the fly.
Determining the local subgraph size. The local sub- graph size iteration (Qt) is a hyperparameter of the algorithm. We adapt the idea of trust regions from trust region-based optimisation algorithms [7, 13, 43] adap- tively set the size of Qt as the optimisation progresses: specifically, we initialise Qo (initial neighbourhood size), pucc_tol (success tolerance), fail_tol (failure toler- ance) and y count "successes" as occasions where BayesOpiG suc- ceeds in improving the function values (i.e., at iteration t. f(ff) < f(uz-1) and "failures" otherwise. Upon con- secutive succ_tol successes, we expand the neighbour- hood size Q < min(roun((7Qe-1))
Algorithm 2 Selecting a local subgraph
I:
Inputs: Best input up to iteration t since the last restart: vi, subgraph size Q.
2: Output: local subgraph G. with Q nodes.
(multiplier) as hyperparameters', and
3: Initialise: D. (vi).
4: while [V.] < Q do
5: Find Ni. the h--hop neighbours of
of
6: if [2:++ + [.V s Q then
7: Add all h-hop neighbours to Ve:
to increase ex- ploration, and upon consecutive fail_ failures, we shrink Qr <- max Qt.1//1.. Qmin)) ) to increase ex- ploitation. The notation round(.) denotes rounding to the nearest integer, and Qmin denotes some minimum value of neighbourhood size (typically set to to include a single node e7 for simplicity, although alternative values may be used). When Qi S Quin- we restart the BO by fitting the surrogate with randomly initialised nodes whose objective function values have not been evaluated.
Vi - V. U.N-
8:
Increment ht h + h +
9:
else
10:
Randomly sample Q - 11/ nodes from Na and add to V.
11: end
12:
end while
13:
return the subgraph G. induced by V
(i.e. the ego-network).
Remarks on the relation to trust-region BO methods. It is worth noting that while conceptually influenced by previous trust region- -BO methods, the local graph construction we use differs from these methods in several crucial aspects. First, we use a bespoke distance metric in the graph space. Second, whereas the purpose of trust regions in previous works is to alleviate over-exploration in high-dimensional spaces, local subgraphs our case also uniquely serve the crucial purpose of allowing BayesOpiG to handle imperfect knowledge about the graphs, as we only need to reveal the topology of the subgraph (as opposed to the entire graph) at any given iteration. Lastly, we discussed, that using trust regions also improves scalability this can be concretely exemplified by the massive speed-up shown in Fig. 3.
Optimisation of the acquisition function. With the local subgraph obtained, we then fit GP surrogate with the covariance function de- fined in $3.1 and optimise log-marginal like-
Wall-clock time (s)
Poly
10²
Poly Full
Suminverse TR
Surinveese Full
lihood. Given that the local search space in our case is finite (of size Q), we simply enu- merate all nodes within G. to compute their acquisition function acq(-) values (which is computed from the predictive mean and vari- ance of the GP surrogate) and pick the max- imiser as the recommended location to query the objective function f(-) for iteration + 1 as V++1 arg max, acq(v). Any off-the-shelf acquisition function may be used, and we adopt expected improvement (EI) [16] in our experiments. It is worth noting that BayesOpiG also fully compatible with existing approaches such as Kriging believer fantasisation [17] for batch BO.
10a
Dif Full
1000
2000
3000
4000
Graph size
Figure 3: Trust regions enable efficient optimisa- tion on large graphs: Wall-clock time with and without trust regions in BayesOpiG with different kernels over graphs of different sizes.
Related Work
The setup we consider by itself novel and largely under-explored. One of the few existing methods that can be used for optimisation over graph search space is COMBO [27]. where the search space modelled as a graph that captures the relationship between different values for group of
We provide an ablation study in App. D show the robustness of BayesOptG hyperparameters.

---

(>)
14
8:55
1.0
040
8.5
6.6
03
1.0
040
6:38
1.
0.0
8.05
Pobrional
San Evein sabpara
Dilaarcc AMD
(b)
Vileedon
Vildedio
Figure 4: Validation of predictive powers of kernels considered on a BA graph of size 200 nodes and parameter m = I, with (a) function values on the nodes corresponding to elements of the eigenvector corresponding to the second smallest eigenvalue and (b) same as above, but corrupted with noise standard deviation o = 0.05. The leftmost column shows the visualisation of the ground truth, and the right columns show the GP posterior mean and standard deviation (error bars) learned by the different kernels against ground truth with Spearman correlation p and learned r (()) (Eq. 1).
categorical variables. It is, therefore, designed explicitly for combinatorial optimisation. Several studies modified COMBO in various ways but followed essentially the same framework for similar tasks, e.g., optimisation over categorical variables [12, 19, 24). Similarly, Ramachandram et al. [30] propose a specific graph construction to optimise multimodal fusion architectures. Our work differs from these studies in that: 1) focus on optimisation over generic, large-scale and potentially unknown graphs; 2) the nodes of the graph are not limited to combinations of values for categorical variables and can represent any entities; 3) the kernel we propose is not limited to diffusion- ones and can adapt to the behaviour of the function to be optimised. Finally, the graph bandit setting ([5, 39, 38]) can be seen be similar ours in the sense that also aims at finding extreme values associated with nodes in graph. However, the bandit problem considers a stochastic setting where nodes are influenced in a probabilistic fashion, and the objective function is actively shaped by this process; in comparison, in our case, we consider an underlying deterministic and black-box function, which is more aligned with the classical BO setting. Moreover, both Valko et al. [39] and Thaker et al. [38] require full graph access and require prohibitive operation on the full graph Laplacian dlecomppoittion/nvversioo
whereas BayesOpiG may work on-the-fly with initially unknown graphs and is much more scalable thanks to the designs in $3.2. Several works also leverage kernels on graphs to build Gaussian processes for graph-structure data [26, 41, 40, 46, 28, 4, 29]. While the kernels proposed in these approaches can, in theory, be used in BO framework, these studies do not address the optimisation problem we consider.
Another line of work focuses on optimisation over graph inputs (in contrast to graph search space) where each input configuration itself is graph. In contrast, in our case, each input configuration is a node. Examples of the former include Ru et al. [34] who model neural architectures as graphs and use Weisfeiler-Lehman kernels [36] perform BO, and Wan et al. [42]. who devise a BO agent for adversarial attack on graph classification models. Other representative examples include Kandasamy et al. [20], Korovina et al. [23] and Cui et al. [8, 9]. We emphasise that, while related, these works deal with different setup and thus require different method compared to the present work. For example, the kernels over graphs used in these methods typically aim to find vector embedding of graphs that account for their topologies. However, once the embedding is computed, standard Euclidean covariance functions (e.g.. the dot product or squared-exponentic kernel) are applied. On the other hand, in the present work, we aim to compute similarities over nodes, where topological information crucial during the covariance computation itself.
5 Experiments
We first validate the predictive power of the GPs with the adopted kernels on graphs and then demonstrate the optimisation performance of BayesOptG both synthetic and real-world tasks. We compare BayesOprG against basclines, including random and local search optimisation algorithms as
7

---

(a) Betweenness; m 2
(b) Betweenness; m=
(c) Betweenness; m
0.2
0.15
0.10
Regret
0.10
0.1
0.05
0.05
0.0
0.00
0.00
25
50
75
100
25
50
75
100
25
50
75
100
(d) Elgenvector: m=2
(e) Eigenvector:
(f) Eigenvector; m
0.3
0.4
Regret
0.2
0.2
0.0
0.0
25
50 #lters
100
25
50 #lters
25
75
#iters
BayesOptG Matern
BayesOptG Bayesopo@_Sanlhvvesee Sunnnverse
Local
BayesOptG Diff
BayesOptG_Pos
DFS
Random
BayesOptG DIR__AD
Figure 5: Maximising centrality scores with the BA random graph model and n = 1000 nodes. Different graphs show different values of the BA hyperparameter {2, 4] and centrality metrics (betweennessleigenveetoo centrality).
(a) Betweenness (k. = 010, 0.1)
Betweenness
Betweenness
Betweenness
(k, = (10, 0.2)
(k, 0.11
(k, = (30, 0.2)
0.006
0.004
0.002
Regret
0.004
0.001
0.002
50
100
50
100
50
100
50
100
(d) Eigenvector
(e) Eigenvector
(f) Eigenvector
[g] Eigenvector
p) = (10, 0.1)
p) = (10, 0.2)
(k, p) 030,
(k, p) = 030) 0.2)
0.015
0.015
0.006
0.006
Regret
0.010
0.004
0.005
0.005
0.002
0.002
0
50
100
0
50
100
50
100
0
50
100
eiters
#iters
#iters
lters
Figure 6: Maximising centrality scores with the WS random graph model and 2000 nodes. Refer to Fig. for legend and additional explanations.
well as BFS and DFS. The description of these baselines given in the App. B.2. In all figures, lines, and shades denote mean and standard error, respectively, across ten trials.
5.1 Validating Predictive Power of Kernels
We first validate the predictive power of the adopted kernels in controlled regression experiments. To do so, we generate functions that are simply the cigenvectors of the graph Laplacian and compare the predictive performance of the kernels using three graph types: 2D grid, Barabási-Albert (BA) [1] and Watts Strrogazz (WS) [45]. We compare the performance in terms of validation error and show the results in Fig. (results for other graph types are shown App. C.1). We find that in the noiseless case, all kernels learn the underlying function effectively (except that the diffusion with ARD kernel learns a non-smooth transform on the spectrum due to its over-parameterisation resulting in underestimations of the uncertainty in the noisy case). Still, the better-regularised kernels (described in $3. 1) are considerably more robust to noise corruption.
(a) Ackley: 0.5
(b) Ackley; a=1
(c) Rosenbrock; 0.5
(d) Rosenbrock; d=
Regret
1
10a
10"
50 #iters
100
50
100
50
100
50
100
Aiters
# liters
Witers
Figure Synthetic test functions task with Ackl e/koee//oosbb functions with noise standard deviation a E {0.5, 1}. Regrets shown in lcale for Rosenbrock; refer to Fig. 5 for legend.

---

(a): 18, v/ (0.1,
(b) (8. ( (0.1,0.15)
(c) (8. V (0.2.00015)
(d) (8. vI 0.15)
0.04
0.04
0.04
0.04
Regret
0.03
0.03
0.03
0.03
0.02
0.02
0.01
50 #ttees
100
0.01
50 eiters
100
100
0.01
100
eiters
#lters
BayesOptG Matem
BayesOptG Diff, ARD
BayesOptG Poly
BayesOptS, Diff
Local
Oate Sumliverse
DFS
Random
Figure 8: Identifying the patient zero task with different SIR model hyperparameters 3 (..1, and E (0.015, 0.15) and probability of recovery of O. Refer to Fig. 20 - 23 for experiments with other hyperparameter combinations.
(a) Enron Mail
(b) Facebook pages
Twitch social
0.04
0.100
0.03
Regret
0.03-
0.075
0.02
0.02
0.050
0.01
0.01
0.025
0
25
50
75
100
0
25
50
75
100
25
50
75
100
#iters
Figure 9: Identifying influential users in a social network task on different real-life social networks (Enron/Facebook page/Twitch). Refer to Fig. 8 for legend.
(a) #skills 2 and ==1
(b) #skills and a=1
(c) #skillss and =0
(d) #skills and a= 10
0.02
Regret
0.02
0.1
0.01
0.00
50
100
100
Niters
+lters
#lters
Figure 10: Team optimisation task with s (number of skills) E {2, 4} and a E 10) with Jaccard index threshold of 0.3 (refer App. B.4.3 for explanations). Refer to Fig. for legend and Fig. 24- 26 for experiments with other hyperparameter combinations.
5.2 Optimisation Tasks
We conduct experiments on a number of synthetic and real-life tasks that involve or imitate expensive optimisation, and we show all results in terms of simple regret (i.e.. the difference between the objective function value and the ground-truth optimum). We consider the following synthetic tasks:
Maximising centrality scores (Fig. 5 and 6; Fig. 18 in App. C.2): aim find the node with maximum centrality measure, from a graph sampled from random graph model. We consider both eigenvector centrality and betweenness centrality as the centrality metrics, and use BA and WS with different hyperparameters as the random graph-generating models. We consider graphs with sizes in the range of 10st in Fig. 5 and In Fig. 18, further scale the size of graphs considered 10th nodes to demonstrate the scalability of our method in a large-scale setup.
Synthetic test functions (Fig. 7): we optimise suite of discretised versions of commonly used synthetic test functions (Ackley and Rosenbrock) on graphs defined as a 2D-grid in both noiseless and noisy setups. The readers referred App. B.3.2 for additional implementation details.
We consider the following real-life tasks:
Identifying the patient zero (Fig. 8; Fig. 20 to 23 in App. C.3): we aim to find the "patient zero" of an epidemic in a contact network, who is the person identified as the first carrier of communicable disease in an epidemic outbreak. We use real-world contact network based on Bluetooth proximity [2], and on top of simulating the epidemic process using the SIR model, the canonical compartmental model in epidemiology [22]. The function values are the time instants when an individual is infected; the readers are referred to App. B.4.1 for more details of this task.
Identifying influential users in social network (Fig. 9): we aim to find the most influential user in a social network. There are multiple ways of defining the influence power of a user, and for simplicity, we follow the common practice of taking node degree as proxy of influence [21]. We

---

use three real-world networks, namely the Enron email network [25], Facebook page network [33], and Twitch social network [32]. The readers are referred to App. B.4.2 for more details.
Team optimisation (Fig. 10; Fig. 24 to 26 in App. C.4): we design a task of optimising team structure, where the objective is to find a team that contains members who are experts in different skills, and their collective expertise represents a diverse skill set. In this case, the teams are modelled as nodes, and edges represent the a priori similarity between teams. While there are various possible ways to model these similarities, in our experiment, we consider that an edge exists between two nodes if the Jaccard index between the two sets of team members is greater than a certain threshold. We include additional details and a formal description of the objective function in the App. B.4.3.
We designed these tasks to imitate expensive but realistic black-box optimisation problems on which the use of Bayesian optimisation is ideal. For example, the identifying patient zero task imitates real-life contact tracing. If executed in real life, each function evaluation requires expensive and potentially disruptive procedures like interviews about the individuals' travel history and the people they were in contact with. On the other hand, the centrality maximisation & identifving inftuential social network users problems mirror common online advertising tasks to identify the influential users without access to the full social network information (which would be near-impossible to obtain given the number of users). Real-life social media often limits how much one may interact with their platform through pay-per-use APIS or hard limits (e.g. upper limit of views). In either case, there is a strong reason to identify the influential users in the most query-efficient manner.
Discussions. In addition to the task-specific results, we further aggregate the performance of the different methods over all tasks in terms of relative ranking in Fig. 11. We find that within individual tasks and ag- gregated across the different tasks, BayesOprG with any kernel choice generally outperforms all baselines in terms of efficiency, final converged values, both. Specifically, Random is simple but typically weak for larger graphs, except for very rough/noisy functions (like Ackley), or the variation in function values is generally small; DFS and BFS are relatively weak as they consider graph topology information only but not the node information (on which the objective function is defined) and can be sensitive to initial- isation; Local search is, on balance, the strongest baseline, and it does particularly well on smoother functions with fewer local minima.
7-
Rank
4-
20
40
80
100
#iters
BF5
BayesOptG Suminverse
BayesOptG Diff
DFS
BayesOptG Dif ARD
Local
BayesbptG, Matern
Random
BayesOptG Poly
Aggregated ranks of the methods (lower is better) vs. the number of evaluations averaged across all experiments.
Figure 11:
As is the case for any GP-based method, the kernel choice impacts the performance, and the performance is stronger when the underlying assumptions of the kernel match the actual objective function. For example, diffusion kernels work well for patient zero identification (Fig. 8) and team optimisation (Fig. 10), the underlying generative functions for both problems, are indeed smooth (in fact, the SIR model in disease propagation is heavily connected to diffusion processes). Diffussoo without ARD further enforces isotropy, assuming the diffusion coefficient in all directions is the same, and thus typically underperforms except for team optimisation, where the generated graph is well structured and Ackley, which is indeed isotropic and symmetric. We recommend only if we know that the underlying function satisfies its rather stringent assumptions. Finally, the SumInverse and DiffARD kernels are generally better, as they offer more flexibility in learning from the data; we recommend using one of these as default without prior knowledge suggesting otherwise.
6 Conclusion
We address the problem of optimising over functions on graphs, a hitherto under- indet-investigated problem. We demonstrate that BO, combined with learned kernels on graphs and efficient local modelling, provides an effective solution. The proposed framework works with generic, large-scale and potentially unknown graphs, setting that existing BO methods cannot handle. Results on a diverse range of tasks support the effectiveness of the proposed method. The current work, however, only considers the case where the optimisation over nodes; possible future works include extensions to related settings, such as optimising over functions defined on edges and/or on hypergraphs.
10

---

Acknowledgement
The authors would like to acknowledge the following sources of funding in direct support this work: X. W. is supported by the Clarendon Scholarship at University of Oxford: P.O. is supported by the EPSRC Centre for Doctoral Training in Autonomous Intelligent Machines and Systems EP/L015897/1; X.D. acknowledges support from the Oxford-Man Institute of Quantitative Finance and the EPSRC (EP/T023333/1). The authors declare no conflict of interest.
References
[1] Barabási, A.-L. and Albert, R. Emergence of scaling in random networks. science, 286(5439): 509-512, 1999.
[2] Barrat, A., Cattuto, C., Kivelä, M., Lehmann, S., and Saramäki, J. Effect of manual and digital contact tracing on covid-19 outbreaks: a study on empirical contact data. Journal of the Royal Society Interfuce, 18(178):2020100) 2021.
[3] Borovitskiy, V., Azangulov, I., Terenin, A., Mostowsky, P., Deisenroth, M., and Durrande, N. Matérn gaussian processes graphs. In International Conference on Artificial Intelligence and Statistics, pp. 2593 2601. PMLR, 2021.
[4] Borovitskiy, V., Azangulov, I., Terenin, A., Mostowsky, P., Deisenroth, M. P., and Durrande, N. Matern Gaussian processes graphs. In International Conference on Artificial Intelligence and Statistics, 2021.
[5] Carpentier, A. and Valko, M. Revealing graph bandits for maximizing local influence. In International Conference on Artificial Intelligence and Statistics, 2016.
[6] Carvalho, C. M., Polson, N. G., and Scott, G. Handling sparsity via the horseshoe. In Artificial Intelligence and Statistics, pp. 73-80. PMLR, 2009.
[7] Conn, R., Gould, I., and Toint, L. Trust region methods. SIAM, 2000.
[8] Cui, J., Yang, B., and Hu, X. Deep bayesian optimization on attributed graphs. Proceedings of the AAAI Conference Artificial Intelligence, 2019.
[9] Cui, J., Tan, Q., Zhang, C., and Yang. B. A novel framework of graph bayesian optimization and its applications to real-world network analysis. Expert Systems with Applications, 170 (114524), 2021.
[10] Daulton, S., Eriksson, D., Balandat, M., and Bakshy, E. Multi-ohjective bayesian optimization over high-dimensional search spaces. In Uncertainty in Artificial Intelligence, pp. 507-517. PMLR, 2022.
[11] Defferrard, M., Bresson, X., and Vandergheynst, Convolutional neural networks on graphs with fast localized spectral filtering. Advances neural information processing systems, 29, 2016.
[12] Deshwal, A., Belakaria, S., and Doppa, J. R. Mercer Features for Efficient Combinatorial Bayesian Optimization. AAAI Conference on Artificial Intelligence, 2021.
[13] 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.
[14] Even, S. Graph algorithms. Cambridge University Press, 2011.
[15] Frazier, P. I. A tutorial on bayesian optimization. arXiv preprint arXiv: 2018.
[16] Garnett, R. Bayesian Optimization. Cambridge University Press, 2023.
[17] Ginshourger, D., Le Riche, R., and Carraro, Kriging well-suited to parallelize optimization. Computational intelligence in expensive optimization problems, pp. 131-162, 2010.

---

[18]
Hamilton, W., Ying, Z., and Leskovec, J. Inductive representation learning on large graphs. Advances neural information processing systems, 30, 2017.
[19] 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, 2022.
[20] Kandasamy, K., Neiswanger, W. Schneider, J., Poczos, B., and Xing, E. P. Neural architecture search with Bayesian optimisation and optimal transport. In Advances in Neural Information Processing Systems (NIPS), pp. 2016-2023 2018.
[21] Kempe, D., Kleinberg, J., and Tardos, É. Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 137-146, 2003.
[22] Kermack, W. O. and McKendrick, A. G. A contribution to the mathematical theory of epidemics. Proceedings of the royal society of london. Series A, Containing papers of a mathematical and physical character, 115(772):700-721 1927.
[23] Korovina, K., Xu, S., Kandasamy, K., Neiswanger, W., Poczos, B., Schneider, J., and Xing, P. Chembo: Bayesian optimization of small organic molecules with synthesizable recommenda- tions. In Artificial Intelligence and Statistics, 2020.
[24] Krummenauer, J., Kammoun, N., Stein, B., and Goetze, J. Encoding categorical variables in Mhysies-informed graphs for Bayesian Optimization. International Conference on Omni-layer Intelligent Systems, 2022.
[25] Leskovec, J., Lang, K. J., Dasgupta, A., and Mahoney, M. W. Community structure in large net- works: Natural cluster sizes and the absence of large well-defined clusters. Internet Mathematics, 6(1):29-123, 2009.
[26] Ng. Y. C., Colombo, N., and Silva, R. Bayesian semi-supervised learning with graph Gaussian processes. In Conference Neural Information Processing Systems, 2018.
[27] Oh, C., Tomezak, M., Gavves, E., and Welling, M. Combinatorial Bayesian Optimization using the Graph Cartesian Product. In Conference on Neural Information Processing Systems, 2019.
[28] Opolka, L. and Liò, P. Graph convolutional Gaussian processes for link prediction. In ICML Workshop on Graph Representation Learning and Beyond, 2020.
[29] Opolka, F. L., Zhi, Y.-C., Lió, P., and Dong, X. Adaptive gaussian processes on graphs via spectral graph wavelets. In International Conference on Artificial Intelligence and Statistics, 2022.
[30] Ramachandram, D., Lisicki, M., Shields, T.J., Amer, M. R., and Taylor, G. W. Bayesian opti- mization on graph- struuuutrut search spaces: Optimizing deep multimodal fusion architectures. Neurocomputing, 298:80-88 89, 2018.
[31] Rasmussen, C. E. Gaussian processes in machine learning. Springer, 2004.
[32] Rozemberczki, B., Allen, C., and Sarkar, R. Multi-scale attributed node embedding, 2019.
[33] Rozemberczki, B., Davies, R., Sarkar, R., and Sutton, C. Gemsee: Graph embedding with self clustering. In Proceedings of the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2019, pp. 65-72. ACM, 2019.
[34] Ru, B., Wan, X., Dong, X., and Osbore,, M. Interpretable neural architecture search via bayesian optimisation with weisfeiler-lehman kernels. International Conference on Learning Representations (ICLR), 2021.
[35] Sapiezynski, P., Stopezynski, A., Lassen, D. D., and Lehmann, S. Interaction data from the copenhagen networks study. Scientific Data, 6(1):1-10, 2019.
12

---

[36] Shervashidze, N., Schweitzer, P., Van Leeuwen, E. J., Mchlhorn, K., and Borgwardt, K. M. leimaan graph kemeess. Journal of Machine Learning Research, 12(9), 2011.
[37] Smola, A. and Kondor, R. Kernels and regularization on graphs. In Learning theory and kernel machines, pp. 144-158. Springer, 2003.
[38] Thaker, P., Malu, M., Rao, N., and Dasarathy, G. Maximizing and satisficing in multi-armed bandits with graph information. Advances in Neural Information Processing Systems, 35: 2019-208 2032, 2022.
[39] Valko, M., Munos, R., Kveton, B., and Kocák, T. Spectral bandits for smooth graph functions. In International Conference on Machine Learning, pp. 46-54. PMLR, 2014.
[40] Venkitaraman, A., Chatterjee, S., and Handel, P. Gaussian processes over graphs. In IEEE International Conference on Acoustics, Speech and Signal Processing, 2020.
[41] Walker, and Glocker, Graph convolutional Gaussian processes. International Conference on Machine Learning. 2019.
[42] Wan, X., Kenlay, H., Ru, B., Blaas, A., Osborne, M. A., and Dong, X. Adversarial attacks on graph classifiers via bayesian optimisation. Conference on Neural Information Processing Systems, 2021.
[43] 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. International Conference on Machine Learning (ICML), 2021.
[44] Wan, X., Lu, C.,, Parker-Holder, J., Ball, J., Nguyen, V., Ru, B., and Oshorne, M. Bayesian generational population- training. In First Conference on Automated Machine Learning (Main Track), 2022.
[45] Watts, D. J. and Strogatz, H. Collective dynamics of 'small-world" networks. Nature, 393 (6684):440-444) 1998.
[46] Zhi, Y.-C., Ng. Y. C., and Dong, X. Gaussian processes graphs via spectral kernel learning. IEEE Transactions on Signal and Information Processing over Networks, 2023.
13

---

A Proof of Semi-Defiittnesss
In this section, show that all kernels considered in this paper positive semi-definite (p.s.d). Specifically, we note that using the terminology defined Eq. 1, any map r - IR + [0, +oo] defines valid covariance kernel. Indeed,
VX XXV,
where u, [X] [u,(21] u/ [22] ...,, u. [z:]] with | The matrix un [ symmetric
p.s.d as the outer product of one non-zero vector: VX E R x [ X x = || [|] 2 As result, our covariance matrix symmetric p.s.d as the weighted sum of symmetric positive semidefinite matrices with positive coefficients. The kernels we presented in this paper correspond to positive r; hence, they are all p.s.d.
B Experimental Details
B.1 Random Graph Models
Barabási-Albert model (BA). The network begins with an initial connected network of mo nodes. New nodes are added to the network one a time. Each new node connected to S mg existing nodes with probability that is proportional to the number of links that the existing nodes already have, The probability p; that the new node is connected to node is:
K;
Pt
Σ kg
where kj is the degree of node j.
Watts- model (WS). The WS model was introduced explain the "small-world" phenomena in variety of networks. It achieves this by interpolating between a randomized structure close to ER graphs and a regular ring lattice. Given mean degree K and a parameter / E [0, 1]. An undirected graph is constructed with N nodes and K edges as follows:
1. Constructs a regular one-dimensional network with only local connections of range K, meaning each node is connected to its K/2 nearest neighbours on each side.
2. For every node 0, - take every edge connecting to K K/2 rightmost neighbours. Rewire each of these edges with probability 3 to random nodes while avoiding self-loop and link duplicates.
B.2 Baseline Algorithms
Breadth first search (BFS) and depth-first search (DFS). These algorithms aim to explore the whole graph data structure. starts with a root node and explores according the depth breadth of the graph. In the former, the algorithm explores as far as possible along each branch before backtracking, In the latter, the algorithm explores all nodes at the present depth prior moving on to the nodes at the next depth level.
Random search. In this algorithm, at each time step, random node is selected for evaluation of our objective function.
Local search. In this algorithm, at each time step. we sample and query random node from neighbour node the maximum value encountered so far, and we move to neighbour node the queried value is better than the incumbent best. When the algorithm reaches local optimum (i.e., all neighbours have worse values than the current optimum), we allow our algorithm restart at random, unvisited node in the graph.
14

---

Figure
Betweeness/Figeeveooor Centrality on BA/WS graphs.
B.3 Synthetic Optimisation Tasks
B.3.1 Maximising network centrality
Centrality measures were introduced in network analysis study the importance of certain vertices with respect to desired characteristics. In this paper, we used two centrality measures: betweenness centrality and eigenvalue centrality. We show examples of these functions sample BA/WS graphs in Fig. 12.
Betweenness centrality. This centrality focuses not just on overall connectedness but on the occupying positions that are pivotal the network's connectivity. The following formula gives the betweenness of node ::
ssa(v)
g(u)
Σ
Ost
S.EV (b) sgft
where ose is the total number of shortest paths from node node and (=)(v) is the number of those paths that pass through v. V denotes the set of neighbouring nodes of v except the node itself.
Eigenvector centrality. This centrality measure accounts for the influence a particular node within the network. The centrality score for the whole set of vertices, represented vector x, is solution to the equation:
Ax Ax;
where the matrix A represents the adjacency matrix and À represents the largest eigenvalue of the adjacency matrix.
B.3.2 Synthetic test functions
In this subsection, we describe the Rosenbrock and Ackley test functions used for our task, both of which are discretised versions of their original, continuous function forms. The mathematical definitions of test functions are listed below and are visualized Fig. 13.
Rosenbrock function.
f(x, 100(y x2)2 (a 1)2
Ackley function.
f(,,v) = -20 ( 0.2 0.5(1/0.22 + y2)) exp (- 0.5(cos 2m + cos 2mry) + 20 + exp(1)
Additive noise. In order to alter the smoothness property of our graph signal defined over the grid, we add random noise governed by noise standard deviation on to be added to the loss function f(r y) = fxx y) e with (0, a)). In our experiment, we vary the noise standard deviation on E (0,0.1, 1,5) for the Ackley function and o, e {0, 0.5, 1) for the Rosenbrock function.
15

---

Figure 13: Test function values taken on a regular graph corresponding to the input space: Rosenbrock
(left); Ackley (right).
Figure 14: Simulation of the SIR process on BA/WS graphs. It worth noting that some local optima visible due to the parameter.
B.4
Roal-World Optimisation Tasks
B.4.1 Finding patient in contact network
In this task, simulate the diffusion processes over graph via epidemics SIR models Kermack & McKendrick [22]. We slightly modify this model to allow for parameter representing the probability of spontaneous infection from unknown factors.
More formally, given a graph G = EV, our model has three parameters. Parameter 3 encodes the probability of infection, the probability of recovery the probability of spontaneous infection, and 7 the time spent since the beginning of the outbreak. Let time = 1,...? be the current time, X,, (T, R) the node status (Infected, Susceptible, Recovered) and S1 Sg,t, SR, the set of nodes in each category at time t. We have:
[P(x R] =
Vu S1 P|xxo,111 I]
(3)
7.
P[x,111 = 1 = =1 1- (1 - c) x (1- -1- (
Yo E S8,6 [Pxx,,111 = 51 = (1- - x (1 (
(4)
Vo E E....
P(xx,,--1 S
= R| 11
(5)
Given such a process, we construct an objective function indicating how close a certain node is to the source of the infection as follows. At time T', where we consider the diffusion have ended (or corresponding to the present moment when looking for patient zero), for every node in SR UST we denote by Tu the first time of infection. The objective function is then defined as:
0 { 11-100 7)2
if E SS.T
Vo f()())
(6)
if E Sr, U
This function takes value in [0, and is maximised when the node corresponds to the patient zero. We expect local methods to perform well in this setting as local behaviour can trace the source of the infection through diffusion, and the variation of the functions on the graph relatively smooth. The introduction of parameter nevertheless adds some sources of "local" minima in the graph objective function we show some examples of such phenomenon in Fig. 14, where we give exemplary graph signals induced by the generative process described in this section.
16

---

B.4.2 Finding influential users in a social network
In this task, we consider common problem in identifying the most influential person within social network. Influence, in this context, is often quantified approximately using degree centrality, which may account for, for example, the number of followers connections an individual possesses. However, the enormity social network graphs often restricts our access to complete graph infor- mation, necessitating alternative search approaches. To validate methodology, conduct tests on various real-world graphs derived from diverse social networks. These include the Enron email network, which represents email communication between members of corporation; the Facebook page network, which is network of interconnected Facehook pages; and the Twitch social network, which provides insight into the relationships among users on the Twitch platform.
B.4.3 Team optimisation
In this task, aim tackle the problem of optimising the performance of a team of individuals with different skills. We will assume that team would perform most effectively when all skills are covered by combining individual skills and 2) some individuals master every skill. More formally, we will consider a pool of N individuals. Each individual can be represented by a vector of skills x; E [o, 1]K where K is the number of skills. This setup fits our framework well in the scenario where the skills of individuals are unknown, and the pool of potential candidates is also unknown in advance. A sample graph generated from this problem shown Fig. 15.
Figure 15: An exemplary graph in- duced from the team optimisation problem.
Skill generative process. each experiment, we will assume individual skills to be generated according to Dirichlet distri- bution with parameter a:
Dir(a), a = =[aa...,.pp
The parameter encodes the sparsity of skill expertise in the general population. Small generates individuals with specialised skills with more probability than large a where all skill levels concentrate to score of 0.5.
Graph construction. To solve this task and allow flexible exploration of teams with varying number of individuals, we construct graph where nodes represent teams and edges are based on the Jaccard index between each pair of team member sets. More specifically, given two teams 81 C N Given N teams, we can
and C N the similarity between them is computed as w(81,82) 5y
#1Uss
then construet an undirected graph with edges:
1 82
[N], (81, E E + w(81,82) Median( (w(s1, 82) 82 C [N]])
Objective function. To model the two desirable properties in terms of team composition, we choose the following objective function:
Ys C [N] f(x) = H&
[H+[]]]
Intuitively, the first term the objective corresponds to the entropy the skill distribution of the whole team, which maximised when the skill distribution is close to the uniform distribution. The second term corresponds to the expected entropy of the distribution of skills of each individual, which is minimised (and the objective maximised) when each individual specialises in one skill. As result, we can expect this objective to be well suited for modelling an ideal composition of team.
C
Additional Experiments
C.1 Kernel Validation
Complementary to Fig. in the main text, we conduct further regression analyses to confirm the expressive power of the investigated kernels. The results are shown in Fig. 16 and Fig. 17.
17

---

Popprril
See of lame prieneal
IiFaiinn a ARp
Ve seln preed out
Vildeia gardiass
Viddede arard 29r3
Viliddn pood
040
150
100
010
Onfacr
(6)
Figure 16: Expressiveness of kernels on grid graph of size n = 200 nodes. Refer to Fig. for more explanations.
Polyooiill
Sun Keeiss adysonia
Budis
(a)
0.4
0.00 0.4
Poly Semial
Sum lnvida sobavenil
Diituaion With AND
(b)
grauid back
pooud
04
12
Figure 17: Expressiveness of kernels on WS graph size n 200 nodes. Refer to Fig. 4 for more explanations.
C.2 Centrality Maximisation on Large Graphs
In this section, we consider a similar problem of centrality maximisation as described in App. B.3.1, but on significantly larger graphs: we use BA and WS random graph generators similar to the experiments in Fig. 5 and Fig. 6 in the main text, but we generate graphs with 10t nodes instead and increase the query budget. We show the results in Fig. 18, and we find that the superiority of BayesOprG methods persists in this setting over the baseline methods.
C.3 Finding Patient Zero Task Real-World Graphs
Setup. In this section, we consider several SIR diffusion problems as described in App. B.4.1 where we aim to find the patient zero on real-world interaction network from the Copenhagen Networks Study [35]. This network represents physical proximity among participants (estimated via Bluetooth signal strength) in population of more than 700 university students and thus is good testbed to examine the diffusion process of hypothetical epidemic outbreak. The visualization of the function on this graph is given by Fig. 19.
18

---

(a) Ackley;
Ackley; o= 0.1.1
(c) Rosenbrock;
(d) Rosenbrock; 0
101
10
Regret
10-2
10
10
10
109
10
10-7
1000
2000
3000
2000
4000
2000
4000 6000
2000
4000
(e) BA
(f) BA
(g) WS Degree centrality: (k,p) (30, 0.1)
(h) WS
Degree centrality:
Degree centrality:
Degree centrality: (k,p) (30, 0.2)
=
10-3
10
10
Regret
6 x 10-
10-5
40
xx
10-6
1000
2000
1000
2000
2000 #lters
4000
2000
4000
elters
#lters
BFS
BayesOptG, DRR[_ARD
BayesOptG Suminverse
BayesOptG Diff
BayesOptG Poly
DFS
Random
Figure 18: Maximising centrality scores with the BA/WS random graph model and n 10 nodes.
Figure 19: Diffusion objective function on the real-world interaction network.
Results. The performance of each algorithm is presented Fig. 20 23 where we use different values of initially infected population fraction and probability of recovery it is clear that due the increased complexity as revealed in Fig. 19, there some performance degradation in all algorithms considered. However, search baseline.
that in most cases, method performs at least well the local
C.4 Team Optimisation
We show additional results for the team optimisation tasks in Fig. 24 to 26. We can observe that the key findings from the main text this problem (Fig. 10) largely hold true for these tasks induced by different parameters.
D Ablation and Sensitivity Studies
In this section, we perform a thorough ablation and sensitivity study how much the additionally introduced hyperparameters affect the algorithm's performance. We report sensitivity analyses
to the most important hyperparameters below, namely Qo (initial trust region size), fail_tol,
19

---

(a) [B. y) = (0.1, 0.005)
(b) () (0.1, 0.015)
(c) (B. V) = (0.11 0.15)
0.06
0.06
Regret
0.2
0.04
0.04
0.1
0.02
0.02
0
50
100
50
100
0
50
100
(d) (B. y) (0 2.2.2..000 0.005)
(e) (B. V) = 10.22000115
(f) [B. y) (0 O 0.15)
0.06
0.06
0.2
Regret
0.04
0.04
0.02
0.02
0.1
50
100
50
100
50
100
(g) (B, y) 0.005)
(h) (B. y) (0.3, 0.015)
(B. y) (0.3, 0.15)
0.10
0.10
0.04
Regret
0.02
100
50 #iters
100
#iters
Iters
BFS
BayesOptG_ MMatem BayesOptG_Pood
BayesOptG_Summ Suullnverseeeeeeee
Local
BayesOptG Diff
DFS
Random
BayesOptG Diff Dif____iDDDDDD ARD
Figure 20: Identifying the patient zero task with different SIR model hyperparameters 3 E {0.1, 0.2, 0.3) and y E (0.005, 0.015, A fraction of 0.0003 of initial population was infected initially. The probability of recovery is set to O.
(order of the kernels) and y (the trust region multiplier in case of successive successes or failures). We also additionally study the effect of introducing the trust region in this section. We perform ablation experiments in the setting with BA graphs and synthetic function optimization. We show the sensitivity analysis in Fig. 27 to 29 it is evident that our algorithm is largely robust to the choice of hyperparameters as long as a value within a sensible range chosen.
Use of trust regions. We compared, on some relatively small graphs (1000 nodes) in Fig. 31 as observed, while there a small drop in performance because of the use of local modelling compared to constructing surrogate model on the whole graph, it is worth noting that, as shown in Fig. 3 in the main text, the full Bayesian optimisation procedure with kernels defined on the whole graph becomes too prohibitive, even for relatively small graph of size 1000, and that when the graph unknown, impossible in the first place to construct a whole-graph GP. This verifies that the trust region strikes promising balance between efficiency and performance.
20

---

(a) (B, y) (0.1, 0.005)
(b) (B. v = (0.1, 0.015)
(c) (B. y) = (0.1, 0.15)
10
Regret
10
10
50
100
0
50
100
50
100
(d) (8. 0.005)
(e) (8. y) (0.2. 0.015)
(f) (B. 1) (0.2, 0.15)
Regret
10-2
10-2
50
100
50
100
50
100
(g) (B. y) (0.3, 0.005)
(h) (B. y) = (0.3, 0.015)
(i) (B. y) (0.3,0.15)
10-1
10-1
Regret
10-2
10
10
100
100
100
#iters
#iters
# #ters
BFS
BayesOptG Matem
Sesespptt_Sumlvverse
Local
BayesOptG_ Diff BayesOptG_DDee LaffGG_iff_RRD ARD
BayesOptG_Poojy
DFS
Random
Figure 21: Identifying the patient task with different SIR model hyperparameters 3 (0.1, 0.2, 0.3) and E (0.005, 2.115,0.15) A fraction of 0.0003 of the initial population was infected initially. The probability of recovery is set to 0.005.
21

---

(a) (B. y) (0.1, 0.005)
(b) (B, V\ = (0.1, 0.015)
(c) (8. y) = (0.1, 0.15)
Regret
10-2
10-2
50
100
50
100
50
100
(d) (8. (0.2, 0.005)
(e) (B. y) (0.2, 0.015)
(f) (B. y) (0.2, 0.15)
3
3 10-2
-0-2
10-2
10-2
Regret
4 40
10
10
3 10
6 10
6x
2x
50
100
50
100
50
100
(g) (B. y) (0.3, 0.005)
(h) (B. y) = (0.3, 0.015)
(i) (B. y) (0.3, 0.15)
Regret
10-2
10-2.
10
100
100
100
#iters
#iters
Iters
BFS
BayesOptG Matem
SeeeoOptt_SSmllversse
Local
BayesOptG_ Diff BayesOptt_DDie Diff ARD
BayesOptG_Poojy
DFS
Random
Figure 22: Identifying the patient task with different SIR model hyperparameters 3 (0.1, 0.2, 0.3) and & E (0.005, 0.015, 0.15. A fraction of 0.003 the initial population was infected initially. The probability of recovery set to 0.
22

---

(a) (8. y (0.1, 0.005)
(b) (B. y) = (0.1, 0.015)
(c) (B. y) (0.1, 0.15)
40
3x
Regret
2x10
10-2
10-2
10-2.
6 10-3
50
100
50
100
50
100
(d) (B. y) (0.2, 0.005)
(e) (B. y) (0.2. 0.015)
(f) (8. 0.15.
Regret
10-2
10-2
10-2.
50
100
50
100
50
100
(g) (B. v (0.3, 0.005)
(h) (B. v) = (0.3, 0.015)
(8. y) (0.3, 0.15)
10-2
Regret
10-2
10-4
10-2
10-6
100
50
100
50 #iters
100
Iters
iters
BFS
BayesOptG Matem BayesOptG_Poojy
SesssppttSSummvverse
Local
BayesOptG_ Diff
DFS
Random
BayesOptt_ Diff Diff__ARt ARD
Figure 23: Identifying the patient task with different SIR model hyperparameters 3 (0.1, 0.2, 0.3) and y E (0.005, 0.015, 0.15.. A fraction of 0.003 the initial population was infected initially. The probability of recovery is set to 0.005.
23

---

(a) #skills 2 and a= 0.1 (b) #skills and 0.1
(c) #skills 8 and = 0.1
0.15
Regret
0.05
0.1-
0.10
0.05
0.00
0.0
50
100
0
50
100
50
100
(d) #skills = 2 and a =
0.16e)
#skills = 4 and a=1
(f)
#skills = 8 and a a=1
0.075
0.15
Regret
0.10
0.050
0.05
0.05
0.025
50
100
0
50
100
50
100
0.0g))
# #skills
2 and
10
(h) #skills 4 and a
10
#skills = 8 and a 10
0.02
0.015
Regret
0.010
0.02
0.01
0.005
50 #lters
100
50 #lters
100
100
#iters
BFS
BayesOptG Matern
Local Random
BayesOptG Diff BayesOptG ARD
BayesOptt_Poon Poly
DFS
Figure 24: Team optimisation task with (2,4) and {1, with Jaccard index threshold of
0.1 (refer App. B.4.3 for explanations)
(a) #skills 2 and 0.1 (b) #skills and 0.1
(c) #skills 8 and 0.1
Regret
0.05
0.1
0.1
0.00
0.0
0.0
50
100
50
100
50
100
(d) #skills and =
0.10 ()) #skills = 4 and =1
(f) #skills = 8 and =
0.15
Regret
0.05
0.10
0.05
0.05
0.00
0.00
100
100
50
100
0g)
# #skills = and = 10
o.o0h)
(h) #skills = 4 and == 10
(i) #skills = 8 and = 10
Regret
0.01
0.02
0.01
0.00
0.00
100
100
50 #lters
100
#iters
#iters
BFS
BayesOptG Matern BayesOptG Poly
Sumlnverse
Local Random
BayesOptG Diff BayesOptG Diff ARD
DFS
Figure 25: Team optimisation task with (2,4) and {1,10) with Jaccard index threshold of
0.2 (refer App. B.4.3 for explanations)

---

(a) #skills 2 and a= 0.1
(b) #skills and a 0.1
(c) #skills 8 and 0.1
Regret
0.05
0.1
0.1
0.00
0.0
0.0
50
100
50
100
0
50
100
(d) #skills 2 and
0.1de)
(e) #skills 4 and = 1
(f) #skills = 8 and = 1
Regret
0.1
0.05
0.05
0.00
0.00
100
100
50
100
(g)
#skills = and = 10
o.02h)
(h) #skills = 4 and a = 10
(i) #skills = 8 and = 10
0.04
Regret
0.01
0.02
0.01
0.00
0.00
0.00
100
100
50 #lters
100
#iters
#iters
BFS
BayesOptG Matern BayesOptG_Poly
Local Random
BayesOptG Diff BayesOptG Diff ARD
DFS
Figure 26: Team optimisation task with (2,4) and a E {1) with Jaccard index threshold of 0.3 (refer App. B.4.3 for explanations)
25

---

Enron
Facebook
Twitch
0.100
Paly
Regret
0.03
0.075
0.02
0.02
0.050
0.025
25
50
75
100
25
50
75
100
25
50
75
100
0.04
0.100
0.03
Suminverss
Regret
0.03
0.075
0.02
0.050
0.01
0.01
0.025
75
100
0.04
0.100
0.03
RIf ARD Regret
0.075
0.02
0.050
0,01
0.025
25
50
75
100
25
50
75
100
25
50
75
100
0.04
0.10
Regret
0.03
0.08
Diff
0.02
0.02
0.06
0.01
0.04
50
75
100
25
100
25
0.04
0.10
0.03
Matern
Regret
0.03
0.02
0.01
0.01
25
50
75
100
100
75
100
#lters
#lters
#iters
Q6:5
Qo:20
Qo:50
Qs: 100
On :200
Figure 27: Sensitivity of performance to Qo different tasks and kernels. From left right: Centrality maximisation on Enron, Facebook and Twitch networks. Kemelss from top to bottom: polynomial, sum-of-inverse polynomials, diffusion (with ARD), diffusion (without ARD), and graph Matérn.
26

---

Enron
Facebook
Twitch
0.04
0.100
0.03
Poly Regret
0.075
0.02
0.02
0.050
0.01
0.025
25
50
75
100
25
50
75
100
25
50
75
100
0.04
0.100
0.03
Suninvers
Regret
0.03
0.075
0.02
0.02
0.050
0.01
0.025
25
50
75
100
25
100
25
100
0.04
0.03
RIff ARD Regret
0.075
0.02
0.02
0.050
0.025
25
50
75
100
100
100
0.10
0.03
Diff
Regret
0.08
0.02
0.06
0.01
0.01
0.04
25
50
75
100
25
50
75
100
25
50
75
100
0.04
0.10
0.03
Matern
Regret
0.03
0.08
0.02
0.02
0.01
0.01
100
#Iters
#liters
#liters
fail_tol:5
fail_ tol:10
fail_tol:20
fail. tol:30
fail_ tol:4o0:0
fail_ tol:50
Figure 28: Sensitivity of performance to fail_tol tol on different tasks and kernels. Refer to Fig. 27 for additional explanations.
27

---

Enron
Facebook
Twitch
0.10
Poly
Regret
0.03
0.08
0.02
0.06
0.04
25
50
75
100
25
50
75
100
25
50
75
100
0.04
0.100
Suninverse
0.03
Regret
0.03
0.075
0.02
0.050
0.01
0.025
75
100
0.04
0.10
0.03
Olff ARD Regret
0.08
0.02
0.02
0.06
0.01
0.04
25
50
75
100
25
50
75
100
25
50
75
100
0.04
0.10
0.03
Diff
Regret
0.03
0.08
0.02
0.02
0.06
0.04
50
75
100
25
100
0.04
0.10
0.03
Matem
Regret
0.08
0.02
0.02
0.06
0.01
25
50 #lters
75
100
25
100
25
100
#iters
#iters
1:1.
y:1.5
2:2.0
3:
y:5.0
Figure 29; Sensitivity performance to y on different tasks and kernels. Refer Fig. 27 for additional explanations.
Enron
Facebook
Twitch
0.04
0.03
Poly Regret
0.075
0.02
0.01
0.050
25
75
100
25
50
100
25
50
100
0.04
0.10
0.03
Supinverss
Regret
0.02
0.02
0.05
0.01
0
25
50
75
100
25
50
100
25
100
7:
0:5
7:10
7:25
7:50
n:
100
Figure 30: Sensitivity of performance to n7 different tasks and kernels. Refer Fig. 27 for additional explanations. Note that only Polynomial and Sum-of-inverse polyooomeeppoooiilllllll kernels requiring non-trivial 7 selection included.
28

---

0.030
BayesOptG Diff Full
0.020
BayesOptG Dirr_ Full
BayesOptG Poly Full
BayesOptG Poly.
0.025
BayesOptG, Poly_TR TR
BayesOptG Paly_
BayesOptG Diff. TR
0.015
BayesOptt Diff
0.020
Regret
0.015
0.010
0.005
0.005
0.000
0.000
20
40
60
80
100
20
40
60
80
100
#iters
#lters
Figure 31: Influence of trust region method performance compared to full graph knowledge in a WS graph of 400 (Left) and 1000 (right) nodes. It is worth noting that while the use of trust regions leads to some trade-off in terms of optimisation performance, without trust regions, the algorithms are significantly more computationally prohibitive. In the graph 1000 nodes (right), the computational cost is more than 20x the cost of local algorithm (shown by Fig. in the main text which focuses on wall-clock time comparison).
29


Reviews:
[{"review_id": "OipQW3wAXt", "reviewer": "Reviewer_nGA9", "summary": "The paper extends the use of Bayesian optimization based methods for optimization of the functions over the nodes of graph this algorithm is dubbed as BayesOptG. Paper mainly focuses on following three aspects: \n1. Kernel design - Authors introduce suitable kernels, diffusion kernel, polynomial kernel and sum of inverse polynomial kernel, which can be used with the Gaussian process (GP) surrogate. \n2. BayesOptG - Algorithm uses GP surrogate with suitable kernels to model the function on graph followed by the use of standard acquisition functions to determine the next query, the algorithm adapts the idea of trust regions not only to scale to larger graphs but also to handle imperfect knowledge about the graphs.\n3. Empirical Results - The algorithm is empirically evaluated both on synthetic and real world datasets and is compared to the other baselines such as random search, local search, depth first search, breadth first search.", "questions": "Questions - \n1. Can you please provide a bit of background on why the kernels mentioned in the paper would result in semi positive definite covariance matrices?\n2. Why are the kernels chosen the right choice and what is the intuition behind the choice? Can the Matern kernel introduced in [3] be used?\n\nSuggestions -\n1. Check the captions of Figure 2 and caption of figure 3 is hard to follow.\n2. Few acronyms were introduced after they were used in prior sections. ex. BA and WS in section 5.1.\n3. Section A2 introduction BFS and DFS is probably jumbled.\n\n[3] Borovitskiy, Viacheslav, et al. \"Matérn Gaussian processes on graphs.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2021.", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This work extends the BO based methods to the functions defined over the nodes of graph.\n2. The algorithm introduced is scalable to larger and general graphs, further it can also be used in the cases with imperfect knowledge of the graph.\n3. Clear introduction of the problem setup and where exactly the BO is being applied.\n4. Experimental evaluation of the algorithm both on synthetic and Real world datasets.", "weaknesses": "Though the paper provides good experimental evaluations for the algorithm it lacks on the theoretical results. Further, little to no intuition is provided why the given choices of kernel functions are the right ones and the guarantees on the semi positive definiteness of the covariance matrix is also missing. The experiments section can further be improved by comparing the results with other algorithms such as spectral bandits[1], and GRUB [2]. \n\n\n[1] Valko, Michal, et al. \"Spectral bandits for smooth graph functions.\" International Conference on Machine Learning. PMLR, 2014.\n\n[2] Thaker, Parth, et al. \"Maximizing and Satisficing in Multi-armed Bandits with Graph Information.\" Advances in Neural Information Processing Systems 35 (2022): 2019-2032.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful and positive feedback. We are glad the reviewer commented positively on our method's strength and experimental results. Please see below for our response to the reviewer’s concerns.\n\n> little to no intuition is provided why the given choices of kernel functions are the right ones \n> Why are the kernels chosen the right choice and what is the intuition behind the choice? \n\nWe thank the reviewer for the suggestions on adding these discussions and insights, which we agree would be useful for prospective users of our algorithm. Please see the [Overall Response: Discussions of relative strengths of different methods and different kernels of BayesOptG](https://openreview.net/forum?id=UuNd9A6noD&noteId=FsjM9qNZ9q) for discussions on this point.\n\n> Can the Matern kernel introduced in [3] be used?\n\nWe thank the reviewer for the suggestion. We can indeed introduce the Matern Kernel in our algorithm. We provided experimental results for the centrality tasks with the Matern kernel with parameter $2.5$ in Fig S1 and S2 in the rebuttal pdf.\n\n> the guarantees on the semi positive definiteness of the covariance matrix is also missing. \n> Can you please provide a bit of background on why the kernels mentioned in the paper would result in semi positive definite covariance matrices?\n\nPlease see the positive semidefiniteness proof below. This will be included in the updated manuscript. In our formulation in eq 1, any map $r : \\mathbb{R}  \\rightarrow [0, +\\infty]$ defines a valid covariance kernel.\nIndeed,\n\n$\\forall \\mathbf{X} \\subset \\mathcal{V}, k(\\mathbf{X}, \\mathbf{X}) = \\sum_{i=1}^{\\tilde{n}} r^{-1}(\\lambda_i)\\mathbf{u}_i[\\mathbf{X}] \\mathbf{u}_i[\\mathbf{X}]^{T}$,\n\nwhere \n\n$\\\\mathbf{u}\\_{i} [\\\\mathbf{X}] = [u_i[x_1], u_i[x_2], ..., u_i[x_{l}]]^{\\\\top}$ with $l = |X|$.\nThe matrix $u_i[X] u_i[X]^{\\top}$ is symmetric positive semidefinite as the outer product of one non-zero vector:\n$\\forall x \\in \\mathbb{R}^{l}, x^{\\top} u_i[X] u_i[X]^{\\top}x = ||u_i[X]^{T}x||_{2}^{2} \\geq 0$. As a result, our covariance matrix is symmetric positive semidefinite as the weighted sum of symmetric positive semidefinite matrices with positive coefficients.\n\nThe kernels we presented in this paper correspond to a positive $r$, hence they are positive semidefinite.\n\n> The experiments section can further be improved by comparing the results with other algorithms such as spectral bandits [1], and GRUB [2]. \n\nWe thank the reviewer for their feedback. We agree that the settings in the spectral bandits and GRUB papers share similarities with ours. However, there are significant differences. First, both of these methods assume that the graph information is fully known and therefore does not involve graph (topology) exploration. In comparison, our approach allows for exploring a potentially unknown graph. Second, we understood both methods are global methods in the sense that the spectral bandit work requires the spectral decomposition of the graph Laplacian, while GRUB requires computing its inversion. Both operations are prohibitive for large graphs. In comparison, our method can handle large graphs (as shown in the additional experiments in Fig S3 in the PDF) due to the setup where the graph topology can be explored on-the-fly.\n\nDespite these differences, we can compare the performance of these methods to our algorithm for small and known graphs, which we will endeavour to include in the updated manuscript.\n\n> Check the captions of Figure 2 and caption of figure 3 is hard to follow.\n> Few acronyms were introduced after they were used in prior sections. ex. BA and WS in section 5.1.\n> Section A2 introduction BFS and DFS is probably jumbled.\n\nWe thank the reviewer for spotting these issues, which will be rectified in an updated manuscript.\n"}, {"review_id": "C0exiQSkkT", "reviewer": "Reviewer_sVur", "summary": "The paper presents a Bayesian optimization algorithm for functions defined on the nodes of (potentially unknown) graphs.  The algorithm combines local modelling via trust regions to account for the potentially unknown nature of graphs with random restart to avoid becoming stuck in local minima.  Novel kernels on graphs are defined (locally) to avoid problems related to overfitting.", "questions": "- Step 4 in algorithm 1: it is unclear how this step is to be interpreted on the first iteration of the algorithm with $v_t^*$ is not defined yet.\n- Why set $Q_{\\rm min} = 1$ (line 226)?  Wouldn't this mean that you *only* test $v_t^*$ for that iteration (region size of $1$), which is redundant as you already (presumably) know the value of $f$ at this node?", "limitations": "N/A", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This paper addresses a novel problem, the discussion is compelling and the results appear to be sound.", "weaknesses": "(see questions below).\n\nMinor point: figure 2 - equation (??).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe thank the reviewer for their positive and insightful impact and are glad the reviewer found our discussions novel, compelling and sound. Please see below for our response to the concerns the reviewer raised.\n\n> Minor point: figure 2 - equation (??).\n\nWe thank the reviewer for pointing this out. We were referring to the mathematical definition of the central node (Line 209).\n\n> Step 4 in algorithm 1: it is unclear how this step is to be interpreted on the first iteration of the algorithm with $v^*_t$ is not defined yet.\n\nThe reviewer is correct in pointing out this fact. This should instead be placed after Line 8 (i.e. after “end if”). $v^*_t$ is initially found by finding the best point in all the randomly initialising points.\n\n> Why set  Q_min = 1(line 226)? Wouldn't this mean that you only test v_t^* for that iteration which is redundant as you already (presumably) know the value of at this node?\n\nThe reviewer is correct in pointing out that when $Q=1$, we have a trivial subgraph consisting of only the node we have queried. We set $Q_{min}$ to 1, as when this happens, we know, *with certainty*, that the current subgraph contains no more unknown information and that a better solution definitely does not exist. In practice, we restart when $Q_{min}$ = 1 or all nodes in the subgraph have been queried before. It is indeed possible to set $Q_{min}$ to a value larger than 1, but that creates an additional hyperparameter; we set it to 1 because, as discussed, this is one of the most definite signals requiring a restart.\n\nWe will clarify this when we update the manuscript.\n"}, {"review_id": "MZUmDnKx0a", "reviewer": "Reviewer_tMg5", "summary": "This paper solves an optimization problem defined on a graph.  Since the problem defined on a graph requires the need to search for a solution in a combinatorial manner, it is a challenging problem.  To tackle such a problem, the authors investigate diverse kernels on a graph and a local search strategy on a graph.  Finally, they provide the experimental results that show the performance of the investigated methods.", "questions": "1. As described above, the authors can provide more thorough discussion on which method is strong at some circumstances and which factor affects to the performance.\n2. Moreover, the authors can discuss analysis on the investigated method in terms of kernel types and local search strategies.  For example, a diffusion kernel is generally able to capture meaningful relationship between two nodes compared to polynomial and sum of inverse polynomials kernels.  On the contrary, the other kernels show their effectiveness in some conditions.  The discussion like this should be included in this paper in order to understand the algorithms appropriately.\n3. Basically, the experimental results are hard to interpret.  Figures are too small and lines are too thin.\n4. The number of evaluations is too small.\n5. Regardless of the visualization of the experimental results, there is no consistency I think.  I do not much care about the inconsistency, but the authors need to discuss why it happens.\n6. I cannot understand the experiment of team optimization.  Each node represents a team, right?  How many team members belong to a team?  The size of team does not affect to the evaluation of team?  I think a skill vector of each member is sum to one because it is drawn from the Dirichlet distribution.  But if the sum of skill sets for team members exceeds 1, what happens?  Is it just treated as 1 or the sum of skill values?", "limitations": "I do not think that this work has specific limitations.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "* The problem defined on a graph has not been studied much.  This topic in particular is interesting in the Bayesian optimization community.\n* Experiment section contains many things to discuss.", "weaknesses": "* Analysis on which method is strong at some circumstances and which factor affects to the performance is lacked.\n* Analysis on the investigated methods is lacked.\n* Discussion on local search strategies is weak.\n* Experimental results seem not consistent.\n* Writing can be improved.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their insightful comments. It seems to us that the biggest concern comes from the discussions of the experimental results and the relative strengths of different methods in different situations. We agree with the reviewer that such a discussion would be helpful for users, especially in a practical setup, and we thank the reviewer for their suggestions. We include a detailed discussion on this point in the [overall response](https://openreview.net/forum?id=UuNd9A6noD&noteId=FsjM9qNZ9q), which will be incorporated into the manuscript, and we are confident that the issues pointed out in the review can be fixed when we update the manuscript. We hope the reviewer can consider increasing their rating in light of this.\n\n> Experimental results seem not consistent. The authors need to discuss why it happens.\n\nWhile we refer the reviewer to our overall response, we would like to emphasise that *our proposed algorithm, BayesOptG* (marked as “BO\\_*” in the figures), *always outperforms or at least performs on par compared to the best baseline* (except for Fig 4 if we opt to use obviously inappropriate kernels such as BO_Diff (without ARD) against the local search, the strongest baseline – see our explanations below). **From this perspective, there is little inconsistency in experimental results**. While there are indeed differences between different kernel choices, as we discussed in the overall response, the fact that different kernels are suited for different problems and that the kernel choice often significantly impacts the modelling performance of GPs is highly expected for *any* GP-based technique. We argue that this is not a weakness of our method, but the fact that BayesOptG performs strongly *regardless of the kernel choice* demonstrates its robustness. \n\n> Analysis on the investigated methods is lacked.\n\n> As described above, the authors can provide more thorough discussion on which method is strong at some circumstances and which factor affects to the performance.\n\n> Analysis on which method is strong at some circumstances and which factor affects to the performance is lacked.\n\n> Discussion on local search strategies is weak.\n\n> Moreover, the authors can discuss analysis on the investigated method in terms of kernel types and local search strategies. For example, a diffusion kernel is generally able to capture meaningful relationship between two nodes compared to polynomial and sum of inverse polynomials kernels. On the contrary, the other kernels show their effectiveness in some conditions. The discussion like this should be included in this paper in order to understand the algorithms appropriately.\n\nAs we mentioned at the beginning of the response, we thank the reviewer for the suggestion and agree this can be important for potential users. We direct the reviewer to our “Overall Response” for the requested discussions in response to all the comments above that the reviewer raised.\n\n> Basically, the experimental results are hard to interpret. Figures are too small and lines are too thin.\n\nWe thank the reviewer for this feedback. We will address this in the revised manuscript.\n\n> The number of evaluations is too small.\n\nWe are unsure whether the reviewer meant i) the query budget or ii) the number of random trials. \n\nIf the reviewer meant i): while we agree it is advantageous to run longer experiments, it is not uncommon in BO work to set the query budget around 100, given the assumption that the evaluation is expensive. If the reviewer meant ii), we again agree that increasing the number of random trials would always be beneficial. However, we argue that the BO algorithm's outperformance over the baselines is strong and consistent with the 10 repetitions we used already.\n\nIn any case, we thank the reviewer’s suggestion and provide some additional experiments where we increase both the query budget and the number of random trials, and the reviewer is referred to Fig S3 and S4 in the rebuttal pdf where the paper's main findings still stand.\n\n> I cannot understand the experiment of team optimization. Each node represents a team, right? How many team members belong to a team? The size of team does not affect to the evaluation of team? I think a skill vector of each member is sum to one because it is drawn from the Dirichlet distribution. But if the sum of skill sets for team members exceeds 1, what happens? Is it just treated as 1 or the sum of skill values?\n\nWe thank the reviewer for the opportunity to clarify our work. We initially set a maximum number of members in team $N$, and a number of “skills” $K$. Then, the graph is built such that each node represents a team with less than $N$ members (there are $2^N$ of these, hence potentially very large), and an edge is defined between teams that have a minimum number of common members (above a certain quantile of the distribution of common members across all possible pairs of teams). The objective function aims at maximising team competence by promoting members who are experts, and that complement each other. One member is indeed a discrete distribution over skills, and so is each team, where each skill component is the average skill component over its members, hence also defining a distribution. If we define the objective function by the difference between the entropy of the skill distribution of the team and the average entropy of the skill distribution over its members, the objective promotes the completeness of the team and the sparsity of skills among the team members. Regarding the size of the team, the reviewer is right in stating it does not influence the objective. We will address this issue by adding a regularising term in a revised version of the manuscript.  \n"}, {"review_id": "jZiMtFFlJM", "reviewer": "Reviewer_GnE3", "summary": "The authors consider the Bayesian optimization for functions defined on a graph (e.g., finding a node in a graph to min/max some function on that graph). The authors propose a local modeling approach for such problem on generic, large-scale and potentially unknown graphs. The authors demonstrate the advantages of the proposed approach on several experiments.", "questions": "The flow of the submission is clear. However, it is better in case the authors elaborate more details for some important parts.\n+ Although the authors discuss in line 229-241, the proposed approach (e.g., local modeling) is closely related to the trust-region-BO. In my understanding, the local modeling is at the heart to make the approach handle possibly large-scale graph. In some sense, they share the same role. \n+ The authors should elaborate how to select the next “subgraph” (even its size is given). Does the selected subgraph require to be connected? (since it seems that the authors do not assume that the graph is connected?). Is there any overlap between subgraphs at different iterations?\n+ The authors should give more details for their experiments in the main manuscript, especially the size of the graph and the objective function for optimization. It is unclear that the authors illustrate the proposed approach for large-scale graphs, (or potentially unknown graphs?) to optimize functions on graph (which are expensive to evaluate) yet.\n+ It is unclear how the proposed algorithm can handle unknow graphs as claimed? Could the authors elaborate it with more details?\n+ It is better to elaborate more details about the Algorithm 1 and 2 in the main text, especially the Algorithm 2.\n+ For the strategy as in line 205-215, could the authors give more explanation when the algorithm finds a subgraph with local minima, is it stuck on that region around the subgraph, or it has some strategy to improve the objective function more? (e.g., by explore to some far regions?)\n\nSome minor points:\n+ What is $\\tilde{A}$ in line 140? There is no explanation for it.\n+ Reference for Equation in Figure 2\n\n---\n\nI thank the authors for the rebuttal.", "limitations": "The authors have not discussed the limitations and potential negative societal impact of their work.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "+ It is interesting to consider Bayesian optimization approach for a function on a graph (i.e., finding a node in a graph which minimizes/maximizes some function defined on that graph).\n+ The local modeling makes the approach to scale up for large-scale graph, potentially unknown graph.\n+ The authors also propose two kernels for Bayesian optimization for functions on graph (which are variant of the diffusion kernel on graph)\n+ The authors provide extensive experiments for the proposed approach.", "weaknesses": "+ The experiments seem weak. It is unclear whether the authors have considered any large-scale graphs, or potentially unknown graphs in the experiments from the main manuscript. It is also unclear about the objective functions for all the experiment whether one needs Bayesian optimization for the tasks yet.  \n+ Some important part needs to elaborate with details, e.g., especially selecting the local subgraph; why the proposed approach can handle potential unknown graph?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed feedback. It seems that the primary concern is 1) how our method deal with unknown graphs and 2) some details of BayesOpt. We address both below, and we hope the reviewer will consider increasing their rating in light of our response.\n\n> The experiments seem weak. \n\nFirst, as the reviewer acknowledged, our paper features an extensive experimental section, perhaps more so than many published works in BO, even though we are considering a novel setup with scarce prior works. Second, BayesOptG consistently outperforms the baselines despite the differences in underlying function properties. We believe both strongly support the strength of our experiments.\n\n> Large-scale & unknown graphs\n\n“Size”: We considered varying graph sizes and detailed them in the figure captions ranging from thousands (synthetic tasks) to tens of thousands in Fig 9 (34,000 for Enron, 14,000 for Facebook graph). In some experiments, the use of smaller graphs (of $\\mathcal{O}(10^3)$) is attributable to the cost of computing the objective function (e.g. betweenness or eigenvector centrality) and not because our method cannot be used for large graphs. To illustrate this, we scale BayesOptG to 1,000,000-node graphs for some tasks in Fig S3 of the rebuttal PDF, where it retains strong performance.\n\n“Potentially unknown graphs”: for all experiments, the full information about the graphs is *never* revealed a-priori (except for regression experiments in §5.1 to test the predictive powers), and thus from this perspective, all experiments feature “unknown” graphs to the BO agent at the start of the algorithm. The graph structure is only incrementally revealed to the BO as the optimisation proceeds: when BO queries a point, its ego-network, a local subgraph, is revealed.\n\n> Why one needs BO for the tasks\n\nPlease see the overall response.\n\n> details on local subgraph selection and why this handles unknown graphs\n\nThe subgraph selection is elaborated by Algorithm 2 and §3.2 – the approach may handle unknown graphs as it does not require the full graph information to be known a-priori. Only when the BO queries a node the graph structure of the ego-network centred around that node is revealed to the BO agent. As such, the algorithm works as long as we can request to reveal the local information around the nodes we query.\n\n> Although the authors discuss in line 229-241, the proposed approach (e.g., local modeling) is closely related to the trust-region-BO. In my understanding, the local modeling is at the heart to make the approach handle possibly large-scale graph. In some sense, they share the same role.\n\nWe’d be grateful if the reviewer could clarify the question in this remark, but we will explain what we meant in paragraph *Remarks on the relation to trust-region BO methods* in §3.2. \n\nThe reviewer is right to say that the local modelling makes scaling the method to large graphs possible, as we only impose GPs on the subgraph. However, as discussed above, local modelling also makes it possible to apply the algorithm to unknown graphs as, at any point in time, the algorithm *only requires information about this local graph* and works as long as we are capable of collecting and querying local graph information around the queried node.\n\nIt’s also worth noting that the primary objective of trust regions in previous BO algorithms is *not* to ensure scalability but to alleviate the curse of dimensionality of GP by focusing on a promising subspace to reduce over-exploration [1]. In the typical BO setup, the scalability is typically purely bottlenecked by the number of training points. Unlike our graph setup, the search space size *plays no role in scalability*. While trust region BO, by the periodic restarting of the GP, resets the training samples of the GP & is indeed more scalable than an algorithm that does not restart, we argue this is a side-effect of restarting and not of trust regions. We argue this is another difference in motivation between us and previous trust region BO methods.\n\n[1] Eriksson et al. (2019). Scalable global optimization via local Bayesian optimization. NeurIPS.\n\n> how to select the next “subgraph” \n\nThe procedure to select the next subgraph is in Algorithm 2. As mentioned in Line 209, the subgraph is constructed around the node with the best objective function seen so far. \n\n> Does the selected subgraph require to be connected?\n\nThe subgraph is the ego-network centred around the best node seen so far, so it is, by definition, connected. Our algorithm still works when there are disconnected components due to the restart mechanism (line 227): while within one restart, the BO will explore one connected graph, the BO may jump to another disconnected subgraph after a restart since the restart location is determined randomly.\n\n> Overlap between subgraphs at different iterations\n\nYes – if the best objective value did not increase, the subgraph does not change from the previous iteration. Otherwise, it is moved to be centred around the new best node, but there will still be overlap (as the new best node must lie within the preceding subgraph) – as illustrated in Fig 1. An additional point to clarify is that the GP is always imposed over the *current* subgraph: when the subgraph changes, some evaluated nodes will no longer be in the current subgraph. We do not impose GP over these points, so the subgraph does not accumulate over previous evaluations.\n\n> is the algorithm stuck on that region around the subgraph, or does it have some strategy to improve  more?\n\nPlease see our description of the restart mechanism to deal with this issue in Lines 227-228. \n\n> tilde{A}\n\nIt is the adjacency matrix of the subgraph. We will clarify this in the revised manuscript.\n\n> Equation in Figure 2\n\nWe will address this in the revised manuscript. We meant to refer to the mathematical definition of the central node, i.e. the best node seen so far (Line 209)."}, {"review_id": "K2zAJefUaG", "reviewer": "Reviewer_4pXS", "summary": "This article proposes a Bayesian optimization approach to solve node-level tasks with graph-structured data. The presented framework, combined with three kernels that capture the covariance functions on graph-structured data, models each node by its ego-graph of a learnable size. The authors argue that this approach not only makes the optimization process tractable but also addresses the challenge that the graph information might not be entirely available. Experiments with synthetic and real-world tasks demonstrate that the presented framework achieves superior or competitive performance.", "questions": "If the graph information is not entirely available, how does breaking the entire graph into multiple ego graphs help? When the ego graph of a node selected in an early iteration is wrong due to missing links, the following iterations will make wrong judgments too.", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. Novelty: good observation on the lack of Bayesian optimization framework on node-level tasks.\n2. Soundness: the three kernels, especially the latter two, are well presented. Their functions in the BO process is well explained and persuasive.\n3. Clarity: Figure 2 and Algorithm 1 help the paper with information presentation. Most entities are well-defined.\n\n", "weaknesses": "1. Significance: BO is usually utilized to approximate black-box functions that are expensive to evaluate. However, the description in the introduction section and the tasks in the experiments fail to demonstrate the necessity of using BO.\n2. Arguing the tractability of the framework, this paper did not discuss the time complexity. And there are no experiment results on running time either. (Solved)\n3. Typo in Algorithm 1. 2: Output: the node that v^*_T that minimises the objective function. Extra \"that\", and \"minimizes\". (Solved)\n4. Figure 2 wrong reference. \"to the central node (Eq. (??) in the figure)\". (Solved)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe appreciate the reviewer’s comments and are glad they have positively remarked on our paper’s novelty, soundness and clarity. We believe that we have addressed the reviewer’s concerns below, and in light of this, we hope that the reviewer will consider increasing their rating.\n\n> Significance: BO is usually utilized to approximate black-box functions that are expensive to evaluate. However, the description in the introduction section and the tasks in the experiments fail to demonstrate the necessity of using BO.\n\nWe will improve the presentation in Introduction and Experiments as suggested and refer the reviewer to our [overall response](https://openreview.net/forum?id=UuNd9A6noD&noteId=FsjM9qNZ9q) on this point.\n\n> Arguing the tractability of the framework, this paper did not discuss the time complexity. And there are no experiment results on running time either.\n\nWe include the time complexity analysis below, which we will add to the final version of the paper.\n\nFirstly, as with all GP-based BO algorithms, BayesOptG scales cubically with the number of training points $N$: $\\mathcal{O}(N^3)$, assuming no other efficient approximations are used. A unique challenge in the graph case is that the algorithm can also be bottlenecked by the *search space size*, as computing the kernels requires eigendecomposition of the Laplacian matrix of the graph, a basic algorithm for which scales $\\mathcal{O}(n^3)$ where $n$ is the number of nodes. Thus, the overall complexity can be given by $\\mathcal{O}(N^3 + n^3)$.\n\nThe restart and local modelling algorithm introduced in §3.2 ensures both terms are tractable. By placing the GP over the local subgraph only, $n$ is now upper limited by the max subgraph size instead of the size of the entire graph, which can be very large. By periodically restarting the GP when the optimisation gets stuck, we implicitly prevent $N$ from growing very large. This is why local modelling ensures the tractability of the framework. \n\nWe also add the running time comparison the reviewer requested in Fig S6 of the rebuttal PDF to demonstrate this more concretely. It is, however, worth noting that exactly due to what the reviewer mentioned previously, given that BO is commonly used to optimise expensive functions, in real life, the computational cost is likely dominated by the cost of querying the objective functions, and thus the number of objective function evaluation that we used in the paper is often a better proxy of the overall cost.\n\n\n> Typo in Algorithm 1. 2: Output: the node that v^*_T that minimises the objective function. Extra \"that\", and \"minimizes\".\n> Figure 2 wrong reference. \"to the central node (Eq. (??) in the figure)\".\n\nWe thank the reviewer and will correct these typos. We were trying to refer to the mathematical definition of the central node (Line 209).\n\n> If the graph information is not entirely available, how does breaking the entire graph into multiple ego graphs help? When the ego graph of a node selected in an early iteration is wrong due to missing links, the following iterations will make wrong judgments too.\n\nWe believe this is a misunderstanding in our setup, and we will clarify this crucial aspect when we revise the paper. \n\nWhen we mentioned that “graph information is not entirely available”, we refer to the setup that we cannot access the graph in full – this is very common either due to the size (e.g., we cannot access the entire Facebook graph as it is too large) or cost (e.g. in the contact tracing example, it is impractical to have the full information beforehand, we that would require us to interview and contact-trace everyone involved). What we can do is query a node and reveal the graph structure around it (the ego-network part), *noiselessly* – this is also a reasonable assumption: using the examples above, this is akin to viewing *a specific person’s* Facebook friends and conducting an exhaustive contact-tracing interview on *a specific person*. Crucially, at this step, we do not consider the case that the network structure revealed locally is noisy or otherwise erroneous (e.g. with missing or fake links), nor are we “breaking the entire graph into multiple ego graphs” as the reviewer suggests – we are simply revealing the structure on the fly.\n\nIn other words, when we say “graph information is not entirely available”, we mean that the global graph is not available to the BO agent initially, but it may query nodes and reveal local subgraphs around them when the optimisation proceeds. This does not mean we have a partial, noisy or otherwise inaccurate graph structure to begin with, which seems to be what the reviewer suggests. While we agree that studying such a more challenging setup is interesting and will include it in future works, this is out-of-scope of the current submission (especially in view that the current submission is one of the first attempts of using BO in this setup, as the reviewer also agreed on)."}]

Author rebuttal:
We thank all reviewers for their feedback. We are glad that they acknowledged the novelty (all reviewers), clarity of writing (4pXS, nGA9, GnE3), soundness (nGA9, sVur, GnE3, 4pXS), and extensiveness (GnE3, tMg5) and strength (sVur, nGA9) of experiments. We address common concerns below.

## Necessity of BO (4pXS, GnE3)

We emphasise the problems studied in Experiments indeed represent or imitate setups where BO is suitable: while they may not be expensive to evaluate *per se*, they each imitate an expensive black-box function in real-life – note that **experimenting on cheap benchmarks as a proxy to expensive, real-life tasks is done in virtually every BO paper** (e.g. evaluating synthetic benchmarks and Contimation/Pest problems in COMBO [1], the most related work, are all cheap if not instant), except that we also design these tasks and provide solutions *ourselves* because of the novel problem setup. For example:

- Identifying patient zero imitates real-life contact tracing. If executed in real life, each function evaluation requires procedures like interviews about the individuals’ travel history and people they were in contact with. This is expensive and potentially disruptive, and given limited resources, the use of a query-efficient method like BO is justified. 

- Centrality maximisation & identifying influential social network nodes mirror a common task for online advertising to identify the influential users without access to the full social network information (which would be near-impossible to obtain given the number of users). Real-life social media often limits how much one may interact with their platform through pay-per-use APIs or hard limits (e.g. upper limit of views). In either case, there is a strong reason to identify the influential users in the most query-efficient manner.

## Discussions of relative strengths of different methods and different kernels of BayesOptG (nGA9, tMg5)

Many factors may affect the algorithm’s relative performance, like smoothness and noisiness of the objective functions, graph sizes, number of local minima and whether isotropy holds true (i.e., function variation in all directions is similar). We discuss each algorithm considered below (the descriptions of the baseline are provided in Appendix A.2). For ease of comparison, we also include Fig S5 in the PDF to show the methods’ rank vs the number of evaluations aggregated across all experiments.

- Random Search is simple but typically weak for larger graphs, except for very rough/noisy functions (like Ackley), or the variation in function values is generally small.
- DFS and BFS are relatively weak as they consider graph topology information only but not the node information (on which the objective function is defined) and can be sensitive to initialisation.
- Local Search is, on average, the strongest baseline, and it does particularly well on smoother functions with fewer local minima (as local search is stuck at a local minimum and requires random restarting; having few local minima reduces such occurrences). Its strength is well-documented: for example, local search on smaller-scale benchmarks in neural architecture search is competitive against state-of-the-art search algorithms [2]. 
- From Fig S5, BayesOptG proposed by us with *any kernel choice* outperforms baselines, but some performance differences due to the kernel choices are bound to occur. We included many possible kernel choices to inform the readers of the performance impact and encourage them to select the most suitable kernel depending on knowledge about the objective function, if any. The importance of kernel choices is well-known for *any* GP-based technique rather than being unique to our method: given that mean functions are typically set to a constant, the kernel completely determines the GP’s behaviour, its modelling effectiveness and, by extension, the effectiveness of any derived technique (e.g. BO).

As is the case for all GP-based methods, the performance is stronger when the underlying assumptions of the kernel match the actual objective function. For example, diffusion kernels work well for patient zero and team optimisation (Figs 7 & 8), as the underlying generative functions for both problems are indeed smooth (in fact, the SIR model in disease propagation is heavily connected to diffusion processes). 

Diffusion without ARD further enforces isotropy, assuming the diffusion coefficient in all directions is the same, and thus typically underperforms except for team optimisation, where the generated graph is well structured (see Fig S7 in PDF) and Ackley (Fig 6 ab), which is known to be isotropic and symmetric. We recommend only if we know that the underlying function satisfies its rather stringent assumptions.

The SumInverse and DiffARD kernels are generally better, as they offer more flexibility in learning from the data; *we recommend using one of these as default if we have no prior knowledge*. The difference is that DiffARD has more learnable parameters and thus is even more flexible, but may also overfit initially when the number of observations is small – such a phenomenon can be seen in Fig S5 in the rebuttal PDF where SumInverse outperforms initially. The final kernel, Polynomial, performs weaker than the inverse; we hypothesise a possible reason is, from Table 1, a single epsilon is added to the polynomial before inversion. Even if the epsilon is chosen to be a small constant, it may still dominate the polynomial term (i.e. the learnt signal) when the latter happens to be small, and this may increase optimization difficulty (whereas for SumInverse, we add an epsilon to each polynomial term). We will thoroughly investigate this in the revised manuscript.

[1] Oh et al. (2019). Combinatorial Bayesian optimization using the graph cartesian product. NeurIPS.

[2] White et al. Local search is state of the art for NAS benchmarks. 7th ICML Workshop on Automated Machine Learning.

Meta-review: This paper considers the problem of Bayesian optimization on a graph that is potentially unknown. The reviewers agree that the problem setting is interesting and could be of interest to various sections of the NeurIPS community. The proposed method appears sound, and the experimental results seem to support its benefits compared to other methods in the literature.
Decision: Accept (poster)