LSPAN: Spectrally Localized Augmentation for Graph Consistency Learning

1 Introduction

Graph machine learning receives considerable attention in recent years due to its ability of exploiting rich information encoded in non-Euclidean data and has been applied to many real-world applications [Fout et al., 2017; Yao et al., 2019; Wu et al., 2020a]. One of the main focuses of this field, graph semi-supervised learning [Zhu et al., 2003; Kipf and Welling, 2017], aims to classify unlabeled nodes in a scarcely labeled graph [Wu et al., 2020b]. However, although Graph Neural Networks (GNNs) [Gori et al., 2005; Scarselli et al., 2008; Kipf and Welling, 2017; Veliˇckovi´c et al., 2018; Hamilton et al., 2017] are introduced to provide powerful solutions for this task, unlabeled nodes that are abundant and informative in practical scenarios [Zhou, 2018; Li et al., 2019; Miyato et al., 2018] are usually not well used - GNNs are trained only over predictions of labeled nodes and the unlabeled nodes are not involved. Recently, graph consistency learning [Park et al., 2021; Bo et al., 2022; Feng et al., 2020] shows a promising framework for utilizing unlabeled nodes by minimizing the predictions divergence of them across different augmented graphs [Zhao et al., 2022; Ding et al., 2022].

∗Corresponding author

Designed for exploiting invariant information with augmented graphs, the performance of graph consistency learning highly relies on the quality of adopted graph augmentation methods. Existing graph augmentation approaches are usually divided into two categories: topology-based approaches [Rong et al., 2020; Zhao et al., 2021; Lin et al., 2023] generate different graph structures by perturbing the adjacency matrix; feature-based approaches [Deng et al., 2019; Feng et al., 2019; Kong et al., 2020; Liu et al., 2022b] perturb node attributes within the feature matrix. In general, previous approaches typically define graph augmentation in the spatial domain (i.e., they work by perturbing either graph structures or node features). Note that although there are recent works like SPAN [Lin et al., 2023] considering spectral information, the spectral knowledge is only used for supervising edge or feature perturbations and they still fall into spatial augmentations.

In this paper, we suggest existing spatial-based augmentation methods can be improved from a new spectral perspective. Specifically, the structure of graph spectrum proves critical in revealing significant graph properties both structurally and semantically [Chung, 1997; Kahale, 1995; Lee et al., 2014; Hammond et al., 2013]. Therefore, preserving the informative spectrum structure is crucial to ensure a good model performance. However, in spatial-domain-based augmentation approaches, the spectrum of an input graph is perturbed at all range of graph frequencies. For example, when an edge is dropped, the spectrum on all Fourier bases can be modified. We define this kind of augmentation as spectrally nonlocalized. In such cases, the relative intensity and location between different spectrum components can be significantly altered and structure of graph spectrum can be largely changed, which may lead to notable information loss in augmented graphs and therefore hinder graph learning. To this end, we hope to design a graph augmentation approach that is able to enhance the preservation of the graph spectrum structure, so as to improve the performance of graph consistency learning.

One promising solution is to keep the majority of graph spectrum unchanged by only perturbing a concentrated part of it, which is named by Localized SPectral AugmentatioN

(LSPAN). Specifically, in LSPAN approach, graph spectrum is not perturbed in the entire frequency range. By contrast, only a small localized "block" of spectrum is modified. In this way, the informative graph spectrum is mostly retained and the graph information can be better preserved, which ensures a better generalization performance for model prediction. This is illustrated in Figure 1 - the graph spectrum is only perturbed within a small scope and is mostly retained in LSPAN method, but the overall spectrum structure is largely changed in non-localized ones. Figure 2 shows the prediction accuracy of GCN on original CORA graph, CORA perturbed by non-localized methods and LSPAN (respectively with drop node/edge probability around 0.5 and spectral perturbation rate around 1/20, which are used in prior works [Feng et al., 2020; Liu et al., 2022b] and ours to report final results to ensure fair comparison). We observe that the performance of graph learning decreases significantly with non-localized augmentations while LSPAN still maintains a good performance, which verifies that the graph information is lost much in non-localized augmentations but well preserved in the proposed LSPAN.

To implement LSPAN, we directly define graph augmentation in the spectral domain. To avoid the time-consuming inverse Fourier transform during training, we introduce the Fourier basis orthogonality, which enables LSPAN to be efficiently performed by simple feature concatenation. Extensive empirical evaluation on real-world benchmarks clearly shows the significant performance gain of our method, as well as good convergence properties compared to existing ones.

We summarize our main contributions as follows:

• We identify that existing graph augmentations can cause graph information loss because they are non-localized in spectral domain - graph spectrums that contain important graph information are perturbed over the entire frequency range and their structures can be largely changed.
• We propose a novel spectrally localized augmentation method called LSPAN, which only perturbs the graph spectrum within a small frequency scope and therefore ensures a better preservation of the graph information.
• We conduct extensive empirical studies on six real-world benchmark datasets across four domains, which clearly show the advanced performance of our proposed method.

2 Preliminaries

Notations. Let G = (X,A) be a connected undirected graph with N nodes and E edges. X ∈ RN×F denotes the feature matrix, where F indicates the number of node features. A ∈ {0, 1}N×N denotes the adjacency matrix, where Aij = 1 if edge exists between node i and j and Aij = 0 otherwise. Then, the graph Laplacian is defined as L = D-A ∈ RN×N , where D indicates the diagonal degree matrix, namely Dii = ∑j Aij. The symmetric normalized adjacency matrix is further defined as ˆA = ˜D- 12 ˜A˜D- 12 , where ˜A represents the adjacency matrix for a graph with added self-loops and ˜D is the diagonal degree matrix of ˜A.

Consistency-Based GNN Methods. Consistency-based graph semi-supervised learning [Park et al., 2021; Bo et al., 2022; Feng et al., 2020] provides powerful framework for exploiting unlabeled nodes by minimizing the prediction divergence of them across different augmented graphs G′ = (X′ ,A′ ) [Zhao et al., 2022; Ding et al., 2022], where X′ and A′ indicate the augmented feature and adjacency matrix. They generally expand the loss function as: L = Lsup + γLcon, where Lsup indicates the supervised loss calculated on different graph views, Lcon indicates the consistency regularization loss used for smoothing the label predictions across augmented graph samples and γ controls the strength of it. Augmented graphs are significantly involved in the calculation of Lsup and Lcon. Therefore, the performance of graph consistency learning highly relies on the quality of adopted augmentation approaches. Our work focuses on designing an augmentation method that is spectrally localized and improves the graph spectrum preservation, so as to enhance the model performance. Next, we briefly review the graph spectrum theory.

Introduction to Graph Spectrum. Digital Signal Processing converts a signal into spectral domain and is adopted for graphs by Graph Fourier transform (GFT) [Shuman et al., 2013]. Specifically, In GFT, the real symmetric matrix L is orthogonally diagonalized by: L = UΛUT . We define the eigenvalues {λi}Ni=1 in Λ as graph frequencies (we assume that λ1 ≤ λ2 · · · ≤ λN). They reveal the distribution of graph spectrum and decide where spectrum components are located. We further define the graph Fourier transform as: ˜X=UT X and inverse graph Fourier transform as: X = U˜X, where X indicates the input graph feature matrix and ˜X the feature matrix projected into the spectral domain. In particular, the i-th column ui of U is defined as the Fourier basis at frequency λi and ˜xi = uTi X is the projection of the graph features on this basis, which therefore reveals the strength of spectrum at frequency λi. Overall, frequencies {λi}Ni=1 decide where components of spectrum are located and feature projections {˜xi}Ni=1 reveal the strength of them. The graph spectrum encoded in {λi}Ni=1 and {˜xi}Ni=1 significantly reveals graph properties and is highly desired to be preserved for good learning performance [Chung, 1997; Kahale, 1995; Lee et al., 2014; Hammond et al., 2013].

3 LSPAN: Spectrally Localized Augmentation on Graphs

In this section, we introduce the proposed Localized SPectral AugmentatioN (LSPAN) to preserve important graph spectrum structure for graph consistency learning. Specifically, we first view graph augmentations from the spectral perspective and define spectrally localized graph augmentation based on this. Then, we implement the localized graph augmentation with orthogonality of Fourier bases, which totally avoids the timeconsuming training time Fourier inverse transform and makes our method easily applicable.

3.1 Viewing Graph Augmentation from the Spectral Perspective

To define spectrally localized augmentation on graphs, we first formalize the graph augmentations in the spectral domain by viewing them as perturbations to graph frequencies and feature projections.

Specifically, as mentioned in Section 2, the spectrum of a graph is encode in {λi}Ni=1 and {˜xi}Ni=1 , where {λi}Ni=1 are eigenvalues of graph Laplacian L = D - A and are defined as graph frequencies, which reveal the location distribution of spectrum components. On the other hand, {˜xi}Ni=1 are projections of input graph feature matrix on Fourier bases {ui}Ni=1 , namely ˜xi = uTi X. ui is the i-th eigenvector of graph Laplacian and defined as the Fourier basis at frequency

λi. Therefore, ˜xi is the feature projection on this basis and reveals the strength of spectrum component at frequency λi.

By this, graph augmentations in the spectral domain can be defined by perturbations on graph frequencies {λi}Ni=1 and feature projections {˜xi}Ni=1 as follows:

Definition 1 (Spectral Augmentation on Graphs). Given a graph with frequencies {λi}Ni=1 and feature projections {˜xi}Ni=1 , the spectral augmentation on it is defined as:

where constant ∆λi and vector ∆˜xi denote the perturbations on the i-th graph frequency and i-th feature projection. P is a set of numbers indicating the locations of perturbed spectrum components.

Based on this, spatial graph augmentations can be formalized in spectral domain as follows:

The proofs are deferred to Appendix A. We observe that, feature augmentation only perturbs strength of spectrum components revealed by projections ˜xi while topology augmentation also perturbs locations of spectrum components revealed by frequencies λi. However, regardless of the kind of perturbation, the entire range of spectrum components can be perturbed (i = 1, 2, · · · ,N) and the spectrum structure may deviate from the original one - usually ∆λi ̸= ∆λj and ∆˜xi ̸= ∆˜xj , which means the relative intensity and location of spectrum components can be significantly altered. Therefore, we propose to better retain the spectrum structure by narrowing and localizing the range of perturbation.

3.2 Defining Spectrally Localized Augmentation

To improve the preservation of graph spectrum, we propose to use spectrally localized augmentation where we only perturb a concentrated part of the spectrum. In this way, we restrict the range of perturbable spectrum to a localized "block" and the informative spectral-domain structure is mostly retained. Specifically, the localized augmentation is defined as follows:

Definition 2 (Localized Spectral Augmentation on Graphs). Given a graph with frequencies {λi}Ni=1 and feature projections {˜xi}Ni=1 , the localized spectral augmentation on it is defined as:

where vector ∆˜xi denotes the perturbation on the i-th feature projection.

We ensure m ≥ 1 and m + n ≤ N + 1. As can be seen, in proposed localized augmentation, frequencies {λi}Ni=1 remain unchanged and feature projections {˜xi}Ni=1 are only perturbed within a concentrated frequency range (i ∈ [m, m + n - 1]). In this way, only n spectrum components are perturbed and the structure of graph spectrum is better preserved as shown in Figure 1.

After performing augmentation in the spectral domain, we then transform the perturbed graph back to spatial domain for graph consistency learning. Specifically, we aim to recover the graph G′ with adjacency matrix A′ and feature matrix X′ from augmented frequencies and feature projections {λ′i , ˜x′i }Ni=1 = {AUG(λi, ˜xi)}Ni=1 . As frequencies {λi}Ni=1 remain unchanged, we simply let A′ = A to preserve the graph Laplacian. Then, the feature matrix is recovered by inverse Fourier transform: X′ = U˜X′ . Remind that U is the eigenvector matrix of graph Laplacian, namely L = UΛUT . ˜X′ denotes the augmented feature projection matrix composed of {˜x′i }Ni=1 , namely ˜X′ = [˜x′T 1 , ˜x′T 2 , · · · , ˜x′T N ]T . Overall, we let A′ = A and X′ = U [˜x′T 1 , ˜x′T 2 , · · · , ˜x′T N ]T .

However, in this augmentation, although matrix U and vectors {˜xi}Ni=1 are pre-calculated, the application of Fourier inverse transformX′ =U˜X′ is time-consuming. To address this issue, we simplify the localized augmentation and use the orthogonality of Fourier bases to implement it.

3.3 Implementing Localized Augmentation with Fourier Orthogonality

To avoid time-consuming Fourier inverse transform at training time, we implement localized spectral augmentation with the orthogonality of Fourier bases. By this, the proposed augmentation can be performed by simple feature concatenation in spatial domain and the training time Fourier transform is totally avoided. Specifically, we first redefine the localized augmentation as:

where two simplification tricks are applied. First, the perturbation to feature projection is redefined as (˜xi +∆˜xi) → [˜xi ; T] where [· ; ·] indicates vector or matrix concatenation and the constant T acts as the "temperature" that controls the intensity of perturbation. Second, the spectrum components are perturbed with same intensity constant T, but ∆˜xi ̸= ∆˜xj could happen in previous definitions. This is equivalent to introducing a new graph signal that has and only has components of the same intensity T at frequencies λ = {λm, λm+1, · · · λm+n-1}.

Under this definition, the localized augmentation is actually a perturbation on the feature projection matrix ˜X = UT X by matrix concatenation in the spectral domain, namely:

where α ∈ {0, 1}N represents the introduced new graph signal where αi = 1 if i ∈ [m, m + n - 1] and αi = 0 otherwise. To achieve the spectral augmentation defined in Equation (4) and Equation (5), a graph with adjacency matrix A and feature matrix X is augmented in spatial domain by:

Algorithm 1 Augmentation Phase of LSPAN

Input: Original graph G = (X,A), eigenvectors of graph Laplacian {ui}Ni=1 , parameters m and n, temperature T Output: Augmented graph G′

• 1: Obtain the adjacency matrix: A′ = A.
• 2: Compute the summation of eigenvectors: u′ = (um + um+1 + · · · um+n-1).
• 3: Generate the augmented feature matrix: X′ = [X ; Tu′ ].
• 4: return G′ = (X′ ,A′ )

Specifically, Fourier bases {ui}Ni=1 are eigenvectors of orthogonally diagonalized real symmetric Laplacian matrix. Based on their orthogonality, it can be derived that ∑m+n-1 i=m UT ui = α. By this, the spectral projection of augmented feature matrix in Equation (6) is ˜X′ = UT [X ; T (um + um+1 + · · · um+n-1)] = [ ˜X ; T ∑m+n-1 i=m UT ui] = [ ˜X ; Tα], which is same as the projection ˜X′ defined in Equation (5). This means, by performing the augmentation in Equation (6), the localized spectral augmentation defined in Equation (4) and (5) is achieved. More details of this are covered in Appendix A.

Overall, the proposed LSPAN method augments a graph G = (X,A) by Equation (6), where for the feature matrix, we first compute the summation of eigenvectors {ui}m+n-1 i=m and then perform a matrix concatenation. The adjacency matrix remains unchanged. Details of the LSPAN augmentation method are outlined in Algorithm 1.

Efficiency of LSPAN. Note that the eigenvectors are drawn from the original graph Laplacian and can be pre-calculated. Therefore, during training, only matrix concatenations and vector summations with computational cost of O(N) are required and the time-consuming Fourier inverse transform is totally avoided, which ensures the efficiency of our method. An empirical time analysis is conducted in Appendix C.9.

Placing LSPAN in the Context of Prior Work. Existing augmentations are mainly divided into topology-based [Rong et al., 2020; Zhao et al., 2021; Lin et al., 2023] and feature-based [Deng et al., 2019; Feng et al., 2019; Kong et al., 2020] ones. We suggest that they are spectrally non-localized and may not well preserve the graph information. Note that the recent works [Lin et al., 2023; Liu et al., 2022a; Ghose et al., 2023] also consider spectral information. But they only use the spectral knowledge for supervising edge or feature perturbations and they still fall into spatial augmentation approaches. The work of SFA [Zhang et al., 2023] has a very different underlying principle to ours where the singular values of feature maps are perturbed and the spectrum information is not utilized. Unlike previous works, we directly perturb graph spectrum components in the spectral domain and can control any specific spectrum components, so as to perform strictly localized augmentation.

4 Spectrally Localized Augmentation on Graph Consistency Learning

We apply the proposed LSPAN method to graph consistency learning framework following the work of GRAND [Feng et al., 2020], so as to show our proposal can be easily deployed in graph consistency learning frameworks and show how the proposed spectrally localized augmentation benefits them.

Specifically, given an input graph G with feature matrix X and adjacency matrix A, we first generate S augmented graphs by Equation (6) where T , n are set as hyper-parameters and we randomly choose m from 1 to N - n + 1 for each augmentation. Then, each of the S graphs with augmented feature matrix X′(s) and adjacency matrix A′(s) is fed into a GNN model to obtain corresponding outputs:

where Z′(s) ∈ [0, 1]N×C represents the prediction probabilities on X′(s) and A′(s) with C denoting the number of node classes. The GNN model can be GCN [Kipf and Welling, 2017], GAT [Veliˇckovi´c et al., 2018] or any other state-of-theart methods. For example, in GRAND, a mixed-order propagation model performed by Z = fmlp( 1 K+1 ∑Kk=0 ˆAkX,Θ) is adopted, where ˆA is the symmetric normalized adjacency matrix, fmlp is a two-layer MLP and Θ are parameters. This design eliminates nonlinearity for high-order feature propagation and helps to reduce the over-smoothing risk.

Then, we conduct consistency training on predictions of S augmentations by employing the loss L = Lsup + γLcon where Lsup is the supervised loss on the labeled nodes, Lcon is the consistency regularization loss and hyper-parameter γ balances them. Specifically, for a graph with M labeled nodes, the supervised loss Lsup is defined as the average crossentropy loss over the S augmentations:

where Y ∈ {0, 1}N×C denotes the label matrix and Yi ∈ {0, 1}C is label vector of the i-th node. On the other hand, the consistency loss Lcon minimizes the distance between predictions on S augmentations and the distribution center of them, namely:

where the label distribution center Z′i is calculated by first taking the average of all distributions, i.e., Zi = 1S ∑Ss=1 Z′(s) i . Then, a sharpening trick [Berthelot et al., 2019] is adopted to enhance the sharpness of the average distribution, where the probability of the i-th node on the j-th class is calculated by Z′ij = Z 1t ij / ∑Cc=1 Z 1t ic (1 ≤ j ≤ C) and the sharpness is controlled by the parameter t ∈ (0, 1].

Finally, during inference, to match the feature dimension of augmented graphs during training, we expand the dimension of feature matrix by appending a zero vector 0N and use the graph G = ([X; 0N ], A) for propagation. The framework of graph consistency learning with LSPAN is shown in Figure 4, where the LSPAN method is employed in the augmentation phase for better spectrum preservation. Note that the proposal can also be plugged into other advanced graph consistency learning frameworks and performed in learnable manners by approaches such as sampling from distribution [Park et al., 2021], which is left for future work.

5 Experiments

In this section, we give a comprehensive evaluation of the LSPANmethod, including the prediction results, convergence analysis and the ablation study. Besides, a sensitivity analysis is conducted in Appendix C.5. We also report the results on large and heterophilic datasets in Appendix C.6, as well as compare other consistency learning frameworks and other spectral methods in Appendix C.7 and Appendix C.8.

5.1 Experimental Setup

We follow the standard semi-supervised graph learning procedure [Kipf and Welling, 2017; Veliˇckovi´c et al., 2018]. The setup and implementation details of LSPAN can be found in Appendix C.3.

Datasets. We perform evaluations on six publicly available benchmarks across four domains: i) citation networks, including CORA and CITESEER [Kipf and Welling, 2017]; ii) protein-protein interactions, including PPI [Hamilton et al., 2017]; iii) social networks, including BLOGCATALOG and FLICKR [Huang et al., 2017]; iv) air traffic, including AIRUSA [Wu et al., 2019]. Statistics and splits of them are summarized in Appendix C.1.

Baselines. To show how localized augmentation benefits graph consistency learning, the consistency learning framework with LSPAN as augmentation approach is first compared with i) GRAND [Feng et al., 2020] and LA-GNNs [Liu et al., 2022b], which adopt the same consistency training framework of ours but use spatial-based augmentations (GRAND performs the feature augmentation and LA-GNNs conducts a local neighbor augmentation). We respectively use GCN [Kipf and Welling, 2017], GAT [Veliˇckovi´c et al., 2018] and aforementioned mixed-order propagation (MOP) as backbones. We also compare the results of ii) other spatial augmentation methods, including BGCN [Zhang et al., 2019], DropEdge [Rong et al., 2020], AdaEdge [Chen et al., 2020], G-GNN [Zhu et al., 2021], GAUG-O [Zhao et al., 2021] and GCL-SPAN [Lin et al., 2023]. Furthermore, the results of iii) backbone models, including GCN [Kipf and Welling, 2017], GAT [Veliˇckovi´c et al., 2018], MOP, Chebyshev [Defferrard et al., 2016], MixHop

[Abu-El-Haija et al., 2019], Graph U-net [Gao and Ji, 2019], GSNN-M [Wang et al., 2020], S2GC [Zhu and Koniusz, 2021], GPR-GNN [Chien et al., 2021] and GraphSNN [Wijesinghe and Wang, 2022] are reported.

5.2 Main Results

The mean node classification accuracy over 100 runs on six real-world benchmarks are summarized in Table 1. We observe that, by adopting LSPAN augmentation, graph consistency learning is improved over all three backbones. Specifically, over GCN, GAT and MOP, consistency learning with LSPAN respectively achieves an average accuracy improvement (across datasets) of 1.8%, 1.6% and 2.7% compared to GRAND. Compared to LA-GNNs, our method achieves an average accuracy improvement of 1.2%, 1.6% and 2.2%. Compared to baseline models, our method achieves an average accuracy improvement of 5.9%, 9.6% and 7.6%, which is non-marginal. It is more fair to compare LSPANwith GRAND, which shares the same consistency learning framework with LSPAN except for the use of non-localized augmentations. The minimum accuracy improvement of LSPAN-MOP over GRAND-MOP is 0.7% (on CITESEER and PPI) and the maximum improvement is 8.2% (on FLICKR). Considering that the minimum improvement of GRAND-MOP over the backbone model is only 0.2% (on FLICKR) and the maximum improvement is only 7.4% (on PPI), the gains of LSPAN are non-trivial. Besides, LSPAN-based approaches, especially LSPAN-MOP, consistently outperform other models. This confirms the necessity and benefits of adopting spectrally localized augmentation in graph consistency learning.

To further validate the performance gain of LSPAN, we plot the curves of testing accuracy and loss function for consistency learning with LSPAN and the GRAND method in Figure ??. We test on three datasets - CORA, CITESEER and FLICKR. We test on FLICKR because the LSPAN method is performed by augmenting feature matrix and the FLICKR dataset has a total number of 12,047 features, which shows the effectiveness of LSPAN on datasets with large feature dimensions. For all datasets, the MOP model is used as the backbone model. From the results, we observe that by adopting localized augmentation, our method converges in a more fast and stable manner, as well as achieving higher accuracies. This validates the good convergence property of consistency learning with LSPAN and verifies the benefit of our proposal.

5.3 Ablation Study

An ablation study is also conducted to verify the necessity of the introduced localized augmentation and examine whether it can be paired with other techniques. Specifically, we compare consistency learning with LSPAN over MOP to several of its ablated variants in Table 2. "w/o Localized AUG" means that we use random DropNode for augmentation. This is reasonable because LSPAN is also performed in a random manner. The drop is 2.1% which clearly illustrates the importance of proposal. Besides, "w/o Multi-Sampling" means we only perform augmentation once per epoch (namely S = 1) and "w/o Sharpening Trick" means we do not use the sharpening trick when calculating the distribution center (namely t = 1). These two variants respectively witness drops of 0.5% and 0.9%, which means multi-sampling and sharpening trick also help when paired with LSPAN. Overall, the promising performance of consistency learning with LSPAN is mainly contributed by the proposed localized augmentation, and it can be easily combined with commonly used techniques.

6 Conclusion

In this paper, we study the issue of exploring high-quality graph augmentation methods for graph consistency learning. We identify that existing augmentations are spectrally nonlocalized, where important graph spectrums are perturbed over the entire frequency range and can be largely changed. To enhance the preservation of graph information, we propose a simple but effective LSPAN method to conduct spectrally localized augmentation. LSPAN perturbs only a small concentrated part of graph spectrum, improves the preservation of spectrum structure and therefore benefits model prediction. Extensive empirical evaluation on real-world benchmarks shows that, by leveraging localized augmentation, graph consistency learning achieves considerable performance gains and always outperforms previous state-of-the-art methods.

Acknowledgments

This research was supported by the National Science Foundation of China (62306133, 62176118).