Summary
The authors describe a theoretical framework for contrastive learning of representations in an open-world setting, where both labelled data and unlabelled data of potentially new classes is available. They explicitly describe the graph encoding positive sample connections and formulate a contrastive loss that amounts to a spectral decomposition of the adjacency matrix. Using this framework, they prove two theorems about the change in clustering quality of their representations via k-means when incorporating some labels. The main take-away is that labelled data helps to cluster another class if this other class has strong connections to the labelled class via data augmentation and was previously poorly clustered. Their method also outperforms several competitors for open-world and self-supervised representation learning with subsequent clustering.
Strengths
I appreciate the theoretical nature of the paper. Understanding the behavior of machine learning models when a clear learning signal via labels is unavailable or just partially available is important for their development and trustworthiness. It is also encouraging that their framework does not only allow a formal investigation but also holds up practically. I find the paper is well written with an appropriate deferral of more technical parts to the appendix. The authors also discuss connections of their work to the more common contrastive SimCLR loss. Their theory seems to be novel for the setting of open-world representation learning.
Weaknesses
**Strength of different types of augmentations:**
In the illustrative example in section 4.1. it is assumed that the probability $\tau_c$ of augmenting across classes if there is a shared attribute (e.g. augmenting a blue cube to a blue ball) is larger than the probability $\tau_s$ of just changing attributes within a class (blue ball to red ball). I find this quite counterintuitive.
First, I am surprised that $\tau_c$ should be non-zero. This might be achievable in the toy setting, but for any real world data, say CIFAR10, it is very unlikely, if not impossible, to augment two images of different classes to the same image. Maybe a plausible change of class can be achieved via cropping (cropping an image of a dog in front of flowers to just the flower) but it still seems unlikely that there should be another image in the dataset that augments to the same view. The same argument applies, to a lesser extend, also to the question if two images of the same class can be augmented to the same view (positivity of $\tau_s$). In the toy setting, I also wonder how positions and sizes were treated. Can a large blue ball in the top left corner only augment to a large blue cube in the top left corner or to any blue cube?
Second, I am surprised by the order of augmentation probabilities. Is it not more likely for two data points of the same class to augment to the same view than for two data points of different classes? A similar requirement seems to relevant for Theorem 4.2 (l255 ff). How crucial are these assumptions (or corresponding ones) for the outcome of the illustrative example, the main theory, and the empirical validation? How relevant does this make the theoretical analysis in real settings?
**Empirical illustration of the main theorems:**
It would strengthen the paper if the authors had included experiments that showed how the predicted quantities in Thm 4.1 and 4.2 behave empirically in real / toy settings. In particular, a graph that shows the $\Delta(\delta)$ terms in both theorems for different $\delta$ values both according to their theory and in terms of actual experiments. This would also make it more evident how restrictive the assumptions of the theorems are and how tight the inequality is. The size and evolution of the three summands in the last equation of Thm 4.2 would also be interesting.
**Minor:**
- I think that highlighting which feature is more separable in Fig 3b) is a bit problematic. First, UMAP plots are known to artificially tear apart structures. Second, the shape separability in 3b1) is also very good (but admittedly less obvious when looking at the plot as the color of the marker is much more prominent that its shape in the 2D plot). Therefore, I would recommend to rather stress the fact that when incorporating labels, the islands of the same shape but of different color seem to be much closer together (i.e. much less separable by color) than without labels.
- It would have helped my understanding of the paper if it was stated more explicitly that label information is made available by providing the label of existing but previously unlabelled points as opposed to adding new labelled points.
- I would suggest to also assign the bottom matrix in Fig 2b) as $\eta_l A^{(l)}$ as in the line above and then add another line $A=...$ below.
Questions
**Size of the data augmentation graph:**
The node set of the graph described in 3.1 is the set of all augmented views of all available data. Why is this even finite? Consider, for instance, image data. Are there not infinitely many ways to color jitter even a single image? Or is the idea to only consider a fixed and finite set of augmentations of each data point that is selected prior to training? This would be different than what is typically done in contrastive learning, where augmentations are applied on the fly. Even when considering a fixed set of augmentations, the size of the graph would have to be many times the size of the original dataset, right?
**Empirical Validation:**
- Were the same positive samples (including label information) used when comparing to SimCLR? From the discussion in appendix D, I think they were not. If that is the case and the SimCLR experiment is purely self-supervised, why is there such a large difference between the known, novel and all classes? Shouldn't all the completely un-/self-supervised methods be agnostic to which class has labels (which they cannot use anyway)?
- Using a ResNet-18 typically leads to about 90% linear probing and kNN accuracy on CIFAR10 for SimCLR. I appreciate that the evaluation is different and k-means is used to infer the clusters here. Nevertheless, I am surprised by the drastic drop in performance. Do the authors have an idea why this happens? Do the same SimCLR representations still achieve about 90% accuracy with linear probing / kNN classifier?
- I appreciate that the paper is about the open-world setting, where there might be novel classes without any labels, so that one can only do clustering and not classification for evaluation. Still the label information is available for CIFAR10 and CIFAR100 and I would have found it interesting to see how the proposed method fares under the SimCLR evaluation protocol with a linear probe / kNN classifier. This setting is standard in the self-supervised learning world and thus makes the quality of the proposed method more interpretable to an audience more familiar with self-supervised rather than open-world representation learning. I assume SORL should outperform SimCLR since it has some label information available at train time, right?
- Why is the performance for the "known" classes lower than that of the "novel" classes and why is the performance for "all" classes (typically) worse still than for the "novel" classes for the methods above the horizontal line in Table 1? For the open-world methods below the horizontal line, the performance is (typically) best on the "known" class, worse on the "novel" class and somewhere in between for "all" classes. This it what I would have intuitively expected.
- The method LSD-C [1] achieves over 80% clustering accuracy on CIFAR-10 without using any labels (and no supervised training of a shallow classifier). It might therefore be a relevant competitor.
**Minor:**
- The batch size of 512 is rather small for contrastive learning. Why is that?
- Are the different islands of points that share both color in shape in Fig 3b meaningful? Do they encode perhaps the size or position?
**References:**
[1] Rebuffi, Sylvestre-Alvise, et al. "Lsd-c: Linearly separable deep clusters." Proceedings of the IEEE/CVF international conference on computer vision. 2021.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Limitations
Limitations were not explicitly discussed. I suggest a more detailed discussion of how their theory and assumptions hold up on real world data, see weaknesses above.