Efficient graph neural architecture search using Monte Carlo Tree search and prediction network

Graph Neural Networks (GNNs) have emerged recently as a powerful way of dealing with non-Euclidean data on graphs, such as social networks and citation networks. Despite their success, obtaining optimal graph neural networks requires immense manual work and domain knowledge. Inspired by the strong searching capability of neural architecture search in CNN, a few attempts automatically search optimal GNNs that rival the best human-invented architectures. However, existing Graph Neural Architecture Search (GNAS) approaches face two challenges: (1) Sampling GNNs across the entire search space results in low search efficiency, particularly in large search spaces. (2) It is pretty costly to evaluate GNNs by training architectures from scratch. To overcome these challenges, this paper proposes an Efficient Graph Neural Architecture Search (EGNAS) method based on Monte Carlo Tree Search (MCTS) and a prediction network. Specifically, EGNAS first uses MCTS to recursively partition the entire search space into good or bad search regions. Then, the reinforcement learning-based search strategy (also called the agent) is applied to sample GNNs in those good search regions, which prevents overly exploring complex architectures and bad-performance regions, thus improving sampling efficiency. To reduce the evaluation cost, we use a prediction network to estimate the performance of GNNs. We alternately use ground-truth accuracy (by training GNNs from scratch) and prediction accuracy (by the prediction network) to update the search strategy to avoid inaccuracies caused by long-term use of the prediction network. Furthermore, to improve the training efficiency and stability, the agent is trained by a variant of Proximal Policy Optimization. Experiments show that EGNAS can search for better GNNs in the promising search region in a shorter search time, with an accuracy of 83.5%, 73.3%, 79.6%, and 94.5% on Cora, Citeseer, Pubmed, and Photo datasets, respectively In particular, compared to the most popular GNAS algorithm, our EGNAS-NP without using the prediction network achieves an accuracy of 83.6% on Cora, 73.5% on Citeseer, 79.9% on Pubmed, and 94.6% on Photo, with a relative improvement of 0.6%, 0.2%, 0.7%, and 0.6%.