| Network science with networks as the main research objects is the key to reveal the internal laws of complex systems and release the value of big data.Its forming theoretical and algorithmic framework will become a new driving force in many fields.The topological structure and attributes of the network jointly determine the function and dynamic characteristics of the networks.Therefore,a basic research problem in network science is: how to design network topological structure and attributes with optimal function or dynamic characteristics,namely Network Optimization Problems.At present,random search,evolutionary algorithms and reinforcement learning have been used to solve network optimization problems in various fields.However,most of these methods ignore the evaluation cost of the networks.To avoid the optimization process falling into local optimum,they usually need to evaluate a large number of individuals to maintain the diversity of the population or training set.They,thus,need to consume too much computational resources and time when handling problems with high evaluation cost and huge search space.How to break through the limitations of existing methods and improve the quality of solution while significantly reducing the evaluation cost is the key to greatly shorten the design cycle and save the cost.However,the problem is very challenging,and no breakthrough has been made so far.Bayesian optimization is a model-based global optimization algorithm,which is extremely suitable for optimizing the expensive-to-evaluate black-box functions.This is just in line with the characteristics of network optimization problems and is expected to provide an ideal general solution for cost-aware network optimization.Based on the above,the paper raises to study: how to bring the advantages of Bayesian optimization into the network optimization problems,in order to obtain the network with the optimal objective and at as low evaluation cost as possible.To tackle this problem,this paper proposes three noval Bayesian graph optimization methods:1)A Bayesian graph optimization based on kernel learning.This method uses a vectoral kernel function to process explicit features,and feeds the networks into the graph kernel function directly to extract hidden features,which integrates the topological structure and the global attributes of the graph.Simultaneously,it can automatically learn the importance of features and the cognitive degree of objective optimization problems.The proposed method is applied to solve several practical network optimization tasks,including reliable network design of infrastructure system,identification of the most active nodes in social network and urban traffic network design.In these real-world tasks,our method obtains the optimal solution with the least evaluation cost.At the same time,we propose a new benchmark for road network optimization: the problem of opening the gated residential areas.To our knowledge,this is the first work to apply the Bayesian optimization to deal with this problem.In addition,we suggest to cooperate with other machine learning technologies to increase the interpretability of the optimization process.In the problem of opening the gated residential areas,we found some instructive and transferable knowledge rules to assist experts in decision-making.2)A Bayesian graph optimization based on deep learning.This method is the first work to integrate graph neural network and Bayesian optimization.It makes full use of the topological structure and all attribute information,reducing the evaluation cost and speeding up the optimization process.As the new deep probabilistic surrogate models based on graph neural network can automatically extract graph features in a data-driven fashion,it can avoid the complicated work of manually designing graph kernel function in the first work of this paper,and can be directly extended to other fields.The time complexity and theoretical convergence of the method are also analyzed,which is the first work to theoretically confirm the convergence guarantee in deep Bayesian optimization content.The proposed method is applied to various problems such as molecular discovery in chemistry,road network optimization in transportation and neural architecture search in automatic machine learning.The experimental results show that the structure-related attributes can indeed help network optimization tasks;the proposed method can obtain optimal or near optimal solutions on all tasks,and can significantly reduce the evaluation cost compared with the state-of-the-art technologies in various fields.3)A Bayesian graph optimization based on generation model.The goal-oriented graph generation model provides a potential solution for network optimization.From a perspective of cost-aware graph generation,we propose a general generation modelbased Bayesian graph optimization to generate the new networks with the optimal goal at as low cost as possible.This method can handle the the high evaluation cost of current generation methods in dealing with real-world tasks,and can break through the limitation of the proposed first two work in this paper which need to give a candidate set in advance.It is an iterative process.Its main idea is to use the generation model to produce an expected network set close to the optimal goal at each iteration,and then use deep Bayesian optimization to choose the most potential network from the candidates for evaluation.We apply the proposed method to solve the two challenging practical tasks including molecular discovery and neural architecture search.The experimental results show that this method can generate the optimal networks and save30% to 95% of the evaluation cost compared to the state-of-the-art technologies.We believe that the three Bayesian graph optimization methods proposed in this paper provide effective,efficient and potential solutions for expensive-to-evaluate network optimization problems in various fields,such as drug design,crystal structure optimization,circuit design,traffic network optimization and material design. |
PDF Full Text Request