# Efficient block contrastive learning via parameter-free meta-node approximation

arXiv: https://arxiv.org/abs/2209.14067 · HTML: https://mlsanity.com/paper/2209.14067/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 40 references that are in the map.
- First posted on arXiv 28 Sep 2022.

## Builds on (most cited first, 27 of 27)

- [A Simple Framework for Contrastive Learning of Visual Representations](https://mlsanity.com/paper/2002.05709/) (2020)
- [Momentum Contrast for Unsupervised Visual Representation Learning](https://mlsanity.com/paper/1911.05722/) (2019)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction](https://mlsanity.com/paper/1802.03426/) (2018)
- [Unsupervised Learning of Visual Features by Contrasting Cluster Assignments](https://mlsanity.com/paper/2006.09882/) (2020)
- [Understanding Contrastive Representation Learning through Alignment and Uniformity on the Hypersphere](https://mlsanity.com/paper/2005.10242/) (2020)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Graph Contrastive Learning with Augmentations](https://mlsanity.com/paper/2010.13902/) (2020)
- [Deep Graph Infomax](https://mlsanity.com/paper/1809.10341/) (2018)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [Unsupervised Deep Embedding for Clustering Analysis](https://mlsanity.com/paper/1511.06335/) (2015)
- [Contrastive Multi-View Representation Learning on Graphs](https://mlsanity.com/paper/2006.05582/) (2020)
- [Prototypical Contrastive Learning of Unsupervised Representations](https://mlsanity.com/paper/2005.04966/) (2020)
- [A Theoretical Analysis of Contrastive Unsupervised Representation Learning](https://mlsanity.com/paper/1902.09229/) (2019)
- [Graph Contrastive Learning with Adaptive Augmentation](https://mlsanity.com/paper/2010.14945/) (2020)
- [Debiased Contrastive Learning](https://mlsanity.com/paper/2007.00224/) (2020)
- [Graph Random Neural Network for Semi-Supervised Learning on Graphs](https://mlsanity.com/paper/2005.11079/) (2020)
- [An efficient framework for learning sentence representations](https://mlsanity.com/paper/1803.02893/) (2018)
- [Attributed Graph Clustering: A Deep Attentional Embedding Approach](https://mlsanity.com/paper/1906.06532/) (2019)
- [Structural Deep Clustering Network](https://mlsanity.com/paper/2002.01633/) (2020)
- [From Canonical Correlation Analysis to Self-supervised Graph Neural Networks](https://mlsanity.com/paper/2106.12484/) (2021)
- [Graph-MLP: Node Classification without Message Passing in Graph](https://mlsanity.com/paper/2106.04051/) (2021)
- [Attention-driven Graph Clustering Network](https://mlsanity.com/paper/2108.05499/) (2021)
- [Contrastive Laplacian Eigenmaps](https://mlsanity.com/paper/2201.05493/) (2022)
- [CGC: Contrastive Graph Clustering for Community Detection and Tracking](https://mlsanity.com/paper/2204.08504/) (2022)
- [SCGC : Self-Supervised Contrastive Graph Clustering](https://mlsanity.com/paper/2204.12656/) (2022)
- [FDGATII : Fast Dynamic Graph Attention with Initial Residual and Identity Mapping](https://mlsanity.com/paper/2110.11464/) (2021)

## Built on by (most cited first, 2 of 2)

- [NBC-Softmax : Darkweb Author fingerprinting and migration tracking](https://mlsanity.com/paper/2212.08184/) (2022)
- [T5-CSBoost: Adversarial Perturbation Resistant LLM Fingerprinting](https://mlsanity.com/paper/2607.14113/) (2026)

## Abstract (arXiv)

Contrastive learning has recently achieved remarkable success in many domains including graphs. However contrastive loss, especially for graphs, requires a large number of negative samples which is unscalable and computationally prohibitive with a quadratic time complexity. Sub-sampling is not optimal and incorrect negative sampling leads to sampling bias. In this work, we propose a meta-node based approximation technique that can (a) proxy all negative combinations (b) in quadratic cluster size time complexity, (c) at graph level, not node level, and (d) exploit graph sparsity. By replacing node-pairs with additive cluster-pairs, we compute the negatives in cluster-time at graph level. The resulting Proxy approximated meta-node Contrastive (PamC) loss, based on simple optimized GPU operations, captures the full set of negatives, yet is efficient with a linear time complexity. By avoiding sampling, we effectively eliminate sample bias. We meet the criterion for larger number of samples, thus achieving block-contrastiveness, which is proven to outperform pair-wise losses. We use learnt soft cluster assignments for the meta-node constriction, and avoid possible heterophily and noise added during edge creation. Theoretically, we show that real world graphs easily satisfy conditions necessary for our approximation. Empirically, we show promising accuracy gains over state-of-the-art graph clustering on 6 benchmarks. Importantly, we gain substantially in efficiency; up to 3x in training time, 1.8x in inference time and over 5x in GPU memory reduction.