Bayesian Optimisation of Functions on Graphs

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.

Strengths

1. Novelty: good observation on the lack of Bayesian optimization framework on node-level tasks. 2. Soundness: the three kernels, especially the latter two, are well presented. Their functions in the BO process is well explained and persuasive. 3. Clarity: Figure 2 and Algorithm 1 help the paper with information presentation. Most entities are well-defined.

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. 2. 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) 3. Typo in Algorithm 1. 2: Output: the node that v^*_T that minimises the objective function. Extra "that", and "minimizes". (Solved) 4. Figure 2 wrong reference. "to the central node (Eq. (??) in the figure)". (Solved)

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.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

N/A

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.

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). + The local modeling makes the approach to scale up for large-scale graph, potentially unknown graph. + The authors also propose two kernels for Bayesian optimization for functions on graph (which are variant of the diffusion kernel on graph) + 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. + Some important part needs to elaborate with details, e.g., especially selecting the local subgraph; why the proposed approach can handle potential unknown graph?

Questions

The flow of the submission is clear. However, it is better in case the authors elaborate more details for some important parts. + 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. + 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? + 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. + It is unclear how the proposed algorithm can handle unknow graphs as claimed? Could the authors elaborate it with more details? + It is better to elaborate more details about the Algorithm 1 and 2 in the main text, especially the Algorithm 2. + 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?) Some minor points: + What is $\tilde{A}$ in line 140? There is no explanation for it. + Reference for Equation in Figure 2 --- I thank the authors for the rebuttal.

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

The authors have not discussed the limitations and potential negative societal impact of their work.

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.

Strengths

* The problem defined on a graph has not been studied much. This topic in particular is interesting in the Bayesian optimization community. * 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. * Analysis on the investigated methods is lacked. * Discussion on local search strategies is weak. * Experimental results seem not consistent. * Writing can be improved.

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. 2. 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. 3. Basically, the experimental results are hard to interpret. Figures are too small and lines are too thin. 4. The number of evaluations is too small. 5. 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. 6. 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?

Rating

3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

I do not think that this work has specific limitations.

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.

Strengths

This paper addresses a novel problem, the discussion is compelling and the results appear to be sound.

Weaknesses

(see questions below). Minor point: figure 2 - equation (??).

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. - 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?

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

N/A

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: 1. 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. 2. 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. 3. 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.

Strengths

1. This work extends the BO based methods to the functions defined over the nodes of graph. 2. 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. 3. Clear introduction of the problem setup and where exactly the BO is being applied. 4. 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]. [1] Valko, Michal, et al. "Spectral bandits for smooth graph functions." International Conference on Machine Learning. PMLR, 2014. [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.

Questions

Questions - 1. Can you please provide a bit of background on why the kernels mentioned in the paper would result in semi positive definite covariance matrices? 2. 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? Suggestions - 1. Check the captions of Figure 2 and caption of figure 3 is hard to follow. 2. Few acronyms were introduced after they were used in prior sections. ex. BA and WS in section 5.1. 3. Section A2 introduction BFS and DFS is probably jumbled. [3] Borovitskiy, Viacheslav, et al. "Matérn Gaussian processes on graphs." International Conference on Artificial Intelligence and Statistics. PMLR, 2021.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

N/A

Clarification on the definition of "scalability" in the rebuttal

We'd like to provide a quick clarification regarding *scalability* when we discuss previous works in BO: When we argued that "the main objective of trust regions in prior BO works is not for scalability" in the rebuttal, we were referring to the scalability in terms of *the number of training points* -- this is also the definition used in seminal papers like [1]. However, if we use a broader definition to include scalability to *the number of dimensions*, we agree that trust regions also help scalability in prior BO literature as they improve the performance of GPs in high dimensions. Despite any definitional differences, our core argument still stands: in prior BO methods, trust regions are mainly used to improve GP performance in high dimensions rather than to accommodate more data. In our case, local subgraphs achieve both: they both restrict the GP's attention to a promising subregion similar to trust regions but also make BO more scalable to more training points, as the GP defined on graphs also scale cubically w.r.t the number of nodes $n$, in addition to the number of training points $N$ with $\mathcal{O}(n^3+N^3)$. Using subgraphs ensures $n$ is tractable -- empirical evidence of this is provided in Fig. S6 of the rebuttal PDF. We thank the reviewer once again for their comments. ### References [1] Liu, H., Ong, Y. S., Shen, X., & Cai, J. (2020). When Gaussian process meets big data: A review of scalable GPs. IEEE transactions on neural networks and learning systems, 31(11), 4405-4423.

Author discussion

We thank all reviewers once again for their feedback. We believe we have largely addressed the concerns in the reviews, and we'd really appreciate it if the reviewers could look at the author feedback. We are always happy to answer any remaining questions they may have.