Through the Dual-Prism: A Spectral Perspective on Graph Data Augmentation for Graph Classification

Graph Neural Networks (GNNs) have become the preferred tool to process graph data, with their efficacy being boosted through graph data augmentation techniques. Despite the evolution of augmentation methods, issues like graph property distortions and restricted structural changes persist. This leads to the question: Is it possible to develop more property-conserving and structure-sensitive augmentation methods? Through a spectral lens, we investigate the interplay between graph properties, their augmentation, and their spectral behavior, and found that keeping the low-frequency eigenvalues unchanged can preserve the critical properties at a large scale when generating augmented graphs. These observations inform our introduction of the Dual-Prism (DP) augmentation method, comprising DP-Noise and DP-Mask, which adeptly retains essential graph properties while diversifying augmented graphs. Graph structures, modeling complex systems through nodes and edges, are ubiquitous across various domains, including social networks (Newman et al., 2002), bioinformatics (Yi et al., 2022), and transportation systems (Jin et al., 2023a). Graph Neural Networks (GNNs) (Kipf & Welling, 2016a) elegantly handle this relational information, paving the way for tasks such as accurate predictions. Their capabilities are further enhanced by graph data augmentation techniques. These methods artificially diversify the dataset through strategic manipulations, thereby bolstering the performance and generalization of GNNs (Rong et al., 2019; Feng et al., 2020; You et al., 2020). Graph data augmentation has progressed from early random topological modifications, exemplified by DropEdge (Rong et al., 2019) and DropNode (Feng et al., 2020), to sophisticated learning-centric approaches like InfoMin (Suresh et al., 2021). Furthermore, techniques inspired by image augmentation's mixup principle (Zhang et al., 2017) have emerged as prominent contenders in this domain (Verma et al., 2019; Wang et al., 2021; Guo & Mao, 2021). Though promising, these augmentation methods are challenged by three key issues as follows. Before the era of deep learning, graph properties, e.g., graph connectivity and diameter, served as vital features for classification for decades (Childs et al., 2009). While now they seem to be ignored, many aforementioned contemporary augmentation methods appear to sidestep this tradition and overlook the graph properties.