摘要
A recent line of research on learning to solve graph optimization problems has attracted much research attention. However, most recent machine learning approaches to graph optimization problems usually employ graph generators to randomly generate training graphs, which may lead to overfitting and deteriorate the model's generalization. To tackle this issue, we observe that enhancing the diversity of training graphs is a crucial factor in improving the model's performance. Therefore, in this paper, we formulate a new research problem, named Graph Augmentation for Diversity Maximization (GRAM), to maximize the training graph diversity by performing graph modifications. We first analyze the NP-hardness of GRAM. We then propose a 2-approximation algorithm and formally analyze its performance guarantee. Experimental results on well-known graph optimization problems show that our proposed approach significantly outperforms the baselines, such as graph augmentation and deep learning-based graph generation approaches.