Contrastive Learning is Spectral Clustering on Similarity Graph
Authors: Zhiquan Tan
Yifan Zhang
Jingqin Yang
Yang Yuan
Venue: ICLR 2024 poster (2024)
Keywords: contrastive learning theory
self-supervised learning theory
representation learning theory
CLIP
multi-modal learning theory
markov random field
kernel method
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
TL;DR: We prove that contrastive learning is equivalent to spectral clustering on the similarity graph and characterize multi-modal representation learning using this equivalence.

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.

Published as a conference paper at ICLR 2024
CONTRASTIVE LEARNING IS SPECTRAL CLUSTERING ON SIMILARITY GRAPH
Zhiquan Tan' Yifan Zhang?* Jingqin Yang** Yang Yuan
"Department of Mathematical Sciences, Tsinghua University 'IIS, Tsinghua University *Shanghai Artificial Intelligence Laboratory *Shanghai Qizhi Institute [tanzq21, zhangyi F21, ]angjq21}en @emails.. ts tsinghua. edu. cn, vvanyangétsinghin enu.cn
ABSTRACT
Contrastive learning is 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, introduce the Kernel- InfoNCE loss, incorporating mixtures of kernel functions that outperform the standard Gaussian kernel on several vision datasets*.
INTRODUCTION
Contrastive learning has emerged as one of the most prominent self-supervised learning methods, especially in the realm of vision tasks (Chen et al., 2020a; He et al., 2019b). This approach trains neural network to map a set of objects into an embedding space, ensuring that similar objects are closely positioned while dissimilar objects remain distanced. The InfoNCE loss, exemplified by SimCLR (Chen et al., 2020a), is a widely employed loss function for achieving this goal.
In their inspiring work, HaoChen et al. (2021) demonstrated that by replacing the standard InfoNCE loss with their spectral contrastive loss, contrastive learning performs spectral clustering on the population augmentation graph. However, the spectral contrastive loss is seldom utilized in practice and is not applicable for analyzing the performance of various similarity functions in the embedding space. Furthermore, when employing the spectral contrastive loss, the final embedding constitutes combination of standard spectral clustering and an additional linear transformation. Consequently. existing results do not establish connection between the original Info loss and standard spectral clustering.
In this paper, we prove that SimCLR, the standard contrastive learning method, performs spectral clustering without modifying the InfoNCE loss or applying additional transformations to the em- beddings. Our analysis involves a collection of n objects X = _ ... X,,] within space X. For these objects, we define similarity graph with an adjacency matrix æ, such that πi, represents the probability X, and X, being paired together in the data augmentation step of contrastive learning. Notice that can be in general asymmetric.
Given this similarity graph, we aim to discover an embedding function f x + Z. Denote A f(X) as the embedding of X, and our objective is to ensure that the Gram matrix Kz with kernel l representing the similarities for Z closely approximates Please refer to Figure I for an illustration.
However, directly comparing with Kz can be difficult, there too many edges in both graphs. Therefore, we define two Markov random fields (MRFs) based on л and Kz and compare the MRFs instead. Each MRF introduces probability distribution of unweighted directed subgraphs
"Equal contribution.
1 'Corresponding author.
"The code is available
I foNCE.

---

Published as a conference paper at ICLR 2024
Similarity matrix
A'
Subgraph
Adjacency matrix
π
Wx X
Spectral clustering
A
t
1 Cross entropy
Ideal loss
Z f(x
Kz
W2 Z
InfoNCE
Gram matrix with kernel ls
Objects Weighted similarity
Proof path
MRF sampling
Loss function
Computation
An illustration of our analysis. The similarity matrix encapsulates the relationships between various images. Given the large size of the matrix, we employ a technique known as Markov Random Field sampling to sidestep the issue of direct utilization. Through research, discovered an equivalence between InfoNCE loss and method known as spectral clustering when a Gaussian kernel function was utilized, thus validating our approach.
Figure 1:
objects (Van Assel al., 2022), denoted as Wx and Wz respectively. As natural approximation to the ideal loss between π and Kz, we employ the cross-entropy loss between Wx and Wz. Our paper's surprising discovery is that the InfoNCE loss is equivalent the cross-entropy loss when each subgraph is constrained to have an out-degree of exactly one. Furthermore, when k is the Gaussian kernel, optimizing the cross-entropy loss corresponds to executing spectral clustering on æ. By combining these two observations, we conclude that employing the InfoNCE loss is equivalent to performing spectral clustering.
Our characterization of contrastive learning hinges on two crucial factors: the augmentation step that defines similarity graph, and the InfoNCE loss that measures the distance between two MRFs. Consequently, any other models incorporating these two factors can be similarly analyzed. Notably, the CLIIP (Radford et al., 2021) model for multi-modal learning fits within this paradigm. Utilizing the same framework, we establish representation theorem for CLIP, demonstrating that it performs spectral clustering on the bipartite graph induced by the paired training data.
Is it possible to improve the InfoNCE loss by using different kernel? Based the maximum entropy principle, we demonstrate that the exponential kernels are the natural choices for capturing the local similarity structure for contrastive learning. Empirically, observe that taking the mixture of Gaussian and Laplacian kernels, which maintain the aforementioned properties, can achieve better performance than the Gaussian kernel several benchmark vision datasets.
In summary, our main contributions include:
We prove the equivalence of SimCLR and spectral clustering on the similarity graph.
We extend our analysis to the modal setting and prove the equivalence of CLIP and spectral clustering on the multi-mode similarity graph.
Inspired by theory, we propose a new Kernel-InfoNCE loss with mixture of kernel functions that achieves better performance than the standard Gaussian kernel (SimCLR) empirically on the benchmark vision datasets.
2 BACKGROUND
In this section, we will introduce the basic knowledge we will use throughout the paper. In this paper, objects to denote data points like images or texts. Given matrix X, X; denote its i-th row, and X,, to denote its (i. j-th entry. Same holds for matrices like WX. x. where we use W x and W X.i.j. respectively.
2

---

Published as a conference paper at ICLR 2024
2.1 CONTRASTIVE LEARNING: SIMCLR
Given query object E X' one similar object (positive samples) Pi for q, and N - other objects {p:)-=. SimCLR finds function (usually neural network) that maps these objects to Z, to minimize the InfoNCE loss of q:
L(q. P1. (p:liz)) - log exp(sim(f(q)) f(P.)))
(I)
E exp(sim f(p:))/r)
Here, the actual loss of takes the summation over different qs, and is temperature hyperparameter. The sim (2 2,) function measures the similarity between Z, Z in 2, and is commonly defined as
sim Z, 2,) = [ 2, or Z Zj. or - 12 Z,il8/2 this paper, we consider the case that 2 is the unit sphere, i.e., ZZ ||z,|| = 1. This is because both SimCLR and CLIP have normalization
2, 2,
z Z;
step in the implementation (Chen et al., 2020a; Radford et al., 2021). Hence, [|Z ||2,, Z Zj. and
-1 2 112/ - Z Zj = -1--1-0 -1+ Z Zz.
(2)
Therefore, these losses the same up constant.
2.2 MULTI-MODAL LEARNING: CLIP
CLIP (Radford et al., 2021) a multi-modal model with a dataset containing millions of (image, text) pairs. During pretraining, for each batch of N pairs of data points, CLIP uses image encoder and a text encoder to get pairs of embeddings, and uses the InfoNCE loss to compute the correct N pairs out of N N possible connections. Specifically, given image a,, compare the its matching score of the paired text b, with the matching scores of other N 1 texts (byligs. using z, Z,
the loss C(a., b,, {bjbyz) defined in Eqn. (1) by setting sim (Z;, Zz) TT, || One can define the loss similarly for text, and the actual loss of the embedding network f takes the summation over all the images and texts.
2.3 REPRODUCING KERNEL HILBERT SPACE
Given two objects Z;, Zj E Z, consider a feature map o 2 - H. where the feature space H. is usually much larger than Z. We may define a kernel & that measures the similarity of Z,, Z, as kZZ,, Zj) A (z,),, (Z,)), i.e., the inner product between the two objects after mapping them to the feature space. For any vector h(Z.) = (h, pp( (Z.))) Specifically, (Z,) as vector in H. represents the function k(- Z,) Z R. because for any Z, E Z, we have (ZZ,, Z,) = (z,(Z)) 40 (Z,)). Formally, have: Definition 2.1 (Reproducing kernel Hilbert space). Let H be a Hilbert space R-valued functions defined non-empty set Z. A function & Z x Z RR is called reproducing kernel of H. and H. is a reproducing kernel Hilbert space, if satisfies
H. it also corresponds to function h(-) Z - R. defined as
vZ, E Z, k(, Z,) E H. VZ, E 2, vh H. (h, k(., Z.)) hZ.))
We focus on the cunslation-invariann be written as (Z. Z,) for k E Z + R. The Moore-Aronszajn's 's theorem states that if & is symmetric, positive definite kernel on 2, there is a unique Hilbert space of functions H on for which & is reproducing kernel.
kernel in our paper, where the kernel kZZ,, Zz) can always
For instance, the Gaussian kernel a symmetric, positive definite kernel that yields an RKHS with infinite dimensions. One of the advantages of reproducing kernel is that the similarity can be computed directly in 2 without using the feature map to go the potentially infinite dimensional Hilbert space. However, reproducing kernel's similarity structure should idcally align with the semantic meanings of specific tasks. For example, is unlikely to calculate the semantic similarity of two images directly using predefined reproducing kernel in the pixel space.
Consequently, we ask it is possible to find an embedding function f + Z, where can compute the similarity of two objects in X' with a predefined kernel function, i.c., whether Kz matches with π in Figure 1. In other words, we hope to map the objects to a space where the semantic similarity in X' is naturally embedded. This is the starting point of our paper.
3

---

Published as a conference paper at ICLR 2024
0.7
0.7
0.7
0.7
0.6
0.2
0.6
0.2
0.6
0.4
0.4
0.4
0.4
Prob=0.42
Prob=0.08
Prob=0.28
Prob=0
Figure 2: Sampling probabilities of the subgraphs defined by P(W; ).) The first subfigure represents the underlying graph π, the next three subfigures represent three different subgraphs with their sampling probabilities. The last subfigure has sampling probability 0 because the purple node has out-degree larger than
2.4 MARKOV RANDOM FIELD
In this subsection, we present the framework (without proofs) of MRF for dimension reduc- tion (Van Assel al., 2022). We have modified some definitions and lemmas for our learning scenarios, and the readers may check the paper for more details on this framework.
Consider objects Z [Z ... Zn] in 2. We use a symmetric and translation invariant kernel k: 2 - F to represent the similarities in 2, where symmetric means k(x) = x-x Given Z and k, we define the gram matrix as Kz & (A:Z, - (z))( which is also the adjacency matrix representing the similarities of objects in Z.
Due to the large size of and in practice π is usually formed by using positive samples sampling and hard to explicitly construct, directly comparing Kz and π can be difficult, so we treat them as MRFs and compare the induced probability distributions on subgraphs instead. In our paper, subgraphs are directed unweighted graphs from the set Sw _ (W& E {0, 1]nXn X v(i.j) E [n]² W., = 00. The
distribution of W is generally defined follows.
Definition 2.2 (Distribution of W). Let π E R4 we define the distribution P(W:n x
Q( (..) W... where (?(W) & II,E,, w.,=I called unitary out-degree filter.
To provide clearer interpretation of the definition, we can break down the expression ((W))[(.)e)ppp Wiy into two parts. Firstly, we view W as the adjacency of a graph, the unitary out-degree filter ((W) checks if each node of the graph has exactly one out-going edge. Therefore, only subgraphs with unitary out-degree will be preserved, while subgraphs with other out-degree values will be filtered out. As we will see later, this exactly corresponds to the setting that the InfoNCE loss uses exactly one positive neighbor. Secondly, [[G,)te[aaa TT the scores of each edge in compared with Wij. This multiplication results in the un-normalized likelihood of W under æ, it is noticeable that the constraint of single outgoing edge of each node that ensures that the multiplication results reflect the consistent of W and π. See Figure 2 for an illustration.
W., multiplies
By applying Definition 2.2 to Kz, obtain the following expression for P(W; Kz): P(W; Kz) Q W (W))eeeeeee -j) Wi,, This expression represents the prior probability of under Kz.
Due to the unitary out-degree filter, P(W; T)) has the following property.
Lemma 2.3. For W ~ P(; Vi E [n], W, ~ M(1 T./ / E3 Tiis), where M is the multinomial distribution. Moreover given any i, E [m). W, is independent to W.. Where W: is the i-th row of W, n, is the i-th row of π.
Below we define the cross entropy loss given distribution æ and the similarity matrix Kz.
H () - - Ewx~ log Pow.lloooaaa.. Wx;
(3)
The following lemma will be helpful analyzing the cross-entropy loss, which states that when two distributions can be aligned and decomposed, their cross-entropy loss also be decomposed.
Lemma 2.4. Assume X' = X, X ... Xs and there are two probability distributions and Q supported X. Suppose P = Pi ... P& and Q QI ... @ Qu. with P. and Q2 supported on X. Let H(P, Q) e F. [log Q(=)). Then H(P, Q) Σk H(P,, Q.).
4

---

Published as a conference paper at ICLR 2024
The next lemma shows that the cross-entropy loss can be converted to the combination of repulsion and attraction terms.
Lemma 2.5. minz H (Z) is equivalent to
min
Σ
Piy logh(Zz 2,) + log R(Z),
(4)
z
(1,))((1)3
where P = Ewx~P(sn) Wx). and R(Z) = Ewesw P(Z. W) with P(Z, W) (Z, W)Q(W).
oc
The second term in Eqn. (4) punishes trivial solutions like Z = 0, as 0 is mode for fx(-, W) for any W, which incurs large log RZ)). The first term can be interpreted using the graph Laplacian operator, defined below.
Definition 2.6 (Graph Laplacian operator). The graph Laplacian operator is function L that maps X n non-negative matrix to a positive semi-definite matrix such that:
Wis
if
Vi,j E [n]?, L(W)
W L O.W.
AE(m]
We will then introduce the definition of spectral clustering used in paper.
Definition 2.7 (Spectral Clustering). Let W I the adjacency matrix of a graph and be the graph Laplacian operator. Then the following optimization problem is called performing spectral clustering on the graph whose adjacency matrix is W:
min tr L(W)Z)+ E(Z),
(5)
where E(Z) is regularization term.
By simple calculation, when is the Gaussian kernel, the first term in Eqn. (4) becomes tr (Z T L'Z) where L = Ewx [L( In other words, Eqn. (4) is equivalent to doing spectral clustering with repulsion regularizer log R(Z).
3 CONSTRASTIVE LEARNING: SIMCLR
In this section, we will prove our main theorem that contrastive learning is spectral clustering on a similarity graph. We assume that there are finitely many objects in X, denoted as This is the same assumption used by HaoChen et al. (2021), who also demonstrated that the finite case can be easily extended to the infinite case by replacing sum by integral, adjacency matrix by adjacency operator, etc. For continuous augmentation methods like adding Gaussian noise, we can discretize in a natural way. Assuming finite number of objects can help avoid non-essential technical jargon.
With n objects in X, consider a similarity graph defined on these objects, which gives a similarity matrix π of size n. However, for real scenarios like learning images, it is extremely difficult to obtain such from human labeling. Therefore, we compute using the prior knowledge of the dataset. For example, in the original SimCLR paper (Chen al., 2020a), there are different augmentation methods. Each augmentation method may generate many different augmented images that look similar the original image. For every original image X,, we define a probability distribution such that each object X, gets sampled with probability Tij. For example, during the augmentation process, suppose X, has probability, say 1/9, to be an augmentation of X,, then TT. 1/9. Therefore, can be represented as vector in R
Stacking all probability distributions together for i E [n]. get matrix R2X", In this section, we assume the sampling process is symmetric, i..., ग.j = n The stochastic data augmentation samples Wx based i.e., Wx ~ P(;
5

---

Published as a conference paper at ICLR 2024
3.1 MAIN THEOREM
Theorem 3.1. For the SimCLR algorithm, denote I as the neural network, Z :- f(X), and a as the similarity graph defined by the data augmentation process where objects are connected iff they are posilive samples of each other. Then SimCLR is equivalent to solving the following program:
min L(T)Z) + log R(Z),
z
which runs spectral clustering on π.
Proof. Please refer to Appendix A.
Discussions. Empirically, the InfoNCE loss is applied to large batch of the object, rather than all the n objects that Theorem 3.1 requires. This explains why SimCLR RR benefits from larger batch size, large memory
e.g. Chen al. (2020a) bank for storing more samples.
batch size of 4096, and He et al. (2019b)
While using the same framework from (Van Assel al., 2022), our Theorem 3.1 is significantly different from their results on dimension reduction from at least two aspects. Firstly, in the object space X, we have predefined similarity graph æ,, but they were using a kernel matrix Kx based on X and a kernel kx. This is because in the dimension reduction setting, the imput objects are assumed to be well-structured data points, but in the self-supervised learning setting, the input objects are images or texts, where translation invariant kernel cannot be used for computing the similarities. Secondly, their cross-entropy loss directly computed from Kx, while Wx is never explicitly sampled. In contrast, in our method, π is never explicitly used, and the cross entropy loss is indirectly computed from the randomly sampled Wx.
The equivalence proved is exact. Therefore, after learning, the embedding space contains different components, corresponding to various (sub-) classes of the objects. This characterization naturally explains why contrastive learning works well for classification-rellted downstream tasks.
4 MULTI-MODAL LEARNING: CLIP
In this subsection, we extend Theorem 3.1 to the multi-modal setting by analyzing CLIP, which applies the contrastive loss to the image-text pairs. The image-text pairs can be represented with the following pair graph.
Definition 4.1 (Pair graph). Consider two modalities of objects A, B, and undirected unit-weight edges E (aa b,) a, A, b, B) The pair graph between A, B directed bipartite graph AA = (A, B, E), with the weight of each outgoing edge normalized by the out-degree of the node.
By definition, TA,B is not necessarily symmetric. Consider the where the dataset contains 10 images of "dog". all of them are connected to the same text "dog". In this case, the text dog has 1/10 probability to each image, while each image has only one edge with 100% probability to the text. However, since each row of π A.B is still a probability distribution, we still have the next theorem.
Theorem 4.2 (CLIP's objective). For the CLIP algorithm, denote π F. as the pair graph. Then CLIP is equivalent running the generalized spectral clustering π AA
Proof. Please refer to Appendix A.
Discussions. In Theorem 4.2, we say CLIP runs the generalized spectral clustering because L(T A.B. is not necessarily the Laplacian of a symmetric graph, although one still compute the optimal embedding Z following Eqn. (4). The pair graph may contain a huge number of isolated edges. Empirically, CLIP picks strong image and text encoders with good prior knowledge about the dataset. Such prior knowledge may bias towards a better embedding for grouping the isolated edges with more semanties.
Theorem 4.2 also assumes that all the objects are sampled in Wx. while empirically a really big batch size of 22,768 is used in Radford et al. (2021). Moreover, the probability distribution TP:: TA.B)

---

Published as a conference paper at ICLR 2024
used in Theorem 4.2 is slightly different from the implementation of CLIP, in the sense that CLIP uniformly samples the edges in E, but here we uniformly sample the objects in A B. When the image-text pairs dataset has high quality, the difference between these two sampling schemes becomes negligible as the variance of object out-degrees is extremely small.
4.1 APPLYING TO LACLIP
Due to computation resources limitations, we haven't implemented improved CLIP algorithm ourselves. Interestingly. a direct improvement to CLIP based on our theory was recently conducted. We shall present this algorithm LaCLIP carefully (Fan al., 2023) and discuss why can be seen as a direct application of our theory.
Roughly speaking, LaCLIP is direct extension of CLIP by not only incorporating image augmen- tations but using text augmentation as well. Specifically, we can treat language rewrites as text augmentations. For each image text pair KT), the text augmentation can be derived as follows:
augr (Ør) ~ Uniform ([vT, on .... TT.l))
(6)
where TT, is the text itself or its rewrite.
Then training loss over the images in LaCLIP becomes:
N
exp (sim (fr (augr (x+)) fr (augr (a+))) log
f
Σ exp (sim (fr (aug) (x+)) fo (augr (xf))) /T)
where fr and fr are image and text encoders respectively.
From the pair graph point of view, LaCLIP expands the nodes in the "text side" of the pair graph by including the nodes of the rewrite (augmented) texts. Moreover, the augmented images are connected to augmented texts, this augmented pair graph will have more clusters between similar objects than the original CLIP pair graph. Thus, from the spectral clustering, it will be natural to expect I IaCLIP shall cluster similar objects across modalities better than CL.IP Indeed, the zero-shot transfer ability of LaCL.IP significantly improves (Fan et al., 2023).
USING NEW KERNELS
5.1 MAXIMUM ENTROPY PRINCIPLE
In this subsection, we offer an interpretation of InfoNCE-like loss, suggesting that exponential kernels are natural choices use in this type of loss. Given a query sample q. let s/s represent the similarity between and the contrastive sample p, for i E [m]. computed by kernel k. Without loss of generality, assume P1 is the (positive) neighbor of q according to prior knowledge, but 1 is not necessarily the largest value in eù. Ideally, we desire th to be the largest or at least among the few largest similarities, which indicates that our kernel properly aligns with the prior knowledge of X.
To optimize toward this goal, we must design loss function that captures the ranking of th1- Since the ordering function is discrete and lacks gradient information, we need to convert it into a soft and continuous function that enables gradient- based optimization. Specifically, probability distribution a to represent the neighborhood structure of q in relation to 4/, satisfying 1/1 S E ayth;, and Vi, 0g 0. If t/ is the largest, e1 is the sole solution; otherwise, can be more diverse. For instance, when all th values are equal, a can be a uniform distribution.
employ
Intuitively, if there are numerous other the values similar éh, the neighborhood structure of q is not as optimal as when en is the only object close to q. Formally, this means a should have fewer non-zero entries or least concentrate on a1, We use its entropy (() =- -Et a log a to represent this diversity, which results in the following optimization problem.
(P1) maxa
H(a)
S.t.
a 1, = 10:=1,, 1, On 2
1 Di 0,4 50
By minimizing the solution of (PI), we can discover an embedding that more accurately approximates the prior knowledge. However, how can we solve (P1)? By introducing the Lagrangian dual variable
7

---

Published as a conference paper at ICLR 2024
O, obtain the subsequent program (P2)'s solution upper bound times the solution of (P1). Consequently, minimizing (P2) simultaneously produces a smaller upper bound (P1) as well, indirectly aiding us in achieving our objective.
(P2) maxa -F(a)
s.l. a In = 1, a1 an 20
where F((x) = 1/1 Σ 0,44 +
Ei=1 04 log
We present the following theorem for solving (P2).
Theorem 5.1 (Exponential kernels are natural). The solution of (P2) satisfies:
exp (+
E. (ax) -r log Di exp (+)%))
Proof. Please refer to Appendix A.
Using this framework, we can derive results akin to the max-min optimization formulation from Tian (2022) as a corollary.
5.2 BERNEL-INFONCE LOss
In this subsection, we will show how to use the derivation above to improve InfoNCE loss. The- exp(2
orem 5.1 suggests that the loss function of the form -T log Σー exp v:
natural choice for characterizing the neighborhood similarity structure. When the similarity between the query sample and neighbourhood sample is defined as y C - (q) - (P:)] where C is a large positive constant and 7 > We find recovers the exponential kernels defined as follows:
Ko (x,y) exp (- x y|1
(7,
(7)
We then define our kernel-based contrastive loss, Kernel-InfoNCE, as follows:
Cht Lntee- (1, PI, (p:) == - -log K3 Pi)
(8)
Li=1 Keep (4.
Note equation (8) can be easily derived by setting the kernel A in equation (3) to exponential kernel. Our framework in Section is suitable for explaining losses that are adapted from InfoNCE by changing kernels. We consider generalizing the exponential kernel a bit. We propose to use the mixture of two exponential kernels as potential candidates for replacing the Gaussian kernel. There are two kinds of mixing methods. The first one is taking the weighted average of two positive definite kernels.
The other mixing method is concatenation, which splits the input vectors into two parts, where the first part uses the first kernel, and the second part uses the second kernel. It is easy to see that both mixing methods maintain the strictly positive definite property of the base kernels. We list the two types of kernel mixtures below.
Simple Sum Kernel:
K( my) == exp(-Ilf(x) (xxlf((xx)((((x))))))
f(x;)113mm)) +exp(-11f(x)) - f(x))11//))
Concatenation Sum Kernel:
K(),, == exp((Il](xx))0 n] 100--ffa f(x) : + exp(-11
2n] f(x))a 2n 2n]]l//m)
6 EXPERIMENTS
In our experiments, we reproduce the baseline algorithm SimCLR (Chen et al., 2020a), and replace SimCLR's Gaussian kernel with other kernels. We then test against SimCLP RR using Kernel-InfoNCE
8

---

Published as a conference paper at ICLR 2024
Table I: Results on CIFAR-10, CIFAR-100, and TinyImageNet datasets.
CIFAR-10
CIFAR 100
TmnglnageNet
Method
200 epochs
400 epochs
200 epochs
400 epochs
200 epochs
400 epochs
SimCLR (repro.)
88.11 + 0.09
90.60
62.57 + 0.10
66.29 + 0.12
34.00 0.18
37.83 0.09
Laplacian Kernel
89.26 +: 0.18
9.103
63.16 0.15
06.09 = 0.11
35.91 0.21
38.71
7 0.5 Exponential Kemel
89.00 0.07
0.123
63-48 + 0.22
65.81 + 0.19
34.17 0.13
38.75
Simple Sum Kernel
89.52 0.09
91.72 0.10
66 67 = 0.20
68.62 = 0.15
36.61
= 0.13
39.38 01.38:00 0.16
Concatenation Sum Kernel
89.89 = 0.18
91.28 + 0.07
66.10 + 0.21
68.57 + 0.11
35.98 + 0.17
38.77 + 0.22
loss on various benchmark vision datasets, including CIFAR-10/100 (Krizhevsky al., 2009) and TinyImageNet (Le & Yang, 2015).
For each algorithm, we first train encoder I on the training dataset to minimize the empirical loss function generated by the kernel. Then, following the standard linear evaluation protocol, we freeze the encoder and train a supervised linear classifier, which takes the output representation of f as input. Additional experimental details, dataset information, and results can be found in Appendix B.
Experimental Results. We summarize our empirical results on various benchmark datasets in Table 1. It is evident that we have achieved better performance than SimCLR on all three benchmark datasets, with the Simple Sum Kernel reaching the best average performance.
RELATED WORK
Contrastive learning constitutes a classical method extensively employed representation learn- ing (Hadsell et al., 2006; Becker & Hinton, 1992). Owing to its recent applications in self-supervised learning, contrastive learning has garnered widespread attention and achieved state-of-the-ar re- sults in numerous downstream tasks within computer vision (Tian al., 2020; Cui et al., 2021), graph representation learning (You et al., 2020; Hassani & Khasahmadi, 2020; Deng et al., 2022), multi-modality (Radford al., 2021), and beyond. Contrastive predictive coding (Oord al., 2018) represents one of the pioneering methods to incorporate the concept of contrastive learning in sulf-super learning. Subsequently, various methods have sought enhance performance. SimCLR (Chen et al., 2020a) and MoCo (Chen et al.. 2020b) advocate for utilizing a large batch size and momentum update mechanism to guarantee effective learning. Moreover, the hard negative sampling method (Kalantidis et al., 2020) has been explored to mitigate the impact of false negative sampling.
Despite the empirical success of contrastive learning, the theoretical comprehension of its underlying mechanisms remains limited. Oord et al. (2018) demonstrate that the InfoNCE loss can be regarded as surrogate loss for maximizing mutual information. Arora et al. (2019) give the generalization bound for contrastive learning under a latent class assumption. HaoChen et al. (2021) incorporate the concept of augmentation graph to facilitate the analysis of contrastive learning and propose surrogate loss spectral contrastive loss. They show that this surrogate loss is equivalent to spectral clustering on augmentation graph. Wang et al. (2022) propose that aggressive data augmentations lead to overlapping support of intra-class samples, allowing for the clustering of positive samples and the gradual learning of class-separated representations, providing new insights of understanding contrastive learning. Balestriero & LeCun (2022) link a variant of contrastive loss to the ISOMAP algorithm. Hu al. (2022) connect contrastive learning with stochastic neighbor embedding. Wang & Isola (2020) reveal that the quality of embedding can be decomposed into an alignment component and uniformity component, considering both the loss function and the embedding space.
CONCLUSION
In this paper, we take the probabilistic perspective of contrastive learning, and prove that it is essentially running spectral clustering on the predefined similarity graph. Extending this result to multi-modal learning, we show that CLIP is also doing the generalized spectral clustering on the pair graph. Based on the maximum entropy principle and other useful properties, propose to use the mixtures of exponential kernels (Kemel-IInfNNE loss) to replace the Gaussian kernel, which has achieved better performance empirically.

---

Published as a conference paper at ICLR 2024
REPRODUCIBILITY STATEMENT
For reprodueibility, we share our code at https://gitthi hot.aaoaaoaaaaaaaaaaa.ee Kernel-InfoNCCe The experiment results can be reproduced following the instructions in the README document. We also provide our experiment details Appendix B.
ACKNOWLEDGMENTS
The authors would like to thank Van Assel for clarifying a derivation step in his paper, and anonymous reviewers and ACs for their helpful suggestions. This work is supported by the Ministry of Science and Technology of the People's Republic of China, the 2030 Innovation Megaprojects "Program on New Generation Artificial Intelligence" (Grant No. 2021 AAA01500000
AUTHOR CONTRIBUTIONS
Yifan Zhang suggests the relationship between MRF and contrastive learning. Zhiquan Tan discovered the MRF framework for dimension reduction (Van Assel al., 2022), and applied this framework to prove Theorem 1. He also introduced the viewpoint of the maximum entropy principle for contrastive learning. Yifan and Zhiquan proposed Kernel-InfoNCE loss and refined the paper. Jinggin Yang did comprehensive experiments on Kernel-InfoNCe loss. Yang Yuan extended Theorem 3.1 to CLIP, and wrote most of the paper.
REFERENCES
Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saun- shi. A theoretical analysis of contrastive unsupervised representation learning. arXiv preprint arXiv:1902.09220 09229992.. 2019.
Randall Balestriero and Yann LeCun. Contrastive and non-contrastive self-supervised learning recover global and local spectral embedding methods. arXiv preprint arXiv:2205. /508, 2022.
Suzanna Becker and Geoffrey Hinton. Self-organizing neural network that discovers surfaces in random-dot stereograms. Nature, 355(6356):111-166 1992. 9
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International conference on machine learning, pp.
1597-1607. PMLR, 2020a. 1, 3, 6, 8,
Xinlei Chen, Haoqi Fan, Ross B. Girshick, and Kaiming He. Improved baselines with momentum contrastive learning, 2020b.
Jiequan Cui, Zhisheng Zhong, Shu Liu, Bei Yu, and Jiaya Jia. Parametric contrastive learning. In Proceedings of the IEEE/CVF international conference on computer vision, pp. 715-724, 2021.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference computer vision and pattern recognition, pp. 248-255. leee, 2009. 14
Zhijie Deng, Jiaxin Shi, Hao Zhang, Peng Cui, Cewu Lu, and Jun Zhu. Neural eigenfunctions are structured representation learners. arXiv preprint arXiv:2210. /2637, 2022. 9
Lijie Fan, Dilip Krishnan, Phillip Isola, Dina Katabi, and Yonglong Tian. Improving clip training with language rewrites. arXiv preprint arXiv:2305.2008. 2023.
Raia Hadsell, Sumit Chopra, and Yann LeCun. Dimensionality reduction by learning invariant mapping. In 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR106) volume 2, pp. 1735-1742. IEEE, 2006. 9
Jeff Z HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma. Provable guarantees for self sulf-super deep learning with spectral contrastive loss. Advances in Neural Information Processing Systems, 34:5000-5011, 2021. 1, 5,9
10

---

Published as a conference paper at ICLR 2024
Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning graphs. In International Conference on Machine Learning, pp. 4116 1116-4126. PMLR, 2020. 9
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016. 15, 16
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. arXiv preprint arXiv: 191 1911.9722, 2019a. 16
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. arXiv preprint arXiv: (XX1v:9111.077000 2019b. 1,6
Tianyang Hu, Zhili Liu, Fengwei Zhou, Wenjia Wang, and Weiran Huang. Your contrastive learning is secretly doing stochastic neighbor embedding. arXiv preprint arXiv:2205. 2022. 9
Sergey Ioffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift, International Conference on Machine Learning, pp. 448-456. 2015. 15
Yannis Kalantidis, Mert Bulent Sariyildiz, Noe Pion, Philippe Weinzaepfel, and Diane Larlus. Hard negative mixing for contrastive learning. Advances in Neural Information Processing Systems, 33: 11798-21800 2020. 9
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Citeseer, 2009. 9, 14
Ya Le and Xuan Yang. Tiny imagenet visual recognition challenge. CS 231N, 7(7):3, 2015. 9, 14
Liam Li, Kevin Jamieson, Afshin Rostamizadeh, Ekaterina Gonina, Moritz Hardt, Benjamin Recht, and Ameet Talwalkar. Massively parallel hyperparameter tuning. arXiv preprint arXiv:1810.05934, 5, 2018. 15
Richard Liaw, Eric Liang, Robert Nishihara, Philipp Moritz, Joseph E Gonzalez, and Ion Stoica. Tune: research platform for distributed model selection and training. arXiv preprint arXiv:/807.00. 18, 2018. 15
Vinod Nair and Geoffrey E Hinton. Rectified linear units improve restricted boltzmann machines. In Ieml, 2010. 15
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv preprint 1807.08807.03744 2018. 9
Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International Conference on Machine Learning, pp. 8748 8763. PMLR, 2021. 2, 6,
The PyTorch Lightning Team. fiforch-lightming A machine learning library. https:: /tt::/ggtttt com/ Li Lightning AIA htta:///ww//..ginnn/ee/eeeeee/ee 1.8.6. 15
www.nn/g/eweeeeeeeeeeeeeeeeeeeee taaeees/tag///.. 6, December 2022. Version
Yonglong Tian, Chen Sun, Ben Poole, Dilip Krishnan, Cordelia Schmid, and Phillip Isola. What makes for good views for contrastive learning? Advances' in Neural Information Processing Systems, 33:6827-6838 2020. 9
Yuandong Tian. Understanding deep contrastive learning via coordinate-wist optimization. In Advances in Neural Information Processing Systems, 2022. 8
Hugues Van Assel, Thibault Espinasse, Julien Chiquet, and Franck Picard. A probabilistic graph coupling view of dimension reduction. Advances in Neural Information Processing Systems, 2022. 2, 4, 6, 10
11

---

Published as a conference paper at ICLR 2024
Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through align- ment and uniformity on the hypersphere. In International Conference on Machine Learning, pp- 9939. PMLR, 2020. 9
Yifei Wang, Qi Zhang, Yisen Wang, Jiansheng Yang, and Zhouchen Lin. Chaos is ladder: A new theoretical understanding of contrastive learning via augmentation overlap. arXiv preprint
0rXiv:2203.13457, 2022. 9
Yang You, Igor Gitman, and Boris Ginsburg. Scaling sgd batch size 32k for imagenet training. arXiv preprint S000:::77000880000 6(12):6, 2017. 15
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances in Neural Information Processing Systems, 33: 5812-5823, 2020. 9
12

---

Published as a conference paper at ICLR 2024
A APPENDIX FOR PROOFS
Proof of Theorem 3.1.
Proof. Our proof has two steps. In Step we will show that SimCLR is equivalent to minimizing the cross entropy loss defined in Eqn. (3). In Step will show that minimizing the cross-entropy loss is equivalent to spectral clustering on æ. Combining the two steps together, we have proved our theorem.
Step 1: SimCLR is equivalent to minimizing the cross entropy loss.
The cross entropy loss takes expectation Wx x PT;5 which means Wx has exactly one non-zero entry in each row i. By Lemma 2.3, we know every row of Wx is independent of other rows. Moreover, Wx.: M(1, / Σj π. (M1, π.), because π, itself is probability distribution. Similarly, know Wz also has the row-independent property by sampling over F(; Kz). Therefore, by Lemma 2.4, we know Eqn. (3) is equivalent to:
Ewx. log P(Wz. = Wx.: K2)].
This expression takes expectation over Wx,; for the given row i. Notice that W non-zero entry, which equals 1 (same for Wz Wz,:). As result expand the above expression to be:
Wx,i x, has exactly one
Pr(Wx.t X log Pr( (W z,1. 1).
it
By Lemma 2.3, Z.i.j = 1) = Kz,s// Kz for j + i. Recall that Kz = (k(Z; exp(-1| 1 7, 13/2r)
Z,) (E))eee which means kz,1,// Kz,ill Enge expl 12, Zull 222r for j * i, when is the Gaussian kernel with variance T.
Notice that Z: = [(X;,, so we know
expl exp(-11f(Xx f(x)) Exae exp((11f(XX)))
log Pr (Zz. =) -log log
(10)
f(Xx f(xx)1
The right hand side is exactly the InfoNCE loss defined in Eqn. (1). Inserting Eqn. (10) into Eqn. (9), we get the SimCLR algorithm, which first samples augmentation pairs (i.j) with Pr((,..,5 1) for each row i, and then optimize the InfoNCE loss.
Step 2:
minimizing the cross entropy loss is equivalent spectral clustering
By Lemma 2.5, we may further convert the loss to
min Σ P.. kZz Z,) + log R(Z).
(11)
(i.j)E[n)²
Since l is the Gaussian kernel, this reduces
min tr ((T)ZZL(TZ))))))) + log R(Z),
where we use the fact that E Ew [(W)) = L(T), because the Laplacian operator is linear and (x (Wx) n.
Proof of Theorem 4.2.
Proof. Since Wx P(: TA.B), we know Wx has exactly non-zero entry in each row, denoting the pair that got sampled. notable difference compared to the previous proof is we now have n ng objects in graph. CLIP deals with this by taking mini-batch of size 2N, such that
13

---

Published as a conference paper at ICLR 2024
nLA 7= ng = N. and adding the 2NV InfoNCE losses together. We label the objects in A as [na]] and the objects in as {na+ +, 7 + ng).
Notice that A. is bipartite graph, the edges of objects in A will only connect object in B and vice versa. We can define the similarity matrix in as Kz, where Kz (i, + = Kz +n =
k-Z Zj) for [nal.j [ns], and otherwise set Kz (i,j) 0. The rest is same as the previous proof.
Proof of Theorem 5.1.
Proof. Since the objective function consists of a linear term combined with an entropy regularization, which is strongly concave function, the maximization problem is convex optimization problem. Owing to the implicit constraints provided by the entropy function, the problem is equivalent to having only the equality constraint. We then introduce the Lagrangian multiplier À and obtain the following relaxed problem:
E(a) 11 Σ ar +
Σ o log + X (a 1n 1).
As the relaxed problem is unconstrained, taking the derivative with respect to a; yields
αā(()
da. -by + (logaa + ai
1 + +1 =
a4
Solving the above equation implies that a; takes the form a, exp (+ exp ( - 11) Since exp( $ vi.)
0ù lies on the probability simplex, the optimal or is explicitly given by oi = Dس expl [cre) Substituting the optimal point into the objective function, we obtain
exp
(1)
exp (+ E exp (#wD
exp (t
E. Fxx') 1/1
1==1 exp (+ W
log E exp (+
11 log
Σ exp
(
Thus, the Lagrangian dual function is given by
-E (ax) - log exp (1
Σ exp (+
B MORE ON EXPERIMENT DETAILS
CIFAR-10 and CIFAR-100. CIFAR-10 (Krizhevsky et al., 2009) and CIFAR-100 (Krizhevsky al., 2009) are well-known classic image classification datasets. Both CIFAR-10 and CIFAR-100 contain total of 60k 32 x 32 labeled images of different classes, with 50k for training and 10k for testing. CIFAR- 10 similar CIFAR-100, except there are 10 different classes in CIFAR-10 and 100 classes in CIFAR-100.
TinyImageNet Tiny ImageNet (Le & Yang, 2015) is a subset of ImageNet (Deng et al., 2009). There are 200 different object classes in Imaeene with 500 training images, 50 validation images, and 50 test images for each class, All the images in TinyImageNet are colored and labeled with size of 64 64.
Pseudo-code. Algorithm presents the pseudo-code for our empirical training procedure.
We also provide the pseudo-code for core loss function used in the training procedure in Algorithm 2. The pode almost identical to SimCLR's ' loss function, with the exception of an extra parameter 7.
14

---

Published as a conference paper at ICLR 2024
Algorithm Training Procedure
Require: trainable encoder network f. batch size N, augmentation strategy aug, loss function with hyperparameters args for sampled minibatch rii- do
2: for all i E 1, ..... N do
3: draw two augmentations L - aug (zi), 1/ - aug (15))
4:
= J (4:). 2 (())
5: end for
6: compute loss L = L(N, 2, z',, args)
7: update encoder network f to minimize L
8: end for
9: Return encoder network f
Algorithm 2 Core loss function C
Require: batch size N, two encoded minibatches 21, 22, y, temperature т
1: concat (z1: 22)
2: for E 1, ..... 2N, j E 11,...,2N 2N do
3: St.j = || 2
4: end for
5: define (i,,) (i,,j log Σズ (k7ri)epp((tt)
eap cxp(s:./7)
6: Return 2N Σm [1ii, + N) + l N.
Utilizing the core loss function C, we can define all kernel loss functions used in our experiments in Table 2. For all 2 with even dimensions n,, we define z1, = 2; n/2] and ZR, 24 [n/2 2 : n).
Kernel
Loss function
Laplacian
2N,,,,2,,y=11,
Sum
A C
=
Concatenation Sum
> > (N, 1, + (1 A) * (N, 2R.
2R, z/20 = T2)
0.5
C (N, 0.
Table Definition of kernel loss functions our experiments
Baselines. We reproduce the SimCLR algorithm using PyTorch Lightning (Team, 2022).
Encoder details. The encoder f consists of a backbone network and a projection network. We employ ResNet50 (He et al., 2016) as the backbone and 2-layer MLP (connected by batch normalization (Ioffe & Szegedy, 2015) layer and a ReLU Nair & Hinton (2010) layer) with hidden dimensions 2048 and output dimensions 128 (or 256 in the concatenation kernel case).
Encoder hyperparameter tuning. For each encoder training case, we randomly sample 500 hyperparameter groups (sample details are shown Table 3) and train these samples simultaneously using Ray Tune (Liaw al., 2018), with the ASHA scheduler (Li al., 2018). Ultimately, the hyperparameter group that maximizes the online validation accuracy (integrated in PyTorch Lightning) within 5000 validation steps is chosen for the given encoder training case.
Encoder training. We train each encoder using the LARS optimizer (You et al., 2017), LambdaLR Scheduler in PyTorch. momentum 0.9, weight decay 10-6, batch size 256, and the aforementioned hyperparameters for 400 epochs on a single A- 100 GPU.
Image transformation. The image transformation strategy, including augmentation, is identical to the default transformation strategy provided by PyTorch Lightning.
Linear evaluation. The linear head is trained using the SGD optimizer with cosine learning rate scheduler, batch size 64, and weight decay 10 for 100 epochs. The learning rate starts at 0.3 and ends
15

---

Published as a conference paper at ICLR 2024
Hyperparameter
Sample Range
Sample Strategy
start learning rate
log uniform
[0, 1]
uniform
T1, [0, 1]
log uniform
Table 3: Hyperparameters sample strategy
Moco Experiments. We also tested our method based on MoCo (He et al., 2019a). The results summarized in Table 4, Here choose ResNet18 (He et al., 2016) the backbone and set temperature of 0.1 as default. For our simple sum kernel, we set = 0.8. The results show that our method outperforms the original MoCo method.
Table 4: MoCo Experiment Results CIFAR-10 and CIFAR-100.
CIFAR-10
CIFAR-100
Method
200 epochs
400 epochs
1000 epochs
200 epochs
400 epochs
1000 epochs
MoCo (repro.)
76.41 0.12
80.01 0.15
84.45 0.08
47.02 0.11
52.50 + 0.07
57.62 0.15
Laplacian Kernel
78.09
46.12 0.22
53.44 0.17
59.10 10 0.14
Simple Sum Kemee
78.12 0.15
83.23 0.18
87.50 0.20
46.65 65 1 0.06
53.62 1 0.19
59.83 1 0.12
C EXPERIMENTS ON SYNTHETIC DATA
Consider a scenario with n clusters, each containing & vertices. Let the probability of vertices u and from the same cluster belonging to π p. Conversely, for vertices u and v from different clusters, let the probability of belonging to be We generate the graph π randomly, based on p and We experiment with values of 100 and n for ease of visualization, embedding all points in two-dimensional space. Each vertex's 's initial position originates from normal distribution. In each iteration, we sample subgraph of uniformly, ensuring each vertex has an out-degree of We then optimize the corresponding vectors using InfoNCE loss with an SGD optimizer and iterate until convergence. Our experimental setup consists of an SGD learning rate of 1, an InfoNCE loss temperature of 0.5, and batch size of 50. We evaluate two scenarios with different p and values: p = 1, q = O, and p = 0.75, = 0.2. The results of these experiments are visualized in Figure The obtained embeddings exhibit the hallmark pattern of spectral clustering of graph π.
16

---

Published as a conference paper at ICLR 2024
Figure Visualizations of the optimization process using InfoNCE, Loss on the vectors corresponding to π. Points of identical color belong to the same cluster within л. To showcase the internal structure of π. we randomly select 10 vertices from each cluster to display the edge distribution of π
17


Reviews:
[{"review_id": "FBwTx0WK1B", "reviewer": "Reviewer_PnKu", "summary": "The authors present a theoretical result concerning contrastive learning. Contrastive learning is a semi-supervised task that aims to map objects into an embedding space such that similar objects are close and dissimilar objects are far apart. Their results concern the widely-used SimCLR loss, an example of an InfoNCE loss. The authors show that optimizing InfoNCE is equivalent to solving a spectral clustering problem. Based on this theoretical insight, they give an argument that exponential kernels are natural and propose a variant of InfoNCE, Kernel-InfoNCE, where they use an alternative exponential kernel in place of the usual Gaussian kernel. Doing so led them to using a Simple Sum kernel, which achieves slightly improved empirical performance on CIFAR image-text data sets. \n\nThis paper is closely related to HaoChen et al 2021; that paper proposed a type of contrastive loss that constitutes performing spectral clustering. The authors of this paper extend this by proving that SimCLR itself constitutes performing spectral clustering. This paper is also related to Van Assel et al., 2022, which analyzes dimensionality reduction methods such as t-SNE using a Markov random field framework adopted by the authors of this paper.", "questions": "See above", "limitations": "", "rating": 10, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "This is an important theoretical result concerning a widely-used method. This work helps bridge the gap between theory and practice in contrastive learning. I have several comments, none of which are major.", "weaknesses": "Minor comments: \n\nI found parts of the text difficult to follow because it lacks guideposts explaining the purpose of each section at a high level. \n\nIt would help to have a definition of spectral clustering for the purposes of the paper. \n\nEq1: I think this is meant to be a sum over different q's; the text says as much, but that's not how it's defined in Eq1. \n\n\"we will flip $X_i$ to get $X_j$ with probability 1/9; it's not clear what \"flip\" means or why the probability is 1/9.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ENx5AvTHkU", "reviewer": "Reviewer_TB2Y", "summary": "The paper applies a probabilistic graph coupling perspective to view two typical constrastive learning methods, including SimCLR and CLIP, and interpretes them as spectral clustering or generalized spectral clustering. Moreover, it also attempts to propose to use exponential kernels to replace the Gaussian kernel. Preliminary experiments show that using a mixtures of exponential kernels to replace the Gaussian kernel in the SimCLR loss yields improved classification accuracy.", "questions": "- The reviewer was confused by the discussion before introducing problem (P1). It is weired to have a problem in (P2) and the solution in Theorem 5.1. \n\n- Moreover, there are mistakes in the formulation of (P2). It is neither the Lagrangian nor the Lagrangian dual problem. It is misleading or something is missig to claim minimizing (P2) producing an upper bound of (P1). \n\n- The reviewer cannot see that ``Theorem 5.1 suggests that the loss function of that form is a natural choice for characterizing the neighborhood similarity structure\".  \n\n- The reviewer is not clear how to have a RBF kernel from the form in Theorem 5.1.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "+ It is interesting to interprete the InfoNCE loss in SimCLR and CLIP into the perspective of probablistic graph coupling and thus find the connection to spectral clustering or generalized spectral clustering.", "weaknesses": "- The reviewer was confused by the discussion before introducing problem (P1). Since that it is required that the $\\mathbf \\alpha$ has fewer nonzero entries, some objective of sparsity-promoting property is necessary. However, in (P1) an entropy regularization term is imposed. It is well known that the optimal solution for the maximal entropy problem in the discrete random variable is a uniform distribution. Here, the optimal solution for $\\alpha_i$ should be $1/n$. It is weired to have a problem in (P2) and the solution in Theorem 5.1. Note that $\\tau$ is the Lagrangian multiplier, i.e., dual variable, it is incomplete to have the dual variable inside. \n\n- Moreover, there are mistakes in the formulation of (P2). It is neither the Lagrangian nor the Lagrangian dual problem. It is misleading to claim minimizing (P2) producing an upper bound of (P1). \n\n- In Section 5.2, it is stated that Theorem 5.1 suggests that the loss function of that form is a natural choice for characterizing the neighborhood similarity structure. The reviewer cannot see this point. Such a form is nothing but a choice on purpose to use the maximal entropy (or due ot mistakes?). \n\n- In Eq. (6), it is a RBF kernel, cannot be directly yielded from the form in Theorem 5.1. Because having an exponential form does not imply to have the property of a RBF kernel. In this way, the so-called kernel-InforNCE is nothing but a heuristic form to define the similarity in the InfoNCE loss function. \n\n- The related work is not good. Some remarks on the previous work are either improper or even misleading. \n\n- The experimenal evaluation is limited.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZKmgGvshdd", "reviewer": "Reviewer_Hqsc", "summary": "- The paper proves that contrastive learning with the standard InfoNCE loss is equivalent to spectral clustering on the similarity graph, which is defined by the data augmentation process. \n- The paper extends this result to the multi-modal setting and shows that CLIP is equivalent to spectral clustering on the pair graph.", "questions": "> see the Weaknesses\n- Could you please share your reasons behind this?  it to be innovative?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- It provides a novel theoretical analysis of contrastive learning and its connection to spectral clustering, which can help understand the underlying mechanisms and principles of this popular self-supervised learning method.\n- It proposes a new Kernel-InfoNCE loss with mixture of kernel functions that is inspired by theory and achieves better performance than the standard Gaussian kernel on several benchmark vision datasets", "weaknesses": "- I think the motivation is not good enough, such a conclusion is easy to obtain, i.e.,  InfoNCE loss is equivalent to spectral clustering. Since graph is pariwise relationship and constrastive is also pairwise relationship, both have the similar objective.\n- as the first point, I think the kernel infoNCE is also not well motivated. \n\n#### It's important to address these concerns regarding motivation in your paper. To improve the motivation for both the InfoNCE loss and the kernel InfoNCE, you might consider the following:\n\n> InfoNCE Loss Motivation:\n\n- Emphasize the practical significance and real-world applications of the InfoNCE loss. How does it relate to real-world problems or datasets in a way that goes beyond spectral clustering?\n- Highlight specific challenges or limitations in existing methods that the InfoNCE loss aims to address.\n\n> Kernel InfoNCE Motivation:\n\n- Explain how the kernel InfoNCE extends the motivation from the InfoNCE loss. What specific problems or scenarios does the kernel-InfoNCE address that are not covered by the standard InfoNCE?\n- Provide examples or use cases where kernel InfoNCE can be especially valuable.\n> By offering a more compelling rationale and demonstrating the practical relevance of these concepts, you can strengthen the motivation for these components in your paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CMGMWnYfdn", "reviewer": "Reviewer_5UyX", "summary": "This paper proves that contrastive learning with the standard InfoNCE loss is equivalent to spectral clustering on the similarity graph. Using this equivalence as the building block, the authors extend our analysis to the CLIP model and rigorously characterize how similar multi-modal objects are embedded together. Based on the maximum entropy principle, the authors demonstrate that the exponential kernels are the natural choices for capturing the local similarity structure for contrastive learning.", "questions": "1. Why choose Laplacian kernel and Simple Sum kernel for the MoCo experiment results should be further stressed, i.e., why the Gaussian kernel is not selected here.\n\n2. Why the authors choose p=1,q=0 and p=0.75 and q=0.2 in the syntetic experiment?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The  originality, quality, and significance are well supported by the proof of the equivalence of SimCLR and spectral clustering on the similarity graph and the extension to the multi-modal setting.\n\n2. The clarity is satisfied based on the clear illustration of the analysis in Figure 1 and the clear motivations and contributions in the Introduction part of this paper.", "weaknesses": "1. The rationality of treating K_Z and \\pi as MRFs and comparing the induced probability distributions on subgraphs should be better explaned, which is not well persuasive as shown in this version of the submitted paper.\n\n2. For the definition of W, the authors are expected to further explain the mentioned unitary out-degree filter, which may be confused for the readers in understanding this definition.\n\n3. The reason that cross-entropy loss can be converted to the combination of repulsion and attraction terms is expected to be further given after Lemma 2.4. Is it closely related to Lemma 2.5 and what is the specific relation?\n\n4. In the experiment, the improvements of the proposed method is not obvious compared with SimCLR on the given datasets. The authors should further analyze the reason for 200 epochs and 400 epochs, respectively.\n\n5. The authors should repeat each experiment for many times and list the mean and deviation to avoid the possible randomness, i.e.,  Table 1 and Table 4.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)