<p>In recent years, graph learning has achieved impressive advances with the development of deep networks for graph data. However, unlike images, texts or voices, graph datasets are usually in small size, causing the failure of deep network training due to over-fitting and limiting the generalization capacity of trained networks. Moreover, collecting large graph datasets is costly with a lot of effort, and sometimes needs expertise, becoming impossible in many scenarios. To address this issue, data augmentation is a widely-used solution to expand the training sets by applying transformations to original data to generate more diverse samples. Unfortunately, this approach is losing its power for graph data because graph labels can be unexpectedly changed under graph transformation operations, adding more noise to the data. In this paper, we propose a novel data augmentation for graphs to handle the lack of training data by 1) casting the original multi-class graph classification into the harder problem of multi-label classification and thus preventing from over-fitting when data samples are too easy for networks to learn, and 2) applying multi-label mixup to diversify the training samples without introducing generated graphs with wrong labels. Experiments on benchmark datasets demonstrate the significant improvement of our proposed method in comparison with other state-of-the art graph augmentation techniques for graph classification problem.</p>