PaperlayerView exact revision on arXiv

Source-linked AI summary

Spectral Feature Augmentation for Graph Contrastive Learning and Beyond

Yifei Zhang, Hao Zhu, Zixing Song, Piotr Koniusz, Irwin King

arXiv:2212.01026v1cs.LGcs.AIcs.CV

TL;DR

Feature augmentation remains a little-studied complement to contrastive learning, and unbalanced view spectra can impair alignment. The paper uses incomplete power iteration to rebalance and perturb singular values. It reports gains across graph and image benchmarks, compatibility with other augmentations and losses, and a lower generalization bound.

  • Problem

    Feature augmentation is a plausible but little-studied complement to contrastive learning, while unbalanced singular values can make view alignment suboptimal.

    Source: §1 · pp. 1–2

  • Method

    Incomplete power iteration partially rebalances feature-map spectra and injects noise into singular values, followed by alignment of the rebalanced views.

    Source: §1 · p. 2, §3 · p. 3

  • Results

    SFA consistently achieves the best node-classification results across datasets, outperforms baselines on three graph-classification datasets, and improves GRACE by 3% on Cora and 4% on Citeseer.

    Source: §4.1 · pp. 5–6

  • Takeaways & Limitations

    SFA is compatible with other augmentation strategies and contrastive losses, and the paper reports better alignment with a lower generalization bound.

    Source: §1 · p. 2, §5 · p. 7

    The paper acknowledges a limitation of its method.

    Source: H Broader Impact and Limitations · p. 15

Abstract

from arXiv · show

Although augmentations (e.g., perturbation of graph edges, image crops) boost the efficiency of Contrastive Learning (CL), feature level augmentation is another plausible, complementary yet not well researched strategy. Thus, we present a novel spectral feature argumentation for contrastive learning on graphs (and images). To this end, for each data view, we estimate a low-rank approximation per feature map and subtract that approximation from the map to obtain its complement. This is achieved by the proposed herein incomplete power iteration, a non-standard power iteration regime which enjoys two valuable byproducts (under mere one or two iterations): (i) it partially balances spectrum of the feature map, and (ii) it injects the noise into rebalanced singular values of the feature map (spectral augmentation). For two views, we align these rebalanced feature maps as such an improved alignment step can focus more on less dominant singular values of matrices of both views, whereas the spectral augmentation does not affect the spectral angle alignment (singular vectors are not perturbed). We derive the analytical form for: (i) the incomplete power iteration to capture its spectrum-balancing effect, and (ii) the variance of singular values augmented implicitly by the noise. We also show that the spectral augmentation improves the generalization bound. Experiments on graph/image datasets show that our spectral feature augmentation outperforms baselines, and is complementary with other augmentation strategies and compatible with various contrastive losses.

1 Introduction

Graph contrastive learning uses augmentations to create views, but feature augmentation remains little studied and random feature perturbations can ignore covariance and semantic correlations. The paper proposes spectral feature augmentation to rebalance and perturb singular values, improving alignment while remaining compatible with other augmentations and contrastive losses.

1 Introduction

  • Learned graph augmentations can require supervision, while random augmentations may adversely affect downstream tasks.These limitations motivate a simple, efficient augmentation complementary to existing strategies.Source: §1 · p. 1
  • Spectral feature augmentation injects noise into singular values, aiming to preserve semantic correlations that random feature perturbations can ignore.The approach perturbs singular values rather than orthogonal bases by much.Source: §1 · pp. 1–2
  • Unbalanced singular values let dominant directions drive view alignment, sacrificing weaker orthogonal directions and producing suboptimal bases alignment.The paper identifies this as a source of suboptimal GCL models.Source: §1 · p. 2
  • Incomplete power iteration partially balances the spectra of two views and injects augmentation noise into their singular values in one or two iterations.Rebalanced spectra support alignment of the views’ orthonormal bases.Source: §1 · p. 2
  • The paper derives the iteration’s expected spectrum-rebalancing effect and the variance of its implicit spectral augmentation.It also proposes MaxExp, Power Norm, and Grassman-feature-map variants with different rebalancing and noise-injection profiles.Source: §1 · p. 2

2 Related Work

Prior work spans input-space graph augmentations and feature-space methods, including channel augmentation and random projections. This paper instead perturbs and rebalances the singular values of both views.

2 Related Work

  • Graph augmentations include attribute masking, edge permutation, node dropout, and adaptive or adversarial perturbations.The passage also surveys image, language, and transportation augmentations.Source: §2 · p. 2
  • Feature-space approaches include channel augmentation, COSTA’s random projections, and methods that augment few-shot features or transfer analogies.Analogy-based augmentations are not applicable to contrastive learning due to its lack of labels.Source: §2 · p. 2
  • Unlike COSTA’s feature augmentation, this work perturbs and rebalances singular values of both views and reports outperforming COSTA.Source: §2 · p. 2

3 Proposed Method

The method applies spectral feature augmentation to two graph views before projecting their representations and computing a contrastive loss. Its incomplete power iteration partially rebalances feature-map spectra, implicitly adds noise to singular values, and is used to improve view alignment and the generalization bound.

3 Proposed Method

  • Two augmented graph views pass through a shared GCN encoder, spectral feature augmentation, and a shared projection head before contrastive loss is applied.The encoder produces feature maps for each view, and the augmentation is applied to the maps separately.Source: §3 · pp. 2–3

3.1 Spectral Feature Augmentation for GCL

  • Starting from a random vector, incomplete power iteration estimates and subtracts a low-rank component, yielding feature maps with partially rebalanced spectra and implicitly perturbed singular values.The expected push-forward describes the rebalancing, while stochasticity produces variance in augmented singular values; both effects are strongest at k = 1 and decline for k ≥ 2.Source: §3.1 · pp. 3–4, Figure 3 · p. 4

3.2 Why does the Incomplete Power Iteration work?

  • SFA reweights cross-view alignment so leading singular vectors contribute less, addressing the neglect of smaller-singular-value directions in unbalanced feature maps.The paper states that this improved alignment yields a better contrastive-learning generalization bound.Source: §3.2 · pp. 4–5

4 Experiments

The experiments evaluate SFA across graph and image tasks and report strong node- and graph-classification results. Analysis examines its spectrum rebalancing, alignment, augmentation combinations, iteration count, noise robustness, and alternative spectral methods.

4.1 Main Results

  • SFA consistently achieves the best node-classification results across all datasets, and improves GRACE by 3% on Cora and 4% on CiteSeer.The study also reports that SFA works with the Barlow Twins loss.Source: §4.1 · pp. 5–6, Table 1 · p. 6
  • SFA outperforms all baselines on three graph-classification datasets; the image-classification table reports top-1 accuracy on CIFAR10, CIFAR100, and ImageNet-100.The supplied passages do not state image-classification winners or values.Source: Table 6 · p. 6, §4.1 · p. 6, Table 5 · p. 6
  • SFA adds negligible runtime overhead, with a cost described as negligible for fewer than eight iterations.The method uses a few matrix-matrix or matrix-vector multiplications; direct SVD is costly per minibatch and unstable in back-propagation.Source: §4.1 · p. 6, Table 2 · p. 6, Figure 4 · p. 6

4.2 Analysis on Spectral Feature Augmentation

  • With SFA, consecutive singular-value gaps decrease during training, balancing leading spectrum components; Fig. 6 also shows improved alignment between views.The reported spectrum evolution agrees with the paper's propositions on rebalancing.Source: §4.2 · p. 6, Figure 6 · p. 7
  • Combining graph augmentation AG with spectral augmentation AF* yields gains of 3.7%, 6.0%, and 4.8% on Am-Computer, Cora, and CiteSeer over no augmentations.AF* with AG also outperforms AF with AG by 1.1%, 2.4%, and 1.7%, respectively.Source: §4.2 · p. 6, Table 7 · p. 6
  • The best gain occurs at k=1 or 2; without power iteration, performance drops by 1.5%, 3.3%, and 2.2% on Am-Computer, Cora, and CiteSeer.The paper associates low k with both spectrum flattening and significant spectral augmentation.Source: §4.2 · p. 6, Table 8 · p. 7
  • On Cora and CiteSeer node classification, SFA is reported robust to noisy features, while mostly leaving non-leading, noise-bearing components unchanged.The noise setting adds Gaussian noise to original node features, with intensity controlled by ϵ.Source: §4.2 · p. 7, Table 9 · p. 7
  • SFA outperforms MaxExp(F), Power Norm., Power Norm.*, and Grassman; the paper notes that these alternatives differ in which spectral components they rebalance or augment.MaxExp(F) augments non-leading singular values, while Grassman binarizes the spectrum and may reject useful boundary signal.Source: §4.2 · p. 7, Table 10 · p. 7, Figure 7 · p. 7

5 Conclusions

The conclusions characterize SFA as a fast spectral feature augmentation that rebalances and perturbs useful singular values, improving view alignment and the generalization bound. The accompanying proofs bound augmentation error and relate spectral gaps to alignment quality.

5 Conclusions

  • SFA rebalances and augments useful spectrum through implicit noise injection, yielding better alignment and a lower generalization bound.The paper also describes incomplete power iteration as very fast.Source: §5 · p. 7

B Bounded Noise Matrix.

  • If ∥V−eV∥2 ≤ ϵ, each absolute-error element Eij is bounded by η = 2ε∆˜σ12/(nπ+2ε), where n is the node count and ∆˜σ12 is the singular-value gap of eH.Source: B Bounded Noise Matrix · p. 10
  • The bounded error limits augmented spectral gaps, brings singular vectors closer to their originals, and improves the quality of angle alignment between views.The proof gives the corresponding error bound in terms of the singular-vector difference.Source: B Bounded Noise Matrix · p. 10, §C.5 · p. 12

C.2 Proof of Proposition 1

  • When σ_i ≥ σ_j, the proof establishes ordered coefficients 1 ≥ λ_i ≥ λ_j ≥ 0 using the i.i.d. normal initialization.The argument uses the distribution of the projected random vector.Source: §C.2 · pp. 10–11

C.3 Proof of Proposition 2

  • The exact distribution of v_i, a weighted sum of chi squares, is an ongoing research topic, so the proof uses a highly accurate surrogate.The passage attributes the surrogate result to Feiveson and Delaney (1968).Source: §C.3 · p. 11

C.4 Proof of Proposition 3

  • The variance expression is obtained by integrating the density derived in Proposition 2 and simplifying hypergeometric functions.The passage says the integration was performed using Mathematica.Source: §C.4 · p. 11

C.6 Proof of Theorem 1

The proof bounds downstream error under a stated augmentation and classification condition. It also uses a spectral upper bound to argue that clipping and balancing lower the energy of the SFA loss.

C.6 Proof of Theorem 1

  • For a (σ, δ)-augmentation, if samples in each class's main part intersecting Sε are correctly classified, then Err(G) ≤ (1 − σ) + Rε.Rε is defined as the probability of Sε, the set where all augmentations of a sample remain at least ε apart under f.Source: §C.6 · p. 12

C.7 Upper bound of φ

  • The push-forward function is upper-bounded by ¯φ(σ_i) − O(k), and the bound allows more tightening at lower k.The passage identifies this upper bound with the AxMin pooling operator and says spectrum clipping and balancing lower Eq. (6)'s loss energy relative to Eq. (5).Source: §C.7 · p. 12

C.8 Derivation of MaxExp(F)

The MaxExp(F) derivation applies a spectrum-rebalancing transformation using the feature map's singular-value structure. The Grassman variant replaces soft spectrum flattening with a binarized push-forward and per-sample noise.

C.8 Derivation of MaxExp(F)

  • Using H's SVD, the MaxExp(F) derivation forms A2 = H⊤H and applies MaxExp(F) to A to produce eH = HBC, with the push-forward rebalancing the spectrum.A and B are computed as matrix square root and inverse square root using 10 Newton-Schulz iterations.Source: §C.8 · p. 12

C.9 Derivation of Grassman

  • The Grassman feature map replaces soft spectrum flattening with a binarized variant, using per-sample normally drawn noise while κ controls the spectrum cutoff.The variance of the noise is selected per sample.Source: §C.9 · pp. 12–13

C.10 Derivation of Matrix Square Root.

This alternative spectrum-rebalancing approach replaces soft flattening with a matrix square-root push-forward, whose steepness is controlled by β.

C.10 Derivation of Matrix Square Root.

  • The matrix square-root push-forward uses normally drawn Δβ noise and constrains 0 ≤ β + Δβ ≤ 1; Newton-Schulz iterations implement the function.β controls the steepness of the balancing curve.Source: §C.10 · p. 13

D Dataset Description

The experiments use citation, Wikipedia, and Amazon co-purchase networks for node tasks, alongside a ResNet-18 setup for image classification.

D Dataset Description

  • Cora, CiteSeer, PubMed, and WikiCS are citation or Wikipedia networks with labeled nodes; Am-Computer and AM-Photo are product co-purchase networks with review-based features.The product networks have ten and eight node classes, respectively.Source: D Dataset Description · p. 13

D.1 Implementation Details

  • Image classification uses ResNet-18 for 1,000 CIFAR epochs and 400 ImageNet-100 epochs.The hyperparameter setting follows [da Costa et al. 2022].Source: §D.1 · p. 13

D.2 Hyper-parameter Setting for node classification and clustering

  • The main-result hyperparameters are listed in Table 12.The supplied passage does not specify their values.Source: §D.2 · p. 13

D.3 Baseline Setting

  • The major GSSL baselines vary in graph augmentation and contrastive objective, including edge removal, feature masking, InfoNCE, and Barlow Twins.Other listed choices include Personalized PageRank, node shuffling, Jensen-Shannon Divergence, and Bootstrapping Latent loss.Source: §D.3 · p. 13

E Additional Empirical Results

SFA achieves the best reported node-clustering NMI and ARI across the evaluated benchmarks. Additional results examine alignment on CiteSeer and WikiCS.

Node Clustering

  • SFA achieves the best NMI and ARI scores on all three node-clustering benchmarks.Table 14 covers Am-Computer, Cora, and CiteSeer; the text reports ten runs per method.Source: E Additional Empirical Results · p. 13

Improved Alignment

F Matrix Preconditioning

The matrix-preconditioning comparison highlights constraints of that alternative and features of SFA. The incomplete iteration explains how SFA's spectrum rebalancing arises.

F Matrix Preconditioning

  • The preconditioner is designed to improve linear-system solving, but the described approach cannot flatten leading singular values while leaving the rest unchanged.Grassmann feature maps instead form a subspace from κ leading singular values; the comparison also considers PCA with κ = 20 components.Source: F Matrix Preconditioning · p. 14
  • Matrix preconditioning requires an invertible SPD matrix and complicates recovery of the rectangular feature matrix; SVD backpropagation can fail for non-simple eigenvalues.The passage notes that inversion is required.Source: F Matrix Preconditioning · p. 14
  • SFA performs better than the compared alternatives by retaining some non-leading singular values, augmenting leading ones, and avoiding SVD backpropagation.The comparison includes matrix preconditioning, Grassmann feature maps, and PCA.Source: F Matrix Preconditioning · p. 14, Table 16 · p. 15

G Why does the Incomplete Iteration of SFA Work?

  • For small iteration counts, the power-iteration matrix focuses on leading singular vectors, and its complement balances a power-law spectrum.The passage explains this as the inverse power-law non-linearity acting on the feature matrix.Source: G Why does the Incomplete Iteration of… · p. 15

H Broader Impact and Limitations

The authors describe SFA as a plug-in for graph-learning applications, while noting that it does not encode a fairness prior.

Broader Impact

  • The framework is proposed for applications including recommendation systems, neural architecture search, and drug discovery; SFA is described as a plug-and-play layer with negligible runtime cost.The authors also connect it to training user and item embeddings for the cold-start problem in online shopping.Source: H Broader Impact and Limitations · p. 15

Limitations

  • Because SFA does not model a fairness prior, the GCL model still needs to address bias that may enter through data collection or graph construction.The authors name gender and ethnicity bias as examples.Source: H Broader Impact and Limitations · p. 15
Loading 2212.01026v1…