# LEGO-Learn: Label-Efficient Graph Open-Set Learning

arXiv: https://arxiv.org/abs/2410.16386 · HTML: https://mlsanity.com/paper/2410.16386/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 54 references that are in the map.
- First posted on arXiv 21 Oct 2024.

## Builds on (most cited first, 30 of 36)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [A Baseline for Detecting Misclassified and Out-of-Distribution Examples in Neural Networks](https://mlsanity.com/paper/1610.02136/) (2016)
- [A Simple Unified Framework for Detecting Out-of-Distribution Samples and Adversarial Attacks](https://mlsanity.com/paper/1807.03888/) (2018)
- [Enhancing The Reliability of Out-of-distribution Image Detection in Neural Networks](https://mlsanity.com/paper/1706.02690/) (2017)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Generalized Out-of-Distribution Detection: A Survey](https://mlsanity.com/paper/2110.11334/) (2021)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [Image-based Recommendations on Styles and Substitutes](https://mlsanity.com/paper/1506.04757/) (2015)
- [Likelihood Ratios for Out-of-Distribution Detection](https://mlsanity.com/paper/1906.02845/) (2019)
- [Open-Set Recognition: a Good Closed-Set Classifier is All You Need?](https://mlsanity.com/paper/2110.06207/) (2021)
- [OpenOOD: Benchmarking Generalized Out-of-Distribution Detection](https://mlsanity.com/paper/2210.07242/) (2022)
- [Is Out-of-Distribution Detection Learnable?](https://mlsanity.com/paper/2210.14707/) (2022)
- [Uncertainty Aware Semi-Supervised Learning on Graph Data](https://mlsanity.com/paper/2010.12783/) (2020)
- [Energy-based Out-of-Distribution Detection for Graph Neural Networks](https://mlsanity.com/paper/2302.02914/) (2023)
- [Active Learning for Graph Embedding](https://mlsanity.com/paper/1705.05085/) (2017)
- [Graph Policy Network for Transferable Active Learning on Graphs](https://mlsanity.com/paper/2006.13463/) (2020)
- [GOOD-D: On Unsupervised Graph Out-Of-Distribution Detection](https://mlsanity.com/paper/2211.04208/) (2022)
- [Distance Metric Learning using Graph Convolutional Networks: Application to Functional Brain Networks](https://mlsanity.com/paper/1703.02161/) (2017)
- [Open-world Learning and Application to Product Classification](https://mlsanity.com/paper/1809.06004/) (2018)
- [TIMME: Twitter Ideology-detection via Multi-task Multi-relational Embedding](https://mlsanity.com/paper/2006.01321/) (2020)
- [Active Learning for Graph Neural Networks via Node Feature Propagation](https://mlsanity.com/paper/1910.07567/) (2019)
- [Active Learning for Open-set Annotation](https://mlsanity.com/paper/2201.06758/) (2022)
- [Learning on Graphs with Out-of-Distribution Nodes](https://mlsanity.com/paper/2308.06714/) (2023)
- [MultiOOD: Scaling Out-of-Distribution Detection for Multiple Modalities](https://mlsanity.com/paper/2405.17419/) (2024)
- [Meta-Query-Net: Resolving Purity-Informativeness Dilemma in Open-set Active Learning](https://mlsanity.com/paper/2210.07805/) (2022)
- [Entropic Open-set Active Learning](https://mlsanity.com/paper/2312.14126/) (2023)
- [Entropic Out-of-Distribution Detection](https://mlsanity.com/paper/1908.05569/) (2019)
- [MetaOOD: Automatic Selection of OOD Detection Models](https://mlsanity.com/paper/2410.03074/) (2024)
- [Structured Citation Trend Prediction Using Graph Neural Networks](https://mlsanity.com/paper/2104.02562/) (2021)
- [Graph Partitioning and Graph Neural Network based Hierarchical Graph Matching for Graph Similarity Computation](https://mlsanity.com/paper/2005.08008/) (2020)

## Built on by (most cited first, 10 of 10)

- [DPU: Dynamic Prototype Updating for Multimodal Out-of-Distribution Detection](https://mlsanity.com/paper/2411.08227/) (2024)
- [Secure On-Device Video OOD Detection Without Backpropagation](https://mlsanity.com/paper/2503.06166/) (2025)
- [Few-Shot Graph Out-of-Distribution Detection with LLMs](https://mlsanity.com/paper/2503.22097/) (2025)
- [Graph Synthetic Out-of-Distribution Exposure with Large Language Models](https://mlsanity.com/paper/2504.21198/) (2025)
- [M3OOD: Automatic Selection of Multimodal OOD Detectors](https://mlsanity.com/paper/2508.11936/) (2025)
- [LLM-Powered Text-Attributed Graph Anomaly Detection via Retrieval-Augmented Reasoning](https://mlsanity.com/paper/2511.17584/) (2025)
- [When LLMs meet open-world graph learning: a new perspective for unlabeled data uncertainty](https://mlsanity.com/paper/2505.13989/) (2025)
- [A Systematic Study of Model Extraction Attacks on Graph Foundation Models](https://mlsanity.com/paper/2511.11912/) (2025)
- [HOPE: Heterophily-Aware Open-Set Node Classification with Pseudo-Extrapolation](https://mlsanity.com/paper/2609.08685/) (2026)
- [GTA: Graph Theory Agent and Benchmark for Algorithmic Graph Reasoning with LLMs](https://mlsanity.com/paper/2609.12265/) (2026)

## Abstract (arXiv)

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 many 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 tackles 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 select 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 uses 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, with up to a 6.62% improvement in ID classification accuracy and a 7.49% increase in AUROC for OOD detection.