Towards Understanding Parametric Generalized Category Discovery on Graphs

Thank you for the helpful comments and guidance!

Weaknesses

• W1: You are absolutely right! Thank you for your meticulous attention. We will revise this.
• W2: In subsequent calculations involving W, we set $\lambda = 1$, with assuming that the embeddings and labels are important equally.
• 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.
• 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.
• 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: $$\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].$$ Similar setups apply to other adjacent (old, new) class pairs. All Wasserstein distances in Secs. 3–4 are computed under this scheme.
  Some 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$".

---

Questions

• 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:

  	[2]	Ours
  Input Space	$P(\mathbf{W}_X; \mathbf{B})$	$P(\mathbf{W}_X; \mathbf{B})$
  Embedding Space	$P(\mathbf{W}; \mathbf{Z})$	$P(\mathbf{W} \mid \mathbf{Z}) \propto P(\mathbf{Z} \mid \mathbf{W}) P(\mathbf{W}; \pi)$

• Q2: Our design is motivated by:

  1. Reduced computation: Running SS-KM on $n$ samples is far cheaper than on $2n$.
  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.

• 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.

---

References

[1] Transfer and Alignment Network for Generalized Category Discovery , AAAI2024

[2] Contrastive Learning is Spectral Clustering on Similarity Graph, ICLR2024

We are grateful for your constructive suggestions!

Experimental Designs or Analyses

We will include a complexity analysis in the revised version. Let:

• $n$: Number of samples
• $K$: Number of prototypes
• $I$: SS-KM iterations
• $d$: Embedding dimension

SS-KM (executed every $t$ epochs):

• Space: $O(nd + Kd)$
• Time: $O(nKId)$ (amortized: $O(nKId/t)$ per epoch)

SWIRL loss (per epoch):

• Similarity computation: $O(nKd)$
• Denominator summation + division: $O(nK)$
• Total time: $O(nKd)$
• Space: $O(nK)$ (similarity matrix)

Overall:

• Time: $O(TnKd + TnKdI/t)$ → With $I=10$, $t=20$: $O(TnKd)$
• Space: $O(nK + nd)$
• Compared to InfoNCE ($O(n^2d)$), this overhead is negligible.

---

Weaknesses

• W1: We will add schematic diagrams to Sections 3 and 4 for clarity.
• 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.

---

Suggestions

Typos: Thank you for your meticulous review!

• 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:

$

f_k(\mathbf{Z}, \mathbf{W}) \propto \prod_{(i,j) \in [N]^2} k(\mathbf{z}_i - \mathbf{z}j)^{W{ij}}.

$

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. We will add diagrams to illustrate this intuitively in the revised manuscript.

---

Questions

• 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.
• 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.

[1] Generalized Category Discovery , CVPR2022

We sincerely thank you for the valuable comments that helped improve our paper!

---

Claims and Evidence

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.

For 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.

Experimental Designs or Analyses

The 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.

Additionally, 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.

Weaknesses

• W1: We will promptly release the code and document all hyperparameter settings in configuration files.
• 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.
• W3: Thank you—we will explicitly clarify the paper’s scope in the revision.
• W4: We will add schematic diagrams for Sections 3 and 4 to improve readability.

Suggestions

• 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.
• S2: Practical examples will be added in the revised version.

Questions

• Q1: Yes, except the content about GCN encoder.
• Q2: Excluding global normalization violates the PMRF’s fundamental dependency assumption, making our framework incompatible with such losses.
• Q3: This ultimately depends on which capability is prioritized in a specific application. Regarding the theoritical side, it does not influence the bound formulation.
• Q4: Please refer to Claims and Evidence.

[1] PolyGCL: GRAPH CONTRASTIVE LEARNING via Learnable Spectral Polynomial Filters, ICLR2024

Thanks for your constructive suggestions! We hope the response can address your concerns.

• 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.

• 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.

• W3: We have carefully checked the entire manuscript to ensure no similar errors remain.

• 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.

• 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.

• 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.

• 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.

[1] Prototypical Contrastive Learning of Unsupervised Representations, ICLR 2021.