Coarse-to-Fine Open-Set Graph Node Classification with Large Language Models

AI summary

Overview

Research area: Open-set learning on graphs — combining graph neural networks (GNNs) with large language models (LLMs) for out-of-distribution (OOD) detection and, more ambitiously, OOD classification.

Technical level: Advanced. The paper assumes familiarity with GNNs, out-of-distribution detection, text-attributed graphs, and LLM prompting.

Scope in one sentence: The paper proposes a Coarse-to-Fine Classification (CFC) framework that first uses LLM prompts to detect OOD nodes and propose candidate outlier labels, then trains a GNN-based fine classifier on those semantic OOD samples, and finally uses LLM prompts again to assign OOD nodes to distinct unknown classes — without any true OOD label information.

What This Paper Is About

Standard GNN classifiers assume every test node belongs to one of the known (in-distribution, ID) classes, so they fail when deployed on graphs containing nodes from unseen classes. Existing open-set methods typically lump all unknown nodes into a single "OOD" bucket, which is far less useful in high-stakes settings like fraud detection or medical diagnosis where the type of unknown matters. The paper's goal is to extend OOD detection into OOD classification: not only flagging unknown nodes but partitioning them into multiple distinct unknown classes, using LLM knowledge in place of missing OOD labels.

Key Contributions

1. A new task formulation. The authors introduce OOD classification on graphs as a harder extension of OOD detection — a $(C+u)$-class problem where $u$ distinct OOD classes must be recovered even though $u$ is not predefined and no OOD labels exist.
2. A coarse-to-fine framework (CFC). CFC combines (i) an LLM-based coarse classifier that detects OOD nodes and generates candidate outlier labels, (ii) a GNN-based fine classifier trained on those semantic OOD samples with label-propagation denoising and an improved manifold mixup augmentation, and (iii) a final LLM-based OOD classification step over a post-processed OOD label space.
3. Semantic OOD instead of synthetic OOD. Rather than generating synthetic proxy unknowns or relying on auxiliary outlier exposure, CFC uses instances that are genuinely out-of-distribution by their inherent meaning, which the authors argue improves interpretability and reduces distribution discrepancy.
4. Empirical and theoretical support. CFC is reported to enhance OOD detection by 10% over state-of-the-art approaches on graph and text domains and to reach up to 70% accuracy in OOD classification on graph datasets; Theorem 3.1 argues CFC's OOD subspace has dimension $dim(\mathcal{H}+\mathcal{H}')-(C+1)$ versus $dim(\mathcal{H})-(C+1)$ for general methods, yielding a smoother decision boundary.

Main Findings

• OOD detection gains. Across the text-attributed graph datasets Cora, Citeseer, WikiCS, and DBLP, CFC outperformed all baselines. On Cora (two OOD classes, e5-large-v2 encoder) CFC reached ID accuracy 87.49 ± 0.80, OOD accuracy 95.74 ± 0.67, and overall 90.00 ± 0.37; on DBLP it reached 78.47 ± 1.01 ID, 86.89 ± 0.71 OOD, and 84.03 ± 0.15 overall.
• Large margins over second-best. The paper reports over or around a 10% improvement in overall accuracy over the second-best method on Cora, WikiCS, and DBLP, and over 10% overall accuracy margin across all datasets in the three-OOD-class setting (DBLP excluded because it has only four classes).
• The coarse step alone is already strong. CFC (w/o D/M) — the framework without denoising and manifold mixup — still delivered comparable or better results than all other baselines (for example 85.44 ± 0.20 ID, 94.50 ± 0.31 OOD, 88.20 ± 0.20 overall on Cora).
• Comparing to closed-set behavior. Against GCN_sigmoid on Cora, ID accuracy dipped from 90.64% to 87.49% while OOD detection rose from 0% to 95.74%. Against the open-set baseline G²Pxy on Cora, CFC raised OOD accuracy from 72.46% to 95.74%.
• OOD classification results. With the post-OOD label space and GPT-4o, CFC achieved 69.76%, 70.30%, 57.96%, and 48.45% accuracy on Cora, Citeseer, WikiCS, and DBLP respectively in the two-OOD-class case. The abstract describes this as "up to 70% accuracy in OOD classification on graph datasets."
• Raw LLM detection is limited. When GPT-4o is given only the ID label space, the paper reports that it recognizes only about half of the OOD samples in most cases, which the authors state makes it unsuitable for high-stakes applications. GPT-4o's own overall accuracies in Table 1 were 68.62 (Cora), 47.50 (Citeseer), 67.43 (WikiCS), and 66.11 (DBLP).
• Non-textual graphs. CFC also works on Amazon-Computer (78.15 ± 0.96 ID, 86.54 ± 1.03 OOD, 82.28 ± 0.41 overall) and Amazon-Photo (82.81 ± 0.77 ID, 76.14 ± 4.76 OOD, 81.81 ± 0.07 overall).
• Prompt constraints matter. Removing the constraint (rejecting with high confidence for Easy-Reject, adding a candidate OOD label space for Hard-Reject) degraded OOD performance on AUROC.
• LLM choice for detection. GPT-4o outperformed Llama models on Cora and Citeseer, with Llama3-8b slightly better than Llama2-7b; Llama models used few-shot prompting with one ID and one OOD example, while GPT-4o used zero-shot prompting.
• Ablation on denoising and augmentation. CFC variants without denoising (CFC w/o D/M and CFC w/o D) consistently had lower ID accuracy across all datasets than CFC (w/o M) and CFC with denoising; the manifold mixup augmentation gave significant improvement over CFC (w/o D/M) on all datasets.
• Encoder choice. Among e5-large-v2, Sentence Transformer, Llama2-7b, and Llama2-13b feature encoders, e5-large-v2 performed better and more stably in joint training; Llama2 excelled on ID topics for Citeseer while e5 and ST performed well on OOD.

Methodology in Plain English

The pipeline runs in three phases.

Phase 1 — Coarse classification with an LLM. Graph nodes are described as text. Given the list of known ID labels, an LLM is asked whether a test node's label falls inside that list, and to state a confidence score. The authors split this into two prompt designs: Easy-Reject (used for Cora, DBLP, and WikiCS), where the ID classes cover only a small portion of their broader categories, so the prompt only marks a node OOD when the LLM is highly confident; and Hard-Reject (used for Citeseer, Computer, and Photo), where the ID classes cover a large portion of their major categories, so the LLM first summarizes the major categories and proposes candidate OOD labels that fit those categories but are absent from the ID set, and then classifies with that candidate space in hand. A confidence threshold of 0.7 is applied.

Phase 2 — Fine classification with a GNN. The OOD nodes identified by the LLM are noisy and possibly few. A label propagation step (using the normalized adjacency, resetting training-node labels each iteration) removes nodes that are actually ID. Manifold mixup then mixes hidden embeddings of low-confidence boundary nodes with the center embedding of the OOD set — $ ilde{x}_i = \alpha h_i^k + (1-\alpha) h_c^k$ with label $C+1$ — to synthesize more OOD samples. The paper generates 100 OOD samples for text datasets and over 2000 for the Computer and Photo datasets. A two-layer GCN is trained on the training nodes plus the augmented OOD set to produce a $(C+1)$-class classifier.

Phase 3 — OOD classification. The candidate OOD labels collected earlier are post-processed with similarity measures such as TF-IDF to merge near-duplicates and drop categories with too few samples, producing a post-OOD label space. The LLM is then prompted once more to assign each detected OOD node to a category in that space.

Data setup. Each dataset designates multiple classes as OOD ($u \geq 2$) and the rest as ID. For ID classes, 50% of nodes are used for training; the remaining ID nodes and all OOD nodes are split 40% validation and 60% test. Results are averaged over 5 runs.

Why This Matters

Impact on research. The paper reframes open-set graph learning from a binary detect/reject problem into a multi-class unknown-classification problem, and it argues that semantic OOD samples ground in real meaning rather than synthetic proxies. It also supplies a theoretical argument (Theorem 3.1, with Assumption 3.1 stating a $C$-class feature space has dimension $d-C$) for why semantic OOD data expands the representation subspace and smooths the detection boundary.

Real-world applications (as identified in the paper):

• Financial networks, where grouping phishing attacks, insider threats, and money-laundering schemes into one unknown category oversimplifies distinctions needed for mitigation.
• Medical diagnosis, listed among high-stake settings demanding deeper insight into unknown samples.
• Fraud detection, likewise cited as a domain where distinguishing unknown categories matters.
• Autonomous driving, also listed among high-stakes applications requiring distinction between unknown classes.

Industry relevance. The authors note CFC's framework can be extended to text data, making it a flexible open-set solution beyond graphs. Recovering separate unknown categories supports more informed decision-making, better data utilization, and more nuanced responses in deployed systems — the paper explicitly contrasts this with the cost of threshold tuning and with the computation cost of training on large volumes of synthetic or auxiliary OOD samples.

Future Directions

• Handling the truncation of LLM recall. Because GPT-4o recognizes only about half of OOD samples when given the ID label space alone, improving coarse-stage recall without flooding the pipeline with false positives remains an open problem.
• Extending beyond the current domains. The paper states the framework can be applied to text data, and demonstrates non-textual graph results, leaving broader domain transfer as an open question.
• Scaling the OOD label space. The number of unknown classes $u$ is not predefined in open-set scenarios; determining and validating $u$ reliably (the paper examines $u=2$ and $u=3$ cases, with DBLP limited to the other three datasets for $u=3$) is an unresolved element.
• Reducing ID accuracy trade-off. CFC's ID accuracy on Cora dropped from 90.64% to 87.49% relative to GCN_sigmoid, so closing the gap between closed-set ID performance and open-set capability is a natural next step.

Target Audience

Researchers and practitioners working on graph neural networks, open-set recognition, OOD detection, and LLM-augmented learning, particularly those deploying models in high-stakes domains such as finance, medicine, and autonomous systems. It is also relevant to readers interested in prompt engineering for structured data, since the Easy-Reject and Hard-Reject prompt designs are tied to how much of the ID label space is covered by its major categories.

Authors’ abstract

Developing open-set classification methods capable of classifying in-distribution (ID) data while detecting out-of-distribution (OOD) samples is essential for deploying graph neural networks (GNNs) in open-world scenarios. Existing methods typically treat all OOD samples as a single class, despite real-world applications, especially high-stake settings such as fraud detection and medical diagnosis, demanding deeper insights into OOD samples, including their probable labels. This raises a critical question: can OOD detection be extended to OOD classification without true label information? To address this question, we propose a Coarse-to-Fine open-set Classification (CFC) framework that leverages large language models (LLMs) for graph datasets. CFC consists of three key components: a coarse classifier that uses LLM prompts for OOD detection and outlier label generation, a GNN-based fine classifier trained with OOD samples identified by the coarse classifier for enhanced OOD detection and ID classification, and refined OOD classification achieved through LLM prompts and post-processed OOD labels. Unlike methods that rely on synthetic or auxiliary OOD samples, CFC employs semantic OOD instances that are genuinely out-of-distribution based on their inherent meaning, improving interpretability and practical utility. Experimental results show that CFC improves OOD detection by ten percent over state-of-the-art methods on graph and text domains and achieves up to seventy percent accuracy in OOD classification on graph datasets.