Contrastive Learning Is Spectral Clustering On Similarity Graph
- URL: http://arxiv.org/abs/2303.15103v4
- Date: Fri, 23 Feb 2024 13:32:47 GMT
- Title: Contrastive Learning Is Spectral Clustering On Similarity Graph
- Authors: Zhiquan Tan, Yifan Zhang, Jingqin Yang, Yang Yuan
- Abstract summary: We show that contrastive learning with the standard InfoNCE loss is equivalent to spectral clustering on the similarity graph.
Motivated by our theoretical insights, we introduce the Kernel-InfoNCE loss.
- Score: 12.47963220169677
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Contrastive learning is a powerful self-supervised learning method, but we
have a limited theoretical understanding of how it works and why it works. In
this paper, we prove that contrastive learning with the standard InfoNCE loss
is equivalent to spectral clustering on the similarity graph. Using this
equivalence as the building block, we extend our analysis to the CLIP model and
rigorously characterize how similar multi-modal objects are embedded together.
Motivated by our theoretical insights, we introduce the Kernel-InfoNCE loss,
incorporating mixtures of kernel functions that outperform the standard
Gaussian kernel on several vision datasets. The code is available at
https://github.com/yifanzhang-pro/Kernel-InfoNCE.
Related papers
- A Graph-Theoretic Framework for Understanding Open-World Semi-Supervised
Learning [33.05104609131764]
Open-world semi-supervised learning aims at inferring both known and novel classes in unlabeled data.
This paper formalizes a graph-theoretic framework tailored for the open-world setting.
Our graph-theoretic framework illuminates practical algorithms and provides guarantees.
arXiv Detail & Related papers (2023-11-06T21:15:09Z) - Hodge-Aware Contrastive Learning [101.56637264703058]
Simplicial complexes prove effective in modeling data with multiway dependencies.
We develop a contrastive self-supervised learning approach for processing simplicial data.
arXiv Detail & Related papers (2023-09-14T00:40:07Z) - CARL-G: Clustering-Accelerated Representation Learning on Graphs [18.763104937800215]
We propose a novel clustering-based framework for graph representation learning that uses a loss inspired by Cluster Validation Indices (CVIs)
CARL-G is adaptable to different clustering methods and CVIs, and we show that with the right choice of clustering method and CVI, CARL-G outperforms node classification baselines on 4/5 datasets with up to a 79x training speedup compared to the best-performing baseline.
arXiv Detail & Related papers (2023-06-12T08:14:42Z) - Fisher Information Embedding for Node and Graph Learning [5.263910852465186]
We propose a novel attention-based node embedding framework for graphs.
Our framework builds upon a hierarchical kernel for multisets of subgraphs around nodes.
We provide theoretical insights into generalizability and expressivity of our embeddings.
arXiv Detail & Related papers (2023-05-12T16:15:30Z) - GraphLearner: Graph Node Clustering with Fully Learnable Augmentation [76.63963385662426]
Contrastive deep graph clustering (CDGC) leverages the power of contrastive learning to group nodes into different clusters.
We propose a Graph Node Clustering with Fully Learnable Augmentation, termed GraphLearner.
It introduces learnable augmentors to generate high-quality and task-specific augmented samples for CDGC.
arXiv Detail & Related papers (2022-12-07T10:19:39Z) - Joint Embedding Self-Supervised Learning in the Kernel Regime [21.80241600638596]
Self-supervised learning (SSL) produces useful representations of data without access to any labels for classifying the data.
We extend this framework to incorporate algorithms based on kernel methods where embeddings are constructed by linear maps acting on the feature space of a kernel.
We analyze our kernel model on small datasets to identify common features of self-supervised learning algorithms and gain theoretical insights into their performance on downstream tasks.
arXiv Detail & Related papers (2022-09-29T15:53:19Z) - Hypergraph Modeling via Spectral Embedding Connection: Hypergraph Cut,
Weighted Kernel $k$-means, and Heat Kernel [1.8528929583956726]
We propose a theoretical framework of multi-way similarity to model real-valued data into hypergraphs for clustering via spectral embedding.
Our algorithm empirically shows better performance than existing graph and other modeling methods.
arXiv Detail & Related papers (2022-03-18T11:51:59Z) - Contrastive learning of strong-mixing continuous-time stochastic
processes [53.82893653745542]
Contrastive learning is a family of self-supervised methods where a model is trained to solve a classification task constructed from unlabeled data.
We show that a properly constructed contrastive learning task can be used to estimate the transition kernel for small-to-mid-range intervals in the diffusion case.
arXiv Detail & Related papers (2021-03-03T23:06:47Z) - Kernel learning approaches for summarising and combining posterior
similarity matrices [68.8204255655161]
We build upon the notion of the posterior similarity matrix (PSM) in order to suggest new approaches for summarising the output of MCMC algorithms for Bayesian clustering models.
A key contribution of our work is the observation that PSMs are positive semi-definite, and hence can be used to define probabilistically-motivated kernel matrices.
arXiv Detail & Related papers (2020-09-27T14:16:14Z) - Graph Neural Networks with Composite Kernels [60.81504431653264]
We re-interpret node aggregation from the perspective of kernel weighting.
We present a framework to consider feature similarity in an aggregation scheme.
We propose feature aggregation as the composition of the original neighbor-based kernel and a learnable kernel to encode feature similarities in a feature space.
arXiv Detail & Related papers (2020-05-16T04:44:29Z) - Embedding Graph Auto-Encoder for Graph Clustering [90.8576971748142]
Graph auto-encoder (GAE) models are based on semi-supervised graph convolution networks (GCN)
We design a specific GAE-based model for graph clustering to be consistent with the theory, namely Embedding Graph Auto-Encoder (EGAE)
EGAE consists of one encoder and dual decoders.
arXiv Detail & Related papers (2020-02-20T09:53:28Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.