Towards Understanding Parametric Generalized Category Discovery on Graphs
Authors: Bowen Deng
Lele Fu
Jialong Chen
Sheng Huang
Tianchi Liao
Zhang Tao
Chuan Chen
Venue: ICML 2025 poster (2025)
Keywords: Generalized Category Discovery
Graph Machine Learning
Representation Learning
Primary area: general_machine_learning->unsupervised_and_semisupervised_learning

Abstract: Generalized Category Discovery (GCD) aims to identify both known and novel categories in unlabeled data by leveraging knowledge from old classes. However, existing methods are limited to non-graph data; lack theoretical foundations to answer *When and how known classes can help GCD*. We introduce the Graph GCD task; provide the first rigorous theoretical analysis of *parametric GCD*. By quantifying the relationship between old and new classes in the embedding space using the Wasserstein distance W, we derive the first provable GCD loss bound based on W. This analysis highlights two necessary conditions for effective GCD. However, we uncover, through a Pairwise Markov Random Field perspective, that popular graph contrastive learning (GCL) methods inherently violate these conditions. To address this limitation, we propose SWIRL, a novel GCL method for GCD. Experimental results validate our (theoretical) findings and demonstrate SWIRL's effectiveness.

Towards Understanding Parametric Generalized Category Discovery on Graphs
Bowen Deng" 12
Lele Fu"
2
Jialong Chen
Sheng Huang?
Tianchi Liao? Tao Zhang? Chuan Chen
Abstract
2024; Hou al., 2024) aims to identify and label novel classes. However, GNCD assumes only new-class samples during testing, which is often unrealistic. We introduce Graph Generalized Category Discovery (GGCD), which addresses both old and new-class nodes during testing.
Generalized Category Discovery (GCD) aims to identify both known and novel categories in un- labeled data by leveraging knowledge from old classes. However, existing methods are limited to non-graph data; lack theoretical foundations to answer When and how known classes can help GCD. We introduce the Graph GCD task; provide the first rigorous theoretical analysis of paramet- ric GCD. By quantifying the relationship between old and new classes in the embedding space us- ing the Wasserstein distance W, we derive the first provable GCD loss bound based on W. This analysis highlights two necessary conditions for effective GCD. However, we uncover, through a Pairwise Markov Random Field perspective, that popular graph contrastive learning (GCL) meth- ods inherently violate these conditions. To ad- dress this limitation, we propose SWIRL, a novel GCL method for GCD. Experimental results val- idate our (theoretical) findings and demonstrate SWIRL's effectiveness.
Compared to GGCD, Visual GCD (VGCD) has made sig- nificant progress. VGCD methods consist of two main parts: contrastive learning (CL.) and classification. Based the classifier type, VGCD can be divided into: 1) non- parametric methods, such as Vanilla GCD (Vaze et al., 2022), which use classifiers like Semi cumi--upervieed K- K-means (SS- KMM;; 2) parametric GCD methods, such as SimGCD (Wen et al., 2023), that use parametric classifiers like MLPs. Re- gardless of the method or data type. a common consensus is that leveraging knowledge from old classes aids in distin- guishing new classes. However, the theoretical mechanisms behind this consensus are unclear, motivating our research:
Question 1:
When and how do old classes help (paramet- ric) generalized category discovery on graphs?
Despite empirical progress, the theoretical foundations of GCD remain limited. Chiaroni et al. (2023) proposed maxi- mizing the mutual information between representations and classifier predictions. Rastegar et al. (2024) derived and minimized an upper bound on the Kullback-Leibler (KL) di- vergence between the predicted distribution p(ū; = ûj) and the true one p(3k = yバ) over all (i.j) pairs. Both thcories fail elucidate the intrinsic role of old-class knowledge in new-class discovery and lack related provable GCD loss bounds, due to the lack of formal analysis of the relationship between old and new classess and its impact GCD.
1. Introduction
Graph machine learning (GML) (Wu et al., 2021b; Liu al., 2022a) has made notable strides in many fields like recommendation systems (Pal et al., 2020) and financial risk management (Motie & Raahemi, 2024). Traditional GML assumes all categories are known during training, limiting its ability to handle unknown new classes during testing in real-world open-world scenarios. Prior solutions, such as Graph Open-set Recognition (Wu et al., 10 Zhang et al., 2023a; 2024), detect and reject nodes from unseen classes, while Graph Novel Category Discovery (GNCD) (Jin al.,
Intuitively, when the embeddings of old classes I and 1' are well-separated, distinguishing between new classes u and u' can be achieved by aligning their embeddings with those of I and I', respectively. Specifically, The closer the predictions for u are to those for 1, and for u' to I', the more effectively the knowledge for differentiating 7 and I' transfers to and u'. Formally, ship, considering both embeddings and labels, using the Wasserstein distance W between the joint (embedding, la- bel) distributions of old and new classes. Following the common practice of replacing discrete metrics with differ- entiable surrogate losses, we define a surrogate loss Eq. 5 that faithfully reflects GCD performance. We then derive
Equul contribution 'School of Computer Science and En- gineering, Sun Yat-Sen University, Guangzhou, China 'School of Systems Science and Engineering, Sun Yat-Sen University, Guangzhou, China 'School of Software Engineering, Sun Yat- Sen University, Zhuhai, China. Correspondence to: Chuan Chen <chenchuan wyw...cssuuu......
quantify this relation-
Proceedings of the 4nnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Towards Understanding Parametric Generalized Category Discovery on Graphs
an upper bound for this loss based on W. Analyzing the influence of W on this upper bound reveals that effective GCD requires constraining the global structure of categories in the embedding space. However, mainstream graph con- trastive learning (GCL) methods mainly optimize pairwise local structures, failing to impose these global constraints. Our theoretical analysis using Pairwise Markov Random Field (PMRF) confirms this limitation. Additionally, GCN (Kipf & Welling, 2017) encoders' smoothing effect mixes categories, also disrupting the global structure. To address these, we propose SWIRI,, new GCL method that provides improved control over the relationships among categories in the embedding space. Our main contributions are:
classified, while those from new classes should be grouped into clusters that represent distinct new classes.
2.2. Adapting VGCD Baselines to Graphs
For node-level graph tasks, embedding graph information into the embeddings allows subsequent processing rely only Thus, can adapt VGCD methods to graphs by replacing the CL module with GCL, leaving the classifier design unchanged. The adaptation details is in Appendix B.
2.3. The Surrogate Loss for GCD Performance
The performance of GCD is primarily evaluated by: 1) semi- supervised classification accuracy on old-class data, and 2) clustering accuracy on new-class data. GNN encoders can inject graph structure information into embeddings and thus deduce the embedding dataset DD = Y.) ] The conditionals of the data from the old class | and the new class are separately denoted by Pt p(zly () p(zly') and Pu p(zly = u) p(zly"), where y y" y E V'c { y E R Σ Vo = } are respectively the unique label vectors of class I E C and u E U. The label distribution within old/new/all classes is denoted as pc(c)/pu (c)pp(cc)))p)))))))))))))))))))
1. We introduce the GGCD task for graph data and adapt multiple VGCD methods for GGCD.
2. We define a GCD loss, quantify the relationship be- tween old and new classes using Wasserstein distance, and then develop the first provable GCD loss upper bound theory (Theorem 3.5), answering Question 1.
3. We identify the negative impact of the GCN encoder GCD, and provide the first PMRF-based analysis of GCL,, revealing the undesired randomness of category relations in the embedding space (Theorem 4.3).
Old Capability. For the whole old class data, the population classification loss of (parametric) classifier h reads
4. We propose SWIRL, a new GCL method for GGCD.
Lc(h) = Σ (( IEC
(1)
5. We validate all (theoretical) analyses on synthetic datasets and demonstrate SWIRL's effectiveness real-world graphs.
where L: X>'c + R measures the discrepancy between two label distributions. During training, only the empirical version for of pt is available, leading to the empirical loss (h).). L can also quantify the similarity between two hypotheses h and h², given the data from the class set C
2. Graph GCD Preliminaries
We formulate the GGCD problem, design GGCD baselines, and define loss that faithfully reflects GCD performance.
Ec = Σ ((C()).n.L(((2)).
eEC
2.1. GGCD Problem Formulation
where p(c) is the label distribution of all data from C.
Given an n-node attributed graph G X), where A e A == (0, j is the binary adjacency matrix and X E Raxd denotes the node features, Aij = means nodes and j are linked and the feature vector of node i is given by x; == [], E EX. The node-level dataset D (A, (xx, y4 )) is partitioned into two parts: 1) the labeled subset Dz = (A, [(x,, )r) consisting of nodes from C, known old and 2) the unlabeled subset Dy of nodes without labels. In GCD, the unlabeled nodes belong to C distinct categories C L U U, where U (u), .., M.C.) denotes the new classes. We adapt the transductive setting (Vaze et al., 2022) to graphs such that all edges and node features are accessible during training but only the labels of nodes from Dí are known. In testing, the nodes from old classes are expected to be accurately
New Capability. For the new-class nodes (z,, V:) from class u, the predicted 9 arg max; y, may not match the true one u. Thus, we use a clustering loss instead of a classification loss distinguish new classes.
Lh) >> pu pu(w)Epten L(h(z), h(z")) + oF weu
(3)
classes L = (41,12... .2..2....c,... ..
F Σ pulu))u(u')) wgw
(e) L(h(z)) h(zz)
where the first term attracts the intra-class samples, F repels the inter-class ones, and a > 0 scales the repulsion force.
Considering both old and new capability leads the loss
T (b) = cL + Tu 8>0
(4)
2

---

Towards Understanding Parametric Generalized Category Discovery on Graphs
Optimizing Eq. (4) may lead to a trivial GCD solution:
Assumption 3.3. The loss function L(:,)) : N''x''c - R satisfies the triangle inequality and is r-Lipschitz (r>00) w.r.f. the first argument. That
Suppose Cn = C. and all old-class samples are predicted perfectly, i.c., (h)
O. Without loss of generality, as- sume that all nodes from the new class 21 = Co + are all predicted as 11 1, those from Ui = C. + are predicted as (2 2, and so on. In this case, Lu(() = O, leading to (h) = 0. But we cannot distinguish new-class data from old-class data (Reject Capability). To resolve this issue, the expected prediction hu = Ep across all new-class data should be supported only on U. Thus, we have to minimize the Kl.-divergence between bu and pu(c), yielding the final GCD loss of classifier h.
((y,, - L(y2,8s) S SrL(y1,32).
(6)
Losses such as MSE, MAE and Jensen-Shannon distance (Englesson & Azizpour, 2021) satisfies Assumption 3.3 but Cross Entropy (CE) DaE does not. Nevertheless, the equiv- alence of MSE and CE has been demonstrated empirically (Hui & Belkin, 2020) and theoretically (Zhou et al., 2022).
Thus, our theory, based on Assumption 3.3, is expected to also hold when L = Dcg, as further evidenced by our illustrative experiments involving CE (Sec.s 3.4 and 4.3).
(h) = (h)(h) + Lu(h) + wDw.aaDlellllllleaeooo
(5)
3. Understand Parametric GCD Classifiers
Assumption 3.4. Given distributions pi (21) and p2 (22), h Z + Vc is said (AA-Liipshhtzz transferable if
Using the classifier h and the embedding dataset induced by GNN encoders, we have defined the GCD loss Eq. (5). Addressing Question 1 involves investigating how the the old-and-new relationship influences Old/New/Reject capa- bilities. We reflect this relationship with the old-and-new Wasserstein distance, and analyze its impact on GCD.
Pr (T(((ZZ)), M(z))) (Z( 22)) S ((A),>>0 (7) ((1-P2))
R + [0, 1], L and D denote the respective met- rics in Y' and Z, and #(1..22) is the joint distribution of (z), 22) coupled by pi (z1) and (2(2).
where Φ: :
3.1. Quantify the Old-and-new Relationship
Assumption 3.4 ensures that, under different distributions, the classifier's output typically does not change by more than A-times the input variation. If this property does not hold, the predictions for new-class nodes will be almost unaffected by the old-class knowledge (embedded in the classifier weights). This contradicts the GCD's ' motivation of discovering new classes by leveraging old knowledge. Therefore, Assumption 3.4 is essential for the tractability of GCD problems when employing parametric GCD methods.
To investigate the relationship between old and new classes using both embedding and label information, we introduce the joint Wasserstein distance in Definition 3.1.
Definition 3.1. The Wasserstein distance between two joint probability distributions p1 = p2, u) and p2 = pC (22,1)
over the metric space (2 x C, DA) is given by
inf / renl
(p1, p2)
Da [(21. u), (22. di [(2, (22.
3.3. The GCD Loss Upper Bound Theorem
where Dd [ u). (2) AD(Z1, 22) + L(y", y²) is the cost of transporting (2), u) to 122,1),2 X > 0 weights the embedding distance, and 11(p1. P2) is the set of couplings over (Z x 2)² such that fg Le [[21, u); (z2, 1)] dzzd1
Under these assumptions, we analyze the influence of W on the GCD loss Eq. (5), leading to Theorem 3.5.
Theorem 3.5 (The GCD Loss Upper Bound Theory). Let Assumptions 3.2, 3.3 and 3.4 hold and h be the optimal hypothesis that minimizes the GCD loss Eq. (5). Let ni = E TM and nu = E., Thu be the total numbers of old and new class samples, respectively. And suppose that the dataset is
P1 and Jz Su π. [Zz, u); (z2.1) [)] dz du P2.
3.2. The Assumptions of Our GCD Theory
We present and discuss the assumptions used in this work.
Then there exists, c' and ni. such that for ny > -1, nC > ni, and all À >> 0, Lie (h) is bounded as, with probability at least 8 w (5. > 0).
Assumption 3.2. The embedding space is bounded ||z|| < B, and h is Lipschitz such that L(h(zz), h(zz)) S.
Lee (h) SaF + (2 (2++3)Lcch)))) ())c + 2W (pu (z. v). pe (z, 8)) (8a)
Assumption 3.2 requires that embeddings are bounded and the classifier is Lipschitz. The boundedness can be met by bounding the spectral norms of encoder weights (Tang& & Liu, 2023) and normalizing the input node features (Verma & Zhang, 2019). The Lipschitz continuity, which depends on the spectral norms of h 's weights (Virmaux& & Scaman, 2018), is a common assumption in neural network analysis (Redko et al., 2022; Khromov & Singh, 2023).
+ (kL((e()) 2Eu + E To,
S In
2
3)) 12) To =o=
2n'c w
2 log
2 x
1
+2
r rS((A) + v /
+
Vnui
V
3

---

Towards Understanding Parametric Generalized Category Discovery on Graphs
where b= Pr(y E.). Pe is the uniform distribution over C, h = E, h((z) is the expected prediction over both the old and new data, and (z(z.)) y) and pu (z, y) are respec- tively the empirical old and new joint distributions. Wr is hereafter abbreviated as W. v'y is the number of old- class training samples while ng/nu is the total number of old-Inew-class samples in the whole embedding dataset DD=
where b = Pr(y E U) EyEu Je plz, y)de, h Ep(z.y) M(z), and DKu(Pel(h) is minimized when the en- tropy H(h) = - -cec h(c) log h(c) is maximized.
3.4. Illustrative Experiments
To validate the above remarks, particularly the impact of W, we conducted a series of experiments. Specifically, we compared the performance of an MLP classifier across multiple embedding datasets with varying W values to investigate how the old-and-new relationship affects the Old/New/Reject Capabilities, thereby addressing Question 1. Since Theorem 3.5 focuses on the classification phase af- ter obtaining embeddings, we use only the CE and ER losses to train the final MLP classifier on the synthetic embedding datasets. This setup allows us to isolate the effects of repre- sentation learning and elucidates the embedding properties required for a parametric classifier to achieve strong GCD performance.
In the bound Eq. (8a). Le(hh) indicates the (old-class) training classification loss of the optimal GCD solution h". Er/Eu represents the deviation between any h and h" on the old-/new-class distribution. Lc(h²) with Eg corresponds to Old Capability. F reflects h's ability to distinguish new classes. F plus Eu corresponds to New Ca- pability under the constraint of old-class data. (Pz(Pel)h) corresponds to Reject Capability. The old-and-new distri- bution discrepancy (pe (z. y). pic(z,) y)) (abbreviated as W later) can influence all three Capabilities, as elabo- rated later. Tg summarizes all the sample complexity terms.
To provide an intuitive interpretation of Theorem 3.5, we present in Appendix F.2 an example with total of four classes: two old classes (cats and trucks) and two new classes (lions and sports cars). Fig. 5 illustrates the re- lationships between these classes and their impact on the Wasserstein distance between old-class and new-class data.
Synthetic Embedding Datasets. We generate three 2D embedding datasets Dj. Dÿj and Dj. as shown in Fig. la- Ic. Each dataset contains eight classcs/clusters, with four inner clusters representing new classes (centroids labeled as x, x, x, *) and four outer clusters representing old classes (centroids labeled *, *,, *). The dataset generation models and hyperparameters are provided in Appendix G.3, From Dj to Dj. the relative distances between old and new class centroids progressively decrease (i.e., W1 >> W2 > Wa),, reflecting different old-and-ne dd--wnw-eww relationships.
Implications of Theorem 3.5
Remark 3.6. W in Theorem 3.5 describes the relationship between old and new classes, and should be small to bound the GCD loss. A small W implies that the categories with closer semantic relations (i.c., smaller label distances in V'c) should also be more proximate in Z, according to the joint- distribution-style Definition 3.1. That is pushing new classes towards those old classes semantically closer to them.
Verify Remark 3.6: Large W Undermines GCD. In Df (Fig. la), new classes are mixed and are closer each other than to old classes, resulting in large W1. By increasing the distances between new classes while reducing the relative distance between new and old classes, we obtain Dž (Fig, lb), where W₂ < W1. As stated in Remark 3.6, a decrease in W implies that the distance between new classes and their adjacent old classes becomes smaller, which allows more of the distinguishing features between old classes to transfer to the new classes. From Df to D2 * moves closer to *, * to *, * to * and * to *. As a result, the New Capability in Dř outperforms that in Dj: as shown in Fig, le, Reject ACC remains nearly unchanged, while New RACC improves by about 7 points.
Remark 3.7. When considering W in isolation, Remark 3.6 encourages small W. However, a too small value implies that the new-class data entirely collapse into old classes, which degrades Reject, and then New and Old Capabili- ties. This aligns with Theorem 3,5: when new classes are mixed into old ones, substantially, causing the bound rise even W decreases. Remark 3.8. Theorem 3.5 justifies Entropy Regularization (ER) (Assran et al., 2022; Wen et al., 2023), which pushes the expected prediction uniformly distributed across C, appears as DK (Pellh) in the upper bound Eq. (8a). This term, according to Proposition 3.9, upper bounds the reject term DK (prr()) in the GCD loss Eq. (5).
(P]llh in Eq. (8a) increases
Verify Remark 3.7:
Too Small W Undermines GCD. By further reducing the relative distance between new and old classes from Dř, new-class data move even closer to the old classes, resulting in Dj (Fig. Ic) with a smaller Wasserstein distance W3 < Wz. Although the new and old classes are now closer, the overlap between the data of new and old
Proposition 3.9. If Pu, Pe E Vc are uniform distributions over lt and C respectively, and the data distribution is class- balanced, then it follows that
All evaluation metrics are formally defined and discussed in Appendix G.I, where refine the conventional GCD metries towards more faithful GCD evaluation.
DKL(Pull < 1 (KL(PelI))
(9)
4

---

Towards Understanding Parametric Generalized Category Discovery on Graphs
D2. GE_ER
F25, CE_ER
GE
100
Performance (%%
60
40
20
HRSSooe
Old
New RACC Rejest ACC
(a) Di, W1 = 333
(b) D W2 = .99 (c) D W3 = .17
(d) D w/o ER
(e) GCD Performance
Figure I: (a-c) The datasets and the decision boundaries (marked by background colors) of MLPs trained with the CE+ER criterion. (d) The decision boundary of MLP trained with CE and without ER on D2 (e) The GCD performance.
classes counteracts the benefits of the reduced W, and the performance does not improve as it did in the transition from Di to Dj. This overlap leads to more misclassifications, where new-class samples are predicted as old classes and vice versa (Remark 3.7), which is reflected in a significant drop in Reject ACC. As shown in Fig. Ie, Reject ACC in Dj drops significantly compared Dj, and both New RACC and Old RACC also decline due to the confusion between new and old classes.
4.1. GCL Framework Violates Lesson 1
PMRF View of GCL Framework Inspired by Tan et al. (2023), we encode the similarity relations among all raw and possibly augmented nodes using B E [o, [0,1,, where Bij is the chance of nodes and j being sampled as a positive pair under data augmentation. As form of human prior in GCL, the augmentation should align B with human cogni- tion of node relations and guide the model to approximate B. In the raw space X, approximating B through simple similarity computations is challenging. However, a good encoder f can produce an embedding space 2, where B can be effectively approximated by the node embedding relation matrix K E TR:50 where Ky = k(z, 2,) induced by a simple kernel function k(;,)) -) in the embedding space Z.
Verify Remark 3.8: Entropy Regularization Matters. In Dj when ER is removed, as noted in Remark 3.8, all new-elass data are predicted as old classes as shown by the decision boundary in Fig. Id, resulting in complete loss of New Capability in Fig. le.
We follow the coupling framework from Assel et al. (2022), and treat the embeddings as observations of Pairwise Markov Random Field (PMRF) defined on graph W e {0, ] NNN, with each category corresponding to a graph connected component (CC). According to spectral graph theory (Chung, 1997). the Laplacian L of this graph has a null-space ker L of rank C, and the orthogonal comple- ment (ker L)+ A signal Z N can be decomposed as Z Zo + Z₁, where Zo and Z are the projections onto the subspaces S, (ker L) @ IR and S = (ker L) @ Rd. respectively. For node in class Zo.; is the mean embed- ding of all nodes in class c, enabling Zp to model the global category positions, while Z, captures the relative positions of nodes within their respective CCs (aka clusters).
3.5. Main Takeaway: Two Lessons
Theorem 3.5 provides an upper bound for the GCD loss. Analyzing this bound implies that, for effective GCD per- formance, the embeddings induced by the GNN encoder should satisfy Lesson 1: a sufficiently small aid-and-new Wasserstein distance W discussed in Remark 3.6; Lesson 2: limited overlap between new and old classes (i.e., a not too small W) discussed in Remarks 3.7 and 3.8.
4. GCL Loses Category Semantic Relations
The small W in Lesson 1 requires that for pair of old and new classes (u, 1) that are closer than another pair (u, in the category semantic space Vc, the embeddings of u and I should be much closer than those of (u, I'). That is, the embedding distances between classes, i.e., the Category Em- bedding Relations, should align with the Category Semantic Relations in Vcc Lesson 2 implies that there should be certain distance kept between the embeddings of old and new classes Both lessons impose constraints on the cate- gory embedding relations. However, we find that the GCL methods in the parametric GCD baselines (c.g., SimGCD) inherently fail to satisfy these constraints, as revealed by the PMRF interpretation of GCL (Sec. 4.1) and the smoothing effect of GCN encoder (Sec. 4.2).
The conditional measures on the orthogonal subspaces So and S,, denoted 1f (Zol W) (parameterized by & > 0) and Pk: (M, (based on kernel k), are orthogonal. Their product defines the joint measure p(Z(W) on S = Sy @ S.. Introducing a graph prior p(W;)) parameter- ized by n, the posterior of subgraph conditional on node embeddings, reads p( ((l x p( ((; ()))), Mini- mizing InfoNCE loss amounts to minimizing the cross- entropy DCE (p( W B) B)I((()))))) Here, p(Wx: B) x 2D (D II B Wx.0 is the distribution of sub- graphs sampled from B, where each subgraph Wx x is
perre,p(Wxx
5

---

Towards Understanding Parametric Generalized Category Discovery on Graphs
sampled with one random augmentation step. (W) - II, I(W++ ++ = 1) filters out the subgraphs where any node has more than one outgoing edges, aligning with the single- positive-sample manner in GCL methods such as GRACE.
Theorem 4.1. Minimizing InfoNCE loss is equivalent to minimizing the cross entropy Dcr(p(W. W x; B)IlP(W W Z)) between the subgraph distribution p( W w;; B), which de- pends on data augmentation, and the subgraph posterior p( ZZ in the PMRF.
(a) D1. W .33
(b) Dr, Secd=2050
(c) Dr, Sced=800
Apart from InfoNCE loss, SupCon loss is also common. It utilizes augmentations of known same-class samples as extra positive samples. If each node i has m. known same- class nodes; then, one augmentation step can yield a sub- graph satisfying (r((W) A II, I(W S my). Since aug- mentations of different nodes are independent, this process equivalent to independently sampling m, times subgraphs satisfying DD(W), From this, we reach Corollary 4.2.
(d) Ds. W3 .19 (e) D3. Scod=2050 (f) D3, Seed=800
Figure 2: (a,d) The CSBM graphs; (b,c,e,f) the embedding space learned by GCL with the InfoNCE+SupCon criterion.
Corollary 4.2. Minimizing SupCon loss is equivalent to minimizing the cross cross-entropy between subgraph distribu- tions stated in Theorem 4.1 excepet the subgraphs here are contrained by (P)))) instead of (iD(()(W)))
violating Lesson 1. The second issue arises when new class is considerably linked to adjacent old class I, causing the node embeddings of u to collapse into those of due to local smoothness. This violates Lesson 2.
The GCL Framework Loses Category Semantic Rela- tion The above presents a more refined treatment of the embedding space than Tan al. (2023), exposing a critical limitation not achievable using existing contrastive learning theorems (Huang al., 2022; Hu al., 2022; Tan et al., 2023; Parulekar et al., 2023; Waida et al., 2023; Ge et al., 2024). Specifically, the embedding relations (i.e., distances) between categories are random and thus not aligned with the (either known or unknown) category semantic relations in Ve. violating Lesson 1. The point lies in the degeneracy of the conditional distribution on the PMRF constructed in the embedding space: the variance of the distribution con- trolling the global category positions Zu becomes infinite under the equivalences stated in Theorem 4.1 and Corol- lary 4.2. Theorem 4.3 summaries this uncontrollability of Category Embedding Relations in GCL.
4.3. Illustrative Experiments
Synthetic CSBM Graphs (Deshpande et al., 2018) are widely used to evaluate graph learning methods. We gener- ate two CSBM graphs, D, and Dz. by first generating node features and labels like Dj and Dž (in Sec. 3.4), and then constructing graph structures with intra-class and inter-class connection probabilities. See Appendix G.4 for details. The main challenges in Dj and D3 are, respectively, distinguish- ing: 1) new classes u and u/: 2) old class and new class u.
Verify Theorem 4.3. Figs. 2a and 2d illustrate Dj and Dz. Figs. 2b and 2e show the embedding spaces learned with GRACE, using InfoNCE and SupCon losses, while exclud- ing other components of SimGCD. To showcase the ran- domness of category embedding relations/distances stated in Theorem 4.3, we run the experiments with different ran- dom seeds, resulting in Figs. 2c and 2f. Comparing Figs. 2b and 2c for Dj, * and * have roughly swapped global positions, while the relative positions of *t, x,, and have also changed markedly. Specifically, in Fig. 2c, * is more distant from x and x than in Fig. 2b. For D3. from Fig, 2e to 2f, the original clockwise arrangement of (*, x) + (*,, *) + (k,,
Theorem 4.3, The InfoNCE or SupCon loss optimization is equivalent to minimizing Der(p( W x; B)IlP( W ( when the conditional distribution of category centers of (Z)lW) diffuse uninformatively.
4.2. GCL Encoder Violates Two Lessons
Besides the GCL framework, GCNs (Kipf & Welling, 2017), widely used GCL encoders, have the smoothing effect (Rusch et al., 2023) that can lead to undesired category embedding relations. The first issue occurs when a new class u is connected to other neighboring new classes u', and local smoothness pulls them closer together, pushing them relatively further from old classes. This results in an increase in the old-and-new Wasserstein distance W.
(*, x)) is disrupted. The distances D(*, *) and D + x), get very small. Furthermore, we find that triangles formed by the embedding centers of any three classes exhibit substantial deformation in both Dj and
D3 when the seeds are changed.
6

---

Towards Understanding Parametric Generalized Category Discovery on Graphs
clusters of C. old classes, while the remaining ones repre- sent unknown clusters. Typically, set K Co model the embedding space in a fine-grained manner. For node i, it is assigned to prototype s(i), and the prototype index is id(s(i)] E [1 : Kj. The prototype relations are then used as a surrogate for category relations.
Representation Learning with Category-Semantic- Aware Dilation. SWIRL employs the SWIRL loss, an gelaacc-to-proootyye contrastive loss that leverages proto- type relations. It follows Lessons 1 and 2 by controlling the repulsion force (and consequently the distances) between classes. Unlike InfoNCE or SupCon, which uniformly re- pel all negative samples, SWIRL applies differentiated re- pulsion. Specifically, we set six levels of repulsion force, denoted tg < to 44 < t3 < l < t1. On Lesson To prevent mixing between adjacent categories, for node i assigned to s(i) O, the supervision signals from old classes make these assignments relatively reliable. There- fore, we apply (i) the smallest repulsion force le between and s(i), and (ii) the largest force t1 between i and all other old prototypes. For a node j assigned to s()) & O since these assignments are less reliable than those for old prototypes, we apply (iii) a moderately low repulsion force is between j and s(j), and (iv) moderately high repulsion force 12 between and all other new prototypes. On Lesson 1: To prevent large Wasserstein distances between old and new classes, the separation between these classes should remain moderate. Therefore, we apply (v) a low repulsion force t4 to each pair of new-class node and an old proto- type. Similarly, (vi) apply moderately strong repulsion force 13 between each old-class node and a new prototype. Finally, the loss for an (either raw or augmented) node i is
(a) Dr, W1 (b) D,, W/ .c.(c) Dr. W1 .29.
SimGCD SimGCD-GPI SWIRL (Ours)
(d) D3, W3 = (c) Dg, 1 (f),()) D3. W1 = 35. SimGCD
SimGCD-GPR SWIRL (Ours)
Figure 3:
The embedding space learned by different GCD methods. Backgournd colors mark the decision boundaries.
Verify the impact of GCN encoder on GCD. Sec. 4.2 discusses the impact of the GCN encoder's smoothing effect on GCD. To reveal this effect, we replace GCN with GPR (Chien et al., 2021) that can escape from local smoothness, denoted as SimGCD-GPR. In D1, new classes are highly mixed, with an even greater degree of mixing observed in the SimGCD representation space (Fig. 3a). After replacing the encoder with GPR, the reduction in local smoothness results in increased embedding distances between the new classes (Fig. 3b). In D3, the mixing of old and new classes prevents SimGCD from distinguishing * and x,, * and x * and s,, and * and * (Fig. 3d). This issue is mitigated by SimGCD-GPP GPR that uses non-smooth GPR (Fig. 3e).
I.sw (i) = - -log r(i, id(s()))))e (((s))))))((e.,0(() ((2,.(())
(10)
Σx r(i, -)e-((e,s)) st),,t)
5. Proposed SWIRL for Parametric GCD
Sec. presents two lessons outlining the conditions for good GCD performance that embeddings should satisfy. Sec. 4 reveals that the GCL module in the adapted SimGCD strug- gles to meet these conditions about category embedding relations. In this section, we propose Semantic-a Ware dlla- tion contRastive Learning (SWIRL... a novel GCL method for parametric GGCD, following Lessons 1 and 2.
x K |t1 : tel chooses the where r(i,k) [1 :1]
force level according to the above designs.
The overall loss of SWIRL. The core of SWIRL lies in aligning the category relations in the learned embedding space, as much as possible, with the Category Embedding Relations advocated by Lessons and 2. After obtaining the clusters and the node-to-prototype assignments (i.e., pseudo- labels) through SS-KM, we push away different clusters with varying repulsion forces based on these pseudo-labels and their confidence levels that depend on how much old class prototypes O = {s .....,.o) are involved in. The varying repulsion forces are implemented by, as explained in Sec. C.2, applying a weight r(i, k) to the scores of negative (sample, prototype) pairs. Specifically, we define six levels of repulsion forces < to < ls < ta < ls < l2 < t for
The Category Relation Speculation via Prototypes. To adhere to Lessons 1 and 2 regarding category relations, estimating these relations without relying the labels of new-class nodes is essential. To achieve this, we utilize SS-KM on the node embeddings averaged over two aug- mentation views to obtain K prototypes P = (s".... .ss.....ss] node-to-prototye and the node-to- prototype assignments. Among these, the
first C. prototypes O (s!,...,ss.) correspond to the
7

---

Towards Understanding Parametric Generalized Category Discovery on Graphs
the SWIRL loss.
Table 1: The performance on CSBM graphs Dj and D3.
SWIRL denotes SWIRL-GCN.
2n
r(i, id ((,id D(zz,a()))
Lsw = Σ log 1=1
(11)
Σx r(i, (i, st
D1
HRScore
Old RACC
New RACC
Reject ACC
SimGCD
68.22
99.58
51.88
99.79
exp(losD(zzz s*
,(( E0
SimGGD-GPR
77.18
99.79
62.92
99.48
exp(tisD(z::
s(i) E 0 # *** E0
SWIRL-GPR
87.72
100.0
78.13
98.54
exp(ta>D(2,,,)
=())0+ 40
SWIRI
96.24
97.29
95.21
98.54
r(i, k)
exp(148D(2z
.s()) =0)
Dg
HRScore
Old RACC
New RACC
Reject ACC
cxp(tss((2,,s" s))
=0)
SimGCD
64.76
98.96
48.12
73.75
SimGCD-GPP
88.77
98.12
81.04
90.52
(xp(t2sD(z.,s*")
.s()) $0 40
SWIRL-GPR
82.39
96.88
71.67
89.58
SWIRL
94.03
95.83
92.29
97.81
where > 0 controls the scale of repulsion force, id[s(i)] is the prototype index of node i's prototype s(). Since Lsw primarily emphasizes the global structure in the embed- ding space and may neglect the preservation of local struc- tures, we adopt weighted combination of the InfoNCE loss LNCE and the SWIRL loss as the total representation learning objective. Furthermore, following SimGCD, we in- corporate the Entropy Regularization (ER) loss on all nodes and apply the Cross Entropy (CE) loss on those labeled (old-class) nodes. The overall training loss for SWIRL
Csw = (1 - (1=22) + LsW + taILER) + agLCE,
(a) SWIRL-GPR
(b) SWIRL-GCN
where 01, 02 > O are the weights shared with SimGCD, and B1 > an additional hyperparameter for SWIRL.
Figure 4: The representation spaces learned with different GNN encoders on D3. (a) Low intra-cluster cohesion blurs the inter-cluster boundaries. (b) High intra-cluster cohesion facilitates inter-cluster separability.
The impact of varying 31 is analyzed in Appendix G.7.
Complexity analysis. The complete training procedure of SWIRL is summarized in Alg. 1. The SS-KM algorithm, which is executed every t epochs, has space complexity of Ond + Kd) and a time complexity of O(nKTd) where the number of SS-KM iterations and n, K, and d represent the number of samples, prototypes, and embedding dimen- sion, respectively. When amortized over all epochs, its per-epoch cost reduces to OnKTTd/t). Meanwhile, Lsw contributes a time complexity of OnK'd) per epoch, domi- nated by the computation of similarities between samples and prototypes, while requiring OnnK) space for storing similarity matrices. Let T be the training epochs. Overall, SWIRL results a total time complexity of OTTnKd), as- suming small constant l/t, and an overall space complex- ity of OnnK nd), which is significantly more efficient than the (n)d) complexity of LNCE, making the extra overhead from s.w negligible.
that in SimGCD, satisfying Lesson 1. On Da, SWIRL ef- fectively separates all adjacent old-and-new category pairs, resulting in a larger old-and-new Wasserstein distance W than SimGCD, satisfying Lesson 2. And as shown in Table 1, SWIRL- outperforms the others on both datasets.
SWIRL with GPR encoders. Unlike SWIRL-GCN, which consistently benefits CGN across datasets, SWIRL-GPR out- performs SimGCD-GPR on Di but underperforms on D3. To investigate this discrepancy, we visualize the representa- tion space of SWIRL-GPR on D3 in Fig. 4. It shows signifi- cantly weaker intra-cluster cohesion compared to SWIRL- GCN. Low intra-cluster cohesion hampers the formation of clear inter-cluster separations and decision boundaries, leading GCD failure. We attribute this issue to both the GPR encoder and SWIRL's emphasis on information from distant nodes/spaces beyond local neighborhoods, which neglects local structural cues and weakens cluster compact- ness. Moreover, prior work (Chen et al., 2023) has noted that GPRs are inherently difficult to train with current GCL methods. Therefore, we recommend using GCN instead of GPR with SWIRL..
5.1. Illustrative Experiments: SWIRL excels SimCGD
To evaluate whether SWIRL can establish desired cate- gory embedding relations, we conducted experiments on the CSBM graphs D, and D3 introduced in Sec. 4.3. As shown in Figs 3c and 3f, SWIRL learns more discriminative embed- dings. On D1, the old-and-non new Wasserstein distance W of SWIRL's representation space is substantially smaller than
8

---

Towards Understanding Parametric Generalized Category Discovery on Graphs
Table 2: Mean and standard deviation of performance (%) on real-world graph datasets. The best metric is in bold.
Datasets
Metrics
GCN
SS-KM
UNO+
VanillaGCD
SimGCD
SWIRL (Ours)
HRScore
6.88:10.76
3.65+0.0
30.47:17.044
62.4026.59
53.14 33.13320..3
64.5344.63
Cora
Old RACC
92.22=0.69
54.79+0.0
91.78+0.87
84.5524.85
77.10=7.48
85.7042.47
New RACC
3.8726.18 18
1.89#0.0
19.34=12.0
49 19,8027.63
44.41=19.82
52.03:6.022
Reject ACC
40.56226.3
37.44+0.0
56.76+12.77
84.10=1.26
17.42+18.33
88. 18.16
HRScore
0.00=0.00
39,90+0.0
41.48+10.98
65 65.3546.10
46.36+3.72
55.6243.03
Citeseer
Old RACC
69.91=1.72
51.5047.61 48.41
65.2331174
59.91+2.83
55.9543.88
New RACC
0.00=0.00
33,93+0.0
37.61+13.76
16.26=11.20
38.0424.97
55.3242.35
Reject ACC
44.00=0.00
63.20+0.0
14.32+15.4
83.164.4.94
78.78+2.39
84.6240.61
HRScore
15.39=3.99
25.1
50.97=6.38
51.32=1.27
46.51=5.10
52.93+2.72
Wiki
Old RACC
74.47=0.71
44.35+0.0
64.8845 04
56,32=1.8
75.05=0.42
$7.5242.91
New RACC
8.64#2.43
17.51
43.1 19.1119990 96
47 17.2042.13
33.91+5.55
49.0 19.0342.87
Reject ACC
65.31+2.85
58.00+0.0
77.51+3.41
72.79:2.61
74.98+2.34
15.19
HRScore
55.83=1.32
50.37+0.0
76.72+5.12
66.1623.11
67.13=8.60
77.62+4.27
A-Photo
Old RACC
91.15=1.11
65.97=0.0
85.54+2.57
88.3623.37
89.55=1.99
90,0843.16 16
New RACC
40.24=1.22
40.74+0.0
69.9888.77
52.93+3.31
14.58
68.3315,66
Reject ACC
82.78=1.00
71.29+0.0
91.7242.77
94.98=1.56
91.51#6.55
93.80+0.33
HRScore
32.94=15.56
27.43=0.0
49.6847.66 66
56.8843.79
32.38+2.81
61.46::4.54
A-C A-Computers
Old RACC
77.61=0.99
44.14
73.8744.16 16
70.82+3.18 18
29.71=6.78
85,3448.79
New RACC
21.99=11.03
19.92+0.0
38, 18.1149.41
47. 36,566..77 97
38.71 04
48.32+4.48
Reject ACC
78.4745.21
60,89+0.0
44.4643.44
78.83+3.30
52,56+4.02
88.38+2.24
6. Experiments on Real-world Graph Datasets
overall performance, measured by HRScore, compared to its competitors. Notably, on the largest dataset, A-computers, SWIRL outperforms all baselines across all metries. On Citeseer, while SWIRL still lags behind Vanilla GCD, it substantially outperforms other parametric GCD methods, i.e., SimGCD and UNO+. These results highlight SWIRL's effectiveness and the importance of understanding paramet- ric GCD performance for developing better methods.
We now evaluate all GGCD methods on real-world graphs.
6.1. Experimental Setup
Datasets and Split. We created node-level GGCD datasets based on five existing datasets: Cora, Citeseer, Wiki, A- Computers, and A-Photo. For Cora and Citeseer, we used the public splits, while for the other three datasets, The entire node set is stratified into train, validation, and test subsets in a 2:2:6 ratio. In each dataset, the first C//2 classes are designated as old classes, while the remaining classes are considered new classes. The old-class nodes in the training set form Dz, while all other nodes constitute Du. During testing, predictions are made for all nodes in Du, with performance evaluated specifically on nodes that also belong to the test set. See Appendix G for the evaluation protocol and implementation details.
7. Conclusions
We introduce the Generalized Graph Category Discovery (GGCD) task and develop several baselines. We provide the first theoretical answer to the core GCD question: "When and how do old classes help (parametric) generalized cate- gory discovery on graphs?" Using the Wasserstein distance W between the joint (embedding, label) distributions of old- and new-class nodes, we quantify their relationship and its impact on GCD. Theorem 3.5 formalizes this, offering a provable GCD loss upper bound dependent on W and identi- fying the necessary category embedding relation conditions for low GCD loss. We proceed to analyze GCL methods that employ InfoNCE-style losses, which are commonly used in parametric GCD baselines, through the lens of PMRF and the smoothing effect of GCNs. Our analysis reveals that such GCL methods often fail to meet the conditions for low GCD loss. To address this, we propose SWIRL,, new GCL method that controls the category embedding relations. Experiments on synthetic and real graph datasets validate our theoretical analysis and confirm SWIRL's effectiveness.
6.2. The GGCD Performance
Our primary goal is to develop a theoretical understanding of Parametric GCD. Beyond the theoretical contributions, our simple yet effective method, SWIRL, shows strong empirical performance. Our comparisons include several GGCD methods adapted from VGCD, such as Vanilla GCD, SimGCD, UNO+, SS-KM, and GCN. Among these, SS-KM directly predicts node features, while GCN incorporates an additional ER loss alongside the cross-entropy loss. As shown in Table 2, SWIRL achieves a significantly higher

---

Towards Understanding Parametric Generalized Category Discovery Graphs
Acknowledgments
Cao, S., Lu, W., and Xu, Q. Deep Neural Networks for Learning Graph Representations. In Proceedings of the AAAI Conference Artificial Intelligence, volume 30, February 2016. doi: 10.1609/aai..v2. wttpaaaiv001111.11111
The research is supported by the National Key Research and Development Program of China (2023YFB2703700) and the National Natural Science Foundation of China (62176269).
Cao, X., Zheng, X., Wang, G., Yu, W. Shen, Y., Li, K., Lu, Y., and Tian, Y. Solving the Catastrophic Forgetting Prob- lem in Generalized Category Discovery. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 16880-16889, 2024.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here
Caron, M., Misra, I., Mairal, J., Goyal, P., Bojanowski, P., and Joulin, A. Unsupervised learning of visual features by contrasting cluster assignments. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS '20, pp. 9912-9924, Red Hook, NY, USA, December 2020. Curran Associates Inc. ISBN 978-1-7138-2954-6
References
Akiba, T., Sano, S., Yanase, T., Ohta, T., and Koyama, M. Optuna: A Next-generation Hyperparameter Opti- mization Framework. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Dis- covery & Data Mining, pp. 2623-2631, Anchorage AK July 2019. ACM. ISBN 978-1-4503-6201-6 doi:
Chen, J., Lei, R., and Wei, Z. PolyGCI: GRAPH CON- TRASTIVE LEARNING via Learnable Spectral Polyno- mial Filters. In The Twelfth International Conference on Learning Representations, October 2023.
10.114553292500.333777
Arthur, D. and Vassilvitskii, S. K-means++: The advantages of careful seeding. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '07, pp. 1027-1035, USA, January 2007. Society for Industrial and Applied Mathematics. ISBN 978-0- 89871 1624-5
Chen, T., Kornblith, S., Norouzi, M., and Hinton, G. Simple Framework for Contrastive Learning of Visual Representations. In Proceedings of the 37th Interna- tional Conference Machine Learning, pp. 1597-1607. PMLR, November 2020.
Assel, H. V., Espinasse, T., Chiquet, J., and Picard, F. A Probabilistic Graph Coupling View of Dimension Re- duction. In Advances in Neural Information Processing Systems, October 2022.
Chiaroni, F. Dolz, J., Masud, Z. I., Mitiche, A., and Ben Ayed, I. Parametric Information Maximization for Generalized Category Discovery. In Proceedings of the IEEE/CVF International Conference on Computer Vision, Pp. 1729-1739, 2023.
Assran, M., Caron, M., Misra, I., Bojanowski, P., Bordes, F. Vincent, P. Joulin, A., Rabbat, M., and Ballas, N. Masked Siamese Networks for Label-Efficient Learning- 17th European Confer- ence, Tel Aviv, Israel, October 23-27, 2022, Proceedings, Part XXXI, pp. 456-473, Berlin, Heidelberg, October 2022. Springer- Verlag. ISBN 978-3-031-19820-5. doi: 10. 10.1007//78-3-000 19821-2.26.
In Computer Vision -
Chien, E., Peng, J., Li, P., and Milenkovic, O. Adaptive Universal Generalized PageRank Graph Neural Network. In International Conference Learning Representations, January 2021.
Chung, F. R. Spectral Graph Theory, volume 92. American Mathematical Soc., 1997.
Bendale, A. and Boult, T. E. Towards Open Set Deep Networks. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 1563-1572, June 2016. doi: N0.1109/CPPR22016
Crouse, D. On implementing 2D rectangular assignment algorithms. IEEE Transactions on Aerospace and Elec- tronic Systems, 52(4):1679-1696 August 2016. ISSN 1557-9603. doi: 10.1 10.1109//AES.201 210.9/TAEE.201.144000 140952.
Bolley, F., Guillin, A., and Villani, C. Quantitative con- centration incqualities for empirical measures on non- compact spaces. Probability Theory and Related Fields, 137:541-593, 2007. doi: 00.10077/000440000000000000 0004-7.
Cuturi, M. Sinkhorn distances: Lightspeed computation of optimal transport. In Burges, C., Bottou, L., Welling, M., Ghahramani, Z., and Weinberger, K. (eds.), Advances in Neural Information Processing Systems, volume 26.
Cao, K., Brbic, M., and Leskovec, J. Open-Wort World Semi- Supervised Learning. In International Conference on Learning Representations, October 2021.
Curran Associates, Inc., 2013.
10

---

Towards Understanding Parametric Generalized Category Discovery on Graphs
Deng, B., Wang. T., Fu, L.,, Huang. S., Chen, C., and Zhang, T. THESAURUS: contrastive graph clustering by swap- ping fused gromov- wasserseein couplings. In Proceed- ings of the AAAI Conference on Artificial Intelligence, pp. 16199-16207, 2025.
on Artificial Intelligence and Statistics, volume 9 of Pro- ceedings of Machine Learning Research, pp. 297-304, Chia Laguna Resort, Sardinia, Italy, 2010. PMLR.
Hailperin, T. Boole's 's Logic and Probability: A Critical Exposition from the Standpoint of Contemporary Algebra, Logic and Probability Theory. Elsevier, 1986.
Deng, J., Dong, W., Socher, R., L.-.,, K., and Fei- Fei, L. ImageNet: A large-scale hierarchical image database. In 2009 IEEE Conference Computer Vi- sion and Pattern Recognition, pp. 248-255 June 2009. doi: 10. 101110999V.200999595
Han, K., Vedaldi, A., and Zisserman, A. Learning to Dis- cover Novel Visual Categories via Deep Transfer Clus- tering. In 2019 IEEE/CVF International Conference on Computer Vision (ICCV), pp. 8400-8408. IEEE Com- puter Society, October 2019. ISBN 978-1-7281-4803-88 doi: 10.1109/CCC22221.000888
Deshpande, Y., Sen, S., Montanari, A., and Mossel, E. Con- textual Stochastic Block Models. Advances in Neurul Information Processing Systems, volume 31. Curran As- sociates, Inc., 2018.
Han, K., Rebuffi, S.-A., Ehrhardt, S., Vedaldi, A., and Zisserman, A. AutoNovel: Automatically Discovering and Learning Novel Visual Categories. IEEE Transac- tions on Pattern Analysis and Machine Intelligence, 44 (10):6767-6781, October 2022. ISSN 1939-3539, doi: 10. 10.1109//AM1222211.30999
Djellout, H., Guillin, A., and Wu, L. Transportation cost-information inequalities and applications to ran- dom dynamical systems and diffusions. 2004. doi: 10.1214/0091 (tt///09911999400 1790400000031..
Englesson, E. and Azizpour, H. Generalized Jensen- Shannon Divergence Loss for Learning with Noisy La- bels. In Advances in Neural Information Processing Sys- tems, November 2021.
HaoChen, J. Z.,, Wei, C.,, Gaidon, A., and Ma, T. Prov- able guarantees for self-supervised deep learning with spectral contrastive loss. In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, vol- ume 34, pp. 5000-5011. Curran Associates, Inc., 2021.
Feng, K., Li, C.,, Zhang, X., and Zhou, J. Towards Open Temporal Graph Neural Networks. In The Eleventh Inter- national Conference on Learning Representations, Febru- ary 2023.
Hou, Y., Chen, X., Zhu, H., Liu, R., Shi, B., Liu, J., Wu, J., and Xu, K. NC2D: Novel Class Discovery for Node Clas- sification. In Proceedings of the 33rd ACM International Conference on Information and Knowledge Management, CIKM '24, pp. 849-859, New York, NY, USA, Octo- ber 2024. Association for Computing Machinery. ISBN 979-8-4007-0433-9, doi: 10. 10.114572627673337777799
Fey. M. and Lenssen, J. Fast graph representation learning with PyTorch Geometric. In International Conference on Learning Representations, 2019.
Fini, E., Sangineto, E., Lathuilière, S., Zhong, Z., Nabi, M.. and Ricci, E. A Unified Objective for Novel Class Discovery. In 2021 IEEE/CVF International Conference on Computer Vision (ICCV), pp. 9264-9272, October 2021. doi: 10. 00.1009/CCCV4492222221111 .00915.
Hu, T., Liu, Z., Zhou, F., Wang, W., and Huang, W. Your Contrastive Learning Is Secretly Doing Stochastic Neigh- bor Embedding. In The Eleventh International Confer- ence Learning Representations, September 2022.
Galke, L., Franke, B., Zielke, T., and Scherp, A. Life- long Learning of Graph Neural Networks for Open-World Node Classification. In 2021 International Joint Confer- ence on Neural Networks (IJCNN, pp. 1-8, July 2021. doi: 10. (T0p:/JJCNN5228.222212..2
Huang, H., Wang. Y., Hu, Q., and Cheng, M.-M. Class- Specific Semantic Reconstruction for Open Set Recogni- tion. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(4) April 2023a. ISSN 1939- 3539. doi: 10. 10.1009TPAM...00.33000..
Ge, J., Tang, S., Fan, J., and Jin, C. On the Provable Ad- vantage of Unsupervised Pretraining. In The Twelfth International Conference on Learning Representations, 2024.
Huang, S., Zhang. Y., Fu, L.,, and Wang, S. Learnable multi-view matrix factorization with graph embedding and flexible loss. IEEE Transactions on Multimedia, 25: 3259-3272, 2023b. doi: 10. 10.109/7MM.22223315999
Gutmann, M. and Hyvärinen, A. Noise-contrastive estima- tion: A new estimation principle for unnormalized statis- tical models. In Teh, Y. W. and Titterington, M. (eds.), Proceedings of the Thirteenth International Conference
Huang, W., Yi, M., Zhao, X., and Jiang, Z. Towards the Generalization of Contrastive Self- seff-Supervised Learning. In The Eleventh International Conference on Learning Representations, September 2022.

---

Towards Understanding Parametric Generalized Category Discovery on Graphs
Hui, L. and Belkin, M. EVALUATION OF NEURAL AR- CHITECTURES TRAINED WITH SQUARE LOSS VS CROSS-ENTROPY IN CLASSIFICATION TASKS. In International Conference on Learning Representations, October 2020.
Liu, Y., Jin, M., Pan, S., Zhou, C., Zheng, Y., Xia, F,, and
Yu, P. Graph Self-Supervised Learning: A Survey. IEEE Transactions Knowledge and Data Engineering, pp. 1-1, 2022a. ISSN 1041-4347, 1558-2191, 2326-3865. doi: 10.1 2..1099/KDDDE22222377222
Jeh, G. and Widom, J. Scaling personalized web search. In Proceedings of the 12th International Conference World Wide Web, WWW '03, pp. 271 271-279, New York, NY, USA, May 2003. Association for Computing Ma- chinery. ISBN 978-1-581 13-680-7. doi: 10.1 10.11457775152. 775191.
Liu, Y., Tu, W., Zhou, S., Liu, X., Song, L., Yang, X., and Zhu, E. Deep Graph Clustering via Dual Correlation Reduction. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 7603-7611, June 2022b. doi: 10.1609/aaai htt////ai.v366...22.. v3617.20726.
Liu, Y., Zheng, Y., Zhang, D., Chen, H.. Peng. H., and Pan, S. Towards unsupervised deep graph structure learning. In Proceedings of the ACM Web Conference 2022, pp. 1392-1403, 2022c.
Jin, Y., Xiong, Y. Fang, J., Wu, X., He, D., Jia, X., Zhao, B., and Yu, P. S. Beyond the Known: Novel Class Discovery for Open- Open-World World Graph Learning. In Onizuka, M., Lee, J.-G., Tong, Y. Xiao, C., Ishikawa, Y., Amer-Yahia, S., Jagadish, H. V., and Lu, K. (eds.), Database Systems for Advanced Applications, pp. 117-133, Singapore, 2024. Springer Nature. ISBN 978-981-97 -99-8---97---7-11.
Lloyd, S. Least squares quantization in PCM. IEEE Trans- actions on Information Theory, 28(2):129- 137, March 1982. ISSN 1557-9654. doi: 10.1109/TIT. 1982. 1982.406499,
doi: 10.
0007/97-9911-7-5597
Lovasz, L. Matching Theory (North-Holland Mathematics Studies). Elsevier Science Ltd., GBR, 1986. ISBN 0-444- 87916-1.
Khosla, P., Teterwak, P., Wang, C., Sarna, A., Tian, Y., Isola, P., Maschinot, A., Liu, C., and Krishnan, D. Supervised contrastive learning. In Advances in Neural Information Processing Systems, volume 33, pp. 18661-18673, 2020.
Lu, Z., Nie, F., Wang, R., and Li, X. A differentiable per- spective for multi-view spectral clustering with flexible extension. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(6):7087-7008, 2022.
Khromov, G. and Singh, S. P. Some Fundamental Aspects about Lipschitz Continuity of Neural Networks. In The Twelfth International Conference on Learning Represen- tutions, October 2023.
Mohri, M., Rostamizadeh, A., and Talwalkar, A. Founda- tions of Machine Learning (Second Edition). 2018.
Kingma, D. P. and Ba, J. Adam: A Method for Stochastic Optimization, January 2017.
Motie, S. and Raahemi, B. Financial fraud detection using graph neural networks: A systematic review. Expert Sys- tems with Applications, 24001221566 April 2024. ISSN 0957-4174. doi: 10. 00.0116f.eswaa2223.1222
Kipf, T. N. and Welling, M. Semi-supervised classifica- tion with graph convolutional networks. In International Conference on Learning Representations, 2017.
Krause, J., Stark, M., Deng, J., and Fei-Fei, L. 3D Ob- ject Representations for Fine-Grained Categorization. In 2013 IEEE International Conference on Computer Vi- sion Workshops, pp- 554-561, December 2013. doi: 10.10097CCV..201..777.
Otholt, J., Meinel, C., and Yang, H. Guided Cluster Aggre- gation: A Hierarchical Approach to Generalized Category Discovery. In Proceedings of the IEEE/CV Winter Con- ference on Applications of Computer Vision, pp. 2618- 2627, 2024.
Krizhevsky, A. Learning Multiple Layers of Features from Tiny Images. 2009.
Pal, A., Eksombatchai, C., Zhou, Y., Zhao, B., Rosenberg, C., and Leskovec, Pinnersage: Multi-modal user em- bedding framework for recommendations at pinterest. In Proceedings of the ACM SIGKDD International Confer- ence Knowledge Discovery & Data Mining, pp. 2311- 2320. ACM, 2020. doi: 10. 00.1145/3394866.443222
Li, W., Fan, Z., Huo, J., and Gao, Y. Modeling Inter-Class and Intra-Class Constraints in Novel Class Discovery. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pp. $449-3458, 2023.
Liu, H., Yang, Y., and Wang, X. Overcoming Catas- trophic Forgetting in Graph Neural Networks. In Pro- ceedings of the AAAI Conference on Artificial Intelli- doi:
Parmar, J., Chouhan, S., Raychoudhury, V., and Rathore, S. Open-world Machine Learning: Applications, Chal- lenges, and Opportunities. ACM Computing Surveys, 55 (10):1-37, October 2023. ISSN 0360-0300, 1557-7341. doi: 14/313333661881.
gence, volume 35, pp. 8653-8666 May 2021.
10. 335.9/
12

---

Verma, S. and Zhang, Z.-L. Stability and Generalization of Graph Convolutional Neural Networks. In Proceedings of the 25th ACM SIGKDD International Conference on Towards Understanding Parametric Generalized Category Discovery on Graphs
Parulekar, A., Collins. L.,, Shanmugam, K., Mokhtari, A., and Shakkottai, S. InfoNCE loss provably learns cluster- preserving representations. In Neu, G. and Rosasco, L. (eds.), Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pp. 1914-1961. PMLR, July 2023.
Shchur, O., Mumme, M., Bojchevski, A., and Günnemann, S. Pitfalls of Graph Neural Network Evaluation, June 2019.
Sun, Y., Shi, Z., Liang, Y., and Li, Y. When and How Does Known Class Help Discover Unknown Ones? Provable Understanding Through Spectral Analysis. In Proceed- ings of the 40th International Conference Machine Learning, pp. 330133303333 33043, PMLR, July 2023.
Paszke, A., Gross, S., Chintala, S., Chanan, G., Yang, E., DeVito, Z., Lin, Z., Desmaison, A., Antiga, L., and Lerer, A. Automatic differentiation in PyTorch. October 2017.
Tan, K. C., Liu, Y., Ambrose, B., Tulig, M., and Belongie, S. The Herbarium Challenge 2019 Dataset, June 2019.
Perera, P. and Patel, V. M. Deep Transfer Learning for Multiple Class Novelty Detection. In 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 11536-11544, June 2019. doi: 10.1109/ 2VP1.2019.01181..
Tan, Z., Zhang, Y., Yang, J., and Yuan, Y. Contrastive Learn- ing is Spectral Clustering on Similarity Graph. In The Twelfth International Conference on Learning Represen- tations, October 2023.
Pu, N., Zhong, Z., and Sebe, N. Dynamic Conceptional Contrastive Learning for Generalized Category Discov- ery. In 2023 IEEE/VV Conference on Computer Vision and Pattern Recognition (CVPR), pp. 7579-7588. IEEE Computer Society, June 2023. ISBN 899----500-- doi: 10.1 0WW.CCCVRR3222.2223.0007
Tang, H. and Liu, Y. Towards Understanding Generaliza- tion of Graph Neural Networks. In Proceedings of the 40th International Conference on Machine Learning, pp. 33674-33719, PMLR, July 2023.
Tarvainen, A. and Valpola, H. Mean teachers are better role models: Weight-averaged consistency targets improve semi-supervised deep learning results. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, pp. 1195-1204, Red Hook, NY, USA, December 2017. Curran Associates Inc. ISBN 978- 1-118-60999
Rastegar, S., Doughty, H., and Snoek, C. Learn to categorize or categorize to learn? Self-coding for generalized cate- gory discovery. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 72794-72818, Curran Associates, Inc., 2023.
Rastegar, S., Salehi, M., Asano, Y. M., Doughty, H., and Snoek, G. M. SelEx: Self-expertise in fine -ne-grained generalized category discovery. In European Conference on Computer Vision, 2024.
Thomas. MTCAJ. and Joy, A. T. Elements of Information Theory. Wiley-Interscience, 2006.
Troisemaine, C., Lemaire, V., Gosselin, S., Reiffers-Maason, A., Flocon-Cholet, J., and Vaton, S. Novel Class Discov- ery: An Introduction and Key Concepts, February 2023.
Redko, I., Morvant, E., Habrard, A., Sebban, M., and Ben- nani, Y. A survey on domain adaptation theory: Learning bounds and theoretical guarantees, July 2022.
Vaze, S., Han, K., Vedaldi, A., and Zisserman, A. Open- Set Recognition: A Good Closed-Set Classifier is All You Need. In International Conference on Learning Representations, October 2021.
Ren, Y. Pu, J., Yang, Z., Xu, J., Li, G., Pu, X., Yu, P. S., and He, L. Deep Clustering: A Comprehensive Survey. IEEE Transactions on Neural Networks and Learning Systems, 36(4):5858-5878 April 2025. ISSN 2162-2388. doi: 10.1 1..100/INNLSS2224..4000
Vaze, S., Han, K., Vedaldi, A., and Zisserman, A. General- ized category discovery. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 7492-7501, 2022.
Rosvall, M. and Bergstrom, C. T. Maps of random walks on complex networks reveal community structure. Proceed- ings of the National Academy of Sciences, 105(4):1118- 1123, January 2008. doi: 10.10733pnas.0706855 0706851105.
Vaze, S., Vedaldi, A., and Zisserman, A. No representation rules them all in category discovery. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Processing Sys- tems, volume 36, pp. 19962-19989, Curran Associates, Inc., 2023.
Rusch, T. K., Bronstein, M. M., and Mishra, S. A Survey on Oversmoothing in Graph Neural Networks, March 2023.
Sen, P., Namata, G., Bilgic, M., Getoor, L., Galligher, B., and -ldd T. Collective Classification in Network Data. Al Magazine, 29(3):93-9)))) 93, September 2008. ISSN 2371-9621, doi: 10. v2009/aiaa..v9.3.22211
13

---

Wu, M., Pan, S., and Zhu, X. OpenWGL: Open-world graph learning for unseen class node classification. Knowledge and Information Systems, (3(9):2405-2430 September 2021a. ISSN 0219-1377, 0219-3116. doi: 10.1007/ Towards Understanding Parametric Generalized Category Discovery on Graphs
Knowledge Discovery & Data Mining, KDD '19, pp. 1539-1548, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 978-1-4503-6201-6 doi: 10.1115//29255033339666
Xu, H., Xiang, L.,, Ou, J., Weng, Y., Wang. X., and Zhou, C. Open-World Graph Active Learning for Node Clas- sification. ACM Transactions on Knowledge Discovery from Data, 18(2):1-00, February 2024. ISSN 1556-4681, 1556-472X. doi: 10. 145/3607144.
Virmaux, A. and Scaman, K. Lipschitz regularity of deep neural networks: Analysis and efficient estimation. In Proceedings of the 32nd International Conference Neural Information Processing Systems, pp. 3839-3848, 2018.
Yang. H.-M., Zhang, X.-Y., Yin, F., Yang, Q., and Liu, C.-L. Convolutional Prototype Network for Open Set Recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(5);2358-23770 May 2022. ISSN 1939-3539. doi: 10. 109/TPAMM.2000.304002
Wah, C., Branson, S., Welinder, P., Perona, P., and Belongie, S. The caltech-UCSD birds-200-2011 dataset. July 2011.
Yang, X., Song, Z., King, I., and Xu, Z. A Survey on Deep Semi-Supervised Learning. IEEE Transactions on Knowledge and Data Engineering, 35(9):8934 8954, September 2023. ISSN 1558-2191. doi: 10.1 10.1109TT 2022.3220219.
Waida, H., Wada, Y., Andéol, I.., Nakagawa, T., Zhang. Y., and Kanamori, T. Towards Understanding the Mecha- nism of Contrastive Learning via Similarity Structure: A Theoretical Analysis. In Machine Learning and Knowl- edge Discovery in Databases: Research Track: European Conference, ECML PKDD 2023, Turin, Italy, September 18- 22, 2023, Proceedings, Part IV, pp. 709-727, Berlin, Heidelberg, September 2023. Springer- ISBN 978- doi: 00.1007/998.3300--444222
Zhang, H. and Patel, V. M. Sparse Representation-Base Open Set Recognition. IEEE Transactions on Pattern Au-
Analysis and Machine Intelligence, gust 2017. ISSN 1939-3539, doi: 10. 10.1.............. 2613924.
Wang, H., Vaze, S., and Han, K. SPTNet: An Efficient Al- ternative Framework for Generalized Category Discovery with Spatial Prompt Tuning. In The Twelfih International Conference on Learning Representations, October 2023.
Zhang, H., Li, A., Guo, J., and Guo, Y. Hybrid models for open set recognition. In Computer Vision-ECCV 2020: 16th European Conference. Glasgow, UK, August 23-28, 2020, Proceedings, Part III 16, pp. 102-117. Springer, 2020.
Wen, X., Zhao, B., and Qi, X. Parametric classification for generalized category discovery: A baseline study. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 16590-16600, 2023.
Zhang, Q., Li, Q., Chen, X., Zhang, P., Pan, S., Fournier- Viger, P., and Huang. J. Z. A Dynamic Variational Frame- work for Open- Woon-World Node Classification in Structured Sequences. In 2022 IEEE International Conference on Data Mining (ICDM), pp. 703-712, November 2022. doi: 10. NLL1099CDD55444..22200000
Zhang, Q., Shi, Z., Zhang. X., Chen, X., Fournier- Viger, P., and Pan, S. G2Pxy: Generative open-set node classification on graphs with proxy unknowns. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IICAI '23, pp. 4576 4583, <conf-loc>, <city>>Macao</cit>>> <country>> P.R. PRR.China=ccoountry> </conf-loc>> August 2023a. ISBN 978-1-956792-00-44 doi: 10.24963/ijcai. 2023/509.
110115-021-0159440.
Wu, Z., Pan, S., Chen, F., Long, G., Zhang. C., and Yu, P. A Comprehensive Survey on Graph Neural Networks. IEEE Transactions on Neural Networks and Learning Systems, 32(1):4-22 24,,, January 2021b. ISSN 2162-237X, 2162-2388, doi: 10. N0.1109/TNNLS 202.MMS9220222292833
Xia, J., Wu, L.. Wang, G., Chen, J., and Li, S. Z. ProGCL: Rethinking Hard Negative Mining in Graph Contrastive Learning. In International Conference on Machine Learn- ing. pp. 24332-24346. PMLR, 2022.
Zhang, Q., Li, X., Lu, J., Qiu, I.., Pan, S., Chen, X., and Chen, J. ROG_PL: Robust open-set graph learning via region-based prototype learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 9350-9358, 2024.
Xie, J., Girshick, R., and Farhadi, A. Unsupervised deep embedding for clustering analysis. In Balcan, M. F. and Weinberger, K. Q. (eds.), Proceedings of the 33rd Inter- national Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 40..478-88 New York, New York, USA, June 2016. PMLR
Zhang, S., Khan, S., Shen, Z., Naseer, M., Chen, G., and Khan, F. S. PrompiCAL: Contrastive Affinity Learning via Auxiliary Prompts for Generalized Novel Category Discovery. In 2023 IEEE/CVF Conference on Computer
14

---

Towards Understanding Parametric Generalized Category Discovery on Graphs
Vision and Putlern Recognition (CVPR), pp. 3479-3488, June 2023b. doi: 10.1 111100//VVVR5279922200000222
Zhao, B., Wen, X., and Han, K. Learning Semi-supervised Gaussian Mixture Models for Generalized Category Dis- covery. In 2023 IEEE/CVF International Conference on Computer Vision (ICCV), pp. 16577-16587. IEEE Com- puter Society, October 2023. ISBN doi: 10. 101110//CV1110000022.00022222221
Zhong, Z., Zhu, L., Luo, Z., Li, S., Yang, Y., and Sebe, N. OpenMix: Reviving Known Knowledge for Discovering Novel Visual Categories in an Open World. In Proceed- ings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 9462-9470, 2021.
Zhou, D.-W., Ye, H.-J., and Zhan, D.-C. Learning Place- holders for Open-Set Recognition. In 2021 IEEE/CVF Conference Computer Vision and Pattern Recogni- tion (CVPR), pp. 4399-4408, June 2021. doi: 10.1 109/ CVPR46437.2021.0006
Zhou, J., Li, X., Ding, T., You, C., Qu, Q., and Zhu, Z. On the Optimization Landscape of Neural Collapse un- der MSE Loss: Global Optimality with Unconstrained Features. In Proceedings of the 39th International Con- ference on Machine Learning, pp. 27179-27202. PMLR, June 2022.
Zhu, F., Ma, S., Cheng, Z., Zhang, Y., Zhang, Z., and Liu, C.-L. Open-world Machine Learning: A Review and New Outlooks, March 2024.
Zhu, Y., Xu, Y., Yu, F., Liu, Q. Wu, S., and Wang, L. Deep Graph Contrastive Representation Learning, July 2020.
15

---

Towards Understanding Parametric Generalized Category Discovery Graphs
Appendix
Table of Contents
A Related Work
16
A.1 Visual Generalized Category Discovery (VGCD)
16
A.2 Open-world Graph Learning..
18
B Details of GGCD Baselines Adapted from VGCD
19
B.1
Adapting SimCLR and SupCon for Graphs
B.2 Adapting VGCD Methods for Graphs
20
C More Details of the Proposed GCL Method, SWIRL
20
C.I Total Loss Full Procedure SWIRL
C.2 The Gradients of InfoNCE-style Loss with Pair Weights
21
Some Proof Auxiliaries
D.1
Auxiliaries for Theorems Parametric GCD Classifiers in Sec. 3
................................
22
D.2
Auxiliaries Theorems on (Graph) Contrastive Learning Presented in Sec. ................................
E
Proofs of Theorems Parametric GCD Classifiers in Sec.
25
E.1
Proof of GCD Upper Bound in Theorem 3.5
25
E.2 An Illustrative Example of Theorem 3.5
................................
28
E.3 The Proof of Entropy Regularization Trick in Proposition 3.9
28
F
Proofs of Theorems on (Graph) Contrastive Learning Presented in Sec.
29
F.I Proof of Theorem 4.1
29
F2 Proof of Corollary 4.2
................................
32
F3 Proof of Theorem 4.3
33
G
Supplementary Details of the Experiments
G.1 Evaluation Protocol
33
G.2 Hardware and Software Environment
................................
G.3 Experimental Details for GCD Upper Bound Theory (Sec. 3.4)
................................
35
G.4 Experimental Details for GCL. Theory (Sec. 4.3)
................................
35
G.5 Experimental Details for SWIRL on Synthetic CSBM Graphs (Sec. 5.1)
36
G.6 Experimental Details for Real-world Experiments (Sec. 6)
37
G.7
Hyperparameter Analysis for SWIRI on Synthetic CSBM Graphs
39
A. Related Work
A.1. Visual Generalized Category Discovery (VGCD)
The Generalized Category Discovery (GCD) task was first introduced by Vaze et al. (2022) for visual image data (Krizhevsky, 2009; Deng et al., 2009; Tan et al., 2019; Krause et al., 2013; Wah et al., 2011). Concurrently, Cao et al. (2021) proposed the same setting under the name open-world semi-supervised learning. The GCD problem a composite task that involves (i) semi-supervised classification of known-class samples and (ii) clustering of novel-class samples. Thus, it is closely related
16

---

Towards Understanding Parametric Generalized Category Discovery on Graphs
to both semi-supervised learning (Yang et al., 2023) and (deep) clustering (Lloyd, 1982; Xie et al., 2016; Lu al., 2022; Ren et al., 2025).
Vaze et al. (2022) developed a simple yet robust Visual GCD (VGCD) method, Vanilla GCD, which first learns image representations through semi-superrised contrastive learning using SimCLR (Chen et al., 2020) and SupCon (Khosla et al., 2020), followed by clustering these representations using a Semi-Supervised K-Means (SS-KM) classifier. SS-KM enforces old-class samples with known labels to be assigned to their corresponding old-class clusters, enabling both classification for old classes and bluseer-based discovery of novel classes. Subsequent research has evolved along two main directions. The first direction aims to enhance the representation learning component while maintaining a non-parametric classifier. The second direction investigates replacing the aan-aaametrric SS-KM, which is inefficient for mini- inference, with parametric classifier, such as a prototype-based classifier.
Non-parametric VGCD Methods. In GCD, contrastive learning is employed for representation learning, with the key challenges being the construction of positive and negative sample pairs and the selection of an appropriate pretext task. Subsequent methods primarily focus on improving these aspects.
DCCL (Pu et al., 2023) constructs a graph adjacency matrix based on sample embeddings and applies InfoMap (Rosvall & Bergstrom, 2008) for clustering on the graph to obtain conceptual labels. It then computes cluster centroids for each concept and performs contrastive learning at both the iistancc-to-concept and instance-to-instane levels. After representation learning. SS-KM is used to obtain the final results. PrompiCAL (Zhang et al., 2023b) builds K-Nearest-Neighbors (KNN) graphs in the embedding space and determines edge weights by counting the number of shared KNN neighbors between two nodes. It then applies graph diffusion capture long-range sample relationships. Using predefined edge weight thresholds and labeled data, it constructs binary affinity graph G, where endpoints of edges in G are treated positive pairs, while all other sample pairs serve as negative pairs for additional contrastive loss. KS-KM is used to generate the final results after representation learning. To address the GCD problem without prior knowledge of the number of categories, Zhao et al. (2023) proposed parametric semi-supervised clustering variant of Gaussian Mixture Model (GMM), GPC, which alternates between contrastive representation learning and category number estimation. Upon completion of training, both the encoder and cluster centers are obtained. During inference, classification is performed by identifying the nearest cluster center. Inspired by the human categorization system, Rastegar et al. (2023) propose InfoSieve, representation learning method that seeks optimal hierarchical sample encoding in the embedding space. SS-KM is used for final clustering. For fine- ane-grained semantic distinction tasks, Rastegar et al. (2024) further introduce SelEx, a representation learning method designed to mitigate the disruption of fine-grae tine-graneed semantics caused by data augmentation while providing flexible hierarchical category semantic structures.
Parametric VGCD Methods. Without additional constraints, a parametric MLP classifier tends to assign new-class test samples to the most similar old class, resulting in a severe bias towards old classes. Therefore, in parametric GCD, beyond improving representation learning, appropriately handling the classifier's class preference is equally crucial.
Wen et al. (2023) investigated why parametric classifiers underperform compared to the non-parametric SS-KM and identified bias towards old classes as the key issue. To mitigate this bias, they introduced Entropy Regularization (ER), which encourages the model's overall prediction distribution align with a uniform class distribution. Their method, SimGCD, was the first parametric classifier to surpass Vanilla GCD. (Chiaroni et al., 2023) proposed InfoMax, which maximizes the mutual information between embeddings and a prototype classifier's 's's prediction distribution. They incorporated known labeled samples into parametric mutual information maximization objective with a weighting factor X. To address class imbalance in long-tail distributions, they further designed strategy for selecting X. Cao et al. (2024) observed that in later training stages, SimGCD may misclassify old-class samples as new classes, leading to a bias towards new classes. To counteract this, they introduced LegoGCD, which identifies potential known samples in unlabeled data and applies entropy regularization to stabilize their predictions.
The methods mentioned above construct positive and negative sample pairs and apply contrastive loss following SimCLR and SupCon, without leveraging the rich semantic information embedded in old-class sample labels and representations. As result, they struggle to generate high-quality pseudo-labels for training the classification head and encoder. Several methods aim to address this.
GCA (Otholt et al., 2024) employs unsupervised clustering to form many small local clusters and then aggregates these clusters into target classes using provided labels and neighborhood relations. The aggregated results facilitate the construction
17

---

Towards Understanding Parametric Generalized Category Discovery on Graphs
of positive and negative pairs, which are then used train the encoder f and MLP classifier h with binary cross-entropy loss on every pairs. Unlike non-parametric methods, GCA requires clustering on the entire dataset only during training to generate pseudo-labels, while at inference, it efficiently supports mini-batch predictions using only the classifier h. Vaze et al. (2023) tested SimGCD on the more challenging Clever4 dataset and found that it performed poorly on new classes, which they attributed to the low quality of pseudo-labels assigned to new-class samples. Inspired by Mean-Teacher semi-supervised learning (Tarvainen & Valpola, 2017). they introduced jGCD, a parametric GCD method designed to be more robust to noisy labels (of new-class samples). SPTNet (Wang et al., 2023) introduced trainable visual prompts combined with fine-tuning model parameters to fully exploit the capabilities of pre-trained visual models and better adapt to the GCD task. All three methods GCA, ,GCD, and OPPTNet-incorpone uniform label distribution as a prior to mitigate bias towards old classes
Current I. Limitations. While these methods have achieved success, their design and evaluation have primarily focused on image datasets, overlooking the widely prevalent graph data. To address this gap, we introduce the node-level Graph GCD task and establish multiple baseline methods. More importantly existing GCD methods have not thoroughly investigated the mechanism by which knowledge from old categories facilitates novel category discovery. In related task, Novel Category Discovery (NCD), Sun et al. (2023) proposed NSCL., graph-theoretically inspired representation learning algorithm, and analyzed the intrinsic mechanisms of novel category discovery from the perspective of spectral contrastive learning theory (HaoChen et al., 2021). However, GCD is much more complex than NCD, as it involves not only distinguishing novel categories but also ensuring accurate classification of old-class sample. Furthermore, existing GCD methods differ from NSCL, making its theoretical framework inadequate to answer the fundamental question: "When and how do old classes help generalized category discovery?" In this work, we systematically address this question in the context of parametric GCD. Since different methods employ diverse representation learning modules, we aim for generalizable conclusions by conducting theoretical analysis of classifier performance within the embedding spaces induced by encoders. After establishing the necessary embedding conditions for good GCD performance, we further examine whether the learned embeddings from graph representation learning modules satisfy these conditions. Taken together, these efforts represent our first systematic attempt to answer: "When and how do old classes help (parametric) generalized category discovery (on graphs)?"
A.2. Open-world Graph Learning
In real-world applications, deployed models frequently encounter novel categories that were unseen during training. This challenge, inherent to open-world machine learning, has been extensively studied in non-graph data (Parmar et al., 2023; Zhu et al., 2024). Existing non-graph approaches for handling novel categories can be broadly classified into three paradigms. 1) Open-Set Recognition (OSR): Accurately classifies known-class samples while assigning all unknown-class samples to single "unknown" category (Bendale & Boult, 2016; Zhang & Patel, 2017; Perera & Patel, 2019; Zhang et al., 2020; Vaze et al., 2021; Zhou et al., 2021; Yang et al., 2022; Huang et al., 2023a). 2) Novel Category Discovery (NCD): Clusters unknown-class samples into distinct novel categories (Han et al., 2019; Zhong et al., 2021; Han et al., 2022; Li et al., 2023; Troisemaine et al., 2023). 3) Generalized Category Discovery (GCD): Simultancously classifies known-class samples and clusters unknown-class samples, reviewed in Sec. A.I.
However, progress in open-world graph learning remains limited. 1) Graph OSR: Wu et al. (2021a) introduced Open WGI. the first transductive OSR model for static graphs, while Zhang al. (2022) proposed OSSC, an OSR model for discrete-time dynamic graphs. The G2 Pry model (Zhang et al., 2023a) addresses inductive OSR static graphs. More recently, Zhang et al. (2024) handled inductive graph OSR tasks in the presence of in-distribution samples with incorrect labels. 2) Graph NCD: Jin et al. (2024) proposed ORAL, the first transductive Graph NCD method for static graphs. Hou et al. (2024) introduced NC-NCD, a two-stage training framework where only labeled old-class nodes are available in the first stage, and only unlabeled new-class nodes are available in the second stage. Although NC-NCD considers all classes during testing, its staged training paradigm inherently leaks side information about the distinction between old and new categories, making it less challenging task than GCD, where the ability to distinguish old and new categories is crucial. 3) Other Open-Worke Graph Learning Tasks: Xu et al. (2024) explored World Graph Active Learning, where the model selects the most valuable nodes for labeling upon the appearance of novel-category nodes and then retrains accordingly. Galke et al. (2021): I): Liu et al. (2021); Feng et al. (2023) studied Continual Learning on Evolving Graphs, where OSR, NCD, and GCD information is incrementally revealed to the model, making catastrophic forgetting the key challenge.
We follow the transductive setting (Vaze et al., 2022), focus on the GCD tasks for static graphs, and extend multiple VGCD
18

---

Towards Understanding Parametric Generalized Category Discovery Graphs
baselines graph data.
B. Details of GGCD Baselines Adapted from VGCD
VGCD methods can generally be broken down into two parts: 1) contrsative learning to train an encoder f. and 2) classification with a semi-supervised classifier h that can be either non-parametric (e.g., SS-KM) or parametric (e.g., MLP). For graph adaptation, we focus on the representation learning part, because effective GNN encoders can encode graph structural information into node embeddings, making the explicit use of structures not mandatory in the classification part.
There numerous graph contrastive learning methods available (Liu et al., 2022a; Zhu al., 2020; Xia et al., 2022; Liu et al., 2022c; Huang et al., 2023b; Liu et al., 2022b; Deng et al., 2025). However, to minimize modifications to the VGCD method while deriving the GGCD baselines, we select GRACE, which is most similar to SimCLR, as the foundation for the graph representation part.
B.1. Adapting SimCLR and SupCon for Graphs
The representation learning part of VGCD methods is typically build upon SimCLR (Chen et al., 2020). The popular graph contrastive learning (GCL) method GRACE (Zhu et al., 2020) directly extends SimCLR to graph data by proposing the graph data augmentations and using GNN encoders. Two graph views 91 and G2 are generated from input graph = (A, X) by applying augmentations like edge dropping, node feature masking, or subgraph sampling. shared GNN encoder f (A, X) Z maps nodes in each augmented view to embeddings. For node u, its representation
SimCLR - GRACE:
in 91 and G2 is separately given by:
2 (1) = z = 1/ (1),)))),
(2) = 2 =I X2)).-
(12)
(1) (
Without loss of generality, we concatenate these two views into Z =
such that the positive sample of node i is
i + n if comes from view / j= n i comes from view
That is 2; = Zitn = (22) i S n and 2j = k,-n zi-n if <is 2n. Then the InfoNCE loss LNCE (Gutmann Hyvärinen, 2010) is used train f. In terms of cosine similarity cos(:,)), this loss encourages the alignment of the same node's embeddings across different views while separating those of different nodes.
2m 2s, 2;)/T]
exp (20,
(NCE(1) = INNCEEZ, 2z) ) = log
(13)
Σ
Ei=1 exp (cos 2/)
And the loss over all nodes is
2n LNCE Σ 2=1
2n
exp (cos(z;, 22; 2;)/T} > 0.
(ICE())= =-
Σ log
(14)
2n Di=1 exp (cos Zi 2 2/)TT
SupCon -> GRACE-SC: Since SupCon (Khosla et al., 2020) differs from SimCLR solely in its use of labels to construct positive and negative pairs, it can be easily adapted to graphs by building on GRACE. We replace the InfoNCE loss in GRACE with the SupCon loss
Lsc(1)
Lsc(Z,,2;)
-1
Σ
log
exp [cos( 2i, 2,)/T}
(15)
mi jES(
Σ 1=1 exp (cos(z,, 2,, T/]
1
log exp fcos( Zi /
Lsc Lsc(t)=
=
Σ
(16)
m4
Lnm Li= exp coos z,, /T}
==1
jES(
where S(i) includes all augmented nodes with the same label as node i, and m, is the cardinality of the set S(i) \ i. We refer this SupCon adaptation as GRACE-SC.
19

---

Towards Understanding Parametric Generalized Category Discovery on Graphs
B.2. Adapting VGCD Methods for Graphs
Vanilla GCD (Vaze et al., 2022) uses SimCLR and SupCon for representation learning, and then Semi-Supervised K-means (SS-KM) for label assignment. SS-KM utilizes the known old-class nodes derive old-class centroids and enforces the assignment of these nodes to their respective old-class centroids. Unlabeled nodes are subsequently clustered following the standard K-means algorithm. Adaptation: We replace SimCLR and SupCon with GRACE and GRACE-SC introduced in Sec. B. All other components remain unchanged. The total training loss is
LVamillaGDD (1 02) + a2L.sc,
0/2
UNO+ (Fini et al., 2021; Vaze et al., 2022) extends the celfsuueeeeiee CL method SwAV (Caron et al., 2020) to the semi-supervised GCD task. It employs a parametric classifier to predict old and new class labels for each augmented view. cost matrix then constructed based on the predictions to solve the Optimal Transport (OT) assignment, where the assignment of one view serves as pseudo-labels for the other view. Adaptation: Data augmentation follows GRACE, with f(+) replaced by a GCN. All other components remain unchanged.
SimGCD (Wen et al., 2023) adopts the representation learning methods in Vanilla GCD while replacing SS-KM with a parametric prototype classifier. The classifier provides predictions for two views, and then the prediction for every view is distilled as the pseudo-label to the other view. This approach is Self-Distillation (SD) (Assran al., 2022) with the SD loss
Lip(i)
LCE (hy. h,)
2n
2n
LSD
(iD = Σ Dos(h h.).
(17)
For the labeled samples, SimGCD employs the Cross Entropy (CE) loss
LCz Σ De
(18)
iEDz
Additionally, SimCGD utilizes the Entropy Regularization (ER) loss LER (Assran et al., 2022) on the entire D to mitigate the bias towards old classes, which becomes popular later in VGCD (Vaze et al., 2023; Wang et al., 2023).
LER = -H(h) =
log h
(19)
h
2n Σ h; 1E2n
(20)
Finally, the training objective for SimGCD is
LSimGDD = (1 (INCE + LSD LnLER) + a2(Lsc + LCE),
an 022 >
(21)
Adaptation: We replace SimCLR and SupCon with GRACE and GRACE-SC introduced in Sec. B.1. All other components remain unchanged.
After adapting these VGCD methods for graph data, the GNN encoder (e.g., GCN) maps the graph data into the embedding space, i.e., f (A, X') > Z. And the final prediction is made by the parametric or non non-maraetrric classifier h Z - V'c
where V' is the set of all probability distributions over C categories, i.e., Vc {y RC Σ ye =1]. Unless otherwise specified, in the following content, we will refer to the adapted versions of VGCD baselines for graph datasets directly by their original names. For instance, the adapted version of SimGCD will still be referred to as SimGCD.
C. More Details of the Proposed GCL Method, SWIRL
C.1. The Total Loss and Full Procedure of SWIRL
20

---

Towards Understanding Parametric Generalized Category Discovery Graphs
Algorithm 1 The full procedure of SWIRL
Input Data: The graph 9 (A, X) with E edges and do node feature dimensions; The full node set D (A, {xx, 1=);; The labeled subset Dr = (A, {(x,, ys) (ii)) of Co old classes; The unlabeled subset Dy of nodes from all C > Co classes.
Model: The GCN encoder f: (A, + Z and the MLP classifier h :
V/c
Common Hyperparameters: The edge drop rate pe and the feature drop rate pz in data augmentation module; The training epochs T; The loss weights a1 2. and a2 0.35.
SWIRL Hyperparameters: The prototype number K 2 C; The repulsion force scale s; The weight (11 of the SWIRL loss.
Output: The predicted labels for all unlabeled nodes.
1: while T' do
2: Perform SS-KM on Z to get K prototypes {s'..... ..... sK which include C. old prototypes O = {s ..... ....,,s))..
3: Based on Z, compute I.SWIRL with Eq. (11), LNCE with Eq. (14), LEN with Eq. (19), and LoE with Eq. (18).
4: Compute the total training loss LSWIRL = (1 (LNCE + B.LLSIIL + aILEn) + a2LCE.
5: Backward to update f and h.
6: t t 1.
7: end while
8: Set the model (f and h) "eval' mode and make predictions.
C.2. The Gradients of Ittyle Loss with Pair Weights
Our SWIRL loss can be viewed as weighted InfoNCE-style loss. Here, we analyze the impact of the weight r(i, k) on the gradient of the loss function w.r.t. the pairwise distance between samples, i.e., the repulsion force.
exp ( (z; //T
L log Ex r(i, k)) exp (- (Zz,, 2x)/T}
D(2i, 2,) + log
2n
ki),k) exp f D-D(Z,, 2x) 2T)
T T> 0
Differentiating L with respect to the positive-pair distance D(2s, 22) leads to
Th
r(i,j) exp( D(2;, (
(22)
(z 24)
T E r(i, (i) e 2/)
Similarly, we get the gradient w.r.t the negative-pair distance D D(z,, Zit)
r(i, k) exp { D (z, 2/) }
(23)
aD(z, ZR.
Σ r(i, k²) exp { D Zi, Zx: )/T}
Denote by p(k(i) the softmaxed weighted similarity
r(i exp { D(z, 24 1/3
p(k]))
2n Ek=1 r(i, exp 1-D(z, z
then we
TTg
1 - p(pl)))))
(24)
0D @D(,, 2,))
p(k(())
(25)
OD(z, Zk.
For positive-pair (i,j)
When increasing rii,j) and thus p(jlt,, the positive-pair distance gets a smaller gradient magnitude as Eq. (24) and the attraction slowed down.
Conversely, decreasing r(,,)) causes a stronger attraction force that brings and j together.
21

---

Towards Understanding Parametric Generalized Category Discovery Graphs
For negative-pair ki
When increasing r(ú, k) and thereby p(k]i), the negative-pair distance gets a larger gradient magnitude as Eq. (25) and the repulsion accelerated.
Conversely, decreasing r(i, k) leads to a weaker repulsion force.
D. Some Proof Auxiliaries
D.1. Auxiliaries for Theorems Parametric GCD Classifiers in Sec. 3
Theorem D.1 (Bolley al. (2007), Theorem 2.1). Let μ be probability measure in the metric space (Z,D(; D(,,)) that admily square-exponential moment. That for any 22 2
I (aD'(an dp((zz) t00,
or equivalently μ. satisfies the Talagrand inequality Ti (c()) (1) & V Hrll),, > 0 (Djellout et al., 2004), where Wi(n, p)) is the Wassersteom distance. Denote by fa Em= 82, the corresponding empirical measure defineded sample of independent variables (za) drawn from μs. Then, for any d' >> dim(2 2) and d' <, there exists constant No
determined only by d', d', and some eqquare-eppoenee moment of p. such that for any > O and N 2 No max (5-(d+22)
Pr (r exp (-ENe))
(26)
And by setting exp
N-2 8, follows that with probability least 8,
2 Nc
W)( S
In
(27)
8"
Theorem D.2. Given a hypothesis h > Sc that outputs a prediction in a [C]-dimensional simplex (i.e., non-negative entries summing to 1), we denote the loss on one sample Ys) that adheres to Assumption 3.2 by T. I(21, Ys). Let the empirical mean loss on n samples (Zi, Yis.yile Yn and the generalization loss respectively be
A(h)
Σ 1=1
Li Σ L(z..y)) 1=1
R(h) L(z,))((,N))
Then holds that for e > 0, Pr (1R(()) R(h)] 2 $) < 52 2xxp(-22is -2n= S2). And with probability at least 1
S2
2 In
R(h) < R(h)
(28)
2n
Proof. The loss L3 bounded S) according to Assumption 3.2. Directly applying Hoeffding's Inequality finishes the
proof, similar to Corollary 2.10 in (Mohri et al., 2018). Ineq. (28) is obtained by setting 2 exxp(22ne" /see 6.
Lemma D.3. L(..)) convex function w.r.t. one input parameter given the other fixed, then it follows that
Eaz-p, F. ~p. ~p_, I(h(z), 2 [. h(2),
(12,), Bz up. l((zz)))))
22

---

Towards Understanding Parametric Generalized Category Discovery Graphs
Proof. Since L is convex function, have, according Jensen's is inequality, that
pu(()) / Pu(z (L(())) hlz))) Egrp Ex ~nw L(h(z), ((()))(()))))))))))))))))))))h))
(29a)
Pu Pu(())dz [ Pulz (L(()))((()))))))))))))))()))))) h(z ()dz
(29b)
2 (,(())( d))
(29c)
2 ((B(M))),
(29d)
Lemma D.4. Given of Liiisshctt transferable hypothesis h (Assumption 3.4), the union of regions where the transferable Lipschitzness does not hold denoted by
N {Z b2) L(h((z)) AD(Z1, z2)}
where À > O, . is metric in Z and ((:-)) satisfies Assumptions 3.3 and 3.2. Then it holds that
JEENOP kL(h(zi), ((22)d u), 1)) kSØ(1)+
/ (2xcy=
u), (22,1)).
(30)
Proof. In the following proof, Ineq. (3la) comes from that L(h(zz),,(( is bounded by S in the region (2 x Z) \ Ω (see Assumption 3.2). Ineq. (31b) is due to the definition of the region Q2 which admits the transferable Lipschitzness defined in
Assumption (3.4). Ineq. (31c) is the result of non-negativity of norm D.
M J kL(h(z)), ((2)))))))(())))T((((( (z2,
[ ([(h()))) / T((2), u), (22, dz) dudzzdl
[ kL(h(zz), h (2 dzpdzz ( T(21, Z2) 1/21, uy dudd
[ (L(h(z)), ((2)) d2)
Jzzz
AL(b(Z)), 22 dz)zzizz + / (L((z)))), ((22) (z), 22) 22) dz2
< //
ST(21, 22) + / M() 22 dz d22
(31a)
(ExZ)10
I k5 {
<(2,, 22 d2) + / kAD(Z1, (2) dz)
(31b)
(2x2)10
= k50(1)+ kAD(Z),
2y ) JT Zz) dz
n
s k(S((a)+ [
kAD Z2) Z2) dz
(31c)
Jzzz
/ /[Excp 22)(2 u), ())
kSO(A)+
(31d)
Lemma D.5. Given a function h² > Ye and two joint distributions p(zı, u) and p(zz,1) 1) over the space 2 x C, the
23

---

Towards Understanding Parametric Generalized Category Discovery Graphs
following expectation about L: Ve Vc + Rzo over the coupling distribution ((21, u), (22, hold.
MEeOP [((h(zz): L(h (Z2)) d (2,, ())
I p(a1,
- 2xx
2xc
Proof. The proof is substantially based on the definition of coupling, which reads that p(z1, u) and p(zz, 1) are two marginal distributions of it.
JEEOOP -1(())))))))-(((()))))) L(h (z2) y²)) dr((z), u), (22,1))
(32a)
((h"(z)), (() (22, ())
(32b)
(2xe)
= -eeror (21), u), (21, 1)d(22,1)
-
(2x0) L(h" (Z2) (Z1, u), (zz. l)) u)d(zz.1)
(32c)
=J
JzxC T((21, u), (2) (22, ())
(21), (z)
2xc
-S (((21, (zz, 1))((1))))
L(h" (Zz), y' )d(zz,1)
(32d)
2xe
2xc
= -J p(2), u) y
p(z2, ()Lhh")L(""(a )d(22,1).
(32e)
2xx
D.2. Auxiliaries for Theorems on (Graph) Contrastive Learning Presented in Sec. 4
Theorem D.6 (Assel et al. (2022); Theorem 1). The Pairwise Markov Random Field (PMRF) on the graph Wis with the unnormalized density function
Ju W)
II (UJE
k(2; - We..
Let each category correspond to a graph connected component, then Nd can be orthogonally decomposed into So= =ker L) & Rd and S (ker L) Rd where L is the graph Laplacian matrix of W. If k Awg--interrbbbeee and bounded above Ag almost everywhere, then fu(Z, W) is >s,- -integrable.
Lemma D.7 (Tan al. (2023); Lemma 2.4). Suppose the space X constructed by M spaces X1
X2
X XM-
On the m-th subspace there are probability distributions Pm and Qm over Xm. Then the cross entropy between the joint distributions P P1 Pa X
@ PM and = Q1 & Q2 8 Qm can be decomposed into all subspaces
DCE (P)() & EE log Q(x)
Σ Dc
Lemma D.8. k shift invariant kernel, then fr (Z, W) is not integrable on So-
24

---

Towards Understanding Parametric Generalized Category Discovery Graphs
Proof. With the shift property of k, we readily get
(z, W)
fu Zo, W)
II k(z; 20,i, 20.1) Wyy (KJ)
II k(z; 20,i, 20.3) W/s
(33)
(1))(N
Wis = fz, W), II 21),,
=
(1
where Eq. (33) is because that k(z; 2, Zo W # only when j is from the same category as i (i.e., Zo.: = Zo.j).
In contrast, if they are from different classes (and hence clusters), k(z; 20 2j Zo.s) z0.s)W.. Wi = 1 contributes nothing to the density function. Such invariance and non-negativity of fx makes not integrable on Sg.
E. Proofs of Theorems on Parametric GCD Classifiers in Sec. 3
E.1. Proof of GCD Upper Bound in Theorem 3.5
Theorem E.1 (Restate Theorem 3.5). Let Assumptions 3.2, 3.3 and 3.4 hold and h be the optimal hypothesis that minimizes the GCD loss Eq. (5). Let n. Ei my and nu En be the total numbers of old and new class samples, respectively. Then there exists, d' and n1, such that for ny > nh, ng > ni, and all X > 0, Lie is bounded as, with probability at least w (8, w > 0),
(h) SaF + (2+
(2
1 + 1/ DKi((Pl) + 2Eu + Eg + Ta,
52 ln
2
To -2 (2) /
2n'r
+ +2 rSo(A) + V log 8 (TT
Vnc
where b= P E U), Pe is the uniform distribution over C, h = (()) is the expected prediction over both the old and new data, and pclz, y) and (2 y) are respectively the empirical old and new joint distributions. W is hereafter abbreviated W. n'c is the number of old-class training samples while ne/ra, nu is the total number of old-/new-class samples in the whole embedding dataset D
Proof. We first expand the GCD loss
(he = (Lc((h) + Lu(h) +y (C) 8,7 0,
(35)
1
and then bound the consequent components. By finding the upper bounds for these components, we successfully connect the old-class and nlw-class data with the Wasserstein distance between joint (embedding, label) distributions.
25

---

Towards Understanding Parametric Generalized Category Discovery on Graphs
Step 1 We first tackle Li (l),, leaving the entropy regularization to later.
(h) =BLc(h) + (h)
(36a)
=8 Σ (c())Exzp:LLh(1 I(h(2), +
Σ
pu (p(()) E.t h(zzt)
(36b)
IEC
wEll
Σ (u)
Σ pu T Bu--rp (((2)),((z)))
(36c)
NElL
aFu
S Σ Pre(u) [Berspu Eattip L(h(z), 1: (z)) 1(10((2) (z") + I(h" (2.) (x())
(36d)
NEW
+ a Σ pr((u) Σ (u (-Eapp ~p LL((2), h(2 )>l +B Σ (pc ((((z),)))
(36e)
well
aza'
IEC
Fi The repulsion force between new classes
=2 Σ pu( Exmp, ( (z)) +
Σ NEL
Ex- L(h (2) (z+))
(36f)
uell
+ aF1 + 3 Σ ((
(36g)
IEC
Fu: The estimation enror new class
Ee:
The estimation error on data
pu Exx L(M(z), E
L(()) taFi
(36h)
uEl
IEC
+ (2+ 3) Σ Pa(l))a-pi pm L(h"
(36i)
IEC
Rc(h*): The old class
Σ weld
Pu Ezzp Ez ~p. L (2), (z
L(h
(36j)
lEC
The attraction within new
Ti: The interplay between old and new classes
=2Eu Ec aF + (2 Rc +T1
(36k)
Step 2 Now we further cope with Rg(h*).
Like classical generalization bound single hypothesis (Mohri al., 2018), relate our bound with the empirical loss
Re(h²) = Eiec (C)()) L(h" (z), by applying Theorem D.2 to Rc(h"). Then with probability at least 1 - we have
S2 2n
Re(h") & Rc(h") +
In
(37)
Step 3 We investigate the interplay between old and new classes Ti, which is the core of this work. To simplify the symbols, we abbreviate (c()) to p()), (u) to p(u), (2, u) to p(z, u). pc(z, 1) to p)z,
Ineq. (38c) comes from the triangle inequality of norm.
Eq. (38h) is consequence of that the coupling π ((21, w), (22, ()) between p(zI, u) and p(z2, I) (i.e., joint distribution of (21, u) and (22, I)) is defined to have the marginals p(z1, u) and p(22, 1). Thus we can recover Eq. (38g), given any or the optimal coupling π minimizing the final bound, as stated in Lemma (D.5).
To simplify the process and enhance understanding, we slightly abuse notation by replacing the summation symbol over u and with the integral symbol. Note that this substitution does not affect the overall correctness of the reasoning logic as the
26

---

Towards Understanding Parametric Generalized Category Discovery on Graphs
expectation operator is linear.
T
Σ Bar, L wEM
L(h (2)
p(l)Ezzpi (2))()).))
(38a)
IEC
Ex(1) /
Σ p(u)
dddz +
(38b)
WEM
IEC
Σ p(u) [L(H(()) I(y", hr (2+)2) }}] Pu Pu(z))u(z* ddddzt 2 22> p())) /
(38c)
wEHl
IEC
Σ
Ep(w) p((u) [f ( / L(y", 10 (0 (ul(t
- ΣE(() p()) / 5()(()))')m(( (38d)
uEll
LEC
-2
Σ plu) ((
Σp(() / L(0())))
(38e)
LuEl
IEC
-2
Σ
Ep(l) I y(
(381)
LuE
IEC
| ueu 22
dud - /Eco L(h p(zz, dzzddl
-2
(38g)
yt) , / [L(h(Zz). L(h' (zz))
du ((Z), u), (z)
(38h)
(2xex²
=2
(z2) ((((
(22) y*) (22) ( u), (22,1))
(38i)
(2xO)²
22
- - 11 1
(22), d u), (22,
(38j)
(2xe)²
22
(21(" - | 11(4 (22), (22). x0)r dr ( u), ())
(38k)
(2x0)2
L (zz). So(1)) / [Exc]] [rAD(Z), -((0 ((x x') || do ((z), u), (22,1))
2
(381)
22 (S)(A) [ SEEXCTP [rAD(Z), 22) L(y", y()] dr dr((2), u), (22, 1))
(38m)
-2 (A)) + WTT(p(z, u), 1)2
(38n)
Ineq. (38k) is because of the r-Liipchitzness of the discrepancy function I, in its first argument (Assumption 3.3).
Ineq. (381) holds owing to Assumption 3.4 and Assumption 3.2, which lead to the term r:S((A) that covers the sample space regions violating the transferable Lipschitzness claimed in Assumption 3.4. A detailed explanation about this can be found in Lemma (D.4). (pi (z, y) (z( y))
Ineq. (38m) follows from the triangle inequality of L. (T u) p(z, ()) is the discrepancy between the underlying distributions, which can be only estimated via the empirical distributions p(z, u) and ().
Eq. (38n) is given by Definition 3.1. According to Theorem D.I, it holds that with probability at least 1 - 5
Ti < (A) + (f u), f(2, 1)) + WT (p(z, u). ((z, u)) + (p(z, 1), [)]
2 V ā 5
2
(
1
1
= rSO(A) + WT (1(z, u), u(, ())
log
+
(39a)
Tnu
/nc
The estimated interplay between old and new classes
Here the first inequality is because Wasserstein distance a valid metric and hence satisfies the triangle inequality. And the second equality is obtained by setting the probability thresholds in Theorem D.I to 6/2 for WT (p(z, u), p(z, u)) and (y((, 1()
27

---

Towards Understanding Parametric Generalized Category Discovery on Graphs
(b)
(c)
(d)
(e)
Figure 5: An illustrative example of Theorem 3.5 with 2 new classes and 2 new classes. The GCD loss upper bound for all other cases is higher than that of case (c). (a) Poor knowledge transfer: The lion is far from cat, and sports cars are far from truck. The blue segment (cat-truck distance) cannot constrain lion-sports car separation. (b) Unconstrained new-class separation: Though new classes (lion, sports cars) may naturally separate, this distance is not unconstrained by old-class knowledge. (c) Ideal case: Semantically related old-new classes (e.g., cat-lion, truck-sports car) cluster appropriately. (d) Misaligned semantics: Global representation distances resemble (c), but semantically incoherent (e.g., cat near sports cars). Thus, the old-new Wasserstein distance (Def. 3.1) is significantly higher. (e) Loss of reject capability: New classes (lion/sports cars) overly overlap with old classes (cat/truck), While Wasserstein distance is small, the model fails to reject ambiguous samples (old vs. new class), leading to large (Pl(Pel)h) in Eq. (8a).
Step 4 The probabilistic inequalities (39a) and (37) are then combined. According to the Boole-Fréchet incqualities (Hailperin, 1986), we have, with probability at least w 6,
Ti + Re(h") < The sum of two upper bounds.
Substituting the upper bounds of Tiand R2(h") into Eq. (36k) reaches the upper bound on (h)..
Step 5 In sequel, the upper bound on y DDLL
given in 3.9 is substituted into Eq. 35, which finishes the proof.
E.2. An Illustrative Example of Theorem 3.5
Suppose we have a total of four categories: two old classes (cats and trucks) and two new classes (lions and sports cars). After training on feature-label paired data from the two old classes, the classifier has already achieved strong discriminative performance in distinguishing between the old classes (cats and trucks). In the representation space learned using InfoNCE and SupCon contrastive losses, the representations of cats and trucks also well-separated.
At this stage, in the representation space derived by the encoder, there may exist five typical relationship patterns between old and new classes, as illustrated in Fig. 5. Among these, the third scenario (Fig. 5c) best aligns with human intuition, and it corresponds to the smallest upper bound of the GCD loss in Theorem 3.5. The other scenarios represent undesirable cases that we aim to avoid. Notably, Fig. 5d may be casily confused with Fig. 5c; however, in Fig. 5d, , semantically similar old and new classes are actually not adjacent, which contradicts our intuition and results in a larger GCD loss upper bound.
E.3. The Proof of Entropy Regularization Trick in Proposition 3.9
Proposition E.2 (Restate Proposition 3.9). If Pu, Pe E Vc are uniform distributions over U and C respectively, and the data distribution is class-balanced, then it follows that
DRI(Pu < ( DKa(Pellh),
(40)
where b Pr(y E U). h = ((z), and DKz (Pell)) is minimized when the entropy Hh) = = -cecc hoech()) log log maximized.
is
Proof. For the entire underlying data dsitribution p(z, y), we introduce a binary random variable to indicate whether data originates from an old or new category. By definition, ptt = 0) = a and p(t = 1) = 1 a represent the proportions of new and old category data, respectively. We can then decompose the distribution as
p(z, 4) = plz, ylt = 0)p(t = 0) + p(z, 1)p(t = 1) (2)) (1 a)pc v),
28

---

Towards Understanding Parametric Generalized Category Discovery on Graphs
leading to the expansion of h below.
h
E (((2))
(41a)
(41b)
Σ / Pu(z, ((lz)))((zdzz (1- + Σ / pc(z, (())))) nEll"
(41c)
LEC
aa (z. (/)) (1 a) p))p((2)))(()
(41d)
ah, + (1 - hi
(4le)
Since the data distribution is class- balanced, C2/C and 1 Co/C. And current parameteric GCD methods (Wen et al., 2023; Vaze et al., 2023) rarely misclassify old class samples belonging new classes, so for any E U, hı(e) 0. With this at hand, we readily get that
Pc(y)
Po(y) log Polu) h(y)
DKL(Pellh)
= Σ
Polu) log ahu(v) + (1 a)hi(v)
+
Σ VEC
(42a)
yEU
Σ yENl
log
+ (Pel(i())
(42b)
C
aha(y)
Σ yEu
log
+ PRi(Pellhi
(42c)
Cn)
Σ
log
1 DKI(Pellh ()
(42d)
C
Cnhn(y)
yEk
=
aD (Pui(Pul)..) + DKI(Pell ()..
(42c)
As (KllPelhh C) 2 0, it follows that
DKL (Pullha) S Drr
a
Because Pe is uniform distribution, the minimizer of DKL (Pcl()) is uniform distribution, which, is the maximizer of the entropy (h) (Thomas & Joy, 2006).
F. Proofs of Theorems on (Graph) Contrastive Learning Presented in Sec. 4
F.1. Proof of Theorem 4.1
Theorem F.1 (Restate Theorem 4.1). Minimizing InfoNCE loss equivalent to minimizing the cross-entropy between the
subgraph distribution p( W x; B), which depends on data augmentation, and the subgraph posterior distribution pl W Z).
Proof. The InfoNCE loss is usually formulated as
exp (cos(2e 2i, 2,,/T] Σg exp (cos Z,, Zz. /2///T/
LNCE(Z,,2) = - llog
(43)
where z,and zy are the i-th and j-th rows of the embedding feature matrix Z, r >> 0 is the temperature, and cos(:.) is the cosine similarity. To compare (pe(p( W x; B)]pp(W Z)) with it, we need to get more detailed form of this cross entropy.
The unornalized density function of PMRF
For probabilistic modeling, we introduce one unnormlaized density function based on kernel for the PMRF in Z.
(Z,WW)
II
k(z,, 2z)) We.
(44)
(1
29

---

Towards Understanding Parametric Generalized Category Discovery Graphs
In PMRF, the dependencies among random variables restricted variable pairs (i.e., (8,5).. As a result, the unnormalized density can naturally be modeled product form over all variable pairs. Here, shift-invariant kernel k(z,, 2,) = kzz zj) is used, aligning with the shift-invariant Gaussian kernel in InfoNCE, indicating that the relationships between variables depend solely on their relative positions. Intuitively, larger edge weights Wa and higher node similarity k(2;- 2.)) correspond to higher subgraph scores, making such subgraphs more likely to appear.
The density function of the projection on S = (ker D)+ @ R2
According to Theorem D.6, (Z, W) integrable on S (ker & Rd. Thus valid distribution pZz (W) on the the measure space (S1, (1)), As,) ) is accessible, where ({S) is Borel o-algebra on S and Às, the Lebesgue measure
Si.
Pr(dZi ()) ())s (dZ,) Ca(W) (Z,, W)ss (dZ,)
C&(W) / fz, W)dAs,
The density function of the projection on So (ker L) N R.
Unlike the previous case, if lo is a fift--invariant kernel (i.e., as in InfoNCE), fZ, W) is not integrable on Sp. as demonstrated Lemma D.8. A new valid distribution density is thus required on the subspace Sg. To address this, we design a Borel function (; W): Wxd > R (E > 0) that satisfies the following three conditions for validity and applicability:
For any Z Raxd (Z, W) = =f= (Zn. W). This ensures the function depends only on the projection of Z onto Sn (i.e., Zo) rather than the entirety of Z.
For any nonzero positive real number R4. (:, W) is integrable Sg.
As > (t, W) + 1. This allows f to become increasingly flexible, even modeling scenarios where all information is entirely lost (i.e., when the function takes the constant value of 1 everywhere)
With this at hand, we define the distribution p( W) on measure space (So, ((Sp), Aso)-
1 Pr(dZo) W) p(Zo) W) (dZo) (+W) o (Zo. (dZo)
(=()) / fz W)dls
The density function of the projection on the entire space S.
Since So orthogonal to Sj, it holds that the product measure on S So S1 the product of two measures respectively defined on Sp and S
Pr(dZ[w) Pr(dZo Pr(d
Cw(W) (Zo. W) (dZo)
C+(W) fu W)As, (dZz)
(Z, ())
(45)
CE(W)
-P(Z(W)As(dZ))
where C (W) absorbs the normalization constants of two subspace conditionals, and Eq. (45) is due to (z, ())
(Zo, W) and the shift invariant property of (Z1, W) = [z, W).
The prior distribution of W.
Similar to Definition 2 (Assel et al., 2022), we introduce the prior distribution for W that depends on π N
Pr (: C (W))d(WW) (W)
II
T
W
(1.))[N]
30

---

Towards Understanding Parametric Generalized Category Discovery Graphs
where the kernel k should satisfies the conditions in Theorem D.6 and Up (W) - II I( is to filter out subgraphs consistent with InfoNCE loss, i.e., those subgraphs with more than outgoing edges for any node.
The posterior distribution of W.
With likelihood and prior, we have the posterior of W
Pr(W[Z) & Pr(ZW) W) Pr (W;
D.
(((W) (Z. W WA W) &
Pr (W)
D
x (Z, [1, (W)
II (1.))
We
= (z, w) W)
II (N
Wi,
II (N))
k(z: - 23) Way
(W)
II (N
(Ty 22))
(46)
Denote the sample space of W as Sw - ( (0, 1J,1N (V(i)) E [N]?, W.: 0), we can normalize Eq. (46) to
HAMEN [Tyb(z 21)1 I(Wi+ 1)
Pr(WIZ)
Ewesw NAJENNP [Tih((2 -2))] Wws T(W 1) HonEEN (Tack(2; - 25)1 Wis I(Wi+ =1)
HEEEN EiEM Tak(z, - 21)
[IJEINI [Tig 2z)) Wis I(Wi+ =
II
(47)
ΣIEIN Tak(z; 21)
The distribution of each W,
Wi
Fz, 2i)
II (N
I(W+ 1).
(48)
EIEIN Tak(zz z1)
The distribution characterized by Eq. (48) actually has the properties that the rows of W are all independent and the i-th row follows the multinomial distribution
W, ~ (W,IZ) = M (1, Tiyk(z, 2,)
(49)
EiE(N Tak(2; 2;))
JEINI
where the vector parentheses is the i-th row of K divided by the corresponding row sum and K is the pairwise relation matrix induced by kernel l in Z.
The cross entropy between the posterior of W and ((Wx: B) that depends on the data augmentation strategy.
Consider the subgraph distribution in the input space. Methods like SimCLR (Chen et al., 2020) and GRACE (Zhu et al., 2020) perform augmentation as sampling subgraph Wx from the human prior encoded B, and the out-degrees of all nodes in W x are equal to aligned with the single positive sample setting GRACE. When both Bi, and Wiy are large, nodes and are more similar and should form positive pair. To meet this requirement, the subgraph distribution designed as follows
p Wx:
x: B) x I(Wx x.++ = 1)
II
B
Wx.8 kj
(1J))N
Let the sample space of Wx be Sw A {We NXN ((I.)) [N]2, W. = 0}. we can normalized the above
31

---

Towards Understanding Parametric Generalized Category Discovery Graphs
distribution
I Bij IIXx++ =)
p PWxx B)
Ewxesw I(CLEEENJ Bij x (eW', =
MaSENN By *.XWII(WX. =1)
MMEIN EiEINi Ba
[IJEIN] Bij IeeiIixxx.. x =
II
EIEMM] Bu
iE[M]
The distribution row x,i
Wx.0
Byg
II (AJ)
I(Wx = 1);
EIE(N) Ba
which means
BBg
Wx. (Wx M
1,
(50)
EiE(N Ba
JE[N]
Now, let us formalize the cross-entropy. Since each row of W independent, we have p( Z) IEENN p( (W Z)) Similarly, during data augmentation, the sampling of positive samples for each instance independent, leading to p( p(Wx: x: B) [k p(W,,; x,; B). Consequently, the difference between matrix distributions can be decomposed row-wise according to Lemma D.7.
DcE(MWWx:
Σ
Des(o(Wx..BBll/WWW
DeE (Pill)
Psj log Q
N
N
Bij
Tick((z 2j) EiE(N] Tak(z, 21)
log
(51)
Eie(N|
Ba
1=1
If the parameter 1 for the prior W and is the Gaussian kernel, then Eq, (51) retrieves the famous InfoNCE loss.
N
N
Bij log
exp (cos( (z;, 2;)/T}
Σ
=
EiE[N]
Ba ΣIE[N] exp (cos(z, Zi, zi) /T)
il
where
is the By is the probability of sampling as the positive sample for i, and the log Eie(N) exp coopc ΣieNi Ba
exp cosfccoszz, (0)0((222)))) //T]
InfoNCE loss positive pair (i.j).
E2. Proof of Corollary 4.2
Corollary F22 (Restate Theorem 4.2). Minimizing SupCon loss is equivalent minimizing the cross-entropy stated in Theorem 4.1.
Proof. The overall proof approach is similar to the equivalence proof between InfoNCE and Des (x( Wx: B)ll(((()))
(Theorem 4. 4.1). The key difference lies in how multiple positive pairs introduced by label information are handled.
32

---

Towards Understanding Parametric Generalized Category Discovery Graphs
It is noted that the out-degree of each node in the sampled subgraph does not exceed my. If no duplicate nodes are sampled, the out-degree equals my; otherwise, it is less than mi. For node i, the augmentations of my same-class samples independent of each other. Thus, under the SupCon setting, the current distribution of each row of W can be expressed as
my
Pao W X.; B)
II P x B)
Psc ZZ)
π (W.
where p( W x,6 B) and pl ; Z) correspond to Eq. (50) and Eq. (49), respectively. Consequently, under the SupCon
setting, Eq. (51) (with the prior parameter π = 1) becomes
Σ
DeE(Pec Wx,,; P) (W))))
N
Des(((W B)jpll
(52)
Psg log Qui
jØt
N
Bij
k(z; - zz))
Σ
log
(53)
ZIE[N]
Bu
LiE(N) k(z; - 21))
where Eq. (52) is due Lemma D.7 and A can be regarded the population SupCon loss for anchor node i. Denote by fr the positive node sampled in the r-th augmentation step. Then according the non-negativity of cross entropy and k(z, 2 - log Σie[n k(z:-2))) it follows that
N
k(zi Zz.))
log
CE(NN k(z; =21)
i=1
m
ki(z; -Zj.) log
m
EIENN k(z; m1))
which exactly coincides with the empirical SupCon loss (Khosla et al. (2020); Eq. (2) ) for anchor node i.
F.3. Proof of Theorem 4.3
Theorem F.3 (Restate Theorem 4.3). The InfoNCE or SupCon loss optimization is equivalent to minimizing Dee(p(W, ()llP(W())) when the conditional distribution of category centers p² (ZolW) diffuse uninformatively.
Proof. In the proof of Theorem F.1, the equivalence condition between InfoNCE loss optimization and the minimization of Dce (p( Wx; B) Ip(( W|Z) [)) is that the distribution of (ZolW) W) diffuses uninformatively. The proof Corollary F.2 follows similar process to that of Theorem F.I, where the equivalence condition between SupCon loss optimization and the minimization of Dor(p( W B)llp(W(())) is also that the distribution (Zo) (Z) diffuses uninformatively. Therefore.
Theorem 4.3 holds.
G. Supplementary Details of the Experiments
G.1. Evaluation Protocol
The Conventional VGCD metrics The standard evaluation protocol used in VGCD (Vaze et al., 2022) employs clustering accuracy to measure the overall performance (All ACC), new-class performance (New ACC) and old-class performance (Old ACC).
33

---

Towards Understanding Parametric Generalized Category Discovery Graphs
Let W [wyy] be the C x C confusion matrix, where Wij is the count of samples with true label j and predicted label Clustering Accuracy is computed by solving linear sum assignment (LSAA) problem (Lovasz, 1986; Crouse, 2016). mapping each ground truth predicted label a(c) to maximize correct predictions among (test) nodes.
c
All ACC = max
W ac),c
(54)
New ACC and Old ACC are computed
Emeu W Wa(u)ar
New ACC
(55)
Eweu Ee=1 W c,u
Elec W Wa(l),
Old ACC
(56)
Σiec Ec We.
The Rectified GCD metries We argue that the traditional GCD metries introduced above fail account for the adverse effects of confusion between known and novel categories. Under no circumstances should novel categories be mapped to known categories, as such incorrect mappings violate the core objective of the GCD task: ensuring that known categories are accurately identified as their true labels while distinguishing novel categories. Therefore, we contend that traditional metrics do not fully and faithfully reflect the performance of GCD. Regarding the old-class performance, the LSA within C may assign true old classes to new classes, which is undesirable. Hence, we adopt the conventional classification accuracy as a rectified version.
Old RACC = ΣIEC WL.
(57)
SiEcEe Wo.t
Respecting the new-class performance, the computation of New ACC may result in cases where a true old class is assigned to new label tr, violating the intended separation of known and novel categories expected in GCD. To address this, we propose a Rectified Clustering Accuracy (RACC) metric to better evaluate the performance on novel categories. Without loss of generality, assume the first C, classes are the old categories and the remaining are the new categories. We extract the bottom-right C. x C. submatrix Wneww) of the confusion matrix W, which corresponds the confusion among new categories. Based on Winew), we solve the Linear Sum Assignment (LSA) problem within the new categories, mapping each ground truth new label u to predicted new label b(u). The Rectified metric is then defined
New RACC
max
Wnew
(58)
Eu= ΣC
W
b(u).u
G.M
It important note that when novel-elass samples are misclassified old classes, (new) loses many samples and b(u),u decreases significantly, resulting in a low New RACC. This makes New RACC more faithful reflection of performance on novel categories in the GCD context compared to New ACC. Given that performance on both known and novel categories is critical for GCD, and the harmonic mean penalizes large disparities between values, we replace All ACC with the Harmonic mean of Old RACC and New RACC Scores (HRScore), to evaluate the overall GCD performance:
Eu=1 Co [[eww)
if Old RACC-O or New RACC-O otherwise
HRScore
(59)
2
Reject ACC is computed by merging all "old classes" into a single class (Known) and all "new classes" into another class (Unknown), constructing a 2 x 2 confusion matrix (()) and calculating the proportion of the sum of its diagonal elements to the total sum of all elements.
2 W('), is
Reject ACC = Σ Σ W
(60)
G.2. Hardware and Software Environment
The experiments were carried out across two different systems. The first system runs Ubuntu 22.04 and is equipped with an RTX 4090 GPU (24GB), an Intel i7-12700 CPU, and 64GB of RAM. The second system, which uses Ubuntu 20.04,
34

---

Towards Understanding Parametric Generalized Category Discovery on Graphs
features an RTX 4090 GPU (24GB), dual Intel Xeon Gold 6240C processors, and 126GB of RAM. Both systems have the same Conda environment, which includes PyTorch 2.5 (Paszke et al., 2017) and PyG 2.5 (Fey & Lenssen, 2019), all built on CUDA 12.1.
G.3. Experimental Details for GCD Upper Bound Theory (Sec. 3.4)
Synthetic Node Embedding Datasets In the 2D plane, generate square with radius Tı, placing its four vertices Molc [1 4|) the centroids of four new classes along the coordinate axes. Then, centered at S1, we generate another square S2 with radius (> r1). and use its vertices He(c [5 8)) as the centroids of four old classes. For each class we sample 200 points from N M(pn, I as the sample embeddings. By controlling rı, de- and /1/r2, we control the confusion between new and old classes. We generate three embedding datasets Di Dī. shown in Fig. la-lc, where the corresponding Wasserstein distances satisfy W1 > W2 > W3. and the centroids of the new (x) and old (*) classes are marked by (x, x. x, x) and (*, *, *), respectively.
Specifically, for these three embedding datasets, the raw data is generated with the following settings: for all new classes, of 15, and for old classes, of 10. The other parameters for each dataset are follows:
For Di: 11 = 8/21/12 = 0.5.
For Dj: 16,r1/r2 1.
For Dj: P1 r//r 2.
Subsequently, all data undergoes Z-Score Normalization to ensure consistency in numerical ranges across datasets. The entire node set is stratified into training, validation, and test subsets in a 2:2:6 ratio, which are subsequently used for training and evaluation, as described Sec. 6.1. Note that the old classes are designed to be easily distinguishable due to the large inter-class distances. This enables us to focus on understanding how the old-and-new relationship impacts GCD, with excluding the influence of mixing old classes.
Model and Training Setup In the experiments on synthetic node embedding datasets, the setup is follows:
Classifier: A 2-layer MLP classifier with an input dimension of 2, a hidden layer dimension of 24, and an output dimension equal to the number of classes (8).
Training Loss: The model is trained using Cross-Entropy (CE) loss on labeled samples and Entropy Regularization (ER) on all samples. The overall training objective is LMLP = (1 - Len + 02 where 0:2 = 0..3.
Optimization: We train the model for 1000 epochs using the Adam optimizer (Kingma & Ba, 2017) with learning rate of 0.01.
We report the performance with the model weights from the final training epoch. The main results are shown in Fig. le. To ensure consistency, the model parameters are initialized with the same weights at the start of training for each dataset.
G.4. Experimental Details for GCL Theory (Sec. 4.3)
Synthetic CSBM Graph Datasets In the 2D plane, we first generate node features and labels following the process described for Dj and D in Sec. G.3. Next, intra-class nodes are connected using Bernoulli distribution with a probability p ===00 0.05, while inter-class nodes are connected with a probability of q = 0.001, resulting in the adjacency matrix. This procedure produces the CSBM (Deshpande et al., 2018) graph datasets D, and D3, whose details are summarized in Table 3. For each dataset, the entire node set is stratified into training, validation, and test subsets in 2:2:6 ratio, which are then used for training and evaluation, as described in Sec. 6.1.
Model and Training Setup for Verifying Theorem 4.3 Theorem 4.3 discusses the uncontrollability of the global structure between categories in the node embedding space learned through InfoNCE and SupCon losses. To validate this theorem, we train an encoder using GRACE and GRACE-SC. The setup is as follows:
Encoder:
The 2-layer GCN encoder has input, hidden, and output dimensions of 2, 36, and 2, respectively.
35

---

Towards Understanding Parametric Generalized Category Discovery on Graphs
Table 3: The statistics of CSBM graphs. W is the Wasserstein distance between old and new classes in the input node
feature space.
Dataset
#Nodes
#Edges
#Features
#Classes
#Old Classes
Homophily Ratio
W
D1
1600
18014
2
8
4
0.88
0.33
D3
1600
18356
8
4
0.89
0.19
The graph data augmentation module randomly drops 20% of the edges and injects Gaussian noise with a standard deviation of 0.2 and mean of zero into the node features.
Augmentation:
Training Loss: The training loss is weighted combination of InfoNCE and SupCon losses, i.e., LGCL L2)LNCE + 022 Lsc, and we set 0.35.
Optimization: The model is trained over 1000 epochs using the Adam optimizer, set at a learning rate of 0.01.
After training, we utilize the GCN encoder to generate embeddings for all nodes and visualize them. Figs 2b and 2c show the embedding spaces obtained on the dataset D, using random seeds 2050 and 800, respectively, under the same model weight initialization. Figs. 2c and 2f present the results on D3. The analysis in Sec. 4.3 confirms the randomness of global structure.
Model and Training Setup for Verifying the impact of GCN encoder on GCD Sec. 4.2 examines the impact of the GCN encoder's smoothing effect on GCD, focusing on the undesired mixing of categories. While replacing the GCN encoder with an MLP in control experiment eliminates the effects of GCN's local smoothing, completely discards graph structural information, which would distort the contrastive results. Therefore, we opt for the high-pass GNN, GPR (Chien et al., 2021), which preserves structural information while escaping from the local smoothing effect?. The setup is:
The 2-layer GCN encoder has input, hidden, and output dimensions of 2, 36, and respectively. The GPR encoder is chained by two parts: the first is 2-layer MLP feature extractor with dimensions (2, 36, 2) that output X'; the second is a GPR convolution layer formulated as Z = Σk= 0g ((D 1) - + I) + I) 1)-1/2) & X', where
Encoder:
D is the degree matrix of A and 0 is initialized with Personal Page Rank (Jeh & Widom, 2003).
Classifier: The MLP classifier has input, hidden, and output dimensions of 2, 24, and 2, respectively.
Augmentation: The graph augmentation process involves randomly removing 20% of edges and adding zero-mean Gaussian noise with standard deviation of 0.2 to node features.
Training Loss: The training loss is LSimGDD = (1 (2) + LSD + o1LER) + as(Lsc + LCE). We set 02 = 0.35 and 01 = 2, as is commonly done by default in many baselines (Vaze et al., 2022; Wen et al., 2023).
Optimization: Training involves 1000 epochs with the Adam optimizer, employing learning rate of 0.01.
G.5. Experimental Details for SWTRL on Synthetic CSBM Graphs (Sec. 5.1)
SWIRL a novel GCL method, inspired by the GCD theory for understanding parametric GCD methods (Theorem 3.5) and designed enhance the GCL module in the baseline parametric GCD method. SimGCD. To visually demonstrate that SWIRL learns embedding space more beneficial for GCD-one one that better aligns with the embedding conditions Lessons 1 and 2 derived from Theorem 3.5-we we conduet comparative experiments SimGCD, SimGCD-GPR, and SWIRL. The learned embedding spaces for the three methods are shown in Fig. 3, with the metrics presented in Table 1. For SimGCD and SimGCD-GPR, the experimental setup is as described in Sec. G.4. The setup for SWIRL as follows:
the CSBM graphs Dj and Ds, evaluating
Encoder: The 2-layer GCN encoder has input, hidden, and output dimensions of 2, 36, and 2, respectively.
"B analyzing the learned GPR coefficients from our experiments, we found that the GPR encoders and D3 effectively act as high-pass graph filters, distinguishing them from low-pass and locally smoothing nature of GCN.
36

---

Towards Understanding Parametric Generalized Category Discovery Graphs
The MLP classifier has 2 dimensions for the input layer, 24 dimensions for the hidden layer, and dimensions for the output layer.
Classifier:
Augmentation:
The graph data augmentation component randomly removes 20% of the edges and introduces Gaussian noise with a mean of zero and a standard deviation of 0.2 into the node features.
Training Loss: The training loss Lsw = (1 - a2) + 3 Lsw + a LER) + aaLLEE. We set a2 = 0.35 and a1 2, which are commonly used values in many baseline models (Vaze al., 2022; Wen et al., 2023), and choose
31 20.
Optimization: We use the Adam optimizer with a learning rate of 0.01 to train the model for 1000 epochs.
G.6. Experimental Details for Real-world Experiments (Sec. 6)
Real-world Graph Datasets We consider public graph datasets: Cora, Citeseer (Sen al., 2008), Wiki (Cao et al., 2016), Amazon-Phon Photo (A-Photo), and Amazon- Computtrss (A (N-Computers) (Shchur al., 2019). The statistics of these graphs summarized in Table 4. For each real-world graph dataset, we use the same hyperparameter settings and conduct five experiments with different random seeds (20, 21, 22, 23, 24), reporting the mean and standard deviation of the results.
Table 4: The data statistics of the used real-world graph datasets.
Dataset
#Nodes
#Edges
#Features
#Classes
#Old Classes
#New Classes
Homophily Ratio
Cora
2485
5069
1433
4
0.81
Citeseer
2110
3668
3703
6
3
0.74
Wiki
2405
23192
4973
17
9
0.61
Amazon-Photo
7650
238162
745
8
4
0.83
Amazon-Computers
13752
491722
767
10
5
0.78
We begin by provide additional GGCD details uncovered earlier, and then provide the hyper- parameter values the search space in Table 5. For each method, use Optuna (Akiba et al., 2019) to perform 40 optimization runs, with the Old RACC on the validation node set as the objective for hyperparameter search. Note that since only the old classes are known, we cannot use the New RACC or HRScore on validation set to guide the hyperparameter search. Additionally, we employ early stopping for each experimental run. the validation Old RACC does not improve for Max Epochs consecutive epochs, training is terminated immediately. This approach not only reduces experimental costs also accounts for findings by Wen et (2023), which suggest that prolonged training can degrade Old Capability.
Implementation Details
SS-KM (Vaze al., 2022): The baseline directly applies SS-KM the node features, utilizing the K-means++ initialization strategy for cluster centroids (Arthur & Vissilvitskii, 2007). The number of clusters is set to the number of categories C, the distance metric is Euclidean distance. The maximum number of iterations max_iter=200, the number of centroid reinitializations miini==0,,. and the convergence check condition is tolerance=le-6.
GCN (Kipf& & Welling, 2017): The output layer dimension of the GCN baseline is set to the total number of classes C. Since the Cross-Entropy (CE) loss can only leverage the supervision from the C. old classes, it is unable handle novel categories, making ineffective baseline. Therefore, we incorporate Entropy Regularization (ER) loss and optimize the objective
LOON 0.35) 4LER + 0.35LCE.
Vanilla GCD (Vaze et al., 2022): We use the Graph adaptation variant from Sec. B. Specifically, we first perform supe-supe contrastive training based on GRACE and GRACE-SC to obtain the GCN encoder, and then apply SS-KM to make predictions based on the encoder's output. The number of clusters for SS-KM is set the number of categories C, with K-means++ initialization and the following parameters: tolerance le-5, max_iter- 100, and inil 1. The training objective is
Lv CvansilaGCD = - (1-00.55 ( + 0.35Lsc.
022 0.
37

---

Towards Understanding Parametric Generalized Category Discovery Graphs
UNO+ (Fini et al., 2021; Vaze al., 2022): The optimal transport problem is solved using Sinkhom (Cuturi, 2013) to compute the optimal node-to-prototype probability pseudo-label matricesZ()) and Z for the view embeddings z and z For old-class nodes with known labels, their pseudo-labels are forcibly replaced with the corresponding one-hot vectors of the true labels. Then, cowteemperature cross-entropy loss is applied to supervise the predictions from the other view. The loss function is
02 2
Σ DEE 2 [ ( [213]]] ==1
LUNO+
SimGCD (Wen al., 2023): The original version of SimGCD, designed for VGCD, uses a prototype classifier. However, we found that two-layer MLP generally performs better graph data, particularly the CSBM graph datasets Dj and D3 that we generated. The training loss for SimGCD is
LSmGGD (1 (LNCE + LSD + 2LER) + (35 LCB).
SWIRL (Ours): SWIRL is novel Graph Contrastive Learning (GCL) method designed for Parametric GGCD. Unlike the classic Parametric method SimGCD, SWIRL eliminates the use of Self Distillation (SD) and SupCon losses, while retaining the InfoNCE loss to optimize the local structure of the embedding space. The SWIRL loss introduced to regulate the global structure. The number of clusters used in the SS-KM for computing the SWIRL loss set to K(> C), with tolerance Ie-4, max iter 20, and inil 1. The training loss for SWIRL
Lsw = (1 - (LNCE + B1 Lsw + 2L.R) + 0.35I.c--
Table 5: Hyperparameters of GGCD methods and the corresponding values or search spaces
Common Hy perparaameerr
Group
Hyperparameter
Value or Search Space
Learning Rate
[0.001, 0.005, 0.01, 0.05, 0.1] [0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8] [0.0, 5c-5, 1c-4, 5e-4, 1c-3, 5c-3, 1e-2)
Dropout
Optimization
Weight Decay
Max Epachs
[200, 400, 800]
GCN Encoder Layer
[2, 3,4] ["relu", "prelu"I
GCN Encoder Activation
Neural Network Arch.
Hidden Dim.
[64. 128, 256, 512, 1024]
MLP Projector Layer
MLP Classifir Layer
Edge Removal Rate
[0. 0.1, 0.2, 0.4, 0.5, 0.6] [0. 0.1, 0.2, 0.3, 0.4, 0.5, 0.6] [0.1:1.5], step=0.1 0.07
Graph Augmentation
Feature Masking Rate
InfoNCE Loss Temp.
SupCon Loss Temp.
Losses
ER Loss Temp.
0.1
ER Weight
Supervised Loss Weight 02
0.35
Some Specific Hyperparameters
Group
Hyperparameter
Value or Search Space
SD Loss Teacher Temp.
0.04
SD Loss Student Temp.
SimGCD
SD Loss Warmup Teacher Temp.
0.07
SD Loss Warmup Epochs
30
GCN
ER Loss Weighta
Temp.
0.1
UNO+
Sinkhorn Num Iterations
Sinkhorn Epsilon
0.05
SWIRL Loss Weight 3
[1, 50]
Repulsion Force Scale
[0.00001, 0.0001, 0,001, 0.01]
SWIRL
Repulsion Force Degree 4
f, + 0.14
Prototype Number
[20, 200]
38

---

Towards Understanding Parametric Generalized Category Discovery on Graphs
70
70
6B
G0
86
79
86
57
20
54
GD
93
26
67
83
25
8G
57
87
83
87
85
75
74
68
75
74
73
6B
71
70
68
74
75
37
70
73
66
72
81
70
F7
50
76
78
B6
70
79
69
80
B1
84
83 60
89
89
83
57
B5
88
80
91
79
81
93
72
88
92
71
78
80
84
83
96
97
85
9G
93
83
99
86
91
92
100
BV
DR
F3
21
PO
21
7M
59
76
92
85
Hetric
CHd PACC||
Metric Old RACC|
Metric
Cld RACC
Metric
OIS RACC
Metricc
Old RACC
Metric RACC/
RM
SHI
100
100
100
MB
MMM
100
97
100
100
40
S/3
915
1:00
-00
LOG
400
100
1.00
1.00
100
100 LUD
1:00
LU0
L00
100
L00
A00
SV
100
SM
100
99
100
LUD
99
MB
98
3.00
100
1:00
1.00
100
1.00
1:00
200
100
1.00
100
1000
1.00
99
99
100
100
1.00
300
98
80
96
100
LOD
100
96
96
305
S/3
SKS
919
A000
100
SV
100
9/3
94
300
S1V
100
LOD
ADO
L00
A00
LO0
U4
95
72
26
25
75
Marric
Now RACC|
P.
Metric
New RACC|
1.0
Metric
New RACC|
20
Metric
NOW RACC
20
Mctric
NEW RACC
Metriic
NeW R4CC
-50
95
96
95
70
53
50
50
155
50
54
50
53
69
153
53
56
52
59
52
52
70
71
4D
05
64
X1
12
20
40
76
70
74
60
60
92
54
57
CO
R2
R2
65
05
C6
72
77
78
78
69
56
62
50
52
51
49
56
61
46
57
76
51
76
S2
78
52
75
65
68
85
59
57
50
93
PO
62
75
100
77
R1
57
51
51
55
65
66
53
61
PC
80
05
Metricc Rejmet ACC
55
Matric
Pejjctt
ACC|
10
Matric
Rejjett ACC| 1A
20
Matric
Rajjett ACC| P:
30
Matric
Rejjct ACC
Pi
40
Metric:
Rejject ACC
50
09
99
9D
99
99
0D
1000
09
100
100
100
100
100 100 100
100
100
100
100
100
100
100
L00
A00
100
1000
98
100
100
98
100
99
L00
20
1:00
1:00
1000
100
4n
100
100
100
100
100
100
1:0
100
100
100
100
9n
99
100
10
23
8
8
99
1.00
.00
100
L00
100
100
100 100
100
100
100
100
1000
100
100
100
100
100
100
99
100
100
100
100
100
90
98
100
100
3
4
99
1000
40
99
100
100
1.00
100
1.00
100
100
100
49
94
99
90
120
8
8
100
L00
100
100
100
88
100
100
100
27
88
5.
5:-05
0.000
0.000
0,50
00
0.3
Se-03
0
0.003
9,003
0.2
0
00:005
0,202
0.03
0.5
0000
00:00
0,901
00
Se-02
0.000
00005
0.00
000
Se-05
0000
0.003
0,993
Figure 6: The hyperparameter sensitivity of our SWIRL on the CSBM graph Di. where the challenge is distinguishing new classes. Each row corresponds to a GCD metric, while each column represents a different value of the SWIRL loss weight 31. At each position, the heatmap visualizes how the number of prototypes K and the repulsion force scale s jointly impact the GCD metrie values. In each heatmap, the maximum value is highlighted with blue box, and the minimum value is highlighted with green box.
G.7. Hyperparameter Analysis for SWIRL on Synthetic CSBM Graphs
SWIRL has three key hyperparameters to tune: 31, 8, and K. To analyze their impact on SWIRL, we conduct experiments on the synthetic CSBM graphs D1 and D3 described in Sec. G.4. The results of the hyperparameter grid search on these datasets are presented in Fig. 6 and Fig. 7, respectively. For each hyperparameter, we select six discrete values from the search space defined in Table 5, resulting in a total of 216 experiments (6 6 6 grid search). To comprehensively illustrate the relationship between hyperparameters and various GCD metrics, we organize the visualization using faceted plots based on four GCD metrics and six values of [1. Within each heatmap, we show the effects of and K on GCD performance.
For D1, the primary challenge is distinguishing different novel categories. As shown by Fig. 6, the second and fourth rows of the heatmaps indicate that the three hyperparameters have little impact on Old RACC and Reject ACC. When the number of prototypes is low (i.e., K = 8), SWIRL likely fails to adequately approximate the global structure, making it difficult to regulate the true global structure simply by increasing the SWIRL loss weight Bi. Since global structure is crucial for leveraging old-class knowledge in novel category discovery, both HRScore (first row) and New RACC (third row) exhibit clear downward trend for K- = 8 as 31 increases. Conversely, when the number of prototypes is large (i.e., K = 100), the model approximates the global structure more effectively. As the regulation strength increases from left to right, New RACC (third row) and HRScore (first row) improve significantly. This suggests that when distinguishing novel categories is the primary challenge, a larger number of prototypes should be used alongside a higher SWIRL loss weight 31.
For D3. the key challenge is distinguishing closely related known and novel categories. As displayed in Fig. 7, the first and fourth rows reveal that as 81 increases, placing more emphasis on global structure, Reject ACC and HRScore decline
39

---

Towards Understanding Parametric Generalized Category Discovery on Graphs
Mettic
F:
93
90
BO
76
7B
93
97
97
S7
96
R2
72
7R
95
96
95
95
95
96
9G
95
37
94
97
85
97
97
96
97
97
94
92
94
91
92
84
29
92
79
77
74
77
79
83
74
60
83
95
95
95
95
95
9G
95
96
95
96
97
97
97
97
92
92
91
92
93
96
66
81
B1
78
71
77
76
78
75
100
95
96
UB
85
75
73
Hetric
Cld RACC||
Metric
Old RACC|
Metric
Cld RACC
Metric
OIS RACC
Metricc
RACC
Metric
01 RACCI
bR
30
56
40
50
94
94
94
96
94
96
96
96
9/5
96
922
910
92
PL
92
F4
154
90
57
65
54
58
68
72
6
22
98
90
95
96
98
86
90
50
68
48
59
89
23
PQ
MB
97
95
15
87
95
81
35
305
SH4
94
95
SV
MB
93
95
96
94
9-
91
96
9C
92
522
90
933
95
F2
51
75
5C
64
52
6
SC
Marric NOW RACC|
Metricc K New RACC|
100
Matric New RACC| PL.
20
Mctric NEW RACC P.
20
Micrric
NeW RACC|
PL
Metriic
NEW RACC
PL
-50
DC
9G
DC
97
R5
91
91
90
87
99
9S
69
9D
96
99
99
99
99
95
100
96
99
9D
96
20
9B
40
96
96
92
92
QR
90
50
95
RS
96
57
37
96
96
96
93
94
96
98
96
57
57
94
96
93
95
93
97
97
97
99
96
98
95
20
100
9B
50
95
90
96
Reject ACC 55
Matri
Dl M.L. AOC
10
Matric
Rejpet ACC
Matric
Reject ACC D:
30
Matric
Recect ACC| P
Metric
Rejject ACC
Ps
07
87
07
PG
96
96
P6
91
85
94
BG
92
92
50
96
8G
BG
29
77
79
81
78
82
83
75
77
BL
8D
20
T9
RD
77
29
80
5
5
8
15
96
98
98
96
P8
97
87
97
97
97
97
92
92
92
93
92
91
87
87
83
85
88
83
81
73
79
80
78
77
22
X
98
40
40
97
mn
77
150
82
86
78
53
5:-05
0.003
0.005
0,50
0.3
Se-03
0
0.0033
0.03
0000
00:05
000
0.5
00001
0.000
0,001
0.02
5e-03
0.0002
00005
0.003
000
5e-05
00001
00003
6,00
00:
Figure 7: The hyperparameter sensitivity of our SWIRL on the CSBM graph D3. where the challenge is distinguishing between adjacent new and old classes. Each row corresponds to a GCD metric, while each column represents a different value of the SWIRL loss weight 31. At each position, the heatmap visualizes how the number of prototypes K and the repulsion force scale s jointly impact the GCD metric values. In each heatmap, the maximum value is highlighted with blue box, and the minimum value is highlighted with green box.
significantly. This is likely due to overemphasizing global structure, which constrains instance-level discrimination between similar known and novel category nodes, making them harder to distinguish. To validate this hypothesis, we visualize the embedding space and decision boundaries from the experiment with 31 = 50, s = 0.01 and K 100 in Fig. 8. The visualization clearly shows that many old-class nodes are misclassified as novel categories, confirming that when the primary challenge distinguishing adjacent known and novel categories, a smaller SWIRL loss weight 3n should be used.
Across both Dj and Dz, we observe that the optimal results rarely achieved when 0. This demonstrates the effectiveness of SWIRL's distinct design, six levels of repulsion force, compared to other eestance-to-proootyy contrastive losses. Finally, identifying the primary challenge in target dataset is non-trivial. Since this work primarily focuses on parametric GGCD theory and its validation, addressing this more practical issue is left for future research.
40

---

Towards Understanding Parametric Generalized Category Discovery on Graphs
Figure 8: The learned embedding space of SWIRL on the CSBM graph Dz. with B1 = 50, 8 = 0.01 and K = 100.


Reviews:
[{"review_id": "yGFNXGB99B", "reviewer": "Reviewer_Hzoz", "summary": "This paper studies the generalized category discovery problem in graph node classification context. The authors aim to answer the question “When and how do old classes help (parametric) generalized category discovery on graphs?” in a theoretical way. The answer from the authors is based on the relationships between old and new categories in the embedding space, the elements of which are later fed into a parametric classifier to make final predictions. Specifically, the Wasserstein distance between the distributions of old-class and new-class embeddings should be minimized, provided that the embeddings of the old and new categories do not overlap. Later, the authors find that the representation learning methods in current GCD methods tend not to meet this. And to address this issue, they propose a new GCL method, SWIRL.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your constructive suggestions! We hope the response can address your concerns.\n\n+ **W1**: When keeping other hyperparameters consistent, adding **SWIRL** loss alone to **SimGCD** not only achieves a better **HRScore** but also reaches a high performance level as fast as at **epoch=5**.  The implementation is based on the code https://github.com/CVMI-Lab/SimGCD.\n\n|   CIFAR100       | HRScore (epoch = 5) | HRScore (epoch = 200)| Old RACC | New RACC | Reject ACC |  \n|----------|----------|------------|----------|----------|------------|  \n| **SimGCD** | 33.9     | 77.9       | 81.8     | 74.3     | 91.9       |  \n| **SWIRL**  | **65.7**     | **78.4**      | 78.4     | 78.1     | 90.8       |  \n\n+ **W2**: In the revised version, we will include a schematic diagram to illustrate the theoretical result in **Sec. 3**: semantically similar categories should also be close in the representation space. Additionally, we will add another diagram to visualize the **PMRF perspective of GCL** mentioned in **Sec. 4**.  \n\n+ **W3**: We have carefully checked the entire manuscript to ensure no similar errors remain.  \n\n+ **W4**: For **parametric GCD methods** (the main focus of this work), preventing new-class samples from being misclassified as old classes is crucial. Thus, the weight of the supervised signal typically needs to be lower than that of the self-supervised signal. Here, we follow the hyperparameter selection of **SimGCD**. Moreover, since all methods use the same weight settings, adopting different weights on other datasets does not affect the conclusions of this paper.  \n\n+ **W5**: Thank you for pointing this out. To be precise, when $s=0$, the **SWIRL loss** closely resembles **PCL [1]**. The key distinction of our method lies in how we **push away different samples and clusters with varying repulsion froce**.  \n\n+ **W6**: $\\mathbf{B}$ represents the relationship among all **N samples** (including all possible augmented views) in our framework. The dataset of **n nodes** is just a subset. $B_{ij}$ denotes the similarity between nodes **i** and **j**, as well as the probability of sampling them as a positive pair. In each augmentation step, we sample one positive node **j** for each node **i**. Once sampled, the edge **(i,j)** becomes part of the subgraph $\\mathbf{W}_X$. Since **n << N**, the **N × N** matrix $\\mathbf{W}_X$ is actually a small graph with **2n non-isolated nodes**. The remaining **N-2n** samples are isolated and retained in $\\mathbf{W}_X$  only for formulation convenience.  \n\n+ **W7**:   $\\Omega_D(\\mathbf{W})$ equals **1** only when each row of $\\mathbf{W}_X$ has exactly one non-zero element (i.e., each node has only one neighbor). Thus, multiplying by it ensures that in the sampled subgraph each node has a single positive node.  \n\n[1] *Prototypical Contrastive Learning of Unsupervised Representations*, ICLR 2021.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "No.", "experimental_designs_or_analyses": "Yes. This paper has sound and valid experimental designs to support the claims of authors.", "relation_to_broader_scientific_literature": "This paper is, as far as I know, the first theoretical work to answer “When and how do old classes help (parametric) generalized category discovery?” in the field of GCD. But the theories seem to hold only for those methods using parametric classification head (e.g., MLP). In spite of this, the quantization of the relationship between old and new categories and the GCD loss upper bound make this work quite novel. The analysis of contrastive learning methods in Sec. 4 is insightful to design new representation learning methods for GCD problem. Though the authors put a graph context, the main results in this work seem to hold for image data as well.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths:\n1.\tThis paper is well-organized to answer the question “When and how do old classes help (parametric) generalized category discovery on graphs?” \n2.\tThe theorems answer the question clearly and the proposed SWIRL is motivated by the theoritical results.\n3.\tThe hyperparameter analysis shows that the proposed method is not sensitive to hyperparameters, which is good for practice.\n\nWeaknesses:\n\n1.\tI suggest the authors test SWIRL on image datasets such as CIFAR100 to make this work more comprehensive.\n\n2.\tThere are a lot of theorems, and the paper is very dense in math. More intuitive discussion can help readers to understand.\n3.\tIn line 1938, p36, 035 should be 0.35.\n\n4.\tFor all datasets, the weights of supervision and self-supervision losses are fixed to 0.35 and 0.65, respectively. Is this an appropriate way?\n\n5.\tIn line 2076, p38, the authors state that “compared to other instance-to-prototype contrastive loss”. This statement is not accurate since $s=0$ can only derive one form of instance-to-prototype contrastive loss, whereas in reality, there are many other forms of instance-to-prototype contrastive losses.\n\n6.\tIn Sec. 4.1, the authors say that $\\mathbf{W}_{X}$ is the subgraph sampled from $\\mathbf{B}$. But no clear sampling definition and meaning are provided, leading to some confusion. What’s the shape of the sampled subgraph? \n\nFurthermore, how can $\\Omega_{D}(\\mathbf{W})$ align with the single-positive-sample manner in GCL methods such as GRACE?", "other_comments_or_suggestions": "See the weakness part.", "questions_for_authors": "See the weakness part.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ezvzpoGfZN", "reviewer": "Reviewer_ZGRQ", "summary": "The paper focuses Graph Generalized Category Discovery (GGCD), an node-level task aimed at identifying both known and novel categories in unlabeled nodes by leveraging knowledge from labeled old classes. The authors provide the first theoretical analysis for parametric GCD on graphs, quantifying the relationship between old and new classes using the Wasserstein distance in the embedding space. This analysis establishes a provable upper bound for the GCD loss, revealing two critical conditions: (1) small Wasserstein distance between old and new classes to transfer discriminative knowledge, and (2) sufficient separation to avoid overlap between old and new classes. Through a Pairwise Markov Random Field (PMRF) perspective, they show that mainstream graph contrastive learning (GCL) methods employing InfoNCE or SupCon losses inherently violate these conditions due to uncontrolled category relations and the smoothing effect of GCN encoders. To address this, the paper proposes SWIRL, a new GCL method designed to better control global category relations. Experiments on synthetic and real-world graphs validate the theoretical findings and show SWIRL's effectiveness", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank you for the valuable comments that helped improve our paper!\n\n---\n\n### **Claims and Evidence**  \n**Theorem 3.5** summarizes three key aspects of **GCD**: **Old**, **New**, and **Reject Capability**. This work primarily focuses on the latter two (involving new-class data), so we intentionally made old classes easily distinguishable to eliminate interference and study how the ability to separate old classes transfers to new ones. From this perspective, our experimental setup validates the **New/Reject Capability** aspects of **Theorem 3.5**.  \n\nFor the **Old Capability** part of **Theorem 3.5**, we previously conducted experiments under an alternative setting: placing old classes *inside* and new classes *outside* (current old-class positions). The results confirmed that insufficient Old Capability negatively impacts new-class separation, aligning with theoretical predictions.  \n\n\n\n### **Experimental Designs or Analyses**  \nThe results for **SWIRL-GPR** are shown below. On dataset **D1**, SWIRL outperforms **SimGCD-GPR**, while the opposite holds for **D3**. Upon visualizing the representation space of **SWIRL-GPR on D3**, we observed significantly weaker intra-cluster cohesion compared to **SWIRL-GCN**, leading to poorer GCD performance. We attribute this to both **GPR encoders** and **SWIRL** emphasizing information from distant nodes/spaces *beyond local neighborhoods*, which neglects local structural cues and hinders tight cluster formation.  \n\nAdditionally, since **GPR encoders** are inherently challenging to train in unsupervised graph contrastive learning (e.g., via GRACE-style methods) [1], we recommend pairing **SWIRL** with a **GCN encoder** for better local-space cohesion.  \n\n| **D1**       | **HRScore** | **Old RACC** | **New RACC** | **Reject ACC** |  \n|--------------|------------|--------------|--------------|----------------|  \n| SimGCD-GPR   | 77.18      | 99.79        | 62.92        | 99.48          |  \n|SWIRL-GPR| **87.72**  | **100.0**    | **78.13**    | 98.54          |  \n\n| **D3**       | **HRScore** | **Old RACC** | **New RACC** | **Reject ACC** |  \n|--------------|------------|--------------|--------------|----------------|  \n| SimGCD-GPR   | **88.77**  | **98.12**    | **81.04**    | 90.52          |  \n| SWIRL-GPR    | 82.39      | 96.88        | 71.67        | 89.58          |  \n\n### **Weaknesses**  \n+ **W1**: We will promptly release the code and document all hyperparameter settings in configuration files.  \n+ **W2**: This work focuses on *theoretically* explaining how old-class knowledge transfers in GCD. We achieved this goal, and our theoretical results guide GCD method design. The heuristic **SWIRL** merely validates this guidance; rigorous provable methods are left for future work.  \n+ **W3**: Thank you—we will explicitly clarify the paper’s scope in the revision.  \n+ **W4**: We will add schematic diagrams for **Sections 3 and 4** to improve readability.  \n### **Suggestions**  \n+ **S1**: Although not re-emphasized, all verification experiments used $L = D_{CE}$ (cross-entropy loss), and results aligned well with theoretical predictions, demonstrating their partial equivalence.  \n+ **S2**: Practical examples will be added in the revised version.  \n### **Questions**  \n+ **Q1**: Yes, except the content about GCN encoder.\n+ **Q2**: Excluding global normalization violates the PMRF’s fundamental dependency assumption, making our framework incompatible with such losses.  \n+ **Q3**: This ultimately depends on which capability is prioritized in a specific application. Regarding the theoritical side, it does not influence the bound formulation. \n+ **Q4**: Please refer to **Claims and Evidence**.  \n\n\n[1] PolyGCL: GRAPH CONTRASTIVE LEARNING via Learnable Spectral Polynomial Filters, ICLR2024", "claims_and_evidence": "The efficacy of the SWIRL method has been amply demonstrated. The principal theoretical outcomes of the authors were validated under a specific category distribution layout (as illustrated in Figure 2). Although the results align closely with the theory, it is incumbent upon the authors to further elucidate whether this layout sufficiently attests to the universality of the theoretical findings.", "methods_and_evaluation_criteria": "The authors have employed reasonable evaluation metrics, and the proposed method effectively addresses the target problem at hand.", "theoretical_claims": "I haven't looked at the proof process, but these theorems do align with my intuition.", "experimental_designs_or_analyses": "I have checked all claims, experimental designs, and analyses. Overall, the designs and analyses are valid to demonstrate authors’ claims. However, in the experiments of Section 4, the authors should present and discuss the performance of SWIRL-GPR, which is trained using the SWIRL method with a GPR encoder.", "relation_to_broader_scientific_literature": "This paper extends GCD from image domain to graph domain, with a novel theoretical analysis on GCD methods (e.g., SimGCD) that relies on parametric classification heads. Though the application cases are about graphs, most analyses in this work seem to fit into the cases of non-graph data. Hence, it can be taken as the first comprehensive analysis of parametric GCD performance from both classification head and representation learning sides.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "**Strengths**\n\n-  The authors represent the first attempt to quantify the relationship between the distributions of old and new classes, which I think is crucial for GCD analysis, particularly for the analysis of generalization error. \n- The theoretical findings provide valuable insights that can inform the development of novel GCD methodologies. \n- The proposed method is designed with the inspiration from authors’ theoretical analyses.\n\n**Weaknesses**\n\n- The final hyperparameters for all methods are not reported. \n- Despite the extensive theoretical content presented earlier, the method proposed by the authors, SWIRL, appears to be essentially heuristic in nature.\n- The author's title suggests an exploration of generalized category discovery on graphs, but the content of the article primarily focuses on GCD methods that utilize parametric classifiers. I believe this is not appropriate.\n- The paper is too mathematical to read in some parts (e.g., Sec. 4.1).", "other_comments_or_suggestions": "- The last sentence of Assumption 3.3 mentions that the author's experiments also support the equivalence between \\( L = D_{CE} \\) and \\( L = MSE \\), but the author does not analyze this in the results discussions.\n\n- In Appendix G.1, the author has improved the existing evaluation protocol, but the explanation of its advantages is not sufficiently intuitive. I think some specific examples would help readers quickly grasp the key points of the improvements.", "questions_for_authors": "1. Do the theoretical results in Sections 3 and 4 directly apply to parametric GCD methods for image data?\n2. The computational efficiency of the InfoNCE loss is high when the batch size is large. Some works in other fields [1] have found that the pairwise sigmoid loss without global normalization can enable more efficient contrastive training. Is it possible for your theory in Section 4 to extend to contrastive learning algorithms that utilize this type of loss?\n3. The loss \\( L_{te}(h) \\) (Eq. 5), which reflects the GCD performance of the classifier \\( h \\), is a weighted sum of three GCD capabilities. However, how are the weights for the three components determined?\n4. In the illustrative experiments (Sections 3.4 and 4.3), the authors employed a similar spatial arrangement for the category space: new classes are situated inside, while old classes are placed outside. Why was this design necessary? Have the authors experimented with other types of layouts?\n\n[1] Sigmoid Loss for Language Image Pre-Training, ICCV2023", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eytlKtuNcP", "reviewer": "Reviewer_Af98", "summary": "This paper introduces Generalized Category Discovery on Graphs (GGCD), a novel task addressing open-world learning on graph-structured data where unlabeled nodes may belong to both known and novel classes. The authors defined a surrogate GCD loss to reflect the GCD performance and established a theoretical bound. To minimize this bound, they argue that it is necessary to reduce the Wasserstein distance between the distributions of known and novel classes while maintaining their independence. Subsequently, they analyze the limitations of existing baseline methods in satisfying these conditions and propose a heuristic approach, SWIRL, to address these challenges. The experiments demonstrate SWIRL’s effectiveness and support the theoretical claims.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for your constructive suggestions!\n\n### **Experimental Designs or Analyses**  \nWe will include a **complexity analysis** in the revised version. Let:  \n- $n$: Number of samples  \n- $K$: Number of prototypes  \n- $I$: SS-KM iterations  \n- $d$: Embedding dimension  \n\n**SS-KM** (executed every $t$ epochs):  \n- **Space**: $O(nd + Kd)$  \n- **Time**: $O(nKId)$ (amortized: $O(nKId/t)$ per epoch)  \n\n**SWIRL loss** (per epoch):  \n- Similarity computation: $O(nKd)$  \n- Denominator summation + division: $O(nK)$  \n- **Total time**: $O(nKd)$  \n- **Space**: $O(nK)$ (similarity matrix)  \n\n**Overall**:  \n- **Time**: $O(TnKd + TnKdI/t)$ → With $I=10$, $t=20$: $O(TnKd)$  \n- **Space**: $O(nK + nd)$  \n- Compared to **InfoNCE** ($O(n^2d)$), this overhead is negligible.  \n\n---\n\n### **Weaknesses**  \n+ **W1**: We will add schematic diagrams to **Sections 3 and 4** for clarity.  \n+ **W2**: This paper’s primary goal is *not* to propose the highest-performing method, but to provide a **theoretical analysis** of parametric GCD’s core motivation—*leveraging old-class knowledge to distinguish new classes*—and validate it via controlled experiments. **SWIRL** serves only to demonstrate that our theory can inspire new designs. Thus, comparisons with state-of-the-art GCD baselines are deferred to future work.  \n\n---\n\n### **Suggestions**  \n**Typos**: Thank you for your meticulous review!  \n\n+ **S1**: We treat node embeddings $z_i$ ($i \\in [N]$) as random variables with pairwise dependencies defined by $\\mathbf{W}$. Here, $W_{ij}=1$ indicates a relationship between nodes $i$ and $j$. $\\mathbf{W}$ can be seen as the underlying graph of node embeddings, charterizing the relationships between node embedding random variables and the corresponding pairwise Markov random field (PMRF). The joint distribution on this PMRF is:  \n  \\[\n  f_k(\\mathbf{Z}, \\mathbf{W}) \\propto \\prod_{(i,j) \\in [N]^2} k(\\mathbf{z}_i - \\mathbf{z}_j)^{W_{ij}}.\n  \\]  \n  Each class corresponds to a connected component/cluster of the graph $\\mathbf{W}$, with its center representing global class position in the embedding space. **Theorems 4.1–4.3** show these centers have *infinite variance*, making their positions uncontrollable. \n  We will add diagrams to illustrate this intuitively in the revised manuscript.  \n\n---\n\n### **Questions**  \n+ **Q1**: The conclusions in **Sec. 4** apply to *all* representation learning methods using **InfoNCE** or **SupCon loss** (thus including GCD [1]). For **Sec. 3**, the assumptions (e.g., Lipschitzness of $h$) do *not* hold for GCD’s SS-KM classifier.  \n+ **Q2**: $\\mathbf{A}$ is the observed graph of $n$ nodes—a tiny subset of $N$ possible (augmented) nodes. Each augmentation step connects these $n$ nodes to another $n$ positives in $\\mathbf{W}_X$ (an $N \\times N$ graph with $N-2n$ isolated nodes). For theoretical purposes, large $N-2n$ does *not* matter, and the methods inspired by theoretical results actually plays with the small $n\\times n$ graph.\n\n[1] *Generalized Category Discovery* , CVPR2022", "claims_and_evidence": "Overall, the claims here are well-supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The datasets are pervasive, and the criteria make sense.", "theoretical_claims": "I have reviewed the proof of Theorem 3.5, and it is substantially correct under the assumptions employed by the authors.", "experimental_designs_or_analyses": "Yes, I reviewed the experimental design and analyses, and overall, they are well-structured and appropriate for validating the paper’s claims. However, one issue is the lack of scalability analysis for SWIRL.", "relation_to_broader_scientific_literature": "The paper advances generalized category discovery (GCD) and (open-world) graph machine learning.\n\n-\tIt extends GCD [1] to graph data\n\n-\tIt introduces a theoretical framework based on Wasserstein distance to quantify the relationships between old and new classes, diverging from prior GCD theories based on mutual information [2] or pairwise consistency distribution [3]. With this framework, a GCD loss upper bound is achieved.\n\n-\tThis loss bound leads to two category relation conditions that the representation learning should meet. And the authors critiques popular graph contrastive learning (GCL) paradigm through a PMRF perspective, revealing its inability to control global category relations. This flaw is not discoverable with prior contrastive learning theory [4]. \n\n-\tAdditionally, it contextualizes known GCN smoothing effects within GCD, demonstrating how oversmoothing disrupts category separation.\n\n\n[1] Generalized Category Discovery\n\n[2] Parametric Information Maximization for Generalized Category Discovery\n\n[3] SelEx: Self-expertise in fine-grained generalized category discovery\n\n[4] Contrastive Learning is Spectral Clustering on Similarity Graph", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths: \n\n-\tThe theory assumptions are well discussed and not very strong.\n\n-\tMany theory claims are verified with controllable experiments excluding irrelevant factors not mentioned in theories.\n\nWeaknesses: \n\n-\tThis paper has so much math stuff that completely grasping it is not easy. \n\n-\tThe three GCD baseline models from the computer vision community are not up to date.", "other_comments_or_suggestions": "Typos:\n\n-\tSection 1. Paragraph 4. Transferrs -> Transfers\n\n-\tP20. Postive-pair-> Positive-pair\n\nSuggestions:\n\nSubsection 4.1 is hard to read for those not familiar with MRF and the underlying probabilistic graph model is not very clear under the context of contrastive learning. It would be helpful to provide some intuitive examples or diagrams to illustrate how MRF concepts integrate with contrastive learning, thereby enhancing the readability and clarity of this section.", "questions_for_authors": "1: It is interesting to know if it is possible to extend the theoretical analysis in this article to non-parametric GCD methods, e.g., GCD [1].\n\n2: What’s the relationship between $\\mathbf{W}_X$ in Sec. 4 and the data graph $\\mathbf{A}$?\n\n[1] Generalized Category Discovery", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cUTl9zqQJN", "reviewer": "Reviewer_Mgiw", "summary": "This paper first proposes a theoretical analysis about parametric GCD, and then design a new graph contrastive learning method, SWIRL, with the insights from the theoretical analysis. They propose the first GCD loss upper bound theory and identifying some necessary conditions about category relationships for good GCD performance. Besides, they reveal that the current GCL methods can not satisfy these conditions from the lens of a pairwise Markov random field. The proposed GCL method alleviates the randomness of category relation in the embedding space.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the helpful comments and guidance!\n\n### **Weaknesses**  \n\n+ **W1**: You are absolutely right! Thank you for your meticulous attention. We will revise this.\n+ **W2**: In subsequent calculations involving **W**, we set $\\lambda = 1$, with assuming that the embeddings and labels are important equally.  \n+ **W3**: The **H-score** in [1] is essentially the harmonic mean of **New ACC** and **Old ACC** (defined in **Appendix G.1**), both computed after remapping all classes via *linear sum assignment*. This may maps true new classes as old classes and vice versa, intruding the GCD purpose. Our proposed **HRScore** improves upon this by harmonizing **New RACC** and **Old RACC**—*without* remapping new clasess to old ones —better fitting GCD’s objectives. For formulas and distinctions, see **Appendix G.1**.  \n+ **W4**: Here, $n$ is the number of *observed* nodes in the graph dataset, while $N$ represents the total *potential* nodes (e.g., in citation networks, $N$ includes unpublished/unobserved papers). During contrastive learning, augmentations on $n$ nodes effectively select positive samples from $N \\gg n$ nodes based on human priors.  \n+ **W5**: You’ve identified a key point we didn't elaborate on for a not that length manuscript. In the computation of Wasserstein distances in **Secs. 3 and 4**, class labels $\\mathbf{y}^c$ are *not* one-hot. For example, in **Fig. 1**, adjacent old (yellow, $c=1$) and new (blue, $c=5$) classes are assigned:  \n  $$\n  \\mathbf{y}^1 = [0.95, 0, 0, 0, 0.05, 0, 0, 0, 0], \\quad \\mathbf{y}^5 = [0.05, 0, 0, 0, 0.95, 0, 0, 0, 0].\n  $$\n  Similar setups apply to other adjacent (old, new) class pairs. All **Wasserstein distances** in **Secs. 3–4** are computed under this scheme.  \nSome experiments conducted by us but not included in this manuscript show such *non-one-hot* labels generally improve GCD performance since such semantic-aware labels facilitate transfering the knowledge of distinguishing old classes into distinguishing new ones, aligning with our statement that \"*embedding-space category relations (distances) are random and hard to align with semantic relations in $\\mathcal{Y}_C$*\".  \n\n---\n\n### **Questions**  \n\n+ **Q1**: Using our notation, the differences between [2] and our work are summarized below, where $\\pi$ is our *relation prior* in embedding space and $\\mathbf{B}$ is the prior in the input space. Our key point lies in constructing a **PMRF** for embeddings and introducing posterior probabilities for the node relation graph $\\mathbf{W}$ in the embedding space:  \n\n  |                | [2]                          | Ours                                                                 |  \n  |----------------|------------------------------|----------------------------------------------------------------------|  \n  | **Input Space**  | $P(\\mathbf{W}_X; \\mathbf{B})$ | $P(\\mathbf{W}_X; \\mathbf{B})$                                    |  \n  | **Embedding Space** | $P(\\mathbf{W}; \\mathbf{Z})$ | $P(\\mathbf{W} \\mid \\mathbf{Z}) \\propto P(\\mathbf{Z} \\mid \\mathbf{W}) P(\\mathbf{W}; \\pi)$ |  \n\n+ **Q2**: Our design is motivated by:  \n  1. **Reduced computation**: Running **SS-KM** on $n$ samples is far cheaper than on $2n$.  \n  2. **Enhanced consistency**: Prototypes derived from *averaged node embeddings* resemble clustering \"mini-cluster\" centroids from paired views, improving positive-pair alignment. Our empirical tests confirm that this strategy is better.  \n\n+ **Q3**: **SWIRL**’s distinction from other prototype contrastive methods is its *multi-level repulsion force*, whose efficacy is highlighted in **Line 2015 (p.38)** of the manuscript.  \n\n---\n\n### **References**  \n[1] *Transfer and Alignment Network for Generalized Category Discovery* , AAAI2024\n\n[2] *Contrastive Learning is Spectral Clustering on Similarity Graph*, ICLR2024", "claims_and_evidence": "Yes, all the claims made in the submission supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "Yes, the methods and evaluation criteria make sense for the problem at hand.", "theoretical_claims": "Yes. I have checked the proofs of the main results, i.e., Theorem 3.5 and Theorem 4.3. I didn't see any obvious mistakes.", "experimental_designs_or_analyses": "I have reviewed all the experimental designs. I think these experiments are essentially complete and can support the authors' claims.", "relation_to_broader_scientific_literature": "This article presents the first systematic theoretical analysis of GCD methods that employ a parametric classifier, addressing a gap in the current theoretical understanding of GCD methods. The authors' analysis of contrastive learning approaches utilizing InfoNCE and SupCon loss functions can, in fact, be regarded as an independent contribution to the theory of contrastive learning.", "essential_references_not_discussed": "The references are comprehensive.", "other_strengths_and_weaknesses": "**Strengths**:\n\n1. Current (parametric) GCD methodologies lack a systematic theoretical analysis, and this paper fills that void.  \n2. The theoretical analysis in this paper inspired the authors' proposed SWIRL method, which has demonstrated high experimental performance. This indicates that the authors' theories can, to some extent, guide the design of GCD methods, a trait that is highly commendable in theoretical work.\n3. The visualization of representations and decision boundaries (as depicted in Figures 1-3) intuitively elucidates the implications of the principal findings in Sections 3 and 4, thereby facilitating an understanding of the main theoritical results.\n\n**Weaknesses**:\n\n1. If I have not misunderstood, the term $D_{KL}(P_{\\mathcal{C}}\\|\\bar{h})$ included in the upper bound, according to Proposition 3.9, should originate from a prerequisite condition: the data distribution is class-balanced. However, the authors did not declare this condition in Theorem 3.5.  \n2. This paper employs the Wasserstein distance (Definition 3.1) to quantify the relationship between old and new categories, which incorporates a hyperparameter $\\lambda$ that balances the influence of features and labels. However, the subsequent calculations do not elucidate the determination of this value or the methodology for its selection (e.g., in Figure 1).\n3. The new evaluation metrics proposed in this paper, such as HRScore, appear to actually come from existing work [1].\n4. The meaning of $N$ in line 263, p5 is not given. What’s the difference between $N$ here and $n$ in Section 2.1?\n5. In Sections 3 and 4, the authors demonstrate the embedding space and the Wasserstein distance between old and new categories in this space. Calculating this Wasserstein distance requires considering the semantic distances between categories in the label space. However, if the authors consider one-hot labels, the semantic distance between any pair of categories \\( u \\) and \\( l \\) would be the same as that between \\( u \\) and \\( l' \\). This implies that the distance would effectively reduce to a Wasserstein distance based solely on the representations \\( z \\). As a result, the authors' statement in line 290—\"the embedding relations (i.e., distances) between categories are random and thus not easy to be aligned with the (either known or unknown) category semantic relations in \\(\\mathcal{Y}_C\\)\"—would become less meaningful.\n\n\n[1] W. An et al., “Transfer and alignment network for generalized category discovery,” in Proceedings of the AAAI Conference on Artificial Intelligence, 2024.", "other_comments_or_suggestions": "It appears that Lemma D.3 in Appendix D has not been utilized. Please verify this point and make the necessary revisions.", "questions_for_authors": "- Q1: In line 285, p6, the authors state that “The above presents a more refined treatment of the embedding space than [1]”. Can you provide more details about this comparison?\n\n- Q2: In the propsoed SWIRL, the authors derive prototypes by clustering the average representations across two views. The rationale for not clustering the complete set of representations from both views remains unaddressed. Is there a discernible difference in performance between these two approaches?\n\n- Q3: Prototype-based contrastive learning methods have been extensively explored in the literature. The advantage of SWIRL over these existing approaches appears to be primarily rooted in its theoretical motivation. Are there any other distinctive features that significantly differentiate SWIRL from current prototype-based contrastive learning methods?\n\nI may change my score based on the authors' rebuttal regarding weaknesses and questions.\n\n[1] Z. Tan, Y. Zhang, J. Yang, and Y. Yuan, “Contrastive Learning is Spectral Clustering on Similarity Graph,” presented at the The Twelfth International Conference on Learning Representations, 2023.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper presents the first theoretical analysis of parametric generalized category discovery (GCD) on graphs, introducing a GCD loss upper bound and identifying conditions under which old-class knowledge benefits the discovery of new categories. The proposed SWIRL framework is derived from these insights and empirically validated. Key concerns were raised initially, including the scalability and efficiency of SWIRL and technical details. The authors provided comprehensive and thoughtful responses to all raised issues, and the consensus is that it meets the bar for acceptance.
Decision: Accept (poster)