# Open-World Semi-Supervised Learning for Node Classification

Yanling Wang1,2, Jing Zhang1∗, Lingxi Zhang1, Lixin Liu3, Yuxiao Dong4
Cuiping Li1, Hong Chen1, Hongzhi Yin5 $*$ Corresponding author 1 School of
Information, Renmin University of China 2 Zhongguancun Laboratory  3 Alibaba
Group 4 Department of Computer Science and Technology, Tsinghua University  5
School of Information Technology and Electrical Engineering, The University of
Queensland<EMAIL_ADDRESS>{zhang-jing, zhanglingxi, licuiping,
<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Open-world semi-supervised learning (Open-world SSL) for node classification,
that classifies unlabeled nodes into seen classes or multiple novel classes,
is a practical but under-explored problem in the graph community. As only seen
classes have human labels, they are usually better learned than novel classes,
and thus exhibit smaller intra-class variances within the embedding space
(named as imbalance of intra-class variances between seen and novel classes).
Based on empirical and theoretical analysis, we find the variance imbalance
can negatively impact the model performance. Pre-trained feature encoders can
alleviate this issue via producing compact representations for novel classes.
However, creating general pre-trained encoders for various types of graph data
has been proven to be challenging. As such, there is a demand for an effective
method that does not rely on pre-trained graph encoders. In this paper, we
propose an IMbalance-Aware method named OpenIMA for Open-world semi-supervised
node classification, which trains the node classification model from scratch
via contrastive learning with bias-reduced pseudo labels. Extensive
experiments on seven popular graph benchmarks demonstrate the effectiveness of
OpenIMA, and the source code has been available on
GitHub111https://github.com/RUCKBReasoning/OpenIMA.

###### Index Terms:

Node classification, Open-world semi-supervised learning, Variance imbalance,
Contrastive learning

##  I Introduction

With the advance of graph neural networks (GNNs), semi-supervised node
classification [1, 2, 3, 4, 5, 6, 7] has achieved remarkable breakthroughs.
Despite the success, most node classification models are developed under the
closed-world setting, assuming that both labeled and unlabeled data originate
from the same set of classes. In real-world scenarios, this assumption rarely
holds true because it is impractical for humans to label all possible classes
in the world. Therefore, some studies [8, 9, 10, 11, 12, 13] explored open-
world node classification, where test nodes are assumed to be from either seen
classes or novel classes. These efforts treat nodes of novel classes as out-
of-distribution (OOD) instances, thus assigning them into an outlier class.
More practically, our work aims to classify test nodes into previously seen
classes or multiple novel classes, formally named as open-world semi-
supervised learning (open-world SSL) for node classification. Figure 1a
illustrates an example in a coauthor network, where nodes represent authors,
edges depict coauthor relationships, and the colors of the nodes denote the
authors’ primary research fields. Since novel research fields emerge over
time, and it is challenging to promptly update the label information, a model
is desired to classify unlabeled authors into previously seen fields or newly
emerging fields.

(a) An example of open-world SSL in a coauthor network.

Imbalance Rate Separation Rate Test Accuracy Seen Novel InfoNCE  1.002 1.239
0.728 0.727 InfoNCE+SupCon  1.071 1.271 0.751 $\uparrow$ 0.710 $\downarrow$
InfoNCE+SupCon+CE  1.089 1.275 0.771 $\uparrow$ 0.730 $\uparrow$ OpenIMA
(Ours) 1.048 1.430 0.783 $\uparrow$ 0.759 $\uparrow$

(b) Effects of the variance imbalance on the Coauthor CS dataset. The
imbalance rate quantifies the imbalance of intra-class variances between seen
and novel classes, and the separation rate measures the separation between
seen and novel classes. Detailed calculation method is introduced in Section
III-B

Figure 1: Motivations of this work. (a) The solid circles represent labeled
nodes, and the dashed circles represent unlabeled nodes. (b) The results are
averaged over ten runs. Model performance on other datasets are reported in
Table III.

The key to solving this problem lies in high-quality node representation
learning. However, as only seen classes have manually labeled nodes, the seen
classes are often better learned than the novel classes to exhibit smaller
intra-class variances in the embedding space. We illustrate the imbalance of
intra-class variances between seen and novel classes on the right side of
Figure 1a. In fact, the variance imbalance also occurs on other types of data.
To alleviate the issue, efforts [14, 15, 16, 17, 18, 19, 20, 21] in the field
of computer vision commonly use a pre-trained ResNet [22] or a pre-trained
Vision Transformer (ViT) [23] to obtain more compact representations for
samples of novel classes. Nevertheless, graph community presently lacks
general pre-trained feature encoders because data distributions can vary
significantly across different graph types [24, 25]. Although pre-trained
graph encoders like GCC [24] and Graphormer [25] have been proposed, the
related studies typically conduct pre-training and fine-tuning/prompting [26,
27, 28] on the same or similar types of graph data, which limits their
applicability. Without a general and powerful pre-trained graph encoder, the
variance imbalance between seen and novel classes naturally becomes a core
factor to impact open-world SSL on a graph. Motivated by this, we target to
(1) explore how the variance imbalance affects open-world SSL for node
classification, and (2) design an effective method to alleviate the variance
imbalance issue without relying on pre-trained graph encoders.

To achieve the goal, we start with a preliminary experiment on the well-known
Coauthor CS graph dataset [29]. Firstly, we divide classes into seen classes
and novel classes, and construct a labeled set and an unlabeled set (Cf.
Section V). To quantify the variance imbalance and measure the separation
between seen and novel classes, we introduce two metrics — imbalance rate and
separation rate in Section III-B. Initially, we employ the unsupervised
contrastive loss InfoNCE [30] to learn representations for both labeled and
unlabeled nodes, enabling unbiased learning of seen and novel classes. Then we
successively add supervised losses to retrain the model, including a
supervised contrastive loss SupCon [31] and the classic cross-entropy (CE), to
enhance the representation learning of labeled nodes. By doing this, the
intra-class variances of seen classes can gradually decrease, leading to
increasing imbalance rates (Cf. the second column of Figure 1b). Meanwhile,
the seen classes become more separated from the novel classes, leading to
increasing separation rates (Cf. the third column of Figure 1b). Under
different imbalance/separation rates, we run K-Means [32] over node
representations to cluster nodes, and align seen classes with specific
clusters for final node classification. From Figure 1b, we make the following
observations:

  * •

When the separation rate is relatively low, the imbalance rate plays a crucial
role in impacting the model performance on novel classes. Clearly, increasing
the imbalance rate would decrease the accuracy on novel classes (Cf. InfoNCE
vs. InfoNCE+SupCon), as dispersed node representations of novel classes are
prone to be incorrectly clustered.

  * •

When the seen classes are thoroughly learned and become well separated from
the novel classes, the increase of the imbalance rate would not hurt the
performance on novel classes (Cf. InfoNCE+SupCon vs. InfoNCE+SupCon+CE).

Our theoretical analysis in Section IV-A supports these findings.

Inspired by the insights, we propose an IMbalance-Aware method named OpenIMA
for Open-world semi-supervised node classification — a simple and effective
method to suppress the imbalance rate and increase the separation rate
(demonstrated in Figure 1b). Specifically, we introduce pseudo labels to
reduce the intra-class variances of novel classes and enhance the learning of
seen classes. Generally, previous work trains a classifier in a supervised or
semi-supervised manner for pseudo-labeling [15, 33, 34]. However, due to the
absence of powerful pre-trained feature encoders for representing nodes, the
node classifier tends to be seriously biased towards the seen classes.
Therefore, we convert to unsupervised clustering to foster a more equitable
pseudo-labeling. Considering the unordered nature of cluster IDs, we align
clusters with classes. However, the clusters corresponding to novel classes
can not be aligned, making the class IDs of novel classes remain unordered.
Hence we adopt contrastive learning (CL) to learn the bias-reduced pseudo
labels, as CL captures semantic knowledge by learning whether two samples come
from the same class instead of assigning them to specific classes as done in
cross-entropy.

Overall, our work makes the following contributions:

  * •

Based on empirical and theoretical analysis, we find that the imbalance of
intra-class variances between seen and novel classes is a critical factor that
impacts open-world SSL on a graph. To our knowledge, this is a pioneer work to
theoretically analyze the imbalance of intra-class variances between seen and
novel classes. Moreover, we investigate open-world SSL for node
classification, which has been less-explored before.

  * •

Based on our intriguing observations, we develop OpenIMA for open-world semi-
supervised node classification, which alleviates the variance imbalance issue
to more effectively learn seen and novel classes from scratch.

  * •

We conduct comprehensive experiments on seven real-world node classification
datasets by comparing OpenIMA with representative baselines. The experimental
results demonstrate the superiority of OpenIMA over the baselines. Especially
on Coauthor Physics and ogbn-Products, OpenIMA derives 11.8% and 12.5% gains
of overall accuracy compared with the best baseline, respectively.

##  II Related Work

This work explores open-world SSL for node classification. Therefore, we first
review research on open-world SSL. Then, we introduce tasks similar to open-
world SSL and explain how open-world SSL differs from these tasks. Finally, we
review efforts on open-world node classification to explain differences
between these works and OpenIMA, and then clarify the challenge of open-world
SSL for node classification.

###  II-A Open-World Semi-Supervised Learning

The goal of open-world SSL [14, 15, 16, 17, 18, 19, 20, 21] is to group
unlabeled instances into seen classes and multiple novel classes. Considering
that the novel classes lack human labels, existing open-world SSL methods
usually perform pseudo-label generation to enable a self-training style
learning [33, 34, 15, 21]. In general, a classifier composed of a feature
encoder and a classification head, is trained to generate pseudo labels.
However, as only seen classes have human labels, the classifier is prone to be
biased towards the seen classes. In the field of computer vision, powerful
pre-trained vision encoders are widely used to initialize the feature encoder
[33, 15, 21], which largely alleviates the difficulty in discriminating
between seen and novel classes and thus reduces the biased prediction.
Nevertheless, when it comes to the graph community, due to the absence of
general pre-trained graph encoders, we desire a more effective solution to
generate bias-reduced pseudo labels.

For the variance imbalance between seen and novel classes, a previous work
named ORCA [20] has mentioned it as a critical factor to affect open-world
SSL, while it does not theoretically analyze this factor. ORCA alleviates the
variance imbalance by controlling the supervised learning of labeled data, so
that the intra-class variances of seen classes can be similar to that of novel
classes. Consequently, such a solution may suppress the performance on seen
classes (Cf. ORCA-ZM vs. ORCA in Table III). In contrast, our method targets
to effectively learn both seen and novel classes.

###  II-B Open-World Semi-Supervised Learning Related Tasks

Open-world SSL is related to but distinct from several open-world learning
tasks, including open-set recognition (OSR) [35, 36, 37], robust semi-
supervised learning (robust SSL) [38, 39, 40, 41], novel class discovery (NCD)
[42, 43, 44, 8], and zero-shot learning (ZSL) [45, 46, 47]. To distinguish
between them, we divide them into three categories — $C$+1 classification,
$\bar{C}$ classification, and $C$+$\bar{C}$ classification (Cf. Table I).

OSR and robust SSL are $C$+1 classification tasks, where they regard instances
of novel classes as OOD instances and perform $C$+1 classification to group
the OOD instances into one single class. Specially, OSR considers inductive
setting, while robust SSL considers transductive setting. NCD is a $\bar{C}$
classification task, as it classifies the OOD instances into multiple novel
classes but assumes that the unlabeled data only involves novel classes. Both
open-world SSL and ZSL are $C$+$\bar{C}$ classification tasks. However, ZSL
requires prior knowledge like semantic attributes of classes, so that it can
learn mappings between samples and the prior class semantic information for
prediction. A recent approach called Zero-Knowledge ZSL (ZK-ZSL) [48] does not
use semantic attributes of novel classes, while it still requires the prior
knowledge of seen classes. Compared to ZSL, open-world SSL is more flexible
because it does not make any assumption about the prior knowledge of any
class. Notably, $C$+1 classification methods can be adjusted for open-world
SSL by post-clustering the detected OOD instances. Additionally, $\bar{C}$
classification methods can be adjusted for open-world SSL by aligning some of
the discovered novel classes with previously seen classes. However, these
extensions have been demonstrated to not perform well [14, 20, 34], indicating
the necessity of specific methods for open-world SSL.

###  II-C Open-World Node Classification

Open-world node classification is an emerging task in the graph community.
Existing efforts primarily perform under the setting of $C$+1 classification
[8, 9, 10, 11, 13, 49]. For example, OODGAT [9] and OpenWGL [8] treat nodes of
novel classes as OOD instances and assign them into a single class. In
addition, open-world active learning has been explored on graph data [50],
while it requires iterative human annotation. Different from previous work,
this paper considers a more practical setting (i.e., open-world SSL), in which
the OOD nodes will be grouped into multiple novel classes without human-in-
the-loop. Notably, a concurrent work devises an open-world SSL algorithm
called RIGNN [51] for graph classification. However, it can not be used to
solve the node classification problem. To our knowledge, this paper is a
pioneer work to explore open-world SSL for node classification and
theoretically analyze factors that affect open-world SSL.

Previous open-world SSL methods are primarily studied in the field of computer
vision and thus often benefit from general pre-trained vision encoders. Due to
an absence of general pre-trained graph encoders, these methods are sub-
optimal when extended to graph data (Cf. Section V). Concretely, open-world
SSL for vision data [15, 14, 33, 17] typically leverages a pre-trained vision
encoder, such as a pre-trained ResNet [22] and a pre-trained Vision
Transformer [23], to initialize the feature encoder. The pre-trained encoders
provide semantically meaningful initial representations, naturally
facilitating discriminative representations for instances of both seen and
novel classes. Nevertheless, there is an absence of general pre-trained graph
encoders because different types of graphs have distinct data distributions
(e.g., a social network and a biological network exhibit very different data
properties). Although pre-trained GNNs like GCC [24] and Graphormer [25] have
been proposed, they typically conduct pre-training and fine-tuning/prompting
on the same or similar types of graphs, thus limiting their practical
applications. Therefore, in the absence of general pre-trained graph encoders,
it is worth exploring more effective open-world SSL methods to train the node
classification models from scratch.

TABLE I: Comparison between popular settings of open-world learning. $C$ denotes the number of seen classes, and $\bar{C}$ denotes the number of novel classes. Settings |  Seen Classes | Novel Classes
---|---|---
$\bar{C}$ Classification  |  Not Classify  | Classify
$C$+1 Classification  |  Classify  | Not Classify
$C$+$\bar{C}$ Classification  |  Classify  | Classify

##  III Preliminary

###  III-A Problem Definition

Let $G=\left(\mathcal{V},\mathcal{E},\mathcal{X}\right)$ be a graph, where
$\mathcal{V}$ is the set of nodes, $\mathcal{E}$ is the set of edges, and
$\mathcal{X}$ is the set of initial node features. $\mathcal{V}$ can be
divided into two distinct sets: a labeled set $\mathcal{V}_{l}$ and an
unlabeled set $\mathcal{V}_{u}$. We denote the set of classes associated with
the nodes in $\mathcal{V}_{l}$ as $\mathcal{C}_{l}$ (i.e., the set of seen
classes) and the set of classes associated with the nodes in $\mathcal{V}_{u}$
as $\mathcal{C}_{u}$. In the open-world SSL problem,
$\mathcal{C}_{l}\neq\mathcal{C}_{u}$ and
$\mathcal{C}_{l}\cap\mathcal{C}_{u}\neq\emptyset$. The set of novel classes is
$\mathcal{C}_{n}=\mathcal{C}_{u}\backslash\mathcal{C}_{l}$.

###### Problem 1

Open-World SSL for Node Classification. Given a partially labeled graph
$G=\left(\mathcal{V}_{l},\mathcal{V}_{u},\mathcal{E},\mathcal{X},\mathcal{Y}_{l}\right)$,
where
$\mathcal{Y}_{l}=\\{y_{i}|v_{i}\in\mathcal{V}_{l},y_{i}\in\mathcal{C}_{l}\\}$
is the set of manual labels. We abbreviate “class label” as “label”. Let
$\mathcal{Y}_{u}=\\{y_{i}|v_{i}\in\mathcal{V}_{u},y_{i}\in\mathcal{C}_{u}\\}$
be the labels of $\mathcal{V}_{u}$, the goal is to learn a function

$\mathcal{F}:{G}=\left(\mathcal{V}_{l},\mathcal{V}_{u},\mathcal{E},\mathcal{X},\mathcal{Y}_{l}\right)\rightarrow\mathcal{Y}_{u}$
(1)

End-to-End Solution vs. Two-Stage Solution.  Existing efforts on open-world
SSL can be categorized into end-to-end methods [34, 20, 33, 17] and two-stage
methods [14, 16]. The former jointly optimizes a feature encoder and a
classification head in an end-to-end manner, where the cross-entropy and an
clustering objective [20, 34, 44] are used together for model optimization.
Due to supervised losses, end-to-end methods tend to over-fit seen classes,
thereby needing well-designed regularizations and/or powerful pre-trained
feature encoders for alleviation [20, 34, 33, 17]. Conversely, two-stage
methods [14, 16] decouple representation learning and prediction, where they
use non-parametric algorithms to cluster instances based on well-learned
representations, and then align clusters with classes to obtain final
prediction. The two-stage methods have been demonstrated to reduce the bias.
Inspired by this, we will follow the two-stage design.

###  III-B Calculation of Imbalance Rate and Separation Rate

Here we introduce how to calculate the imbalance rate and separation rate
between seen and novel classes. Given all the node representations of a class,
we calculate the mean and standard deviation of these representations. Given a
seen class and a novel class, as well as their values of mean and standard
deviation ($std$), we calculate the imbalance/separation rate by

$imbalance\\_rate=\frac{\text{max}\left(std_{seen},std_{novel}\right)}{\text{min}\left(std_{seen},std_{novel}\right)}$
(2)

$separation\\_rate=\frac{||mean_{seen}-mean_{novel}||_{2}}{std_{seen}+std_{novel}}$
(3)

The final imbalance rate and separation rate are averaged over all seen-novel
class pairs.

##  IV Methodology

Based on intuitions from a theoretical model, we propose OpenIMA to perform
open-world SSL for node classification.

###  IV-A Theoretical Motivation

Variance imbalance (i.e., seen classes exhibit smaller intra-class variances
than novel classes in the embedding space) is a potential key factor in
affecting open-world SSL for node classification. Here we theoretically
analyze how the variance imbalance affects model performance. In specific, we
consider $N$ data samples from a seen class and a novel class, and perform
K-Means clustering. Particularly, we assume the cluster IDs and class IDs are
aligned, so that the cluster labels can be used for classification. In the
theoretical model, the data-generation distribution $P_{XY}$ is a uniform
mixture of two spherical Gaussian distributions. Please note $X$ here does not
denote initial node features but denotes data samples in a latent feature
space. The class label $Y$ is either 1 or 2 with equal probability. Condition
on $Y=1$, $X|Y\sim\mathcal{N}(\bm{\mu}_{1},\Sigma_{1})$, and $Y=2$,
$X|Y\sim\mathcal{N}(\bm{\mu}_{2},\Sigma_{2})$. Formally, K-Means ($K$=2)
assigns each data sample to the nearest cluster by

$\hat{y}=\arg\min\limits_{j}||\bm{x}-\bm{\theta}_{j}||_{2},j\in\\{1,2\\}$ (4)

where $\bm{x}$ denotes a data sample, $\hat{y}$ denotes the predicted cluster
label, and $\bm{\theta}_{j}$ denotes the center of the $j$-th cluster. As we
assume that the cluster IDs and class IDs are aligned, we can use $\hat{y}$ to
denote the predicted class label. The cluster center is iteratively updated by
the average of the data samples assigned to the cluster. It is straightforward
to verify that the expectation of the converged cluster centers output by
K-Means will be $\bm{\theta}_{j}=\mathbb{E}[X|\hat{Y}=j]$, and the expectation
of clustering accuracy on each cluster will be
$ACC_{j}=\mathbb{E}[\mathbbm{1}(\hat{Y}=j)|Y=j]$.

Let $\sigma_{j}^{2}$ denote the largest eigenvalue of $\Sigma_{j}$, i.e.,
$\sigma_{j}^{2}={\lambda_{max}(\Sigma_{j})}$. A large value of
$\sigma_{j}^{2}$ indicates that the corresponding class has a large intra-
class variance. We define the variance imbalance rate between the given two
classes as $\gamma=\max(\sigma_{1},\sigma_{2})/\min(\sigma_{1},\sigma_{2})$.
Intuitively, as $\sigma_{1}$ and $\sigma_{2}$ are key parameters of $P_{XY}$,
$\gamma$ could affect the clustering accuracy. In particular, if the latent
classes are separated with nearly no overlap, the cluster boundaries are easy
to find, and thus K-Means can correctly partition data samples with high
possibility regardless of the imbalance rate. We model this by the following
theorem and prove it in Section VI.

###### Definition 1

Given two spherical Gaussian distributions
$\mathcal{N}(\bm{\mu}_{1},\Sigma_{1})$ and
$\mathcal{N}(\bm{\mu}_{2},\Sigma_{2})$, they are $\alpha$-separated if

$||\bm{\mu}_{1}-\bm{\mu}_{2}||_{2}=\alpha(\sqrt{\lambda_{max}(\Sigma_{1})}+\sqrt{\lambda_{max}(\Sigma_{2}))})=\alpha\left(\sigma_{1}+\sigma_{2}\right)$

where $\alpha$ can be represented by
$||\bm{\mu}_{1}-\bm{\mu}_{2}||_{2}/\left(\sigma_{1}+\sigma_{2}\right)$, so a
large $\alpha$ indicates that the two distributions are highly separated.

Assume that $\mathcal{N}(\bm{\mu}_{1},\Sigma_{1})$ and
$\mathcal{N}(\bm{\mu}_{2},\Sigma_{2})$ are $\alpha$-separated. Without loss of
generality, suppose that $\sigma_{1}<\sigma_{2}$, we have:

###### Theorem 1

With $1<\gamma<2$, for any $\delta$, there exists a constant $\overline{N}$,
if the number of samples $N\geq\overline{N}$, with a possibility at least
1-$\delta$,
(1) if $1.5<\alpha<3$, $ACC_{2}$ and $\sigma_{1}$ a.s. are positively
correlated;
(2) if $\alpha>3$, $|1-ACC_{1}|<0.05$ and $|1-ACC_{2}|<0.05$.

Interpretations.  Let $\sigma_{1}$ be the intra-class variance of the seen
class, and $\sigma_{2}$ be that of the novel class, we have
$\sigma_{1}<\sigma_{2}$. The theorem illustrates two facts.

  * •

Increasing the imbalance rate can suppress the clustering accuracy on the
novel class. According to the first point of Theorem 1, the decrease of
$\sigma_{1}$ will lead to a decrease of $ACC_{2}$, while the imbalance rate
$\gamma=\max(\sigma_{1},\sigma_{2})/\min(\sigma_{1},\sigma_{2})=\sigma_{2}/\sigma_{1}$
will increase with the decrease of $\sigma_{1}$. Therefore, a negative
correlation exists between $ACC_{2}$ and $\gamma$. In other words, increasing
the imbalance rate can adversely affect the clustering accuracy on the novel
class.

  * •

If seen and novel classes are well-separated in the embedding space,
clustering accuracy on each class is hard to be affected by the imbalance
rate. Concretely, when the seen class is effectively learned and can be
clearly distinguished from the novel class, we can say that the two classes
are $\alpha$-separated, with $\alpha$ taking a large value. Based on the
second point of Theorem 1, the imbalance rate hardly affects the clustering
results if $\alpha$ is large enough.

Motivation.  Based on the above theoretical analysis, a model trained from
scratch is desired to (1) reduce the intra-class variances of novel classes to
get a lower imbalance rate, and (2) thoroughly learn the seen classes,
encouraging their separation from novel classes.

###  IV-B Overview of OpenIMA

Given a graph
$G=\left(\mathcal{V}_{l},\mathcal{V}_{u},\mathcal{E},\mathcal{X},\mathcal{Y}_{l}\right)$,
the inference of OpenIMA contains the following three steps:

  * •

Node embedding. A GNN encoder like GAT [52] encodes node representations
$\mathcal{Z}_{l}=\\{\bm{z}_{i}\in\mathbb{R}^{d}|v_{i}\in\mathcal{V}_{l}\\}$
for labeled nodes and
$\mathcal{Z}_{u}=\\{\bm{z}_{i}\in\mathbb{R}^{d}|v_{i}\in\mathcal{V}_{u}\\}$
for unlabeled nodes.

  * •

Clustering. The classic algorithm K-Means [32] is applied to cluster nodes
based on their representations $\mathcal{Z}_{l}\cup\mathcal{Z}_{u}$, where the
number of clusters is set to be $|\mathcal{C}_{l}|+|\mathcal{C}_{n}|$. In
fact, other clustering algorithms [53, 54, 55, 56] can also be employed.

  * •

Cluster-Class Alignment and Node Classification. We run the Hungarian optimal
assignment algorithm [57] on the set of labeled nodes to find the optimal
alignment between classes and clusters. Let $\mathcal{M}$ be the set of
possible cluster-to-class mapping functions, the optimal alignment is found by

$m^{*}=\arg\max\limits_{m\in\mathcal{M}}\sum_{v_{i}\in\mathcal{V}_{l}}\mathbbm{1}\left\\{y_{i}=m\left(o_{i}\right)\right\\}$
(5)

where $\mathbbm{1}$ is an indicator function which takes value of 1 if
$y_{i}=m\left(o_{i}\right)$ and 0 otherwise. $o_{i}$ and $y_{i}$ are the
cluster label and class label of the $i$-th node in $\mathcal{V}_{l}$,
respectively. With the optimal alignment $m^{*}$, we can predict class labels
for the unlabeled nodes via
$\hat{\mathcal{Y}}_{u}=m^{*}\left(\mathcal{O}_{u}\right)=\\{m^{*}\left(o_{i}\right)|v_{i}\in\mathcal{V}_{u}\\}$.
In particular, the clusters involve both seen and novel classes, so the number
of clusters is more than that of seen classes, and thus a portion of cluster
IDs will not be aligned.

###  IV-C Objective Function

To optimize the GNN encoder, we employ the simple and effective cross-entropy
(CE) to learn the valuable manual labels, and perform Contrastive Learning
with Bias-reduced Pseudo labels (BPCL) to suppress the intra-class variances
of novel classes and better separate seen classes from novel classes.

$\mathcal{L}_{\text{OpenIMA}}=\mathcal{L}_{\text{BPCL}}+\eta\mathcal{L}_{\text{CE}}$
(6)

where $\eta$ is a scaling factor. Because we use the CE to optimize the GNN
encoder, we introduce a classification head on top of the GNN encoder to
derive logits for computing the CE loss.

The most popular method of pseudo-labeling is to train a classifier in a
supervised/semi-supervised manner for pseudo label generation [58, 59, 60, 33,
34, 21, 15]. However, only seen classes have manual labels, so the classifier
tends to be biased towards seen classes (Cf. evaluation of OpenLDN/SimGCD in
Table III).

Bias-Reduced Pseudo Label Generation.  In order to mitigate the above problem,
we turn to unsupervised clustering, which is free from manual labels.
Specifically, we run an unsupervised clustering algorithm over node
representations $\mathcal{Z}_{l}\cup\mathcal{Z}_{u}$ to obtain cluster
predictions $\mathcal{O}_{l}$ for labeled nodes and $\mathcal{O}_{u}$ for
unlabeled nodes, where the number of clusters is
$|\mathcal{C}_{l}|+|\mathcal{C}_{n}|$. Intuitively, samples near the cluster
centers are more likely to be correctly predicted. Hence we define the
prediction confidence of node $v_{i}$ to be inversely proportional to
$||\bm{z}_{i}-\bm{\theta}_{o_{i}}||_{2}$, where $o_{i}$ is the predicted
cluster label of the node $v_{i}$, and $\bm{\theta}_{o_{i}}$ is the
corresponding cluster center. According to the confidence values, we sort
$\mathcal{O}_{l}\cup\mathcal{O}_{u}$ in descending order and select the top
$\rho\%$ of them as the reliable ones to alleviate erroneous training. As a
portion of samples have been manually labeled, we only supplement pseudo
labels $\mathcal{O}_{u}^{s}\subset\mathcal{O}_{u}$ for unlabeled nodes that
exist in the top-$\rho\%$ set. With the optimal cluster-to-class alignment
$m^{*}$, we derive the final pseudo labels
$\hat{\mathcal{Y}}_{u}^{s}=m^{*}\left(\mathcal{O}_{u}^{s}\right)$. In this
paper, we use the classic K-Means clustering. Other clustering algorithms [53,
54, 55, 56] can also be employed.

Learning with Bias-Reduced Pseudo Labels.  As cluster IDs are unordered, we
need to align clusters and classes, so that we can use the manual labels and
pseudo labels together. However, different from the closed-world setting [61],
the cluster IDs corresponding to novel classes can not be aligned, making some
class IDs remain unordered. Fortunately, contrastive learning (CL) can deal
with unordered class IDs, as it captures semantic knowledge by learning
whether two samples come from the same class rather than assigning samples to
specific classes like cross-entropy. Hence the presence of unordered class IDs
will not hinder the pseudo label-enhanced learning. In specific, we design the
following CL scheme with our bias-reduced pseudo labels.

Embedding-level CL. Given $N_{b}$ randomly sampled nodes to form a mini-batch,
we perform data augmentation on each sample twice to obtain positive pairs,
and thus a batch contains $2N_{b}$ data points. Let $\left(i,j\right)$ be the
indices of a positive pair within the batch, we minimize the following
objective,

$\small\mathcal{L}_{\text{BPCL}}^{emb}=-\frac{1}{2N_{b}}\sum_{i=1}^{2N_{b}}\frac{1}{|\mathcal{P}(i)|}\sum_{j\in\mathcal{P}(i)}\log\frac{\exp\left(\bm{z}_{i}^{\top}\cdot\bm{z}_{j}/\tau\right)}{\sum_{k=1}^{2N_{b}}\mathbbm{1}_{[k\neq
i]}\exp\left(\bm{z}_{i}^{\top}\cdot\bm{z}_{k}/\tau\right)}$ (7)

where $\bm{z}_{i}$ denotes the $\mathcal{\ell}_{2}$-normalized representation
of the $i$-th data point in the batch, $\mathbbm{1}_{[k\neq i]}$ is the
indicator function which takes value of 1 if $k\neq i$ and 0 otherwise, and
$\tau$ is the temperature parameter. Following SimCSE [62], we pass the same
input to the feature encoder twice. By using the standard dropout [63] twice,
we can obtain the representations $\bm{z}_{i}$ and $\bm{z}_{j}$ as a “positive
pair”. Within the batch, $\mathcal{P}(i)$ denotes the indices of the $i$-th
data point’s positive samples. The positive samples share the same class label
with the $i$-th data point. Notably, Eq. 7 and SupCon [31] have the same form.
However, different from the fully supervised SupCon, BPCL defines positive
pairs based on both manual labels and pseudo labels. Specially for nodes
without manual and pseudo labels, Eq. 7 can be viewed as the InfoNCE loss
because $|\mathcal{P}(i)|=1$.

Logit-level CL. We observe that combining CE loss can benefit the
effectiveness of BPCL (Cf. Section V-C). The CE loss is computed based logits
output by the classification head. To better optimize the classification head,
we propose to utilize the abundant pseudo labels of the unlabeled nodes.
Considering that cross-entropy can not deal with the unordered class IDs of
novel classes, we design the following logit-level objective,

$\small\mathcal{L}_{\text{BPCL}}^{logits}=-\frac{1}{2N_{b}}\sum_{i=1}^{2N_{b}}\frac{1}{|\mathcal{P}(i)|}\sum_{j\in\mathcal{P}(i)}\log\frac{\exp\left(\bm{e}_{i}^{\top}\cdot\bm{e}_{j}/\tau\right)}{\sum_{k=1}^{2N_{b}}\mathbbm{1}_{[k\neq
i]}\exp\left(\bm{e}_{i}^{\top}\cdot\bm{e}_{k}/\tau\right)}$ (8)

where $\bm{e}_{i}=\text{l2\\_norm}\left(W^{\top}\bm{z}_{i}\right)$ is the
$\mathcal{\ell}_{2}$-normalized logits of the $i$-th data point in the batch,
and $W$ is the weight matrix of the classification head (i.e., a linear
layer).

Finally, BPCL loss combines the above two CL objectives,

$\mathcal{L}_{\text{BPCL}}=\mathcal{L}_{\text{BPCL}}^{emb}+\mathcal{L}_{\text{BPCL}}^{logits}$
(9)

Discussions.  Unlike some previous open-world SSL methods that adopt
contrastive learning [14, 20, 15, 16, 17], OpenIMA employs contrastive
learning with the aim of better leveraging the bias-reduced pseudo labels.
Without the help of general pre-trained graph encoders, we mitigate the
variance imbalance issue by learning with high-quality pseudo labels.
Considering that our generated pseudo labels are bias-reduced but involve
unordered class IDs, we employ contrastive learning to prevent unordered class
IDs from hindering the learning process. Please note that our goal is not to
innovate a CL scheme but to propose an effective method for open-world SSL on
a graph.

Complexity Analysis of OpenIMA.  We denote the dimension of node
representations as $d$, the number of nodes in a graph as $N$, the number of
labeled nodes as $M$, the batch size as $N_{b}$, the number of clusters as
$K$, and the number of iterations in K-Means as $T$. The time complexity can
be divided into five parts: (1) The time complexity of CE-based supervised
learning is $\mathcal{O}(MdK)$; (2) The time complexity of BPCL is
$\mathcal{O}(NdN_{b})$; (3) The time complexity of K-Means is
$\mathcal{O}(TNdK)$. Acceleration of K-Means has been widely studied [64, 65,
66], which helps extend OpenIMA to large graphs.; (4) The time complexity of
Hungarian algorithm is $\mathcal{O}(M^{3})$. If the size of labeled nodes is
large, we can sample a subset of labeled nodes for computation; (5) The time
complexity of selecting reliable pseudo labels is $\mathcal{O}(NlogN)$ as we
need run a sorting algorithm. Considering that $N_{b}$, $d$, $K$, $T$ and $M$
are relatively small, the complexity of OpenIMA is approximately about
$O(NlogN)$.

##  V Experiments

###  V-A Experimental Settings

Datasets.  The used datasets include two citation networks Citeseer [1] and
ogbn-Arxiv [67], three co-purchase networks Amazon Photos [29], Amazon
Computers [29], and ogbn-Products [67], and two coauthor networks Coauthor CS
[29] and Coauthor Physics [29]. Statistics of them are in Table II.

TABLE II: Statistics of the used datasets Graph | #Nodes | #Edges | #Features | #Classes
---|---|---|---|---
Citeseer | 3,327 | 4,676 | 3,703 | 6
Amazon Photos | 7,650 | 119,082 | 745 | 8
Amazon Computers | 13,752 | 245,861 | 767 | 10
Coauthor CS | 18,333 | 818,94 | 6,805 | 15
Coauthor Physics | 34,493 | 247,962 | 8,415 | 5
ogbn-Arxiv | 169,343 | 1,166,243 | 128 | 40
ogbn-Products | 2,449,029 | 61,859,140 | 100 | 47

For each graph, we randomly select 50% of classes as seen classes, and use the
remaining classes as novel classes. For each seen class, we randomly sample 50
nodes (500 nodes for the larger datasets ogbn-Arxiv and ogbn-Products) to form
the training set and another 50 nodes (500 nodes for ogbn-Arxiv and ogbn-
Products) to form the validation set. The remaining nodes are assigned to the
test set. We use ten random seeds to derive ten train/validation/test splits
for each graph.

Baselines.  We compare with two kinds of baselines. First, we compare with
open-world node classification algorithms, showing that existing open-world
node classification models which perform $C$+1 node classification are not
suitable for extending to the open-world SSL setting. In specific, we compare
with the typical algorithms — OODGAT [9] and OpenWGL [8], where we cluster the
detected out-of-distribution (OOD) nodes with K-Means to identify multiple
novel classes.

Second, open-world SSL baselines are compared to show that they are sub-
optimal for extending to the node classification, as they are originally
proposed for vision data and often benefit from the powerful pre-trained
feature encoder. Particularly, we replace the vision encoder with the graph
encoder GAT [52]. The end-to-end open-world SSL baselines include:

  * •

ORCA [20], which designs an uncertainty adaptive margin mechanism to control
the supervised learning of labeled data, so that intra-class variances of seen
classes can be similar to that of novel classes, thus reducing the variance
imbalance.

  * •

ORCA-ZM [20], which removes the margin mechanism from ORCA (i.e., ORCA with
Zero Margin).

  * •

SimGCD [15], which trains a classifier with self-distillation and entropy
regularization.

  * •

OpenLDN [34], which trains a classifier with well-designed regularizer to
generate pseudo labels, and learns the pseudo-labeled data using the standard
cross-entropy loss.

  * •

OpenCon [33], which trains a classifier to assign pseudo labels to the OOD
samples and learns the pseudo labels of samples of novel classes via CL.

The two-stage open-world SSL baselines run K-Means over node representations,
and align clusters with classes for node classification. The losses for
representation learning include:

  * •

InfoNCE [30], which adopts the unsupervised CL loss InfoNCE to learn both
labeled and unlabeled data.

  * •

InfoNCE+SupCon, which additionally adds the supervised CL loss SupCon [31] to
learn labeled data.

  * •

InfoNCE+SupCon+CE, which further adds cross-entropy loss to enhance the
learning of seen classes.

Notably, a semi-supervised K-Means algorithm is designed in GCD [14], which
forces samples of the same class to be clustered together. However, if a class
has diverse node representations, such an operation could group samples of
different classes together [68]. We find that K-Means performs better than the
semi-supervised K-Means on the used datasets, so we adopt the classic and
effective K-Means for clustering.

Evaluation Metric.  We adopt the widely used clustering accuracy [14, 34, 20,
44] for evaluation. Given the ground-truth class labels and the predicted
cluster labels of the test nodes, we run the Hungarian algorithm to align the
class IDs and cluster IDs. After that, we can calculate the overall accuracy.
Following GCD [14], we run the Hungarian assignment only once across all
classes, and calculate the resultant accuracy on seen and novel classes,
respectively. We repeat all the experiments ten times with ten different
train/validation/test splits, and the reported accuracy is averaged over the
ten runs.

TABLE III: Overall evaluation by test accuracy (%). † indicates the $C$+1 node classification is extended to solve the open-world SSL setting by clustering the detected OOD nodes. ‡ denotes the two-stage variant of the original method. The bold numbers represent the best results, and the underlined numbers represent the second best results. |  Citeseer |  Amazon Photos |  Amazon Computers |  Coauthor CS |  Coauthor Physics
---|---|---|---|---|---
| All | Seen |  Novel  | All | Seen |  Novel  | All | Seen |  Novel  | All | Seen |  Novel  | All | Seen | Novel
OODGAT† | 46.4 | 56.9 |  37.5  | 63.0 | 71.1 |  54.5  | 61.3 | 63.3 |  55.9  | 68.1 | 68.8 |  65.6  | 68.3 | 69.4 | 62.5
OpenWGL† | 62.4 | 71.0 |  54.2  | 71.8 | 74.8 |  69.3  | 57.6 | 65.9 |  44.6  | 58.6 | 67.1 |  50.3  | 73.3 | 85.0 | 68.1
ORCA-ZM | 58.3 | 72.8 |  44.4  | 74.6 | 89.9 |  58.2  | 63.8 | 73.7 |  52.6  | 75.0 | 74.2 |  73.5  | 64.7 | 81.1 | 55.9
ORCA | 58.2 | 68.0 |  49.0  | 76.2 | 87.1 |  64.9  | 60.9 | 67.8 |  53.7  | 73.9 | 81.6 |  68.3  | 66.2 | 84.8 | 58.2
SimGCD | 61.5 | 70.6 |  53.4  | 80.5 | 90.0 |  70.8  | 61.9 | 73.8 |  50.3  | 71.2 | 84.2 |  61.2  | 60.9 | 81.1 | 52.8
OpenLDN | 62.3 | 73.9 |  51.6  | 80.9 | 90.6 |  71.9  | 63.3 | 76.5 |  51.8  | 68.4 | 80.6 |  60.3  | 62.2 | 72.4 | 57.2
OpenCon | 68.8 | 75.0 |  62.1  | 82.6 | 92.1 |  72.8  | 62.3 | 74.9 |  51.2  | 73.5 | 83.4 |  67.5  | 65.8 | 95.0 | 55.4
OpenCon‡ | 66.7 | 73.7 |  60.0  | 82.9 | 87.9 |  78.1  | 59.4 | 69.0 |  53.2  | 71.0 | 81.9 |  64.8  | 62.6 | 83.8 | 54.4
InfoNCE | 68.1 | 70.7 |  65.2  | 76.3 | 78.5 |  75.1  | 56.1 | 51.3 |  59.1  | 72.2 | 72.8 |  72.7  | 60.6 | 58.1 | 60.2
InfoNCE+SupCon | 68.1 | 71.9 |  64.1  | 75.6 | 80.3 |  72.0  | 56.3 | 52.5 |  58.9  | 72.4 | 75.1 |  71.0  | 60.5 | 59.7 | 59.8
InfoNCE+SupCon+CE | 68.1 | 73.6 |  62.6  | 76.4 | 80.5 |  72.9  | 55.8 | 54.7 |  56.5  | 74.4 | 77.1 |  73.0  | 62.8 | 79.4 | 56.1
OpenIMA | 68.1 | 71.8 |  64.3  | 83.6 | 89.9 |  77.3  | 67.8 | 77.8 |  59.0  | 77.1 | 78.3 |  75.9  | 78.0 | 93.6 | 72.2

Parameter Settings.  Detailed settings are introduced in Section VII. Here we
introduce the metric for hyper-parameter selection. For the closed-world
problems, accuracy on the validation set is widely used for hyper-parameter
selection. However, in the open-world SSL problem, relying on the validation
accuracy can make models biased to seen classes because the validation set is
composed of only seen classes. Recently, OpenCon [33] designs a validation
strategy that splits the labeled classes into two parts, i.e., “seen classes”
and “novel classes”, to construct a virtual open-world SSL task. The best
hyper-parameters are then selected according to performance on the constructed
task. However, the data distribution of the virtual task may significantly
differ from that of the real-world scenario. Moreover, it is hard to construct
an effective validation task if the number of labeled classes is small.

Therefore, we devise a metric called SC&ACC for hyper-parameter selection
under the open-world SSL setting, involving two popular metrics — Silhouette
Coefficient (SC) [69] and Clustering Accuracy (ACC). SC is a clustering metric
that measures the clustering quality based on the representations and the
predicted cluster labels. SC&ACC takes into account model performance on both
seen and novel classes, thus alleviating the bias towards seen classes. As the
open-world SSL is a transductive problem where unlabeled data is available
during training, we calculate ACC on the validation set and SC on the union of
validation and test sets. Under different combinations of hyper-parameters, we
derive different (SC, ACC) value pairs. We normalize the values of SC via min-
max normalization and also perform min-max normalization for values of ACC.
Then, for each combination of hyper-parameters, we take the weighted sum of
the normalized SC and the normalized ACC (the weight takes value 0.5) to
obtain the value of SC&ACC.

###  V-B Overall Evaluation

From Table III and Table IV, we observe that: (1) Existing open-world node
classification methods are not suitable for extending to the open-world SSL
setting. OpenIMA outperforms OODGAT† and OpenWGL† on all the datastes. (2)
Existing open-world SSL methods are sub-optimal when extended to the node
classification setting. Without powerful pre-trained feature encoders, the
open-world SSL baselines can not guarantee good performance on both seen and
novel classes. (3) OpenIMA can alleviate the variance imbalance issue.
Compared to InfoNCE which guides unbiased learning, OpenIMA not only achieves
higher accuracy on seen classes but also derives better/comparable performance
on novel classes. (4) OpenIMA better mitigates the variance imbalance issue
compared to ORCA. ORCA-ZM can outperform ORCA on seen classes, implying that
controlling the learning of seen classes could suppress the learning quality.
In contrast, OpenIMA can achieve good performance on both seen and novel
classes. (5) The proposed bias-reduced pseudo-labeling is effective. Compared
to OpenLDN, SimGCD, and OpenCon, which train a classifier in a semi-supervised
manner for pseudo-labeling, OpenIMA better balances the performance on seen
and novel classes to derive better overall accuracy. Particularly, SimGCD and
OpenCon can perform well on vision datasets with the assistance of powerful
pre-trained vision encoders [15, 33]. (6) Representations learned by the end-
to-end methods are insufficient. We run K-Means over node representations
learned by the competitive baseline OpenCon (denoted as OpenCon‡). However,
such a two-stage variant reduces overall accuracy on most of the datasets. (7)
OpenIMA also performs well on larger datasets. We use mini batch-based K-Means
[66] for the larger datasets. Consequently, the clustering quality could be
affected. Hence we refine OpenIMA for larger datasets via 1) predicting with
the classification head and 2) adding a widely used pair-wise loss [20] to
mitigate the over-fitting of seen classes. As shown in Table IV, OpenIMA still
obtains the best overall accuracy compared with the competitive baselines.

TABLE IV: Evaluation on larger datasets by test accuracy (%). |  ogbn-Arxiv (169,343 nodes) |  ogbn-Products (2,449,029 nodes)
---|---|---
| All | Seen |  Novel  | All | Seen | Novel
ORCA-ZM  | 41.6 | 47.0 |  31.6  | 49.5 | 61.5 | 32.3
ORCA  | 41.6 | 44.7 |  34.6  | 46.8 | 55.5 | 34.3
OpenCon  | 32.2 | 31.8 |  31.6  | 43.7 | 46.0 | 43.0
OpenIMA | 43.6 | 49.2 |  32.9  | 62.0 | 73.6 | 44.3
TABLE V: Ablation studies by overall test accuracy (%). $\mathcal{L}_{\text{BPCL}}^{emb}$ | $\mathcal{L}_{\text{BPCL}}^{logit}$ |  $\mathcal{L}_{\text{CE}}$ |  Citeseer |  Amazon Photos |  Amazon Computers |  Coauthor CS |  Coauthor Physics
---|---|---|---|---|---|---|---
✗ | ✗ |  ✓  |  49.5  |  60.1  |  60.1  |  65.9  | 49.3
✓ | ✓ |  ✗  |  67.8  |  80.8  |  55.8  |  76.0  | 58.8
✗ | ✓ |  ✗  |  67.2  |  79.7  |  56.5  |  73.4  | 54.6
✗ | ✓ |  ✓  |  67.0  |  81.9  |  67.7  |  75.8  | 82.5
✓ | ✗ |  ✗  |  68.7  |  80.6  |  55.7  |  77.0  | 59.1
✓ | ✗ |  ✓  |  69.0 |  82.8  |  66.4  |  78.1 | 64.0
✓ | ✓ |  ✓  |  68.1  |  83.6 |  67.8 |  77.1  | 78.0
Ours w/o PL  |  67.2  |  77.2  |  57.3  |  71.6  | 64.1

###  V-C Ablation Studies

We analyze components of $\mathcal{L}_{\text{OpenIMA}}$ according to Table V.
(1) $\text{BPCL}_{logit}$+$\text{BPCL}_{emb}$ performs better than CE on most
datasets because a large number of unlabeled data is not learned by CE. (2)
$\text{BPCL}_{logit}$+CE performs better than $\text{BPCL}_{logit}$ on four
out of five datasets, and $\text{BPCL}_{emb}$+CE performs better than
$\text{BPCL}_{emb}$ on all the datasets, indicating that CE contributes to the
BPCL. (3) CE contributes most on Amazon Computers and Coauthor CS, and
$\text{BPCL}_{logit}$+CE performs better than $\text{BPCL}_{emb}$+CE on the
two datasets. CE loss is computed based on the classification head. That is to
say, if it is highly necessary to well optimize the classification head,
logit-level BPCL takes effect as it brings rich information from the unlabeled
data to enhance the learning of the classification head. (4)
$\text{BPCL}_{logit}$+CE sometimes performs better than
$\text{BPCL}_{emb}$+CE, while $\text{BPCL}_{emb}$+CE sometimes performs better
$\text{BPCL}_{logit}$+CE. OpenIMA combines CE, $\text{BPCL}_{emb}$, and
$\text{BPCL}_{logit}$ to derive satisfied performance across all the datasets.
(5) Removing bias-reduced pesudo-labeling from OpenIMA (i.e., ours w/o PL)
decreases the model performance, demonstrating the effectiveness of our
pseudo-labeling method.

Figure 2: Effects of hyper-parameters $\eta$ and $\rho$. TABLE VI: Overall evaluation by test accuracy without knowing the real number of novel classes (%). |  Citeseer |  Amazon Photos |  Amazon Computers |  Coauthor CS |  Coauthor Physics
---|---|---|---|---|---
| All | Seen |  Novel  | All | Seen |  Novel  | All | Seen |  Novel  | All | Seen |  Novel  | All | Seen | Novel
ORCA-ZM | 52.2 | 70.1 |  35.1  | 69.3 | 84.4 |  52.6  | 66.0 | 74.3 |  57.6  | 74.8 | 74.8 |  72.9  | 69.7 | 63.6 | 67.5
ORCA | 52.8 | 65.6 |  40.2  | 71.8 | 82.2 |  59.0  | 64.4 | 75.1 |  52.1  | 72.9 | 75.6 |  70.3  | 70.9 | 70.4 | 67.1
OpenCon | 53.4 | 68.8 |  39.3  | 80.9 | 92.2 |  70.3  | 64.5 | 80.4 |  51.9  | 76.4 | 88.8 |  66.9  | 58.3 | 94.9 | 44.0
OpenIMA | 67.6 | 73.8 |  60.4  | 74.7 | 77.8 |  67.4  | 67.0 | 72.9 |  58.2  | 80.2 | 78.9 |  80.0  | 74.4 | 72.1 | 73.9
TABLE VII: Evaluation of hyper-parameter search metrics on Amazon Photos (%). We report the absolute accuracy gap between seen and novel classes in the last column. Method |  Metric | Test Accuracy
---|---|---
|  | All | Seen | Novel | Gap
ORCA-ZM |  SC  | 54.4 | 67.3 | 39.0 | 28.3
|  ACC  | 71.4 | 86.5 | 54.9 | 31.6
|  SC&ACC  | 74.6 | 89.9 | 58.2 | 31.7
ORCA |  SC  | 41.4 | 44.7 | 33.9 | 10.8
|  ACC  | 73.3 | 85.8 | 60.3 | 25.5
|  SC&ACC  | 76.2 | 87.1 | 64.9 | 22.2
SimGCD |  SC  | 79.6 | 87.7 | 71.9 | 15.8
|  ACC  | 79.5 | 92.1 | 66.1 | 26.0
|  SC&ACC  | 80.5 | 90.0 | 70.8 | 19.2
OpenLDN |  SC  | 48.6 | 48.9 | 46.0 | 2.9
|  ACC  | 71.6 | 88.4 | 52.3 | 36.1
|  SC&ACC  | 80.9 | 90.6 | 71.9 | 18.7
OpenCon |  SC  | 83.6 | 90.8 | 76.0 | 14.8
|  ACC  | 82.0 | 92.3 | 72.0 | 20.3
|  SC&ACC  | 82.6 | 92.1 | 72.8 | 19.3
OpenCon‡ |  SC  | 80.4 | 85.7 | 74.9 | 10.8
|  ACC  | 81.2 | 91.5 | 71.8 | 19.7
|  SC&ACC  | 82.9 | 87.9 | 78.1 | 9.8
InfoNCE |  SC  | 77.0 | 77.1 | 77.5 | 0.4
|  ACC  | 75.4 | 78.5 | 73.4 | 5.1
|  SC&ACC  | 76.3 | 78.5 | 75.1 | 3.4
InfoNCE+SupCon |  SC  | 77.2 | 77.5 | 77.3 | 0.2
|  ACC  | 75.5 | 79.7 | 72.4 | 7.3
|  SC&ACC  | 75.6 | 80.3 | 72.0 | 8.3
InfoNCE+SupCon+CE |  SC  | 77.6 | 78.5 | 77.2 | 1.3
|  ACC  | 75.5 | 79.7 | 71.8 | 7.9
|  SC&ACC  | 76.4 | 80.5 | 72.9 | 7.6
OpenIMA  |  SC  | 83.3 | 89.3 | 77.1 | 12.2
|  ACC  | 82.1 | 90.6 | 73.4 | 17.2
|  SC&ACC  | 83.6 | 89.9 | 77.3 | 12.6

###  V-D Effects of Hyper-Parameters

Taking Coauthor CS/Physics as the examples, Figure 2 shows how the scaling
factor and pseudo label selection rate impact the test accuracy of OpenIMA.
(1) Scaling factor $\eta$. On Coauthor CS, the accuracy on seen classes
increases as the $\eta$ increases. However, a large $\eta$ tends to suppress
the accuracy on novel classes due to the over-fitting of seen classes.
Notably, for Coauthor Physics, a larger $\eta$ leads to a significant gain in
accuracy on seen classes (over 30%), which suggests that the label information
might be seriously underutilized if using a small $\eta$. Therefore, for the
Coauthor Physics, using a larger $\eta$ improves performance on both seen and
novel classes. (2) Pseudo-label selection rate $\rho$. On Coauthor CS,
properly increasing the number of pseudo labels can benefit model performance
on both seen and novel classes. However, too many pseudo labels can induce
more noise to suppress the model performance. Particularly on Coauthor
Physics, supplementing pseudo labels inhibits the model performance on seen
classes. This is because the seen classes have been well learned with a small
number of pseudo labels (achieving over 90% accuracy on seen classes with
$\rho=25$). Hence increasing $\rho$ can amplify the negative impact of noisy
pseudo labels of seen classes.

###  V-E Investigation of Number of Novel Classes

In this section, we discuss how to deal with the situation, in which the
number of novel classes is unknown. If we have sufficient validation data, we
can follow existing efforts [14] to estimate the number of novel classes
according to clustering accuracy on the validation set before model training.
However, each seen class could have limited label information in practice.
Therefore, we treat the number of novel classes as a hyper-parameter. In this
paper, before model training, we run K-Means over node representations learned
by InfoNCE, and roughly estimate the number of novel classes according to the
silhouette coefficient metric. For each of the used datasest, we find that the
roughly estimated number of novel classes is less than 10. Hence we set the
number of novel classes to range from 1 to 10, and determine the value of the
hyper-parameter according to the SC&ACC metric. In Table VI, we compare
OpenIMA with the most competitive baselines, including ORCA, ORCA-ZM, and
OpenCon. The results show that OpenIMA still performs the best on most of the
datasets. This is an exploration of the unknown number of novel classes. We
will further investigate how to determine the number in our future work.

###  V-F Evaluation of Hyper-Parameter Search Metrics

Taking Amazon Photos as the example, we compare different metrics for hyper-
parameter search in Table VII, and make the following observations. (1)
Searching based on ACC (validation accuracy) tends to result in a larger
accuracy gap between seen and novel classes, indicating that the resultant
models are biased towards seen classes. (2) The effectiveness of SC
(silhouette coefficient) or ACC varies across different methods. ORCA-ZM,
ORCA, and OpenLDN prefer ACC, while InfoNCE, InfoNCE+SupCon, and
InfoNCE+SupCon+CE favor SC. In contrast, SC&ACC has a more stable performance
across various methods and datasets, better contributing to the evaluations of
the open-world SSL models. Similar observations can be found on other
datasets.

##  VI Proof

###  VI-A Proof Skeleton

In this section, we target to prove Theorem 1. We use bold lowercase letters
to represent vectors, regular lowercase letters to represent scalars, and
regular uppercase letters to denote matrices. To simplify the problem, we
first show that we can transform the K-Means clustering over $d$-dimension
data (generated from a uniform mixture of spherical Gaussian distributions
$\mathcal{N}\left(\bm{\mu_{1}},\Sigma_{1}\right)$ and
$\mathcal{N}\left(\bm{\mu_{2}},\Sigma_{2}\right)$) to the K-Means clustering
over 1-dimension data (generated from the uniform mixture of
$\mathcal{N}\left(\mu_{1},\sigma_{1}\right)$ and
$\mathcal{N}\left(\mu_{2},\sigma_{2}\right)$) without loss of generality. Then
we bridge the accuracy $\\{ACC_{1},ACC_{2}\\}$ and the distribution parameters
$\\{\mu_{1},\mu_{2},\sigma_{1},\sigma_{2}\\}$ to prove Theorem 1.

To do this, we introduce a partition threshold $s$ and a function
$h\left(s,\mu_{1},\mu_{2},\sigma_{1},\sigma_{2}\right)=2s-\theta_{1}-\theta_{2}$.
Here $\theta_{1}$ and $\theta_{2}$ are cluster centers found by K-Means based
on the partition threshold $s$. Therefore, $\theta_{1}$ and $\theta_{2}$ can
be represented by $\mu_{1},\mu_{2},\sigma_{1},\sigma_{2}$, and $s$. If
$(\theta_{1}+\theta_{2})/2$ exactly equals $s$, the cluster centers will not
change in the subsequent iterations of K-Means. In other words, the optimal
partition threshold $s^{*}$ is the solution of
$h\left(s,\mu_{1},\mu_{2},\sigma_{1},\sigma_{2}\right)=0$. To prove the first
point of Theorem 1, we prove that $s^{*}$ and $\sigma_{1}$ have a negative
correlation, and $ACC_{2}$ is negatively correlated with $s^{*}$. Hence we can
derive that $ACC_{2}$ is positively correlated to $\sigma_{1}$. To prove the
second point of Theorem 1, we calculate value ranges of $ACC_{1}$ and
$ACC_{2}$ based on value ranges of $s^{*}$, $\alpha$, and $\gamma$.

###  VI-B Proof of the First Point of Theorem 1

Given any $d$-dimension vectors $\bm{\mu_{1}}$ and $\bm{\mu_{2}}$, there
exists a rotation matrix $R$ and a bias $\bm{b}$ that can transform
$\bm{\mu_{1}}$ and $\bm{\mu_{2}}$ to the first dimension, i.e.,

$\footnotesize
R\bm{\mu_{1}}+\bm{b}=\left(\mu_{1},0,...,0\right),R\bm{\mu_{2}}+\bm{b}=\left(\mu_{2},0,...,0\right)$
(10)

Since K-Means clustering is based on the Euclidean distance metric, the
clustering result will keep the same if all samples are rotated and moved with
$R$ and $\bm{b}$. Hence we can assume that the distribution $P_{XY}$ is
symmetry about the first dimension, i.e.,
$\bm{\mu_{1}}=\left(\mu_{1},0,...,0\right),\bm{\mu_{2}}=\left(\mu_{2},0,...,0\right)$.
Here we assume that $\mu_{1}<\mu_{2}$ and $\mu_{1}=0$. For spherical Gaussian
distributions, we can denote $\Sigma_{1}$ and $\Sigma_{2}$ by
$\Sigma_{1}=\textbf{I}\sigma_{1}^{2},\Sigma_{2}=\textbf{I}\sigma_{2}^{2}$.
Without loss of generality, we assume that $\sigma_{1}<\sigma_{2}$.

A typical method of initializing cluster centers is to average the randomly
selected samples. Since data samples are from $P_{XY}$, and $P_{XY}$ is
symmetry about the first dimension, the expectations of initial cluster
centers are on the first dimension, and the expectations of the cluster
centers predicted by each iteration of K-Means are also on the first
dimension. Therefore, the expectations of final optimal cluster centers also
locate on the first dimension, represented by
$\bm{\theta_{1}}^{*}=\left(\theta_{1}^{*},0,...,0\right),\bm{\theta_{2}}^{*}=\left(\theta_{2}^{*},0,...,0\right)$.
Up to now, we have transformed the K-Means on a $d$-dimension distribution to
the K-Means on a 1-dimension distribution without loss of generality.

Suppose we have a $d$-dimensional variable
$\left(x_{1},x_{2},...,x_{d}\right)$. According to the property of marginal
distribution in multivariate spherical Gaussian distribution, the probability
density function of $x_{1}$ is
$\mathbbm{P}\left(x_{1}=t\right)=\frac{1}{2}\mathbbm{P}\left[\mathcal{N}\left(\mu_{1},\sigma_{1}\right)=t\right]+\frac{1}{2}\mathbbm{P}\left[\mathcal{N}\left({\mu_{2}},\sigma_{2}\right)=t\right]$.
Given the partition threshold $s$ found by K-Means, we can calculate the
expectation of current cluster center
$\bm{\theta_{1}}=\left(\theta_{1},0,...,0\right)$ by

$\displaystyle\theta_{1}$
$\displaystyle=\mathbbm{E}\left[x_{1}|x_{1}<s\right]=\frac{\mathbbm{E}\left[x_{1}\mathbbm{1}\left(x_{1}<s\right)\right]}{\mathbbm{P}\left(x_{1}<s\right)}$
(11)
$\displaystyle=\frac{\frac{1}{2}\mathbbm{E}_{x_{1}\sim\mathcal{N}\left(\mu_{1},\sigma_{1}\right)}\left[x_{1}|x_{1}<s\right]+\frac{1}{2}\mathbbm{E}_{x_{1}\sim\mathcal{N}\left(\mu_{2},\sigma_{2}\right)}\left[x_{1}|x_{1}<s\right]}{\frac{1}{2}\mathbbm{P}_{x_{1}\sim\mathcal{N}\left(\mu_{1},\sigma_{1}\right)}\left(x_{1}<s\right)+\frac{1}{2}\mathbbm{P}_{x_{1}\sim\mathcal{N}\left(\mu_{2},\sigma_{2}\right)}\left(x_{1}<s\right)}$

Let $\Phi\left(x\right)$ and $\varphi\left(x\right)$ be the cumulative
distribution function (cdf) and probability density function (pdf) of the
standard normal distribution, respectively, we have

$\footnotesize\mathbbm{P}_{x_{1}\sim\mathcal{N}\left(\mu_{1},\sigma_{1}\right)}\left(x_{1}<s\right)=\Phi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)$
(12)
$\footnotesize\mathbbm{P}_{x_{1}\sim\mathcal{N}\left(\mu_{2},\sigma_{2}\right)}\left(x_{1}<s\right)=\Phi\left(\frac{s-\mu_{2}}{\sigma_{2}}\right)$
(13)

According to Lemma 1 in Section VI-D, we have

$\footnotesize\mathbbm{E}_{x_{1}\sim\mathcal{N}\left(\mu_{1},\sigma_{1}\right)}\left[x_{1}|x_{1}<s\right]=\mu_{1}\Phi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)-\sigma_{1}\varphi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)$
(14)
$\footnotesize\mathbbm{E}_{x_{1}\sim\mathcal{N}\left(\mu_{2},\sigma_{2}\right)}\left[x_{1}|x_{1}<s\right]=\mu_{2}\Phi\left(\frac{s-\mu_{2}}{\sigma_{2}}\right)-\sigma_{2}\varphi\left(\frac{s-\mu_{2}}{\sigma_{2}}\right)$
(15)

Substituting the above equations into Eq. 11, we can derive

$\footnotesize\theta_{1}=\frac{\mu_{1}\Phi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)-\sigma_{1}\varphi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)+\mu_{2}\Phi\left(\frac{s-\mu_{2}}{\sigma_{2}}\right)-\sigma_{2}\varphi\left(\frac{s-\mu_{2}}{\sigma_{2}}\right)}{\Phi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)+\Phi\left(\frac{s-\mu_{2}}{\sigma_{2}}\right)}$
(16)

Similarly, we can derive

$\footnotesize\theta_{2}=\frac{\mu_{1}-\mu_{1}\Phi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)+\sigma_{1}\varphi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)+\mu_{2}-\mu_{2}\Phi\left(\frac{s-\mu_{2}}{\sigma_{2}}\right)+\sigma_{2}\varphi\left(\frac{s-\mu_{2}}{\sigma_{2}}\right)}{1-\Phi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)+1-\Phi\left(\frac{s-\mu_{2}}{\sigma_{2}}\right)}$
(17)

According to Eq. 16 and Eq. 17, as $\theta_{1}$ and $\theta_{2}$ can be
represented by $\mu_{1},\mu_{2},\sigma_{1},\sigma_{2}$, and $s$, we define a
function
$h\left(s,\sigma_{1},\sigma_{2},\mu_{1},\mu_{2}\right)=2s-\theta_{1}-\theta_{2}$.
Notably, $\theta_{1}$ and $\theta_{2}$ are determined based on the current
$s$. If $s$ exactly equals $(\theta_{1}+\theta_{2})/2$, the cluster centers
will not change in the subsequent iterations of K-Means. In other words, the
optimal partition threshold $s^{*}$ found by K-Means is the solution of
$h\left(s,\sigma_{1},\sigma_{2},\mu_{1},\mu_{2}\right)=0$.

Now we target to discuss the monotonicity of functions $h\left(s\right)$ and
$h\left(\sigma_{1}\right)$, aiming to explore the correlation between
$\sigma_{1}$ and $ACC_{2}$. Before calculating the derivatives, we restrict
$s$ into a smaller interval to simplify our proof. As proved in previous
studies, the optimal cluster centers found by K-Means can be very close to the
ground-truth cluster centers [70], that is

$\footnotesize|\theta^{*}_{1}-\mu_{1}|<\epsilon,|\theta^{*}_{2}-\mu_{2}|<\epsilon$
(18)

where $\epsilon$ is a rather small value (compared to
$\mu_{2}-\mu_{1},\sigma_{1},\sigma_{2}$). Thus, we have

$\footnotesize|s^{*}-\frac{\mu_{1}+\mu_{2}}{2}|=|\frac{\theta_{1}^{*}+\theta_{2}^{*}}{2}-\frac{\mu_{1}+\mu_{2}}{2}|\leq\frac{|\theta_{1}^{*}-\mu_{1}|}{2}+\frac{|\theta_{2}^{*}-\mu_{2}|}{2}<\epsilon$
(19)

That is to say,
$s^{*}\in\left[\frac{\mu_{1}+\mu_{2}}{2}-\epsilon,\frac{\mu_{1}+\mu_{2}}{2}+\epsilon\right]$.
We will prove that $h\left(s\right)$ is a strictly monotone increasing
function within the interval
$\left[\frac{\mu_{1}+\mu_{2}}{2}-\epsilon,\frac{\mu_{1}+\mu_{2}}{2}+\epsilon\right]$.

For the second part of $h\left(s\right)$, we calculate the derivative

$\displaystyle\frac{\partial\theta_{1}}{\partial s}$
$\displaystyle=\frac{\frac{\mu_{2}-\mu_{1}}{\sigma_{2}}\varphi\left(\frac{s-\mu_{2}}{\sigma_{2}}\right)\Phi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)-\frac{\mu_{2}-\mu_{1}}{\sigma_{1}}\varphi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)\Phi\left(\frac{s-\mu_{2}}{\sigma_{2}}\right)}{\left(\Phi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)+\Phi\left(\frac{s-\mu_{2}}{\sigma_{2}}\right)\right)^{2}}$
(20)
$\displaystyle\quad+\frac{\frac{s-\mu_{1}}{\sigma_{1}}\varphi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)+\frac{s-\mu_{2}}{\sigma_{2}}\varphi\left(\frac{s-\mu_{2}}{\sigma_{2}}\right)}{\Phi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)+\Phi\left(\frac{s-\mu_{2}}{\sigma_{2}}\right)}$
$\displaystyle\quad+\frac{\left(\sigma_{1}\varphi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)+\sigma_{2}\varphi\left(\frac{s-\mu_{2}}{\sigma_{2}}\right)\right)\left(\frac{\varphi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)}{\sigma_{1}}+\frac{\varphi\left(\frac{s-\mu_{2}}{\sigma_{2}}\right)}{\sigma_{2}}\right)}{\left(\Phi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)+\Phi\left(\frac{s-\mu_{2}}{\sigma_{2}}\right)\right)^{2}}$

With the restriction of $\alpha$-separated (Cf. Definition 1), we have
$||\bm{\mu_{1}}-\bm{\mu_{2}}||_{2}=\alpha\left(\sigma_{1}+\sigma_{2}\right)$.
Since we have assumed that $\mu_{2}>\mu_{1}$, we can derive

$\footnotesize\mu_{2}-\mu_{1}=\alpha\left(\sigma_{1}+\sigma_{2}\right)=\alpha\left(1+\gamma\right)\sigma_{1}=\alpha\left(1+1/\gamma\right)\sigma_{2}$
(21)

As $1.5<\alpha<3,1<\gamma<2$, we have

$\footnotesize
3\times\left(1+1\right)>\frac{\mu_{2}-\mu_{1}}{\sigma_{2}}=\alpha\left(1+1/\gamma\right)>1.5\times\left(1+0.5\right)=2.25$
(22) $\footnotesize
3\times\left(1+2\right)>\frac{\mu_{2}-\mu_{1}}{\sigma_{1}}=\alpha\left(1+\gamma\right)>1.5\times\left(1+2\right)=3$
(23)

Then, we can obtain the inequalities below,

$\displaystyle\varphi\left(\frac{s-\mu_{2}}{\sigma_{2}}\right)$
$\displaystyle<\varphi\left(\frac{\left(\frac{\mu_{1}+\mu_{2}}{2}+\epsilon\right)-\mu_{2}}{\sigma_{2}}\right)$
(24)
$\displaystyle=\varphi\left(\frac{\mu_{2}-\mu_{1}}{2\sigma_{2}}-\frac{\epsilon}{\sigma_{2}}\right)<\varphi\left(1.1\right)$
$\displaystyle\varphi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)$
$\displaystyle<\varphi\left(\frac{\left(\frac{\mu_{1}+\mu_{2}}{2}-\epsilon\right)-\mu_{1}}{\sigma_{1}}\right)$
(25)
$\displaystyle=\varphi\left(\frac{\mu_{2}-\mu_{1}}{2\sigma_{1}}-\frac{\epsilon}{\sigma_{1}}\right)<\varphi\left(1.45\right)$
$\footnotesize\Phi\left(1.5\right)<\Phi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)<\Phi\left(3\right),\Phi\left(\frac{s-\mu_{2}}{\sigma_{2}}\right)<1-\Phi\left(1.1\right)$
(26)

According to the pdf values and cdf values of the standard normal
distribution, for the first part of Eq. 20, we have

$\displaystyle\frac{\frac{\mu_{2}-\mu_{1}}{\sigma_{2}}\varphi\left(\frac{s-\mu_{2}}{\sigma_{2}}\right)\Phi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)-\frac{\mu_{2}-\mu_{1}}{\sigma_{1}}\varphi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)\Phi\left(\frac{s-\mu_{2}}{\sigma_{2}}\right)}{\left(\Phi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)+\Phi\left(\frac{s-\mu_{2}}{\sigma_{2}}\right)\right)^{2}}<0.8$
(27)

For the second part of Eq. 20, we have222As the left side of Eq. 28 is not a
monotonic function, we use numerical simulation to determine the threshold.

$\displaystyle\frac{\frac{s-\mu_{1}}{\sigma_{1}}\varphi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)+\frac{s-\mu_{2}}{\sigma_{2}}\varphi\left(\frac{s-\mu_{2}}{\sigma_{2}}\right)}{\Phi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)+\Phi\left(\frac{s-\mu_{2}}{\sigma_{2}}\right)}<0.1$
(28)

For the third part of Eq. 20, we have

$\displaystyle\frac{\left(\sigma_{1}\varphi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)+\sigma_{2}\varphi\left(\frac{s-\mu_{2}}{\sigma_{2}}\right)\right)\left(\frac{\varphi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)}{\sigma_{1}}+\frac{\varphi\left(\frac{s-\mu_{2}}{\sigma_{2}}\right)}{\sigma_{2}}\right)}{\left(\Phi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)+\Phi\left(\frac{s-\mu_{2}}{\sigma_{2}}\right)\right)^{2}}<0.1$
(29)

Summing up the above inequalities, we derive
$\frac{\partial\theta_{1}}{\partial s}<1$, where $\mu_{1}<\mu_{2}$, and
$\sigma_{1}<\sigma_{2}$. As the relative size relationship between
$\sigma_{1}$ and $\sigma_{2}$ does not affect the above proof, and
$-\mu_{1}>-\mu_{2}$, we have $\frac{\partial-\theta_{2}}{\partial-s}<1$, and
thus we can derive $\frac{\partial\theta_{2}}{\partial s}<1$. Therefore, we
have

$\footnotesize\frac{\partial h\left(s\right)}{\partial
s}=2-\frac{\partial\theta_{1}}{\partial s}-\frac{\partial\theta_{2}}{\partial
s}>2-1-1=0$ (30)

Up to now, we have proved that $h\left(s\right)$ is strictly monotone
increasing within
$\left[\frac{\mu_{1}+\mu_{2}}{2}-\epsilon,\frac{\mu_{1}+\mu_{2}}{2}+\epsilon\right]$.

Next, we discuss the monotonicity of $h\left(\sigma_{1}\right)$ by calculating
the derivative below,

$\footnotesize\frac{\partial
h\left(\sigma_{1}\right)}{\partial\sigma_{1}}=-\frac{\partial\theta_{1}}{\partial\sigma_{1}}-\frac{\partial\theta_{2}}{\partial\sigma_{1}}$
(31)

We have assumed that $\mu_{1}=0$, so that we can derive

$\displaystyle-\frac{\partial\theta_{1}}{\partial\sigma_{1}}$
$\displaystyle=\frac{\left(1+\frac{\left(s-\mu_{1}\right)^{2}}{\sigma_{1}^{2}}\right)\varphi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)\left(\Phi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)+\Phi\left(\frac{s-\mu_{2}}{\sigma_{2}}\right)\right)}{\left(\Phi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)+\Phi\left(\frac{s-\mu_{2}}{\sigma_{2}}\right)\right)^{2}}$
(32)
$\displaystyle+\frac{\left[\sigma_{1}\varphi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)-\mu_{2}\Phi\left(\frac{s-\mu_{2}}{\sigma_{2}}\right)+\sigma_{2}\varphi\left(\frac{s-\mu_{2}}{\sigma_{2}}\right)\right]\frac{s-\mu_{1}}{\sigma_{1}^{2}}\varphi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)}{\left(\Phi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)+\Phi\left(\frac{s-\mu_{2}}{\sigma_{2}}\right)\right)^{2}}$

The denominator of Eq. 32 is positive. For the only negative term in the
numerator of Eq. 32, we can obtain that

$\displaystyle\mu_{2}\Phi\left(\frac{s-\mu_{2}}{\sigma_{2}}\right)\frac{s-\mu_{1}}{\sigma_{1}^{2}}\varphi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)$
(33)
$\displaystyle=\left(\mu_{2}-\mu_{1}\right)\Phi\left(\frac{s-\mu_{2}}{\sigma_{2}}\right)\frac{s-\mu_{1}}{\sigma_{1}^{2}}\varphi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)$
$\displaystyle<\frac{1}{2}\left(\mu_{2}-\mu_{1}\right)\frac{s-\mu_{1}}{\sigma_{1}^{2}}\varphi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)\left(\Phi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)+\Phi\left(\frac{s-\mu_{2}}{\sigma_{2}}\right)\right)$
$\displaystyle<\left(1+\frac{\left(s-\mu_{1}\right)^{2}}{\sigma_{1}^{2}}\right)\varphi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)\left(\Phi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)+\Phi\left(\frac{s-\mu_{2}}{\sigma_{2}}\right)\right)$

That is to say, the only negative term in the numerator is smaller than one of
the positive term in the numerator. Therefore, we have
$-\frac{\partial\theta_{1}}{\partial\sigma_{1}}>0$. $\theta_{1}$ and
$\theta_{2}$ are determined by the K-Means algorithm. Notably, we have
transformed to conduct the K-Means on a 1-dimension distribution, and assume
that $\mu_{1}<\mu_{2}$. As the partition threshold $s$ increases, $\theta_{2}$
will increase, and $\theta_{1}$ will also increase because more larger
instances are assigned to the first cluster. As $s$ decreases, $\theta_{1}$
will decrease, and $\theta_{2}$ will also decrease because more smaller
instances are assigned to the second cluster. In other words, $\theta_{1}$ and
$\theta_{2}$ are positively correlated. Hence we derive that
$-\frac{\partial\theta_{2}}{\partial\sigma_{1}}>0$, and thus we have
$\frac{\partial h\left(\sigma_{1}\right)}{\partial\sigma_{1}}>0$, i.e.,
$h\left(\sigma_{1}\right)$ is strictly monotone increasing.

We have proved that both $h\left(s\right)$ and $h\left(\sigma_{1}\right)$ are
strictly monotone increasing functions. Now we aim to discuss the correlation
between $\sigma_{1}$ and $ACC_{2}$ based on the above proved conclusions.
Firstly, we formulate $ACC_{2}$ as follows,

$\displaystyle ACC_{2}=$
$\displaystyle\mathbbm{E}\left[\mathbbm{1}\left(\hat{Y}=2\right)|Y=2\right]=\mathbbm{E}\left[\mathbbm{1}\left(x_{1}>s\right)|Y=2\right]$
(34) $\displaystyle=$
$\displaystyle\mathbbm{P}_{x_{1}\sim\mathcal{N}\left(\mu_{2},\sigma_{2}\right)}\left(x_{1}>s\right)=1-\Phi\left(\frac{s-\mu_{2}}{\sigma_{2}}\right)$

We prove $ACC_{2}$ and $\sigma_{1}$ a.s. are positively correlated by:

  * •

Given two candidate values $\sigma_{1}^{\prime}$ and
$\sigma_{1}^{\prime\prime}$ for $\sigma_{1}$, suppose that
$\sigma_{1}^{\prime}<\sigma_{1}^{\prime\prime}$, we have
$h_{\sigma_{1}^{\prime}}\left(s\right)<h_{\sigma_{1}^{\prime\prime}}\left(s\right)$
because $h\left(\sigma_{1}\right)$ is strictly monotone increasing.

  * •

Suppose that $s^{*\prime}$ is the solution of
$h_{\sigma_{1}^{\prime}}\left(s\right)=0$, and $s^{*\prime\prime}$ is the
solution for $h_{\sigma_{1}^{\prime\prime}}\left(s\right)=0$, we have
$h_{\sigma_{1}^{\prime\prime}}\left(s^{*\prime}\right)>h_{\sigma_{1}^{\prime}}\left(s^{*\prime}\right)=h_{\sigma_{1}^{\prime\prime}}\left(s^{*\prime\prime}\right)=0$.
Considering that $h\left(s\right)$ is a strictly monotone increasing function,
we have $s^{*\prime}>s^{*\prime\prime}$. Thus, if
$\sigma_{1}^{\prime}<\sigma_{1}^{\prime\prime}$, we have
$s^{*\prime}>s^{*\prime\prime}$. In other words, $s^{*}$ and $\sigma_{1}$ have
a negative correlation.

  * •

Substituting $s^{*\prime}$ and $s^{*\prime\prime}$ into Eq. 34
($s^{*\prime}>s^{*\prime\prime}$), we have
$1-\Phi\left(\frac{s^{*\prime}-\mu_{2}}{\sigma_{2}}\right)<1-\Phi\left(\frac{s^{*\prime\prime}-\mu_{2}}{\sigma_{2}}\right)$.
That is to say, $ACC_{2}$ and $s^{*}$ also has a negative correlation.

  * •

As we have proved (1) $s^{*}$ and $\sigma_{1}$ have a negative correlation,
and (2) $ACC_{2}$ and $s^{*}$ also have a negative correlation, we finally
prove that $ACC_{2}$ is positively correlated to $\sigma_{1}$.

According to the law of large numbers and Chebyshev inequality, if we perform
sampling a large number of times, i.e., generating a large amount of data
samples according to $P_{XY}$, the calculated results should be very close to
the expectations. Therefore, there exits a constant $\overline{N}$, if the
number of data samples $N\geq\overline{N}$, with a possibility at least
1-$\delta$, $ACC_{2}$ and $\sigma_{1}$ a.s. have a positive correlation.

###  VI-C Proof of the Second Point of Theorem 1

As mentioned before, the optimal cluster centers found by K-Means are very
close to the ground-truth cluster centers [70], so we can derive
$s^{*}\in\left[\frac{\mu_{1}+\mu_{2}}{2}-\epsilon,\frac{\mu_{1}+\mu_{2}}{2}+\epsilon\right]$
according to Eq. 18 and Eq. 19. Here we relax the value range to be
$s^{*}\in\left[\frac{\mu_{1}+\mu_{2}}{2}-\frac{\sigma_{1}}{2},\frac{\mu_{1}+\mu_{2}}{2}+\frac{\sigma_{2}}{2}\right]$.
Based on the relaxed range of $s^{*}$ and the restriction that $\alpha>3$, we
have

$\displaystyle ACC_{1}$
$\displaystyle=\Phi\left(\frac{s-\mu_{1}}{\sigma_{1}}\right)>\Phi\left(\frac{\frac{\mu_{1}+\mu_{2}-\sigma_{1}}{2}-\mu_{1}}{\sigma_{1}}\right)=\Phi\left(\frac{\mu_{2}-\mu_{1}}{2\sigma_{1}}-\frac{1}{2}\right)$
(35)
$\displaystyle=\Phi\left(\frac{\alpha\left(1+\gamma\right)-1}{2}\right)>\Phi\left(2.5\right)>0.99$
$\displaystyle ACC_{2}$
$\displaystyle=1-\Phi\left(\frac{s-\mu_{2}}{\sigma_{2}}\right)>1-\Phi\left(\frac{\frac{\mu_{1}+\mu_{2}+\sigma_{2}}{2}-\mu_{2}}{\sigma_{2}}\right)$
(36)
$\displaystyle=1-\Phi\left(\frac{\mu_{1}-\mu_{2}}{2\sigma_{2}}+\frac{1}{2}\right)$
$\displaystyle=\Phi\left(\frac{\alpha\left(1+1/\gamma\right)-1}{2}\right)>\Phi\left(1.75\right)>0.95$

Thus, we derive $|1-ACC_{1}|<0.05$ and $|1-ACC_{2}|<0.05$.

###  VI-D Lemma 1 and Its Proof

###### Lemma 1

For $X\sim\mathcal{N}\left(\mu,\sigma^{2}\right)$, the expectation of
truncated normal distribution is

$\footnotesize\mathbbm{E}_{x\sim\mathcal{N}\left(\mu,\sigma^{2}\right)}\left[x|a<x<b\right]=\mu\left[\Phi\left(\beta\right)-\Phi\left(\alpha\right)\right]-\sigma\left[\varphi\left(\beta\right)-\varphi\left(\alpha\right)\right]$
(37)

where $\alpha=\frac{a-\mu}{\sigma}$ and $\beta=\frac{b-\mu}{\sigma}$.

Proof: Converting the expectation into integral form to have

$\displaystyle\mathbbm{E}_{x\sim\mathcal{N}\left(\mu,\sigma\right)}\left[x|a<x<b\right]=\int_{a}^{b}\frac{x}{\sqrt{2\pi}\sigma}e^{-\frac{\left(x-\mu\right)^{2}}{2\sigma^{2}}}dx$
(38)
$\displaystyle=\int^{\frac{b-\mu}{\sigma}}_{\frac{a-\mu}{\sigma}}\frac{\left(\sigma
z+\mu\right)}{\sqrt{2\pi}}e^{-\frac{z^{2}}{2}}dz$
$\displaystyle=\frac{\sigma}{\sqrt{2\pi}}\int^{\frac{b-\mu}{\sigma}}_{\frac{a-\mu}{\sigma}}ze^{-\frac{z^{2}}{2}}dz+\mu\int^{\frac{b-\mu}{\sigma}}_{\frac{a-\mu}{\sigma}}\frac{e^{-\frac{z^{2}}{2}}}{\sqrt{2\pi}}dz$
$\displaystyle=-\sigma\frac{e^{-\frac{z^{2}}{2}}}{\sqrt{2\pi}}\bigg{|}^{\frac{b-\mu}{\sigma}}_{\frac{a-\mu}{\sigma}}+\mu\left[\Phi\left(\frac{b-\mu}{\sigma}\right)-\Phi\left(\frac{a-\mu}{\sigma}\right)\right]$
$\displaystyle=\mu\left[\Phi\left(\beta\right)-\Phi\left(\alpha\right)\right]-\sigma\left[\varphi\left(\beta\right)-\varphi\left(\alpha\right)\right]$

##  VII Detailed Experimental Settings

For all models, we use the graph attention network GAT [52] as the feature
encoder and the Adam optimizer with weight decay 1e-4 for optimization. We set
the number of GAT layers to 2, the hidden dimension to 128, the number of
attention heads to 8, and the dropout rate [63] to 0.5. Due to the dropout
strategy, we follow SimCSE [62] to pass the same input to the encoder twice to
obtain the positive pairs for CL.

Settings of maximal training epochs and batch size. We set the maximal
training epochs (max_epoch) to 100 for end-to-end models and 20 for two-stage
models. Specially, we set the max_epoch to 50 for ORCA, ORCA-ZM, and SimGCD,
as we find that max_epoch=50 would be better for the three baselines. For
ogbn-Products that has millions of nodes, a model can converge within a
smaller number of training epochs because the dataset can be partitioned into
more mini-batches during a training epoch. Therefore, we set max_epoch to 10
for all methods on ogbn-Products. For methods that adopt mini-batch training,
we set the batch size to 2048 (4096 on the larger datasets ogbn-Arxiv and
ogbn-Products).

Settings of model-specific parameters. For the baselines, their specific
hyper-parameters are set to the empirical values given by the authors. For
OpenIMA, we set the scaling factor $\eta$ to 1, the temperature parameter
$\tau$ to 0.7, and the pseudo-label selection rate $\rho\left(\%\right)$ to 75
by default. Specially, we observe that properly increasing the value of $\eta$
can significantly boost the validation accuracy on Amazon Computers and
Coauthor Physics (accuracy gains on the validation sets $>$ 15%). Hence we
search $\eta\in\\{10,20\\}$ for the two datasets. On Amazon Photos, we find
that the end-to-end baselines tend to perform better than the two-stage
baselines in overall accuracy. That is to say, the classification head plays
an important role on Amazon Photos, so we also search $\eta\in\\{10,20\\}$ for
this dataset. On Amazon Photos, Amazon Computers, and Coauthor Physics,
increasing $\eta$ benefits the model performance, making the pseudo labels
more reliable (especially for pseudo labels of seen classes), so we use a
smaller temperature parameter $\tau=0.07$ to obtain more confident contrastive
predictions. Besides, we observe that the validation accuracy on Citeseer and
ogbn-Arxiv is noticeably lower than that on other datasets, indicating a
higher learning difficulty on the two datasets. Hence we lower $\rho(\%)$ to
25 on Citeseer and ogbn-Arxiv to reduce the noisy pseudo labels.

Settings of learning rate. We observe that the optimal learning rates of end-
to-end models tend to be different on the same dataset, so we search the
learning rate for each end-to-end model. The CL-based two-stage models (i.e.,
InfoNCE, InfoNCE+SupCon, InfoNCE+SupCon+CE, and OpenIMA) share the similar
learning scheme, and we observe that they tend to share the same optimal
learning rate on the same dataset. Intuitively, if instances have rich initial
features, it could be easier for CL to capture the semantic relationships
between them, and thus a smaller learning rate is preferred for a stable
convergence. According to this, we set the default learning rate of the two-
stage CL-based models to 1e-4 on Coauthor CS and Coauthor Physics, 1e-3 on
Citeseer, Amazon Photos, and Amazon Computers, and 1e-2 on ogbn-Arxiv and
ogbn-Products. As a larger $\eta$ is used on Amazon Photos, Amazon Computers,
and Coauthor Physics, the gradient produced by CE will be strengthened, so we
increase the learning rate of OpenIMA by an order of magnitude on the three
datasets to strengthen the gradients contributed by BPCL. On Coauthor Physics,
we set the learning rate to 1e-2 for the CL-based two-stage baselines. We test
other settings of learning rate for all the CL-based two-stage baselines and
find that the above setting is the optimal choice.

##  VIII Conclusion

This work is one pioneer study of open-world SSL for node classification. Due
to an absence of general pre-trained graph encoders, it is challenging to
simultaneously learn effective node representations for both labeled seen
classes and unlabeled novel classes, resulting in an imbalance of intra-class
variances between seen and novel classes. Based on the empirical and
theoretical analysis, we propose a simple and effective method named OpenIMA,
which alleviates the variance imbalance issue without relying on general pre-
trained graph encoders. Extensive experiments on the widely used graph
datasets show the effectiveness of OpenIMA. We hope this effort could be
inspiring for future work on open-world graph learning.

## Acknowledgment

This work is supported by the National Key Research & Develop Plan
(2023YFF0725100) and the National Natural Science Foundation of China
(62322214, U23A20299, 62076245, 62072460, 62172424, 62276270). This work is
supported by the Australian Research Council under the streams of Future
Fellowship (Grant No.FT210100624) and the Discovery Project (Grant
No.DP240101108). We also acknowledge the support from the Public Computing
Cloud, Renmin University of China. We sincerely thank the reviewers for their
valuable comments.

## References

  * [1] T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” in _ICLR_ , 2017.
  * [2] W. L. Hamilton, Z. Ying, and J. Leskovec, “Inductive representation learning on large graphs,” in _NeurIPS_ , 2017, pp. 1024–1034.
  * [3] K. Xu, W. Hu, J. Leskovec, and S. Jegelka, “How powerful are graph neural networks?” in _ICLR_ , 2019.
  * [4] Z. Liu, C. Chen, L. Li, J. Zhou, X. Li, L. Song, and Y. Qi, “Geniepath: Graph neural networks with adaptive receptive paths,” in _AAAI_ , 2019, pp. 4424–4431.
  * [5] Y. Wang, J. Zhang, S. Guo, H. Yin, C. Li, and H. Chen, “Decoupling representation learning and classification for gnn-based anomaly detection,” in _SIGIR_ , 2021, pp. 1239–1248.
  * [6] J. Liu, M. He, G. Wang, N. Q. V. Hung, X. Shang, and H. Yin, “Imbalanced node classifcation beyond homophilic assumption,” in _IJCAI_ , 2023, pp. 7206–7214.
  * [7] L. Qu, H. Zhu, R. Zheng, Y. Shi, and H. Yin, “Imgagn: Imbalanced network embedding via generative adversarial graph networks,” in _KDD_ , 2021, pp. 1390–1398.
  * [8] M. Wu, S. Pan, and X. Zhu, “Openwgl: open-world graph learning for unseen class node classification,” _Knowl. Inf. Syst._ , vol. 63, no. 9, pp. 2405–2430, 2021.
  * [9] Y. Song and D. Wang, “Learning on graphs with out-of-distribution nodes,” in _KDD_ , 2022, pp. 1635–1645.
  * [10] L. Galke, I. Vagliano, B. Franke, T. Zielke, and A. Scherp, “Lifelong learning in evolving graphs with limited labeled data and unseen class detection,” _CoRR_ , vol. abs/2112.10558, 2021.
  * [11] L. Galke, I. Vagliano, B. Franke, T. Zielke, M. Hoffmann, and A. Scherp, “Lifelong learning on evolving graphs under the constraints of imbalanced classes and new classes,” _Neural Networks_ , vol. 164, pp. 156–176, 2023.
  * [12] Y. Ming, Y. Sun, O. Dia, and Y. Li, “How to exploit hyperspherical embeddings for out-of-distribution detection?” in _ICLR_ , 2023.
  * [13] Q. Zhang, Q. Li, X. Chen, P. Zhang, S. Pan, P. Fournier-Viger, and J. Z. Huang, “A dynamic variational framework for open-world node classification in structured sequences,” in _ICDM_ , 2022, pp. 703–712.
  * [14] S. Vaze, K. Hant, A. Vedaldi, and A. Zisserman, “Generalized category discovery,” in _CVPR_ , 2022, pp. 7482–7491.
  * [15] X. Wen, B. Zhao, and X. Qi, “Parametric classification for generalized category discovery: A baseline study,” in _ICCV_ , 2023, pp. 16 544–16 554.
  * [16] S. Zhang, S. H. Khan, Z. Shen, M. Naseer, G. Chen, and F. S. Khan, “Promptcal: Contrastive affinity learning via auxiliary prompts for generalized novel category discovery,” in _CVPR_ , 2023, pp. 3479–3488.
  * [17] F. Chiaroni, J. Dolz, I. M. Ziko, A. Mitiche, and I. B. Ayed, “Mutual information-based generalized category discovery,” _CoRR_ , vol. abs/2212.00334, 2022.
  * [18] B. Ye, K. Gan, T. Wei, and M. Zhang, “Bridging the gap: Learning pace synchronization for open-world semi-supervised learning,” _CoRR_ , vol. abs/2309.11930, 2023.
  * [19] B. Zhao, X. Wen, and K. Han, “Learning semi-supervised gaussian mixture models for generalized category discovery,” in _ICCV_ , 2023, pp. 16 577–16 587.
  * [20] K. Cao, M. Brbic, and J. Leskovec, “Open-world semi-supervised learning,” in _ICLR_ , 2022.
  * [21] Z. Sun, S. Chen, T. Yao, B. Yin, R. Yi, S. Ding, and L. Ma, “Contrastive pseudo learning for open-world deepfake attribution,” in _ICCV_ , 2023, pp. 20 825–20 835.
  * [22] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _CVPR_ , 2016, pp. 770–778.
  * [23] A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani, M. Minderer, G. Heigold, S. Gelly, J. Uszkoreit, and N. Houlsby, “An image is worth 16x16 words: Transformers for image recognition at scale,” in _ICLR_ , 2021.
  * [24] J. Qiu, Q. Chen, Y. Dong, J. Zhang, H. Yang, M. Ding, K. Wang, and J. Tang, “GCC: graph contrastive coding for graph neural network pre-training,” in _KDD_ , 2020, pp. 1150–1160.
  * [25] C. Ying, T. Cai, S. Luo, S. Zheng, G. Ke, D. He, Y. Shen, and T. Liu, “Do transformers really perform badly for graph representation?” in _NeurIPS_ , 2021, pp. 28 877–28 888.
  * [26] X. Sun, H. Cheng, J. Li, B. Liu, and J. Guan, “All in one: Multi-task prompting for graph neural networks,” in _SIGKDD_ , 2023, pp. 2120–2131.
  * [27] Z. Liu, X. Yu, Y. Fang, and X. Zhang, “Graphprompt: Unifying pre-training and downstream tasks for graph neural networks,” in _WWW_ , 2023, pp. 417–428.
  * [28] M. Sun, K. Zhou, X. He, Y. Wang, and X. Wang, “GPPT: graph pre-training and prompt tuning to generalize graph neural networks,” in _SIGKDD_ , 2022, pp. 1717–1727.
  * [29] O. Shchur, M. Mumme, A. Bojchevski, and S. Günnemann, “Pitfalls of graph neural network evaluation,” _CoRR_ , vol. abs/1811.05868, 2018.
  * [30] A. van den Oord, Y. Li, and O. Vinyals, “Representation learning with contrastive predictive coding,” _CoRR_ , vol. abs/1807.03748, 2018.
  * [31] P. Khosla, P. Teterwak, C. Wang, A. Sarna, Y. Tian, P. Isola, A. Maschinot, C. Liu, and D. Krishnan, “Supervised contrastive learning,” in _NeurIPS_ , 2020, pp. 18 661–18 673.
  * [32] D. Arthur and S. Vassilvitskii, “k-means++: the advantages of careful seeding,” in _SODA_ , N. Bansal, K. Pruhs, and C. Stein, Eds. SIAM, 2007, pp. 1027–1035.
  * [33] Y. Sun and Y. Li, “Opencon: Open-world contrastive learning,” _Trans. Mach. Learn. Res._ , vol. 2023, 2023.
  * [34] M. N. Rizve, N. Kardan, S. Khan, F. S. Khan, and M. Shah, “Openldn: Learning to discover novel classes for open-world semi-supervised learning,” in _ECCV_ , vol. 13691, 2022, pp. 382–401.
  * [35] X. Sun, Z. Yang, C. Zhang, K. V. Ling, and G. Peng, “Conditional gaussian distribution learning for open set recognition,” in _CVPR_ , 2020, pp. 13 477–13 486.
  * [36] W. J. Scheirer, A. de Rezende Rocha, A. Sapkota, and T. E. Boult, “Toward open set recognition,” _IEEE Trans. Pattern Anal. Mach. Intell._ , vol. 35, no. 7, pp. 1757–1772, 2013.
  * [37] C. Geng, S. Huang, and S. Chen, “Recent advances in open set recognition: A survey,” _IEEE Trans. Pattern Anal. Mach. Intell._ , vol. 43, no. 10, pp. 3614–3631, 2021.
  * [38] R. He, Z. Han, Y. Yang, and Y. Yin, “Not all parameters should be treated equally: Deep safe semi-supervised learning under class distribution mismatch,” in _AAAI_ , 2022, pp. 6874–6883.
  * [39] Y. Chen, X. Zhu, W. Li, and S. Gong, “Semi-supervised learning under class distribution mismatch,” in _AAAI_ , 2020, pp. 3569–3576.
  * [40] L. Guo, Z. Zhang, Y. Jiang, Y. Li, and Z. Zhou, “Safe deep semi-supervised learning for unseen-class unlabeled data,” in _ICML_ , vol. 119, 2020, pp. 3897–3906.
  * [41] K. Saito, D. Kim, and K. Saenko, “Openmatch: Open-set consistency regularization for semi-supervised learning with outliers,” _CoRR_ , vol. abs/2105.14148, 2021.
  * [42] Y. Hsu, Z. Lv, and Z. Kira, “Learning to cluster in order to transfer across domains and tasks,” in _ICLR_ , 2018.
  * [43] Z. Zhong, L. Zhu, Z. Luo, S. Li, Y. Yang, and N. Sebe, “Openmix: Reviving known knowledge for discovering novel visual categories in an open world,” in _CVPR_ , 2021, pp. 9462–9470.
  * [44] K. Han, S. Rebuffi, S. Ehrhardt, A. Vedaldi, and A. Zisserman, “Automatically discovering and learning new visual categories with ranking statistics,” in _ICLR_ , 2020.
  * [45] Y. Xian, B. Schiele, and Z. Akata, “Zero-shot learning - the good, the bad and the ugly,” in _2017 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, Honolulu, HI, USA, July 21-26, 2017_. IEEE Computer Society, 2017, pp. 3077–3086.
  * [46] S. Liu, M. Long, J. Wang, and M. I. Jordan, “Generalized zero-shot learning with deep calibration network,” in _NeurIPS_ , 2018, pp. 2009–2019.
  * [47] W. Chao, S. Changpinyo, B. Gong, and F. Sha, “An empirical study and analysis of generalized zero-shot learning for object recognition in the wild,” in _ECCV_ , vol. 9906, 2016, pp. 52–68.
  * [48] Z. Li and H. Liu, “Zero-knowledge zero-shot learning for novel visual category discovery,” _CoRR_ , vol. abs/2302.04427, 2023.
  * [49] Q. Zhang, Z. Shi, X. Zhang, X. Chen, P. Fournier-Viger, and S. Pan, “G2pxy: Generative open-set node classification on graphs with proxy unknowns,” in _IJCAI_ , 2023, pp. 4576–4583.
  * [50] H. Xu, L. Xiang, J. Ou, Y. Weng, X. Wang, and C. Zhou, “Open-world graph active learning for node classification,” _ACM Trans. Knowl. Discov. Data_ , vol. 18, no. 2, pp. 43:1–43:20, 2024.
  * [51] X. Luo, Y. Zhao, Z. Mao, Y. Qin, W. Ju, M. Zhang, and Y. Sun, “RIGNN: A rationale perspective for semi-supervised open-world graph classification,” _Transactions on Machine Learning Research_ , 2023.
  * [52] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio, “Graph attention networks,” in _ICLR_ , 2018.
  * [53] T. W. Tsai, C. Li, and J. Zhu, “Mice: Mixture of contrastive experts for unsupervised image clustering,” in _ICLR_ , 2021.
  * [54] J. Li, P. Zhou, C. Xiong, and S. C. H. Hoi, “Prototypical contrastive learning of unsupervised representations,” in _ICLR_ , 2021.
  * [55] V. Sharma, M. Tapaswi, M. S. Sarfraz, and R. Stiefelhagen, “Clustering based contrastive learning for improving face representations,” in _FG_ , 2020, pp. 109–116.
  * [56] M. Caron, I. Misra, J. Mairal, P. Goyal, P. Bojanowski, and A. Joulin, “Unsupervised learning of visual features by contrasting cluster assignments,” in _NeurIPS_ , 2020, pp. 9912–9924.
  * [57] H. W. Kuhn, “The hungarian method for the assignment problem,” in _50 Years of Integer Programming 1958-2008 - From the Early Years to the State-of-the-Art_ , 2010, pp. 29–47.
  * [58] Z. Zhao, L. Zhou, L. Wang, Y. Shi, and Y. Gao, “Lassl: Label-guided self-training for semi-supervised learning,” in _AAAI_ , 2022, pp. 9208–9216.
  * [59] Y. Zhang, X. Zhang, J. Li, R. C. Qiu, H. Xu, and Q. Tian, “Semi-supervised contrastive learning with similarity co-calibration,” _IEEE Trans. Multim._ , vol. 25, pp. 1749–1759, 2023.
  * [60] F. Yang, K. Wu, S. Zhang, G. Jiang, Y. Liu, F. Zheng, W. Zhang, C. Wang, and L. Zeng, “Class-aware contrastive semi-supervised learning,” in _CVPR_ , 2022, pp. 14 401–14 410.
  * [61] K. Sun, Z. Lin, and Z. Zhu, “Multi-stage self-supervised learning for graph convolutional networks on graphs with few labeled nodes,” in _AAAI_ , 2020, pp. 5892–5899.
  * [62] T. Gao, X. Yao, and D. Chen, “Simcse: Simple contrastive learning of sentence embeddings,” in _EMNLP_ , 2021, pp. 6894–6910.
  * [63] N. Srivastava, G. Hinton, A. Krizhevsky, I. Sutskever, and R. Salakhutdinov, “Dropout: A simple way to prevent neural networks from overfitting,” _Journal of Machine Learning Research_ , vol. 15, no. 56, pp. 1929–1958, 2014.
  * [64] W. Zhao, H. Ma, and Q. He, “Parallel _K_ -means clustering based on mapreduce,” in _CloudCom_ , vol. 5931, 2009, pp. 674–679.
  * [65] Y. Li, K. Zhao, X. Chu, and J. Liu, “Speeding up k-means algorithm by gpus,” _J. Comput. Syst. Sci._ , vol. 79, no. 2, pp. 216–229, 2013.
  * [66] D. Sculley, “Web-scale k-means clustering,” in _WWW_ , 2010, pp. 1177–1178.
  * [67] W. Hu, M. Fey, M. Zitnik, Y. Dong, H. Ren, B. Liu, M. Catasta, and J. Leskovec, “Open graph benchmark: Datasets for machine learning on graphs,” in _NeurIPS_ , 2020.
  * [68] Y. Wang, J. Zhang, H. Li, Y. Dong, H. Yin, C. Li, and H. Chen, “Clusterscl: Cluster-aware supervised contrastive learning on graphs,” in _WWW_ , 2022, pp. 1611–1621.
  * [69] P. J. Rousseeuw, “Silhouettes: A graphical aid to the interpretation and validation of cluster analysis,” _Journal of Computational and Applied Mathematics_ , vol. 20, pp. 53–65, 1987.
  * [70] A. T. Kalai, A. Moitra, and G. Valiant, “Efficiently learning mixtures of two gaussians,” in _Proceedings of the forty-second ACM symposium on Theory of computing_ , 2010, pp. 553–562.