TY - JOUR
T1 - A novel framework of graph Bayesian optimization and its applications to real-world network analysis
AU - Cui, Jiaxu
AU - Tan, Qi
AU - Zhang, Chunxu
AU - Yang, Bo
N1 - Publisher Copyright:
© 2020 Elsevier Ltd
PY - 2021/5/15
Y1 - 2021/5/15
N2 - Network structure optimization is a fundamental task of many expert and intelligent systems, such as the intelligent tools for chemical molecular discovery and expert systems for road network design. However, traditional model-free methods suffer from the expensive computational cost of evaluating networks; almost all the research on Bayesian optimization is aimed at optimizing the objective functions with vectorial inputs, e.g., the hyper-parameters in any expert systems. This work focuses on applying Bayesian optimization to optimize network structure with graph-structured inputs, and presents a flexible framework, denoted as graph Bayesian optimization (GBO), to handle arbitrary graphs. By combining the proposed framework with graph kernels, it can take full advantage of implicit graph structural features to supplement explicit features guessed according to the experience, such as tags of nodes and any attributes of graphs. Simultaneously, the proposed framework can identify which features are more important during the optimization process. By collaboratively working with a down-stream decision tree, the GBO can not only find the optimum but also discover its knowledge represented by rules, which can further enhance its interpretability and assist expert decision-making. A novel problem of opening the gated residential areas is presented in this work, which can serve as one benchmark task of road network design. Intensive experiments conducted on three real-world applications, including robust network design, the most active node identification, and urban transportation network design, demonstrate its efficacy and potential applications.
AB - Network structure optimization is a fundamental task of many expert and intelligent systems, such as the intelligent tools for chemical molecular discovery and expert systems for road network design. However, traditional model-free methods suffer from the expensive computational cost of evaluating networks; almost all the research on Bayesian optimization is aimed at optimizing the objective functions with vectorial inputs, e.g., the hyper-parameters in any expert systems. This work focuses on applying Bayesian optimization to optimize network structure with graph-structured inputs, and presents a flexible framework, denoted as graph Bayesian optimization (GBO), to handle arbitrary graphs. By combining the proposed framework with graph kernels, it can take full advantage of implicit graph structural features to supplement explicit features guessed according to the experience, such as tags of nodes and any attributes of graphs. Simultaneously, the proposed framework can identify which features are more important during the optimization process. By collaboratively working with a down-stream decision tree, the GBO can not only find the optimum but also discover its knowledge represented by rules, which can further enhance its interpretability and assist expert decision-making. A novel problem of opening the gated residential areas is presented in this work, which can serve as one benchmark task of road network design. Intensive experiments conducted on three real-world applications, including robust network design, the most active node identification, and urban transportation network design, demonstrate its efficacy and potential applications.
KW - Bayesian optimization
KW - Graph kernels
KW - Graphs
KW - Networks
KW - Structure optimization
UR - http://www.scopus.com/inward/record.url?scp=85099460923&partnerID=8YFLogxK
U2 - 10.1016/j.eswa.2020.114524
DO - 10.1016/j.eswa.2020.114524
M3 - Journal article
AN - SCOPUS:85099460923
SN - 0957-4174
VL - 170
JO - Expert Systems with Applications
JF - Expert Systems with Applications
M1 - 114524
ER -