Bayesian Optimization of Functions over Node Subsets in Graphs

We thank the reviewer for acknowledging the novelty and potential of our work! Please see our responses to the raised questions below.

How such approaches achieve provably good performance when we have no assumptions on function $f$? It is likely to fall into no-free-lunch theorem.

We’d like to respond from the general Bayesian Optimization (BO) perspective.

First, BO is most suitable for optimizing functions that are black-box and expensive to evaluate. If we have access to the gradient of the function, or the function is easy to evaluate, then there are more appropriate alternatives such as gradient-based optimizers or Reinforcement Learning (RL) methods. However, if the function is black-boxed and its values are costly to observe, then sample efficiency becomes an essential criterion to the optimizer, that is, we wish to obtain the best possible location within a limited number of queries. Note that RL usually requires a large number of samples to train the reward/policy models, which is infeasible under this setting.

The performance gain in BO mainly comes from the surrogate modeling approach, where a tractable model (e.g. Gaussian Processes) is used to gradually approximate the underlying function based on the observations. At each iteration, the surrogate model is fitted with previous observations and generates predictions on the rest search space, which allows us to identify the most promising location based on past knowledge, and then query its function value. In the next iteration, this new observation will be used to re-fit the surrogate, and we repeat the process until hitting the evaluation budget.

It means that, even though we have no prior knowledge about $f$ at the beginning, the algorithm tries to adaptly learn the pattern in $f$ along the search, where the next move is always guided by past knowledge, and thus explaining the superior performance of BO over other random heuristic methods.

It seems the structure (in particular, the edges) of the graph is not mentioned. Is the graph structure not essential in this context?

The underlying graph structure is very critical to the problem from the following perspectives.

1. Unlike classical combinatorial optimization over discrete space (e.g. searching for the optimal hyper-parameter combination), the configurations (i.e. node subsets) in our setting are not independent but linked via an underlying graph structure, which needs to be considered during optimization. This is why a graph GP is adopted as the surrogate model, where the similarity between configurations is measured by a kernel on graph (Equation 2), as discussed in Section 3.2.

2. Specifically, the above kernel is defined as a function of the graph Laplacian matrix $L$, which is computed by $L = D - A$, with $D$ being the degree matrix and $A$ being the adjacency matrix. This is how the edges are incorporated into modeling.

3. If the graph is sparse (e.g. a grid is sparser than a fully connected graph), the combinatorial graph will also be sparse. Then, with a fix-sized combo-subgraph of $Q$ combo-nodes, we can cover more hops (i.e. distant nodes) from the center combo-node at each iteration. Thus, the algorithm will traverse the comb-graph (i.e. substituting the elements in the subset) at a faster pace, as discussed in Lemma 3.2.

4. If the underlying graph structure is informative (e.g. BA network is more uniquely structured with heterogeneous node degree distribution as opposed to the WS network, whose node degree is more homogeneous distributed), the combinatorial graph will also be informative. In this case, it means that the kernel in the graph GP surrogate will capture more structural information, which eventually helps the algorithm visit better locations during optimization, as explained in Sections 3.3 and 4.

The performance scales poorly as k.

We are glad that the reviewer noticed our discussion on the limitation about subset size $k$, and we would like to make some further clarification below.

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

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

The choice of hyperparameter is ad-hoc.

We have conducted an ablation study in Appendix I to analyze the sensitivity of GraphComBO to the combo-subgraph size $Q$ and the non-improvement tolerance $`failtol`$, where the results show that the proposed method is quite robust to the latter. However, we do agree with the reviewer that the algorithm would benefit from an automatic strategy for determining the combo-subgraph size $Q$ (e.g. an adaptive design of $Q$), which we will leave to future exploration.

We’d like to thank the reviewer again for the comments that helped us improve the current work. We believe that we have now addressed all the concerns from the original reviews, and hope the reviewer could kindly consider increasing the rating/confidence in light of this.

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

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

[3] Robust Influence Maximization, KDD 2016

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

We would like to thank the reviewer for acknowledging the contribution of the proposed framework. Please see our response to the review comments below.

If applying Bayesian optimization to the problem is indeed novel, then I think it is an interesting contribution for the ML community, even if none of the ideas appears to be very involved in itself.

It is not very surprising that an approach that makes informed decisions to guide the search outperforms simple baselines like BFS or local search, somewhat weakening the significance of the results to me.

As discussed in the introduction, there are many optimization problems on graphs that involve expensive black-box functions defined on node subsets, e.g. outcomes from real-world implementation, results of large number simulations, and outputs from graph neural networks; at the same time, there are many applications where the underlying graph is not known a priori, e.g. offline social networks and contact networks. However, there is no general framework in the literature to optimize such black-box functions of node subsets in graphs, except for the classical graph traversal algorithms such as BFS/DFS and local search.

While we agree with the reviewer that it is very intuitive and “expected” that BO will outperform these classical algorithms, the main contribution of our work is, as pointed out by the reviewer, extending BO to this novel setup via an effective approach and obtaining good results over the existing baselines. To design such a framework, we have made the following technical contributions:

1. We proposed a combinatorial graph tailored for node subsets in a generic graph.

2. We introduced a recursive algorithm to sample subgraphs from the combinatorial space.

3. To handle the combinatorial explosion problem, we use a local approach to traverse the combinatorial graph space by iteratively sampling its subgraphs and moving around the subgraph center to more promising regions, which is guided by a surrogate model.

In the early stage, we tried other localization methods such as selecting nodes inside a subgraph on the original graph as the subset. However, since we need to maintain the diversity of the subset to cover potentially distant nodes, none of them can fit into the problem as cohesively as the current method, which makes our design non-trivial.

Are there other common baselines in the literature that are not based on Bayesian optimization?

As discussed above, to the best of our knowledge, the only existing baselines are those based on graph traversal algorithms, which have been modified to the current problem setting. In particular, we have proposed $k$-random walk and $k$-local search (Appendix B) as baselines that operate on the original graph, which have shown strong results in some of our experiments. We are more than happy to discuss with the reviewer if they believe there are works in the literature that tackle the same problem setups as ours.

In addition, we would like to mention that a new experiment has been added to the general response, in which we compare our method to COMBO (nevertheless, a BO baseline) on small-scale networks. The result (Fig. 4 rebuttal PDF) shows the proposed framework consistently outperforms this baseline, and we kindly refer the readers to the general response for more details if they find it relevant.

If one were to compare the present approach against a task-specific approach, do you have intuition on whether the present approach would perform significantly worse?

We thank the reviewer for this high-level question on the suitability of our framework to specific problems, to which we’d like to respond from the general Bayesian Optimization (BO) perspective in the following.

First, BO is most suitable for optimizing functions that are black-box and expensive to evaluate. If we have access to the gradient of the function, or the function is easy to evaluate, then there are more appropriate alternatives such as gradient-based optimizers or Reinforcement Learning (RL) methods, and we believe BO, as a black-box solver, would not be an appealing approach in those settings.

However, if the function is black-boxed and its values are costly to observe, then sample efficiency becomes an essential criterion to the optimizer, that is, we wish to obtain the best possible location within a limited number of queries. Note that RL usually requires a large number of samples to train the reward and policy models, which is infeasible under this setting.

Based on the above discussion, if our goal is to optimize certain expensive black-box functions, where some “good guesses” can be obtained from domain knowledge or a task-specific approach, we can always incorporate that information into BO by either initializing the search at the promising locations identified by the task-specific method, or updating the prior in the surrogate with the domain knowledge. This implies that, in most cases, BO serves as a complement to the domain-specific methods rather than a complete substitute.

Other: ego-subgraph is not defined

We thank the reviewer for this reminder. In Lemma 3.2, an $\ell$-hop ego-subgraph centered at an arbitrary combo-node $\hat{v}$ on the combo-graph means that we create an ego-network around $\hat{v}$ with its $\ell$-hop neighbors, and the resulting ego-network is an ego-subgraph. We will make sure this concept is clear in the revised version.

We’d like to thank the reviewer again for the comments that helped us reflect on our work. We believe that we have now addressed the concerns from the original reviews, and hope the reviewer could kindly consider increasing the rating/confidence in light of this.

We would like to thank the reviewer for the detailed feedback which helped us improve the current work. In summary, the reviewer's concerns are (1) If the framework can handle noisy observations, and (2) Comparison with COMBO on small networks. Please see below for our responses.

Do you account for noise in your framework? It is unclear to me whether the described algorithm is fit for noisy problems.

Yes, similar to other common BO methods, the proposed framework can handle noise. As pointed out by the reviewer, we used the Ackley function on a 2D grid with Gaussian noise as the underlying function in one of the synthetic experiments, meanwhile under real-world setups, we also used noisy results from simulations as the underlying functions.

For the notations, we intended to express the most standard setup in BO, that is $y = f(x) + \epsilon$, with $\epsilon \sim N (0, \sigma^2_{\epsilon})$ being the noise term. We will make sure this is clear in the revised version.

A more comprehensive experiment under the noisy setting

To better answer the other questions from the reviewer and show our framework’s capability of handling noise, we further conduct a noisy experiment at different noise levels on BA ($|V|=10k$) and WS ($|V|=1k$) networks with $k=8$, where the goal is to maximize the average PageRank within a node subset, i.e., $f(\mathcal{S}) = \frac{1}{k}\sum_{i=1}^k PageRank(\mathcal{S}_i)$, with $\mathcal{S}$ being a subset of $k$ nodes $\\{v_1, v_2, …, v_k\\}$ in the underlying graph.

Can you provide an estimate of the noise level to the signal variance?

While it is difficult to show the noise level to the signal variance in real-world experiments because of the combinatorial space, we can construct a standardized signal under this synthetic setting with the following procedures:

First, we standardized the PageRank scores over all nodes to mean=0 and std=1 in the original space (denoted as $PageRank_s$). To standardize the underlying function in the combinatorial space, we multiply $\sqrt{k}$ to the avg. $PageRank_s$ as the final underlying function $\tilde{f}(\mathcal{S})$, that is,

$\tilde{f}(\mathcal{S}) = \sqrt{k} f_s({\mathcal{S}}) = \frac{1}{\sqrt{k}} \sum_{i=1}^k PageRank_s(\mathcal{S}_i)$,

in which $\mathbb{E}[\tilde{f}(\mathcal{S})] = 0$, and $Var(\tilde{f}(\mathcal{S})) = \frac{1}{k} Var(\sum_{i=1}^k PageRank_s(S_i)) = \frac{1}{k} \times k \times Var(PageRank_s(v)) = 1$.

Now, we can simply add random Gaussian noise to $\tilde{f}(\mathcal{S})$. Specifically, we consider $\epsilon \sim N (0, \sigma^2_{\epsilon})$ with $\sigma_{\epsilon}$ at [0.1, 0.25, 0.5, 1], where the level of noise can be directly estimated since both the underlying function and noise are now of mean=0 and std=1. In addition, we further plot the estimated density of the original and noisy signals in Fig.2 (rebuttal PDF) to intuitively visualize the difference, which is done by randomly sampling $10^5$ observed values in the combinatorial space $\binom{\mathcal{V}}{k}$.

In the noisy setting, why does the framework apply the acquisition function to unvisited combo-nodes only? Why change the location of the combo-graph based on the observations instead of the posterior mean or the acquisition function?

We would like to thank the reviewer for this insightful question. As suggested, we implement GraphComBO-Noisy, which uses the best posterior mean across both visited and non-visited combo-nodes within the combo-subgraph as the new center.

How do you expect your algorithm to react to noisy function values? I believe its behavior would be quite different, especially because the location of the combo-graph is selected according to the observed function value, which is not longer accurate.

The results (Fig.3 rebuttal PDF) show that the original method GraphComBO is robust to the noisy observations on both networks at different noise levels from $\sigma=0.1$ to $\sigma=1$. Compared with GraphComBO-Noisy, the observation-guided method performs comparably in most cases, except for a very noisy setting when $\sigma=1$ on WS networks, where we can observe a clear advantage from the method guided by posterior mean, and it can be explained as follows.

Unlike classical discrete combinatorial functions of independent variables, the underlying functions in our problems are highly related to the graph structure. For example, BA networks are known for rich structural information due to the scale-free characteristics (i.e. node degree is exponentially distributed), which makes the distribution of the original signal heavily right-skewed with extreme values even after standardization (Fig.2 Left). By contrast, the WS small-world network (randomly rewired from a ring) has more homogeneous node degrees, and thus the original signal will be more normally distributed after standardization (Fig.2 Right).

Therefore, the noise level (even at $\sigma=1$) is less significant on BA networks when the algorithm finds the promising region, Whereas on WS networks at $\sigma=1$, just as the reviewer described, we can see the algorithm is “misguided” by the observations compared to the posterior mean when the signal is highly corrupted.

Comparison with COMBO on small graphs

We thank the reviewer for acknowledging our different problem settings from COMBO. As suggested, we have implemented COMBO on smaller BA and WS networks of 500 nodes, which are still much larger than the ones used in their experiments ($|V|<50$). The results are presented in Fig. 4 in the rebuttal PDF, and we can see a clear advantage of our framework over COMBO. Please refer to the general response for a more detailed analysis.

We’d like to thank the reviewer again for the insightful comments, and we will make sure to include the above discussion in the revised version. We believe that we have now addressed all the concerns from the reviews, and hope the reviewer could kindly consider increasing the rating in light of this.

We thank the reviewer for the prompt engagement in the rebuttal, as well as their increased positive rating of our work. Please see our following explanations regarding the choice of GraphComBO (observation-guided) and GraphComBO-Noisy (posterior mean-guided).

• Under the noiseless setting in our experiments (e.g. synthetic experiments with centrality measures), the difference in their performance is minimal after we tried both methods on several synthetic graphs with different synthetic functions, where GraphComBO only slightly outperforms GraphComBO-noisy in a few cases when $k$ is relatively big.

• Under the noisy setting, (e.g. the new experiment in our rebuttal and the real-world experiments involving simulation results), we observed that GraphComBO-Noisy has a clear advantage over the observation-guided method when the noise level is high.

Since we often lack prior knowledge of the noise level when first encountering signals in real-world experiments, we will set the suggested GraphComBO-Noisy as the default option, given its overall performance across different settings, while retaining the observation-guided method in the revised version for noiseless scenarios.

We thank the reviewer again for the suggested method and will make sure to incorporate the above changes in the main manuscript. We are more than happy to discuss any additional improvements that would make the reviewer evaluate our work more positively and potentially further raise the rating.

We thank the reviewer for the detailed feedback that helped us improve our work. Please find our detailed response below.

The empirical evaluation would benefit from including other BO baselines. I believe that LADDER could be a particularly strong candidate.

To the best of our knowledge, this is the first attempt in the literature at extending BO to black-box optimization of functions over node subsets in a generic graph, which means we are addressing a new problem setup that has not been explored by existing works.

For LADDER, we argue that their setting is fundamentally different from ours, where their underlying function (from their experiments) is defined on graph structures, i.e., their search space consists of different graphs and the goal is to find the optimal graph, which requires a graph kernel to measure the similarity between two graphs. However, in our setting, the underlying function is defined on node subsets from a single graph. After mapping the subsets to nodes on the combo-graph, a kernel on graph is required to measure the similarity between two nodes.

The closest match to the current work is COMBO, where the search space consists of node subsets from different (small) graphs ($|V|<50$ in their experiments with $k<50$). Nevertheless, it can not scale to large graphs due to the infeasible computational cost from the eigendecomposition of the underlying graphs.

With that being said, we have added the comparison with COMBO in the general response on small BA and WS graphs of $|V|=500$ (still much larger than the graphs in their experiments), where the result (Fig.4 rebuttal PDF) shows a clear advantage of our framework over COMBO.

We will add the above discussion in the revised version and are happy to discuss more if the reviewer believes there are works in the literature that tackle the same problem as ours.

Real-world application networks are typically much larger than those considered in the empirical evaluation. I believe this approach is restricted to graphs significantly smaller than those typically encountered in real-world applications.

Firstly, we validated our method across various real-world applications on contact networks, social networks, transportation networks, and molecule graphs that scale from order $10^2$ to $10^4$. This is consistent with the real-world graphs used in graph machine learning (e.g. graph neural networks: GCN, GAT, GIN) and graph data mining literature (e.g. influence maximization [1,2,3]), which are in the same order as ours -- based on this, we believe the graphs considered are comparable to the literature and not "significantly smaller" than realistic graphs.

Second, the graphs considered in other graph-related BO works, e.g. LADDER (mentioned by the reviewer), COMBO, NASBO, GRABNEL, are much smaller than ours, which are typically at order $10^1$ and $10^2$.

A new experiment on larger network with larger subset size $k$

Lastly, our framework can scale to large graphs, as it assumes no prior knowledge of the full graph and takes a local modeling approach that gradually reveals the graph structure. To better support our claim, we further test it on a large social network OGB-arXiv ($|V|=1.7\times10^5$) from open graph benchmark with $k$ up to 128, where the results in Fig.1 (rebuttal PDF) show a clear advantage of our framework over the other baselines.

Additionally, larger values of k are likely to be of interest in these applications. The current results suggest that the proposed approach may not offer improvements over some baselines in these more challenging scenarios.

We argue that setting $k<50$ (<1% of the network) is very a common paradigm in the literature of subset selection on graphs [1,2,3], which has been proven to be NP-hard in many problems due to the combinatorial explosion in search space $\binom{N}{k}$, e.g. $\binom{1000}{32}\approx2.3\times10^{60}$. As such, the diminishing performance gain w.r.t. subset size $k$ poses a general challenge in the literature [4], and it becomes even more challenging in our setting, since the underlying function is fully black-boxed and we assume no prior information of the graph structure.

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

The technical novelty is somewhat limited, as the proposed approach mainly combines BayesOptG over the combo graph with a local search heuristic.

As the prior work BayesOptG only considers $k=1$, which is limited for many real-world applications, we aim to generalize the framework to a combinatorial setting with the following technical contributions:

1. A combinatorial graph tailored for node subsets in a generic graph.
2. A recursive algorithm to sample subgraphs from the combinatorial space.
3. To handle the combinatorial explosion problem, we use a local approach to traverse the combinatorial graph space by iteratively sampling its subgraphs.

In the early stage, we tried other localization methods such as selecting nodes inside a subgraph on the original graph as the subset. However, since we need to maintain the diversity of the subset to cover potentially distant nodes, none of them can fit into the problem as cohesively as the current method, which makes our design non-trivial.

For the variable size of the subset, we believe it belongs to a different but interesting setup, and leave it to future work for exploration. And for the graph-theoretic concepts, we will make sure they are clear in the revised version.

We believe that we have now addressed all the concerns from the original reviews, and hope the reviewer could kindly consider increasing the rating in light of this.

Please find the references in the comment chatbox below.

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

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

[3] Robust Influence Maximization, KDD 2016

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

Dear Reviewer u7DA,

As the discussion period is drawing to a close, we'd like to kindly remind you of our rebuttal, and we remain keen to discuss the issues being raised and further improve the quality of our work.

Thank you again for your time and efforts in reviewing our manuscript, and we are looking forward to your response.

Best,

Authors of Submission #4018