PaperlayerView exact revision on arXiv

Source-linked AI summary

Rethinking and Scaling Up Graph Contrastive Learning: An Extremely Efficient Approach with Group Discrimination

Yizhen Zheng, Shirui Pan, Vincent Cs Lee, Yu Zheng, Philip S. Yu

arXiv:2206.01535v2cs.LGcs.AI

TL;DR

Graph contrastive learning reduces dependence on labels but incurs similarity-computation, memory, and training-time costs, especially on large graphs. The paper revisits this paradigm and introduces Group Discrimination and its GGD model, which classify positive versus topology-corrupted node groups with binary cross-entropy. GGD achieves competitive or state-of-the-art performance with substantially better efficiency across the evaluated datasets.

  • Problem

    Graph contrastive learning reduces reliance on labels but is inefficient in time and memory and often needs many epochs on large-scale graphs.

  • Method

    Group Discrimination replaces similarity computation with binary classification of positive and topology-corrupted negative node groups, implemented in GGD with a Siamese GNN and binary cross-entropy loss.

  • Results

    GGD achieves state-of-the-art performance with substantially lower time and memory consumption, including 10,783× faster total training than GBT on ogbn-arxiv.

  • Takeaways & Limitations

    Group Discrimination provides an efficient and scalable self-supervised alternative to graph contrastive learning for large-scale graph representation learning.

Abstract

from arXiv · show

Graph contrastive learning (GCL) alleviates the heavy reliance on label information for graph representation learning (GRL) via self-supervised learning schemes. The core idea is to learn by maximising mutual information for similar instances, which requires similarity computation between two node instances. However, GCL is inefficient in both time and memory consumption. In addition, GCL normally requires a large number of training epochs to be well-trained on large-scale datasets. Inspired by an observation of a technical defect (i.e., inappropriate usage of Sigmoid function) commonly used in two representative GCL works, DGI and MVGRL, we revisit GCL and introduce a new learning paradigm for self-supervised graph representation learning, namely, Group Discrimination (GD), and propose a novel GD-based method called Graph Group Discrimination (GGD). Instead of similarity computation, GGD directly discriminates two groups of node samples with a very simple binary cross-entropy loss. In addition, GGD requires much fewer training epochs to obtain competitive performance compared with GCL methods on large-scale datasets. These two advantages endow GGD with very efficient property. Extensive experiments show that GGD outperforms state-of-the-art self-supervised methods on eight datasets. In particular, GGD can be trained in 0.18 seconds (6.44 seconds including data preprocessing) on ogbn-arxiv, which is orders of magnitude (10,000+) faster than GCL baselines while consuming much less memory. Trained with 9 hours on ogbn-papers100M with billion edges, GGD outperforms its GCL counterparts in both accuracy and efficiency.

1 Introduction

GCL reduces reliance on labels through self-supervised mutual-information learning, but similarity computation and long training make it costly at scale. The paper introduces Group Discrimination and GGD to classify positive and negative node groups efficiently while retaining strong representation-learning performance.

  • 1 Introduction: GCL methods rely on mutual-information maximization and similarity calculations, and typically require many epochs on large datasets.These requirements increase training time and resource consumption as graph size grows.
  • 1 Introduction: GGD introduces Group Discrimination, replacing similarity computation with binary classification of positive and negative node groups.Positive samples come from the original or augmented graph, while negative samples are produced by corrupting topology through node shuffling.
  • 1 Introduction: The approach targets faster training, faster convergence, and higher scalability while achieving competitive or state-of-the-art performance with self-supervised baselines.The paper evaluates GGD across eight datasets, including the billion-edge ogbn-papers100M graph.
  • 1 Introduction: GGD uses a Siamese GNN with an encoder and projector to generate embeddings for original or augmented graphs and topology-corrupted graphs.The resulting two groups of node embeddings are discriminated with a simple binary cross-entropy objective.

2 Rethinking Representative GCL Methods

The analysis argues that DGI and MVGRL’s apparent mutual-information objective reduces to discriminating node groups because an improperly applied Sigmoid makes DGI’s summary vector nearly constant. This motivates Group Discrimination, which replaces node-pair similarity operations with binary classification and improves efficiency.

  • 2.1 Rethinking GCL Methods: DGI’s Sigmoid-treated summary vectors become approximately constant across Cora, CiteSeer, and PubMed, with values near 0.50 or 0.62 depending on activation.The reported constants are ϵ=0.50 with ReLU/LReLU/PReLU and ϵ=0.62 with Sigmoid.
  • 2.1 Rethinking GCL Methods: Except when the summary vector is zero, changing its constant value has little effect on performance, undermining DGI’s intended anchor–summary contrastive interpretation.With a zero summary vector, node embeddings become zero after multiplication and the model converges to a trivial solution.
  • 2.1 Rethinking GCL Methods: The analysis concludes that DGI effectively discriminates original-topology nodes from corrupted-topology nodes rather than learning through mutual-information interaction.Rewriting the objective with corrupted nodes as samples yields a binary cross-entropy formulation using aggregated node embeddings.
  • 2.1 Rethinking GCL Methods: Replacing DGI’s original loss with DGIBCE dramatically improves memory and time efficiency while slightly enhancing model performance.The authors attribute the efficiency improvement to removing multiplication operations between node pairs.
  • 2.1 Rethinking GCL Methods: MVGRL exhibits the same technical defect as DGI and extends the resulting group-discrimination behavior with diffusion augmentation for additional global information.The passage states that diffusion augmentation enhances model performance.
  • 2.2 Definition of Group Discrimination: Group Discrimination assigns class indicators to positive samples from the original graph or augmented views and negative samples produced by graph corruption.Binary discrimination uses indicator 1 for the positive group and 0 for the opposing group.

3 Methodology

GGD learns unsupervised node representations by discriminating positive embeddings from corrupted negative embeddings with a Siamese GNN and BCE loss. Its pipeline optionally augments graphs, corrupts topology, aggregates embeddings, and uses embedding reinforcement for downstream classification.

  • Graph Group Discrimination: GGD learns node representations without labels using a Siamese network and binary cross-entropy group discrimination.The framework comprises augmentation, corruption, a Siamese GNN network, and group discrimination.
  • Augmentation and Corruption: Augmentation optionally applies edge and feature dropout, while corruption shuffles node order in the feature matrix to create negative samples with incorrect network connections.Augmentation changes across training iterations to increase task difficulty rather than create contrastive views.
  • Siamese GNN and Group Discrimination: The Siamese GNN uses the same encoder and multilayer-perceptron projector for positive and negative groups, aggregates 2N embeddings, and classifies them by group.The backbone can use different GNNs, while the experiments adopt GCN; aggregation may be sum, mean, or linear.
  • Model Inference: At inference, the trained GNN encoder is frozen and produces node embeddings from the input graph for downstream tasks.The learned representations have predefined hidden dimension D′ and can support tasks such as node classification.
  • Embedding Reinforcement: Embedding reinforcement sums local-view and diffused-view embeddings to strengthen final representations, which are evaluated with logistic regression for node classification.The authors note that graph diffusion can impair scalability, while the reinforcement operation is easy to compute.

4 Related Work

Related work covers GNN representation learning, graph contrastive learning, and scalable GNNs. Existing scalable approaches primarily address supervised settings, leaving unsupervised large-scale graph learning as the closest related challenge.

  • Graph Neural Networks: GNNs learn low-dimensional node embeddings through message passing, supporting downstream tasks such as node classification and applications across multiple domains.The surveyed domains include federated learning, trustworthy systems, dynamic graphs, and anomaly detection.
  • Graph Contrastive Learning: GCL reduces reliance on labels by maximizing mutual information between semantically similar instances and minimizing it between dissimilar instances.DGI, for example, contrasts node embeddings with a graph-level summary vector using a JSD estimator.
  • Scalable GNNs: Scalable GNN methods use layer-wise sampling, graph sampling, or linear models, but these approaches focus on supervised learning and are not applicable when labels are unavailable.Examples include GraphSAGE, Cluster-GCN, GraphSAINT, SGC, and PPRGo.

5 Experiments

Across eight benchmark datasets, GGD achieves competitive or superior node-classification performance while substantially reducing training time, memory use, and required epochs.

  • The evaluation covers five small- and medium-scale datasets plus ogbn-arxiv, ogbn-products, and ogbn-papers100M.The largest dataset contains over 110 million nodes and 1 billion edges.
  • GGD generally outperforms all baselines across five small- and medium-scale datasets, ranking second only to CG3 on CiteSeer.
  • 19.2× faster per epoch on Amazon Photos and 64.5% lower memory use on Amazon Computers than the most efficient baseline.The efficiency gains are attributed to excluding similarity computation and avoiding multiplication of node embeddings.
  • GGD reaches state-of-the-art performance on ogbn-arxiv and ogbn-products after only one training epoch.On ogbn-arxiv, the method reaches peak performance in the first epoch and remains stable as epochs increase.
  • 10,783× faster than GBT on ogbn-arxiv and 381× faster on ogbn-products in total training time.On ogbn-products, GGD also improves over GBT by 6% on validation accuracy and 5.2% on test accuracy using one epoch.
  • On ogbn-papers100M, GGD achieves 60.2 test accuracy versus 59.3 for BGRL and 58.9 for GBT after one epoch.GGD trains in about 9 hours, whereas each BGRL or GBT epoch requires over one day; DGI and GMI do not scale reasonably to this graph.

6 Explore Group Discrimination

This section examines topology corruption and explains group discrimination as separation between positive and negative embedding distributions.

  • DGI and MVGRL generate negative samples by shuffling the feature matrix, thereby changing the graph’s neighboring structure.
  • Group discrimination contrasts nodes generated with correct topology against nodes generated with corrupted topology to learn topology-sensitive embeddings.
  • Optimizing the group-discrimination loss is equivalent to maximizing the Jensen-Shannon divergence between positive and negative embedding distributions.
  • Separating the distributions makes positive embeddings progressively closer to the optimal node-embedding distribution and avoids similarity to negative samples.Figure 6 depicts positive samples separating from negative samples while approaching the optimal distribution.

7 Future Work

The paper identifies extensions of group discrimination as future work while noting its potential for resource-constrained applications.

  • Future work includes extending binary group discrimination to multiple groups and designing corruption techniques that create harder negative groups.
  • GD’s efficiency may support deployment in applications such as recommendation systems with limited labels and computational resources.

Checklist

The checklist reports that the paper documents its claims, theoretical assumptions, reproducibility materials, and limitations, while omitting error bars.

  • The authors report that the paper describes its contributions and scope, theoretical assumptions, and complete proofs.
  • The paper reports reproducible experimental materials, including code, data, training details, and computing-resource information.
  • The checklist states that error bars were not reported despite experiments being run multiple times.
  • The paper uses existing publicly available datasets and reports no newly created datasets or human-subject research.

A.1 Proof of Proposition 1

Proposition 1 analyzes how GNN activations followed by sigmoid become concentrated near fixed values as the input scale shrinks. The limiting value depends on the encoder’s activation function.

  • The proof uses a one-layer GCN with normalized features, self-loops, and a Xavier-initialized learnable weight matrix.The encoder output is formed through graph propagation followed by multiplication with W.
  • The analysis models each pre-activation as approximately normal with scope [μ − cδ, μ + cδ].Here c controls approximation precision, while δ is the estimated standard deviation.
  • Sigmoid outputs after ReLU converge to 1/2 as δ approaches zero.The derived range is approximately [1/2, 1/2 + cδ/4].
  • With sigmoid as the GNN activation, applying sigmoid again converges to approximately 0.62 as δ approaches zero.The first sigmoid concentrates near 1/2, so the second produces sigmoid(1/2) ≈ 0.62.

A.2 Proof for Theorem 1

Theorem 1 shows that the group-discrimination objective optimally separates positive and negative embedding distributions. Maximizing its binary objective is equivalent to maximizing their Jensen–Shannon divergence.

  • The optimal discriminator output for an embedding h is Ppos(h) / (Ppos(h) + Pneg(h)).This follows by maximizing a log-likelihood term of the form a log(x) + b log(1 − x).
  • Substituting the optimal discriminator into the objective yields expectations over positive and negative samples classified by their normalized distribution densities.The two terms correspond to positive-label and negative-label discrimination.
  • Maximizing the group-discrimination loss is equivalent to maximizing JS(Ppos ∥ Pneg).Therefore, the positive and negative embedding distributions tend to become separated.

A.2.1 Connection with DGI

The analysis argues that DGI and MVGRL’s objectives reduce to group discrimination under their sigmoid-based implementations, motivating removal of the summary vector. It also connects GGD’s efficiency to linear scaling and evaluates MVGRL’s augmentation trade-off.

  • Connection with DGI: Under the stated constant-summary assumptions, the optimal classifier cannot outperform random guessing because p(H, s) equals p(H)p(s).The analysis therefore reports a constant optimal error rate and MI(H; s) = 0, contradicting DGI’s stated theorem under those assumptions.
  • Connection with DGI: DGI’s constant-summary formulation is equivalent to separating positive and negative embedding distributions with Jensen–Shannon divergence.This motivates removing the summary vector and directly applying binary cross-entropy to the two groups.
  • Rethinking MVGRL: MVGRL’s official JSD-based implementation also becomes group discrimination, and its BCE replacement performs on par with the original MVGRL loss.Including both diffused-view groups improves performance from 82.2 to 83.1 in the reported ablation.
  • Rethinking MVGRL: Diffusion augmentation supplies additional global information but requires expensive matrix inversion and substantially increases graph density, memory, and processing costs.The reported graph-power computation takes 0.22 seconds on ogbn-arxiv and 209 seconds on ogbn-papers100M.
  • Efficiency Analysis: For sparse graphs with |E| = O(N), GGD’s computation is dominated by its Siamese GNN and scales linearly with the number of nodes N.The encoder is run on both augmented and corrupted graphs.
Loading 2206.01535v2…