LEGO-Learn: Label-Efficient Graph Open-Set Learning
Authors: Haoyan Xu
Kay Liu
Zhengtao Yao
Philip S. Yu
Mengyuan Li
Kaize Ding
Yue Zhao
Venue: Accepted by TMLR ()

Abstract: How can we train graph-based models to recognize unseen classes while keeping labeling costs low? Graph open-set learning (GOL) and out-of-distribution (OOD) detection aim to address this challenge by training models that can accurately classify known, in-distribution (ID) classes while identifying and handling previously unseen classes during inference. It is critical for high-stakes, real-world applications where models frequently encounter unexpected data, including finance, security, and healthcare. However, current GOL methods assume access to a large number of labeled ID samples, which is unrealistic for large-scale graphs due to high annotation costs.  
In this paper, we propose LEGO-Learn (Label-Efficient Graph Open-set Learning), a novel framework that addresses open-set node classification on graphs within a given label budget by selecting the most informative ID nodes. LEGO-Learn employs a GNN-based filter to identify and exclude potential OOD nodes and then selects highly informative ID nodes for labeling using the K-Medoids algorithm. To prevent the filter from discarding valuable ID examples, we introduce a classifier that differentiates between the $C$ known ID classes and an additional class representing OOD nodes (hence, a $C+1$ classifier). This classifier utilizes a weighted cross-entropy loss to balance the removal of OOD nodes while retaining informative ID nodes. Experimental results on four real-world datasets demonstrate that LEGO-Learn significantly outperforms leading methods, achieving up to a $6.62\%$ improvement in ID classification accuracy and a $7.49\%$ increase in AUROC for OOD detection.

Published in Transactions on Machine Learning Research (05/2025)
LEGO-Learn: Label-Efficient Graph Open-Set Learning
Haoyan Xu University of Southern California
haoyananuussc.om
Kay Liu
zliu234 @uic. edu
University of Illinois Chicago
Zhengtao Yao University of Southern California
2yao92480uscccom edu
Philip S. Yu University of Illinois Chicago
psyu@uic. edu
Mengyuan Li University of Southern Cakifornia
mengguanki@use..ed
Kaize Ding Northwestern University
kaize. www.nnnorrttttttrrr.cmomm edu
Yuc Zhao
yzhao01 Matioo000@ussco edu
University of Southern California
Reviewed on OpenReview: https: openreview. net/ forum? id= J6o2TT
Abstract
How can we train graph-based models recognize unseen classes while keeping labeling costs low? Graph open-set learning (GOL) and out-of-distribution (OOD) detection aim to address this challenge by training models that accurately classify known, in-distribution (ID) classes while identifying and handling previously unseen classes during inference. It is critical for high-stakes, real-world applications where models frequently encounter unex- pected data, including finance, security, and healthcare. However, current GOL, methods assume access to a large number of labeled ID samples, which is unrealistic for large-scale graphs due high annotation costs.
In this paper, we propose LEGO-Learn (Label- Efficieet Graph Open-set Learning), a novel framework that addresses open-set node classification on graphs within a given label budget by selecting the most informative ID nodes. L.F.O-Learn employs GNN-based filter to identify and exclude potential OOD nodes and then selects highly informative ID nodes for labeling using the K-Medoids algorithm. To prevent the filter from discarding valuable ID examples, we introduce a classifier that differentiates between the C' known ID classes and an additional class representing OOD nodes (hence, a C++ classifier). This classifier utilizes a weighted cross-entropy loss to balance the removal of OOD nodes while retaining informative datasets demonstrate that LEGO-Lear ID nodes. Experimental results on four achieving up 6.62% improvement in ID significantly outperforms leading methods, classification accuracy and 7. 7.49% increase in AUROC for OOD detection.
1 Introduction
Graph-structured data has bocome increasingly important in various fields, including social networks (Xiao
al. 2020 Fan al.] 2019 Hao al. 2024). citation networks (Cummings & Nassar 2020
Gao et al.
2021
and biological systems (Ktena al. 2017 Zhang et al. 2021b Xu et al. 2021
2020 Bai et al. 2020

---

Published in Transactions on Machine Learning Research (05/2025)
due to its ability to model complex relationships between entities. Traditional node classification approaches in these contexts typically operate under a closed-set assumption, where both the labeled and unlabeled data are drawn from the same class distribution. However, in many real-world scenarios, models are expected
to operate in an open-set environment, encountering previously unseon classes or ont-of-distributio (OOD)
data during test time (Zhang et. al. 2021a Qin et al. 2024; Dong el. al. 2024 Liu et al. 2023 Guo et al.
2023
Fang et al. 2022: Yang et al. 2024a Heo & Kang 2024). This discrepancy between training and test
distributions necessitates models that can classify in-distribution (ID) data while reliably detecting OOD
instances, despite being trained exclusively on ID data. Some recent works (Wu et al. 2020 Song & Wang,
Zhao et al.; 2020 Wu et al. 2023) have aimed to extend graph neural networks (GNNs) to the open-set learning paradigm. On the one hand, these approaches enable GNNs to perform robustly under open-set conditions. On the other hand, they assume access to a large amounl of labeled ID data for training, However, accessing a large amount of labeled data is unrealistic for large-scale, real-world graphs, where obtaining accurate labeled data is costly and time-consuming (Scttles 2009] Tang et al.] (021). Without considering the label budget, current solutions become impractical for resource-constlaanne settings, where efficient use of labeled data is critical (Liu et al.) 2021). Thus, improving the label efficiency is the key to practical graph open-set learning (GOL) methods. As shown in Fig. [ GOL refers to the task of learning from graph data in scenarios where the unlabeled nodes may belong to unknown classes. The goal is to accurately classify ID (known) nodes while effectively detecting and handling OOD (unknown) nodes. A detailed problem definition of GOL is provided in $3.1
2022
Label Efficiency Challenges in GOL. There are two applicable approaches to addressing this issue. First, label-efficient learning techniques, such as graph active learning (GAL), can effectively reduce labeling costs for closed-set node classification tasks (Cai et al., 2017 Ning et al. 2022 Wu et al.. 2019). They focus selecting the most informative nodes for labeling, minimizing the number of labels required for successful training. Thus, GAL methods prioritize labeling nodes that exhibit high uncertainty or diversity, which often include OOD samples that differ significantly from majority ID samples (Yan et al.] 2024 Safaci et al. 2024). However, the literature indicates that open-set learning benefits more from labeled ID data than from OOD samples (Ning et al. 2022 Park et al. 2022 Yang et al., 2024b Safaei et al., 2024), as OOD samples cannot be directly used to train the target ID) classifier. When querying OOD examples for labeling, human annotators would disregard these OOD examples they are unnecessary for the target task, leading to a waste of the labeling budget (Park et al. 2022). Consequently, GOL benefits more from labeled ID samples than OOD samples, which makes applying GAL methods for GOL non-ideal. Second, there are also label-efficient
learning for open-set scenarios in the context of image classification Ning et al. (2022); Park et al. (2022)
Yang et al. (224bb); Mao et al. 2024): : Han et al. 2023 Yan et al. (2024). However, the grid-like structure of image data where each sample is assumeed independent differs fundamentally from the interconnected
nature of graphs. In graph data, nodes are not isolated but influenced by their neighboring nodes, presenting unique challenges. Thus, label-efficient open-set methods for images do not directly translate to GOL, where dependencies between nodes must be considered in the design. In summary, addressing the intersection of open-set classification, label efficioncy, and OOD detection for graph data-referred to as GOL in this work presents a complex challenge. There is a pressing need for novel approaches that balance label efficiency and accurate OOD detection in graphs, ensuring that models generalize effectively while operating within labeling constraints.
Our Observations and Proposal. Consider citation network where the goal is to classify papers into specific MT. research fields, such as robotics, computer vision, and natural language processing (see Fig. 1. However, the network also includes papers from unrelated fields like neuroscience and biology, which do not contribute to the primary classification task. Labeling these OOD papers would be inefficient, as they do not aid in training the ID) classifier, as we discussed above. Therefore, a practical label-efficient GOL met is (1) accurately identifying and filtering OOD nodes and (2) selecting the most informative ID nodes for labeling to enhance classifier training.
needed, with two key properties:
In this work, we focus on label-efficient graph open-set learning (see the problem definition in $3.1 aiming to train an accurate and robust ID classifier within a specific label budget. Our objective is to select informative ID examples for training, enabling the classifier to make confident predictions for ID nodes and effectively detecting OOD nodes, where the classifier is expected to show low confidence. To achieve this, we propose
2

---

Published in Transactions on Machine Learning Research (05/2025)
label-gfficient graph open-set learning framework, termed LEGO-Learn. Our approach addresses two key challenges: (1) filtering out OOD nodes while preserving informative IT) nodes, and (2) selecting the most valuable ID nodes for labeling. As shown in Fig. 2 we start by tackling the first challenge: filtering OOD nodes. We introduce a GNN-based filter, which captures graph structure and node dependencies to identify potential OOD nodes. This step ensures that most OOD nodes are removed before any labeling occurs. Next, we focus on selecting the most informative ID nodes for labeling. Given the limited label budget, we use the K-Medoids algorithm to choose diverse, representative nodes from the filtered potential ID set. This ensures that the labeled nodes provide maximum utility for training the classifier by covering various parts of the graph's 's feature space. Once we have the labeled ID nodes, they are used to train our ID classifier. However, we found that while strong filter effectively removes OOD nodes, it can also discard informative ID nodes. To mitigate this, we design a (C + 1) class classifier with a weighted cross-entropy loss. This classifier reduces the risk of over-filteriin by penalizing the removal of valuable ID nodes, ensuring that the filter retains a balanced set of useful data for further training.
Our technical contributions include:
First Label-efficient Graph Open-set Learning Method. To the best of our knowl- edge, we are the first to identify this critical real-world problem and provide a thorough setting and solution.
Open-set Citation Network
Query Set
Selection
Annotation
Novel Framework Design. We introduce LEGO-Learn, a general framework that effec- tively filters out potential OOD nodes while se- lecting highly informative ID nodes for manual labeling. The core of LEGO-Learn is GNN- based filter, designed with a weighted cross- entropy loss to balance between purily theilyyhhhpt the pro- portion of retained ID examples-ane informa- liveness the usefulness of selected examples for improving the target task.
Robotics NLP
Training
Uniaheled modes
Classifier
Labeled nodes GOD nodes
Figure 1: The illustration of graph open-set classifica- tion in a citation network. We aim to classify papers into ML research fields such as robotics, CV, and NLP (ID classes). We want to find nodes from ID classes to train the ID classifier.
Effectiveness. LEGO-Learn is validated on four extensive node classification datasets, all under label budget constraints. Experimental results show that LEGO-Learn can efficiently filter out OOD nodes and improve both ID classification and OOD detection. Specifically, LEGO-Learn achieves up to a 6.62% increase in classification accuracy and a 7.49% improvement in AUROC for OOD detection compared to 12 baseline methods. hoa..b//c//heetttyaa//ggggg
The code is available at:
2
Related Work
2.1
Node-level Graph Open-set Learning
Recent literature has extensively studied the detection of OOD samples on which models should exhibit low confidence. OODGAT (Song & Wang 2022) introduces GNN model that explicitly captures the interactions between different kinds of nodes, effectively separating inliers from outliers during feature prop- agation. OpenWGL (Wu et al. 2020) introduces an uncertain node representation learning method based on a variational graph autoencoder, which can identify nodes from unseen classes. GKDE (Zhao et. al., 2020) introduces a network for uncertainty-awart estimation, designed to predict the Dirichlet distribution of nodes and detect OOD data. GNNSafe (Wu al.) 2023) demonstrates that standard GNN classificrs inherently have strong capabilities for detecting OOD samples and introduces a provably effective OOD discriminator built on energy function derived directly from graph neural networks trained using standard classification
3

---

Published in Transactions on Machine Learning Research (05/2025)
loss. However, all of these methods assume the availability of sufficient ID labels in an open-set scenario, which is not always practical in real-world situations where labeled data is often costly to obtain.
2.2 Label-efficient Graph Learning
Many label-efficient learning methods are designed to optimize the performance of semi-superrised node classification under a label budget constraint. AGE (Cai et al.) 2017) selects the most informative nodes for training by considering both graph-baser based information (such as node centrality) and the learned node embeddings (including node classification uncertainty and embedding representativeness). FeatProp (Wul et al. 2019) selects nodes by propagating their features through the graph structure, followed by K-Medoids clustering, which makes it less susceptible to inaccuracies in the representations learned by under-traing models. Recently, based on K-Medoids clustering to select important nodes, MITIGATE (Chang et al., 2024) devises a masked aggregation mechanism for generating distance features that consider representations in latent space and features in the previously labeled set. These graph label-efficient learning methods are usually based on the closed-set assumption that the unlabeled data are drawn from known classes, which causes them to fail in open-set node classification tasks. OWGAL (Xu et al. 2023) studies the learning problem on evolving graphs with insufficient labeled data and known classes. It uses prototype learning and label propagation to assign high uncertainty scores to target nodes in both the representation and topology spaces. While also considering label efficiency in open-world settings, their approach differs from ours by dynamically expanding the GNN classifier to accommodate new known classes instead of detecting OOD nodes. In contrast, our goal is to train a robust ID classifier, with a fixed number of known classes, that achieves high label efficiency the open-sct sctting.
2.3 Label-efficient Open-set Annotation
Label-efficient open-set learning has been widely studied in image classification field. LIOSA (Ning et al. 2022 is one of the first active learning framework for real-world large-scale open-set annotation tasks. It can precisely select examples of known classes by decoupling detection and classification. MQ-Net (Park et al. 2022) utilizes meta-lcarning techniques to achiove the optimal balance between purity and informativeness.
PAT. Yang al., 2024b) evaluates unlabeled instances based on informativeness and representativennss, balancing pseudo-1D ID and pseudo-OOD instances in each round. Actively querying pseudo-OOl OOD instances improves both the ID classifier and OOD detector. EOAL (Safaei et al. 2024) quantifies uncertainty using closed-set and listance-based entropy scores to distinguish known from unknown samples, then applies clustering to select the most informative instances. Yan et al. (2024) selects highly informative ID) samples by balancing two proposed criteria: contrastive confidence and historical divergence, which measure the possibility of being ID and the hardness of a sample, respectively. However, these approaches are based on the assumption that data samples are generated independently, making them difficult to apply to graph- structured data, where node instances are interdependent.
3 Proposed Method
3.1 Problem Definition
Node-level Graph Open-set Classification. Given a graph G = (V, X),, where Vis the set of nodes and E is the set of edges, along with node features X fx, E V} and node labels Y = {vo E V}. We have a limited labeled node set VT. and a large unlabeled node set Vv, where Vr. = (uf J and Vo = {u J==1- Each labeled node of belongs to one of C known classes Yz (ye]e, while unlabeled node uf may belong to an unknown class not included in Yr.
yau
The problem is framed in a semi supervsperv,s,d, transductive setting, where we can access the full set of nodes during training but only a subset of class labels (ID classos). In general, the task is twofold:
1. OOD Detection: For each node V, determine whether it belongs to one of the in-distribution C known classes or from the out-of-distributiin unknown classes.
4

---

Published in Transactions on Machine Learning Research (05/2025)
Graph
OOD Filtering ($3.3)
Node Selection ($3.5)
First C Classes Potential ID Nodes
GNN
Classification and OOD Detection
zi
clustering
Post-hoc OOD Detector ($3.6)
GNN-based ID Classifier ($3.4)
Medold nodes
training Human-in-the-Loog
Ordinary nodes
Unlabeled nodes
Labeled Set
O aa
Labeled nodes
query
selecting
Unknown Set
Annotator
Medolds
Figure 2: An overview of our framework LEGO--Laar. The first step is to GNN-based filter to identify and remove OOD nodes, while using C + 1 classifier with weighted cross-entropy loss to avoid mistakenly eliminating valuable ID nodes (3.3) A K-Medoids-based node selection method ($3.5) is then applied to choose the most informative ID nodes, which are annotated and used for the next round of training the ID classifier ($3.4). Finally, the filter is retrained with both ID and unknown nodes, and a post-hoc OOD detection method applied to strengthen the ID classifier's 's ability to recognize unseen classes ($3.6).
2. ID Classification: For nodes identified as ID nodes, classily them into one of the predefined classes.
Label-efficient Graph OOD Detection and ID Classification. Given an initial training set Versin on G, labeling budget B, and a loss function I, our goal is to selectively construct query set that contains many known (ID) examples as possible. At the same time, aim to select the most informative and representative ID nodes. After selection, the chosen ID nodes are labeled with class labels, while the remaining selected nodes are considered unknown (OOD) nodes.
The goal the selection procedure to select a subset of nodes under label budget constraint, such that querying their labels will allow us to construct a strong ID classifier. Thus we want select a subset of nodes 8 C VV Virain that produces a model with the lowest loss on the remaining nodes Viest:
arg min Eo,EVon (1ys, [s)] P
(1)
where f is our target ID classifier, is the label prediction with f of node vs Specifically, let V2 be the current labeled set, Vo the pool of unlabeled nodes available for selection, and Vo the set of nodes identified as OOD, ie., not belonging to any known ID class. Then after querying the labels of the selected nodes V", known nodes V are annotated and the labeled set is updated to V2 = V2 U V2, while nodes Ve with unknown OOD classes are added to the unknown set Vo and Vo = Vo U V8- Also, Vu = Vu V and
[3] = = q. Thus, the precision of ID classes can be defined as:
P precision
(2)
p +
3.2 Overview of LEGO-Learn
In real-world scenarios, graphs often contain a large number of unlabeled nodes, many of which may be OOD nodes and irrelevant to the target task. Remember that our objective is to train ID classifier using
5

---

Published in Transactions on Machine Learning Research (05/2025)
only limited number of ID labels, aiming for high accuracy in ID classification while effectively detecting OOD data, where the classifier is expected to exhibit. low confidence. Therefore, we strive to filter out many OOD nodes as possible before labeling. To achieve this, the first step is to design GNN-based filter to identify and remove potential OOD nodes (see $3.3). However, many useful ID nodes often exhibit high prediction uncertainly, especially during the initial rounds of training. These "hard but informative' ID nodes are more likely to be mistaken for OOD nodes. As a result, filtering out OOD nodes may also unintentionally remove significant number of these valuable ID nodes. To mitigate this issue, we employ a C+1 1 classifier with weighted cross-entropy loss to strike balance between purity-ensuring that filtered nodes are truly oOD-and
as many useful ID nodes as possible.
Using the current labeled ID nodes, we can train the target ID classifier and generate node representations (see $3.4). Then we can obtain the representation of the unlabeled potential ID nodes from the ID classifier and the filter. Next, K-Medoids- based node selection method is applied to select the most informative nodes from the unlabeled potential ID nodes (sce $3.5p. After these informative nodes are annotated, the newly labeled ID nodes be used in the next. round of training for the larget ID classifier. Additionally, both the unknown OOD nodes and the labeled ID nodes are employed to retrain the GNN filter. After training the ID classifier with all the annotated nodes, any post-hoc OOD detection methods can be applied to the classifier to enhance its ability to recognize unseen classes (see $3.6 l. Fig. 2 illustrates the pipeline of the proposed framework L.EGOTLearn.
Algorithm 1 The LEGO-Learn algorithm
Require: Current filter fo and classifier 9o, current labeled set Vz, unknown set Vo and unlabeled set Vv, query batch size b
2:
Ensure: 0,, 0g. Vz, Vo and Vy for the next iteration
3: Process:
4:
# Filter training
3.3
Update By by minimizing Ly Eq. 4 using VL and Vo
Get the current potential unlabeled ID nodes DIP from the first C classes of prediction of unlabeled
Vo
# ID classifier training
3.4
8:
Update 8g by minimizing L in Eq. 7 using VL
9:
Get the embeddings H.P of nodes 17
10:
# K-Medoids based node selection
3.5
Compute pairwise distance based on embeddings H/P and get m medoids
11:
12:
Select nodes V from the m medoids with the highest uncertainty of prediction
13:
# Node annotation
14:
Query the selected nodes' labels and obtain Vř and Vo, where 1Vj 1/ |V- = b
15:
Update labeled, unknown, and unlabeled sets: V,, = Vy UV2 Vo = Vo U Vg and V/ Vú \ V
16:
Output: f,, 0g. VL, Vo and Ve for the next iteration
17: # OOD detection
3.6
18: Apply post-hoe OOD detection methods to the trained ID classifier for identifying OOD nodes.
3.3 Step 1: Removing 0OD Nodes via GNN Filter
Assume that we want train a C-class ID classifier. To achieve this, we extend the filter with an additional (C+1) 1) -t output to predict the unknown class. We want detect whether node belongs an unknown (C th class, possibly filtering out. many OOD nodes as possible before annotation. In this case, select nodes predicted to belong to the first C known classes for the next step, while excluding those identified as unknown. In this paper, we use a two-layer standard graph convolutional network (GCN) the OOD filter, and set the output dimension of the last layer as C 11
The output the OOD filter the representation matrix Zfättr E IR NxC+1) for nodes:
Z fitter GNN futte (A, X)
(3)

---

Published in Transactions on Machine Learning Research (05/2025)
Here, denote the OOD filter GNN However, sometimes the graph has many OOD nodes (i.e, the number of OOD nodes is much larger than the number of nodes of any ID class). To prevent filtering out too many useful ID nodes, we use the following weighted cross-entropy loss function:
Cj f
(()) (c) log 10C+1ly,
(C+1) log ((Ct))..
Here we introduce the weight wCC+1 to balance the purity and informativeness. While a larger w(C+1) can effectively filter out OOD nodes, may also unintentionally remove many highly informative ID nodes, which is undesirable for the later process. Conversely, a smaller w(C+1) preferable when OOD nodes dominate the training set, as prevents the excessive removal of valuable ID data.
With Aitter from the GNN filter, potential ID nodes and pass them to the node selection module to further select the most informative ones for labeling. The unlabeled set is denoted as VU, and the potential ID node set is represented as V.P.
select the nodes predicted to belong to the first C' classes
To specify the relationship between D and Vy more preciscly, we use the output of the OOD filter Bitter to identify the indices of the potential unlabeled ID nodes by selecting nodes whose predicted class labels fall within the known classes 1 to C:
ide { i Vul arg max yitter |i, s cc
(5)
Finally, the polential ID node set is defined as:
vi {ur idx)
(6)
3.4 Step 2:
Train ID Classifier with the Current ID Node Set
With the help of the OOD filter, we can train the target ID classifier with more labeled ID nodes while adhering to the label budget constraint. Assume that the current labelled node set is Vz, then the cross- entropy loss function for node classification over the labeled node set is defined as:
C
1
ΣΣ
Uie In Dic
VL
iEV.
Here, any GNN can be used as the ID classifier. For example, consider a two-layer GCN, The output of the first layer is as follows:
(AAD-XX(O0)
H
where Á = A D.: = E, I is the identity matrix, and ( is the weight matrix. This propagated node feature matrix H is used for subsequent clustering to select the most informative nodes. The final output the ID classifier is the representation matrix NXC for all nodes, which is:
z o - (
(9)
3.5 Step 3: K-Medoids Based Node Selection
Most node selection methods generally prioritize nodes with high prediction uncertainty or diverse repre- sentations for labeling. However, open-set noise distorts these metrics, as OOD nodes also exhibit high uncortainty and diversity due their lack of class-specific features or shared inductive biascs with ID ex- amples. Thanks our OOD filter, which removes many OOD nodes, we can focus on sclecting the most informative ones from the remaining potential ID nodes.

---

Published in Transactions on Machine Learning Research (05/2025)
After obtaining the indices idæ of the first C classes of unlabeled nodes predicted by the OOD filter and the propagated node feature matrix H from the ID classifier, we can derive the representation of potential unlabeled ID nodes:
H = H(izz.))
(10)
Then we compute the pairwise Fuclidean distance between nodes in the unlabeled potential ID node set:
d(e, uy) = [|, h2ll22
(11)
where hy and h; are the propagated node feature of node ve, by from the ID classifier. Similar prior studies (Liu et al. 2022), we then perform K-Medoids clustering on v where the centers selected for the candidate set must be actual nodes within the graph. The number of clusters is defined as After getting the medoids, we select the top b nodes with the highest uncertainty of prediction for annotation.
3.6 Post-hoc OOD Detection
Our goal is to develop powerful and robust ID classifier. To achieve this, the classifier must excel in two key aspects: first, it should provide accurate and high-confidence predictions for ID nodes; second, it should give low-confidence predictions for OOD nodes, ensuring effective diffcrentiation between the two. In this way even without a post-hoe method the ID classifier inherently possesses the ability to identify an OOD node.
Any post-hoc OOD detectors [Liang et al. 2017 Lee et al. 2018 Hendrycks Gimpel 2016 Yang et al., 2022 can be applied into our framework, since the ID) classifier is already capable of OOD detection (Wul et al. 2023 Vaze al. 2021), and good post-hoc method will strengthen its OOD detection ability. For each node 0;, it has final representation vector E RC from the output of ID classifier. Here simply use
the entropy of the predicted class distribution as OOD scores as in Macêdo et al. (2021); Ren et al. (0019)
The entropy of 2; calculated as follows:
6, 4= -=
Σ Biy (21g
(12)
The higher the entropy of zi, the more likely is that node v. belongs to an unknown class. The process of LEGO-Learn approach is summarized in Algorithm I
4
Experiments
Our experiments address the following research questions (RQ): RQI ($4.2): How effective is the proposed LEGO-Learn in ID class classification and node-level OOD detection in comparison to other leading basc- lines? RQ2 ($4.3 414): What nodes are important for open-set classification and how does the OOD filter influence the open-set learning performance? RQ3 ($4.5): How do different design modules in LEGO-Learn impact its effectiveness?
4.1
Experimental Setup
4.1.1 Datasets
We test LEGO-Learn four real-world datasets (Sen et al. 2008 Shehur et al. 2018 McAuley et al. 2015 that are widely used as benchmarks for node classification, i.c., Cora, Amazon AmazonComputer Computers, AmazonPhoo and LAsia. We preprocess datasets using the same pipeline as in Song & Wang (2022). For each dataset, we split all classes into ID and OOD sets, ensuring that the ID classes are relatively balanced in terms of node count. The OOD class and OOD ratio for the four datasets are shown in Appendix A Additionally, the number ID classes is set
minimun of three prevent overly simple classification tasks.
For each dataset with C ID classes, randomly select 10 C' of ID nodes and the number of OOD nodes as the validation set. We then randomly select 500 ID nodes and 500 OOD nodes as the test set. All remaining nodes constitute the 'unlabeled node pool'.
8

---

Published in Transactions on Machine Learning Research (05/2025)
Table 1: Performance comparison (best highlighted in bold) of different models on ID classification and OOD dctection tasks for Cora and Amazon-CS datascts. LEGO-Learn achieves the best across all baselines.
Cora
Amazon- CS
Model
Method
ID ACC
AUROC f
AUPR
FPR 4
ID ACC f
AUROC1
AUPR
FPR.
Random
0.8254
0.7742
0.7821
0.5190
0.7420
0.6686
0.6833
0.6604
Uncertainty
0.8112
0.7609
0.7585
0.5689
0.5920
0.5963
0.5952
0.7788
GCN-ENT
FeatProp
0.8530
0.7678
0.7696
0.5500
0.7346
0.7082
0.7121
0.6079
MITIGATE
0.8346
0.7551
0.7649
0.5511
0.6304
0.6666
0.6551
0.7039
Random
0.7287
0.7861
0.8165
0.4533
0.8048
0. 0373
0.7652
0.4849
Uncertainty
0.7884
0.7961
0.8173
0.4615
0.7428
0.7564
0.7853
0.4630
OODGAT
PeatProp
0.7772
0.8055
0.8233
0.4414
0.8044
0.8135
0.8276
0.3757
MITICATE
0.7998
0.7965
0.8175
0.4379
0.7950
0.8446
0.8361
0.3553
Random
0.8166
0.7390
0. 7585
0.7092
0.7490
0.6445
0.6437
0.7836
Uncertainty
0.7892
0.7226
0. 7.7166
0.6582
0.6656
0.6031
0,5982
0.7864
GNNSafe
FeatProp
0.8448
0.7473
0.7560
0.6640
0.7290
0.6820
0.6620
0.7034
MITIGATE
0.8410
0.7633
0.7728
0.6256
0.7088
0.6536
0,6390
0.7440
LEGO-Learn
0.8684
0.8804
0.8878
0.2869
0.8710
0.8533
0.8474
0.3216
Table 2: Performance comparison (best. highlighted in bold) of different models ID classification and
OOD detection tasks for smaazon-phote and LastFMAst datasets. LEGO-Learn achieves the best across all baselines.
Amazon-photo
LastFMAsia
Model
Method
ID ACC
AUROC
AUPR
FPR
ID ACC 1
AUROC 1
AUPR
FPR J
Random
0.9054
0.7970
0.7937
0,4883
0.6900
0.7990
0.8148
U.4702
Uncertainty
0.7784
0.7228
0.7158
0.6270
0.6170
0.7306
0.7366
0.6079
GCN-ENT
FeatProp
0.8950
0.8014
0.7983
0.4888
0.6518
0.7765
0.7788
0.5425
MITIGATE
0.8552
0.7818
0.7744
0.5234
0.6598
0.7719
0.7751
0.5347
Random
0.9306
0.8776
0,8891
0,2863
0.7616
0.8752
U.8917
0.3005
Uncertainty
0.9098
0.8173
0.8336
0.3978
0.6888
0.8307
0.8518
0.3963
OODGAT
FeatProp
0.9390
0.8823
0.8806
0,2955
0.7278
0.8662
0.8786
0.3406
MITIGATE
0.9264
0.8628
0.8693
0.3373
0.7088
0.8448
0.8645
0.3735
Random
8936
0.7664
0. A.7560
0.5869
0.6980
0. 0.7885
0.7998
0.5997
Uncertainty
0.8066
0.7077
0.6970
0.6873
0.6477
0.6962
0.6905
0.6957
GNNSafe
FeatProp
0.8794
0.7550
0.7297
0.5931
0.6652
0.7318
0.7240
0.6327
MITIGATE
0.8672
0.7695
0.7542
0.5944
0.6662
0.7113
0.7046
0.6868
LEGO-Learn
0.9648
0.9257
0.9279
0.1856
0.7818
0.8852
0.9035
0.2627
4.1.2 Basclines
We compare LEGO-Learn with two types of baselines: (1) graph OOD detection methods, including GCN- ENT (Kipf& & Welling 2016), OODGAT (Song & Wang 2022), GNNSafe (Wu et al. 2023) (2) node selection methods for node classification, including random, uncertainty (Luo et al. 2013), FeatProp (Wu et al. 2019 MITIGATE (Chang et al. 2024). However, since there are no current mothods specifically designed for our setting, we need to modily the baselines to better fit our context. In general, we use the following baselines:
GON-ENT-random, GCN-ENT-uncortaing CCN-ENT-FeatPPen GON-ENT-MITIGATE we use GCN as the backbone of ID classifier and node embeddings entropy as post-hoc OOD detection method. We use four different selection methods to select training nodes to label: (1) randomly select nodes from the unlabeled node pool (2) select the nodes with largest uncortainty of predictions (3) use graph active learning method FeatProp (Wu et al.) (2019) select nodes (4) use the K-Medoids based method with
masked aggregation mechanism proposed in Chang et al. (024 to select nodes.

---

Published in Transactions on Machine Learning Research (05/2025)
OODGAT-random, OODGAT-mmertainyy OODGAT-Feat OODGAT-MITICATE OODGAT as the ID classification and OOD detection backbone and combine it with the previous four selection strategies.
use
GNNSafe-random GNNSale-uncerraainty, Frosape-Fea.Prop, GNNSale-MITIGATE similarly, we use GNNSafe as the graph open-set classification backbone, combining it with the previous four selection strategics.
For our model LEGO-Learn, two standard GCN layers as the OOD filter. It is important to note that we rely solely on the ID classifier for OOD detection, as our goal is to assess its ability to make accurate predictions for ID nodes while effectively identifying OOD nodes.
two OODGAT layers ID classifier and entropy OOD score. We use
4.1.3 Evaluation Metrics
For the ID classification task, we use classification accuracy (ID) ACC) as the evaluation metric. For the OOD detection task, we employ three commonly used metrics from the OOD detection literature (Song & Wang 2022|: the area under the ROC curve (AUROC), the precision-recall curve (AUPR), and the false positive rate when the true positive rate reaches 80% (FPR&80). In all experiments, OOD nodes are considered positive cases. Details about these metrics are provided Appendix B
4.1.4 Implementation Details
The initial label budget for all datasets is 5 nodes per ID class. The total label budget is 15 nodes per ID class. For each round of selection, we select x C of nodes from the unlabeled pool and annotate the selected nodes for all methods. It should be noted that although the total number of final labeled nodes is 15 C, many of these labeled nodes may be OOD nodes and therefore cannot be used to train the ID classifier.
For all K-Medoids based selection methods, the number of clusters is set to 48. In each round of node selection, we select 2 x C' of nodes with the highest uncertainty of prediction from the 48 medoids. All GCNs have 2 layers with hidden dimensions of 32. The weight for the unknown class in the filter's loss function is chosen from f0.001, 0.1, 0.2] based on the results of the validation set. All models use a learning rate of 0.01 and a dropout probability of 0.5. We average all results across 10 different random seeds.
4.2 Main Results
We present the performance comparison of different models on ID classification and OOD detection tasks for four datasets in Tables and From the results, we make the following observations:
1. LEGO-Learn outperforms all baselines: Across all datasets, our proposed method LEGO-Learn consistently outperforms all bascline models in both ID classification accuracy and OOD detection metrics. Specifically, four datasets, for ID classification, the best improvement is observed on Amazon-photo dataset, where ID accuracy increases from 80.48% (achieved by the best baseline OODGAT with random selection) to 87.10%, 6.62% improvement. Moreover, LEGO-Learn demonstrates remarkable improvement in OOD detection metrics, achieving higher AUROC and AUPR scores while maintaining a lower @P across all datasets. The best improvement seen on the Cora dataset, where the OOD) AUROC increases from 80.55% (achieved by the best baseline, OODGAT with FeatProp) to 88.04%, 7.49% improvement.
2. Effectiveness of K-Medoids clustering: The baselines incorporating FeatProp and MITIGATE, which use siitering--aseel node selection methods, generally perform better than those using uncortainty-baso selection. This suggests that clustering helps select more informative nodes. However, they still fall short compared to L.GGO-Lear, highlighting the effectiveness of our integrated approach that combines OOD filtering with clustering.
3. Limitations of uncertainty-based selection: Basclines using uncertainty-based node selection often perform worse than those using random selection because they tend to select nodes with high prediction
10

---

Published in Transactions on Machine Learning Research (05/2025)
uncertainty, which are often OOD nodes in open-set setting, leading to lower precision and negatively affecting the performance of the ID classifier.
4. OODGAT layer can enhance OOD detection performance more than ID classification ac- curacy: Using the same node selection method, models employing OODGAT layers as the backbone for the ID classifier generally demonstrate significantly better OOD detection performance compared to those with GCN layers. This improvement arises because OODGAT layers are specifically designed for node-level OOD detection, effectively separating ID nodes from OOD nodes during feature propagation. However, due to having more parameters than standard GCN layers, OODGAT layers may struggle to achieve high ID classification accuracy when the number of labeled nodes available for training is limited.
4.3 What Nodes Are Important for Graph Open-set Classification?
We calculate the final precision of ID nodes for various selection methods, as defined Ning et al. (2022) Precision here refers the ratio of true ID nodes to the total number of selected and annotated nodes. The baseline results are averaged across three different graph open-set learning models. As shown in Table B LEGO-Learn achieves the highest precision across all datasets. This demonstrates our method can effectively filter out OOD nodes before node selection and annotation. Interestingly, most node selection methods achieve lower precision compared with random selection. That is because current selection methods tend to select nodes with higher uncertainty in predictions or greater diverse in representations, while nodes with higher uncertainty are more likely to be OOD nodes.
Table 3: Precision values of ID nodes.
Amazon- CS
Amazon- F-stFM-
Model
Method
Cora
Photo
Asia
random
0.4783
0.4933
0.4853
0.4600
uncertainty
0.3500
0.4053
0.2960
0.2874
GCN-ENT
FeatProp
0.3383
0.4067
0.2920
0.2622
MITIGATE
0.3333
0.4080
0.2747
0.2852
random
0.4783
0.4933
0.4853
0,4600
uncertainty
0.3400
0.2973
0.3093
0.2370
OODGAT
FeatProp
0.3350
0.3427
0.2600
0.2444
MITIGATE
0.3433
0.3040
0.2600
0.2274
random
0.4783
0.4933
0.4853
0.4600
uncertainty
0.3467
0.4560
0.3160
0.3274
GNNSafe
FeatProp 0.3650
0.4240
0.3013
0.2889
MITIGATE
0.3667
0.4346
0.2893
0.2889
LEGO-Learn
0.5733
0.6333
0.6173
0.6978
Although current node selection methods cannot select a high proportion of ID nodes from the unlabeled node pool, they can achieve compelitive performance compared to random selection, which has higher precision. This suggests that highly informative nodes are very useful for training the TD classifier. Our method can not only select informative nodes but can also filter out many potential OOD nodes, enabling it to achieve both high precision in ID node selection and high classification accuracy.
4.4 A Strong Filter Is Not All You Need
In general, if the GNN filter can remove more OOD nodes, the precision of ID nodes will improve. As result, the ID classifier will be better trained with more ID nodes and perform more effectively. However, this is not always the case. While a filter with a large (C++)) (strong filter) can filter out more OOD nodes, it does not always lead improved performance of the ID classifier. We compare the performance of our method using a strong filter (w(C+1) 1) and a normal filter (w(C+1) = 0.1) on LastFMAsh dataset. The results shown in Table
11

---

Published in Transactions on Machine Learning Research (05/2025)
Table 4: Comparison of strong filter and normal filter performance on LastaMAsia. improve ID classification precision while decreasing the accuracy.
The strong filter may
ID ACCT f
AUROCT f AUPR f FPR. +
Precision 1
Strong Filter
0.7602
0.8818
0.9010
0.2636
0.7444
Normal Filter
0.7810
0.8710
0.8881
0.3036
0.6385
As we can see from the results, the strong filter significantly increases the precision of TD nodes (from 0.6385 to 0.7444) but does not enhance ID classification performance (a drop from 0.7810 0.7602) compared the normal filter with a smaller w(C+)) This indicates that while strong filter removes out more OOD nodes before annotalion, it also filters out many useful ID nodes. As a result, it becomes impossible to select these valuable nodes in later stages. Often, these informative ID) nodes are more similar to OOD nodes due to their high prediction uncertainty. More importantly, this demonstrates that highly informative nodes are crucial for training the ID classifier. Sometimes, using fewer informative nodes more effective for training the ID classifier than relying on a larger number of simpler nodes. In summary, this suggests that we should use the weight w(C+1) balance purity and informativeness. We leave the design of more powerful filter, capable of removing most OOD nodes while relaining the majority of informative ID nodes, for future work.
4.5 Ablation Study
To understand the contribution of each component in our proposed framework LEGO-Learn, we conduct an ablation study on Cora dataset by systematically removing altering specific modules and observing the impact on the performance. Table presents the results of this study across four key variants of our model:
Table 5: Ablation study Cora. LEGO-Learn achieves the best performance.
ID ACC +
AUROC f
AUPR
FPR
LEGO-Learn-ATT
0.8644
0.8285
0.8299
0.4220
LEGO-Learn-Filter
0.7998
0.7965
0.8175
0.4579
LEGO-Learn-Cluster
0.7764
0.7689
0.8023
0.4683
LEGO-Learn
0.8684
0.8804
0.8878
0.2869
LEGO-Learn-TT:: The OODGAT layer in the GNN-based ID classifier for LEGO-Learn is replaced with GCN-ENT.
The backbone uses K-Medoids clustering for node selection but omits the OOD filtering process. All unlabeled nodes in the original graph used for clustering, and the medoids with highest uncertainty are selected for annotation. The annotated ID nodes are used to train the ID classifier.
LEGO-Learn-Filter
LEGO-Learn- -oo-Leeen--Clueer: The node clustering part removed. The backbone employs the GNN-based OOD filter without additional clustering or selection steps. Instead, after filtering, nodes are randomly selected for annotation to train the ID classifier.
The performance of L.EGO-Learn (the complete framework) significantly outperforms both LEGO-Learn-Filee and L.GO-Learn-Chiee Chustr,, demon- strating the necessity of each component. The node selection module better selects the most informative nodes, allowing the ID classifier to be well-trained. Additionally, the filter is crucial because it removes most of the OOD nodes, thereby improving the purity of ID nodes.
LEGO-Learn vs. ABGGO-Laan-PPiterLEEEGLLLeee
Impact of OODGAT Layer (LEGO-Learn-ATTT) Replacing the original OODGAT layer with a stan- dard GCN-ENT model (LEGO-Leam-ATT)) results a noticeable drop both AUROC (from 0.8804 to 0.8285) and AUPR (from 0.8878 to 0.8299). The GNN-based OODGAT layer clearly enhances the per- formance of the model in detecting OOD nodes compared to GCN layers, suggesting that the attention mechanism used for separating ID nodes and OOD nodes can lead to better OOD detection.
12

---

Published in Transactions on Machine Learning Research (05/2025)
5 Conclusion and Future Directions
In this paper, we addressed the problem of label-efficient graph open-set learning for the first time and in- troduced LEGO-Learn (Label-Efficient Graph Open-set Learning), a novel framework designed to tackle the challenges open-set node classification on graphs under strict label budget constraints. LEGO-Learn in- tegrates a GNN-basod OOD filter with a K-Medoids-basee node selection strategy, enhanced by a weighted cross-entropy loss to balance the retention of informative ID nodes while filtering out OOD nodes. Our extensive experiments four real-world datasets demonstrate that LEGO-Learn consistently outperforms state-of-the-art methods in both ID classification accuracy and OOD detection under label budget con- straints. Ablation studies further highlight the importance of cach component in our framework. Future work includes scaling LEGO-Learn to accommodate larger and more complex graphs, developing improved node selection strategies for OOD detection, optimizing the trade-off between purity and informativeness, exploring the performance of graph open-set learning under varying proportions of OOD nodes, and modeling different annotators' accuracy when labeling different types of nodes.
Acknowledgments
This work was partially supported by the National Science Foundation under Award No. 2428039, No. 2346158, and No. 2106758. Any opinions, findings, and conclusions recommendations expressed are those of the authors and do not necossarily reflect the views of the National Science Foundation.
References
Yunsheng Bai, Ken Gu, Yizhou Sun, and Wei Wang. Bi-level graph neural networks for drug-drug interaction prediction. orXiv preprinl Xrxvv:2006.1 1 14002, 2020.
Hongyun Cai, Vincent W Zheng, and Kevin Chen-Chuan Chang, Active learning for graph embedding. arXiv preprint arxio: 105. 05085, 2017.
Wenjing Chang, Kay Liu, Kaize Ding, Philip S Yu, and Jianjun Yu. Multitask active learning for graph anomaly detection. aixiv preprinl NNN:2401.13210 2024.
Danicl Cummings and Marcel Nassar. Structured citation trend prediction using graph neural networks In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3897-3901. IEFE, 2020.
Hao Dong, Yue Zhao, Eleni Chatzi, and Olga Fink. Multiood: Scaling out-of-distribution detection for multiple modalities. Xixiv preprint or arXin:2405. 17419 2024.
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In The world wide web conference, pp. 417-426, 2019.
Zhen Fang, Yixuan Li, Jie Lu, Jiahua Dong, Bo Han, and Feng Liu. Is ont-of-ddistriiutiin detection learnable? Advances in Neural Information Processing Systems, 35:37199-3707 2022.
Jun Gao, Jiazun Chen, Zhao Li, and Zhang. Ics-gnn: lightweight interactive community search via graph neural network. Proceedings of the VLDB Endowment, 14(6):1006-1018, 2021.
Yuxin Guo, Cheng Yang, Yuluo Chen, Jixi Liu, Chuan Shi, and Junping Du A data-centric framework endow graph neural networks with distiriiistii detection ability. In Proceedings of the 29th ACM SIGKDD Conference Knowledge Discovery ond Data Mining, pp. 638-648, 2023.
Peng Han, Zhiming Chen, Fei Jiang, and Jiaxin Si. Active learning for open-set annotation using contrastive query strategy. In International Conference on Newral Information Processing, pp. 19 31. Springer, 2023.
Nan Hao, Yuangang Li, Kecheng Liu, Songtao Liu, Yingzhou Lu, Bohao Xu, Chenhao Li, Jintai Chen, Ling Yue, Tianfan Fu, et al. Artificial intellgence--ideed digital twin design: A systematic review. Preprints, 2024.
13

---

Published in Transactions on Machine Learning Research (05/2025)
Dan Hendryeks and Kevin Gimpel. A baseline for detecting misclassified and out-of-distribution examples 2016.
in neural networks. arxiv preprint
Jachyuk Heo and Pilsung Kang. Avoid wasted annotation costs in open-set active learning with pre-trained vision-langnage model. arXiv preprint vrXio2240804991, 2024.
Thomas N Kipl and Max Welling, Semi-supervised classification with graph convolutional networks. arxiv
preprint 1 609. 02907, 2016.
Sofia Tra Ktena, Sarah Parisot, Enzo Ferrante, Martin Rajchl, Matthew Lee, Ben Glocker, and Daniel Rucekert. Distance metric learning using graph convolutional networks: Application to functional brain networks. In Medical Image Compuling and Computer Assisted Intervention- MICCAI 2017: 20th In- ternational Conference, Quebec City, QC, Canada, September 11-13, 2017, Proceedings, Part I 20, pp. 469-477. Springer, 2017.
Kimin Lee, Kibok Lee, Honglak Lee, and Jinwoo Shin. A simple unified framework for detecting out- of-distribution samples and adversarial attacks. Advances in neural information processing systems, 31, 2018.
Shiyu Liang, Yixuan Li, and Rayadurgam Srikant. Enhancing the reliability of out-of-distribution imago detection in neural networks. Xiviv preprint arxiv: 706.02690, 2017.
Juncheng Liu, Yiwei Wang, Bryan Hooi, Renchi Yang, and Xiaokui Xiao. Lscale: latent space clustering- based active learning for node classification. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 55-70 70. Springer, 2022.
Yixin Liu, Kaize Ding, Huan Liu, and Shirui Pan. Good-d: On unsupervised graph out-of-distribution detection. In Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining, pp. 339 347, 2023.
Yiyue Liu, Ke Jin, Jian Lai, and Lixin Zhang. Towards open set graph classification. In Proceedings of the 2021.
30th ACM International Conference on Information & Knowledge: Management, pp.
Wenjie Luo, Alex Schwing, and Raquel Urtasun. Latent structured active learning. Advonces in newral information processing systems, 26, 2013.
David Macêdo, Tsang Ing Ren, Cleber Zanchettin, Adriano LI Oliveira, and Teresa Ludermir. Entropic ditt---disttiiutioon detection. In 2021 international joint conference on neural networks (IJCNN), pp.
1 IEEE, 2021.
Ruiyu Mao, Ouyang Xu, and Yunhui Guo. Incousistency-baseed data-centric active open-set annotation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 4180 4188, 2024.
Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton Van Den Hengel. Image-based recommen- dations on styles and substitutes. In Proceedings of the 38th international ACM SIGIR conference on research and development in information retrieval, pp. 43-17 02,552211 2015.
Kun-Peng Ning, Xun Zhao, Yu Li, and Sheng-Jun Huang. Active learning for open-set annotation. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition, pp. 41-49, 2022.
Dongmin Park, Yooju Shin, Jihwan Bang, Youngjun Lee, Hwanjun Song, and Jae-Gil Lee. Meta-query-net: Resolving purity- senttty-nformativennee dilemma in open-set active learning. Advances in Newral Information Processing Systems, 35:31416-31429, 2022.
Yuehan Qin, Yichi Zhang, Yi Nian, Xueying Ding, and Yue Zhao. Metaood: Automatic selection of ood detection models. arXiv preprint ar arX:::240000807, 2024.
Jie Ren, Peter Liu, Emily Fertig, Jasper Snock, Ryan Poplin, Mark Depristo, Joshua Dillon, and Balaji Lakshminarayanan Likelihood ratios for out-of-distribution detection. Advances in neural information processing systems, 32, 2019.
14

---

Published in Transactions on Machine Learning Research (05/2025)
Bardia Safaci, VS Vibashan, Celso M de Melo, and Vishal M Patel. Entropic open-set active learning. In Proceedings of the AAAT Conference Artificial Intelligence, volume 38, pp. 4686-4694, 2024.
Prithviraj Sen, Galileo Namala, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collec- tive classification in network data. Al magazine, 29(3): 93, 2008.
Burr Settles. Active learning literature survey. 2009,
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint 1111:18811008666 2018.
Yu Song and Donglin Wang. Learning on graphs with out-of-distribation nodes. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1635-1645, 2022.
Ying-Peng Tang, Xiu-Shen Wei, Borui Zhao, and Sheng-Jun Huang. Qbox: Partial transfer learning with active querying for object delection. IEEE brunsactions on neural nelworks and learning systems, 34(6); 3058-3070, 2021.
Sagar Vaze, Kai Han, Andrea Vedaldi, and Andrew Zisserman. Open-set recognition: A good closed-set classifier is all you need? 2021.
Man Wu, Shirui Pan, and Xingquan Zhu. Openwgl: Open-world graph learning. In 2020 JEEE international conference on data mining (iedm), pp. 681 690. IEEE, 2020.
Qitian Wu, Yiting Chen, Chenxiao Yang, and Junchi Yan. tnergy-based out-of-distribution detection for graph neural networks. arXiv preprinl ar Xiv:2300 02914, 2023.
Yuexin Wu, Yichong Xu, Aarti Singh, Yiming Yang, and Artur Dubrawski. Active learning for graph neural networks via node feature propagation. arXiv preprint arXiv: 07567, 2019.
Zhiping Xiao, Weiping Song, Haoyan Xu, Zhicheng Ren, and Yizhou Sun. Timme: Twitter ideology-detection via multi-task multi-relational embedding. In Proceedings of the 26th ACM SIGKDD international con- ference on knowledge discovery & data mining, pp. 2258 2268, 2020.
Haoyan Xu, Runjian Chen, Yueyang Wang, Ziheng Duan, and Jie Feng. Cosimgnn: towards large-scale graph similarity computation. arXiv preprint arXiv:2005.071 07115, 2020.
Haoyan Xu, Ziheng Duan, Yueyang Wang, Jie Feng, Runjian Chen, Qianru Zhang, and Zhongbin Xu. Graph partitioning and graph neural network based hierarchical graph matching for graph similarity computation. Neurocomputing, 439:348-362 2021.
Hui Xu, Liyao Xiang, Junjie Ou, Yuting Weng, Xinbing Wang, and Chenghu Zhou. Open-world graph active learning for node classification. ACM Transactions on Knowledge Discovery from Data 18(2):1-22 20, 2023.
Zizheng Yan, Delian Ruan, Yushuang Wu, Junshi Huang, Zhenhua Chai, Xiaoguang Han, Shuguang Cui, and Guanbin Li. Contrastive open-set active learning based sample selection for image classification. IEEE Transactions on Image Processing, 2024.
Jingkang Yang, Pengyun Wang, Dejian Zou, Zitang Zhou, Kınyuan Ding, Wenxuan Peng, Haoqi Wang. Guangyao Chen, Bo Li, Yiyou Sun, al. Openood: Benchmarking generalized out-of-distribbtiio detec- tion. Advances in Neural Information Processing Systems, 35:32598 32611, 2022.
Jingkang Yang, Kaiyang Zhou, Yixuan Li, and Ziwei Liu. Generalized out-of-distribution detection: A
survey. International Journal of Computer Vision, pp. 1-28, 2024a.
Yang Yang, Yuxuan Zhang, Xin Song, and Yi Xu. Not all out-o--dist data are harmful to open-set active learning. Advances in Neural Information Processing Systems, 36, 2024b.
Xiang Zhang, Lina Yang, Jingjing Li, and Xin-Shun Zhang. Open-world learning and application to product classification. World Wide Web, 24(5) 2021a.
15

---

Published in Transactions on Machine Learning Research (05/2025)
Xiao-Meng Zhang, Li Liang, Lin Liu, and Ming-Jing Tang. Graph neural networks and their current appli- cations in bioinformatios. Fronliers in genelics, 12:690049, 2021b.
Xujiang Zhao, Feng Chen, Shu Hu, and Jin-Hee Cho. Uncertainty aware semi-supervised learning on graph data. Advances in Neural Information Processing Systems, 13:12227-12886, 2020.
16

---

Published in Transactions on Machine Learning Research (05/2025)
A Datasets Information
Cora is a citation network where each node represents published paper, and each edge indicates a citation between papers. The objective is to predict the topic of each paper as its label class. This dataset includes 2708 nodes, 10556 edges, 1433 features, and distinct classes.
Amazon-CS is a product co-purchasing network from the Amazon platform, where cach node represents product, and each edge indicates that two connected products are frequently bought together. The label of each node corresponds to the product's category. This dataset contains 13752 nodes, 491722 edges, 767 features, and 10 classes.
Amazon-Phous is a product co-purchasing network on Amazon, where each node represents a product and each edge indicates that two connected products are frequently bought together. The label of each node corresponds to the product's category. This dataset includes 7650 nodes, 238162 edges, 745 features, and 8 classes.
The LastiMMsia dataset consists of 7624 users from the LastFM music platform, who are classified into one of 18 regions based on their listening habits. The graph is built on the basis of users' friend connections, containing 55612 edges. Each user is described by a feature vector 128 attributes representing the artists they listen to. The task to classify users into one of the regions based on their musical preferences and social connections.
Table 6: OOD class and OOD ratio for different datasets
Datasct
OOD class
OOD ratio
Cora
[0, 1, 3]
0.51
Amazon-Compun
0, 3, 4, 5, 9]
0.49
Amazon-Photte
[1, 6, 7
0.52
MMsia
2, 3, 4, 5, 9, 10, 12, 17
0.53
Table 7: Statistics for main datasets
Dataset
#Nodes
# #Edges
# FFeatures # Classes
Cora
2708
10556
1433
Tmazzon-Comput
13752
491722
767
10
Amazon-Photo
7650
238162
745
8
Last.
7624
55612
128
18
B Descriptions of Evaluation Metrics
AUROC stands for "Area. Under the Receiver Operating Characteristic Curve." is a performance metric used in binary classification tasks evaluate how well model distinguishes between positive and negative classes. A higher AUROC value indicates better model performance in distinguishing between the two classes.
AUPR stands for the area under the precision-recall (PR) curve, similar to AUC, but it provides a more effective performance evaluation for imbalanced data.
FPR80 refers the false positive rate (FPR) when the true positive rate (TPR) reaches 80%. It used measure the likelihood that an OOD example is incorrectly classified as ID when most ID samples are correctly identified. A lower FPRS0 value indicates better detection performance.
17

---

Published in Transactions on Machine Learning Research (05/2025)
C Different Label Budgets
Here, we present the results for different label budgets on Lasta'MAsia. As shown in Table 8 and Table LEGO-Learn achieves better performance across various label budgets.
Table 8: 20 x C label budget
ID ACC 1 AUROC f
AUPR
FPR80
0.6844 LEGO-LLarr
GCN-ENT
0.7863 0.9057
0.7923
0.5158
0.7826
0.9179
0.2287
Table 9: 10 X C label budget
ID ACC f
AUROC f
AUPR +
FPR80 +
0.6248 LEGO-Learn
GCN-ENT
0.7527 0.8624
0.7518
0.5903
0.7512
0.8812
0.3116
D Standard Deviation Results
We assess the model's stability by presenting the standard deviation values of LEGO-Learn and GCN-ENT for two datasets in Table 10 As shown in the table, our method and the baseline generally exhibit similar variance values.
Table 10: Our method and bascline generally have similar standard deviation values.
ID ACC
AUROC
AUPR f
FPRS0 4
Cora (LEGO-Learn)
6.54%
1.40%
0.30%
13.63%
LastFMAsia (LEGO-Learn)
3.41%
3.13%
2.43%
10.24%
Cora (GCN-ENT) LastFMAsis (GCN-ENT) 4.25%
6.31%
5.47%
5.64%
14.93%
2.90%
3.32%
12.63%
E OOD Detection Under Different Category Divisions
To demonstrate generalizability, we modify the OOD divisions of Cora (where the ID classes are 1, 2, 3, and 4) and LastFMAsia (where the ID classes range from 0 to 8). The results of LEGO-Learn and GCN-ENT, using the same K-Medoids method, are presented in Table 11. From these results, we observe that LEGO-Learn consistently outperforms the baseline, regardless of the division.
F Parameter Sensitivity Analysis
The ID classification accuracy of LEGO-LLarr under different w values in the filter for LastFMAsia is presented Table
G OOD Scores
We visualize the OOD scores predicted by LEGO-Learn for ID and OOD nodes the test set. As shown the Fig. G the scores for ID and OOD inputs are well-separated. This proves that our method effectively identifies OOD nodes and accurately predicts ID nodes.
18

---

Published in Transactions on Machine Learning Research (05/2025)
Table 11: The results of LEGO-Learn and GCN-ENT for another OOD division of Cora and MMAsa.
Model
ID ACC
AUROC
AUPR
FPR80
GCN-ENT (Cora)
0.8249
0.8290
0.8216
0.4550
LEGO-Learn (Cora)
0.8376
0.9210
0.9244
0.2086
GCN-ENT (LastFMAsia)
0.7294
0.7575
0.7473
0.5850
LEGO-Learn
0.8024
0.8684
0.8714
0.3427
Table 12: classification accuracy of our method under different w values for LastFMAsia
0.01
0.1
0.2
0.3
0.4
1
0.7624
0.7800
0.7770
0.7692
0.7650
0.7602
LEGO-Leam
I0 Nodes OOD Modes
Density
06
02
04
0.6
0.8
1.0
12
14
000 Score
Figure 3: OOD scores histogram
19


Reviews:
[{"review_id": "k5WTSInwPY", "reviewer": "Reviewer_598D", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n1. The paper tackles a practically important and underexplored problem—label-efficient graph open-set node classification—which is highly relevant to real-world scenarios where annotation costs are prohibitive, and OOD classes commonly exist.\n\n2. The implementation is natural for its target: by combining a GNN-based OOD filter with a K-Medoids-based node selection strategy, the paper proposes a complete and principled pipeline that handles both selective annotation and open-set filtering, ensuring that both classification accuracy and OOD detection performance are addressed simultaneously.\n\nWeaknesses:\n1. The paper does not provide experiments that systematically vary the ratio between unseen (OOD) classes and known (ID) classes to measure how the method performs under different levels of “openness.” In practice, the degree of open-world-ness can significantly impact both ID classification and OOD detection performance. Without such experiments, it is difficult to assess how well LEGO-Learn manages the trade-off between filtering OOD nodes and retaining informative ID nodes as this ratio shifts.\n\n2. The paper could benefit from evaluating the method in fully closed-world (all test nodes are ID) and fully open-world (all test nodes are OOD) settings. These extremes could provide meaningful anchors for comparison against classical node classification methods (in closed-world) and classical OOD detection methods (in fully open-world). This would help clarify LEGO-Learn’s relative performance in scenarios where specialized baselines may excel.\n\n3. Given that the paper emphasizes label-efficiency, it is surprising that no experiments systematically vary the available annotation ratio. Varying the amount of labeled data (e.g., from very scarce labels to moderate label availability) would help demonstrate LEGO-Learn’s robustness under different supervision levels and better support its label-efficient claims.\n\n4. The framework likely involves a trade-off between ID classification accuracy and OOD detection performance as openness increases, and potentially another trade-off between model performance and label availability. However, these trade-offs are not discussed or visualized in the paper (correct me if I missed). A systematic exploration of these dynamics could make the contributions more convincing and generalizable.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper is (very likely) the first attempt to address the important but under-explored problem of label-efficient graph open set learning (GOL). The authors propose LEGO-Learn, a two-stage framework that combines a GNN-based filter for OOD removal with a K-Medoids clustering strategy for selecting diverse and informative ID nodes under a strict label budget.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. The first recommended change is adding openness ratio experiments. I strongly recommend the authors conduct experiments that vary the ratio between OOD and ID classes in the test set (i.e., degree of “open-world-ness”). This will help assess how LEGO-Learn performs across different levels of openness, from low-OOD to highly OOD-dominated scenarios. Without this, it is hard to fully validate the framework’s generalizability to varying real-world open-set conditions.\n\n2. To fully contextualize LEGO-Learn’s performance, please include experiments at the two boundary cases: (a) Fully closed-world (all test nodes are ID) to compare against classical node classification methods. (b) Fully open-world (all test nodes are OOD) to compare against classical OOD detection methods.\n\nThen, the progressive levels between (a) and (b) would also help position LEGO-Learn relative to both standard GNN classifiers and graph OOD baselines.\n\n3. Since the paper positions LEGO-Learn as a label-efficient solution, I recommend providing experiments that vary the amount of available annotated data (e.g., from 1% to 10% labeled nodes). This will better showcase the method’s performance under different levels of supervision.\n\n4. While optional, it would significantly strengthen the paper to visualize or discuss the trade-offs LEGO-Learn faces as the openness ratio or label budget changes. This could help practitioners understand when and how to deploy LEGO-Learn based on resource availability and the expected level of open-worldness in their graphs.", "broader_impact_concerns": "not applicable", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "DubWuu2YrJ", "reviewer": "Reviewer_RfXH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- The paper tackles a problem in graph-based learning, offering a novel solution that integrates OOD filtering and label-efficient node selection.\n- Extensive experiments on four datasets show that LEGO-Learn outperforms existing methods in both ID classification and OOD detection.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces LEGO-Learn, a framework for label-efficient graph open-set learning (GOL). The proposed method addresses the challenge of training graph-based models to recognize unseen classes while minimizing labeling costs. LEGO-Learn employs a GNN-based filter to identify and exclude potential out-of-distribution (OOD) nodes and selects highly informative in-distribution (ID) nodes for labeling using the K-Medoids algorithm. The framework is evaluated on four real-world datasets, demonstrating significant improvements in ID classification accuracy and OOD detection compared to existing methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- What is the real-world significance of this new setting?\n- Why can GNNs filter out most of the OOD nodes? Is there any theoretical guarantee for this? As is well known, GNNs tend to suffer from over-smoothing. I have concerns about their ability to identify outliers.\n- As is well known, a significant portion of node anomalies stems from the influence of their topological structure. Apart from using GNNs, the paper does not incorporate any additional graph structural information. Can this approach accurately identify anomalous nodes?\n- Is there any visualization to demonstrate that the authors have indeed identified anomalous nodes and accurately predicted in-distribution (ID) nodes?\n- Can the authors analyze the effectiveness of their method from multiple perspectives, such as complexity analysis, efficiency comparison, sensitivity analysis, and case studies, to further enrich their experiments?", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "7uMyZNdSvf", "reviewer": "Reviewer_YY2z", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**: This paper seems solid to me. I was able to understand the main points and ideas fairly quickly. The experimental evaluation seems fairly thorough with new baselines which it outperforms on 4 datasets. There is a nice ablation study. \n\n**Weaknesses**: \n- At points, the writing can be a bit sharper, clearer and to the point. \n- The experiments lack repeated runs\n- The experimental setup is not as clearly compelling as the given example", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors consider the problem of node graph classification, where we only care about (and have data for) a subset of the classes. Can we detect which of the nodes are from a class for which we have no data? This is the problem of open-set learning. The authors combine this setting with active learning to identify what nodes to label (or mark OOD). \nTheir solution trains a GNN that identifies (potential) OOD (outside class) nodes, and uses a K-medoids clustering algorithm to select datapoints for active learning. Their method greatly outperforms the baselines.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- I don't think the authors perform repeated runs of the method on the algorithm. The authors use 4 digits of standard deviation, which does not mean much without repeated runs. Two digits significance should be sufficient.\n- Section 3.1: I found the part below equation 1 hard to understand, but it is quite vital. May be worth spending more words on the different sets introduced here, and what is meant with 'selecting' subsets of nodes and what the annotators do. (Eg what is the goal of this selection procedure). \n- Section 3.3: My understanding is that the authors implemented the OOD filter by training a C+1-label classifier (where the last class corresponds to OOD). Why not use a binary classifier for in vs out of distribution?\n- Section 3.6: I was confused that the ID classifier is used for OOD detection post-hoc. Why not the OOD filter?\n- Section 4.1.1: Is the split between ID and OOD classes in some way meaningful? Or just random? It would be nice for the story of the paper if there's a setup like Figure 1 / page 2 where there is a clear distinction. \n- Figure 3 is pretty confusing to me design-wise. For the same space, a table should just work? And the use of averaging of the other methods is also confusing to me. \n- Section 4.3: Table 8 is referenced but I think it should be table 7.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers agree that the paper should be accepted. I think that the revisions cleared the concerns raised by reviewers, and that the paper is interesting and valuable to the community.
Decision: Accept (poster)