A Graph-Theoretic Framework for Understanding Open-World Semi-Supervised Learning
Authors: Yiyou Sun
Zhenmei Shi
Yixuan Li
Venue: NeurIPS 2023 spotlight (2023)
Keywords: open-world learning
clustering
spectral analysis
TL;DR: N/A

Abstract: Open-world semi-supervised learning aims at inferring both known and novel classes in unlabeled data, by harnessing prior knowledge from a labeled set with known classes. Despite its importance, there is a lack of theoretical foundations for this problem. This paper bridges the gap by formalizing a graph-theoretic framework tailored for the open-world setting, where the clustering can be theoretically characterized by graph factorization. Our graph-theoretic framework illuminates practical algorithms and provides guarantees. In particular, based on our graph formulation, we apply the algorithm called Spectral Open-world Representation Learning (SORL), and show that minimizing our loss is equivalent to performing spectral decomposition on the graph. Such equivalence allows us to derive a provable error bound on the clustering performance for both known and novel classes, and analyze rigorously when labeled data helps. Empirically, SORL can match or outperform several strong baselines on common benchmark datasets, which is appealing for practical usage while enjoying theoretical guarantees.

A Graph-Theorets Framework for Understanding Open-World Semi-Supervised Learning
Yiyou Sun, Zhenmei Shi, Yixuan Li
Department of Computer Sciences University of Wisconsin, Madison {sunyiyou, zhmeishi, sharonli)@cs iisc.edu
Abstract
Open-world semi-supervised learning aims at inferring both known and novel classes in unlabeled data, by harnessing prior knowledge from a labeled set with known classes. Despite its importance, there is lack theoretical foundations for this problem. This paper bridges the gap by formalizing graph-theoretic frame- work tailored for the open-worke setting, where the clustering can theoretically characterized by graph factorization. Our graph-theoretic framework illuminates practical algorithms and provides guarantees. In particular, based on our graph formulation, we apply the algorithm called Spectral Open-world Representation Learning (SORL), and show that minimizing our loss is equivalent to performing spectral decomposition on the graph. Such equivalence allows able eтror bound on the clustering performance for both known and novel classes, and analyze rigorously when labeled data helps. Empirically, SORL match or outperform several strong baselines on common benchmark datasets, which is appealing for practical usage while enjoying theoretical guarantees. Our code is available at https:/ // thub. com/ com/deepl detpp waaninggnwssca/
derive a prov-
Introduction
Machine learning models in the open world in- evitably encounter data from both known and novel classes [2. 15, 16, 65, 79]. Traditional su- pervised machine learning models are trained on closed set of labels, and thus can strug- gle effectively cluster new semantic concepts. On the other hand, open-world semi- supervised learning approaches, such as those discussed in studies [7, 63, 69], enable models to distin- guish both known and novel classes, making them highly desirable for real-world scenarios. As shown in Figure the learner has access to labeled training dataset D; (from known classes) as well as large unlabeled dataset D., (from both known and novel classes). By opti- mizing feature representations jointly from both labeled and unlabeled data, the learner aims to create meaningful cluster structures that corre- spond to either known novel classes. With the explosive growth data generated in various
Labeled Data D
Unlabeled Data D,,
Figure 1: Open-worke Semi- Semi-supervised Learning aims correctly cluster samples in the novel class and classify samples in the known classes by uti- lizing knowledge from the labeled data. An open question is "what is the role of the label informa- tion in shaping representations for both known and novel classes?" ? This paper aims to provide for- mal understanding.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

domains, open-worle semi-superrised learning has emerged as a crucial problem in the field of machine learning.
Motivation. Different from self-supervised learning [5, 8, 11, 12, 23, 26, 68, 77], open-world semi-supervised learning allows harnessing the power of the labeled data for possible knowledge sharing and transfer to unlabeled data, and from known classes to novel classes, In this joint learning process, we argue that interesting intricacies can arise-the labeled data provided may be beneficial or unhelpful to the resulting clusters. We exemplify the nuances in Figure 1. In one scenario, when the model learns the labeled known classes (e.g., traffic light) by pushing red and green lights closer, such a relationship might transfer to help cluster green and red apples into coherent cluster. Alternatively, when the connection between the labeled data and the novel class (e.g., flower) weak, the benefits might be negligible. We argue perhaps obviously- that a formalized understanding of the intricate phenomenon is needed.
Theoretical significance. To date, theoretical understanding of open-world semi-supervised learning still in its infancy. In this paper, we aim to fill the critical blank by analyzing this important learning problem from a rigorous theoretical standpoint. Our exposition gravitates around the open question: what is the role of labeled data in shaping representations for both known and novel classes? To answer this question, we formalize a graph-theoretic framework tailored for the open-world setting, where the vertices are all the data points and connected sub-gree -obbggaass form classes (either known or novel). The edges are defined by combination of supervised and self-supervised signals, which reflects the availability of both labeled and unlabeled data, Importantly, this graph facilitates the understanding of open-world semi-supervised learning from spectral analysis perspective, where the clustering can be theoretically characterized by graph factorization. Based on the graph-theoretic formulation, we derive a formal error bound by contrasting the clustering performance for all classes, before and after adding the labeling information. Our Theorem 4.2 reveals the sufficient condition for the improved clustering performance for class. Under the K-means measurement, the unlabeled samples in one class can be better clustered, their overall connection to the labeled data is stronger than their self-clusterability..
Practical significance. Our graph-theoretic framework also illuminates practical algorithms with provided guarantees. In particular, based on our graph formulation, we present the algorithm called Spectral Open- Representation Learning (SORI. adapted from Sun et al. [64]. Minimizing this loss is equivalent to performing spectral decomposition on the graph (Section 3.2), which brings two key benefits: (1) it allows us to analyze the representation space and resulting clustering performance in closed- form; (2) practically, it enables end-to-end training in the context of deep networks. We show that our learning algorithm leads to strong empirical performance while enjoying theoretical guarantees. The learning objective can be effectively optimized using stochastic gradient descent on modern neural network architecture, making desirable for cal-world applications.
Problem Setup
We formally describe the data setup and learning goal of open-world semi-supervised learning [7]. Data setup. We consider the empirical training set D, U Di,, as union of labeled and unlabeled data.
1. The labeled set Dj {ž,, y: - with yı 3/. The label set 3) is known.
2. The unlabeled set D. { where each sample can come from either known or novel classes'. Note that we do not have access to the labels in Du. For mathematical convenience, we denote the underlying label set as Vanl where Y) C Van- We denote
C. = au the total number of classes.
The data setup has practical value for weal-world applications. For example, the labeled set is common in supervised learning; and the unlabeled set can be gathered for free from the model's 's operating environment the internet. We use P: and P to denote the marginal distributions of labeled data and all data in the input space, respectively. Further, we let Pt. denote the distribution of labeled samples with class label V/.
'This generalizes the problem of Novel Class Discovery 119,22,27, 27,2,, 82, 83J, which assumes the unlabeled set purely from novel classes.
2

---

Learning target. Under the setting, our goal is to learn distinguishable representations for both known and novel classes simultaneously. The representation quality will be measured using classic metrics, such as K-means clustering accuracy, which we will define mathematically in Section 4.2.2. Unlike classic semi-supervised learning [86], we place no assumption on the unlabeled data and allow its semantic space to cover both known and novel classes. The problem is also referred to as open-world representation learning [63], which emphasizes the role of good representation in distinguishing both known and novel classes.
Theoretical analysis goal. We aim to comprehend the role of label information in shaping represen- tations for both known and novel classes. It's important to note that our theoretical approach aims to understand the perturbation in the clustering performance by labeling existing, previously unlabeled data points within the dataset. By contrasting the clustering performance before and after labeling these instances, we uncover the underlying structure and relations that the labels may reveal, This analysis provides invaluable insights into how labeling information can be effectively leveraged to enhance the representations of both known and novel classes.
3 A Spectral Approach for Open-world Semi-Supervised Learning
In this section, we formalize and tackle the open-world semi-supervised learning problem from graph-theoretic view. Our fundamental idea is to formulate it as clustering problem-where similar data points are grouped into the same cluster, by way of possibly utilizing helpful information from the labeled data Dj. This clustering process can be modeled by a graph, where the vertices are all the data points and classes form connected sub-graphs, Specifically, utilizing our graph formulation, we present the algorithm- - Spectral Open-world Representation Learning (SORL) in Section 3.2. The process of minimizing the corresponding loss fundamentally analogous to executing a spectral decomposition on the graph.
3.1 A Graph-Theoreeh Formulation
We start by formally defining the augmentation graph and adjacency matrix. For clarity, we use I to indicate the natural sample (raw inputs without augmentation). Given an T, we use T(x(z) to denote the probability of being augmented from F. For instance, when represents an image, T(- can be the distribution of common augmentations [11] such as Gaussian blur, color distortion. and random cropping. The augmentation allows us to define general population space X, which contains all the original images along with their augmentations. In our case, X' is composed of augmented samples from both labeled and unlabeled data, with cardinality |.X'= = N. We further denote X1 as the set of samples (along with augmentations) from the labeled data part.
We define the graph G(X', w) with vertex X and edge weights w. To define edge weights w, we decompose the graph connectivity into two components: (1) self-supervised connectivity w(w) by treating all points in X' as entirely unlabeled, and (2) supervised connectivity wn(() by adding labeled information from Pi to the graph. We proceed to define these two cases separately.
First, by assuming all points as unlabeled, two samples (z, x+) are considered positive pair if:
Unlabeled Case (u): x and xx are augmented from the same image ī. ~ P.
For any two augmented data x, x X, (a) denotes the marginal probability of generating the pair:
(u) TT (x'(z).
(I)
which can be viewed as self-supervised connectivity [11, 23]. However, different from self-supervised learning, we have access to the labeled information for a subset of nodes, which allows adding additional connectivity to the graph. Accordingly, the positive pair can be defined as:
Labeled Case ()): x and x+ are augmented from two labeled samples Tn and 3 with the same known class i, In other words, both and E are drawn independently from Pt.-
Considering both case (u) and case ()), the overall edge weight for any pair of data (x, x') is given by:
Wan' = The (w) + mww (1) zz's where w mmm
ERIPY EEWP, T T( (x (z((z))
(2)
NE
3

---

and Tuu 7I modulates the importance between the two cases. The magnitude of Waar indicates the "positiveness" or similarity between and x². We then use w, Exex Wan' to denote the total edge weights connected to a vertex
Remark: A graph perturbation view. With the graph connectivity defined above, define the adjacency matrix A E gNxN with entries Agz' Wzz' Importantly, the adjacency matrix can be decomposed into two parts:
now
Perturbation by adding labels
A A A + m
which can be regarded as the self-supervised adjacency matrix A perturbed by additional labeling information encoded in A This graph perturbation view serves critical foundation for our theoretical analysis of the clustering performance in Section 4. As a standard technique in graph theory [14], we use the normalized adjacency matrix of G(X,,))
A D $ AD-
where E NXN is a diagonal matrix with DEM x = w. The normalization balances the degree of each node, reducing the influence of vertices with very large degrees. The normalized adjacency matrix defines the probability of x and x' being considered as the positive pair from the perspective of augmentation, which helps derive the learning loss show next.
3.2 SORL: Spectral Open- World Representation Learning
We present an algorithm called Spectral Open-world Representation Learning (SORL), which can be derived from a spectral decomposition of Á. The algorithm has both practical and theoretical values. First, it enables efficient end-to-end training in the context of modern neural networks. More importantly, it allows drawing a theoretical equivalence between learned representations and the top-k singular vectors of Á. Such equivalence facilitates theoretical understanding of the clustering structure encoded in Å. Specifically, we consider low-rank matrix approximation:
min FERN xk Lut (F, A) = A-FFT
(5)
According to the Fckart-Young- Yoo----uunggskk theorem [17], the minimizer of this loss function is F& E N such that F contains the top-k components of À'S SVD decomposition.
Now, if we view each row f of F as scaled version of learned feature embedding : + R the Lm (F A) can be written as a form of the contrastive learning objective. We formalize this connection in Theorem 3.1 below?.
Theorem 3.1. We define f-- / (x) for some function f. Recall quo nn are coefficients defined in Eg. (2). Then minimizing the loss function Cma(F. (F, A) is equivalent to minimizing the following loss function for f. which we term Spectral Open-world Representation Learning (SORL):
2nnxa((f) + oi Ca(s) + 2n (z) + (2, LSO -2) - -
(6)
where
Li(f)
Σ
E RI P o PP,
(2(
E
[f(x) (x+)),
P.PP x~T(1B.), T(-(a.)
ie
a~T (1112))) ~T(1)2))
La(f) = Σ
{x-))
beE
fa(f)= = Σ
{(())T((>))) (s(f)= .o(())
(x
P.PP [
i.PPy PP iE THE))) ((
=~T()) ~(())
'Theorem 3.1 is primarily adapted from Theorem 4.1 in [64]. However, there is distinction in the data setting, as Sun et al. [64] do not consider known class samples within the unlabeled dataset.

---

Proof. (sketch) We can expand (F) and obtain
(m)(F,A) Exx'xx (Alyeee
f.
const Ensexx (- (-2wart f waws (f(x) f
The form of LSORL(f) is derived from plugging Wax (defined in Eq. (1)) and wz. Full proof is in Appendix A.
Interpretation of LSORL(( (f). At high level. L1 and L2 push the embeddings of positive pairs to be closer while C3. L1 and Ls pull away the embeddings of negative pairs. In particular, L1 samples two random augmentation views of two images from labeled data with the same class label, and Le samples two views from the same image in A. For negative pairs, L3 uses two augmentation views from two samples in A with any class label. L4 uses two views of one sample in X4 and another one in X. Ls uses two views from two random samples in X. This training objective, though bearing similarities NSCL [64], operates within a distinct problem domain. Accordingly, we derive novel theoretical analysis uniquely tailored to our problem setting, which we present next.
4 Theoretical Analysis
So far we have presented a spectral approach for open-world semi-supervised learning based on graph factorization. Under this framework, now formally analyze: how does the labeling information shape the representations for known and novel classes?
4.1 An Illustrative Example
We consider toy example that helps illustrate the core idea of our theoretical findings. Specifically, the example aims to distinguish 3D objects with different shapes, as shown in Figure 2. These images are generated by a 3D rendering software [31] with user-defined properties including colors, shape, size, position, etc. We are interested in contrasting the representations (in the form of singular vectors), when the label information is either incorporated in training or not.
Data design. Suppose the training samples come from three types, X' .......'g Let Let X X T be the sample space with known class, and X .' be the sample space with novel classes. Further, the two novel classes are constructed to have different relationships with the known class. Specifically, X Xo shares some similarity with X x in color (red and blue); whereas another novel class X has no obvious similarity with the known class. Without any labeling information, it can difficult to distinguish X XO from X 'g since samples share common colors. We aim to verify the hypothesis that: adding labeling information X f (i.e., connecting and has larger (beneficial) impact cluster X than Xg.
X
-
+
Tm
2T.TA
Novel Clasa
2n
2T:T.
Au (1)
2n
77
2n
To
TO
2n
2T
2m
Known Class
0
0
2
2r
Eq.
(1,2,3)
(n)
(n
+ 7
Telm T2)
(e -omm++x0 72)
(n
refo
X
A 7,, (0)
7/m
O
r))
m
(a) Definition Augmentation Probability
(b) Adjacency Matrix
An illustrative example for theoretical analysis. We consider 6-node graph with one known class (cube) and two novel classes (sphere, cylinder). (a) The augmentation probabilities between nodes are defined by their color and shape in Eq. (7). (b) The adjacency matrix can then be
Figure 2:
calculated by Equations in Sec. 3. where we let Tu 0. 7u in Appendix B. The magnitude order follows
6. 77 = 4. The calculation details are
T
0.
5

---

Augmentation graph. Based on the data design, we formally define the augmentation graph, which encodes the probability of augmenting source image ž to the augmented view ar:
T1 if color(x) color (T), shape(#r) shape
Te if color(2) = color( 8), shape(r) F shape 7
( 8)
(7)
T. if color(2) color( shape(a) shape [
To if color(z) o (alor()) # shape(E)
With Eq. (7) and the definition of the adjacency matrix in Section 3.1, we can derive the analytic form of A(u) and A, as shown in Figure 2(b). We refer readers to Appendix B for the detailed derivation. The two matrices allow us to contrast the connectivity changes in the graph, before and after the labeling information is added. Insights. We are primarily interested in analyzing the difference of the representation space derived from A(") and A. We visualize the top-3 eigenvectors' of the normalized adjaceney matrix A(w) and Å in Figure 3(a), where the results are based on the magnitude order Ti > > T. > O. Our key takeaway is: adding labeling information to known class X & helps better distinguish the known class itself and the novel class OO' which has stronger commection/similariyy with X A
Qualitative analysis. Our theoretical insight can also be verified empirically, by learning represen- tations on over 10,000 samples using the loss defined in Section 3.2. Due to the space limitation, we include experimental details in Appendix 1. In Figure 3(b), we visualize the learned features through UMAP [43]. Indeed, we observe that samples become more concentrated around different shape classes after adding labeling information to the cube class.
(More separable color)
(More separable shapo)
Add labels "cubo"
1,2
0.5
0.2
07
0.4
0.8
-.6 404 -0.2
08
0.8
0.6
Annotation:
(a1) space Top-3 eigenvectors A(s))
(a2) Feature space with Top-3 eigenvecctrs
(b1) UMAP with
with empirical space A
empirical space Alu)
Figure 3: Visualization of representation space for toy example. (a) Theoretically contrasting the feature formed by top-3 eigenvectors of A(") and Á respectively. (b) UMAP visualization of the features learned without (left) and with labeled information (right). Details are Appendix B (eigenvector calculation) and Appendix E. (visualization setting).
4.2
Main Theory
The toy example offers an important insight that the added labeled information is more helpful for the class with a stronger connection to the known class. In this section, we formalize this insight by extending the toy example steps: (1) derive the closed-form solution of the learned representations; (2) define the clustering performance by the K-means measure; (3) contrast the resulting clustering performance before and after adding labels. We start by deriving the representations.
more general setting. As roadmap. we derive the result through three
4.2.1 Learned Representations in Analytic Form
Representation without labels. To obtain the representations, one can train the neural network X' + & using the spectral loss defined in Equation 6. We assume that the optimizer is capable to obtain the representation (1)) E R xk that minimizes the loss, where each row vector z, f(x:)_ Recall that Theorem 3.1 allows to derive a closed-form solution for the learned feature space by the spectral decomposition of the adjacency matrix, which is Á(w) in the case without labeling information. Specifically, we have F(")) = / D(w) z(n), where ((() F
p(K) contains the
When
0, the top-3 eigenvectors almost equivalent the feature embedding.

---

top-k components of A(")ss SVD decomposition and D(") is the diagonal matrix defined based on the row sum of A("), We further define the top-k singular vectors of A(a) v/() E [ so
have Fx ( V = where x is diagonal matrix of the top-k singular values of A("), By
equalizing the forms of F("", the flosed-formed solution of the learned feature space is given by z(1) = [_(")]] v (u) (-(")
Representation perturbation by adding labels. We now analyze how the representation is "per- turbed result of adding label information. We consider [ 1 to facilitate better under- standing of our key insight. We can rewrite A in Eq. 3 as:
A(d) _ A + Su1"
where we replace Ti å to be more apparent in representing the perturbation and define R.N. (92 = Es [xx(T)). Note that I can be interpreted as the vector of "the semantic connection for sample x to the labeled data". One can easily extend r classes by letting ( E RR
Here we treat the adjacency matrix as a function of the perturbation. In a similar manner as above, we can derive the normalized adjacency matrix A() and the feature representation Z(6) in closed form. The details included in Appendix C.4.
4.2.2 Evaluation Target
With the learned representations, we can evaluate their quality by the clustering performance. Our theoretical analysis of the clustering performance can well connect to empirical evaluation strategy in the literature [75] using -mmeans clustering accuracy/error. Formally, we define the ground-truth partition of clusters by II 1 T22 .... T where Ti is the set of samples' indices with underlying label Yi and C' is the total number of classes (including both known and novel). We further let
f Ei be the center of features in and the average of all feature vectors be An EJE[N1
The clustering performance of K-means depends on two measurements: Intra-class measure and Inter-class measure. Specifically, we let the intra-class measure be the average Euclidean distance from the samples' feature the corresponding cluster center and we measure the inter-class separation as the distances between cluster centers:
Mintraclase (II, Z)
z; m,ll" 21 .Mitter-laa class (II, Z)
|
Pn 11.
(8)
WEll Strong clustering results translate into low Maura-class and high Minterclass- Thus we define the K-means measure as:
nEll EE
M Mims (II, Z) Minroelasss (II, 2) Minterclass (II, Z).
We also formally show in Theorem 4.1 that the K-means clustering error is asymptotically equivalent the K-means measure we defined above.
Theorem 4.1. (Relationship between the K-means measure and K-means error.) We define the E the index of samples that from class division however is closer Pa than p. In other word, Ex-xx' = {i: i π. [|z [txlle 2 ||z - - [|2]- Assuming /r-- >> O, we define below the clustering error ratio from n' En-Yr! and the overall cluster error ratio E1,2 2 as the Harmonic Mean of En- among all class pairs:
-
Σ U8
where Entss!
Ex | +
Ex-sa'
TT.''EL
The K-means measure Mkms (II, Z) has the same order of the Harmonic Mean of the cluster error ratio between all cluster pairs with proof in Appendix C.3.
E = O.Mess (11, Z)).
"To understand perturbation by adding labels from more one class, one can take the summation of the perturbation by each class. It is theoretically inconvenient directly analyze the clustering since it is non-differentiaabe target.
7

---

The K-means measure M (II, 2) have a nice matrix form as shown in Appendix C.2 which facilitates theoretical analysis. Our analysis revolves around contrasting the resulting clustering performance before and after adding labels as we will shown next.
4.2.3 Perturbation in Clustering Performance
With the evaluation target defined above, our main analysis will revolve around analyzing "how the extra label information help reduces Mims (TT, Z)". Formally, we investigate the following error difference, as a result of added label information:
Kmms (6) Mams (T,, 2) -Mass (II, Z())),
where the closed-form solution is given by the following theorem. Positive Amms (6) means improved clustering, as a result of adding labeling information.
Theorem 4.2. (Main result.) Denote Vi(a) (NNx(N-)) as the null space of vi(u) and A( vl() s( y as the spectral gap between k-th and k + 1-th singular values of A(u), we have;
v/uuT as the rank-k approximation for A(w), Given 8,m >> O and let Gk
ALmo (6) = =n Tr (r Ve (I+ V - (idg(()g))))))))))))))))))))(d + 0 8²)
9k
where diag(:) converts the vector to the corresponding diagonal matrix and Y E IR-NN matrix encoding the ground-truth clustering structure in the way that Yaw' > 0 x and x' has the same label and T < 0 otherwise. The concrete form and the proof are in Appendix C.4.
Theorem 4.2 is more general but less intuitive to understand. To gain better insight, we introduce Theorem 4.3 which provides more direct implications. We provide the justification of the assumptions and the formal proof in Appendix C.5.
Theorem 4.3. (Intuitive result.) Assuming the spectral gap G& is sufficiently large and lies
in the linear span of V((), We also assume VT. E 11, Vi E Tei (()) =: lx_ which represents
the connection between class to the labeled data. Given 8, m1, 72 > O, we have:
Almm (0) 2 817772
Σ EFeel Ar. (8).
RCETT
where
Connection from class to the labeled data.
2(1 We ) EiEn, Ejer, 2,7 zj N Intra-class similarity
AT. (6)
(kr
N)
Eien Ejen. 2 23 )
Unter- similarity
Implications. In Theorem 4.3, we define the class-wise perturbation the K-means measure as An.(0) (6). This way, we can interpret the effect of adding labels for a specific class c. If we desire Ar. (5) to be large, the sufficient condition is that
connection of class to the labeled data > intra-class similarity inter-class similarity.
We use examples in Figure epitomize the core idea. Specifically, our unlabeled samples consist of three underlying classes: traffic lights (known), apples (novel), and flowers (novel). (a) For unlabeled traffic lights from known classes which are strongly connected to the labeled data, adding labels to traffic lights can largely improve the clustering performance; (b) For novel classes like apples, it may also help when they have a strong connection to the traffic light, and their intra-class similarity is not as strong (due to different colors); (c) However, labeled data may offer little improvement clustering the flower class, due to the minimal connection to the labeled data and that flowers' self- celf-clusterability is already strong.

---

Empirical Validation of Theory
Beyond theoretical insights, show empirically that SORL is effective standard benchmark image classification datasets SIFAR-10/100 [35]. Following the seminal work ORCA [7], classes are divided into 50% known and 50% novel classes. We then use 50% of samples from the known classes as the labeled dataset, and the rest as the unlabeled set. We follow the evaluation strategy in [7] and report the following metries: (1) classification accuracy on known classes, (2) clustering accuracy on the novel data, and (3) overall accuracy on all classes. More experiment details are in Appendix E.2.
Table I: Main Results. Mean and std are estimated on five different runs. Baseline numbers are from [7, 63].
CIFAR-10 Novel
C-FAR-100
Method
All
Known
Novel
Known
FixMatch [37]
49.5
50.4
71.5
20.3
23,5
39.6
DS [21]
40.2
45.3
77.6
24.0
23.7
55.1
CGDL [62]
39.7
44.6
72.3
23.6
22.5
49,3
DTC [22]
38.3
39.5
53.9
18.3
22.9
31.3
RankStats [82]
82,9
81.0
86.6
23.1
28.4
36.4
SimCLR [11]
51.7
63.4
58.3
22.3
21.2
28.6
ORCA [7]
88.32033
87,5
89.9
47.2
41,0#1.0
66.7-59
GCD [69]
87,520.5
86,740.
90,1
46.8
43.4400.7
69,7
OpenCon [63]
90.4
#0.00
91.1
89,3*02
52,7#0.
47,8
69. 69.1
SORL (Ours)
93.5 #1.0
92.5 #0.1
94.0
56.1 #0.3
52.0 #0.2
68.2
SORL achieves competitive performance. Our proposed loss SORL is amenable to the theoretical understanding, which our primary goal of this work. Beyond theory, we show that SORL is equally desirable in empirical performance. In particular, SORL displays competitive performance compared to existing methods, as evidenced Table Our comparison covers an extensive collection of very recent algorithms developed for this problem, including ORCA [7], GCD [69], and OpenCon [63]. We also compare methods in related problem domains: (1) Semi-Supervisee Learning [21, 37, 62]. (2) Novel Class Discovery [22, 82], (3) common representation learning method SimCLR [11]. In particular, on CIFAR- 100, we improve upon the best baseline OpenCon by 3.4% in terms overall accuracy. Our result further validates that putting analysis SORL is appealing for both theoretical and empirical reasons.
Broader Impact
From theoretical perspective, our graph-theoretic framework can facilitate and deepen the un- derstanding of other representation learning methods that commonly involve the notion of posi- tive/negative pairs. In Appendix D, we exemplify how our framework can be potentially generalized to other common contrastive loss functions [1 34, 68), and baseline methods that are tailored for the open-world semi-supervised learning problem (e.g.. GCD [69], OpenCon [63]). Hence, believe our theoretical framework has a broader utility and significance.
From a practical perspective, our work can directly impact and benefit many real-world applications, where unlabeled data are produced at an incredible rate today. Major companies exhibit a strong need for making their machine learning systems and services amendable for the open- world setting but lack fundamental and systematic knowledge. Hence, our research advances the understanding of open- world machine learning and helps the industry improve ML systems by discovering insights and structures from unlabeled data.
Related Work
Semi-supervised learning, Semi-supervised learning (SSL) is a classic problem in machine learning. SSL typically assumes the same class space between labeled and unlabeled data, and hence remains closed-world A rich line of empirical works [9, 13, 21, 29, 37, 38, 39, 42, 48, 50, 53, 54, 74, 76, 78] and theoretical efforts [3, 46, 47, 51, 60, 61, 73] have been made to address this problem. An important class of SSL methods is to represent data as graphs and predict labels by aggregating proximal nodes' labels [1, 18, 30, 71, 80, 84, 85). Different from classic SSL, we allow its semantic space to cover both known and novel classes. Accordingly, we contribute graph-theoretic framework tailored to the open-world world setting, and reveal new insights on how the labeled data can benefit the clustering performance both known and novel classes.

---

Open-world semi-supervised learning. The learning setting that considers both labeled and un- labeled data with mixture of known and novel classes is first proposed in [7] and inspires proliferation of follow-up works [49, 52, 63, 69, 81] advancing empirical success. Most works put emphasis on learning high-quality embeddings [49, 63, 69, 81]. In particular, Sun and Li [63] employ contrastive learning with both supervised and self- theoretical setup in Sec. 3.1. Different from prior works, our paper focuses on advancing theoretical understanding. To the best of our knowledge, we are the first to theoretically investigate the problem from a graph-theoretic perspective and provide a rigorous error bound.
signals, which aligns with our
Spectral graph theory. Spectral graph theory is classic research problem [10, 14, 33, 40, 44, 70], which aims to partition the graph by studying the eigenspace of the adjacency matrix. The spectral graph theory is also widely applied in machine learning [1. 6, 45, 56, 58, 64, 86]. Recently, HaoChen et al. [23] derive a spectral contrastive loss from the factorization of the graph's 's adjacency matrix which facilitates theoretical study in unsupervised domain adaptation [24, 57]. In these works, the graph's 's formulation is exclusively based on unlabeled data. Sun al. [64] later expanded this spectral contrastive loss approach to cater to learning environments that encompass both labeled data from known classes and unlabeled data from novel ones. In this paper, our adaptation of the loss function from [64] is tailored to address the open-world semi-supervised learning challenge, considering known class samples within unlabeled data.
Theory for self-supervised learning. A proliferation of works in self- sele-supe representation learning demonstrates the empirical success [5. 8, 11, 12. 23, 26, 68. 77] with the theoretical foun- dation by providing provable guarantees on the representations learned by contrastive learning for linear probing [4, 41, 55, 59, 66, 67]. From the graphic view, HaoChen et [23, 24], Shen et al. [57] model the pairwise relation by the augmentation probability and provided error analysis of the downstream tasks. The existing body of work has mostly focused on unsupervised learning. In this paper, we systematically investigate how the label information can change the representation manifold and affect the downstream clustering performance on both known and novel classes.
8 Conclusion
In this paper, we present graph-theoretic framework for open-world semi-supervised learning. The framework facilitates the understanding of how representations change as a result of adding labeling information the graph. Specifically, we learn representation through Spectral Open- Open-world Representation Learning (SORL). Minimizing this objective is equivalent to factorizing the graph's 's adjacency matrix, which allows us to analyze the clustering error difference between having vs. excluding labeled data. Our main results suggest that the clustering error can be significantly reduced the connectivity to the labeled data is stronger than their self-clusterabiilityy Our framework is also empirically appealing to use since it achieves competitive performance on par with existing baselines. Nevertheless, we acknowledge two limitations to practical application within our theoretical construct:
The augmentation graph serves as a potent theoretical tool for elucidating the success of modern representation learning methods. However, it is challenging to ensure that current augmentation strategies, such as cropping, color jittering, can transform two dissimilar images into identical ones.
The utilization of Theorems 4.1 and 4.2 necessitates an explicit knowledge of the adjacency matrix of the augmentation graph, requirement that can be intractable in practice.
In light of these limitations, we encourage further research to enhance the practicality of these theoretical findings. We also hope our framework and insights can inspire the broader representation learning community to understand the role of labeling prior.
Acknowledgement
Research is supported by the AFOSR Young Investigator Program under award number FA9550-23- 1-0184, National Science Foundation (NSF) Award No. IIS-2237037 15-2333666) Office of Naval Research under grant number N00014-23- 2-4414 and faculty research awards/gifts from Google and Meta. Any opinions, findings, conclusions, or recommendations expressed in this material are those of the authors and do not necessarily reflect the views, policies, or endorsements either expressed or implied, of the sponsors. The authors would also like to thank Tengyu Ma, Xuefeng Du, and Yifei Ming for their helpful suggestions and feedback.
10

---

References
[1] Andreas Argyriou, Mark Herbster, and Massimiliano Pontil. Combining graph laplacians for semi-supervissd learning. Advances in Neural Information Processing Systems, 18, 2005.
[2] Haoyue Bai, Gregory Canal, Xuefeng Du Jeongyeol Kwon, Robert D Nowak, and Yixuan Li. generalization
Feed two birds with one scone: Exploiting wild data for both and detection. In International Conference on Machine Learning, pages 1454-145 PMLR, 2023.
[3] Maria-Florina Balcan and Avrim Blum. A pac-style model for learning from labeled and unlabeled data. In Colt, pages 111-126. Springer, 2005,
[4] Randall Balestriero and Yann LeCun. Contrastive and non-contrastive self-super learn- ing recover global and local spectral embedding methods. Advances in Neural Information Processing Systems, 2022.
[5] Adrien Bardes, Jean Ponce, and Yann Lecun. Vicreg: ization for self-supervised learning. ICLR 2022- 10th-10th International Conference on Learning Representations, 2022.
regular-
[6] Avrim Blum. Learning form labeled and unlabeled data using graph mincuts. In Proc. 18th International Conference on Machine Learning. 2001, 2001.
[7] Kaidi Cao, Maria Brbic, and Jure Leskovec. Open-world semi-supervised learning. In Proceed- ings of the International Conference on Learning Representations, 2022.
[8] Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. Unsupervised learning of visual features by contrasting cluster assignments. Proceedings of Advances in Neural Information Processing Systems, 2020.
[9] Olivier Chapelle, Bernhard Schölkopf, and Alexander Zien, editors. Semi-Supervised Learning. The MIT Press, 2006.
[10] Jeff Cheeger. A lower bound for the smallest eigenvalue of the laplacian. In Problems in analysis, pages 195-200. Princeton University Press, 2015.
[11] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. simple framework for contrastive learning of visual representations. In Proceedings of the international conference on machine learning, pages 1597-1607. PMLR, 2020.
[12) Xinlei Chen and Kaiming He. Exploring simple siamese representation learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 15750-15758, 2021.
[13] Yanbei Chen, Xiatian Zhu, Wei Li, and Shaogang Gong, Semi-supervised learning under class distribution mismatch. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 3569-3578 2020.
[14] Fan RK Chung. Spectral graph theory, volume 92, American Mathematical Soc., 1997.
[15] Xuefeng Du, Gabriel Gozum, Yifei Ming, and Yixuan Li. Siren: Shaping representations for detecting ditto---iitribution objects. Advances in Neural Information Processing Systems, 35: 20434-20449, 2022.
[16] Xuefeng Du, Yiyou Sun, Xiaojin Zhu, and Yixuan Li. Dream the impossible: Outlier imagina- tion with diffusion models. Advances in Neural Information Processing Systems, 2023.
[17] Carl Eckart and Gale Young. The approximation of one matrix by another of lower rank. Psychometrika, 1(3):111-118 1936.
[18] Rob Fergus, Yair Weiss, and Antonio Torralba. Semi-supervised learning in gigantic image collections. Advances in neural information processing systems, 22, 2009.

---

[19] Enrico Fini, Enver Sangineto, Stéphane Lathuilière, Zhun Zhong, Moin Nabi, and Elisa Ricci. unified objective for novel class discovery. In Proceedings of the IEEE/CVF Interattonall Conference on Computer Vision, pages 9284-9292, 2021.
[20] Anne Greenbaum, Ren-cang Li, and Michael L Overton. First-order perturbation theory for eigenvalues and eigenvectors. SIAM review, 62(2):463-4822 2020.
[21] Lan-Zhe Guo, Zhen-Yo Yu Zhang, Yuan Jiang. Yu-Feng Li, and Zhi-Hua Zhou. Safe deep semi- supervised learning for unseen-class unlabeled data. In Proceedings of the international conference on machine learning, volume 119 of Proceedings of Machine Learning Research, pages 3897-3906. PMLR, 13-18 Jul 2020.
[22] Kai Han, Andrea Vedaldi, and Andrew Zisserman. Learning to discover novel visual categories via deep transfer clustering. In Proceedings of the IEEE/CVF International Conference on Computer Vision, 2019.
[23] 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-501 2021.
[24] Jeff Z. HaoChen, Colin Wei, Ananya Kumar, and Tengyu Ma. Beyond separability: Analyzing the linear transferabiliity of contrastive representations to related subpopulations. Advances in Neural Information Processing Systems, 2022.
[25] 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, pages 770-778, 2016.
[26] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 9729-9738, 2020.
[27] Yen-Chang Hsu, Zhaoyang Lv, and Zsolt Kira. Learning to cluster in order to transfer across domains and tasks. Proceedings of the International Conference on Learning Representations, 2018.
[28] Yen- Chang Hsu, Zhaoyang Lv, Joel Schlosser, Phillip Odom, and Zsolt Kira. Multi-class classification without multi-class labels. Proceedings of the International Conference on Learning Representations, 2019.
[29] Junkai Huang, Chaowei Fang, Weikai Chen, Zhenhua Chai, Xiaolin Wei, Pengxu Wei, Liang Lin, and Guanbin Li. Trash to treasure: Harvesting ood data with cross-modal matching for open-set semi-supervised learning. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 8310-8319, 2021.
[30] Tony Jebara, Jun Wang. and Shih-Fu Chang. Graph construction and b-matching for semi- supervised learning. In Proceedings of the 26th annual international conference on machine learning, pages 441-448, 2009.
[31] Justin Johnson, Bharath Hariharan, Laurens van der Maaten, Fei-Fei, C Lawrence Zitnick, and Ross Girshick. Clevr: A diagnostic dataset for compositional language and elementary visual reasoning. In CVPR, 2017.
[32] Antony Joseph and Bin Yu. Impact of regularization spectral clustering. The Annals of Statistics, 44(4):1765-179,, 2016.
[33] Ravi Kannan, Santosh Vempala, and Adrian Vetta. On clusterings: Good, bad and spectral. Journal of the ACM (JACM), 51(3):977555, 2004.
[34] Prannay Khosla, Piotr Teterwak, Chen Wang, Aaron Sarna, Yonglong Tian, Phillip Isola, Aaron Maschinot, Ce Liu, and Dilip Krishnan. Supervised contrastive learning. Advances Neural Information Processing Systems, 33: 13:16661-1867, 2020.
12

---

[35] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[36] Harold W Kuhn. The hungarian method for the assignment problem. Naval research logistics quarterly, 2(1-2):83-97, 1955.
[37] Alex Kurakin, Chun-Liang Li, Colin Raffel, David Berthelot, Ekin Dogus Cubuk, Han Zhang, Kihyuk Sohn, Nicholas Carlini, and Zizhao Zhang. Fixmatch: Simplifying semi-supervised learning with consistency and confidence. In Proceedings of Advances in Neural Information Processing Systems, 2020.
[38] Samuli Laine and Timo Aila. Temporal ensembling for semi-supervised learning. Proceedings of the International Conference on Learning Representations, 2017.
[39] Dong-Hyun Lee et al. Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks. In Workshop on challenges in representation learning, ICML, page 896, 2013.
[40] James R Lee, Shayan Oveis Gharan, and Luca Trevisan. Multiway spectral partitioning and higher-order cheeger inequalities. Journal of the ACM (JACM), 61(6):1-30, 2014.
[41] Jason D Lee, Qi Lei, Nikunj Saunshi, and Jiacheng Zhuo Predicting what you already know helps: Provable supervupe learning, Advances in Neural Information Processing Systems, 34:309-322 -20,-2332222 2021.
[42] Wei Liu, Junfeng He, and Shih-Fu Chang. Large graph construction for scalable semi- coni-supervised learning. In Proceedings of the 27th international conference on machine learning (ICML-10), pages 679-686. Citeseer, 2010.
[43] Leland McInnes, John Healy, Nathaniel Saul, and Lukas Grossberger. Umap: Uniform manifold approximation and projection. The Journal of Open Source Software, 3(29):861, 2018.
[44] Frank McSherry. Spectral partitioning of random graphs. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 529-537. IEEE, 2001.
[45] Andrew Ng, Michael Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. Advances in neural information processing systems, 14, 2001.
[46] Partha Niyogi. Manifold regularization and semi-supervised learning: Some theoretical analyses. Journal of Machine Learning Research, 14(5), 2013.
[47] Samet Oymak and Talha Cihad Gulcu. A thcoretical characterization of semi-supervised learning with self-training for gaussian mixture models. In International Conference on Artificial Intelligence and Statistics, pages 3601-3609. PMLR, 2021.
[48] Jongjin Park, Sukmin Yun, Jongheon Jeong, and Jinwoo Shin. Opencos: Contrastive semi- supervised learning for handling open-set unlabeled data. In Computer Vision-ECCY 2022 Workshops: Tel Aviv, Israel, October 23-27, 2022, Proceedings, Part II, pages 134-149. Springer, 2023.
[49] Nan Pu, Zhun Zhong, and Nicu Sebe. Dynamic conceptional contrastive learning for generalized category discovery. 2023.
[50] Sylvestre-Alvise Rebuffi, Sehastien Ehrhardt, Kai Han, Andrea Vedaldi, and Andrew Zisserman. Semi-supervised learning with scarce annotations. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, pages 762-763, 2020.
[51] Philippe Rigollet. Generalization error bounds in semi-supervised classification under the cluster assumption. Journal of Machine Learning Research, 8(7), 2007.
[52] Mamshad Nayeem Rizve, Navid Kardan, Salman Khan, Fahad Shahbaz Khan, and Mubarak Shah. Openldn: Learning to discover novel classes for open-world semi-supervised learning. Proceedings of the European Conference Computer Vision, 2022.
13

---

[53] Kumiaki Saito, Donghyun Kim, and Kate Saenko. Openmatch: Open-set consistency regulariza- tion for semi-superrvsed learning with outliers. Proceedings of Advances in Neural Information Processing Systems, 2021.
[54] Mehdi Sajjadi, Mehran Javanmardi, and Tolga Tasdizen. Regularization with stochastic trans- formations and perturbations for deep semi-supervised learning. Proceedings of Advances in Neural Information Processing Systems, 29, 2016.
[55] Nikunj Saunshi, Orestis Plevrakis, Sanjeev Arora, Mikhail Khodak, and Hrishikesh Khande- parkar. A theoretical analysis of contrastive unsupervised representation learning. In Interna- tional Conference on Machine Learning, pages 5628-5633 5637. PMLR, 2019.
[56] Uri Shaham, Kelly Stanton, Henry Li, Boaz Nadler, Ronen Basri, and Yuval Kluger. Spectralnet: Spectral clustering using deep neural networks. In 6th International Conference on Learning Representations, ICLR 2018, 2018.
[57] 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. In International Conference on Machine Learning, pages 19847-19878. PMLR, 2022.
[58] Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on pattern analysis and machine intelligence, 22(8):888- 9000 2000.
[59] Zhenmei Shi, Jiefeng Chen, Kunyang Li, Jayaram Raghuram, Xi Wu, Yingyu Liang, and Somesh Jha. The trade-off between universality and label efficiency of representations from contrastive learning. In The Eleventh International Conference on Learning Representations, 2023.
[60] Aarti Singh, Robert Nowak, and Jerry Zhu. Unlabeled data: Now it helps, now it doesn't t. Advances in neural information processing systems, 21, 2008.
[61] Nataliya Sokolovska, Olivier Cappé, and François Yvon. The asymptotics of semi-supervised learning in discriminative probabilistic models. In Proceedings of the 25th international conference on Machine learning, pages 984-991, 2008
[62] Xin Sun, Zhenning Yang, Chi Zhang, Keck- Voon Ling, and Guohao Peng. Conditional gaussian distribution learning for open set recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 13480- 13480-13489, 2020.
[63] Yiyou Sun and Yixuan Li. Opencon: Open-world contrastive learning. Transaction on Machine Learning Research, 2023.
[64] Yiyou Sun, Zhenmei Shi, Yingyu Liang, and Yixuan Li. When and how does known class help discover unknown ones? Provable understanding through spectral analysis. In Proceedings of the 40th International Conference on Machine Learning, Proceedings of Machine Learning Research, pages 33014-33043, PMLR, 2023.
[65] Leitian Tao, Xuefeng Du, Xiaojin Zhu, and Yixuan Li. Non-parametric outlier synthesis. International Conference on Learning Representations, 2023.
[66] Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu. Contrastive estimation reveals topic posterior information to linear models. J. Mach. Learn. Res., 22:281-1, 2021.
[67] Christopher Tosh, Akshay Krishnamurthy, and Daniel Hsu. Contrastive learning, multi-view redundancy, and linear models. In Algorithmic Learning Theory, pages 1179-1206. PMLR, 2021.
[68] Aaron Van den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv e-prints, pages arXiv-1807, 2018
[69] Sagar Vaze, Kai Han, Andrea Vedaldi, and Andrew Zisserman. Generalized category discovery. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, 2022.
14

---

[70] Ulrike Von Luxburg, A tutorial on spectral clustering, Statistics and computing, 17(():395-41) 416, 2007.
[71] Fei Wang and Changshui Zhang. Label propagation through linear neighborhoods. In Proceed- ings of the 23rd international conference Machine learning, pages 985-992, 2006.
[72] Tongzhou Wang and Phillip Isola. Understanding contrastive representation learning through alignment and uniformity on the hypersphere. In International Conference on Machine Learning, pages 9929-9939. PMLR, 2020.
[73] Larry Wasserman and John Lafferty. Statistical analysis of semi-supervised regression. Advances in Neural Information Processing Systems, 20, 2007.
[74] Fan Yang. Kai Wu, Shuyi Zhang, Guannan Jiang, Yong Liu, Feng Zheng, Wei Zhang, Chengjie Wang. and Long Zeng. Class-aware contrastive semi-supervised learning. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2022.
[75] Muli Yang. Yuehua Zhu, Jiaping Yu, Aming Wu, and Cheng Deng. Divide and conquer: Compositional experts for generalized novel class discovery. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 14268-142777 2022.
[76] Qing Yu, Daiki Ikami, Go Irie, and Kiyoharu Aizawa. Multi-task curriculum framework for open-set semi-supervise learning. In Proceedings of the European Conference on Computer Vision, pages 438 488-454. Springer, 2020.
[77] Jure Zbontar, Li Jing, Ishan Misra, Yann LeCun, and Stéphane Deny. Barlow twins: Self- supervised learning via redundancy reduction. In International Conference on Machine Learn- ing. pages 12310- 123200. PMLR, 2021.
[78] Xiaohua Zhai, Avital Oliver, Alexander Kolesnikov, and Lucas Beyer. S41: Self-supervised semi- supervised learning. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 1476-1485, 2019.
[79] Jingyang Zhang, Jingkang Yang, Pengyun Wang, Haoqi Wang, Yueqian Lin, Haoran Zhang, Yiyou Sun, Xuefeng Du, Kaiyang Zhou, Wayne Zhang, et al. Openood v1. 5: Enhanced benchmark for out-of diitt---dittitttionn detection. arXiv preprint 2xXiv22306.09301, 2023.
[80] Kai Zhang, James T Kwok, and Bahram Parvin. Prototype vector machine for large scale semi-supervised learning. In Proceedings of the 26th Annual International Conference on Machine Learning, pages 1233-1240, 2009.
[81] Sheng Zhang, Salman Khan, Zhiqiang Shen, Muzammal Naseer, Guangyi Chen, and Fahad Khan. Promptcal: Contrastive affinity learning via auxiliary prompts for generalized novel category discovery. 2022.
[82] Bingchen Zhao and Kai Han. Novel visual category discovery with dual ranking statisties and mutual knowledge distillation. Proceedings of Advances in Neural Information Processing Systems, 34, 2021.
[83] Zhun Zhong, Enrico Fini, Subhankar Roy, Zhiming Luo, Elisa Ricci, and Nicu Sebe. Neighbor- hood contrastive learning for novel class discovery. In Proceedings of the IEEE Conference on Computer Vision and Patlern Recognition, pages 10867-10875, 2021.
[84] Dengyong Zhou, Thomas Hofmann, and Bernhard Schölkopf. Semi- Semi-supervised learning on directed graphs. Advances in neural information processing systems, 17, 2004.
[85] Xiaojin Zhu. Learning from labeled and unlabeled data with label propagation. Tech. Report, 2002.
[86] Xiaojin Zhu, Zoubin Ghahramani, and John D Lafferty. Semi- supi-supe learning using gaussian fields and harmonic functions. In Proceedings of the 20th International conference on Machine learning (ICML-03), pages 912-919, 2003.
15

---

Appendix
A Technical Details of Spectral Open-world Representation Learning
Theorem A.1. (Recap of Theorem 3.1) We define fz = [x) for some function f. Recall Tus Th are two paraaerrrssssesss defined Eq. (1). Then minimizing the loss function Lut F, A) is equivalent to minimizing the following loss function for f, which we term Spectral Open-world Representation Learning (SORL):
LSORL( (f) -2) - 2nIx(((1)
(10)
Lz(((()) + 2110% (i
where
-(()= -- Σ
[f(x)T(<+t))
iEDi Pr
x~T( (8t) (T(1))
C2(f)
f
By aP xTT(1122) (T(1BB.)
Ca(s) Σ
E 21 P
(
WeE wTT( Rc); (T(E))
E C(() Σ P
f
iEDI
anT (-)1i-1 T((1Ba)
Cs(J)
E
(=)))
Ba PP >~T(133), T(13
Proof. We can expand (mr(F, A) and obtain
(F =
Σ
Way
f Ezy'
2 Ex
(-2 ff w.w (
=const
where f, (z) is a re-scaled version of fzx At high level, we follow the proof in [23]. while the specific form of loss varies with the different definitions of positive/negative pairs. The form of LSORL (f) derived from plugging Wazr and Wy..
Recall that Wan' is defined by
W Waz'
EaiPP EEE~P, (( (I'1²) +
NE
and w. given by
W² = Σ Waw
Σ
Ex Eujn,, T(x(ai) Σ ( E. ΣT (a' (e((
m
iE)
= 7 Σ
E, T T(x(it) + nuEE, x ~ (x((t.)
iEDi
Plugging in Way we have.
16

---

2 Σ
Wer wer f(z) [(x)){(()))
2,''EX
--2
Σ
Wxx+ [a) 1 (x+)
2,ttEX
2m
Σ
EEAPI Ba(xPi
Σ T(s))))((())) f(x) f (x)
iEVI
-21/ Baup 2,
Σ
TT (z'(au)
2m
E PI PE xm T' (((E))
[f(x)
E)Di
2//u
(())(((xt)))
P. 2~T((a (- T((EE.)
2m) 2n,
Plugging wp and war we have,
Σ Wy [ (x/))²
= Σ
Wz (f(x) of (z7))²
Z EX
Σ
M Σ E EEINP. T(x|,)) + m E T
Z Z EX
icDi
Σ
Ex BEINPI T(x + Mu TT (x-))
JEG/
= Σ >
E ERIPP Pt, T(rl71)
Σ
E Egjno, T(x (1)) ( (1-))
5. EX
21/2111 11
Σ
T T B (17
E
F. ENI
+ nhe Σ
Ex
T (x (T. (()))
2, EX
Σ
E P
(x)))
NNT (- - T((E))
Σ
(U(x)T((²))
21/T
iEDi
[ f (x ))
+ +1
E P.P'' ~P, .~T((12..);= T((=E))
CT) + 2m. (f) + n2
17

---

B Technical Details for Toy Example
B.1 Calculation Details for Figure 2.
first recap the toy example, which illustrates the core idea of our theoretical findings. Specifically, the example aims to distinguish 3D objects with different shapes, shown in Figure 2. These images are generated by 3D rendering software [31] with user-defined properties including colors, shape, size. position, etc.
Data design. Suppose the training samples come from three types, Xa. .x Xo Let X be the sample space with known class, and X X be the sample space with novel classes. Further, the two novel classes are constructed to have different relationships with the known class. Specifically, construct the toy dataset with 6 elements shown in Figure 4(a).
Augmentation graph. Based on the data design, we formally define the augmentation graph, which encodes the probability of augmenting source image æ to the augmented view
T1 if color(z) color (z). shape(x) shape (z)
Te if color(2) color ( shape(r) * shape (
(11)
Tx if color(2)) + color ()), shape(x) shape [T);
if color(z) o color(ā), shape((r) * shape (.:).
According the definition above, the corresponding augmentation matrix T with each element formed by T( is given in Figure 4(b). We proceed by showing the details to derive A(a) and A using
X
Class
To
Ti
T
To
X K
Tx
T
Known Class
To
TI
Tx
T
0
Te
X
Ts
Novel Class
U
(a) Definition of Augmentation Probability
(b) Augmentation Graph
Figure 4: An illustrative example for theoretical analysis. We consider 6-node graph with one known class (cube) and two novel classes (sphere, cylinder). (a) The augmentation probabilities between nodes are defined by their color and shape in Eq. (11). (b) The augmentation matrices T derived by Eq. (11) where we let To O.
Derivation details for (w) and A. Recall that each element of ( is formed by w " (e>pT((x()) (x'(z) In this toy example, one then see that A(a) !TTT since augmentation matrix T is defined that each element T.и = T (ax (). Note that explicitly given in Figure 4(b)
and then if we let 77 6, we have the dlose-from:.
T + r2
2
2T Te
2T
0
0
2TITs
T
+ T
To
2T
2T
0
0
(1) 2
2T
2T
T + T + T
2T
0
0
27
27 Te
27
+
+ T
To
0
0
0
0
0
2r2
27
0
2T
2T
18

---

We then derive the second part A whose element is given by:
BE, T( (z/(z)).
TE
Such form can be simplified in Section 4 by defining E RN, (02 Pa,,, Txx and by letting [Di] 1. In this toy example, the known class only has two elements, so I 1 (T,,1 2) (average of I 1st & 2nd column), we then have:
(T + T (Ti + T3)
(Ti + T.)²
( + Ta)
To (Ti + Ta)
0
(n T
(T Te)
To (TI
Ts)
0
A = 11T
Te (TI Ta)
To Te
0
Te (1
Te (T
0
0
0 0
0
0
Finally, if we let = 4 and A = Th 7/.4 (()) + in A(0 we have the full results Figure 2.
B.2 Calculation Details for Figure 3.
In this section, we present the analysis of eigenvectors and their orders for toy examples shown in Figure 2. In Theorem B.1 we present the spectral analysis for the adjacency matrix with additional label information while in Theorem B.2, we show the spectral analysis for the unlabeled case.
Theorem B.1. Let
7p + T3
=o
2T Ts + T + Te
2T Te
2T
0
0
2T
2T T
2T
0
0
(1)
2TITc
2T
-
To
2TIT
0
0
2T
2n Tr
2n
- +
T
+
Te
0
0
0
0
2r
2T
0
0
0
0
2T
27
(n ),
(n + )
TelTi + Tx)
Te(Ti + Tx)
(n tT)
(n + Tx)
Te(TI Ta)
Te(TI Tp)
0
A ya (1)
TelTI + Tx)
TelTI + Ta)
0
Tal Tx) 0
TelTi + Tx) 0
To
0
0
0
and we assume that
44 0,
To To To and Ti To + 1.
Let >i, 22, A3 and 01, V2, be the largest three eigenvalues and their corresponding eigenvectors of D + +AD ł, which is the normalized adjacency matrix of A. Then the concrete form of '1 X2 A3 and U1, U2, v3 can be approximately given by:
16 Te
Å = 1, d =1 \タ 3=
3
G 10,0,0,0,1,1],
82 = [V3, v3, 1,
03 [1,1, 1V.
Note that the approximation gap can be tightly bounded. Specifically, for {1,2,3), we have SainU,ÜÜY Ú < 0 E=)) where U = [1i, U2, va), [01, 02, 0g].
A \ < (((=)))) and (Un
'The sin operation measures the distance of two matrices with orthonormal columns, which is usually used in the subspace distance. See more in https: http///tttgttttttttetee htt.th/b..//ttte////////aaaaasss
19

---

Proof. By +e = and 1
>
0, we define the following equation which
approximates the corresponding terms up to error ( )):
2 - -
1+ 4
3
0
1 - -
2 2+ 2
3
0
0
A R Ā=
3 3
Is
2
3
2
1
0
0
0
0
0
0
0
2
De D = didiag [3(1+22
4he
,3
1 2 Te
+
4he
1 2
Te
+
4
To
1
2
Ta
+ 4
Te
4, 1))
3
3
D 23 D diag (33 (13
1-
To Tc
v3
Ts
2
1
Tg
2
Te
T8
2 Te
2,2
3
T1
T1
D- D-EAD= D- žĀDー
11
$
1 71
1m
1/3 T
0
11
(1 1 Io
v
0
0
v3
2
- 4
2
0
0
1/
2 2/
1
2
0
V3
0
1
0
0
0
2
And we have
D AD- D -
D D 2 D- BAD
<0(( (2))) TI
Let A Ry be six eigenvalues of D 2-AA 1, and ......, dy be corresponding eigenvectors. By direct calculation have
16 Te
A 1, 2o =1, A
2o
3 TI
and corresponding eigenvectors as
6, [0,0,0.0,1,1],
è [V3, 13,
6, = 1311,-33.-33,00
t. 10,0,0,0,1,-11]
For the remaining two eigenvectors, by the symmetrie property, they have the formula
i Ja(" Ts
To
a Ts
Te
To Te -5 To Te
3
0,0.0)
TI π T
T
0, [3(
[]]
3( To Te
a
Ts [6]
a Te 7
),0,0,
7 TI
n
1
11
20

---

where 3 are some real functions. Then, by solving
D= t0, - daoo
D AD l8g E5ez.
we get
de
1/1
1
(3
12
Ts
16 2 )2+ + 108(
Tc
24
20
Te
+
6
9
11
11
T1
T1
1
12 To
16 _ )2 + 108
24
Ts
20
Te
+
9
7
71
11
11
Now, we show that 2,
Ae. By
< 1
and
Te
S TB T
7
2
+
3 +
24 1
- 28
Te
2
3 - 12 TH
- 16 - y + 108
Te
)2
T1
T1
T1
+
36
2 + 35
Ts
2 2 - 144
To Te
+ +18
Ts
Te
2 0.
T1
T1 T1
T1
7
Thus, we have = Am- A Ae
> de=
0. Moreover, also have
de de =1 16
(
(3
12
To
16 Te 22 108( (922 24 To
20 To
6
T1
1
71
7
51
T1
Te
20
T1
Let 21 = -o, = 2o As- = de. Then, by Weyl's Theorem, for i E {1,2,3), we have
- 211 $
D -
< <0(( 2 )).
71
By Davis- Kahan theorem, we have
(2
(i)n( S
0
Ω Is
We finish the proof.
Theorem B.2. Recall A()) is defined in Theorem B.I. Assume 1 >>>>>
> and +Te
11
1. Let X(u), X(u), X(u) and v(a) 122 1/3
(u) (u) be the largest three eigenvalues and their corresponding
eigenvectors of D(w) & (yn A (w)) ( which is the normalized adjucency matrix of 1 A()), Let
\ ((a)_ 1, i((0) =1, 2 11 7
(()) = 10.00..0.1,1]
(N) 1,0, 0).
8
(a) 11,11,,,,,,000
Let (w)) [u] (0)
(1) (()) (o[() " [(()]
Then, for i E (1,2,3), we have (2
1(01 < (((2))) and (in( ( - 0 (
Proof. Similar the proof of Theorem B.I, up error (((5s)), we have the following equation,
2 Ez
2
0
0
71
2 In
_
0
0
Fi
n
2 2
2
0
0
Aw) 7
71
0
2 71
1
0
0
0
0
0
2
2
2
2
21

---

D(a)= ridiag
([
(1122
-
+2
1
+2
1
1
2
+
Te
1
2 Ta
2 T1
4,4
T1
T1
T1
T1
71
11
T1
D(u)
1
diag ([1
Ta
Te
T8
Te
T8
Te
T8
Te
2,2
11
2 I 2
2
0
0
0
2 TI
2
0
2
0
0
Ti
_
0
1
2
2
2
0
0
D(w) $ (nAAu))(w)-)
11
0
2
2
2
0
0
0
0
0
7
0
0
0
Let 1 , (( be six cigenvalue D(w) $
1/u, (w)) and 0(4)
(())
,...,
((M)
be corresponding
eigenvectors. By direct caleulation we have
{ = 1, ( 1, = 4 To
(w) =
Te 5
(1)
=
4 To
4
6
(w)
=
0
T1
and corresponding eigenvector as
(u) [0,0,0,0,1,1]]
62 = [1, 11,1,,,100,0
03 = [1, [1,-1,1,,1,0,0,
(a)
(a) 11,0,1,,-1,00)
0
(a) [1. 1, -1,,-,000
66
06 = (0.0,0.0.1.-1]
Then, by Weyl's Theorem, for E (1, have
1A - X(0 1 ( 1)(w) A()
s <0((_03) 7
By Davis-Kahann theorem, we have
(((
(U)( (00))
$ 00
4( To)
7 Tx)
We finish the proof.
22

---

C Technical Details for Main Theory
C.1
Notation
We let 1n. O,, the n--dimensional vector with all or values respectively. 1xxss 0mxn are similarly defined for m-by-n matrix. Ln is the identity matrix with shape For any matrix V. V(sjj indictes the value at i-th row and j-th column V. the matrix is subscripted like Vk. we comma in-between like (i. Similarly, V(i) and Va.(0) are the i-th value for vector and respectively, [ni is used to abbreviate the set n1...
C.2 Matrix Form of K-means and the Derivative
Recall that we defined the K-means clustering measure of features in Sec. 4:
M (11, 2)
ΣΣ Iz
M
Σ
Fn
(12)
where the numerator measures the intra-class distance: Mintra (II, 2)
Σ
Σ
2; 1al1?
(13)
*El iE
and the denominator measures the inter-class distance:
Minter (II, Z)
Σ
|
1|, P'll
(14)
We will show next how to convert the intra-class and the inter-class measure into matrix form, which is desirable for analysis.
Intra-class measure.
Note that the K K-means intra-class measure can be rewritten in a matrix form:
Mintra (II, 2) = 2- - HH
where Hn is matrix convert mean vectors w.r.t clusters defined by Without losing the generality, we assume Z is ordered according to the partition in II first [T] vectors are in T1, next |2l vectors are in T2, etc. Then Hn is given by:
|
0
0
1
0
Hn
R2
0
0
[m 1 |
Going further, we have:
Mintra = 1| - 1n 11
Tr((1 H21)222'
-Tr(II 22/11 H1))Zz]
TTr(II -H))ZZ
Inter-class measure. The inter-class measure can be equivalently given by:
Minter (TI, 2) = 2n
N INx
where in defined as above. And we can also derive:
1
Minter (II, 2) Hn
INXN 7 1
N
=Tr((H 1
N 1NxN)
-Tr((HF N
HuINNN + N2 (x7)
1
=Tr((H
1 1NxN)ZZT).
N
23

---

C.3 K-means Measure Has the Same Order as K-means Error
Theorem C.1. (Recap of Theorem 4.1) We define the Ex- as the index of samples that is from class division x however is closer to p than pr. In other word, Ex-xx' = {i: i k. T. M l12 2 || - ue [2 Assuming (n-axl O, we define below the clustering error ratio from I' as Ex and the overall cluster error ratio En as the Harmonic Mean of E among all class pairs:
Sm-
=
Σ
where En
Ex-
+
The K-means measure Mams (11, Z) has the same order as the Harmonic Mean of the cluster error ratio between all cluster pairs:
E1,2 = 0 (II, Z)).
Proof. We have the following inequality for E En-+x'
4||2:
M
112 2 2||z:
u 11 2|
Mo 112
|4 Ms 12.
Then we have:
Mintra (II,
ΣV Σ |z M 112
||z 10
iET
||z 11 11
SEC, >a'
l| -1 iEE.-nn
4 S-
||
p 11.
Note that the inter-class measure can be decomposed into the summation of cluster center distances:
Minter (II, 2)
Σ
| ||
Mnl12
Σ
|
N2
M
TE
c'lll
x'lll
|
112
N2
HEll
''lll
C
|=] ||
M 11
N2
where EnjLr
enumerating over any two different class partitions TI. Combining together, we
have:
(| (| [T])
(| | ) || p 11
C(C 1)/
Σ 7F
-CC--1)
Kx-x< |4 u. 113
| [|T[(|]]| + (TT) 1111114 M4,
< <CCC 1)/
N2 11 M
Minter (TI,
CC(C - 11/
4C (II, Z)
O(Mama (II, 2)).
24

---

C.4 Proof of Theorem 4.2
We start by providing more details to supplement Sec. 4.2.1.
Matrix perturbation by adding labels. Recall that we define in Eq. 3 that the adjacency matrix is the unlabeled one A(") plus the perturbation of the label information A
A (*) + 7.
We study the perturbation from two aspects: (1) The direction of the perturbation which given by
A (2) The perturbation magnitude 7)-- We first consider the perturbation direction A and recall
that we defined the concrete form in Eq. 2:
w
(1) Z.
Σ iED;
Ea,-Pi,Br BRi T( (x'
For simplicity, we consider [ = 1 in this theoretical analysis. Then we observe that A is rank-1 matrix can be written as
4 II!
where E R Nxl with (02 = Ea Tx) And we define D, - diag(!).
The perturbation function representation. We then consider a more generalized form for the adjacency matrix:
A(d) A( + Sut
where we the adjacency matrix as a function of the "labeling perturbation" degree 6. is clear that A(0) A()) which is the scaled adjacency matrix for the unlabeled case and that A(m) A. function of 5, the normalized form and the derived feature
When we let the adjacency matrix representation should also be the function of 6. We proceed by defining these terms.
Without losing the generality, we diag A(0) IN which means the node the unlabeled graph has equal degree. We then have:
D(6) & (1 IN 8D:
The normalized adjacency matrix is given by:
A(8) & D(6) (())
For feature representation Z(6), is derived from the top-k SVD components of A(6). Specifically, have:
k
7(8)2(5) = - = Σ (60)),(0)
where we define Ao) as the top-k SVD components of Á(o) and can be further written as Aa( Σj= (6) Here the (6) is the j-th singular value and (ā) is the j-th singular projector (6) = 0y (,)),, defined by the j-th singular vector (6))). For brevity, when O, we remove the suffix (0) since it is equivalent to the unperturbed version of notations. For example, let
A(0) A Z(0) (()) Ax((0) x(")) (0) u. (v) (.) (!")
Theorem C.2. (Recap of Th. 4.2) Denote v(()) Nx(NN) as the null space of v( and A
v (u) v=(") ( the rank-k approximation for A(w) Given 6, > 0 and let Gy the spectral
gap between k-th and is + 1-th singular values of Alu), we have:
ARma(o) om Tr (r (V T UT + (1) ( 2 diag())) + + +8),
-
Gk.
where diag(-) converts the vector to the corresponding diagonal matrix and T E N is matrix encoding the ground-truth clustering structure in the way that T Taz: > if and x' has the same label and Yeg < O otherwise.
25

---

Proof. As we shown in Sec C.2, we can now also write the K-means measure as the function of perturbation:
Th((I - Hn) (()
Mime (0) Tr((Hn x=Nxx)](())2(1))
The proof is directly given by the following Lemma C.3.
Lemma C.3. Let Ti t2 be two real values and T (1+ 12) - 1 1N Let the spectrum
x we have the derivative of the K-means measure evaluated at 5 = 0:
gap G%
[Mamo (6)]
= - Tr rr (v
V (T) IT - -2 D. v (M) 1t v +
6=0
9k
The proof for Lemma C.3 lengthy. We postpone it to Sec. C.6.
C.5 Proof of Theorem 4.3
We start by showing the justification of the assumptions made in Theorem 4.3.
Assumption C.4. We assume the spectral gap 9s large. Such an assumption is commonly used in theory works using spectral analysis [32, 57].
Assumption C.S. We assume lies in the linear span of V/(w) ie., (= I= 0.
The goal of this assumption is to simplify (V (())
IIT (1() ((u) II ( to
* k
Assumption C.6. For any Te E II, Vi,j E Te: (() (0)) =: l. Recall that the (()) means the connection between the i-th sample to the labeled data. Here we can view L. as the connection between class с to the labeled data.
Theorem C.7. (Recap of Theorem 4.3.) With Assumption C.4, C.5 and C.6. Given 6, m. 122 0, we have:
Aomo (0) 2 87172 Σ ITe |T, Ar. (8),
where
Tel
(+) (Ir N) 2(1
(EI 2, ZTzz -Eier Bjgs, 2i 2z).
N
Proof.
The proof is directly given by Lemma C.8 and plugging the definition of Akms
Lemma C.8. With Assumption C.4 C.5 and C.6, we have the derivative of K-means measure with the upper bound:
[Mkms (8)]'
5
77 Σ
|x|L (l+ 11) N
-2 ux u4 mn))
8=0
mETl
Proof. By Assumption C.4 C.5 and C.6 and Theorem 4.2, we have
[Mama
(0))
= - Tr r ( (u) (())) ITT 2.7( Di)
m 1=0
Tr (r (IT - 2A( -
= =-Th ((11+ - - 772
IN1N) (II -2 D:))
N
= (1 + 122 + +M² + MMh
26

---

where
M/ -Tr
Tr (Hm Hm (1T-222) D1)
Σ #Ell
[ -
2 ΣΣ |
SE jEa
Σ (|=|( (1.)) z3))
TEll
Σ
|r]br (Ix - -2 Mz))
tell
M₁ = Ir (nT 2A Di)
Σ | (Lr 2B 23 zi);
mEll
and
Mi Tr INII (IT -2A Di)
N Σ U0 2j
nEll iE
Σ sell
| MTI-
N
We observe that
M, + M'H = Σ
|T|L (1= 24 T M,)+ + Σ |T|[=(1 22 2,)
.Ell
xETl
= 2 Σ
(I -Bi BiE=|/z,113 (z,
.E
< 0,
where the last inequality is by Jensen's Inequality. We then have
1
[Mkme (8))
S MM +Mi
77772
6=0
Σ
|T|L (Lr 24 14 N 2 Σ
|T|L Mn
*ell
*ell
|. | (Lr - -2( MT p H1))
N
mEll
Σ xell
| Lz ((k= ) 22 Mx M Mn)).
C.6 Proof of Lemma C.3
Notation Recap: We define (8) as the top-k SVD components of A()) and can be further written as (6) = E )y (5) Here the (5) is the j-th singular value and (5) is the j-th singular projector (Ø) = (8)) defined by the j-th singular vector uy (6). For brevity, when 5 = 0, we remove the suffix (0) since equivalent to the unperturbed version of notations. For example, we let
Á(()) A())2(() Z(1), (x(0) (( (0) U. (w) (. 4(4)
27

---

Proof. By the derivative rule, we have,
1 M Mintra Mintra (II, Z) Minter (IT, 2)
Mamo (6)
Minter 2)2 Minter (6)
My
Minra (6) 1/1 12222/2 (6)
7 (Tr((In (n)) 1/2 Tr((Hn - [1xx)>((00(()]]
N
!) (Tr((In + Th INXN- - (m2 + +))m)((()2(00TT
N
Th (T(TT22())()))))
k
- Σ T0TD0000+100000000000000000
1=1
where we let 1J1 (1..] 722
Mintra (11.2)
Minter (1.2) and Y (1 + 122 In WIvI We
proceed by showing the calculation of [D(6) $1', (0)( and [0)(
Since (66) 1 + 8D, then [D(
- Dr. To calculate (6)) and (o)(" we first 4=0
need:
[A())])
[D(6) ((0))))())000)--> b1
6=0
[D [A(6)) (D())
1 - + aT 1
- 2 Dr.
Then, according to Equation (3) in [20]. we have:
[,)())]
= (T(0)"(A(0))
6=0
= =Tr(o/") D/A(") -11T -1AT==1TT - - Di))
2
X
1(4)
= -Tr((- D(
(1) + +00111T
a (1) D:))
2
= =Tr(o)
(w) (a" - 11mh Di)).
According to Equation (10) in [20], we have:
[0)(
IN
( + +0/" 1A0)(/)) A(w)
6=0
N
1
(2) [" + /
(A(0'''')
=
((1) - X
$
N
Σ
1
(n) (T) (- D,A(w) + +11 ((w) (1)
+ (1)
(..)or))))))
2
N
1 + (()
1 + (a)
(
1
(1) (nT
2 D1) (w) + +00 10(((((
(w))
(u)
2
Now calculate the derivative of the K K-means loss:
28

---

1 (Mm
= - 1))
7
6=0
6=0
==1
Σ ==1
Tr
(r (DD "/ + +1,00 100) + (0)0)))))))
(w)
1
Tr T
D
(0)
+ 2 , Di --000000000 - -100,,00))))0)00)
0 (0)
2
5=1
= My + M¹ + +Ma.
where
M¹ = Σ )
k
(a)
Tr (r (Drof(") +
2
j=1
k M¹- - Σ
Tr (T)A)())'0 =- -
Tr (ITT - -100 )))oo")))) TA (ro(
j=1
1=1
k
Σ
Tr (aTT - -x0x (o)
j=1
k
M²= = - Σ
Tr (TA! (2) (12;1)))))))
j=1
1/41
1(t) + x()
1/10 +1 ((u
Tr
Σ
(To(")
(1T
2 -D))aauu)) + TT (11
Di)ao(u))
(a)
[a]
2
ΣN2
100) + x(x0 (i)
Σ
(8))) + "o"""a
T
(a)
(0)
x(w) + + Di)
Σ
Σ
ro (w) + 40 rg0
TF
10 - [w)
2
itj.isk
N
(())
1(t) + +1/tm Di)
Σ
Tr
(0) (o (0) + "o)")"
[u]
(w)
2
1 (n)
1 - ) ) (o + (o)))
1/m0 (()
+ X (1)
Di)
Σ
1/00
[n]
2
N
2 + ((m)
Σ
(o + o("
Di)
[u]
[a]
2
1=
29

---

(0) ro ()) ((1 1100 + 1(
Di)
2
N
1 (a) + ((a)
Σ
(0/0)Ta(") + (00
Di)
11
2
1=++1
2/11
+ ((()
Σ
TT
Σ
(a + "a
Di)
2
2
i
N
x(m)
1/a1 + 1
>Σ
TT
( + "00
Di)
((m)
- x(w)
2
k=++1
Thus, we have:
k
2/50 + 1,
My + +M²
Σ
Tr
Σ 2
1
(of") ( + "om"))""
Di)
2
j=1
N
(()
1/ +
(0)
Di) ))
Σ
Tr
+ (o
(u)
2
j=1
1i++11
)
(w)
M¹
Σ
j
Tr r (D) + + Di)
2
j=1
k
(w)
Σ
Tr (0) ( + + Tao Di)
=
2
3=1
= Σ
*
(M)
Tr
( r
Σ
N
(1)
Σ ( DI
N
2
2-1
1=1
N
(a)
Tr
j
$ )
(
(w) + { D.
2
-=1
1=1
Then [Mams-at (8))
/m1 is given by:
8=0"
k
k
32/(0= + x(()
Di) 1.))
M2 + MM + M¹ =
Σ
Tr
ro (M) + (a
2
2
3=1
(M)
(a0)" + ra)" - 25م0 D.))
Tr
(1) (w)
k=
Σn Tr
( ToD (1) ra.""" - -2
)
2
(n)
X(r) (w) (a))) + ( - -1t0 ->DD)i))
A k
Tu
(w)
(u)
[a)T (II - 22 Di
==|
N
(x(()
Σ
11 (w) . (IT -200 Dijugo.
[1]
30

---

1
We represent 11m)
= =1+
Ep=1 (1))))
1 ).. Denote the residual term
-x(n)
Mr
N
8
(u)
p (1)
T (0)) 2s (O) (aT - 21 Di)u,"" = 0 )
gk
p=1
We then have:
M Meme-au(o))
71
6=0
-Tr(V rv y
(w) a T 2x V D.V(
-2Tr(Ve ( TV (u), T T ) +2T[(V ( rv
(w) Ds y DiV M.
-Tr(TV, ve (w) u IT (o) (( ) 2 (1) DiVe ( v T
-2Tr(TVV v T (Ix - v +
Ah Di(IN - VE V(")T( + MM
-2TT(TVV (T) + (1)
4 D TT ( T ( J
--2Th T
V D TT a - Di
v (u) i1 [
(w))
+MM
k
-T (T V a -2A Dj + ((() Vl (n) u1 (V + 9k
31

---

D Analysis on Other Contrastive Losses
In this section, we discuss the extension of our graphic-theoretic analysis to one the most common contrastive loss functions SimCLR []]]. SimCLR loss an extended version of InfoNCE loss [68] that achieves great empirical success and inspires a proliferation of follow-up works [5. 8, 12, 26, 34, 69, 77]. Specifically, SupCon [34] extends SimCLR the supervised setting. GCD [69] and OpenCon [63] further leverage the SupCon and SimCLR losses, and are tailored to the open-world representation learning setting considering both labeled and unlabeled data.
At a high level, we consider a general form of the SimCLR and its extensions (including SupCon, GCD, OpenCon) as:
M(x') sayy )} (15)
E P+) = (x,xt)up,
s(x)))
log
xwpp
x'>p aff
where let the P+ the distribution of positive pairs defined in Section 1. In SimCLR [11], the positive pairs are purely sampled in the unlabeled case (u) while SupCon [34] considers the labeled case (l). With both labeled and unlabeled data, GCD [69] and OpenCon [63] sample positive pairs in both cases.
In this section, we investigate an alternative form that eases the theoretical analysis (also applied in [72]):
Egm (f:P+)= = (apot)
E [f(x) f(xt)]
+ +log
E
s(a/rr
(16)
x, v xfs
Zgnl (f:
(17)
which serves an upper bound of Lgal (f) according to Jensen's 's Inequality.
graph-theoretic view. Recall in Section 3.1, define the graph G(X, w) with vertex set X and edge weights w. Each entry of adjacency matrix is given by Wzzz' which denotes the marginal probability of generating the pair for any augmented data J. X!:
7/ W (u)
(1) + 171 Exx
Waz''
and tr measures the degree of node x::
Wr Σ Waz!
One view the difference between SimCLR and its variants in the following way: (1) SimCLR [11] corresponds to 1 = 0 when there is no labeled case; (2) SupCon [34] corresponds to Th = when only labeled case is considered. (3) GCD [69] and OpenCon [63] correspond to the cases when Y/u m are both non-zero due to the availability of both labeled and unlabeled data.
With the define marginal probability of sampling positive pairs Way' and the marginal probability of sampling a single sample Wz, we have:
Egui (Z;)((W,))
1 Σ
Wax ff))) log
Σ
W. (s')) f(x)TT
T x.
2.2'EX ayyla
1
Tr(Z AZ) + log Tr (DDINI D2) (x)exp(( (
When is large:
32

---

Eximete (2: 2 Tr(Z" AZ) + +oog Ir -D) -
1 Tr(Z" AZ) + +log(1 + )
22)
+ const
Tr(Z AZ) + 1 (DINI( - D2)Z)
+ const
- Tr (A
D D2
Tr(D)² - -T((D2) / + const.
we further consider the constraint that the z = 1, minimizing Laimelr (Z; G(X, w)) boils down to the eigenvalue problem such that Z is formed by the top-k eigenvectors of matrix (A Tr(D)= D Tr(Da). Recall that our main analysis for Theorem 4.2 and Theorem 4.3 is based on the insight that the feature space formed by the top-k eigenvectors of the normalized adjacency matrix D AD- AD- $ Viewed in this light, the same analysis could be applied to the SimCLR loss as well, which only differs in the concrete matrix form. We do not include the details in this paper but leave it as future work.
33

---

E Additional Experiments Details
E.1
Experimental Details of Toy Example
Recap of set up. In Section 4.1 we consider a toy example that helps illustrate the core idea of our theoretical findings. Specifically, the example aims cluster 3D objects of different colors and shapes, generated by a 3D rendering software [31] with user-defined properties including colors, shape, size, position, etc. Suppose the training samples come from three shapes, X X X'g Let 3g be the sample space with known class, and X : be the sample space with novel classes. Further, the two novel classes are constructed to have different relationships with the known class, Specifically, the toy dataset contains elements with unique types:
x=x3 U Ugg.
where
3 = (- B . ."g)
X = ( tFo
X3 (z
Experimental details for Figure 3(b). We rendered 2500 samples for each type of data. In total, we have 12500 samples. For known class XG we randomly select 50% as labeled data and treat the rest unlabeled. For training, we use the same data augmentation strategy as in SimSiam [12]. We use ResNet18 and train the model for 40 epochs (sufficient for convergence) with fixed learning rate of 0.005, using SORL defined in Eq. (6). We set !n 0.04 and 7u = 1, respectively. Our visualization is by PyTorch implementation of UMAP [43], with parameters (n no_neighbors=30, min_dist=1.B 2pread=2, metric=euclidean))
E.2 Experimental Details for Benchmarks
Hardware and software. We run all experiments with Python 3.7 and PyTorch 1.7.1, using NVIDIA GeForce RTX 2080Ti and A6000 GPUs.
Training settings. For fair comparison, we use ResNet- 18 [25] as the backbone for all methods. Similar to [7], we pre-train the backbone using the unsupervised Spectral Contrastive Learning [23] for 1200 epochs. The configuration for the pre-training stage is consistent with [23]. Note that the pre-training stage does not incorporate any label information. At the training stage, we follow the
same practice [7, 63], and train our model f()) by only updating the parameters of the last block of ResNet. In addition, we add trainable two-layer MLP projection head that projects the feature from the penultimate layer to an embedding space & (k- = 1000). We use the same data augmentation n7- 0.25, 7u = 1 with training epoch 100,
strategies as SimSiam [12, 23]. For CIFAR- 10, and we evaluate using features extracted from the layer preceding the projection. For CIFAR- 100, we m 0.0225, 7/, with 400 training epochs and assess based on the projection layer's features. We use SGD with momentum 0.9 as an optimizer with cosine annealing (Ir=0.05), weight decay 5e-4, and batch size 512.
Evaluation settings. At the inference stage, we evaluate the performance in a transductive manner (evaluate on D.). We
semi-supervised K-means algorithm as proposed in [69]. We follow the evaluation strategy in [7] and report the following metrics: (1) classification accuracy on known classes, (2) clustering accuracy the novel data, and (3) overall accuracy on all classes. The accuracy of the novel classes is measured by solving an optimal assignment problem using the Hungarian algorithm [36]. When reporting accuracy on all classes, solve optimal assignments using both known and novel classes.
34


Reviews:
[{"review_id": "GMZDo09tOz", "reviewer": "Reviewer_iP9L", "summary": "The paper tackles the domain of open-world representation learning, which aims to learn representations that can correctly cluster samples in the novel class and classify samples in the known classes by utilizing knowledge from the labeled data. Notably, the motivation of this paper is to provide a theoretical foundation in this area by introducing a novel graph-theoretic framework specifically designed for open-world settings. Theoretically, the crux of the framework involves characterizing clustering through graph factorization. A new algorithm called Spectral Open-world Representation Learning (SORL) is introduced, which essentially involves spectral decomposition on the graph. The authors provide theoretical guarantees by deriving a provable error bound on the clustering performance for both known and novel classes. Practically, the paper also offers empirical evidence, demonstrating that SORL is competitive with, or even superior to, existing methods on benchmark datasets.", "questions": "1. It would be interesting to see the results in a larger benchmark dataset, ImageNet 100. \n\n2. What is the effect of using different known and novel classes ratio besides 50%? Like, 0.25, 0.1.\n\n3. How do you choose the hyper-parameters, $\\eta_{u}$, $\\eta_{l}$?\n\n4. In the supplementary material, it is mentioned that pre-training is used. I wonder why this pre-training is necessary for this method and what it will be without pertaining.", "limitations": "The broader impact has been discussed. It has a positive potential impact on the community.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper is well-written with clear motivation and structure. \nOverall interesting problem; good mathematical exposition; solid theoretical results and analysis; interesting and good experimental results", "weaknesses": "1. The experiments are not sufficient. Other large commonly used benchmark dataset is not used, like ImageNet-100. \n2. The paper has a very good theoretical analysis. But it is still unclear what contributes to the performance improvement.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe thank the reviewer for the insightful questions! Below we address each of your comments in detail. \n \n#### **- Results on ImageNet-100.**\n\nSure! As suggested, we report below results on the ImageNet-100 benchmark, which is commonly compared in the literature.  For ImageNet, the training and evaluation setting is consistent with prior works (ORCA, GCD, OpenCon, etc), which have a division of 50 known classes and 50 novel classes. \n\n\nThe empirical results suggest that SORL is comparable to the current state-of-the-art methods with a <1% gap in terms of overall accuracy. Beyond chasing the benchmarks, the significance of our work lies in providing an in-depth theoretical understanding of the open-world representation learning task (which is urgently lacking in the field). \n\n\n| Method |\tAll | \tNovel |\tSeen |\n|--------|----------|-------|-------|\n| FixMatch  (Kurakin et al., 2020) |  34.9 | 36.7 | 65.8 |\n| DSL\t(Guo et al., 2020)  |  30.8 | 32.5 | 71.2 |\n| CGDL (Sun et al., 2020) |  31.9 | 33.8 | 67.3 |\n| DTC\t(Han et al., 2019) |  21.3 | 20.8 | 25.6 |\n| RankStats  (Zhao & Han, 2021) \t|  40.3 | 28.7 | 47.3 |\n| SimCLR  (Chen et al., 2020a)  |  36.9 | 35.7 | 39.5 |\n| ORCA (Cao et al., 2022) |  76.4 | 68.9 | 89.1 |\n| GCD\t (Vaze et al., 2022) |  75.5 | 72.8 | 90.9 |\n| OpenCon  (Sun et al. 2023)\t|  83.8 | 80.8 | 90.6 |\n| SORL (Ours)\t|  82.9 | 80.4 | 89.2 |\n\n\n#### **- Discussion on the performance improvement over baseline methods.**\n\nWe are happy to share insights on the differences in the representation learning strategies that have been implemented in baseline methods. Two of the most recent methods, GCD and OpenCon, employ a combinatory training approach that leverages both supervised contrastive learning (SupCon) with labeled samples, and self-supervised contrastive learning (SimCLR) with unlabeled samples. A detailed theoretical explanation of this strategy is available in Appendix D.  At a high level, the feature space derived from “SupCon+SimCLR” is given by the top-k eigenvectors of a matrix different from SORL. This insight serves as an invitation to other researchers to further explore and provide more comprehensive comparisons between different representation learning strategies.\n\n#### **- Results with different known/novel class ratios.**\n\nGreat suggestions! We provide a comparison by reducing the known class number from 50 (default) to 25 and 10 on CIFAR-100, while keeping the labeling ratio to be the same (i.e., 50%). The results suggest that using more known classes will help the clustering performance of the novel classes.\n| Known Classes Number | Method |\tAll | Novel | Seen |\n|--------|--------|----------|-------|-------|\n| 50 | SORL | 55.8 | 51.7 | 68.4 |\n| 25 | SORL | 50.1 | 47.7 | 68.5 |\n| 10 | SORL | 48.6 | 47.3 | 66.0 |\n\n#### **- Strategy in choosing hyperparameters $\\eta_u$ and $\\eta_l$.**\n\nGood question! We follow the validation strategy proposed in prior works of open-world representation learning (See Appendix I in Sun et al., 2023). Specifically, we split the classes in $\\mathcal{Y}_l$ equally into two parts: known classes and “novel” classes (for which we know the labels). Moreover, 50% of samples in the selected known classes are labeled. The constructed validation dataset is used to select the hyper-parameters by grid searching. \n\n#### **- The necessity of using a pre-trained model.** \n\nFair concern! We use the pre-trained model mainly for several reasons:\n\n1. *Adhering to Protocols in Prior Works*. The learning setting that encompasses both labeled and unlabeled data, along with a mixture of known and novel classes, was first introduced in ORCA (Cao et al., 2022). This approach employs the ORCA algorithm on a ResNet model pre-trained using self-supervised loss, a strategy also applied in subsequent works (such as OpenCon, GCD, etc.). To maintain a fair comparison, we adhere to this established convention.\n\n2. *Efficiency in Training*. Importantly, by utilizing a pre-trained backbone, both prior works and SORL focus on training only the projection layers and the last block (layer4) of the ResNet, while keeping the preceding blocks fixed. This approach is more effective in training by consuming less GPU memory and significantly reducing the number of gradient update steps.\n\n3. *Emulating the Real-World Pipeline*. In the industry, it's standard practice to first train a model using self-supervised loss on a large corpus of unlabeled data. Leveraging such a pre-trained model enables a wide array of downstream tasks depending on the additional labeled information available. The exploration of the label perturbation on the pre-trained model constitutes a key research question investigated in this paper.\n\nWhat if we do not apply the pertaining? As we have shown in the following table, they exhibit similar performance. \n\n| Pretrain Epochs | Training Epochs | Method | All | \tNovel |\tSeen |\n|--------|--------|----------|-------|-------|-------|\n| 1200 | 400 | SORL | 55.8 | 51.7 | 68.4 |\n| 0 | 1600  | SORL | 55.4 | 52.2 | 67.8 |"}, {"review_id": "rzvLB20sJE", "reviewer": "Reviewer_7sHp", "summary": "This paper formulate the open-world representation learning using the graph. \nThis paper provides theoretical analyses for the framework (Thm 3.1) as well as the framework's performance (Thm 4.1 & 4.2).\nThe experimental results show that the framework outperforms the exiting method in the open-world learning setting.", "questions": "- How much do the things need to be different in order to learn?\n\nBy learning something, how much the SORL can distinguish some similar things?\nIf we do not know anything about the green apple, can we increase the chance to distinguish the different variety of the green apple by learning green signals? Maybe the difference between the variety of the green apple is embedded in the spectral gap, but do you have any insights on this?\n\n- I'm just curious how did you come up with Eq. (6)?\n\n- This is not the question but a comment connecting to (*) in the strength section.\n\nThe Eq.(5) gives the SVD, but in this case Eq.(5) gives the eigendecomposition. Since the normalized Laplacian $L$ is defined as L := I -A, the Eq. (5) gives the k smallest eigenvalues. Thus, since the $k$ smallest eigendecompoition of the normalized Laplacian corresponds to the relaxed solution of the normalized graph cut, the SORL is actually corresponds to the relaxed solution of the normalized graph cut (see Sec.5.3 in [i]). \nFrom this viewpoint, as far as I understand, Thm 3.1 can be more powerful for the spectral clustering community -- the Eq. (6) corresponds the result of the spectral clustering (i.e., the relaxed solution of the normalized graph cut).\n\nWith this, the proposed method is not surprising (in a good sense); the proposed SORL is an open-world learning hinted normalized graph cut.\n\nFrom this view, I'd like to connect the point (**), if this method is faster than SVD, this indicates that there can be some faster way of the spectral clustering?\n \n- This is also minor but the authors might want to cite [i], which is the one of the most cited paper in spectral clustering.\n\n[i] Von Luxburg, Ulrike. \"A tutorial on spectral clustering.\" Statistics and computing 17 (2007): 395-416.\n\n\n\n----\n\nPOST REBUTTAL\n\nI'm satisfied with the authors' rebuttal, therefore I increase my score from 6 to 7.", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall, I enjoy reading this paper and have a positive feeling.\n\n- Formulation. Of Eq. (6). By Thm. 3.1 this formulation corresponds to the SVD of normalized adjacency matrix Eq. (4). See more on the question (*).\n\n- The theoretical insights (Thm 4.1 & 4.2). The analyses using $k$-means measure strengthen the formulation. Particularly, the insight in L251-L258 is interesting; knowing more about green light increases the knowledge about the green apple, but not the flowers. This corresponds to our intuition.", "weaknesses": "There's little I can say, but if I need to raise one, I would like to point out on the experiment.\n\nThe experiment is on the only one split, but I am curious the other splits. Ideally it'd be nice to have results like Fig 4 in [79], y-axis accuracy vs x-axis # of the known labels. \nBy seeing this, we can know \"how many pictures of the green light do we need to learn in order to know the green apple?\"\n\nI also would like to know the computational time, see more on the question section (**)\n\nFrom this viewpoint, I would give 6.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the insightful questions! Below we address each of your comments in detail. \n\n#### **- Experiments with different labeling ratios.**\n\nGreat suggestions! We provide the comparison by reducing the labeling ratio from 50% (default) to 25%, 10% and 0% on CIFAR-100, while keeping the number of known classes to be the same (i.e., 50 in CIFAR-100). The results suggest that a small portion of labels can lead to a strong improvement in the accuracy for both known and novel classes. \n\n| Labeling Ratio | Method |\tAll | Novel |\tSeen |\n|--------|--------|----------|-------|-------|\n| 50% | SORL | 55.8 | 51.7 | 68.4 |\n| 25% | SORL | 54.4 | 50.5 | 64.4|\n| 10% | SORL | 51.6 | 50.4 | 60.2|\n| 0% (unsupervised) | SORL  | 37.3 | 40.2 | 38.3 | \n\n#### **- Insights on learning the variety of similar samples.**\nSure! We are pleased to share insights on the subject of distinguishing similar samples, which revolves around three sub-questions. \n1. *How much can SORL distinguish similar things?*  \nThe ability to differentiate between similar items using the SORL algorithm depends on the embedding size $k$, as determined by the neural network. Specifically, the size $k$ correlates to the rank of the approximation matrix used within the SORL algorithm. A larger $k$ provides a greater capacity to perceive subtle differences among similar samples. In our experiments on the CIFAR dataset, we set $k=1000$ to allow the encoding of a broad spectrum of variations, going beyond mere class distinctions.\n\n2. *How to increase the chance to distinguish the different varieties?*\n a) Should the learning capacity permit, increasing the dimensionality $k$ can extend the \"volume\" to encompass more varieties.\nb) Enhancing the augmentation strategy contributes to a more precise adjacency matrix, assisting the model in better discerning subtle differences between varieties.\n \n3. *What is the relationship between the variety and the spectral gap?* \nAt a high level, the magnitude of singular values ($\\sigma$) reflects the importance of a specific variety (represented by a singular vector). A larger spectral gap implies a significant variation in importance levels. For instance, the $\\sigma$ for features that distinguish red from green would be considerably larger than the $\\sigma$ that differentiates light green from dark green.\n\n#### **- Rationale in deriving Eq. (6).**\nWe derive Eq. (6) by unfolding the Frobenius norm of $\\mathcal{L}_{mf}$. A high-level explanation of proof is in L153 to L155. \n\n#### **- Application of theorem to a broader spectral clustering community.**\nWe are grateful for the reviewer's insightful comments and agree with the potential of applying our algorithm to traditional spectral clustering. In response to the points raised by the reviewer, we offer detailed discussions on the following subjects:\n\n+ *Set up for learning tabular data.* Our SORL algorithm is constructed using an augmentation graph where each element represents the probability of considering two samples as positive pairs. The augmentation strategy can be tailored for tabular data; for example, by adding noise to continuous data or permuting items in discrete data. This approach essentially resembles distance-based graphs, such as the k-nearest neighbor graph.\n+ *Applying the main theorem to the spectral clustering community*. Definitely! We can directly apply Theorem 4.1 (assuming the reference to 3.1 is a typo in the comments) to spectral clustering, provided it is built upon the augmentation graph as discussed in point (a).\n+ *Computational aspects.* We concur with the reviewer's observation that SORL can be more efficient than running a full SVD on the entire graph. This efficiency is due to SORL's utilization of a sampling strategy. It's noteworthy to mention that while SORL is confined to the augmentation graph, SVD can be applied to all graphs.\n+ *Citing [i]*. Thanks for pointing it out! We have added it to our revised draft. "}, {"review_id": "2tf800nNLX", "reviewer": "Reviewer_66eW", "summary": "This paper presents spectral open-world representation learning that aims to learn low-rank approximation of a constructed adjacency matrix. From this perspective, the authors study how the label information help (or hurt) the classification performance by analyzing the error bound. Experiments on image classification benchmarks show the effectiveness of the proposed approach. ", "questions": "1. Is it possible to generalize the analysis to the SSL and supervised learning settings?\n2. Is the spectral gap in theorem 4.1 crucial for the result?", "limitations": "Please see the weakness section. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. The formulation of open-world representation learning problem as a low-rank approximation of a weighted graph adjacency matrix is novel and reasonable.\n2. The representation is clear. The provided illustrative example is helpful for understanding the theory.\n3. The new ORL approach itself is simple yet effective.", "weaknesses": "1. The theoretical analysis presented in the main text is only applicable to the proposed SORL approach. Generalizing to other approaches needs independent considerations as stated by the authors in section 6.\n2. The empirical validation seems somewhat disconnected with the main theoretical result (theorem 4.1 and 4.2) as it only focuses on the performance of SORL. It would be better to conduct experiments to directly validate the main theorems e.g. by showing the connection between performance improvement by adding different label information and factors affecting $\\Delta_{\\pi_s}(\\delta)$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe thank the reviewer for the insightful questions! Below we address each of your comments in detail. \n\n#### **- Generalization of the theoretical analysis.**\n\nFair concern! We are happy to expand our thoughts on the generalization of our theoretical analysis within a broader context. The primary objective of introducing SORL is to establish the first theoretical framework that has been lacking in the field of open-world representation learning for several years. We believe that this framework will open up new avenues for a deeper understanding of the effects of labeling perturbation within the community. Specifically:\n\n+ *SORL answers the fundamental question common to all methods in open-world representation learning*. \nAt a high level, SORL analyzes how the added label changes the representation space that leads to different clustering outcomes. This finding can be generalizable to other methods which may differ in the way of incorporating new labels. \n\n+ *SORL paves the way to formally understand open-world representation learning methods.* \nWe have laid the groundwork for understanding the closed-form solutions of these learning algorithms from a theoretical standpoint. Viewed from this perspective, the same analytical strategy employed in this paper remains applicable. For instance, we demonstrated in Section 6 that \"SimCLR+SupCon\" is a factorization of another regularized form of the adjacency matrix, where the perturbation analysis can be equally applied. \n\n + *SORL is also appealing for practical usage*. \nOur framework is also empirically appealing to use since it can achieve similar or better performance than existing methods on benchmark vision datasets. In particular, on CIFAR-100, we improve upon the best baseline OpenCon (Sun et al., 2022) by 3.4% in terms of overall accuracy. \n\n#### **- Experiments validating theoretical results.**\nThank you for the excellent recommendations! To delve into the performance disparities among cases with different types of label information, we've structured the experimental setup described below. \n\nWe've classified the settings into three categories: `unsup`, `sup-weak`, and `sup-strong`.\n\n+ The `unsup` category represents cases without any label information.\n+ The `sup-weak` setting involves adding labels to the 50 sub-classes within the first 10 super-classes.\n+ The `sup-strong` category entails the distribution of labels evenly across 50 sub-classes spanning all super-classes.\n\nFor clarity, we illustrate the configurations for sup-strong and sup-weak in the tables below, showcasing 20 CIFAR-100 classes within four super-classes. Within this configuration, the names of the known classes (those receiving labels) are highlighted in **bold**.\n\nThis design ensures that the `sup-strong` setting fosters a more significant relationship between known classes with label information and novel classes compared to the `sup-weak` setting. The empirical results presented in the table below substantiate this insight. The clustering accuracy for the novel classes is ranked as: `sup-strong` > `sup-weak` > `unsup`.\n\n\n+ **Empirical comparison**\n\n| Setting | Method |\tAll | Novel | Seen |\n|--------|--------|----------|-------|-------|\n| `unsup` | SORL | 37.3 | 40.2 | 38.3 | \n| `sup-weak` | SORL | 49.8 | 46.4 | 66.0 |\n| `sup-strong` | SORL | 56.3 | 53.5 | 67.1 |\n\n+ **Setting `sup-weak`:**\n \n| Super-class    | Sub-class  |\n|---------------|----------|\n|aquatic mammals | **beaver, dolphin, otter, seal, whale**|\n|fish | **aquarium fish, flatfish, ray, shark, trout**|\n| ... |... |\n|vehicles 1   \t| bicycle, bus, motorcycle, pickup truck, train|\n|vehicles 2   \t| lawn-mower, rocket, streetcar, tank, tractor|\n \n+ **Setting `sup-strong`:**\n \n| Super-class    | Sub-class  |\n|---------------|----------|\n|aquatic mammals | **beaver, dolphin, otter**, seal, whale|\n|fish | **aquarium fish, flatfish**, ray, shark, trout|\n| ... |... |\n|vehicles 1   \t| **bicycle, bus, motorcycle**, pickup truck, train|\n|vehicles 2   \t| **lawn-mower, rocket**, streetcar, tank, tractor|\n\n\n\n#### **- Generalization to the self-supervised or supervised learning setting.**\nOur theorem explores the effects of labeling perturbation by comparing the performance between the self-supervised learning setting and the setting with partially available label information. This analysis can be further generalized to the supervised learning setting. It can be regarded as a special case within the open-world learning framework, where all classes are known and every sample is labeled.\n\n\n#### **- The role of the spectral gap.**\nOur response is in a two-fold manner.\n+ For the clarity of the theoretical results, assuming a large spectral gap is a standard practice in spectral analysis (Joseph et al., 2016; Shen et al., 2022), a convention we also have adhered to in our study.\n+ At a high level, it should be noted that the term remains small in most practical scenarios even in the absence of the spectral gap term.\nIn more detail, the residual term related to the spectral gap, is included in lines 497-498 of the Appendix. For this term to become large, several conditions must be satisfied simultaneously:  1). spectral gap between $\\sigma_k$ and $\\sigma_{n}$ must be small. 2). eigenvector $v_{n}$ (corresponding to $\\sigma_{n}$) in the null space must encode the critical class information that is missing in the feature space; 3). eigenvector $v_{n}$ must align with the vector $\\mathfrak{l}$ which encodes the connection to label data. Although it's theoretically possible to construct a scenario where this occurs, we have chosen not to delve further into this in order to focus on conveying the main intuition of our work.\n\n\n\n\n"}, {"review_id": "4ViiN6Nr37", "reviewer": "Reviewer_1J6p", "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.\n", "questions": "**Size of the data augmentation graph:**  \nThe 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?  \n\n**Empirical Validation:**  \n- 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)?   \n- 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?    \n- 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?   \n- 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.  \n- 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.    \n\n**Minor:**  \n- The batch size of 512 is rather small for contrastive learning. Why is that?  \n- Are the different islands of points that share both color in shape in Fig 3b meaningful? Do they encode perhaps the size or position?\n\n**References:**  \n[1] Rebuffi, Sylvestre-Alvise, et al. \"Lsd-c: Linearly separable deep clusters.\" Proceedings of the IEEE/CVF international conference on computer vision. 2021.\n", "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. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "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:**  \nIn 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.  \nFirst, 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?  \nSecond, 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?    \n\n**Empirical illustration of the main theorems:**  \nIt 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.  \n\n\n**Minor:**  \n- 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. \n- 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.   \n- 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.  ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nWe thank the reviewer for the insightful questions! Below we address each of your comments in detail. \n\n#### **- Discussion on the augmentation graphs.**\nWe have noted the reviewers' concerns regarding the definition of the augmentation graph from several angles, and we address these concerns as follows:\n\n 1. *The feasibility of augmenting two real images to the same view.*  \nWe agree that most images cannot be augmented from images with dissimilar content when limiting the augmentation strategies to commonly applied techniques like cropping and color jittering. However, it becomes achievable once we expand the strategy to include the use of generative models. Though it's not necessary to apply generative augmentation in contrastive learning, the research community (Haochen et al., 2021; 2022; Shen et al., 2022) is actively utilizing the concept of the augmentation graph to theoretically explain the practical success of contrastive learning.\n2. *The finiteness of the augmentation graph.*\nThough $N$ can be incredibly large in practice, it remains finite. It is upper-bounded by $256^{3 \\times W \\times H}$, considering a $W \\times H$ RGB image. Despite its finiteness, the graph remains intractable in practice when considering all augmentation views. This complexity necessitates the use of SORL to learn a low-rank representation space, enabling us to approximate the graph rather than directly optimizing $\\mathcal{L}_{mf}$. \n3. *The order of the augmentation probability.*\nIn the main theory sections (4.1 & 4.2), we do not make any assumptions regarding the order of augmentation probability since it is inherently determined by the augmentation strategies. \n\n#### **- Justification on the graph setup for the toy example.**\n\nWe are happy to provide justification for the reviewer’s concern about the setup in the toy example from several aspects: \n\n1. *Why only consider shape and color?*.\nWe fully agree with the reviewer's insight that real 3D-shape images include a broad range of properties, including color, shape, angle, position, size, material, etc. However, our primary objective with the toy example is to elucidate the main intuition. Therefore, we have chosen to focus solely on the two most salient features, color and shape, in constructing our toy augmentation graph.\n2. *Why assume a non-zero $\\tau_c$?*.\nGiven our simplification of the property set to {color, shape}, we also presume the existence of augmentation strategies capable of permuting colors and shapes. As a result, $\\tau_c$  and $\\tau_s$ are two non-zero values in our toy example.\n3. *Why assume $\\tau_c$ >  $\\tau_s$?*\nIt's essential to note that this assumption only serves to facilitate our illustration and does not impact the main theorem or empirical validation. Our principal goal here is to demonstrate that the addition of labels can alter clustering outcomes. In Figure 3(a), we depict how adding labels to cubes can reverse the incorrect trend where samples are clustered by color. Similarly, one could also construct a toy example where $\\tau_s$ > $\\tau_c$, demonstrating that adding labels to \"red samples\" can invert the clustering results by shapes.\n\n\n\n#### **- Empirical illustration of the main theorems.**\n\nGreat suggestions! In response, we are pleased to introduce numerical verification to affirm the correctness of Theorems 4.1 and 4.2 with our toy example. **Due to the space limitation, we provide the details in the [additional rebuttal pdf](https://openreview.net/attachment?id=09O88IQijF&name=pdf)**.  \n\n\nIt is important to note that applying Theorems 4.1 and 4.2 necessitates explicit knowledge of the adjacency matrix. However, obtaining such a matrix becomes intractable in real datasets, particularly when considering all augmentation views of source images. \n\n#### **- Justification on results of SimCLR.**\n\nWe are happy to collaborate with the reviewer to justify the baseline results, which are directly cited from the prior work ORCA (Cao et al., 2021). To reproduce the results, we train SimCLR on CIFAR-10, using the code available at https://github.com/HobbitLong/SupContrast. Our training achieved an All/Novel/Seen Accuracy of 61.1/81.0/72.1, which is notably higher than what was reported in ORCA. Furthermore, we noted that K-means results tend to fluctuate when accuracy is low and class number is small, as with CIFAR-10. An unfortunate initialization of class centers can significantly downgrade clustering performance. This observation might provide insights into why the magnitude order can sometimes diverge from expectations.\n\n\n\n\n#### **- Other comments and questions.**\n\n+ *Measuring SORL/SimCLR on Linear Probing/KNN classifier protocol.* As suggested, we provide the comparison of SimCLR and SORL below. By having more label information, SORL performs stronger than SimCLR on CIFAR-10, which follows the intuition. \n\n| Method | Linear Probing | KNN classifier|\n|--|--|--|\n| SimCLR | 87.6 | 86.2 |\n| SORL | 92.9 | 91.4 |\n+ *Performance on LSD-C*. For the reviewer's interest, the All/Novel/Seen accuracy on CIFAR-10 is 82.1/88.8/87.6 respectively.\n+ *Why do we use 512 as a batch size?* To ensure a fair comparison in training setup, we follow the protocol in existing works including ORCA (Cao et al., 2021) and OpenCon (Sun et al., 2023). \n+ *What do different islands of points mean in Figure 3(b)?* Great catch! When we generate these 3D shapes, there are other variants like materials (rubber, metal) and sizes (big, small). Therefore, the sub-clusters are very likely to represent other variants. \n\n\n#### **- Writing suggestions.**\n+ *The conclusion of UMAP visualization.* Thanks for the suggestions! We will revise the claim as suggested in Figure 3(b). \n+ *The explicitness of the labeling perturbation setup.* Great comment! See changes in the global response. \n+ *Adjustment in the layout of Figure 2.* Fixed, thanks for the suggestion!\n+ *Add the limitation discussion.* Absolutely! See global response.\n\n"}]

Author rebuttal:

We thank all the reviewers for their constructive and valuable feedback. 
 
We are honored that the reviewers acknowledge the novelty of our graph-theoretic framework (R1, R3, R4) with excellent contribution (R1, R4) and soundness (R1). 
Multiple reviewers value the theoretical nature of our paper (R4), finding theoretical insight to be interesting (R2) and solid (R1). Beyond theoretical insight, the reviewers recognized the practical values of the framework (R4), with the approach to be simple and effective (R3) and empirical results outperforming (R1, R2, R3) the existing methods in the open-world learning setting. We are equally glad with R2's enjoyment in reading the paper, and the comments with excellent presentation (R1, R3), well-written (R1, R4), clear motivation and structure (R1) of our paper. 
 
We have addressed the reviewers’ comments and concerns in individual responses to each reviewer. 
 
(\* As abbreviations, we refer to **Reviewer iP9L** as R1, **Reviewer 7sHp** as R2, **Reviewer 66eW** as R3, and **Reviewer 1J6p** as R4 respectively.)

As suggested by R4, we added the following paragraphs to the draft: 

+ Added the paragraph “Analysis goal” in Section 2: 

*Our analysis goal is to comprehend the role of label information in shaping representations for both known and novel classes. it's essential to note that our theoretical approach aims to understand the perturbation in the clustering performance by labeling existing, previously unlabelled data points within the dataset.  By contrasting the clustering performance before and after labeling these instances, we uncover the underlying structure and relations that the labels may reveal. This analysis provides invaluable insights into how labeling information can be effectively leveraged to enhance the differentiation of both known and novel classes.*
+ Added the limitation discussion section.

*Limitation: Our theoretical framework has two potential limitations to be considered in practice: a)  The augmentation graph serves as a potent theoretical tool for elucidating the success of modern representation learning methods. However, it is challenging to ensure that current augmentation strategies, such as cropping, color jittering, or Gaussian blurring, can transform two dissimilar images into identical ones.  b) The utilization of Theorems 4.1 and 4.2 necessitates an explicit knowledge of the adjacency matrix of the augmentation graph, a requirement that can be intractable in practice. 
In light of these limitations, we encourage further research to enhance the practicality of these theoretical findings.*

Meta-review: The paper aims at improving the theoretical understanding of open-world representation learning by introducing a novel graph-theoretic framework. The paper is well written and the mathematical exposition is clear. Although there were some concerns regarding the breadth of the numerical examples, the authors have addressed those in the rebuttal to the satisfaction of the reviewers.
Decision: Accept (spotlight)