GLNCD: Graph-Level Novel Category Discovery
Authors: Bowen Deng
Lele Fu
Sheng Huang
Tianchi Liao
Jialong Chen
Zhang Tao
Chuan Chen
Venue: NeurIPS 2025 poster ()
Keywords: Novel category discovery
Open-world learning
Graph neural network
Primary area: deep_learning

Abstract: Graph classification has long assumed a closed-world setting, limiting its applicability to real-world scenarios where new categories often emerge. To address this limitation, we introduce Graph-Level Novel Category Discovery (GLNCD), a new task aimed at identifying unseen graph categories without supervision from novel classes. We first adapt classical Novel Category Discovery (NCD) methods for images to the graph domain and evaluate these baseline methods on four diverse graph datasets curated for the GLNCD task. Our analysis reveals that these methods suffer a notable performance degradation compared to their image-based counterparts, due to two key challenges: (1) insufficient utilization of structural information in graph self-supervised learning (SSL), and (2) ineffective pseudo-labeling strategies based on ranking statistics (RS) that neglect graph structure. To alleviate these issues, we propose ProtoFGW-NCD, a framework consisting of two core components: ProtoFGW-CL, a novel graph SSL framework, and FGW-RS, a structure-aware pseudo-labeling method. Both components employ a differentiable Fused Gromov-Wasserstein (FGW) distance to effectively compare graphs by incorporating structural information. These components are built upon learnable prototype graphs, which enable efficient, parallel FGW-based graph comparisons and capture representative patterns within graph datasets. Experiments on four GLNCD benchmark datasets demonstrate the effectiveness of ProtoFGW-NCD.

GLNCD: Graph-Level Novel Category Discovery
Bowen Deng Sun Yat-sen University
Lele Fu Sun Yat-sen University
bowen. www.ddeggmaan..oomm coo
Sheng Huang Sun Yat-sen University
Tianchi Liao Sun Yat-sen University
Jialong Chen Sun Yat-sen University
Tao Zhang
Chuan Chen
Sun Yat-sen University
Sun Yat-sen University
zhangt338@mail sysu. edu. sysu.edu. cn
chenchuan@mail sysu. edu. cn
Abstract
Graph classification has long assumed closed-world setting, limiting its appli- cability to real-world scenarios where new categories often emerge. To address this limitation, introduce Graph-Level Novel Category Discovery (GLNCD), a new task aimed at identifying unseen graph categories without supervision from novel classes. We first adapt classical Novel Category Discovery (NCD) methods for images to the graph domain and evaluate these baseline methods on four di- verse graph datasets curated for the GLNCD task. Our analysis reveals that these methods suffer notable performance degradation compared to their image-based counterparts, due to two key challenges: (1) insufficient utilization of structural information in graph self-supervised learning (SSL), and (2) ineffective pseudo- labeling strategies based on ranking statisties (RS) that neglect graph structure. To alleviate these issues, propose ProtoFGW-NCD, a framework consisting of two core components: ProtoFGW-CL, a novel graph SSL framework, and FGW-RS, structure-aware pseudo-labeling method. Both components employ differen- tiable Fused Gromov-Wassersen Wasserstein (FGW) distance to effectively compare graphs by incorporating structural information. These components are built upon learnable prototype graphs, which enable efficient, parallel FGW-based graph comparisons and capture representative patterns within graph datasets. Experiments four GLNCD benchmark datasets demonstrate the effectiveness of ProtoFGW-NCD.
Introduction
Graph neural networks [70, 10, 1, 6] have become important in modern machine learning, finding applications in diverse domains such as protein function prediction [55], malware detection [2], and social network analysis [71]. However, most existing methods assume either closed-world setting [70, 68, 74], where all test categories are known during training, or an unsupervised setting, where no categories are known [43, 42, 12, 64, 22]. In real-world scenarios, this assumption often breaks down: new graph categories may emerge dynamically (e.g., novel protein structures or previously unseen software behaviors), requiring models adapt to open-world setting. Despite the importance of this challenge, the problem discovering novel graph categories remains unexplored.
We introduce graph-level novel category discovery (GLNCD), task that extends graph classifi- cation to open-world scenarios. Different from node-level NCD [32, 34, 11] aiming to discover new
Corresponding author.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

node categories, GLNCD is to discover novel graph classes (i.e., cluster unlabeled graphs) without explicit label supervision for these classes. In Section 3.1, we construct four diverse GLNCD datasets spanning various graph classification domains, including bioinformatics [55], program analysis [21], social networks [71], and graph-baseds image classification [15]. These datasets serve as benchmarks for evaluating GLNCD methods and highlight the unique challenges posed by graph data.
We adapt classical visual NCD methods (originally designed for image data) [78, 27, 80, 60] to the GLNCD setting. A typical visual NCD method is comprised of self-supervised learning (SSL), supervised learning on known classes, and category discovery. By replacing these components with the counterparts in graph domain (e.g, replacing SSL [23, 24, 5, 7, 9, 76] with Graph SSL [56, 75. 73, 66, 41, 72, 81, 82, 73, 12, 35D, we get the graph variants of visual NCD methods (detailed in Section 3.2). Surprisingly, our experiments (see Figure 1 and Table 2) reveal that these adapted methods perform significantly worse on graph data than on image data. Through systematic investigation presented in Section 4, we identify two key limitations contributing to this underperformance: 1) Existing graph-level SSL methods fail fully exploit the structural information in graphs, resulting in suboptimal graph encoders. 2) The unlabeled sample pscudo-labeling strategy commonly used in visual NCD, ranking statisties (RS) [27]. does not account for the structural information of graphs, leading to low-quality pseudo-labels for unlabeled graph samples.
To address the above limitations, we propose ProtoFGW-CL CL. a new graph SSL framework, and FGW- RS, structure- aware sycudo-labeling method. They constitute our GLNCD method, ProtoFGW-No (Section 5), and both rely on the Fused Gromov-Wassersten (FGW) distance [59, 391, which enables structural comparison between attributed graphs- beyond readout vectors in baseline methods. However, computing pairwise FGW distances between two batches of graphs 91 and G2 with varying sizes is inefficient using the BAPG solver [39] from existing tools [20]. To address this, we design a differentiable BAPG layer that supports efficient parallel computation during both forward and backward passes (Section B). Our BAPG layer assumes that the second group of graphs has uniform size. To handle variable-sized input graphs, we introduce K learnable prototype graphs (I)) of identical size. We then compute the FGW distance matrix V1 E g between G1 and ((B), and V2 between G2 and G By comparing V1 and 22, we derive the pairwise relationships between 9i and G2. which are central to graph SSL and unlabeled graph pseudo-labeling To make ((B) more than just computational intermediaries, we treat them as learnable parameters following [5]. These prototypes are updated through BAPG layer during training, enabling them to capture representative structural patterns from the dataset, thereby benefiting graph SSL and pseudo-labeling.
Contributions: 1) We introduce graph-level novel category discovery (GLNCD), new task that extends graph-level classification to open- woold scenarios, along with four diverse benchmark datasets spanning multiple domains. 2) We adapt classical visual NCD methods to the graph domain and conduct systematic analysis, revealing their limitations in sufficiently capturing structural information in graphs. 3) To address these limitations, we propose ProtoFGW-NCD, a novel GLNCD method built upon differentiable Fused parallel, differentiable BAPG layer for extremely efficient pairwise FGW distance computation.
(FGW) distance. 4) We design
2 Related Work
2.1 Visual Novel Category Discovery for Image Data
Novel Category Discovery (NCD) for image data has been well studied. AutoNovel [27] generates binary pairwise pseudo-labels for unknown samples using ranking statistics (RS), providing learning signals for the ML.P-aaedd clustering head. The quality of these pseudo-labels is closely tied to the representation quality output by the encoder. Incorporating contrastive loss [80] can enhance both representation and pseudo-label quality, thereby improving NCD performance. Exploiting multi-scale representation can improve pseudo-label reliability; for instance, DuaIRS [78] leverages both global and local branches to capture large-scale and tine-nrained visual information, respectively. UNO [19] introduces a funkhorn-based approach to generate pseudo-labels without requiring pairwise comparisons. To better leverage knowledge from known categories, rKD [25] employs fixed, supervised encoder with a known category head to constrain model outputs on known classes during the discovery training phase. Vaze et al. [61] and Cao et al. [4] propose more challenging setting where the model must classify known-category samples and cluster unknown-category samples simultancously during inference. While these methods perform well on regular image data, adapting

---

them to graph- struuturt data requires tailored modifications. We find that straightforward adaptations, such as replacing CNN encoder with GNN encoder, yield poor performance (see Figure 1 and Table 2), suggesting the need for more exploration.
2.2 Open World Graph Learning
Recent graph learning research has begun tackling open-world settings, where a node's class may be one that was unseen during training. In the node classification context, this gives rise to open-set recognition (OSR) problem: the model must classify nodes from known classes while identifying any nodes belonging to novel classes as "unknown."" The seminal OpenWGL method [67] tackles this by learning uncertainty-avee novel classes yield high predictive uncertainty and can be automatically rejected during inference. Hoffimann et al. [31] propose a meta-mode that aggregates multiple confidence scores and employs a weakly-supervised thresholding strategy to decide when to label node as unknown. Zhang et al. [77] propose to generate proxy nodes for unknown categories, tackling inductive node OSR problem. Beyond merely rejecting unknown nodes, NCD methods to cluster unlabeled nodes are proposed. ORAL [34] detects and remove the edges linking old and novel categories to alleviate the bias towards old categories, and uses multi-layer predictions generate pseudo labels for unknown nodes. Hou al. [32] consider a different NCD task that provides old-class nodes in the first training stage and then novel-class nodes in the second one. It is worth noting that open-world graph learning has been explored almost exclusively at the node level so far, and our work is the first to focus on graph-level.
node embeddings via a variational GNN, so that nodes from
3 Datasets and Baselines Adapted from Visual NCD
3.1 Prepare GLNCD datasets
Novel Category Discovery (NCD) can be viewed as a relaxed version of multi-clas classification, where the goal is group samples from the same novel category into the same cluster, without requiring them to be assigned to a specific label (c.g., = 0). Therefore, one common approach to constructing an NCD dataset to treat a subset of classes in a standard multi-class classification dataset as novel categories.
Although over 120 public graph-level datasets [50, 15] are available, observe that only about five real-world multi-class graph classification datasets exist outside of computer vision scenarios. From these, we select three representative datasets spanning diverse domains, which, together with CIFAR10 (graph) [15], form the benchmark for GLNCD (Table 1). Bioinformatics: Graph structures naturally model protein molecules, where nodes represent secondary structure elements and edges indicate either sequential or spatial proximity between elements. The ENZYMES dataset [55, 50] contains six types of proteins with different catalytic functions. We treat the first three classes as old categories and the remaining three as novel categories. Program Analysis: The MalNet- dataset [21] consists of function call graphs (FCGs) derived from Android APK static disassembly. Each graph corresponds to program type (Addisplay, Adware, Benign, Downloader, Trojan). We use the first three classes as old categories and the last two as novel categories. Social Networks: In the REDDITI2K dataset [71, 50], each graph represents discussion thread, where nodes correspond to users and edges denote comment responses. The dataset contains 12 types of graphs, each corresponding to a subreddit. We designate the first six classes as old categories and the last five as novel categories. Computer Vision: An image can be decomposed into super-pixels, each forming node whose features are computed the average RGB values and spatial coordinates of the constituent pixels. Each node is connected to its eight nearest neighbors via edges weighted by Gaussian similarity. The CIFARI0 (graph) dataset [15] is constructed from CIFARIO (image) [38] in this way. And we treat the first five classes as old categories and the rest as novel ones.
Luo et al. [46] incorporated various modern deep learning techniques, e.g., batch normalization [33] and residual connections [30], into GCN [37] and GIN [70] for graph-level tasks. More importantly, they employed Random Walk Structural Encoding (RWSE) [40, 16] as a preprocessing step to extract structural information, which then used as part of the node and edge features. For all four datasets used in this work, we also apply OWSE-based preprocessing with maximum path length of 32.
3

---

Table Overview of GLNCD datasets. # steps is the maximal random walking length [46].
Dataset
# graphs
Avg. # nodes
Avg. # edges
# node/edge Teats
# steps
# #ldd/nww classes
ENZYMES
6000
32.6
124.3
21/0
32
3/3
MalNet-Tin
5000
1410.3
2859.9
0/0
32
2/3
REDDITI2K
11929
391.41
456.89
0/0
32
5/6
CIFARIO
60000
117.6
941.1
5/1
32
5/5
3.2 Design GLNCD Baselines with Visual NCD Methods
A number of NCD methods have been developed in the field of computer vision. If these can be directly adapted the graph-level setting, it would offer a convenient solution GLNCD. To explore this, we adapt three representative visual NCD methods, i.e., AutoNovel [27], NCL [80], and DualRS [78], to the graph domain. These models typically consist of an encoder fo and two classification heads: ht (for novel categories) and h, (for old known categories). The encoder is trained using SSL, the old-class head trained with standard supervised signals from labeled samples, and the new-class head relies on specifically designed laeeul-labeligg strategies for training. By replacing each component with its counterpart in the graph domain, we achieve straightforward adaptation.
AutoNovel: (Stagel) Originally employs a RotNet approach [23] for pre-training, where the encoder learns recognize rotation angles (0', 90" 180%, or 270") to capture semantical image features. (Stage 2) After pretraining, the GNN encoder and the old-class head is trained on old-class samples. (Stage 3) Finally, the new-class head is trained using pairwise ranking statistics (RS) pseudo- generated with new-class sample representations. Adaptation: Since graph data consists of abstract topological structures without spatial orientation, we replace RotNet with GraphCL [75], a contrastive learning method tailored for graph-level tasks. Other stages remain unchanged.
NCL: Builds upon AutoNovel by introducing MoCo-style [29] contrastive loss in (Stage 3), where negative samples are drawn from queues representing labeled and unlabeled data. Positive pairs include augmented views of the same sample and samples sharing the same old class label [36]. A hard-negative mining strategy is also incorporated [54]. Adaptation: The readout outputs of the encoder are Euclidean, so the changes of NCL from AutoNovel can directly fit into graph domain.
DualRS: (Stage 1) Abandons the RotNet- pretrriee ResNet18 and instead uses a ResNet50 backbone pretrained on ImageNet [13] with MoCoV2 [8]. (Stage 2) is removed. (Stage 3) Both classification heads are equipped with global and local branches. The global branch captures coarse- coarse-grained representations, while the local branch focuses fine-grained details. Each branch generates pseudo- labels via RS to train its respective head, and then distilled to the other branch. Adaptation: We use GraphCL. pretrain the GNN encoder. All other components remain unchanged.
We largely retain the original names of the visual NCD methods when referring to their adaptations for the graph domain. To avoid possible confusion in some cases, we prefix them, in these instances, with "G-" " and refer to them as G-AutoNovel, G-NCL, and G-DualRS, respectively.
Challenges in NCD Method Adaptation: From Image to Graph Data
In this section, reveal the failure of adapting the visual NCD methods to the graph domain like Section 3.2, and analyze the underlying reasons.
4.1 Why Direct Adaptation Fails? Ranking Statisties (RS) Fails
Table 2 shows the performance of AutoNovel on three image datasets, well as its adapted version for graph-level tasks on four GLNCD datasets (Section 3. 1),, following the modifications described in Section 3.2. The New ACC (Train) on graph datasets, which is the primary metric of interest in NCD, is significantly lower than that on image datasets. More importantly, we observe a substantial perfor- mance gap between novel-class and old-class samples on graph datasets (Table 2). a phenomenon not present in image datasets. This suggests that the direct adaptation of AutoNovel fails to effectively leverage knowledge from old classes to aid in clustering unlabeled novel-class samples.
Given that lseudo-label quality plays a critical role in the performance of NCD methods, we hypothesize that the observed failure is due to the inability of RS to produce reliable pabudo-labels

---

0.9
CIFARO zimage) ENZYMEE (Srash)
0.25
CIRAR1O (Image)
ENZYMES (Sraph)
0.8
0.32
0.20
Num ACC
0.7
CIFR11 Image))
0.30
0.6
ENZYMES (Gresh)
0.28
0.30
0.5
0.26
0.4
0.22
150
Thaining Epochs
Tatning Epochs
(a) The clustering accuracy unla-(b) (b) The MCC (quality) of RS pseudo (c) The ratio of positive RS beled new-class samples.
labels for sample pairs.
pseudo labels for sample pairs.
Training dynamics of AutoNovel [27] on CIFAR1O (image) and ENZYMES (graph). (a) The performance on unlabeled training dataset. (b) The Matthews Correlation Coefficient (MCC) to evaluate the quality of pairwise pseudo-labels generated via ranking statistics (RS). (c) The ratio of samples for which at least one true positive (same-class) pair is identified by RS. The definitions of these two pseudo-label metrics and the rationale for their selection are provided in Appendix A.
Figure 1:
Table 2: The average performance (over 10 runs) of AutoNovel [27] image and graph datasets. Old ACC (Test) is the accuracy on the old-class samples in test dataset. New ACC (Train) is the clustering accuracy the unlabeled training dataset. The last row is the gap between these metrics.
Datasets
Image
Graph
CIARRO
CIFARTO0
SVHN
ENZYMES
MaiNet-
REDDIT12K
CIFARTO
Old ACC (Test)
95.34
74.51
98.10
73,00
93.30
67.59
61.36
New ACC (Train)
88,50
74.28
94.21
41,90
74.51
39.21
41.67
Old (rowl)- New (row2)
6.84
0.23
3.89
31.10
18.79
28.38
19.69
on graph-based datasets. To verify this, we track the New ACC (Train) along with RS pseudo- label quality CIFAR-10 (image) and ENZYMES (graph), as shown in Figure 1. The results indicate that RS produces higher-quality pseudo-labels on CIFAR-10, with an overall increasing trend during training (Figure lb and Ic). In contrast, ENZYMES, the quality of pseudo-labels remain consistently low throughout training, suggesting that RS fails on graph-structured data in the direct adaptation described in Section 3.2.
4.2
Why RS Fails? Insufficient Exploration of Graph Structure
Ranking statistics (RS) generates pseudo-labels based on the representations output by the encoder (see Appendix A for the details of generation). If the encoder produces high-quality representations (i.c.. samples from the same class are similar and those from different classes are dissimilar), the resulting RS pscudo-labels are typically of higher quality.
We therefore suspect that the representation learned by GraphCL in G-AutoNovel not sufficiently discriminative. This hypothesis would be supported if higher-quality representations led to better pseudo-labels. However, according to recent reports [69, 26, 79], GraphCL performs well or better than other graph SSL methods across wide range of datasets, suggesting that replacing GraphCL with alternative SSL methods would not yield a significant improvement representation quality for comparison purposes. To validate our hypothesis in another way, we pretrain three GNN encoders with increasing representation quality using the Supervised Contrastive (SupCon) loss [36], under settings where 0% (i.c., standard SSL), 50%, and 100% of the ground-truth binary pairwise labels are known. We then evaluate how the quality of RS pscudo-labels and NCD performance vary across these three levels of representation qualities.
Contrary to expectations, the quality of RS pseudo-labels (Figure 2b and 2c) shows little difference across the three representation qualities. Strikingly, despite nearly identical pseudo-label quality, the final NCD performance varies significantly across the three setups. 1) This suggests that representation quality primarily influences the pseudo-label utilization rather than the pseudo-label quality itself: higher-quality representations provide better data manifold, which facilitates learning better decision boundaries even when laeudo-labels are of comparable quality. 2) This result does not imply that
5

---

0.7
0.036
New ACC (CC
0.6
SupSon
Supton
0.250
0.055
SupCon
Braty MCC
0.034
0.5
0.023
0.246
0.032
0.4
0.021
0.242
50
1.50
300
150
150
200
Training Ebochs
(a) The clustering accuracy unla-(b) The MCC (quality) of RS pseudo (c) The raito of true positive RS
beled new-category samples.
labels for sample pairs.
pseudo labels for sample pairs.
Training dynamics of G-AutoNovel [27] on ENZYMES (graph). Three GIN encoders are pretrained with 0% (SSL), 50% (SupCon), and 100% (SupCon). true binary pairwise labels. (a) The performance on unlabeled training dataset. (b) The Matthews Correlation Coefficient (MCC) to evaluate the quality of RS pseudo-labels. pair is identified by RS. The details about of these pseudo-label metrics are provided in Appendix A.
Figure 2:
(c) The ratio samples for which at least one true positive
representation quality has impact pseudo-label quality: as shown in Figure on CIFAR- 10 (image), RS pseudo-label quality improves substantially as the encoder learns better representations during training. Therefore, the nearly identical pseudo-label quality is likely due to the fact that RS is not well-suited to graph data and thus cannot effectively leverage improvements in representation quality to generate better pseudo-labels. We attribute the failure of RS to principal factors: 1) insufficient GNN pretraining that limits the representation quality and thus RS pseudo-label utilization; 2) RS is unsuitable for graph data and fails improve pseudo-label quality even when representation quality increases. Both issues stem from insufficient exploitation of graph structure:
Methods like GraphCL. do not make sufficient use of structural information, resulting in suboptimal representations:
RS operates solely on the readout graph representation vectors, thereby discarding part of valuable graph-structure information.
5 Proposed Method: ProtoFGW-NCD
To test our hypothesis from Section 4.2 that the absence of structural information adversely affects both the SSL (i.e., GraphCL) and RS modules of Auto developed ProtoFGW-NCD (Figure 3). This method was designed as controlled experiment; mirrors the architecture of AutoNovel exactly, with the sole exception of a Bregman Alternating Projected Gradient (BAPG) layer that injects structural information into the SSL. and RS pipelines. Crucially, this integration requires no auxiliary loss functions or sophisticated mechanisms. This design provides clean and direct means to validate our claim by allowing any performance difference to be attributed solely to the inclusion of structural information. The differentiable BAPG layer functions by solving the optimal transport problem between batches of attributed graphs [59, 65, 53], yielding rich structural information for graph comparison. With the inclusion of this layer, the original SSL and RS components of AutoNovel are adapted into our proposed ProtoFGW and FGW-RS modules, respectively.
5.1 ProtoFGW-CL: Graph-level Representation Learning by Swapping Transport Couplings
GraphCL [75] utilizes graph structure only in the message-passing phase of the GNN encoder. The contrastive loss is computed solely on Euclidean vectors obtained via readout operations (e.g., min, sum), and does not explicitly compare struetural differences between graphs G; and G, at this critical stage. Other graph-level SSL methods not only perform similarly to GraphCL but also fail to make full use of graph structure. For instance, some approaches generate views based on structural information (e.g., graph diffusion, communities, or motifs) [62, 57, 28, 58], while others employ multi-channel encoders to exploit more the original graph [69, 47]. However, like GraphCI., they all ignore structures when computing the distances between different graphs graph views.

---

To address this, we propose ProtoFGW-CL, a graph-level contrastive learning method that ex- plicitly computes the distances considering graph structures. Specifically, we compute the Fused Gromov- Wasserstein (FGW) distances between each graph and prototype graphs, normalizes it into codes, and enforces consistency across views. These randomly initialized prototype graphs
{at (A 2
(B) B)) | E E Ne K
(B) ERNx
) K
establish the coordinates for cross-
k=1
view structure- graph comparisons, and are learned with backpropagation to capture represen- tative graph patterns in dataset. The FGW distance (Definition 2) [59, 39] between two graphs is defined as the optimal transport between their probability measures given by Definition 1.
Definition 1. (Graph as Probability Measure) An attributed graph G1 (C1, X1) with Ni = [Vi nodes defines a metric-measure (MM) space (V1, C1, f1). Each node v2 has an explicit node feature vector X1, E 22 C Rd and an implicit structural feature S1,4 E Sz The pairwise relationship among structural features is encoded in C₁. where Cı, Da, (81, S1,g) (1,)) typically represented as an adjacency or Laplacian matrix. The probability measure associated with G1 is defined as μ41 =
Ei h, (1.),....)) where (2) HN = {
is a simplex histogram, R Eim h4 -11 }}
and (x..)) denotes the Dirac delta function located at (S1,5; x1,5).
Definition (FGW distance) Given two attributed graphs G1 (C1, X1) and G2 = (C2, X2), their corresponding probability measures are μ1 Σ h. (x.,)) and μ1 = Ej= 11 ( (2.)) respectively. The FGW distance between them is defined as
N₂ Σ
inf TEll
D2 - (1-aa)Ds (a)) + (lCi (
(I)
where II = =T RNNN TIN, T h(2)) is the feasible set of transport plans, H())) and (2) denote marginal distributions and are typically set to uniform distributions in practice, Do. is a metric in Qz and a E [0, 1] balances the contributions of node features and graph structures.
5.2 FGW-RS: Ranking Statisties with More Graph Structure Information
G-AutoNovel applies ranking statisties (RS) to the Fuclidean readout summary vectors, while graph structure is only implicitly used during message passing. Given the importance of structural information in graph-level tasks, this utilization is insufficient. To enable RS to more directly incorporate graph structure information, we construct two attributed graphs from the representations before readout G = (A,, Z₁) and G = (A2, Zz), corresponding to the two graph samples. We then compute their FGW distances to a set of prototype graphs, resulting in distance vectors V1, V2 E RRK 20.
which are subsequently fed into classic RS used in [27].
The prototype graphs, learned during training, capture diverse representative structural patterns in the dataset. The FGW distances VI, V2 explicitly encode both the input samples' structures and their relations to global patterns in the dataset. This allows RS to generate pseudo-labels that better reflect structural information, thereby improving the quality of pseudo-labels.
5.3 ProtoFGW-NCD: Integrating ProtoFGW-CL and FGW-RS
Unlike AutoNovel [27], which separates pretraining, supervised learning, and category discovery from each other, ProtoFGW-NCD performs representation learning, supervised learning and category discovery within single training process. Figure 3 illustrates the architecture and pipelines. At the
beginning of training, we randomly initialize a set of prototype graphs {o/ % (AA (B) (B)
k=1 Labeled old-class samples and unlabeled new-class samples from the training set mixed and randomly sampled into mini-batches. For each graph sample G, (A,, X,, E,), A, IR N.M. the adjacency matrix, X; E N.N. is the node feature matrix, and E, E E.d, is the edge feature matrix. Data Augmentation: We randomly remove p% of the nodes (and their edges) to get the subgraph G; = (A,, X,, E.) induced by the rest nodes. Encoding: Both G; and G; are passed through a learnable feature encoder to refine node and edge features, followed by a GNN+ encoder So [46]. The outputs at the final GNN layer are denoted as (A,, Z,) and (A, 2.), where Z. and 2, are the learned node representations. FGW Codes: We compute the FGW distances between these
7

---

Uniabeledgraat pipeiiee
Leamable Components
FGW Forward
FOW-OT
Graph Augmentattinn
Prototope Graph
V.
Proji
Detached
flow
Vi
LUGS
parselo
R
Mixed labeled unlabeled grophain
Prok
Leed
Ga
gops
v R
head
FSWLOT
Ece
RK
Prok
CSSL
&
Frue del
Figure 3: Illustration of ProtoFGW-NCD. Unlike previous graph SSL methods that directly compare Euclidean representations, ProtoFGW-CL. maps graphs to codes by aligning them with learnable prototype graphs using the Fused LSSL, these codes are encouraged to be consistent across views, such that the code from one view can be predicted using the other. FG W-RS: The codes of unlabeled graphs are fed into RS to generate pseudo-label matrix S, and also into the new-class head to obtain predictions. The pairwise similarities between these predictions guided by S with LBCg. Supervised Learning: The codes of m labeled graphs and their augmentations are fed into the old-class head to compute LCE.
(FGW) distance. Under the supervision of
outputs and the prototype graphs, resulting distance vectors v,, V; RRK Let m and n denote the number of labeled and unlabeled samples in batch, respectively, The overall training loss is composed of three terms
C LCE + LBC + LSSL
(2)
LCE
log [ho (v.)), + log [ho
(3)
2m
1
Sig log An (v:) hn (v;) + (1 -si)) log (1 hn (vi) hn (v;))
LBCE
(4)
112
1=1
j=1
m4t
LSSL = 2(m + n)
[SM(Z))) log ([SM(Z//T)()) [SM(),)) log ([SM(Z,/T)l)) (5)
k=1
where SM(.) is the softmax operator, g(-) is the projector for SSL, 2; =g(V.,, = 9(v.). Lce provides supervised signals from old-class samples, LBCE guides the new-class head hn, and LSSL encourages the cross-view consistency of FGW codes. Here, Sij E {0, 1} is the binary pscudo-label generated by ranking statistics (RS) based on structure-aware codes V, and Vj. and 8.J = RS considers i and to belong to the same class. FGW is typically solved using iterative algorithms. If backpropagation naively handled by PyTorch, would record many intermediate steps, leading to an excessively large and computationally intractable computational graph. To address this, design a parallel, differentiable FGW module, BAPG layer. This layer supports parallel differentiable FGW distances between by torch_spaant spwrse..a...... Spparse.Sparse In contrast, previous differentiable FGW module [63] only supports CPU backend and relies on slow nested loops for pairwise FGW solving.
[18] and be dense torch Tensor on GPU.
6 Experiments
6.1 Experimental Setup
We adopt the latest improved versions two classic GNN architectures, i.e., GCN+ and GIN+ [46], the backbones for all GLNCD methods. These models achieve approach state-of-the-art

---

Table 3: GLNCD results with GIN" encoder. The 1st and 2nd results are highlighted.
ENZYMES
MalNe: Tiy
REDDITIEK
CHARII
Arg.
Old ACC
New ACC
ACC
New ACC
Old ACC
New ACC
Old ACC
New ACC
Old ACC
New ACC
All
Kotheins
40.76.4118
AunaNovel
73.0=1.39
41.90:162
907722266
6899366.29
67.5940777
39.2140.92
61.853395
41.0741.90
3.00
2:75
2,875
NCT.
70.00+2.44
45.81+5.82
92.55+1.14
79.764744
70.11+0.75
36.57+1.59
67.54+1.24
38.2142.01
2.25
3.00
2.625
DuaiRS
76.35+0.75
39.52+1.12
92.85+1005
69.094.577
660540.58
39.68+1.77
65.7841.39
40.25+0.66
2.25
3.25
2,750
Ours
74000568
37.9563.16
93.3088.76
74.5187.05
67.3910.48
39,9432.42
56,4411.43
44.0411.58
2.50
2.00
22250
Table 4: GLNCD results with GCN* encoder. The 1st and 2nd results are highlighted.
ENZYMES
MaiNes-Tiny Tiny
REDDITIZK
CIPAR1O
Arg. Rank
Now ACC
ACC
Now ACC
Old
Now ACC
010 ACC
New ACC
ART
New ACC
All
39.6721.83
88.66229
66.6019.26
56.7242.76
42.5413.28
37,0542.11
42.2750.12
00.7211.02
5.00
3.75
4.35
AutaNovel
71.3322.74
41.52+1.86
80. 30366.79
624365.40
68.110035
39.08e1334
61.1063.12
41.26e1.31
3.00
2,500
NCL
67.6711499
39.113377
85.5042.35
622221.68
09.3541.11
37.0121.00
70.6340.46
39.6240:82
2.25
2,875
DualRS
64.6743.11
30.33+5.07
68.754745
49.53+3.74
6647H087
40,76+2.77
70.90+0.6
39.1740.86
3.50
3.75
3625
Ours
72.172567
41.013000
109536.16
63.351199
69.313.74
40.8122.66
71.2500611
38,9230.49
1.25
200
1835
performance on graph-level supervised tasks [46]. In the Fused Gromov- Wasserstein (FGW) distance Eq. (I), use the Euclidean distance node feature comparison metric Da_, and the adjacency matrix A to represent pairwise structural relationship C. The attributed graphs used in computing FGW distances are constructed by the node hidden features Z of the final GNN layer and the input graph adjacency matrix A. Inspired by [63], we set the trade-off parameter a as learnable. For data graphs, the marginal probability distributions are set uniform, while for prototype graphs the marginals are made learnable. ProtoFGW-CL. aims to incorporate structural information into the contrastive loss. So for graph data augmentation, we follow GraphCL and simply apply random node dropping: a fraction 9% of nodes are randomly removed, along with all edges connected to them.
6.2
Main Results
The GLNCD datasets constructed in Section 3.1 each include training set, validation set, and test set, as detailed in Table 7. We train the model on all labeled old-class samples and unlabeled new-class samples from the training set. During evaluation, we report two performance metrics: the clustering accuracy on unlabeled (new-class) training samples, denoted as New ACC and the classification accuracy on old-class test samples, denoted as Old ACC. We report the GLNCD results using GIN encoder in Tables 3 while the results for the GCN encoder are provided in Table 4. As shown in these tables, ProtoFGW-NCD, which incorporates more graph structural information, demonstrates decent NCD performance and achieves the highest average ranking on all datasets. This confirms the effectiveness of exploiting more graph structure in GLNCD tasks.
6.3
Ablation Study
We conduct ablation studies on the components of ProtoFGW-NCD by reporting both Old ACC and New ACC to evaluate their effectiveness.
Table 5: Ablation with GCN" on ENZYMES
Method
Old ACC
New ACC
ProtoFGW-NCD consists of four key components: ProtoFGW-CL, PGW-RS, supervised learning, and learnable prototype graphs. Removing the first three components can be achieved by excluding LSSL. LBCE, and LeE from the training loss. To assess the importance of adaptively learned proto- type graphs, we disable gradient updates for them.
wo FGW-RS
72.00+5.1 14
33.33+0.00
Proto
70.5043.69
42.10:4.52
wo Supervised learning
34.00+2.74
41,05+3.36
fixed proto. graphs
62.33+4.32
38.19+2.12
ProtoFGw-NCD
72.1745.67
44.8413.07
The results in Table 5 demonstrate that each component contributes significantly, and removing any leads to noticeable degradation. Among the components, FGW-RS has a minor impact on Old ACC but plays decisive role in New ACC, as its removal leads to a drop to 33.33% equivalent to random guessing among the three unlabeled categories. In contrast, ProtoFGW-CL significantly affects Old ACC while having minimal influence on New ACC. This may be because training the encoder and new head with pseudo-labels from FGW-RS itself serves as form of self-supervised learning (SSL) beneficial for novel category discovery. Without supervised signals, although Old ACC degrades to the level of random guessing, New ACC still achieves notable performance, indicating that ProtoFGW-CI CL effectively guides the model to learn meaningful SSL representations for NCD.

---

140
120
Method
Total time per epoch
Ours
100
POT
batch_st0 Size
64
60
128
256
512
20
200
400
600
800
1000
Number of nodes per graph
Figure 4:
The epoch time (s) of different BAPG solver implementations for FGW problems. The x-axis indicates different synthetic datasets, i.e., CSBM-20-10, CSBM-50-10, CSBM-1000-10.
Table 6:
The average batch time (s) of different BAPG implementations. 1 indicates speedup factor.
The highest speedup for each dataset (row) across all batch sizes is shown boldface.
Batch Size
64
128
256
312
Dataset
POT
Ours
POT
Ours
POT
Ours
POT
Ours
f
CSBM-20-10
8.90
0.04
250.7
17.96
0.02
719.6
34.19
0.03
1296.8
67.34
0.03
2070.2
CSBM-50-10
8.69
0.03
333.5
16.67
0.03
598.8
32.57
0.04
844.8
65.02
0.06
1020.1
1SBM-100-10
8.55
0.03
289.3
16.78
0.04
416.9
32.54
0.07
457.6
65.14
0.14
474.6
CSBM-200-10
8.38
0.06
142.6
16.79
150.2
32.66
0.28
117.9
65.43
CSBM-500-10
8.56
0.53
16.2
17.22
1.20
14.3
33.56
2.43
13.8
67.23
4.85
13.8
CSBM-1000-10
8.58
2.59
3.3
17.12
5.17
3.3
33.54
10.35
3.2
68.26
20.82
3.3
Learnable prototypes critical for both Old ACC and New ACC, resulting in performance changes of approximately 10 and points, respectively. This highlights the necessity of learnable prototypes and our efficient BAPG layer.
6.4 The Efficiency of Our BAPG Layer
In contrast to the BAPG operator in POT [20] which requires a brute-force loop, our proposed BAPG layer (Appendix B) can compute the Fused in (FGW) distance between B1 and B2 graphs in parallel. We compare their efficiency on Contextual Stochastic Block Model (CSBM) graphs [14, 48] with varying numbers of nodes. For graph dataset with N nodes, we assume there 10 prototype graphs, each with N' log N nodes (see Appendix C.2 for more details) and denote by CSBM-N-10 10 the synthesized dataset. The computation times for FGW distance under different batch sizes are presented in Table and Figure 4, where our method achieves a speedup up to 2070.2x compared to the POT implementation.
7 Conclusion
This paper introduces Graph-Level Novel Category Discovery (GLNCD) task, aiming to identify unseen graph categories in an open-world setting. We present four diverse benchmark datasets across different scenarios and systematically adapt classical NCD methods for images to the graph domain. However, experimental results show that these direct adaptations perform poorly on graph data due to insufficient graph structure explorations. To address this issue, we propose ProtoFGW-Ne consists of structure-awart SSL and pseudo-labeling, via a differentiable Fused caamoov-ssserteeinn (FGW) module, BAPG layer. Experiments demonstrate that ProtoFGW-NCD matches or outperforms baseline methods. As direction for future research, would promising to develop methods that explore graph structures more efficiently than FGW module for GLNCD tasks on large-scale datasets.
that
10

---

Acknowledgments
The research is supported by the National Key R&D Program of China (2023YTB2703700) the National Natural Science Foundation China (62176269).
References
[1] Ali Behrouz and Farnoosh Hashemi. Graph Mamba: Towards Learning on Graphs with State Space Models. Proceedings of the 30th ACM SIGKDD Conference on Knowledge Diseovery and Data Mining, KDD '24, pages 119-130, New York, NY, USA, August 2024. Association for Computing Machinery.
[2] Tristan Bilot, Nour EI Madhoun, Khaldoun Al Agha, and Anis Zouaoui. A Survey Malware Detection with Graph Representation Learning. ACM Comput. Surv., 56(11):27:1 June 2024.
[3] Vincent D. Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. Fast unfolding of communities in large networks, Journal of Statistical Mechanics: Theory and Experiment, 2008(10):P1000S October 2008. C.2
[4] Kaidi Cao, Maria Brbic, and Jure Leskovec. Open-World Semi-Supervised Learning. In International Conference on Learning Representations, October 2021. 2.1
[5] Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. Unsupervised learning of visual features by contrasting cluster assignments. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS '20, pages 9912 9924, Red Hook, NY, USA, December 2020. Curran Associates Inc.
[6] Jialong Chen, Bowen Deng, Zhen WANG, Chuan Chen, and Zibin Zheng. Graph neural ricci flow: Evolving feature from curvature perspective. In The Thirteenth International Conference on Learning Representations, 2025.
[7] Ting Chen, Simon Kornblith. Mohammad Norouzi, and Geoffrey Hinton. Simple Framework for Contrastive Learning of Visual Representations. In Proceedings of the 37th International Conference on Machine Learning, pages 15597-6077 PMLR, November 2020.
[8] Xinlei Chen, Haoqi Fan, Ross Girshick, and Kaiming He. Improved Baselines with Momentum Contrastive Learning, March 2020. 3.2
[9] Xinlei Chen and Kaiming He. Exploring Simple Siamese Representation Learning. In 202/ JEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 15745- 15753, Nashville, TN, USA, June 2021. IEEE.
[10] Gabriele Corso, Hannes Stark, Stefanie Jegelka, Tommi Jaakkola, and Regina Barzilay. Graph neural networks. Nature Reviews Methods Primers, 4(1):17, March 2024.
(11) Bowen Deng, Lele Fu, Jialong Chen, Sheng Huang, Tianchi Liao, Zhang Tao, and Chuan Chen. Towards understanding parametric generalized category discovery on graphs. In Forty-second International Conference Machine Learning, 2025.
[12] Bowen Deng, Tong Wang, Lele Fu, Sheng Huang, Chuan Chen, and Tao Zhang. Thesaurus: contrastive graph clustering by swapping fused coomov-wasserstei couplings. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 16199-16207, 2025.
[13] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. ImageNet: A large- scale hierarchical image database. In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pages 248-255, June 2009. 3.2
[14] Yash Deshpande, Subhabrata Sen, Andrea Montanari, and Elchanan Mossel. Contextual Stochastic Block Models. In Advances Neural Information Processing Systems, volume 31. Curran Associates, Inc.. 2018. 6.4, C.2

---

[15] Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking Graph Neural Networks. Journal of Machine Learning Research, 24(43):1-48, 2023. 1.1.
[16] Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bres- son. Graph Neural Networks with Learnable Structural and Positional Representations. In International Conference Learning Representations, October 2021. 3.1
[17] M. Fey and J.E. Lenssen. Fast graph representation learning with PyTorch Geometric. In International Conference on Learning Representations, 2019. C.I
[18] Matthias Fey. Rusty Iusytoospptorccssspp sparss:: PyTorch Extension Library of Optimized Autograd Sparse Matrix Operations. https://gichub.com/musyy htppttorchsspppptpeeeeee sparse. 5.3
[19] Enrico Fini, Enver Sangineto, Stéphane Lathuilière, Zhun Zhong, Moin Nabi, and Elisa Ricci.
A Unified Objective for Novel Class Discovery. In 202/ IEEE/CVF International Conference on Computer Vision (ICCV), pages 9264 9272,, October 2021. 2.1
[20] Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z. Alaya, Aurélie Boisbunon, Stanislas Chambon, Lactitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, Léo Gautheron, Nathalic T.H. Gayraud, Hicham Janati, Alain Rakotomamonjy, levgen Redko, Antoine Rolet, Antony Schutz, Vivien Seguy, Danica J. Sutherland, Romain Tavenard, Alexander Tong, and Titouan Vayer. POT: Python optimal transport. Journal of Machine Learning Research, 22(78):1 1--8, 8, 2021. 1, 6.4, C.1
[21] Scott Freitas, Yuxiao Dong, Joshua Neil, and Duen Horng Chau. Large-Scale Database for Graph Representation Learning. In Thirty-Fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 1), June 2021. 3.1.
[22] Lele Fu, Bowen Deng, Sheng Huang, Tianchi Liao, Chuanfu Zhang, and Chuan Chen. Learn from global rather than local: Consistent context-aware representation learning for multi-view graph clustering. In James Kwok, editor, Proceedings of the Thirty-Fourdh International Joint Conference Artificial Intelligence, IJCAI-25, pages 5145-5153, International Joint Conferences on Artificial Intelligence Organization, 8 2025. Main Track.
[23] Spyros Gidaris, Praveer Singh, and Nikos Komodakis. Unsupervised Representation Learning by Predicting Image Rotations. In International Conference on Learning Representations, February 2018 1.2.2
[24] Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre H. Richemond, Elena Buchatskaya. Carl Doersch, Bernardo Avila Pires, Zhaohan Daniel Guo, Mohammad Gheshlaghi Azar, Bilal Piot, Koray Kavukcuoglu, Rémi Munos, and Michal Valko. Bootstrap your own latent new approach self-supervised learning. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS '20, pages 21271-21288 Red Hook, NY, USA, December 2020. Curran Associates Inc.
[25] Peiyan Gu, Chuyu Zhang, Ruijie Xu, and Xuming He. Class-relation Knowledge Distillation for Novel Class Discovery. In 2023 IEEE/CVF International Conference Computer Vision (ICCV), pages 16428-16437. IEEE Computer Society, October 2023. 2.1
[26] Xiaojun Guo, Yifei Wang, Zeming Wei, and Yisen Wang. Architecture matters: Uncovering implicit mechanisms in graph contrastive learning. In A. Oh, T. Neumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 28585-28610. Curran Associates, Inc., 2023. 4.2
[27] Kai Han, Sylvestre-Alviss Rebuffi, Sébastien Ehrhardt, Andrea Vedaldi, and Andrew Zisserman. AutoNovel: Automatically Discovering and Learning Novel Visual Categories. IEEE Transac- tions on Pattern Analysis and Machine Intelligence, 44(10)x67676671, October 2022. 1, 2.1, 3.2, 1, 2, 2, 5.2, 5.3, A, A, C.I
[28] Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive Multi-View Representation Learning on Graphs. In Proceedings of the 37th International Conference on Machine Learning, pages 4116-4126. PMLR, November 2020. 5.1
12

---

[29] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum Contrast for Unsupervised Visual Representation Learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9729-9738, 2020. 3.2
[30] Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. In Proceedings of the IEEE Conference on Computer Vision and Patlern Recognition, pages 770-778, 2016. 3.1
[31] Marcel Hoffmann, Lukas Galke, and Ansgar Scherp. Open- Sonn-Wordd Lifelong Graph Learning. In 2023 International Joint Conference on Neural Networks (IJCNN), pages 1-9, June 2023. 2.2
[32] Yue Hou, Xueyuan Chen, He Zhu, Ruomei Liu, Bowen Shi, Jiaheng Liu, Junran Wu, and Ke Xu. NC2D: Novel Class Discovery for Node Classification. In Proceedings of the 33rd ACM International Conference on Information and Knowledge Management, CIKM '24, pages 849-859, New York, NY, USA, October 2024. Association for Computing Machinery. 2.2
[33] Sergey loffe and Christian Szegedy. Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift. In Proceedings of the 32nd International Conference on Machine Learning, pages 448-456. PMLR, June 2015, 3.1
[34] Yucheng Jin, Yun Xiong, Juncheng Fang, Xixi Wu, Dongxiao He, Xing Jía, Bingchen Zhao, and Philip S. Yu. Beyond the Known: Novel Class Discovery for Open- World Graph Learning. In Makoto Onizuka, Jae-Gil Lee, Yongxin Tong, Chuan Xiao, Yoshiharu Ishikawa, Sihem Amer- Yahia, H. V. Jagadish, and Kejing Lu, editors, Database Systems for Advanced Applications, pages 117-133, Singapore, 2024. Springer Nature. 1.2
[35] Wei Ju, Yifan Wang, Yifang Qin, Zhengyang Mao, Zhiping Xiao, Junyu Luo, Junwei Yang, Yiyang Gu, Dongjie Wang, Qingqing Long, Siyu Yi, Xiao Luo, and Ming Zhang. Towards Graph Contrastive Learning: A Survey and Beyond, May 2024.
[36] Prannay Khosla, Piotr Teterwak, Chen Wang, Aaron Sarna, Yonglong Tian, Phillip Isola, Aaron Maschinot, Ce Liu, and Dilip Krishnan. Supervised contrastive learning. Advances in Neural Information Processing Systems, volume 33. pages 18661-18673, 2020. 3.2, 4.2
[37] Thomas N. Kipf and Max Welling. Semi- supervupe classification with graph convolutional networks. In International Conference on Learning Representations, 2017. 3.1
[38] A. Krizhevsky. Learning Multiple Layers of Features from Tiny Images. 2009. 3.1
[39] Jiajin Li, Jianheng Tang, Lemin Kong, Huikang Liu, Jia Li, Anthony Man-Cha So. and Jose Blanchet. A Convergent Single-Loop Algorithm for Relaxation of Maanov-Wasserstinn in Graph Data. In The Eleventh International Conference Learning Representations, September 2022. 1, 5.1, B. 1, C.1
[40] Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. In Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 4465 4478. Curran Associates, Inc., 2020. 3.1
[41] Yixin Liu, Ming Jin, Shirui Pan, Chuan Zhou, Yu Zheng, Feng Xia, and Philip Yu. Graph Self-Supervised Learning: A Survey. IEEE Transactions on Knowledge and Data Engineering, pages 1-1, 2022.
[42] Yue Liu, Ke Liang, Jun Xia, Sihang Zhou, Xihong Yang. Xinwang Liu, and Stan Z. Li. Dink- Net: Neural clustering on large graphs. Proceedings of the 40th International Conference on Machine Learning, volume 202 of ICML'23 pages 21794-21812. JMLR.org. July 2023,
[43] Yue Liu, Jun Xia, Sihang Zhou, Xihong Yang, Ke Liang, Chenchen Fan, Yan Zhuang, Stan Z. Li, Xinwang Liu, and Kunlun He. A Survey of Deep Graph Clustering: Taxonomy, Challenge, Application, and Open Resource, September 2023.
[44] Ilya Loshchilov and Frank Hutter. SGDR: Stochastic Gradient Descent with Warm Restarts. In International Conference Learning Representations, November 2016. C.I
13

---

[45] Ily Loshchilov and Frank Hutter. Decoupled Weight Decay Regularization. In International Conference on Learning Representations, September 2018. C.I
[46] Yuankai Luo, Lei Shi, and Xiao-Ming Wu. Unlocking the Potential of Classic GNNs for Graph-level Tasks: Simple Architectures Meet Excellence, February 2025, 3.1, 5.3, 6.1
[47] Zhenfei Luo, Yixiang Dong, Qinghua Zheng. Huan Liu, and Minnan Luo. Dual-channe graph contrastive learning for self-supervised graph-level representation learning. Pattern Recognition, 1 139:109448, 2023. 5.1
[48] Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is Homophily Necessity for Graph Neural Networks? In International Conference on Learning Representations, March 2022. 6.4, C.2
[49] B. W. Matthews. Comparison of the predicted and observed secondary structure of T4 phage lysozyme. Biochimica el Biophysica Acta (BBA) Protein Structure, 405(2):442-451, October 1975. A
[50] C. Morris, N.M. Kriege, F. Bause, K. Kersting, P. Mutzel, and M. Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. In Proceedings of the International Conference on Machine Learning Workshop on Graph Representation Learning and Beyond, 2020. 3.1
[51] M. E. J. Newman. Finding and evaluating community structure in networks. Physical Review E, 69(2):026113, 2004. C.2
[52] Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary De Vito,, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in PyTorch. October 2017. C.1
[53] Gabriel Peyré, Marco Cuturi, and Justin Solomon. Gromov- Wasserstenn Averaging of Kernl and Distance Matrices. In Proceedings of The 33rd International Conference on Machine Learning, pages 2664-2672. PMLR, June 2016. B.1
[54] Joshua David Robinson, Ching Yao Chuang, Suvrit Sra, and Stefanie Jegelka. Contrastive learning with hard negative samples. In International Conference on Learning Representations, 2021. 3.2
[55] Ida Schomburg, Antje Chang, Christian Ebeling, Marion Gremse, Christian Heldt, Gregor Huhn, and Dietmar Schomburg. BRENDA, the enzyme database: Updates and major new developments. Nucleic Acids Research, ((ssupl_1):D431111
January 2004. 3.1.
[56] Fan- Yun Sun, Jordan Hoffman, Vikas Verma, and Jian Tang. InfoGraph: Unsupervised and Semi-supervised Graph-Level Representation Learning via Mutual Information Maximization. In International Conference on Learning Representutions, September 2019.
[57] Susheel Suresh, Pan Li, Cong Hao, and Jennifer Neville. Adversarial Graph Augmentation to Improve Graph Contrastive Learning. In Advances in Neural Information Processing Systems, November 2021. 5.1
[58] Shiyin Tan, Dongyuan Li, Renhe Jiang, Ying Zhang, and Manabu Okumura. Community- Invariant Graph Contrastive Learning. In Proceedings of the 41st International Conference Machine Learning, pages 47579-47606. PMLR, July 2024. 5.1
[59] Vayer Titouan, Nicolas Courty, Romain Tavenard, and Rémi Flamary. Optimal transport for structured data with application on graphs. In International Conference on Machine Learning. pages 6275-6284. PMLR, 2019. 1, 5, C.1
[60] Colin Troisemaine, Vincent Lemaire, Stéphane Gosselin, Alexandre Coiffers-Massone Joachim Flocon-Cholet, and Sandrine Vaton. Novel Class Discovery: An Introduction and Key Concepts, February 2023. 1
[61] Sagar Vaze, Kai Han, Andrea Vedaldi, and Andrew Zisserman. Generalized category discovery. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pages 7492-7501, 2022. 2.1
14

---

[62] Petar Veličković, William Fedus, William L. Hamilton, Pietro Liö, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. In International Conference on Learning Representations, 2019. 5.1
[63] Cédric Vincent-Cuar Rémi Flamary, Marco Corneli, Titouan Vayer, and Nicolas Courty. Template based Graph Neural Network with Optimal Transport Distances. In Advances in Neural Information Processing Systems, October 2022. 5.3, 6.1
[64] Jing Wang, Songhe Feng, Gengyu Lyu, and Jiazheng Yuan. Surer: Structure-adaptive unified graph neural network for multi-view clustering. In Proceedings of the AAAI conference artificial intelligence, volume 38, pages 15520-15527, 2024.
[65] Yejiang Wang, Yuhai Zhao, Daniel Zhengkui Wang, and Ling Li. GALOPA: Graph transport learning with optimal plan alignment. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. 5
[66] Yejiang Wang, Yuhai Zhao, Zhengkui Wang, Ling Li, Jiapu Wang, Fangting Li, Miaomiao Huang, Shirui Pan, and Xingwei Wang. Equivalence is all: unified view for self-supervised graph learning. In Forty-second International Conference on Machine Learning, 2025. 1
[67] Man Wu, Shirui Pan, and Xingquan Zhu. OpenWGL: Open-world graph learning for unseen class node classification, Knowledge and Information Systems, 63(9):2405-244) September 2021. 2.2
[68] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A Comprehensive Survey Graph Neural Networks. IEEE Transactions on Neural Networks
and Learning Systems, 32(1):4-24, January 2021. 1
[69] Jun Xia, Lirong Wu, Jintao Chen, Bozhen Hu, and Stan Z. Li. SimGRACE: A Simple Framework for Graph Contrastive Learning without Data Augmentation. In Proceedings of the ACM Web Conference 2022, WWW '22, pages 1070-1079, New York, NY, USA, April 2022. Association for Computing Machinery. 5.1
[70] Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. 1, 3.1
[71] Pinar Yanardag and S. V.N. Vishwanathan. Deep Graph Kernels. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '15 pages 1365-1374, New York, NY, USA, August 2015. Association for Computing Machinery. 1,1.1
[72] Liang Yang, Yukun Cai, Hui Ning, Jiaming Zhuo, Di Jin, Ziyi Ma, Yuanfang Guo, Chuan Wang. and Zhen Wang. Universal graph self-contrastive learning. In ISCAI, pages 3534-3542, 2025. I
[73] Liang Yang. Zhenna L., Jiaming Zhuo Jing Liu, Ziyi Ma, Chuan Wang, Zhen Wang, and Xiaochun Cao. Graph contrastive learning with joint spectral augmentation of attribute and topology. In AAAI, pages 21983-21991, 2025.
[74] Zhenyu Yang, Ge Zhang, Jia Wu, Jian Yang, Quan Z. Sheng, Shan Xue, Chuan Zhou, Charu Aggarwal, Hao Peng, Wenbin Hu, Edwin Hancock, and Pietro Liò. State of the Art and Potentialities of Graph-level Learning. ACM Computing Surveys, 57(2):1 February 2025.
[75] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS '20, pages 5812 5823, Red Hook, NY, USA, December 2020. Curran Associates Inc 3.2, 5.1
[76] Jure Zbontar, Li Jing, Ishan Misra, Yann LeCun, and Stéphane Deny. Barlow twins: Self- supervised learning via redundancy reduction. In International Conference on Machine Learn- ing, pages 12310-12320. PMLR, 2021.
[77] Qin Zhang, Zelin Shi, Xiaolin Zhang, Xiaojun Chen, Philippe Fournier- Fournier-Viger, and Shirui Pan. G2Pxy: Generative open-set set node classification on graphs with proxy unknowns. In Proceedings of the Seeony International Joint Conference on Artificial Intelligence, UJCAI '23, pages
4576 4583, August 2023. 2.2
15

---

[78] Bingehen Zhao and Kai Han. Novel visual category discovery with dual ranking statistics and mutual knowledge distillation. In Advances Neural Information Processing Systems, volume 34, pages 11982-229944 2021. 2, 3.2, C.1
[79] Yuhai Zhao, Yejiang Wang. Zhengkui Wang, Wen Shan, Miaomiao Huang, and Xingwei Wang. Graph contrastive learning with progressive augmentations. In Proceedings of the 31st ACM SIGKDD Conference Knowledge Discovery and Data Mining V.I, KDD '25, pages 4079-2088, New York, NY, USA. 2025. Association for Computing Machinery. 4.2
[80] Zhun Zhong, Enrico Fini, Subhankar Roy, Zhiming Luo, Elisa Ricci, and Nicu Sebe. Neigh- borhood Contrastive Learning for Novel Class Discovery. In 2021 IEEE/CVE Conference on Computer Vision and Pattern Recognition (CVPR), pages 10862-10870, IEEE Computer Society, June 2021. 1, 2,1, 3.2, C.1
[81] Jiaming Zhuo, Can Cui, Kun Fu, Bingxin Niu, Dongxiao He, Chuan Wang. Yuanfang Guo, Zhen Wang. Xiaochun Cao, and Liang Yang. Graph contrastive learning reimagined: Exploring universality. WWW, pages 641-651, 2024.
[82] Jiaming Zhuo, Yintong Lu, Hui Ning, Kun Fu, Bingxin Niu, Dongxiao He, Chuan Wang, Yuanfang Guo, Zhen Wang, Xiaochun Cao, and Liang Yang. Unified graph augmentations for generalized contrastive learning on graphs. In Neur!PS, 2024.
16

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our main contributions and scope have been accurately summarized in the last paragraph of introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations of work in Section D.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
17

---

Justification:
We do not introduce theoretical results in the paper.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide all the hyper-parameter values or search spaces in Section C.I. We also include the description of the data used in Sections 3.1 and C.I.
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
18

---

Answer: [Yes]
Justification: We plan to release the code, datasets, and pre- pre-trained models with sufficient instructions to faithfully reproduce our results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nips cc/
public/guides /wwo/ooeuiiiiiooooooooo
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/nips. httppsccccpbllccceeecceeeep gww.es/ CooeeSumiiss / ssi (ssonniiycy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We provide these details in Section C.I.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The results in Section include both the means and standard deviations of more than repeating runs.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emrr bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
19

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide the computer resources information in Section C.I.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question:
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: /ttp///eerrpp.eeeeee/eee ccc wtt.ccccppbbbaee httppppubblbhiiieeeeeeeeeeeeeele csQuidel de ines?
Answer: [Yes]
Justification: Our work conform with the Code of Ethics
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes],
Justification:
We discuss the broader impacts of our work in Sections and D.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
20

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: Our work poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All codes and datasets used in this work are publicly available for research purposes.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
21

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [Yes]
Justification:
Our code and pre-processed GLNCD datasets will be provided.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/cooe/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
We do not involve crowsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
We do not involve research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
22

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: LLM is used only for writing, editing, formatting purposes in this paper.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy (ttp:///eerissccccccceeeeeeesss) for what should or should not be described.
23

---

A Measure the Quality of Pairwise Pseudo Labels for Unlabeled Samples
The pseudo labels from ranking statisties (RS) Methods such AutoNovel [27] generate
pairwise pseudo-labels using ranking statistics (RS). Instead of directly computing the similarity (e.g., cosine similarity) between d-dimensional readout vectors V; Readout (G)) and V; = Readout fo (G))) of samples and j, RS ranks the d elements of each vector based on the element magniuudes. the element ranking orders of two readout vectors are consistent, the corresponding samples are likely to belong to the same novel category, and we assign pseudo-label sij 1. Otherwise, we set 8ij = 0. The new-class head h is then trained using binary cross-entropy loss and the pairwise binary labels:
M
M
LBCE
1
ΣΣΣ
Bij log hn (v:) hn (v,) + (1 8ij) log (1 - hn (vi) hn (va))] (6)
M
where In (v:) is the softmaxed prediction on sample and M is the number of unlabeled samples involved.
Han al. [27] found the loss Eq. be the most critical component for NCD. Therefore, we aim to quantify its quality to enable deeper analysis. Given M unlabeled new-class samples, RS generates a {0, M X Let T denote the ground-trute -rrth pairwise label matrix, where Ti = 1 if samples and belong to the same novel class, and Tij = 0 otherwise. Evaluating the quality of RS can thus be framed as a binary classification problem.
pseudo-label matrix
Evaluate pseudo labels with Matthews Correlation Coeflicient According to Proposition 3, there are much more zeros than ones T. So the RS pseudo label quality evaluation is an imbalanced binary classification task, making accuracy an unsuitable evaluation metric. Instead, we adopt the Matthews Correlation Coefficient (MCC) [49], a widely used measure for evaluating classification performance under class imbalance. Let the confusion matrix for the binary classification be
TP FN FP FN)
)
Then MCC is defined as
TP - FP. FN MCC V(TP+ /T)P+ (P)(P + FN)(NN + FP)(TN + FN)
which takes into account all four components the confusion matrix, i.., true positives (TP), true negatives (TN), false positives (FP), and false negatives (FN), and therefore provides a comprehensive measure of the agreement between generated pseudo-labes and the ground truth pairwise labels.
Proposition Consider a class-balanced dataset with C categories, each containing M samples. Define the pairwise comparison matrix T E (0,1)MMxCC such that Tiş = 1 if samples and belong to the same class, and Tij- = otherwise. Then, the fraction of positive entries (i.e., entries
equal to 1) in T is given by
CM2
1
(MM)²
C
Evaluate pseudo labels with the portion of samples with at least one same-class pair stated in Proposition 3, the majority of sample pairs are negative, i.e., with a label 0. Each sample encounters far fewer true positive pairs than negative ones, making true positive pseudo-labels more valuable. Therefore, we use the ratio of samples that have encountered at least one true positive pair to quantify the quality of the pairwise pseudo-labels (generated by RS).
B Parallel Differentiable BAPG Layer for Efficient FGW Distance
B.1 Forward
For two attributed graphs G = (C1, X1) and G2 = (C2, X2), the Fused Gromov Wasserstein dis- tance (Definition 2) between them amounts to, given M IR Kna defined by My Do, (X1,,, X2.).
24

---

the following quadratic optimization problem
FGW min aT M)F + a Σ L(C (25a)Ti,, Ta,
R.j.K.)
s.L. T E [0, 1j
T1 11=
According to Proposition in [53], it holds that
Σ L(C T. T Tu. A.
Cf P +N,,q' (C22) -C2 .T)
where 2 is the elementwise square and IN, R is the all-one vector. Then we have
FGW min (1-
M) (T,
a {
C O pi + +lvg 2C
T 2C,TC!| (Tp
T
s.t. T 1 =1 T'1=q.
We take L(Cii, C2j,) (CI., C2 and employ the Bregman Alternating Projected Gradient (BAPG) method proposed in [39] to solve the optimal transport plan T and the corresponding FGW distance. The pseudo code of BAPG can be found in Algorithm
Algorithm 1: POT BAPG Solver [39] for Fused
Distance (Forward)
Input: Node feature cost matrix M E RR, Sparse structure matrices C₁ E Ru,xx,
C2 E XRe, Distributions p R E IR Trade-off a E (0, 1), entropy 0.
Max iterations T, Tolerance tol
Output: Optimal transport matrix
X and FGW distance
Initialize T pq
2 Elementwise function: f(C,) + C ((C) + Cr,((2) (((2) + C2:
3 Precompute constants: R + f(C))p1, + +1.
4 Define gradient operator V + 20(R (MCCT)T +(1-a)M,
for < to T' do
6 Prex + T;
Row projection:
8
Update: T - @ (- VT/c)
Normalize rows: Ta,: t Σ, Tu.s To.
Pu
Column projection: Update: T - T exp (- VT/E)
Normalize columns: T.b En 9u
Tai T.b
if mod 10 ( then
14
Compute error: err <- T T prev FF; if err < tol then
16
break:
end
18
end
19 end
return T and FGW;
Our proposed method, ProtoFGW-NCD, requires computing pairwise FGW distances between b sparse adjacency matrices of varying sizes (represented as torch_ sparse. SparseTensor) and ba dense adjacency matrices of prototype graphs with uniform size. Ideally, we aim to solve these FGW distances in parallel. However, both the official implementation and the POT implementation only support solving the FGW distance between one pair of dense matrices at one time. When i and b2 are large, invoking these implementations b, by times within nested loops results in prohibitively long computational time.
torch_sparse
thtpps//gihuu..co///so/o http://hhhhh..ooomuuuuu///////on Wwwserstein--or-eeeeee Graphh http::/wwwhooo...ioooeeooooooooo
fused grwmovg wasserstein
25

---

multiplication
Elementwise multiplication
Elementwise division
Zero submatrik
T & KexXn
M(Cs) 3
T
R
sealing T T
M(C))) R
by 20 matrices
20 matrices
by
20 matrioes
1s1
h(Crs)
scattor
14y2
*
Mg2
scattor
7222
A(Cpp)
h(Cz))
191
Scaffer
11y2
*
Pg2
scatter
11c
Figure 5: The illustration of key operators in the forward of our BAPG layer, which parallels POT BAPG solver. The left is to parallel h (TCC))ssh((( (Line in Algorithm 1) and the right parallel [Tol.,
T.l. [Till,, (Line 12 in Algorithm 1), for i E [1 bn] and j [1 ba].
gb
Observing Algorithm 1, we find that the main challenge in parallelizing the fused Gromov- Wasserstein (FGW) computation across 61 groups lies in the irregular sizes of the b1 sparse matrices. To address this, we propose constructing a sparse giant graph C₁ Rexs (where Σh nss) by arranging the sparse matrices C11, Ci2...., Cio, as diagonal blocks:
C
0
0
C
C
E IRex
Cib
This allows for intra-batch parallelization even under irregular matrix dimensions. Meanwhile, the by dense matrices C21, C.2...., C2b, stacked into tensor C2 R enabling parallelization along the first dimension via broadcasting rules. This design enables the by pairs of FGW computations be efficiently implemented using existing operators from torch sparse and torch_scatter.
Since we need to solve for by by transport plans (Te R E [1 byl.j E [1 b2). we represent them using whole tensor T E Raxm Placing the batch size b2 of dense matrices along the first dimension facilitates efficient sparse-dense matrix multiplication (via spmm) over all b2 matrices. Our goal is to parallelize bi FGW with the operations among C₁ xx C2 Rlaxn, x and T X The key computational steps in Algorithm parallelize are
Line 4 (CC)))))) that can be parallelized using the spmm operator from torch torch_sparse
Line 12 [Tyl:bb TTala (Tyle that requires computing the normalization sums ETTTollob for each pair (Cis, C2j) using scatter_ss __m from borch_scatter" fol- lowed by grouped broadcasting across the first two dimensions of T Rb2xexx,
We illustrate the above two parallelization designs in Figure 5. The forward process of our parallel BAPG layer is concluded in Algorithm 2, in a pytorch style.
"https://ittuu..com/// cww//rstt//oocooocooooooo.o hwtpy//cchspppppateaaeet "https///gttuub.oo//// wwwp://wwwwooooooooooooo.aaaaate http:///ssssyyytytocc.hccs scatter
26

---

Algorithm 2: Our BAPG layer for Fused
Distance (Forward)
Input: (1) Node feature cost matrix M E ( (2) Diagonal block matrix
C1 E Roxx stacked by bı sparse structure matrices C11. C12...., Cib, where The tensor C2 E RRlxn, X stacked by b2 dense structure matrices C21: C22..... Cbby- (4) Marginal distributions of 61 sparse matrices p= [Pi P2 ... pb, IR where P; E 1R (5) Marginal distributions of b2 dense matrices q 12 X (6) g E by]" where g(a] is the graph index of node in the giant graph C₁- (7) Trade-off a E (0, 1), entropy c > O. Max iterations T, tolerance tol
= Σn= Tlat- (3)
Operator: : @: @ in pytorch, matrix/tensor multiplication. *: elementwise multiplication.
.view(...): pytorch tensor vvie(..)). [t, ind, :|: pytorch tensor slice. Output: Optimal transport plans T E Raaxaxn of and FGW distances between by b2 pairs
Initialize T (.viewsss 1) q. q.view (2, 1, n)):
2 Elementwise function: f(C1) - C ((,) + C1, - C + C2:
Precompute constants:
R + @(.i)@p.vieur(s 1)11 T In, view(s, 1) Q)@q.viewwweeee (,n,))f((C.)
Define gradient operator VT +- 2a 2M(C))@TTh(C) + (1-a)M,
5 for t - to T do
T prev f- T;
/* Row projection
T T exp V /e) // Update
8
S. = (P/(T.sum, 1)) // Row scaling factor
S...view (b2, s, 1) T Normalize rows
1* Column projection
31
T exp (TVr/) // Update
1* Sum the elements from the same sparse matrix along the 2nd dim group_stee sum scatter scatter_sumi Jum(T. (T. dim =) 1 Broadcast to each group and get columnm scaling factor
31
S. q.view((2, 1, //g//oou_suuup
13
T S. T Normalize columns
if mod 10 then
15
Compute error: err <- |T T prev ||;
16
if' err < tol then
17
break;
18
end
end
end
return T and corresponding FGW distances
B.2 Backward
With L(Cii,k C2j.) (Cir, 22 the gradients of 1-to-1 FGW w.r.t. the input elements
0FGW
= aT
ØM
OFGW
2aC, o (pp)) TC,TT
aC1
0FGW
2aCa o (bq
22TT C.T
0C2
0FGW
([C92
TINT IN, 1, T (C
- 2C,TCT .T. (T,
da
0FGW
0FGW al C Tq.
Öp
0q
27

---

The backward computations of b, FGW distances can be parallelized via similar techniques introduced in parallel FGW computation described in the forward process of our BAPG layer (Section B.I).
C
More Experiments
C.1 Implementation Details
The implementation is based on Pytorch2.5 [52] and PyG2.6 [17]. All experiments are conducted on Ubuntu 22.04 server equipped with an RTX 4090 GPU and Intel Xeon Gold 6240C CPU. For FGW [59, 391, we implement an extremely efficient version from scratch (Section B) instead of using Python Optimal Transport toolbox [20].
Many studies report test performance based on the epoch that achieves the best performance on the validation set. However, in the context of NCD, selecting the epoch based on clustering accuracy over unlabeled validation samples would require knowledge of the ground truth new-class labels, which violates the NCD assumption. Alternatively, using old-class accuracy the validation set may rein- force model bias toward known classes, potentially harm- ing performance on new classes. Therefore, we report results from the final training epoch. In addition to the three baseline methods designed in Section 3.2, we also implement a K-means baseline: after pre- training the GNN encoder with GraphCL, we apply K-means directly to the GNN representations of the unlabeled training samples and old-class test samples, and report the corresponding clustering accuracies. For all experiments, we use the Adam W optimizer [45] and cosine annealing scheduler [44] with warmup.
Table 7: The split information of four GLNCD datasets
Dataset
train
# test
# all
ENZYMES,
420
120
600
MalNet-Tine
3500
1000
5000
REDDITI2K
8350
2386
11929
CIFARIO
35000
10000
60000
Following common practice in visual NCD [80, 78, 27], we first determine the hyperparameters for AutoNovel on given dataset. These hyperparameters are then inherited by NCL and DualRS on the same dataset, and only the hyperparameters that differ from AutoNovel are subsequently tuned for these two methods. ProtoFGW-NCD has fundamentally different architecture from the above baselines, and its hyperparameters are therefore not influenced by AutoNovel. The hyperparameter values or search spaces of these mehods are presented in Table 8.
C.2 Benehmarking Our BAPG Layer Implementation
Section B introduces our BAPG layer for efficient, differentiable FGW distance computation, which leverages torch_sparse and torch_scattee to parallels pairwise FGW computations between b, sparse matrices and b2 dense matrices. Compared the BAPG implementation in POT 6, our improved version supports sparse matrices, parallelized iterative solving, and efficient automatic dif- ferentiation. These enhancements significantly promote the broader application of the FGW distance in graph-level machine learning. In this section, we compare our parallel BAPG implementation with POT on a series of synthetic attributed graph datasets.
Graph sizes considered are 20, 50, 100, 200, 500, and 1000 nodes. For each size, we generate 1000 Contextual Stochastic Block Model (CSBM) graphs 48]. Prototype graphs typically used to represent large-scale topological relationships; thus, each node in a prototype graph corresponds block or community of nodes. While no universally accepted formula exists for determining the optimal number of communities in a network, empirical studies suggest that the number of communities typically grows sub-linearly with the number of nodes N. often approximated as ONN/ log N). especially in scale-free or real-world networks where community sizes follow power-law distribution [51, 3]. Therefore, for graphs of size N, we use 10 prototype graphs of size N/2 log N to capture patterns in the dataset, and the dataset is denoted CSBM-N-10. In Figure 6, we display 10 prototype graphs used to generate 1000 graphs in CSBM-100- 10 dataset. Commonly used batch sizes in graph learning are 64, 128, 256, and 512. We evaluate the efficiency of different
"bapss//yythooorrgihbbbiooeee / oo.gromov.hmllooogoooommo fusee _oroddrroooovvvveeeee wasserstein
28

---

Table Hyperparameter values and search spaces GLNCD methods
Group
Hyperparameter
Value Search Space
Common Hyperparameters
Optimization
Learning rate
[0.001, 0.005, 0.01, 0.05, 0.1]
Dropout
[0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7,
Weight decay
[0.0, 5e-5, le-4, 5e-4, 1e-3, 5e-3, le-2]
Cosine warmup steps
[2,5, 10]
Batch size
[64, 128, 256, 512]
Max epochs
[20, 50, 100, 300]
Neural Network Arch.
GNN encoder layer
[2, 4, 6]
Hidden dimension
[32, 64, 128, 256]
has mus_rrel has_ ffn
[False, True]
[False, True] [batchborm, None]
Normalization
Graph SSL
Node droprate
[0. 0.1, 0.2, 0.3, 0.4, 0.5, 0.6] [0.1, 0.3, 0.7, 1.1]
Temp. for contrastive loss
GLNCD method Hyperparameters
All baselines
Encoder pooling readout
('mean', ''ddd, 'max']
AutoNovel
Topk in RS
[5, 10, 15] [10, 50, 80, 150. 300]
Rampup length
Rampup coefficient
[1.0, 5.0, 25., 50.]
NCL
Labeled NCL loss weight
[0.2, I]
Unlabeled NCL loss weight
[0.2, 1]
Queue length
[200, 2000]
DualRS
Memory bank length Epsilon
[256, 512, 1024]
ProtoFGW-NCD
[0.01, 0.05, 0.07, 0.11. 0.15, 0.19]
Prototype node feature std. # prototype graphs # prototype graph nodes
[0.5, 1.]
range(10, 130, 10)
20
BAPG implementations in comparing all 1000 graphs with the 10 prototype graphs under various batch sizes.
The average time for computing the FGW distance between batch of graphs and all 10 prototype graphs, under different batch sizes across various datasets, shown in Table 6. The total time required to traverse each entire dataset is presented in Figure 4. As summarized in Table 6, our parallel BAPG solver delivers dramatic runtime improvements over the POT implementation across all batch sizes and problem scales. While POT's runtime grows roughly linearly with batch size (e.g., from 2=8,9 at B=64 to =67.3 at B=512 on (SBM-20-10), our approach maintains a nearly constant per-batch cost (=x0.02-0.04 s), yielding speedups that increase from =2500 to x2070 B grows. Furthermore, the degree of acceleration decreases as the graph size N increases increases-exceeding 400x-2000x for mall-to-medium sizes (N (N<100 (00) B=512, yet still achieving 3x-14x for large-size graphs (N=500-1000), These findings demonstrate that our technique effectively amortizes overhead and exploits parallelism for batches of FGW problems, offering exceptional throughput for the tasks of small- and medium-size graphs while retaining nontrivial gains even in large-graph settings. This also supported by the epoch time comparison displayed in Figure 4.
D Limitations
As the first work to consider graph-level NCD, this paper aims to introduce the new task of GLNCD and examine whether existing visual NCD methods can be effectively udapted by simply replacing their components with graph-domain counterparts. To address this question, we adapt three classic NCD methods from computer vision to establish GLNCD baseline approaches (Section 3.2) and evaluate their performance four newly designed GLNCD datasets spanning different domains (Section 3.1).
29

---

1.
Pretorye22
Protetype
-02
0.0
Figure 6: The prototype graphs used to synthesize the 1000 graphs in CSBM-100-10 dataset.
Our experimental results and analysis (Section 4) clearly indicate negative answer, suggesting that current graph SSL methods and ranking statistics are insufficient in capturing structural information within graphs, thereby leading low GLNCD performance. Although we do not adapt the most recent visual NCD methods, the limitations we observe from direct transfer can be generalized to them. This because these recent visual NCD methods would still rely on existing graph SSL techniques for representation learning and employ pseudo-labeling strategies that neglect graph structure to train the new-class head. Additionally, despite the development of our parallel BAPG solver (Section B), which significantly improves computational efficiency solving FGW for graph 1carning-achieiingg achieving an impressive 2070x speedup on the CSBM-20- 10 dataset where graphs have 20 tho experimental results (Section C.2) show that the acceleration drops only about 3.3x larger graphs (CSBM-1000-10), Future work may focus on analyzing the causes of reduced speedup and improving the implementation, exploring alternatives to FGW that more efficiently exploit graph structure to enhance both graph SSL and pseudo-labeling strategies.
30


Reviews:
[{"review_id": "2IX90BftqM", "reviewer": "Reviewer_4CRM", "summary": "This paper introduces Graph-Level Novel Category Discovery (GLNCD), extending graph classification to open-world scenarios where models must discover novel graph categories without supervision. The authors propose ProtoFGW-NCD, addressing limitations of adapted visual NCD methods through two components: ProtoFGW-CL and FGW-RS. A parallel BAPG layer enables efficient FGW computation. Experiments on four diverse datasets show consistent improvements over adapted visual NCD baselines.", "questions": "1. How sensitive is performance to the number of prototype graphs K? \n\n2. How does the α parameter in the FGW distance affect performance across different graph types and domains?", "limitations": "See Weakness", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "**Strengths**:\n1. The transition from closed-world to open-world graph classification addresses a genuine need in applications. While node-level NCD has been explored in prior work [1], this appears to be the first systematic study of graph-level NCD, representing a meaningful contribution to the graph learning literature.\n\n\n2. The controlled experiments in Figures 1-2 effectively demonstrate that traditional ranking statistics fail on graph data even with improved representations. The insight that structural information loss, rather than representation quality, is the bottleneck provides clear motivation for the proposed FGW-based approach.\n\n\n3. The authors develop a differentiable BAPG layer that enables efficient batch computation of FGW distances. The learnable prototype mechanism elegantly solves the variable-sized graph comparison problem.\n\n**Weaknesses**:\n1. While FGW distance is reasonable for graph comparison, the paper lacks a systematic comparison with other graph distance measures (e.g., Graph Edit Distance) or alternative approaches to structure-aware SSL. The choice appears more empirically driven than theoretically necessary, and the complexity-benefit trade-off is not thoroughly analyzed.\n\n2. Given that FGW distance already provides a graph similarity measure, the insistence on using ranking statistics seems like conservative adherence to traditional NCD pipelines rather than optimal design. Why not directly use FGW distances for similarity judgment? The paper doesn't convincingly justify why ranking is still beneficial when operating on structure-aware FGW vectors.\n\n3. The simple node/edge dropping augmentation seems naive for graph data. Have the authors considered more sophisticated graph augmentations that preserve semantic structure? The choice of augmentation strategy could significantly impact the quality of self-supervised learning.\n\n[1] Jin, Y., Xiong, Y., Fang, J., Wu, X., He, D., Jia, X., ... & Yu, P. S. (2024, July). Beyond the Known: Novel Class Discovery for Open-World Graph Learning. In International Conference on Database Systems for Advanced Applications (pp. 117-133). Singapore: Springer Nature Singapore.\n\n[2] Hou, Y., Chen, X., Zhu, H., Liu, R., Shi, B., Liu, J., ... & Xu, K. (2024, October). NC^2D: Novel Class Discovery for Node Classification. In Proceedings of the 33rd ACM International Conference on Information and Knowledge Management (pp. 849-859).", "was_revised": true, "final_justification": "The author's response has effectively addressed my concerns regarding the technical details, and I think GLNCD represents a potentially valuable new task. Therefore, I maintain my original score. \n\nHowever, after reading Reviewer adDu's response, I acknowledge the valid concerns raised about performance. I also note that the authors did not provide any response to Reviewer adDu's comments, leaving these important performance-related questions unaddressed. In light of this, I have adjusted my confidence level to 3, reflecting my support for the work's novelty while also respecting the unresolved concerns raised by other reviewers.", "rebuttal": "We are truly grateful to the reviewer for the exceptionally thorough and insightful evaluation of our work. We sincerely appreciate the time and care you have taken to engage with our work so constructively. Your astute observations have been instrumental in refining key aspects of our methodology and presentation, as we detail in the following responses.\n\n## **Weakness 1**\n\n> While FGW distance is reasonable for graph comparison, the paper lacks a systematic comparison with other graph distance measures (e.g., Graph Edit Distance) or alternative approaches to structure-aware SSL. The choice appears more empirically driven than theoretically necessary, and the complexity-benefit trade-off is not thoroughly analyzed.\n\n**Why not other graph distance measures?**  \n\n- Compared to GED, graph kernels, and spectral distances, FGW's key advantage is its differentiability via implicit differentiation, enabling integration into modern end-to-end systems. The other methods including but not limited to GED, spectral distance, Weisfeiler-Lehman kernel, random walk kernel and spectral distances are non-differentiable, and it is hard to render these methods differentiable.\n- FGW couplings can provide node-level interpretability for graph comparison.  \n- We find that FGW permits batch-to-batch parallelization on GPUs. While 1-to-1 approximated GED can match FGW's complexity, it cannot achieve batch parallelism.\n\n**Why not structure-aware SSL?**  \n\n- Prior work ([20, 58]) shows structure-aware SSL methods don't consistently outperform GraphCL (used in our manuscript) across datasets.  \n- The method proposed in Section 5 specifically aims to validate the hypothesis presented at the end of Section 4: that *structural information deficiency causes G-AutoNovel's failure*. To strictly isolate the variable of \"introducing structural information,\" our comparative method should minimally modify the G-AutoNovel baseline. ProtoFGW-NCD achieves this by simply inserting a BAPG layer before the representation output to inject structural information. Alternative structure-aware SSL approaches typically require complex augmentations and auxiliary losses, leading to multiple architectural modifications that would compromise our controlled comparison.\n- From a purely performance perspective, replacing GraphCL with more sophisticated SSL methods appears promising, and we consider this an important direction for future work.\n\n**Complexity-benefit trade-off**  \n\nThe computational complexity for calculating FGW distance between graphs with $n$ and $m$ nodes is $O(n^2m + nm^2)$. In our implementation, we set the prototype graph size $m$=20 and $n$ depends on the dataset.\n\nThrough parallelization of FGW computation between batches of $b_1$ and $b_2$ graphs, we achieved up to 2000x acceleration since all $b_1b_2$ pairs are parallelized. However, this acceleration essentially trades space for time, the total computational load remains unchanged. Therefore, from a purely practical standpoint, ProtoFGW-NCD is not optimal. As noted in Appendix D, our primary objective is to explore the novel GLNCD task and identify directions for improving baselines, rather than proposing the ultimate model. For validating our hypothesis in Section 4 (that structural information deficiency causes G-AutoNovel's failure), ProtoFGW-NCD serves as an appropriate choice. We reserve the development of more advanced solutions for future work.\n\n## **Weakness 2**\n\n> Given that FGW distance already provides a graph similarity measure, the insistence on using ranking statistics seems like conservative adherence to traditional NCD pipelines rather than optimal design. Why not directly use FGW distances for similarity judgment? The paper doesn't convincingly justify why ranking is still beneficial when operating on structure-aware FGW vectors.\n\n**Why maintain traditional NCD pipelines?**\n\nAt the end of Section 4, we proposed that the traditional G-AutoNovel baseline fails on graph data due to the insufficient exploitation of graph structure:\n\n- Lack of structural information in representations limits pseudo-label utilization\n- Readout vectors + Ranking statistics (RS) lacks structural information, and limits pseudo-label quality\n\nSec. 5 is to design a controlled contrastive method to validate this hypothesis. To strictly isolate the variable of \"introducing structural information\" and observe its impact, we aimed to modify the G-AutoNovel baseline as minimally as possible while incorporating structural information. This ensures performance differences primarily stem from structural information injection rather than major architectural (including SSL loss) changes.\n\nTherefore, ProtoFGW-NCD in Section 5 was intentionally designed as a minimally modified version of G-AutoNovel. Its sole modification is inserting a BAPG layer before representation output, specifically to inject structural information (via FGW) into the final representations.\n\n**Why use ranking statistics (RS) ?**\n\n- Our hypothesis explicitly states that G-AutoNovel's failure stems not only from structural information deficiency in representations, but also from its RS mechanism (operating on simple readout vectors) failing to utilize structural information. To validate the second point, we needed to observe whether the RS mechanism would work more effectively when the input representations (signals to RS) contain structural information. Significant performance improvement would confirm the hypothesis.\n\n- Besides the first point, we know that direct similarity computation between vectors (e.g., $\\mathbb{v}_1$ and $\\mathbb{v}_2$ in Section 5.2) has been extensively shown to be less robust than RS in generating pseudo labels from vector pairs, as discussed in [21] (Discussion, p.4). Given that the structural information injected into representation vectors, RS is still very likely to outperform vector similarity measures.\n\n## **Weakness 3**\n\n> The simple node/edge dropping augmentation seems naive for graph data. Have the authors considered more sophisticated graph augmentations that preserve semantic structure? The choice of augmentation strategy could significantly impact the quality of self-supervised learning.\n\nWe have indeed investigated the potential benefits of sophisticated graph augmentations in graph-level SSL [20, 58]. According to reported results (e.g., Table 3 in [20]), despite more sophisticated augmentation designs, these methods failed to achieve superior performance across all datasets, suggesting that advanced augmentations do not always lead to the desired consistent gains.\n\nFurthermore, it's important to note that ProtoFGW-NCD was specifically designed as a minimally modified variant of G-AutoNovel to validate the hypothesis presented at the end of Section 4. Maintaining consistency in the augmentation strategy was therefore essential for controlled comparison.\n\nIn summary, keeping our augmentation approach consistent with G-AutoNovel's implementation:\n\n- Allows for fair comparison with G-AutoNovel and solid verification of the effect of structural information.\n\n- Is supported by existing literature showing limited benefits of more complex augmentations\n\n## **Question 1**\n\n> How sensitive is performance to the number of prototype graphs K?\n\nWe add additional experiments on ENZYMES to investigate the sensitivity to hyperparameter $K$, as shown in **Tables RT1** and **RT2**. The results demonstrate that: *within the proper range, the model's performance remains relatively stable across different K values*\n\n***Table R1: The performance sensitivity w.r.t. K on ENZYMES with GCN+ backbone. Results are averaged over 10 runs.***\n\n| **K** | 30 | 50 | 70 | 90 | 120 | 150 |\n|---|---|---|---|---|---|---|\n| **Old ACC** | 68.00 | 69.50 | 65.33 | 66.17 | 70.33 | 68.33 |\n| **New ACC** |  44.43 | 45.62 | 48.05 | 48.00 | 47.76 | 46.81 |\n| **Learned $\\alpha\\in [0,1]$** |  0.34 | 0.45 | 0.53 | 0.56 | 0.54 | 0.60 |\n\n***Table R2: The performance sensitivity w.r.t. K on ENZYMES with GIN+ backbone. Results are averaged over 10 runs.***\n\n| **K** |  30 | 50 | 70 | 90 | 120 | 150 |  |  |  |\n|---|---|---|---|---|---|---|---|---|---|\n| **Old ACC** | 73.33 | 64.67 | 71.83 | 72.83 | 68.33 | 71.17 |  |  |  |\n| **New ACC** | 37.62 | 38.14 | 38.19 | 35.24 | 38.86 | 37.95  |  |  |  |\n| **Learned $\\alpha\\in [0,1]$** | 0.22 | 0.26 | 0.25 | 0.23 | 0.25 | 0.26 |  |  |  |\n\n## **Question 2**\n\n> How does the $\\alpha$ parameter in the FGW distance affect performance across different graph types and domains?\n\n$\\alpha$ is a learnable parameter that adapts to the dataset's structure-feature-label relationships. It's initialized as 0.5, and adjusted through the training.  \n\nAs shown in **Tables RT1** and **RT2**, across all valid K settings, the model consistently learns moderate and well-calibrated $\\alpha$ values that effectively balance structural and node feature information.\n\nWe observe that when using GCN+ as backbone, the learned $\\alpha$ values are generally higher than with GIN+, possibly correlating with GCN+'s significantly better New ACC performance.\n\n## References\n\n- [20] Architecture matters: Uncovering implicit mechanisms in graph contrastive learning, NeurIPS 2023.\n- [58]  SimGRACE: A Simple Framework for Graph Contrastive Learning without Data Augmentation, WWW 2022."}, {"review_id": "JOvhADT5dZ", "reviewer": "Reviewer_n3Hv", "summary": "This study investigates the traditional Novel Class Discovery problem in the context of graph-level classification. The authors first introduce several graph datasets suitable for NCD evaluation and design three Graph-Level NCD baselines based on existing image-based NCD methods. Subsequently, they analyze these baselines and identify key limitations that conventional visual NCD designs fail to effectively incorporate graph structural information, leading to suboptimal performance on graph data. To address this issue, the authors propose a novel approach based on optimal transport that integrates graph structural information.", "questions": "See in Weaknesses.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths\n1. This work appears to be the first to explore NCD in the context of graph-level classification. Potential applications, such as novel drug molecule discovery, could benefit from this research.  \n2. The experimental evaluation and analysis of the baselines reveal unique challenges specific to NCD on graph-structured data.  \n3. The authors design and implement an efficient and differentiable Fused Gromov-Wasserstein distance module, which facilitates the application of FGW in graph-level tasks.  \n\nWeaknesses\n1. The study employs a relatively limited number of datasets and baselines.  \n2. The discussion on the challenges of Representation Similarity in graph data (Section 4.2) is somewhat unclear. A more detailed, point-by-point analysis with additional elaboration would strengthen this section.  \n3. The meaning of the \"Avg. Rank/All\" column in Tables 3 and 4 is not explicitly explained. Does it represent the average ranking across all preceding columns?  \n4. The proposed BAPG layer bears similarity to the method presented in [1], but a detailed comparison between the two is lacking.  \n\n[1] Template Based Graph Neural Network with Optimal Transport Distances, NeurIPS 2022.", "was_revised": true, "final_justification": "The author's response largely addressed my concerns.", "rebuttal": "We sincerely thank the reviewer for the thoughtful and constructive feedback on our manuscript. The reviewer's insightful comments have helped us identify areas for clarification and improvement. We appreciate the recognition of our work's novelty in exploring NCD for graph-level classification and the potential applications in domains like drug discovery. Below, we provide a point-by-point response to address the reviewer's concerns\n\n## **Weakness 1**\n\n> The study employs a relatively limited number of datasets and baselines.\n\n**Limited Datasets**:\nAs discussed in Sec. 3.1, while there are over 120 public graph-level datasets, few are naturally suited for multi-class graph classification beyond CV-derived ones (e.g., CIFAR10, MNIST [10], Letter-high, COIL-RAG [42]). Since CV-to-graph conversion is not popular and underperforms CNNs, we retained only CIFAR10 (Graph). Truly suitable GLNCD benchmarks are scarce. Furthermore, we excluded large-scale datasets like ogbg-ppa [R1] since Graph SSL, a key component of GLNCD, currently lacks established scaling laws for large datasets [R2]. These fundamental challenges in large-scale GLNCD scenarios, along with scalability issues, warrant further investigation and are deferred to future work.\n\n**Limited Baselines**:\nAs outlined in Appendix D, we conduct an initial exploration of GLNCD, addressing two key questions: **(1)** whether CV-based NCD methods trivially generalize to graphs, and **(2)** what unique challenges GLNCD presents compared to traditional NCD.\n Our baseline G-AutoNovel and controlled experiments (e.g., feature quality manipulation in Sec. 4) show that standard NCD approaches can not trivially generalize to graph, suggesting structure information loss as a key challenge. This key challenge is further verified by comparing G-AutoNovel with the carefully designed ProtoFGW-NCD.\n While our baselines are not exhaustive, they cover the core components of GLNCD (Graph SSL + Pseudo-Labeling) and are sufficient to answer the two key questions.\n\n## **Weakness 2**\n>\n> The discussion on the challenges of Representation Similarity in graph data (Section 4.2) is somewhat unclear. A more detailed, point-by-point analysis with additional elaboration would strengthen this section.\n>\nWe provide additional clarification for Section 4.2 for better understanding here. The section will be updated in the revised manuscript accordingly.\n\nIn Section 4.1, we propose two metrics to evaluate pseudo-label quality and compare AutoNovel (CIFAR-10) with our G-AutoNovel baseline. Figure 1(b, c) reveals that RS in G-AutoNovel fails to generate effective pseudo-labels, unlike in the image domain.\n\nSection 4.2 investigates **Why RS Fails in Graphs?**\n\n**Hypothesis 1**: RS failure may stem from poor GraphCL (SSL) representations, resulting in low-quality pseudo-labels.  \n**Test**: Using SupCon loss as an oracle, we train encoders with three representation quality levels and evaluate pseudo-label quality and NCD performance.  \n\n**Finding 1**: Figure 2(b, c) shows pseudo-label quality remains consistent across representation levels, rejecting **Hypothesis 1**.  \n**Finding 2**: Despite similar pseudo-label quality, NCD performance varies significantly (Fig. 1a). We conclude:  \n\n- Representation quality primarily affects pseudo-label *utilization* (e.g., learning clearer decision boundaries) rather than their inherent quality.  \n- This phenomenon does not mean that representation quality does not affect pseudo-label quality. On CIFAR-10 (Image), as representation quality improves with training, pseudo-label quality also increases.\n\n**Key Insight**: RS (in G-AutoNovel) is inherently unsuitable for graphs as it cannot refine pseudo-labels even with improved representations.  \n\n**Core point**: GraphCL and RS in G-AutoNovel underutilize graph structural information, harming *utilization* and *quality* respectively. And this leads to low NCD performance.\n\nIn Section 5, we augment G-AutoNovel with a minimal structural-aware BAPG layer to get ProtoFGW-NCD. And we validate the above core point by comparing ProtoFGW-NCD with G-AutoNovel.\n\n## **Weakness 3**\n>\n> The meaning of the \"Avg. Rank/All\" column in Tables 3 and 4 is not explicitly explained. Does it represent the average ranking across all preceding columns?\n\nYes, it is the average ranking of the metrics in the Old ACC and New ACC columns (a total of 8 columns) across the entire dataset. The model ranking for each column is determined by sorting within that column.\n\n## **Weakness 4**\n>\n> The proposed BAPG layer bears similarity to the method presented in [1], but a detailed comparison between the two is lacking.\n\nThe TFGW layer proposed by [51] computes the FGW distances between the input graph (with node representations) and $K$ template graphs. These $K$ distances form a $K$-dimensional explicit structural representation of the input graph, which is then fed into subsequent classification or regression heads.  \n\n**Motivation**: TFGW is designed to improve GNN performance in supervised classification and regression tasks. In contrast, our approach aims to address parallelized comparison between graphs with irregular sizes in self-/semi-supervised tasks.  \n\n**Working Principle**: The forward pass of the TFGW layer employs the Conditional Gradient algorithm from [51], and does not support batch parallelism. In comparison, our BAPG layer adopts a variant of the Bregman Alternating Projected Gradient (BAPG) algorithm [55] parallelized by us. While the gradient formula of the FGW distance remains consistent for a single 1-to-1 FGW problem, TFGW does not support parallelized batch-to-batch backward passes, significantly limiting its applicability.  \n\n**Computational Efficiency**: The TFGW layer does not natively support GPU computation and requires data transfer between host (CPU) and device (GPU). In contrast, the BAPG layer is implemented via PyTorch's `torch.autograd.Function` interface, eliminating CPU-GPU data transfers. Thanks to this and its parallelized design, our BAPG implementation achieves up to 2070x speedup over the implementation in the well-known POT library [15] (see Appendix C.2).  \n\n**Impact on the Field**: Our BAPG layer alleviates the efficiency limitations of previous differentiable FGW operators (e.g., the TFGW layer), potentially enabling wider use of FGW distance-based techniques in modern end-to-end graph learning systems.\n\n## References\n\n- [10] Benchmarking Graph Neural Networks, JMLR, 2023.\n- [42] TUdataset: A collection of benchmark datasets for learning with graphs, ICLRW 2022.\n- [51] Optimal Transport for structured data with application on graphs, ICML 2019.  \n- [55] Template Based Graph Neural Network with Optimal Transport Distances, NeurIPS 2022.  \n- [15] POT: Python Optimal Transport, JMLR, 2021.\n- [R1] Open Graph Benchmark: Datasets for Machine Learning on Graphs, 2020.\n- [R2] Do Neural Scaling Laws Exist on Graph Self-Supervised Learning?, 2024."}, {"review_id": "aGTuTXcFBu", "reviewer": "Reviewer_adDu", "summary": "The authors explored the task of discovering new classes in the graph-level tasks. They begin by analyzing the performance of existing CV methods on graph data, highlighting their inability to effectively utilize structural information. To address this, the authors introduced the Gromov-Wasserstein distance and designed a method that can simultaneously encode both structural and features information by calculating the distance to many learnable prototype graphs. The authors claimed that experiments showed the effectiveness of the proposed method.", "questions": "Please see the Weaknesses.", "limitations": "Yes.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n- The authors explore a novel and valuable problem, which is discovering new classes in graph-level tasks.\n\n- The proposed method is innovative. The authors design multiple prototype graphs and calculate the distribution distance between graphs and prototype graphs to obtain node representations. This idea provides valuable insights to the readers.\n\n- The authors' analysis of CV methods is valuable.\n\nWeaknesses:\n\n- The primary drawback of this paper, in my view, is that the proposed method does not seem to work. In Tables 3 and 4, the improvements of the proposed method compared to existing CV methods are too marginal. Particularly in Table 4, the results for new classes show that the proposed method achieves the same rank of 2 as AutoNovel, indicating no improvement.\n\n- The organization of Section 5 could be improved to enhance clarity. The authors might consider providing an overview of the entire method first, then detailing each part individually. Additionally, I suggest including more explanations to clarify the rationale behind each step, which might make it easier for readers to follow. While I understand the challenge of explaining thoroughly within limited space, the authors could make more references to the appendix and provide additional details there.\n\n- The motivation for selecting the Gromov-Wasserstein distance is missing. There are many existing methods to measure structural similarity. The authors should explain why Gromov-Wasserstein was chosen over others.\n\n- The experiments lack a report on the results of the balance weight $\\alpha$ between structure and feature. It is a learnable parameter, and I believe the authors should provide the learned values to illustrate the extent to which the proposed method leverages structural information.\n\n- I think the authors need to report the results of the proposed method under the settings of Figures 1 and 2 for a comprehensive evaluation of the proposed method.", "was_revised": true, "final_justification": "As I mentioned in my earlier comments, I do not deny the innovation and contribution of this paper, nor do I insist that it should be rejected. However, the proposed method achieves only marginal improvements over approaches that do not incorporate graph structure. This raises two important questions: 1) whether the authors have effectively leveraged the structural information, and 2) whether such structural information should, in fact, be considered for this task. Considering these issues, along with the lack of responses to new comments of all reviewers, I have maintained my score of 3.", "rebuttal": "We sincerely appreciate the reviewer's thoughtful feedback and constructive suggestions, which have helped us identify areas for improvement in both the presentation and technical rigor of our work. Below, we provide a point-by-point response to the reviewer's concerns.\n\n## **Weakness 1**\n\n> The primary drawback of this paper, in my view, is that the proposed method does not seem to work. In Tables 3 and 4, the improvements of the proposed method compared to existing CV methods are too marginal. Particularly in Table 4, the results for new classes show that the proposed method achieves the same rank of 2 as AutoNovel, indicating no improvement.\n\nAs a pioneering work in this field, the primary goal of this paper is to establish comprehensive benchmarks and methodologies, provide in-depth analysis of their performance, and offer valuable insights to the community.\n\nOur ProtoFGW-NCD is primarily designed to validate the argument at the end of Section 4 (i.e.,the lack of structural information causes methods like G-AutoNovel to fail), rather than to propose an optimal method. To strictly control other variables for fair comparison, ProtoFGW-NCD only inserts a BAPG layer into the representation output layer of G-AutoNovel to incorporate structural information, while keeping all other key components (e.g., training loss functions, augmentation strategies) identical.\n\nRegarding the experimental results, in Tables 3 and 4, ProtoFGW-NCD achieves the top rank in performance for old classes and new classes, except for the avg. rank of New ACC in Table 4, where it ties with AutoNovel. However, this does not imply no improvement. On the three inherently graph-structured datasets (ENZYMES, MalNet-Tiny, and REDDIT12K), ProtoFGW-NCD improves over AutoNovel by **7.99%**, **1.47%**, and **4.33%**, respectively. Given that ProtoFGW-NCD differs from G-AutoNovel only by a single BAPG layer, we argue that such improvements already indicate meaningful progress.\n\n As emphasized in the Limitations section, future work should explore more efficient modules for mining structural information to achieve better performance, but that is not the primary goal or core contribution of this paper.\n\n## **Weakness 2**\n>\n>The organization of Section 5 could be improved to enhance clarity. The authors might consider providing an overview of the entire method first, then detailing each part individually. Additionally, I suggest including more explanations to clarify the rationale behind each step, which might make it easier for readers to follow. While I understand the challenge of explaining thoroughly within limited space, the authors could make more references to the appendix and provide additional details there.\n\nThank you for your constructive suggestion. We will reorganize the content according to your advice in future revisions. Here, we provide some additional explanations for Section 5 to enhance clarity.\n\n**Motivation of Section 5.** At the end of Section 4, we propose the viewpoint that the lack of structural information affects both the SSL part (i.e., GraphCL) and the RS part of AutoNovel, leading to its failure. To validate this claim, we designed, ProtoFGW-NCD, a method that is identical to AutoNovel except for one structural information component. It injects structural information into SSL and RS via a BAPG layer, without requiring additional loss terms or more sophisticated strategies.\n\n**Section 5.1: ProtoFGW-CL, Minimal GraphCL Variant with Explicit Structural Information.**\nExisting Graph SSL methods more complex than GraphCL often focus on augmentation strategies and self-supervised loss design. While some incorporate structure, they still do not consistently outperform GraphCL [20, 58]. Thus, we chose a different approach: directly adding a BAPG layer after the GraphCL backbone to inject structural information into the representations. This design allows our method to serve as an extremely simple variant of GraphCL for the comparison study with AutoNovel.\n\n**Prototypes in the BAPG Layer.** SSL requires comparing a set of $b_1$ graphs $\\mathcal{G}_1$ with another set of$b_2$ graphs $\\mathcal{G}_2$. Graph comparison tools that explicitly incorporate structural information include GED and FGW, among which we selected FGW (see response to **Weakness 3** for the behind rationale). Existing differentiable FGW layer requires brute-force looping over$b_1 \\times b_2$ pairs, making it difficult to leverage modern GPU parallelism: primarily because comparing graphs of varying sizes is inherently non-parallelizable. We found that if the graphs in $\\mathcal{G}_2$ share the same size, FGW can be efficiently parallelized (see Appendix B and C.2 of our paper). In practice, this is hard to guarantee, so we introduce a set of fixed-size prototype graphs as intermediaries, and then compare variable-sized graphs by comparing their relationships with these prototypes.\n\n**Sec. 5.2: FGW-RS, Minimal RS Variant with Explicit Structural Information.**\nSince the representations output by the BAPG layer already contain structural information, feeding them directly into traditional RS yields a simple RS comparison method. Had we used vector similarity thresholds instead of RS to generate pseudo-labels, ProtoFGW-NCD (FGW-RS) would no longer serve as a proper and fair comparison to AutoNovel (RS). Moreover, once the representations incorporate structural information, the advantages of RS over vector similarity [21] should manifest as expected.\n\n**Sec. 5.3: ProtoFGW-NCD comprised of ProtoFGW-CL and FGW-RS.**\nCombining the two is natural, as both only require a same BAPG layer. This section primarily outlines the entire pipeline and highlights the advantages of the BAPG layer over the previous differentiable FGW layer, TFGW layer [55].\n\n## **Weakness 3**\n>\n> The motivation for selecting the Gromov-Wasserstein distance is missing. There are many existing methods to measure structural similarity. The authors should explain why Gromov-Wasserstein was chosen over others.\n\nIn addition to (F)GW distance, there are other structural similarity measures such as GED, graph kernels, and spectral distance.\n\n- **Compared to these methods, FGW's key advantage lies in its differentiability via implicit differentiation, which enables seamless integration into modern end-to-end systems**. Other methods, including but not limited to GED, spectral distance, Weisfeiler-Lehman kernel, and random walk kernel, are non-differentiable, and it is challenging to render them differentiable.\n\n- **FGW couplings provide node-level interpretability for graph comparison**.\n- **We find that FGW supports batch-to-batch parallelization on GPUs (see Appendix B for our parallel design)**. While other methods can be (approximately) solved with similar complexity to FGW for a single 1-to-1 graph comparison, they cannot achieve the same level of batch parallelism.\n\n## **Weakness 4**\n>\n> The experiments lack a report on the results of the balance weight $\\alpha$ between structure and feature. It is a learnable parameter, and I believe the authors should provide the learned values to illustrate the extent to which the proposed method leverages structural information.\n\nWe conducted experiments with different numbers of prototype graph on ENZYMES, to observe the learned balance weight values (i.e., the leverage of structural information) under different scenarios.\n\nFrom **Tables R1** and **R2**, we found that:\n\n- In all cases, our method learned non-negligible $\\alpha$, indicating that the proposed approach indeed leverages structural information.\n- Different backbones and prototype numbers influence $\\alpha$, with the backbone having a significant impact.\n\n***Table R1: The performance on ENZYMES with GCN+ backbone. Results are averaged over 10 runs.***\n\n| **K** | 30 | 50 | 70 | 90 | 120 | 150 |\n|---|---|---|---|---|---|---|\n| **Old ACC** | 68.00 | 69.50 | 65.33 | 66.17 | 70.33 | 68.33 |\n| **New ACC** |44.43 | 45.62 | 48.05 | 48.00 | 47.76 | 46.81 |\n| **Learned $\\alpha$** |0.34 | 0.45 | 0.53 | 0.56 | 0.54 | 0.60 |\n\n***Table R2: The performance on ENZYMES with GIN+ backbone. Results are averaged over 10 runs.***\n\n| **K** |30 | 50 | 70 | 90 | 120 | 150 ||||\n|---|---|---|---|---|---|---|---|---|---|\n| **Old ACC** | 73.33 | 64.67 | 71.83 | 72.83 | 68.33 | 71.17 ||||\n| **New ACC** | 37.62 | 38.14 | 38.19 | 35.24 | 38.86 | 37.95||||\n| **Learned $\\alpha$** | 0.22 | 0.26 | 0.25 | 0.23 | 0.25 | 0.26 ||||\n\n## **Weakness 5**\n>\n> I think the authors need to report the results of the proposed method under the settings of Figures 1 and 2 for a comprehensive evaluation of the proposed method.\n\nGiven the restrictions on the rebuttal format imposed by the official Program Chairs, we are unable to present figures such as Figure 1 and 2. Instead, we selected ten consecutive and equally spaced time points and presented the changes in New ACC and MCC (i.e., pseudo-label quality) in **Table R3**.\n\nIn the early stages of training, as MCC improved, New ACC also showed significant improvement. However, in the later stages, after MCC stabilized, New ACC continued to exhibit slight improvements.\n\n***Table R3: The training dynamics on ENZYMES with GCN+ backbone. Results are averaged over 10 runs.***\n\n|Epoch|0|20|40|60|80|100|120|140|160|180|200|\n|---|---|---|---|---|---|---|---|---|---|---|---|\n|MCC|0.147|0.167|0.200|0.200|0.223|0.244|0.246|0.247|0.245|0.248|0.247|\n|New ACC|0.383|0.409|0.404|0.405|0.411|0.446|0.447|0.419|0.404|0.457|0.474|\n\n## References\n\n- [20] Architecture matters: Uncovering implicit mechanisms in graph contrastive learning, NeurIPS 2023.\n- [21] AutoNovel: Automatically Discovering and Learning Novel Visual Categories, TPAMI, 2022.\n- [55] Template based Graph Neural Network with Optimal Transport Distances NeurIPS 2022.\n- [58] SimGRACE: A Simple Framework for Graph Contrastive Learning without Data Augmentation, WWW 2022."}]

Author rebuttal:

Meta-review: This paper introduces Graph-Level Novel Category Discovery (GLNCD) and proposes ProtoFGW-NCD, which leverages prototype-based fused Gromov-Wasserstein distance and structure-aware pseudo-labeling to address the limitations of existing NCD methods on graphs. Reviewers agreed that the problem is timely and important, highlighting the novelty of formulating GLNCD and the efficiency of the proposed differentiable FGW module, but raised concerns about limited datasets, modest performance gains, and insufficient comparisons with alternative distance metrics. The authors clarified the motivation for FGW and provided additional explanations of their design choices, which addressed some concerns but left questions on scalability and evaluation breadth partly unresolved.
Decision: Accept (poster)