Learning to Augment Graph Structure for Both Homophily and Heterophily Graphs

Abstract

Recent years have witnessed great successes in performing graph structure learning for Graph Neural Networks (GNNs). However, comparatively little work studies structure augmentation for graphs, where the augmented structures are only used for training and are not available during inference. This is mainly due to that structure augmentation is a discrete combinatorial optimization problem rather than a continuous optimization problem like structure learning. In this paper, we propose Learning to Augment (L2A), a novel structure augmentation framework that learns customized augmentation strategies for graphs with different homophily levels. Specifically, L2A simultaneously performs the maximum likelihood estimation of GNN parameters and the learning of optimal structure augmentations in a variational inference framework. Moreover, L2A applies two auxiliary self-supervised tasks to exploit both global position and label distribution information in the graph structure to further reduce the reliance on annotated labels and improve applicability to heterophily graphs. Extensive experiments have shown that L2A can produce truly encouraging results at various homophily levels compared with other leading methods and can learn customized structure augmentation strategies across various GNNs architectures and graph datasets. Codes are available at: https://github.com/LirongWu/L2A .