  Attributed graphs, which contain rich contextual features beyond just network
structure, are ubiquitous and have been observed to benefit various network
analytics applications. Graph structure optimization, aiming to find the
optimal graphs in terms of some specific measures, has become an effective
computational tool in complex network analysis. However, traditional model-free
methods suffer from the expensive computational cost of evaluating graphs;
existing vectorial Bayesian optimization methods cannot be directly applied to
attributed graphs and have the scalability issue due to the use of Gaussian
processes (GPs). To bridge the gap, in this paper, we propose a novel scalable
Deep Graph Bayesian Optimization (DGBO) method on attributed graphs. The
proposed DGBO prevents the cubical complexity of the GPs by adopting a deep
graph neural network to surrogate black-box functions, and can scale linearly
with the number of observations. Intensive experiments are conducted on both
artificial and real-world problems, including molecular discovery and urban
road network design, and demonstrate the effectiveness of the DGBO compared
with the state-of-the-art.
