Lovasz Theta Contrastive Learning
Authors: Georgios Smyrnis
Matt Jordan
Ananya Uppal
Giannis Daras
Alex Dimakis
Venue: Submitted to ICLR 2023 (2023)
Keywords: Lovasz theta
Contrastive learning
Similarity graph
Graph Theory

Abstract: We establish a connection between the Lovasz theta function of a graph and the widely used InfoNCE loss. We show that under certain conditions, the minima of the InfoNCE loss are related to minimizing the Lovasz theta function on the empty similarity graph between the samples. Building on this connection, we generalize contrastive learning on weighted similarity graphs between samples. Our Lovasz theta contrastive loss uses a weighted graph that can be learned to take into account similarities between our data. We evaluate our method on image classification tasks, demonstrating an improvement of $1 \%$ in the supervised case and up to $4 \%$ in the unsupervised case.

Under review as a conference paper at ICLR 2023
LOVASZ THETA CONTRASTIVE LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
We establish a connection between the Lovasz theta function of a graph and the widely used InfoNCE loss. We show that under certain conditions, the minima of the InfoNCE loss are related to minimizing the Lovasz theta function on the empty similarity graph between the samples. Building on this connection, we generalize contrastive learning on weighted similarity graphs between samples. Our Lovasz theta contrastive loss uses weighted graph that can be learned to take into account similarities between our data. We evaluate our method on image classification tasks, demonstrating an improvement of 1% in the supervised case and up to 4% in the unsupervised case.
INTRODUCTION
The Lovasz theta function is fundamental quantity in graph theory. It can be considered as the natural semidefinite relaxation of the graph independence number and was defined by Laszlo Lovasz to determine the Shannon capacity of the 5-cycle graph (Lovász) 1979) solving a problem that had been open in combinatorics for more than 20 years. This work subsequently inspired semidefinite approximation algorithms (Goemans & Williamson, 1995) and perfect graph theory (Berge 200T). The Lovasz theta function requires the computation of a graph representation: for given undirected graph GVV, E) we would like to find unit norm vectors v, where E V, such that non-adjacent vertices have orthogonal representations:
of by 0, if (i. $ E.
Every graph has such representation, if the dimension of the vectors is not constrained. The Lovasz theta function searches for graph representation that makes all these vectors in a small spherical cap. These representation vectors can be obtained by solving semidefinite (SDP) program (see Gärtner & Matousek (2012) for a modern exposition).
Similarly, contrastive learning is representation learning technique that yields impressive recent results (e.g. Chen et al. (020b); He et al. (2020); Radford et al. (202T)). This training process aims to learn representations that have similar samples clustered together, while at the same time pulling different ones apart. This can be done in either an unsupervised fashion (i.e. without labels) or in a supervised way (Khosla al. 2020). Contrastive learning approaches typically consider similarity between elements to be binary two samples are similar (positive) or different (negative). However, is natural for some problems consider variability in similarity: Images of cats are closer dogs compared to airplanes, and this insight can benefit representation learning.
We establish a connection between contrastive learning and the Lovasz theta function. Specifically, we prove that the minimizers of the InfoNCE loss in the single positive case are the same (up to rotations) with those of the Lovasz theta optimum graph representation using an empty similarity graph.
Our Contributions:
Using this connection, we generalize contrastive learning using Lovasz theta on weighted graphs JJohansoon et al.) (2035). We define the Lovasz theta contrastive loss which leverages a weighted graph representing similarities between samples in each batch. Our loss is a generalization of the regular contrastive loss, since if positive examples are transformations of one sample and transfor- mations of other images are used as negative examples (so the underlying graph corresponds to the empty one), retrieve the regular constrastive loss. This way, any image similarity metric can be used to strengthen contrastive learning. For unsupervised contrastive learning, we show that our method can yield benefit of up 4% over SimCLR for CIFAR 100 using pre-trained CLIP image

---

Under review as a conference paper at ICLR 2023
Key idea of method. In this figure with respect to the similarity graph between the classes. In the case of regular supervised contrastive learning (on the left), the similarity graph considered is just the empty graph (no class is similar another). On the right, we see our proposed method. While different, the classes of dogs are similar each other and different from cats, so the graph considered by our method reflects that (edge boldness reflects weight magnitude).
Figure 1:
how our proposed method works,
encoder to obtain similarities. For supervised contrastive learning (i.e. class structure used) our method yields 1% benefit over supervised contrastive learning in CIFAR100 (Khosla et al. 2020
The key idea of our method can be seen in Figure [ where we see that we want to connect two samples more strongly if they semantically related. There exists body of work regarding graph representation learning Chen et al. (2020a), which learns functions on a given graph so that the distance between the representations is preserved. While related, work differs from this, since our contrastive learning loss does not seek to explicitly retain the structure of the graph, but rather use guide how aligned or unaligned the representations of some samples must be.
In the rest of this work, we first examine the relationship between the Lovasz theta function and the InfoNCE loss. We then extend the latter via intuition derived from weighted version of the Lovasz theta. Finally, we empirically evaluate our proposed loss, using several ways to model sample similarity.
RELATED WORK
2.1 LOVASZ THETA FUNCTION
The Lovasz theta function Lovászz 1979) is quantity which has been used approximate the chromatic number of graph. This is done by obtaining representation for each vertex, which is clustered around a certain "handle" vector. One of the most important aspects of this function is that it is easily computable by solving an SDP (Gärtner & Matousek (0122), despite the fact that the chromatic number used approximate very difficult to calculate general.
2.2 SELF-SUPERVISED CONTRASTIVE LEARNING
There has been a flurry of activity in self-supervision, e.g. (Chen et al. 2020b He et al., 2020 Oord ct al. 20188 Chen He 2021 Wu et al. 2018). The main goal learn general representations that are good for a variety of downstream tasks. Idcally, we want to learn representations that are more general than those obtained by training classifiers. Wu al. (2018) improved classification accuracy on ImageNet by a large margin over the state of the art. This was further simplified and improved by Chen et al. (2020b) by emphasizing the importance of data augmentations. More recent works (Oord et al. 2018 8 He et al. 2020 Chen & He 2022) extend this by maximizing mutual information. adding a momentum encoder or a stop-gradies
to one copy of their network, respectively. There has also been work obtaining features at multiple granularities of image to improve the learnt representations Zhou et al. (2022). Crucially, these works rely on large datasets of unlabeled data to learn quality representations that then be applied supervised learning tasks.
2

---

Under review as a conference paper at ICLR 2023
Recently, there has been work mining hard negative samples for contrastive learning (Robinson et al. 2021). This line of work considers negative samples that are similar to a given sample as hard negatives, and uses those to perform contrastive learning. While related our work, this approach
orthogonal, since it does not assume that the similarity between samples is a semantic relationship that we want to preserve.
Finally, a pair of works related to ours are those of HaoChen et al. (2021) and Shen et al. (0022) These works formulate the notion of relationship graph between the given samples, by assuming that two samples are connected via an edge with weight equal to the probability that they correspond
views of the same sample. This is a natural measure of similarity between samples. In our work, we shall explicitly use these similarities to perform contrastive learning.
2.3 SUPERVISED CONTRASTIVE LEARNING
Along this line, Khosla et al. (2020) argued that when available we could leverage label information to learn good representations without large amounts of unlabeled data. They use a contrastive loss to pull together representations of samples belonging to the same class and push them apart from those of other samples. Training under this supervised contrastive loss shows an improvement on the classification accuracy ImageNet compared to the cross-entropy loss, without any extra data.
2.3.1 MULTTI-LABEL CONTRASTIVE LEARNING
Several works such as Radford et al. 2021 and Cui al. (2117) use contrastive learning along with supervisory multi-labels such as tags to learn good representations. In particular, CLIP (Radford
al. 2021 maximizes the alignment between representations an image and those of its captions.
The most closely related to our work is the recent paper Zhang et al. (2022) that leverages similarity gleaned from the multi-labels of the data. They define class similarity by using the hierarchical information which can be derived by the multi-label of the sample. They incorporate class similarity information in the contrastive loss by adding a penalty factor for the pairs of images from different classes. The penalty term pushes together representations for images that have similar labels higher in the hierarchy of the multi-label. Thus, they define class similarity by the level at which the labels are similar in the multi-label hierarchy. Note that if the labels are only of single level, then this loss reduces to regular supervised contrastive loss.
In contrast to this work, our loss formulation is derived from principled theoretical connection between contrastive loss and the Lovasz theta function of graph. We define a new generalization of the contrastive loss that is derived from the Lovasz theta function. Moreover, we easily incorporate similarities between samples into our setting, either via class similarities as in ZZhan al. 2022), or via directly assigning similarity to samples.
THE LOVASZ THETA FUNCTION
We start with the classic formulation for calculating the Lovasz theta for a graph.
Definition 3.1 (Lovasz Theta of Graph). Let G (V, E¹) be given (unweighted) graph. Then we define as Lovasz theta of this graph, denoted as ((G), the optimal value of the following mini- mization problem, for N < d:
minimize wi..... un cERd subject to
max; I.....N [c J.
|| = |ug 12 = .... || ||c||== =
(1)
u. u, = O, v(i.)) E E.
Essentially, the solution to this problem is set of vectors u, which are a) aligned with the "handle" vector c and b) are orthogonal to each other when the corresponding vertices of the graph are not connected. This problem is closely related to the chromatic number of the complementary graph. Indeed, we can think of the representations as being the "colors" assigned to each vertex, with the colors being different when the two vertices are connected in the complementary graph.
3

---

Under review as a conference paper at ICLR 2023
In the following, shall use the Delsarte formulation of the Lovasz theta problem JJhhnnson al. 2013
Schrijver 1979):
minimize " CER subject to
max:=1....f
(c' u.)a
||11| | || u uj S 0, v(i.j) $ E.
uN || |e|===1
The reason for this that this formulation is more amenable to an extension on weighted graphs, as we shall see in the next section.
One critical property of the Lovasz theta function is that, while it used approximate chromatic numbers on graphs (which are known to be NP-complete to calculate in general), it is actually easy calculate, This due to the following formulation of equation 2
Theorem 3.1 (Gärtner & Matousek 2012). For N d, the optimization problem in equation 2 be rewritten in the following form:
can
minimize subject to
t, uf u.u Ug St. v(i,)) E, |0 = 1, Vi.
The above problem can be converted into a convex SDP by setting Y = [u][ v;la, (so we have Y 2 0). Thus, the above problem tells us that for each vertex in the graph we want to find a unit representation, such that the vertices which are not connected by an edge have dissimilar represen- tations (in other words, their inner product is minimized).
4 LOVASZ THETA AND CONTRASTIVE LEARNING
4.1 REGULAR CONTRASTIVE LEARNING
One of the most well-known losses used for contrastive learning the InfoNCE loss (Chen et al., 2020b
Wu et al. 2018 Henaf 2020: Van den Oord et al. 2018):
N
exp(vTu:/T)
LInfoNCE =
Σ log Σ jitt exp(vffo/7)
(4)
where v, is the positive sample with respect v. and T is temperature parameter. For the theoretical analysis, we shall make the following simplifying assumptions:
The representation vectors v; E Rd are all unit norm. This constraint often enforced in practice, with the representations produced by the network in question being normalized at the end. Moreover, we assume that N < d, or that the number of vectors is at most equal to their dimensionality. We refer the reader Appendix [ for further discussion.
The only positive sample with respect to v is itself (single positive case). This nullifies the positive term (which serves for alignment between views the same object).
Under these assumptions, we can reformulate our loss as follows:
N
LInfoNCE = const +
Σ log
Σ Jz
exp(o)
(5)
which we aim to minimize under constraint ||0:113 = for all Note that we have multiplied
the loss by > 0, which does not affect the minimization. This loss is directly related to the Lovasz theta problem, as can be seen by the following theorem:
Theorem 4.1 (Equivalence with Lovasz theta). For N < d, the Delsarte formulation of the Lovasz theta problem:
minimize subject to
t. Ms 1, Vi,
(6)
U
< t, Vi *
4

---

Under review as a conference paper at ICLR 2023
and the minimization of the second term of the InfoNCE loss:
minimize subject to
E i==
log Σ exp ||m0 1, Vi,
attain their minima at the same values of the matrix = VTV, where V is the matrix which has the vectors v2 columns (so they have the same minimizers up to rotations).
We defer the proof of this theorem to the Appendix. Intuitively, the connection between the two problems can be shown by bounding the second term of the InfoNCE loss and then considering the two problems as minimization over the inner products. can then be shown that the two problems achieve the same value for the same inner products. This theorem directly links the novel field of contrastive learning with a classical problem in graph theory, thus providing a novel direction in the theoretical underpinnings of contrastive learning.
We can also consider the case of the Supervised Contrastive Loss (Khosla et al. 2020). In this setting, the positive samples for each image are not only its different versions, but rather all images belonging to the same class. Formally, we can write this loss as follows:
SupCon
1
Σ PEP())
up
Σ log
exp(0) 00/00i/)) JEN(
Σ
P(1)
where P(i) = L:: y1 Mi} and N(1) = (i y # yÿ} the sets of positive and negative samples.
Our theorems above only regard the negative samples of the InfoNCE loss. While there works which employ techniques like a slowly moving target (Grill et al.] 2020) or a stop gradient on one part of the network (Chen He 2021) to avoid the use of negatives, they play a major role in the convergence of the simple formulation of the InfoNCE loss, encouraging uniformity across repre- sentations (Wang Isola 2020). By demonstrating this link of the negative samples with the Lovasz Theta, we can show an extension of the InfoNCE loss which can leverage this theoretical connection and use sample similarities within a batch, providing us with an alternative use for these samples.
4.2 EXTENSION TO SIMILARITY GRAPHS
Using the above formulation of the problem, we can leverage the graph theoretical aspect of the Lovasz theta order to incorporate similarity information into our contrastive problem. Let us assume that we have weighted graph G(V, W). with each vertex corresponding this graph, the weights Wiy correspond to the similarity between the samples i and j. As such, we have the condition that Wt,y E [0, 1] (in the case where this matrix of weights W becomes the identity matrix, then this formulation reduces to the regular contrastive loss). In this case, we use a weighted version of the Lovasz theta problem, where we also relax the equality conditions to inequalities (Johansson et al. 2015). This is formulated as:
sample. In
minimize "i..... .ER subject to
max u. | 122 u U S Waji Vi j
||u
|uN| ||||2
where Wiy in this case is the similarity between samples i and j. Indeed, the weight approaches O, the corresponding constraints become the same as in the Lovasz theta problem. If the weight approaches 1, then these samples are perfectly connected, and the corresponding constraint on their inner product becomes trivial. Any value wij E (0, 1) is degree of similarity the less similar the sample are, the more spread apart the representations need to be to satisfy the stricter upper bound.
Lemma 4.1. For N < d. the problem in equation 9 is equivalent to:
minimize Ui.... ekt e subject to
||m 1| || = _... || 112 2= == 1, o U, S Wis + (1 -
(10)
(1-wi,), Wei)t, Vi # + j.
5

---

Under review as a conference paper at ICLR 2023
T-
z/z;
Figure 2: Illustration of the effect of similarity terms wi in the Lovasz contrastive loss. The X-axis denotes the dot product between two features, and the y-axis represents the dot-product after the similarity terms are applied. For completely dissimilar samples, Wij = 0 and this reduces to the contrastive supervised loss. For partially similar samples, the contribution the negative-sample term of the contrastive loss is decreased. As the similarity increases to 1, this inner product vanishes from the Log- pog-Sum-Hi Sum-Exp of the uniformity term of the contrastive loss (the second term).
Using the Lovasz theta on weighted graph, we can create the following form of contrastive loss:
LLonaszoon
0
Σ log
Σ exp jæ
0 t
Wig
(II)
wig)
PEP())
Compared to LsupCon have multiplied the loss function by 0. For finite no difference the minimization, but for + O, this allows us to state the following:
0, this makes
Theorem 4.2. Consider the weighted Lovasz theia problem in equation and the minimization of the second term of the Lovasz theta contrastive loss:
minimize Ex....ERRR
= log Σ exp
Ui 7(1
(12)
subject to
1|01112= |/
|0
| =
Minimizing the limit of the objective of the second problem problem, if Wij < i
0 is relaxation of the first
We defer all proofs to the Appendix. This connection is what allows us to leverage equation to transform the loss we use into equation II In the unsupervised case, the first term consists of different views of the same sample. In any case, we make use of the positive term in our final loss.
We can make few more remarks regarding the term 0 (or other words, as the samples become less and less related), the fraction within the exponents in the above expression becomes closer to the one present in the regular supervised contrastive loss. As Wiy approaches 1 (so the two samples become more and more similar), if v; * vy (which satisfied assuming that the representations are not degenerate), the denominator goes to 0, but the numerator also becomes negative, making the term after the exponentiation negligibly small. this case, the constraint in equation 10 becomes trivial (since the vectors have unit norm).
o u. - in the exponent. As wiy approaches 7(I=::)
The two points above demonstrate that our technique a natural extension of contrastive learning- Indeed, the latter is special case of the former, when the similarities are considered to be the identity matrix. We can also graphically see the effect of waj in each of the terms of the Log-Sum- Exp function. This effect visualized in Figure 2 where term inside the exponent. The higher Wij is, the less this term is penalized if the inner product is large (so the negative terms penalized less if the samples more similar).
that Wij varies the slope of the
One major design choice the above formulation that of the similarity graph that we use. We identify major approaches that be used to derive the similarity matrix.

---

Under review as a conference paper at ICLR 2023
Table Summary of our results on CIEARI00, unsupervised case. We compare our method with SimCLR, using the implementation provided by the authors of Khosla et al. (2020), and MoCo-v2, using the official implementation by the authors of of et al. (2020). The code for the baselines was run with the instructions provided by the authors' github pages, and was ran for 300 and 1000 epochs. We also experimented with two ways to derive our similarity matrix from CLIP.
MoCo-v2
SimCLR
Ours (cutoff)
Ours
ResNet-50, 300 epochs
58.25
64.42
67.52 + 0.79
68.14 + 0.46
ResNet-18 18, 300 epochs
51.96
58.64
60.39 + 1.01
60.70 + 0.73
ResNet-50, 1000 epochs
64.43
68.27
70.22 0.08
70.30 = 0.40
ResNet-18, 1000 epochs
58.94
63.41
64.88 + 0.12
65.24 + 0.19
Supervised case. If we assume that we have access to the labels of the samples during contrastive training, then we can derive the similarities between samples via the similarities between their respective classes. A simple way do this is the following:
1. We obtain a confusion matrix C = [co]]k=
from a pretrained classifier.
2. We normalize the confusion matrix across its rows (so that they all sum to 1).
We set C' [cu]k..E.....Naae
where dki 2 (cH + c.k) if k + and dka
otherwise.
This matrix C' is our class similarity matrix, and given two samples r, and Tyy, with corre- sponding classes yi and y,, we can define their similarity as way dy,,,"
Moreover, we use domain knowledge for the problem, and derive our similarity matrix in alternative fashion. Given hierarchical structure for the classes of the problem, we can derive similarity by considering classes that belong in the same hierarchical superclass as being similar. We examine the above choices in the experimental section.
Unsupervised case. we assume that we do not have access to the labels of our samples during the contrastive training process (or that only part of them is labeled), then we could also leverage pre-existing model to derive sample similarities directly. For example, we could use pretrained image encoder such as CLIP (Radford et al.) [2021), in order to derive a unit norm embedding vi for each sample Tú, and define the similarity between the two samples Wiy "I Vy- While in our experiments arising from this we also experiment by explicitly setting a cutoff in our similarities (setting any negative ones to 0), make this consistent with the rest of the similarity matrices.
didn't 't observe negative similarities
We refer the reader to the Appendix for further analysis. We also note the connection of this formu- lation with the work of Shen et al. (2022). where the authors cast contrastive learning as a spectral graph theory problem on the graph linking the views of the various samples. This graph has edges between views, with weight equal to the probability that the two views belong to the same sample.
EXPERIMENTS
We now examine the above formulation experimentally, by training models using the proposed form of contrastive loss. To do this, we first train our model for a amount of epochs on the given dataset, using the Lovasz theta paradigm we described above. The result of this training is a model which produces a set of good representations for the images in this dataset. We then freeze the learned representations and Iearn linear model on top of them. This linear classifier essentially considers the features of an image to be the outputs of the previous contrastively trained model. We evaluate the quality of our representations using the performance of this linear classifier metric, as in Khosla et al. (2020), by freezing the model learned during the contrastive procedure, and training linear classifier top of the frozen representations for small number of epochs. We also employ a technique commonly used in contrastive learning frameworks, where the contrastive loss is applied not on the representations v, but rather on the output of small head using these representations as input, namely on x = (he (Khosla et al., 2020 Chen et al. 2020b). After contrastive training is performed, this head is discarded, and the representations given input
7

---

Under review as a conference paper at ICLR 2023
Table 2: Summary of our results on CIFARIO0, supervised case. We can see that our method both training with only crossentropy (CE) and the supervised contrastive baseline (SupCon). Our method is implemented by constructing the similarity matrix via the confusion matrix, or via the superclasses in CIFAR 100. The numbers with are taken from Khosla et al. (2020).
CE
SupCon
Ours (Confusion Matrix)
Ours (Superclass)
ResNet-50
75.3*
76.5*
77.15 + 0.11
77.60 + 0.30
ResNet-34
74.98
75.81
76.06 + 0.29
76.55 = 0.40
ResNet-18
72.67
73.78
74.63 + 0.18
74.91 = 0.15
Table 3: Results on our ImageNet-100 experiment. We can see that our method yields slightly better accuracy over both classical Cross Entropy loss and Supervised Contrastive Learning.
CE
SupCon
Ours
ResNet- 18
81.08
81.20
81.58
ResNet-33
82.52
82.66
82.90
are used. In all of our comparisons, we examine ResNets of different sizes as the models trained in the contrastive fashion. Further experimental details can be found in the Appendix.
Unsupervised Similarity Matrix. In this setting, we derive our similarity matrix using the unsu- pervised approach mentioned above. We use CLIP to derive the cosine similarities between samples, and employ them in order to perform Lovasz theta contrastive training on our method. The results of our method can be seen in Table I This evaluation is similar to the one performed in Khosla et al. (2020) in that the feature extractor is trained from scratch using the CIFAR 100 dataset, and not using a transfer learning approach as done in other works (Chen et al. 2020b Grill et al. 2020).
We can see that our method outperforms regular MoCo-v2 and SimCLR pretraining on CIFAR100. This shows that using our similarity matrix, we can take advantage of sample similarities in the case where labels for each of the samples are not immediately available during contrastive pretraining. We refer the reader to Appendix C.T for further discussion on the quality of CLIP representations.
Supervised Similarity Matrix. In this setting, we consider the comparison of our method two supervised baselines. The first one is simple crossentropy loss (CE) where the model is trained in supervised fashion. The second one is that of supervised contrastive learning (SupCon) (Khosla let al. 2020). As mentioned above, this technique is a special case of our method, where each sample considered perfectly similar only to itself (hence the similarity graph is only the identity matrix). As such, direct comparison with it allows matrix provides to our method. We use the evaluation process we described above, on CIFARI00 and ImageNet-100 100 (a subset of 100 classes of ImageNet (Tian et al.) 2020)) using 3 different ResNet architectures. For CIFAR 100, define the similarity matrix via either a) the confusion matrix, derived from model trained with SupCon, or b) via the 20 superclasses defined over the 100 classes of CIFARI00 100 (Krizhevsky et al. 2009). The similarity between two classes belonging to the same superclass was considered as hyperparameter, and was equal to 0.5. For ImageNet-100, derive the similarities using a pretrained ResNet-50 provided by Pytorch. We can see our results in Tables and From our results on CIFAR 100 we infer that the use of the similarity matrix is indeed helpful to the training process. Intuitively, relaxing the constraint on the negatives allows the loss achieve better representation overall. A similar conclusion on ImageNet- 100, where again our method performs better than the baselines. We refer the reader to the Appendix for results on CIFAR10 as well as further experimental details.
to fully understand the benefits that the similarity
be obtained from our results
Ablation on Similarity Matrix. As noted previously, major design choice in our experiments is the method used to derive the similarity matrix, access to which is assumed by our method. Here, test this choice CIFAR 100, in the supervised setting. Namely, we consider the following two
8

---

Under review as a conference paper at ICLR 2023
Spocn Spect 130
Test Accuracy
13
Blending Parameter
Figure 3: Evolution of loss based on blending of similarity matrix. Both plots are based on CIFARI00 100, with models pretrained for 75 and 100 epochs. The blending parameter varies from 0 (similarity matrix identity as in SupCon) to (similarity matrix derived by the confusion matrix).
Table Ablation on the choice of the similarity matrix. Our two proposed choices are retrieving the similarities via the superclasses of the problem, and the other is to examine the inner products of the vectors produced by the text representations of CLIP. The first approach is better, but the CLIP approach gets adequate results, without explicit domain information other than the text labels.
Superclass Similarity
CLIP
ResNet-50
77.60
76.25
ResNet-34
76.55
75.19
ResNet-18
74.91
73.56
methods derive these similarities discussed above: using the superclass similarities provided for CIFARION 100 and using the inner products of the CLIP text representations the labels. Our results can be seen in Table We can see that the superclass similarity approach achieves better accuracy in all 3 of the considered models. However, we should note here that retrieving the similaritics through CLIP requires access only the labels of the problem, and is thus easier to retrieve.
Path from Contrastive Learning to Lovasz Theta Contrastive Learning. A final experiment that we conduct is varying the similarity matrix between the confusion matrix and the identity. For the supervised setting, if C is our class similarity matrix, set C' XC + (1 A)I,
similarity matrix, where À E [0, 1] is a blending parameter. This can show how our performance changes from À 0 (regular SupCon)
(our method). The results can be seen Figure We see that there is subtle and non-mon oonooootooicc but overall increasing trend in performance as the similarity matrix moves closer ours. As such, this blending can be tuned to improve the results.
CONCLUSIONS
We established a connection between the InfoNCE loss and the Lovasz theta of graph. This al- lowed us to generalize contrastive learning using general similarity graphs. Our technique can use any method of measuring similarity between samples to create problem-specifee constrastive loss. Our experiments show benefits over regular contrastive learning, in both the supervised and the additional informa-
unsupervised case, using simple similarity metrics. This is natural since tion provided in the similarity structure. The design decision of how to measure similarity between samples is central for our loss and opens interesting direction for future research.

---

Under review as a conference paper at ICLR 2023
ETHICS STATEMENT
We do not consider our work to have any immediate ethical considerations.
REPRODUCIBILITY STATEMENT
The proofs for all of the theorems in the paper are included in the Appendix. Regarding the exper- iments, we have included details for hyperparameters in the Appendix, and we have also provided anonymized code as part of the supplementary material. This code will be moved to a public repos- itory after the reviewing process.
REFERENCES
Claude Berge. The theory of graphs. Courier Corporation, 2001.
Fenxiao Chen, Yun-Cheng Wang, Bin Wang, and C-C Jay Kuo. Graph representation learning: survey, APSIPA Transactions on Signal and Information Processing, 9, 2020a.
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, 2020b.
Xinlei Chen and Kaiming He. Exploring simple siamese representation learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 15750-15758, 2021.
Peng Cui, Shaowei Liu, and Wenwu Zhu. General knowledge embedded image representation learning. IEEE Transactions on Multimedia, 20(1):198-207, 2017.
Bernd Gärtner and Jiri Matousck. Approximation algorithms and semidefinite programming.
Springer Science & Business Media, 2012.
Michel Goemans and David P Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM), 42(6): 1115-1145, 1995.
Mann-Batteen Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, Carl Doersch, Bernard Avila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, et al. Bootstrap your own latent-a new approach to self-supervised learning. Advances in Neural Information Processing Systems, 33:21271-21284, 2020.
Jeff Z HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma. Provable guarantees for self-supervised deep learning with spectral contrastive loss. Advances in Neural Information Processing Systems, 34:5000-5011, 2021.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 9729-9738, 2020.
Olivier Henaff. Data-efficient image recognition with contrastive predictive coding. In International Conference on Machine Learning, pp. 4182-4192. PMLR, 2020.
Fredrik D Johansson, Ankani Chattoraj. Chiranjib Bhattacharyya, and Devdatt Dubhashi. Weighted theta functions and embeddings with applications to max-cut, clustering and summarization. Ad- vances in Neural Information Processing Systems, 28, 2015.
Pramnay Khosla, Piotr Teterwak, Chen Wang, Aaron Sama, Yonglong Tian, Phillip Isola, Aaron Maschinot, Ce Liu, and Dilip Krishnan. Supervised contrastive learning. Advances in Neural Information Processing Systems, 33:18661-18673, 2020.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
10

---

Under review as a conference paper at ICLR 2023
László Lovász. On the shannon capacity of graph. IEEE Transactions Information theory, 25 (1):1-7, 1979.
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predic- tive coding. arXiv preprint 1rX.v:1807.037444 2018.
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.
Joshua David Robinson, Ching- Yao Chuang, Suvrit Sra, and Stefanie Jegelka, Contrastive learning with hard negative samples. In ICLR, 2021.
Alexander Schrijver. A comparison of the delsarte and lovász bounds. IEEE Transactions on Infor- mation Theory, 25(4):425-42) 1979.
Kendrick Shen, Robbie M Jones, Ananya Kumar, Sang Michael Xie, Jeff Z. HaoChen, Tengyu Ma, and Percy Liang. Connect, not collapse: Explaining contrastive learning for unsupervised domain adaptation. International Conference on Machine Learning, pp. 19847-19878. PMIR, 2022.
Yonglong Tian, Dilip Krishnan, and Phillip Isola.
Contrastive multiview coding. In European conference on computer vision, pp. 776-794. Springer, 2020.
Aaron Van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predic- tive coding, arXiv e-prints, pp. arXiv-1807, 2018.
Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through align- ment and uniformity on the hypersphere. In International conference on machine learning. PMLR, 2020.
Zhirong Wu, Yuanjun Xiong, Stella Yu, and Dahua Lin. Unsupervised feature learning via non- parametric instance-level discrimination. arXiv preprint
2018.
Shu Zhang, Ran Xu, Caiming Xiong, and Chetan Ramaiah. Use all the labels: A hierarchical multi- label contrastive learning framework. arXiv preprint arXiv:2204. 13207, 2022.
Pan Zhou, Yichen Zhou, Chenyang Si, Weihao Yu, Teck Khim Ng, and Shuicheng Yan. Mugs: A multi-granular self- supervised learning framework. arXiv preprint arXiv:2203. 22X1::2033.14115 2022.

---

Under review as a conference paper at ICLR 2023
APPENDIX
A DEFERRED THEOREMS & PROOFS
In this section, we include further theoretical results, including the proofs omitted from the main body of the paper.
On the assumption N < d. The assumption on the number of vectors allows us to convert the Lo- vasz theta problem into a convex one. Indeed, without this assumption, converting the problem into an SDP by setting Y = v would impose constraints on the rank of the matrix Y (specifically, rYnk(Y) I d). Since we know that rank( < N by construction, then having N I makes this rank constraint trivial. If we had these rank constraints, then the problem would be non-convex, given that the domain of the problem (a set of rank constrained matrices) is non-convex.
In practice, whether this constraint is satisfied is based on our choice for model dimensionality and batch size. can however be circumvented, by regular optimization methods operating directly on the representations 21 , UN (rather than their inner products). While the problem may no longer be convex, we can still apply first order optimization methods to find a good stationary point for the loss.
Proof of Theorem 3.1 (012))
The following is an adaptation of the proof found in Gärtner & Matousek
We first show that the following problems:
minimize Wi... M6 .EE subject to
k,
|| = |2g 12 = ... = |uNl2 2 ||c||2 =
(13)
u U < 0, (i. E E,
(c uz S ki Vi,
and:
minimize "i...," ER subject to
k
11 |/2 == =... | 112=1 2 U2 S
(14)
k- (ii & E,
k>
equivalent. To do this, shall show that optimal solution of the first problem be con- verted to a feasible solution for the second one, and vice versa.
Given optimal solution to the first problem Ui...., uN, with optimal value k, we can define the following set of vectors:
1
2:
(15)
Vk
1 c² u,
Note that the conditions of the first problem immediately imply that 2 1, as 0 (c )2 + 1 S Te" Jz S k. Thus, the optimal solution will have k > we can safely ignore the case h: = 1, as this implies that all the vectors are aligned, which can only happen if all vertices
connected. In this case the second problem will also have no constraints to be satisfied other than k > 1 (t < 0), and with no constraints / - approaches -a, which is consistent with k 1. For these vectors, the following hold:
2f žj
of uy
1 1+1) S -
--Σ
[c u,)
|
-
|| [e 4.
1+1 (
1. 1.
Let us now define the matrix Z, with columns the vectors 2,. Thus, z Z is positive semidefinite (by construction) and has diagonal elements which are less than or equal to 1. Thus, we can define the matrix Y z Z + D. where D is a diagonal matrix with non-negative elements, such that yos 1. This matrix Y is also PSD, which means that
write it Y vTV. The columns of V
12

---

Under review as a conference paper at ICLR 2023
precisely the vectors v; that form feasible solution of the second problem, since their inner products (off-diagonal elements of Y) satisfy the required constraints, and their norms (diagonal elements of Y) are equal to 1.
Now, given an optimal solution to the second problem, Ui,.... u with optimal value k. we can again define Y = V"V.. Here we can make an argument that Y must have at least one eigenvalue equal to 0 (in other words, the vectors v; must be linearly dependent). Indeed, if this was not the 0 sufficiently small. This means that the eI) is feasible solution to the second problem (note that the off diagonal
case, we would have Y > 0, so Y - -I ž O, where
matrix Y' = -- elements of Y are negative, multiplying them by positive constant decreases them) which also has lower value for the objective function, which a contradiction. Thus Y is singular, which also implies that there exists unit vector R that has c² u, 0, for all í. We can then define the following vectors:
1 u;
(c Sc+o.vk1 Vk
(16)
For these vectors, we have:
ut u; (1 +0+0+ (k: 1)0! 0j) S 0.
|2, = +1100++ 1
cTuu u JR 1.-
This means that the vectors u, along with e form a feasible solution for the first problem, with objective value k:
For the final step. we note that by setting = - - then by minimizing k we also minimize (since the latter is an increasing function of k). This means that our second problem is equivalent to:
minimize U ER subject to
||
-1022 1 2. vy S t, (i.
| 12= 1,
(17)
$
<<0
However, we note that the constraint 0 can be dropped from the problem. This is due to the fact that the rest of the constraints, for S d, can be satisfied by the solution where all the e; are orthogonal, for example 2, = c,, which would give where V is the matrix with v, as columns. We can then form Y' (1++)I e1, where e > 0 arbitrarily small and 1 the all-ones matrix. This new matrix will have 3/4 1 and V/y -c for all (i,j) & E. Moreover, it will be positive definite, as 1 has N eigenvalues equal to 0, and one of them equal to N, and so this implics that Y' has N (N 1)e >> 0 for arbitrarily small, Thus, we can find a feasible solution .'...., u'y such that Y = v '' and with = - < O. Thus, the optimal solution must have & < 0, meaning that the constraint can be dropped. This completes our proof.
0. Using this solution
base, we have
Y v Y=V"V
eigenvalues equal to
1 + and one of them equal to 1 + Ne
Theorem A.1. Theorem 4.1 in the main paper. For S d, the Delsarte formulation of the Lovasz. theta problem:
minimize subject to
t, 1 1, Vi, U₁
(18)
S t, vi # j.
and the minimization of the second term of the InfoNCE loss:
minimize subject to
T E log Ejtt exp v;
(19)
||0 1, Vi,
attain their minima at the same values of the matrix Y V the vectors vú as columns.
where V is the matrix which has
13

---

Under review as a conference paper at ICLR 2023
Proof. Note that by setting Y V'V, the first problem is converted into:
minimize subject to
t, Yi 1, Vi, Vi S 1, Vi + J. Y = 0,
(20)
while the second problem is converted into:
minimize subject to
E log > j exp
Wig
Yii 1, Vi,
(21)
Y 0.
Let us assume that we have feasible solution Y for the second problem. Let t = m(n-1) Enjapyy Bay (the average of the non-diagonal elements of Y). Due to the convexity of the ex- ponential function and the logarithm being an increasing function, we can apply Jensen's 's inequality in each of the sums inside the logarithms for each given i, thus giving
log
exp
Vij
log
(n exp n-1
jtt Vij
jf
==1
1
(22)
log(n (n 1) +
Vıj
n
i=1 374
=Tnlog(n - 1) + nd.
The final step is precisely the value of our objective function, when all Vij i + are equal to t. This means that, if we replace our solution with the average of the non-diagonal elements, then we will always decrease the value of the objective. Note that the new solution will still be feasible. Indeed, since the original matrix Y is PSD, we have:
1s y1 = n(n 1)t 1) n-1
(23)
The new matrix will use is:
Y
(24)
(so the diagonal elements are 1, and the non-diagonal ones are t). This matrix with rank-1
difference from the identity, and it has inner products of vectors with unit norm), and one eigenvalue equal to - tn = 1+ (n- 1)f (due to the above). Thus the new matrix is also a feasible solution, so is always optimal to have Viy Thus, rewrite problem as follows:
eigenvalues equal to 1 - f 2 0 (since / is the average of
minimize subject to
T Em= log Ej exP Vi:
Vii 1, Vi,
(25)
Vij + j,
Y > 0.
Given the condition for Vij, we can rewrite our objective function as:
log nnn cxp exp (+) Tn log (n(n 1)) + tn.
(26)
Thus, we can easily see that this problem has the same minimizing matrix Y as:
minimize subject to
1 Da = 1, Vi, Mij = t, + Y > 0.
(27)
Finally, we need to argue that this problem has the same optimal solution as equation 20 (or that, in other words, having the constraints Vij f be Vij < does not change the optimal solution).
14

---

Under review as a conference paper at ICLR 2023
This can be easily shown using the exact same argument above if assume that there exists an element Vay < the optimal solution, then we can replace the non-diagonal elements of Y with their average 7 < f, giving us a feasible solution Y' m 0, = 7 < t, which is impossible. Thus, the problem in equation 20 has the same minimizer matrix Y as that in equation 27 This completes the proof, as having the same matrix Y = v and having the vectors all be equal in norm means that the vectors chosen are unique up to rotations.
Lemma A.1. The following holds:
21
lim +
log
exp = max 2i.
(28)
[=1
1=1
Proof. We have:
2i 2 exp (=
exp
máx 2
max S log
exp
(29)
7
1=1
as well as:
max z4 ) =
T log
2
exp
Zi S r log
n nexp
maxxx2
log n1 + max zi-
(30)
2m
1m1
Thus, we get:
max S r log
Σ exp
2i
S t log n + máx 1=1
(31)
==1
1=1
and taking the limit as r + gives us the desired result.
We note here that the convergence is uniform: for given т, the difference between T log Ei=res exp and max 2; is upper bounded by 7 log n, which is independent of 21.-...- Za.
Lemma A.2 (Lemma 4.1 in the main paper). For N < d, the weighted Lovasz Theta problem can other words, the following formulations of the weighted Lovasz
be rewritten as in equation 33
theta problem are equivalent:
minimize Min Mx cERd
maxi=l.....
(c 2.
subject to
||u/112 = ||22| 12 ... |u 2| ||c|1 =
(32)
ui u, S Wij.
and:
minimize U.....yER* subject to
||0 11 1| 12 = _... || 1|2 1, 0. U, Wij + (1 W:y)t.
(33)
Proof. To go from the first problem the second, we begin by reformulating it as follows:
minimize
k
"..... uu cek subject to || = ||22||
uuN = ||c|| = 1,
(34)
u Uj < Wijs (c uu
F.
We can also reformulate the second problem as follows, by setting k- and noticing that increasing k increases:
minimize. U.... subject to ||0
k
|| 1| =
Juy 1|2 1,
(35)
T Uj
< m
k
15

---

Under review as a conference paper at ICLR 2023
Note that we can safely add the constraint t < 0 (equivalently & in the second problem without altering the solution. This is because the same argument as in the proof of the unweighted version holds. As Way 2 0 and N $ d. the solution of the vectors being orthogonal is feasible and will have a J S O. This is because one would have Wij + (1 wyy)) = 0 for some pair i,j with wi < (otherwise the constraint is trivial), and so f 1-wy S O. It is then possible alter the solution slightly as before to decrease all non non-diagonal elements so that < 0 also satisfied. It sufficient to show that the problems in equation [4] and equation [35 are equivalent. Following the technique used by Gärtner & Matousek] (2012) the regular Lovasz theta problem, we do so by showing the two problems have the same optimal value. Let p1 and p2 be the optimal values of the problems in equation 34 and equation 35 respectively.
To show that p1 2 P2, consider optimal solution ui, "y, c². For the same reasons as in the unweighted case, this solution will give p1 2 1, and P1 = only appears if there are no constraints on the inner products, Let us formulate the following matrix Y, with elements:
Uss I.
Mij
P1
1
u CxI u
c¹)
u cτ ctT
u
c²
P1 -1
u uiTuz ( (oTTu))etTTt
(36)
< -1
WrWij
P1 -1
We can also show that this matrix PSD; since yu Z Vij. Vj. Y can be written as Y D+U*U = O, where D is a diagonal matrix with non-negative entries and U is a matrix with columns equal to Consequently, we can use this Y, to create a feasible solution .1,.... UN via Cholesky factorization (i.e. Y VVT, whenever N < d (the constraints arise from the constraints placed on the matrix Y). This feasible solution has objective value pl for the second problem. This means that the second problem has optimal value p2 S pl.
o." ",
To show that P2 2 Pl, start from an optimal solution of the second problem vi...., Vi- Let Y be the matrix with Viy = oTTu uz- We note here that this matrix must have at least one eigenvalue equal to O. If this was not the case, then we would have Amin (Y") > O, and we could construct the following matrix:
Y' Y'=Y' e
(37)
where 1 is the rank-l matrix with all of its elements equal to 1. Note that this would strictly decrease all the non-diagonal elements of Y while leaving the diagonal ones intact. Furthermore, 1 has N - eigenvalues equal to O, and one of them equal to N (as 1u = Nu. where u is the all-ones vector). Thus, since I is a rank-1 1 difference from the diagonal, N of its eigenvalues being equal to 1 and one of them being equal to 1 - N < 0 (given the eigenvalues of I). Thus, we would have, for small enough:
Amin (Y') 2 Amin (Y*) + - (c1
(38)
Thus, by Cholesky decomposition again, we would have feasible solution to problem 35 with strictly smaller off-diagonal elements of Viy. which is a contradiction. Thus, one of the eigenvalues of Y must be O, which means that we can find vector which is orthogonal to all vi...., uy We can then define the vectors:
1
u =
_
10
V2
P2
1 c).
(39)
vP2
These vectors have:
u u;
1
1
((p2 1)0 03 + 1).
(40)
P2
Thus ||u, = 1 (p2 1 11+1) and uff uj S (Wir82
1) Wij- This means that they form a feasible solution for our problem, with objective value p2. Thus p1 S p2.
P2
pa
Combining all of the above gives us p1 = P2, making the above problems equivalent.
16

---

Under review as a conference paper at ICLR 2023
Theorem A.2 (Theorem 4.2 in the main paper.). Consider the followiinggorrulllitt of the weighted Lovasz theta problem:
minimize uy elt subject to
t,
|| 11 -.. | 11=== 1,
(41)
oa Dj waj + (1 - Way)t,
as well as the minimization of the second term of the Lovasz theta contrastive loss:
minimize Vi... subject to
+ E log
Σ exp
1. uz W 7(1-w15)
(42)
||0||2 |1112 222
| =
Minimizing the limit of the objective of the second problem as T - relaxation of the first problem, if wij < L.
Proof. Using the property of Log-Sum-Fxpp to converge uniformly to the maximum of its arguments as goes in this limit the objective of the second problem becomes:
minimize "1...,
Σ maxjşi
1-wiy
(43)
subject to || |/ | = -ow-=
(note that we do argue about the behavior of the minimizing solution of the problem T + O. but rather just the minimization of the limit of the objective function). We now include auxiliary variables &,. changing the problem into the following:
minimize uy....eN Elt subject to
Σ 4i
| 1| ||0 112 = = || 1|2 =
(44)
o U, S wij + (1 wis)ts, vi +
This is relaxation of the following problem:
minimize "y....WER"* subject to
Σ tis |00 2/2
|| 112
|| 1|
(45)
of Uj
Waj + (1 - wiy)ts vi +
t = t, Vi,
which is equivalent to precisely the weighted Lovasz theta problem:
minimize ui....weERt subject to
|1 12 1012_=_.. I 11, 2 U, S why + (1 - Wiy Vi t j.
(46)
In this case, the lack of symmetry of the problem does not allow us to immediately argue that all the must be equal.
B TRAINING DETAILS
In our CIFAR experiments, we made use of an A100 GPU to train our models. In the supervised case, our models were trained for 300 epochs, with batch size of 512, and the same set of hyper- parameters as those used the Supervised Contrastive learning baseline (Khosla et al., 2020). The architecture used in each of the experiments was a ResNet of varying depth, and the projection head used to perform contrastive learning was a two-layer MLP, reducing the dimension of the features to 128. Evaluation was performed by training linear classifier on top of the model for 10 epochs, and reporting the best accuracy obtained on the test set across all of the epochs. In the unsupervised case, the architecture is the same, but models where trained using batch size of 1024, leam- ing rate and temperature т equal to 0.5, and a linear probe trained for 100 epochs over the learned representations (as done in the repository for the code of Khosla et al. 2020
17

---

Under review as a conference paper at ICLR 2023
For our ImageNet- 100 experiments, made use of computing nodes with 4 RTX5000 GPUs. For models trained with cross-entropy, loss, we employed a batch size of 256. Moreover, we made use of Momentum Contrast, when training these models. During MoCo training,
maintained a batch
size of 256 and a memory bank of size 8192 as in Khosla et al. (2020). We trained each model for 200 epochs using the standard hyperparameter choices found in He et al. (2020).
Our baseline models were trained using the code directly provided by Khosla et al. (2020). The confusion matrix based similarities were obtained based the predictions of model trained with Supervised Contrastive Learning.
For the MoCo-v2 baseline, use the implementation provided by He al. (2220). with the stan- dard hyperparameters that they use, and learning rate 0.06 and batch size 512, following their linear scaling guidelines. The only alteration we perform are minor necessary modifications for the code to be compatible with CIFAR100.
For the similarity matrices derived by confusion matrices, they were chosen using the confusion matrices derived by the following models:
For CIFAR, the model used was ResNet-50 trained via SupCon CIFAR. The model was trained for 300 epochs, using the same parameters as in Khosla et al. (2020). and achieved similar accuracy the one reported in that paper.
For ImageNet-1000 the model used was a standard ResNet-50 provided by Pytorch, pre- trained on ImageNet.
The overall code is provided as part of the Supplementary material for review purposes, and will be made publicly available upon acceptance. The code is based upon the publicly available code of Supervised Contrastive Learning and Momentum Contrast, and all the relevant licenses are included.
C FURTHER EXPERIMENTS
C.I QUALITY OF CLIP REPRESENTATIONS
In our experiments above, we derived similarities via inner products using CLIP representations. To show that our method has benefit over simply training a linear model on top of those representations, we train linear classifier on top of a ResNet-50 CLIP model on CIFAR 100, using the preprocess- ing provided by the CLIP pretrained model. The accuracy we obtained from this evaluation was 67.12%, which is lower than SimCLR and our method trained for 1000 epochs, and even lower than our method trained for 300 epochs, as can be seen in Table I As such, we can see that these rep- resentations by themselves are not ideally suited for this task, but they can provide benefits to training procedure, by using our proposed method.
C.2 CONFUSION MATRIX VISUALIZATION
In this section, we include visualization of two similarity matrices used in the main paper. We can see the results in Figure 4 It is evident that the confusion matrix based approach is much more selective than the CLIP based one. Combining this with the fact that both the confusion matrix and the superclass similarities outperforms the CLIP based one, as seen in the experimental section, we can infer the result that the more selective the confusion matrix is, the better the results of our method are (which is also intuitively what we expect to happen).
C.3 EXPERIMENT ON CIFARIO
In Table 5 we can see the results of our method on CIFAR1O, using the similarity matrix derived via the confusion matrix of another model. We can see that while our method obtains good accuracy, we cannot get significant improvements over regular supervised contrastive learning. We believe that this is sensible limitation for our method due to the very small number of classes, it is highly unlikely that any are that similar to begin with. As such, the main benefit of our method, which is being able to leverage sample similarities via their classes during training does not apply. Nevertheless, since many important tasks contain a much larger number of classes, this is only a small limitation.
18

---

Under review as a conference paper at ICLR 2023
0.200
0.8
0.175
1
0.7
0.6
0.125
Class ID
40
Class ID
40
0.5
0.100
0.4
60
60
0.075
0.3
80
0.050
0.2
100
20
40
60
80
100
0.025
1
20
40
60
80
100
0.1
Class ID
Class ID
0.000
0.0
(a) Confusion matrix similarities.
(b) CLIP based similarities.
Figure 4: Similarity matrices used in the main paper, supervised setting. On the left, the confusion matrix similarities, and on the right the CLIP based similarities. In both cases, the diagonal has been set to 0 for the purposes visualization. We can see that while the confusion matrix approach is much more selective in which classes are similar to each other, the CLIP based similarities assign much greater similarities to all classes. This, combined with the results of the relevant experiments, shows the importance of the chosen similarity matrix.
Table 5: Summary of our results on CIFAR10. In this case, our method is competitive with SupCon, but there limitation due to the fewer number of classes. The numbers with * are taken from Khosla al. (2020).
CE
SupCon
Ours
ResNet-50
95*
96*
95.47
ResNet-34
95.15
95.28
95.07
ResNet-
94.37
94.61
94.69
C.4 ABLATION ON SUPERCLASS SIMILARITIES
As ablation, performed the experiments presented in the main paper regarding the superclass similarities on CIFAR, using a different value for the similarity of classes belonging to the same superclass. The results be seen in Table We that we get comparable results with those seen in the main paper. so tuning this hyperparameter may prove useful, in order to improve the performance of the model.
C.5 ITERATIVE UPDATES TO THE SIMILARITY MATRIX
As an extra experiment, we have included an iterative update scheme to our supervised setting. In this experiment, train a model on CIFAR 100 using superclass similarity matrix W as a base. Every 50 epochs, we calculate new similarity matrix W' via the confusion matrix of the current model. and set W = 3 W', with 3 = 0.9 hyperparameter. After training this model for 300 epochs, obtained accuracy of 76.68% on CIFAR 100. While this underperforms compared to our methods, it is still competitive and poses an interesting direction for further research.
D FURTHER DIRECTIONS
Based on all of the above, it not evident whether there a single way to obtain the proper similarity matrix, to get the best possible results. As be seen by experiments, this design decision
19

---

Under review as a conference paper at ICLR 2023
Table 6: Ablation superelass similarity. Our method has comparable results, based on how similar samples from the same superclass but different classes are considered to be (0.5 or 0.8 in this case).
Superclass Similarity 0.5
Superclass Similarity 0.8
ResNet-50
77.60 0.30
77.68 0.49
ResNet-334
76.55 = 0,40
76.35 + 0.06
ResNet-18
74.91 0.15
74.99 + 0.32
influences the performance of our models. As such, work opens interesting research directions in identifying good similarity metrics between samples in contrastive learning.
20


Reviews:
[{"review_id": "y69u-otXc7", "reviewer": "Reviewer_fWo7", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This work points out an interesting connection between Lovasz theta function and contrastive learning. More concretely, the negative term in the InfoNCE loss corresponds to the Lovasz theta problem, with zero weights. From this connection, the authors are able to extend the InfoNCE loss to a broader class and the experiments show some improvement over SimCLR.\n\n--post rebuttal--\n\nThanks to the authors for the rebuttal. After the revision, the paper looks better. However, the main contribution seems less novel to me. The connection Theorem 4.1 is somehow known in contrastive learning, for example, Theorem 5 (revised version) in https://sslneurips21.github.io/files/CameraReady/f-MICL-NeurIPS-workshop.pdf (the exact form is slightly different but it can extend to the current paper). I think the main novelty is the extension to different similarity weights, but the comparison with baseline algorithms is limited (only MoCo, SimCLR and SupCon). More SSL baselines are needed, e.g., SimSiam, BYOL, SwAV, etc. Also, the similarity term $w_{ij}$ needs to be discussed more. \n\nFor the fair comparison part, I don't understand the author's comment. Why can't we use CLIP as a pre-trained model for SimCLR? In this way, both Lovasz and SimCLR would have the same prior knowledge.\n\nIn summary, despite being interesting, I think this paper does not have enough contribution to be accepted, and I disagree with Reviewer 4DeW that it should be given the highest score of ICLR.", "summary_of_the_review": "In summary, my recommendation of the paper is mixed: on the one side, the connection with Lovasz theta problem is defintely interesting and opens up a new approach for finding similarity function; on the other side, this connection is not well explained in the main paper and more empirical comparison is needed.", "strength_and_weaknesses": "Strengths:\n1) The connection between the negative term of InfoNCE and Lovasz theta problem from graph theory is novel. The generalized version also makes sense, since the weight $w_{ij}$ represents the similarity between samples $i$ and $j$.\n2) The authors test the Lovasz generalization to both supervised and unsupervised cases, and show that the linear fine-tuning accuracy can be improved over SimCLR and SupCon.\n3) The supplementary code is attached for reproducibility.\n4) The similarity function can be defined from existing feature encoders such as CLIP. This is a highlight of the current work.\n\nWeaknesses:\nThere are indeed some places where this draft can be improved. \n1) Minor issues of writing/typos: some informal abbreviations: \"doesn't\", \"s.t.\"(eq. (3)), \"don't\", \"aren't\"; parenthesis in Theorem 3.1\n2) The connection part could be written more clearly. Some insights from the appendix can be summarized in the main text. For example, the Jensen's inequality of the negative term leads to a constrained optimization problem w.r.t. the inner products, and thus the Lovasz theta problem. \n3) The 2nd assumption in Sec 4.1 doesn't seem necessary. One can just say that the negative term relates to the Lovasz theta problem.\n4) The comparison between SimCLR and the proposed method is a bit unfair: the Lovasz theta method uses CLIP as some prior knowledge, but this is not used in SimCLR. Also, only SimCLR and SupCon are compared while there are many competitive contrastive learning methods such as MoCo (v1, v2, v3) and SimCLRv2.\n5) The theoretical analysis is not strong enough. Although the paper finds equivalence and extension of InfoNCE, it doesn't show any theory of convergence or generalization property.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "dYxTKnSxzF2", "reviewer": "Reviewer_4DeW", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper establishes a connection between the Lovasz theta function and contrastive learning. Specifically, with InfoNCE - a type of contrastive loss function used for self-supervised learning. They define a novel loss function - Lovasz theta contrastive loss based on a weighted graph representation of the similarities between examples.. \nThe loss function is evaluated with various ways of quantifying sample similarity. The method outperforms existing model SimCLR in both supervised and unsupervised contrastive learning. Previous works introduce the notion of using graph representation with edge weights equal to the probability that two samples correspond to views of the same sample. Current work uses that representation to perform contrastive learning. Under certain choices for model dimensionality and batch size, the paper shows an equivalence between minimizing InfoNCE loss and the Delsarte formulation of the Lovasz theta problem.\nThis equivalence is shown in both supervised and unsupervised cases. The equivalence is used to incorporate degree-of-similarity information into contrastive learning. So this method is a generalization of regular contrastive learning. In unsupervised cases, the method outperforms regular SimCLR pretraining on CIFAR100. In the supervised case, the method outperforms simple cross entropy loss and supervised contrastive learning on CIFAR100 and ImageNet-100. The method can be used with any similarity measure to create a problem specific contrastive loss.\nAs a proof of improvement, the work plots the effect of blending regular contrastive learning with the degree-of-similarity aware method they created. A parameter λ = 0 (regular SupCon) to λ = 1 (their method) is used to blend the effect of setting the class similarity matrix as C’ = λC + (1 − λ)I. It shows an overall improvement in performance as λ increases.\nThe work links the field of contrastive learning to classic graph theory and semi-definite programming. By doing this, it tries to provide a direction to understand the underpinnings of contrastive learning. \n", "summary_of_the_review": "The paper provides an contribution of bridging the field of contrastive learning with Lovasz theta functions and graph theory. We think it will pave the way for incorporating more similarity metrics into contrastive learning methods. The paper provides excellent explanations of contrastive learning functions therefore it is valuable for a wide audience. ", "strength_and_weaknesses": "The paper introduces a new loss function and provides proof that the minimization of certain terms in the proposed loss function is a relaxation of the weighted Lovasz theta function. To do this, they start with a very widely-used contrastive loss function - InfoNCE. They prove that minimizing InfoNCE is the same as minimizing a certain formulation of the Lovasz theta function. This provides a strong basis for the theory of contrastive learning. Additionally it provides a way to include similarity metrics into contrastive methods.\n\nHowever, the results showed minor improvements in performance from SimCLR. It is also prudent to compare the method with other SoTA self-supervised learning methods that learn fine-grained granular features like MUlti-Granular Self-supervised learning (Mugs). We advise the authors to do this as it will help measure the effect of using similarity metrics in this particular loss formulation on performance. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ZyxMb_5XyL", "reviewer": "Reviewer_NuU3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The authors established a connection between contrastive learning and the Lovasz theta problem. They show that with certain assumption the original loss function corresponds to Lovasz theta with an empty similarity graph. Then, by considering Lovasz theta on weighted graphs, they designed a new loss function that incoporates prior knowledge of similarity between examples. Experiements are performed to show that their method can be used to improve both unsupervised and supervised contrastive learning. ", "summary_of_the_review": "The contribution of the paper is two fold (1) it showed the connection between contrastive learning and Lovasz theta, which is a novel viewpoint of contrastive learning (2) and subsequently proposed a loss function that incoporates prior knowledge of similarity. However, the connection to Lovasz theta doesn't yet provide much insights into properties of the learned representations, since there is no further discussion about this in the paper. This may limit its theoretical contribution. Some details are missing in the experiment section. Also, I wonder if one should also expect that adaptively adding similarity information obtaind from the representations given by the current model every certain epochs during training can also improve the performance (i.e., training -> updating similarity matrix using current representations -> training -> updating -> training ...)", "strength_and_weaknesses": "Strength:\n1. The paper provides a new view of contrastive learning by showing its connection to the Lovasz theta problem, which may help further the understanding of contrastive learning.\n2. The proposed loss can be used to boost contrastive learning with any prior knowledge on similarity between examples. \n3. The proposed method can be seen as a new way of using information from pretrained models and transfering the useful knowledge in them to new relevant tasks in the context of contrastive learning. It is more flexible than finetuning since it does not require the model architecture to be the same as the pretrained one. \n\nWeakness:\n1. Theorem 4.1 only shows that the negative pair part in the loss is equivalent to Lovasz theta. The positive pair part is nullified by the assumption of the single positive case. This makes the result less informative considering that the positive part can play an important role. For example, [1] has shown that it encourages alignment between positive pairs and has certain interaction with the negative pair part which corresponds to uniformity. \n2. It is unclear what the quality of representations given by CLIP is. I think most likely it would not be very high, but it is still important to clarify since otherwise there is always a possibility that the CLIP representations are already good enough and it is trivial to beat the baseline by aligning the similarity output by the model with the good-enough representations'. \n3. More clarification is needed on the confusion matrix used in experiments. The authors said it is given by a model pretrained using supcon. But what is the setup for the pretraining and how long has the model been trained? what's the linear evaluation accuracy on its representations? Without knowing the answers to the above questions, it is hard to judge if the corresponding experimental results are meaningful. \n\n[1] Wang, Tongzhou, and Phillip Isola. \"Understanding contrastive representation learning through alignment and uniformity on the hypersphere.\" International Conference on Machine Learning. PMLR, 2020.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Jxb5_A9hQzW", "reviewer": "Reviewer_HNxb", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper studies the InfoNCE loss widely used in contrastive learning from the view of Lovasz theta function. In particular, regardless the positive-pair term of InfoNCE, minimizing InfoNCE corresponds to solving the Lovasz theta function. Inspired by this, the authors relax the constraint of Lovasz theta function beyond orthonormality, and revise the InfoNCE accordingly. Experiments show that the proposed weighted InfoNCE achieves an improvement of 1% in the supervised case and up to 4% in the unsupervised case.", "summary_of_the_review": "Overall, the idea is interesting and novel. The empirical performance is impressive. However, this is an unready paper. A number of issues need to be closed, especially the rigorousness of the theory part and how to interpret the weight $w_{ij}$ as a similarity. This paper needs to be further polished before acceptance.", "strength_and_weaknesses": "Strength:\n- The view of Lovasz theta problem is interesting.\n- The proposed loss achieves significant improvement on empirical performance.\n\nWeaknesses:\n- This paper can only deal with the negative-sample part of InfoNCE and ignores the positive-pair part. The quality of a representation should be affected by these two factors together and these two factors are not independent. \n\n- The relaxation (7) of the original problem (2) is not intuitive. Why do the authors explain the upper bound of  $u_i^T u_j$ as a similarity? Is the minimum similarity equal to zero? In the unsupervised case where CLIP is applied, the similarities could be [-1,1]? In summary, the authors should explain more about how to interpret the weight $w_{ij}$ in the weighted Lovasz theta problem as a similarity.\n\n- I carefully read the proof in the appendix. I find that (12) should include another constraint that $k>1$. Otherwise, (11) and (12) are not equivalent. Also, (15) should include the constraint that $t<0$. For example, (15) always has a feasible solution of $t=1$ while (11) may not have any feasible solution (e.g., $E$ is empty and $d<N$). Similarly, (31) also needs $t<0$. But this is weird: Since $w_{ij}>0$, the upper bound of $v_i^Tv_j$ becomes the weighted average of $1$ and a negative value $t$.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject