PaperlayerView exact revision on arXiv

Source-linked AI summary

From Canonical Correlation Analysis to Self-supervised Graph Neural Networks

Hengrui Zhang, Qitian Wu, Junchi Yan, David Wipf, Philip S. Yu

arXiv:2106.12484v2cs.LG

TL;DR

Graph self-supervised methods often require complex architectures, mutual-information estimators, projectors, asymmetric components, or negative samples. CCA-SSG uses a feature-level objective inspired by Canonical Correlation Analysis, achieves competitive performance on seven benchmarks, and relies on informative, label-invariant augmentations.

  • Problem

    Existing graph self-supervised methods require complex designs, parameterized mutual-information estimators, projectors, asymmetric architectures, or nontrivial negative-sample selection.

  • Method

    CCA-SSG generates two augmented graph views, encodes them with a shared GNN, and optimizes a non-contrastive feature-level CCA-inspired objective using invariance and decorrelation terms.

  • Results

    CCA-SSG outperforms state-of-the-art self-supervised methods MVGRL and GCA on 5 out of 7 benchmarks.

  • Takeaways & Limitations

    The objective retains augmentation-invariant information, discards augmentation-variant information, and decorrelates feature dimensions without negative samples or intricate model components.

  • Takeaways & Limitations

    CCA-SSG relies on high-quality, informative, label-invariant augmentations, whose generation remains an open problem.

Abstract

from arXiv · show

We introduce a conceptually simple yet effective model for self-supervised representation learning with graph data. It follows the previous methods that generate two views of an input graph through data augmentation. However, unlike contrastive methods that focus on instance-level discrimination, we optimize an innovative feature-level objective inspired by classical Canonical Correlation Analysis. Compared with other works, our approach requires none of the parameterized mutual information estimator, additional projector, asymmetric structures, and most importantly, negative samples which can be costly. We show that the new objective essentially 1) aims at discarding augmentation-variant information by learning invariant representations, and 2) can prevent degenerated solutions by decorrelating features in different dimensions. Our theoretical analysis further provides an understanding for the new objective which can be equivalently seen as an instantiation of the Information Bottleneck Principle under the self-supervised setting. Despite its simplicity, our method performs competitively on seven public graph datasets. The code is available at: https://github.com/hengruizhang98/CCA-SSG.

1 Introduction

Graph self-supervised learning methods often rely on complex contrastive designs, including mutual-information estimators, projectors, asymmetric structures, and negative samples. CCA-SSG introduces a simpler feature-level objective that preserves augmentation-invariant information, prevents dimensional collapse, and performs competitively across graph benchmarks.

  • Motivation: Contrastive graph methods require complex designs, parameterized mutual-information estimators, projectors, negative pairs, or asymmetric architectures.Negative-sample selection can be nontrivial and costly for large graphs.
  • Objective: The objective maximizes correlation between augmented views while decorrelating feature dimensions within each view.This design targets augmentation-invariant information and helps prevent dimensional collapse.
  • Method: CCA-SSG introduces a non-contrastive, non-discriminative objective inspired by Canonical Correlation Analysis for unsupervised node representation learning.The framework is based on random graph augmentations, a shared GNN encoder, and a feature-level objective.
  • Theory: The objective has a theoretical relationship to the Information Bottleneck Principle under self-supervised settings.The analysis characterizes the objective as retaining augmentation-invariant information while discarding augmentation-variant information.

2 Related Works and Background

Prior graph self-supervised methods primarily use instance-level contrastive learning, while feature-level objectives address some of its drawbacks. CCA provides the conceptual basis for correlating multiple views while constraining different representation dimensions to remain uncorrelated.

  • Contrastive Learning on Graphs: Graph self-supervised methods adapted from vision commonly use instance-level contrastive learning based on local-global mutual-information maximization.Examples include DGI, InfoGraph, MVGRL, and GCC.
  • Feature-level Self-supervised Objectives: Feature-level objectives have been proposed to address drawbacks of instance-level contrastive methods through clustering, whitening, or redundancy reduction.Examples include Contrastive Clustering, W-MSE, and Barlow Twins.
  • Canonical Correlation Analysis: Canonical Correlation Analysis seeks correlated projections of two random variables using their covariance structure.For multidimensional cases, the projected vectors are constrained to be uncorrelated with one another.
  • Canonical Correlation Analysis: Deep multi-view CCA replaces linear transformations with neural networks, but its precise computation can be expensive.Soft CCA removes the hard decorrelation constraint through Lagrangian relaxation.
  • Canonical Correlation Analysis: Soft CCA combines a cross-view distance term with stochastic decorrelation losses weighted by λ.The decorrelation loss measures the L1 distance between representations and an identity matrix.

3 Approach

CCA-SSG generates two augmented graph views, encodes them with a shared GNN, and optimizes a feature-level CCA-inspired objective. Its invariance and decorrelation terms avoid contrastive components while supporting scalable node representation learning.

  • 3.1 Model Framework: CCA-SSG comprises a random graph augmentation generator, a GNN encoder, and a CCA-based feature-level objective.The model focuses on self-supervised node representation learning for a single graph G = (X, A).
  • 3.1 Model Framework: Two views are created by randomly dropping edges and masking node features, then passed through a shared GNN encoder.The resulting embeddings are normalized along the instance dimension before the objective is computed.
  • 3.2 Learning Objective: The objective maximizes correlation between views while decorrelating feature dimensions so different dimensions capture distinct semantics.The non-negative coefficient λ trades off the invariance and decorrelation terms.
  • 3.3 Advantages over Contrastive Methods: CCA-SSG avoids negative samples, parameterized mutual-information estimators, projector networks, and asymmetric architectures.Its feature decorrelation term naturally prevents trivial solutions caused by the invariance term.
  • 3.3 Advantages over Contrastive Methods: O(D^2) loss space is required for D-dimensional node embeddings, so memory cost does not grow consistently with graph size N.This contrasts with competing approaches whose costs scale with nodes or node pairs.

4 Theoretical Insights with Connection to Information Theory

The analysis interprets CCA-SSG as preserving input information while suppressing augmentation-specific information. Under stated assumptions, the objective connects to self-supervised Information Bottleneck formulations and yields representations intended to be minimal and sufficient for downstream tasks.

  • 4 Theoretical Insights with Connection to Information Theory: The theoretical section analyzes the loss through entropy, mutual information, Information Bottleneck connections, and downstream-task relevance.Definitions use X for input data, S for an augmented view, and ZS for its learned representation.
  • 4.1 An Entropy and Mutual Information Interpretation of the Objective: Under the Gaussian distribution assumption, minimizing the invariance term minimizes the conditional entropy of ZS given X.This proposition characterizes the invariance term through the variability of representations across augmentations.
  • 4.1 An Entropy and Mutual Information Interpretation of the Objective: Under the same assumption, minimizing the decorrelation term maximizes the entropy of ZS.Together, the two terms describe complementary effects on the learned representation.
  • 4.1 An Entropy and Mutual Information Interpretation of the Objective: Optimizing the objective maximizes I(ZS, X) while minimizing augmentation-related information I(ZS, S|X).The analysis interprets this as retaining input information while minimizing information lost or introduced through augmentation.
  • 4.2 Connection with the Information Bottleneck Principle: For 0 < β ≤1, minimizing Eq. (5) is equivalent to maximizing the self-supervised Information Bottleneck objective.When augmentation is reversible, it is also equivalent to learning Minimal and Sufficient Representations for Self-supervision.
  • 4.3 Influence on Downstream Tasks: Assuming task-relevant information is shared across augmented views, optimizing Eq. (5) maximizes I(ZS, T) and minimizes H(ZS|T).The resulting representation is expected to contain minimal and sufficient information about downstream tasks.

5 Experiments

CCA-SSG is evaluated through linear node-classification accuracy on seven benchmarks, with comparisons against unsupervised, self-supervised, and supervised baselines. Experiments also examine component effects, embedding dimension, decorrelation strength, and scalability.

  • Evaluation Protocol: The evaluation freezes the unsupervised encoder before training a logistic-regression classifier on training nodes and reporting test accuracy.Representations are pretrained on all graph nodes without supervision.
  • Comparison with Peer Methods: CCA-SSG achieves the best performance on four larger benchmarks except Coauthor-Physics, and competitive results with MVGRL on Citeseer.On Cora and Pubmed, it outperforms both unsupervised competitors and fully supervised baselines.
  • Ablation Study: Removing the invariance term causes performance degradation, while removing decorrelation can permit dimensional collapse.Node embeddings are normalized across instances, making the decorrelation term important for avoiding a collapsed feature geometry.
  • Ablation Study: Proper decorrelation intensity uses λ from 0.0005 to 0.001; excessive λ neglects invariance and seriously degrades performance.When λ is too small, the decorrelation term has little effect.
  • Embedding Dimension: CCA-SSG benefits from large embedding dimensions, with 512 optimal on most benchmarks, but performance drops as dimension increases further.The authors conjecture that CCA performs dimension reduction and therefore avoid it on already compressed datasets.
  • Scalability Comparison: CCA-SSG uses fewer parameters, shorter training time, and less memory than MVGRL, GRACE, and GCA in most scalability comparisons.Despite its simplicity and efficiency, it achieves better or competitive performance.

6 Conclusion and Discussions

The paper concludes that CCA-SSG provides a simple and efficient CCA-based approach for graph representation learning. It also identifies feature-dimension and augmentation quality as important boundaries, alongside potential societal risks.

  • Conclusion: CCA-SSG uses random augmentations and a GNN encoder without additional components required by contrastive methods.The method is presented as conceptually simple, efficient, and effective for self-supervised graph representation learning.
  • Limitations: The method may perform poorly when input data lacks a large feature dimension because its objective essentially performs dimension reduction.This limitation follows from the tension between dimension reduction and the large embedding dimensions often used in SSL.
  • Limitations: CCA-SSG relies on high-quality, informative, and label-invariant augmentations, but generating augmentations with non-negative downstream effects remains open.The authors state that their augmentations may not perfectly satisfy these requirements.
  • Potential Negative Societal Impacts: The method may reduce manual labeling needs and downplay minority features because it emphasizes shared information across data.The paper identifies possible employment effects and bias toward majority or dominant features as potential negative societal impacts.

B Discussions on Degenerated Solutions in SSL

Self-supervised objectives can suffer from complete collapse, where all samples coincide, or dimensional collapse, where dimensions capture redundant information. The proposed method addresses these failures through normalization and feature decorrelation.

  • Proposed safeguards: Feature-wise normalization naturally avoids complete collapse, while the decorrelation term prevents or alleviates dimensional collapse.The decorrelation term pushes feature dimensions toward orthogonal representations and scatters data points in the embedding space.
  • Contrastive objectives: Contrastive objectives use positive-pair similarity and negative-pair dissimilarity, with per-instance normalization projecting embeddings onto a hypersphere.InfoNCE's numerator handles positive pairs, while its denominator promotes dissimilarity between negative pairs.
  • Collapse types: Complete collapse maps all data samples to one point on the hypersphere, while dimensional collapse distributes them nearly along a line.Dimensional collapse also means different dimensions are highly correlated and capture the same information.
  • Complete collapse: Alignment alone causes complete collapse, whereas uniformity separates embeddings and distributes data points uniformly on the hypersphere.The paper illustrates these cases in Fig. 4(a) and Fig. 4(b).
  • Dimensional collapse: Merely normalizing each feature dimension does not prevent dimensional collapse because the normalized feature matrix can still have highly redundant dimensions.The paper expresses this condition as ˜Z⊤˜Z approximately equal to 1 under column normalization.

D.1 Proof of Proposition 1

The analysis interprets the objective through entropy and mutual information: invariance minimizes augmentation-conditioned representation entropy, while decorrelation maximizes representation entropy. These terms connect the objective to self-supervised Information Bottleneck formulations.

  • Proposition 1: Minimizing the invariance term minimizes the entropy of augmented-view representations conditioned on the input data.Under the augmentation model, this is also described as minimizing the variance of augmentation representations conditioned on the input.
  • Proposition 2: The decorrelation term is equivalent to maximizing the entropy of the augmented-data representations under a Gaussian assumption.Its optimum is reached when the covariance matrix is the identity, with all eigenvalues equal to 1.
  • Theorem 1: Together, the objective maximizes mutual information between view embeddings and input data while minimizing information between embeddings and augmentations conditioned on the input.This is the paper's stated interpretation in Theorem 1.
  • Theorem 2: For 0 < β ≤ 1, minimizing the proposed objective maximizes the self-supervised Information Bottleneck objective.The decomposition combines maximizing H(ZS) with minimizing H(ZS|X).
  • Corollaries: When augmentation is reversible, the objective is equivalent to learning Minimal and Sufficient Representations for Self-supervision.The cited formulation maximizes I(ZX, S) while minimizing H(ZX|S).

D.7 Proof of Theorem 3

Theorem 3 characterizes the learned representation using task-relevant and task-irrelevant information. Under the stated assumption, optimization maximizes a lower bound on task-relevant information and minimizes an upper bound on task-irrelevant information.

  • Theorem 3: Theorem 3 states that optimizing Eq. (5) maximizes task-relevant information I(ZS, T) and minimizes task-irrelevant information H(ZS|T).The theorem's proof establishes these as bounded quantities rather than directly equating both objectives in general.
  • Assumptions: The assumption I(X, T|S) = I(S, T|X) = 0 yields I(ZS, T|X) = 0 in the proof.This conditional-information step is used to derive the theorem's bounds.
  • Information bounds: I(X, S|T) is a fixed gap representing task-irrelevant information shared between the original data and its augmentation.The theorem uses this gap in bounding task-relevant and task-irrelevant information.
  • Implementation note: The implementation uses equivalent objective forms and treats the displayed trade-off parameter as λ′, which is half of λ in the original formulation.This notation applies to the values reported in Fig. 2 and Appendix E.4.
  • Graph augmentations: Graph views are generated by edge dropping and node-feature masking, with the same transformation distributions used for both views.Edge dropping modifies graph structure, whereas feature masking sets selected input features to zero.

E.3 Datasets

The evaluation covers seven public node-classification benchmarks spanning citation, co-authorship, and Amazon co-purchase graphs. Dataset-specific splits, preprocessing, and hyperparameter searches define the experimental setup.

  • Benchmark datasets: Seven benchmarks are evaluated: Cora, Citeseer, Pubmed, Coauthor CS, Coauthor Physics, Amazon Computer, and Amazon Photo.The datasets are used for node classification evaluation.
  • Citation networks: Cora, Citeseer, and Pubmed are citation networks whose nodes are papers and edges represent citation relationships.Their public split uses 20 training nodes per class, plus fixed validation and test sets of 500 and 1000 nodes.
  • Co-authorship graphs: Coauthor CS and Coauthor Physics are co-authorship graphs with author nodes, co-authorship edges, keyword features, and 10%/10%/80% train/validation/test splits.The class labels indicate authors' most active fields of study.
  • Amazon graphs: Amazon Computer and Amazon Photo are co-purchase graphs with product nodes, co-purchase edges, review-based features, product-category labels, and 10%/10%/80% splits.Their node features are bag-of-words encodings of product reviews.
  • Data and setup: All datasets use processed versions from the Deep Graph Library and are publicly available without licenses.The paper also reports that Coauthor-CS uses an MLP instead of a GCN, equivalent to dropping all non-self-loop edges.

F.1 Visualizations of Correlation Matrix

The correlation visualizations show that feature decorrelation prevents node-embedding dimensions from becoming redundant, while augmentation intensity affects downstream classification performance. Low-label evaluations further show strong performance when labeled nodes are scarce.

  • Correlation structure: Without the decorrelation term, embedding correlation increases sharply, indicating that dimensions capture similar rather than orthogonal information.With the term, CCA-SSG learns nearly highly disentangled representations and fundamentally avoids dimensional collapse.
  • Correlation structure: The raw input features of Cora, Citeseer, and Pubmed are nearly fully uncorrelated, with diagonal correlations near 1 and off-diagonal correlations near 0.
  • Correlation structure: Citeseer remains fairly uncorrelated without decorrelation, possibly because its one-layer encoder and shorter training reduce collapse pressure.
  • Augmentation effects: Each dataset has an augmentation combination of feature masking ratio pf and edge dropping ratio pe that yields the best downstream performance.The study reports test accuracy across combinations of pf and pe on seven node-classification benchmarks.
  • Low-label evaluation: CCA-SSG performs especially well under scarce labels, including 1% on Cora and Citeseer and 0.05% on Pubmed.Results compare against Label Propagation, Cheby, and vanilla GCN, using randomly selected training and testing nodes across 20 trials.

G Further Comparisons with previous contrastive methods

The paper compares graph self-supervised methods by their view generation, contrasting pairs, loss functions, and downstream tasks. It emphasizes that prior methods use instance-level contrastive learning, whereas CCA-SSG introduces a non-contrastive, non-discriminative objective inspired by canonical correlation analysis.

  • Comparison framework: The comparison organizes graph self-supervised methods by view generation, contrasting pairs, loss function, and downstream task level.The task levels include node-, edge-, and graph-level learning.
  • Comparison framework: GMI uses a unique and complex view-generation and contrasting-pair design that does not fit the comparison categories.
  • Comparison framework: The taxonomy is conceptual, so individual methods may still contain distinct implementation details and specific designs.
  • Conceptual distinction: Prior methods primarily focus on instance-level contrastive learning, while CCA-SSG uses a non-contrastive and non-discriminative objective.CCA-SSG’s objective is inspired by canonical correlation analysis.
Loading 2106.12484v2…