Spending LLM Calls Where Novel Classes Live: Multi-Scale Uncertainty Signals for Budgeted Open-Set Node Classification

A node classifier trained on a fixed set of classes gets confused when a new class appears in the graph, for example a new research topic in a citation network. That confusion is not scattered at random. It forms a connected patch, because papers on the new topic cite each other. A different kind of confusion, from a single corrupted or mislabeled node, shows up as an isolated spike. This note proposes treating the classifier's per-node uncertainty as a signal on the graph and splitting it into scales with graph wavelets, which are filters that separate smooth, region-wide patterns from sharp local ones. The mid-scale part, which picks out patches rather than spikes, would decide which few nodes deserve an expensive large language model (LLM) query. The LLM checks whether those nodes belong to a new class, and its answers are spread back over the graph as real outlier supervision.

The stakes are practical. The best current open-set graph method, Coarse-to-Fine Open-Set Graph Node Classification with Large Language Models (CFC), prompts GPT-4o on node text to flag unknown-class nodes and then trains a graph neural network on them. It reports 95.74% detection accuracy on Cora, but it queries the LLM per node, which is unaffordable on ogbn-arxiv (169k nodes) or larger graphs. The question here is how much of CFC's accuracy survives when the LLM sees only 1–5% of nodes, and whether graph structure, read at the right scale, is what makes that possible.

Core Claim

Semantic class novelty and structural anomaly leave their traces in different frequency bands of a classifier's uncertainty signal. Novelty concentrates in low-to-mid bands, as coherent communities of elevated uncertainty. Anomalies and label noise concentrate in high bands. This offers a concrete explanation for the "GAD paradox" reported by G-OSR: graph anomaly detectors perform poorly on open-set recognition because they are tuned to the wrong band. Rethinking Graph Neural Networks for Anomaly Detection (BWGNN) showed that anomalies shift spectral energy toward high frequencies and built Beta-wavelet band-pass filters to catch them. We reuse its filters but aim them at a different signal (uncertainty, not raw features), a different band, and a different purpose: choosing LLM queries under a budget rather than scoring anomalies.

Formally, let $L$ be the normalized graph Laplacian, $s \in \mathbb{R}^n$ the per-node energy score of a closed-set graph neural network over $n$ nodes, and $g_j$ the $j$-th Beta-wavelet kernel from BWGNN, applied as a polynomial in $L$ so that no eigendecomposition is needed. The band coefficients are

$$w_j = g_j(L)\, s, \qquad j = 1,\dots,J,$$

and a node's query priority is $q = \sum_j \alpha_j |w_j|$. The weights $\alpha_j$ are learned from a small held-out simulation in which some known classes are withheld, following the withholding trick in UnLLM. The prediction is that the learned $\alpha$ puts most of its weight on mid bands. Queries are then placed at local maxima of the dominant-band coefficients, so one query covers one "bump" of novelty instead of many redundant nodes from the same patch.

Research Program

The pipeline has four steps. First, we train a closed-set graph neural network on the known classes and compute its energy score on every node. Second, we decompose that score with the wavelet bank and select a query set of size $B$ from local maxima of $q$. Third, we query an LLM with CFC's hard-reject prompt, which summarizes the known classes and asks whether the node belongs to one of them or to a new category, plus a short name if it is new. Fourth, we run label propagation to spread the LLM's known/unknown verdicts outward within each queried bump, retrain the network with the verified outliers as an extra "unknown" class, and repeat for two or three rounds, splitting $B$ across rounds.

This connects to the synthetic-data literature by substitution. PromptMix generates borderline examples and then has to relabel the whole synthetic corpus with the LLM (up to 13.5% gain from relabeling), and TrueTeacher spends a 540B teacher on 1.4M examples. CFC already argues that real in-graph outliers beat synthetic noise. Our contribution is to make that choice cheap by spending each LLM call on the most informative real node.

The cost framing comes from routing work. OCaTS decides per query whether to call GPT-4 using distance-to-cache and entropy, and cuts calls by 34% on Banking77 at 82.68% vs 83.05% accuracy. ProxRouter shows that nearest-neighbor routers break on outlier queries. Both treat inputs as independent points in an embedding space. Our method differs in that the decision to call the LLM depends on a node's graph neighborhood at a chosen scale, which is what lets one call stand in for a whole patch.

There is a first-order diagnostic that needs no LLM at all, and it comes before any of this. On Cora, Citeseer and ogbn-arxiv, we withhold classes in the G-OSR protocol and use PyGOD's outlier generators (PyGOD) to inject structural and attribute anomalies. We then measure how the energy of the uncertainty signal splits across bands for each population. If the band profiles of novel-class nodes and injected anomalies overlap heavily, the core premise is false and the project stops there.

Baselines

The naive reference is random selection of $B$ nodes for LLM querying, followed by the same propagation and retraining. It tells us whether graph-aware selection matters at all.

The first strong comparison is no LLM at all. Here we use the post-hoc and graph-specific detectors from G-OSR under its protocol and a matched backbone. Maximum softmax probability (MSP) is reported there at about 91% AUROC on Cora and about 68% on ogbn-arxiv. EMP is reported at 95.74% AUROC on Cora and 98.44% on Coauthor-CS. GNNSafe is included as well; it propagates energy scores over the graph, and no reported result found on Lacuna for GNNSafe's standalone AUROC, although CFC reports beating GNNSafe and GOLD by roughly 10% in detection accuracy.

The strongest existing method is CFC with full per-node LLM querying, which reports 95.74% detection accuracy on Cora and 48–70% accuracy at naming unknown classes. This is the accuracy ceiling. We re-run it with the same open-weight LLM we use, so that the comparison is not confounded by the choice of model. We also run it with GPT-4o on Cora and Citeseer to anchor our numbers to the published ones.

Next is an OCaTS-style selector adapted to nodes: query the nodes with the highest entropy or the greatest embedding distance from labeled nodes, with no graph filtering.

The key ablations share the wavelet machinery but change the band. The first uses only the high-pass band (BWGNN's anomaly setting). The second uses only a single low-pass smoothing of the energy score, which approximates GNNSafe's propagation. The third uses all bands with learned $\alpha$ but without the local-maximum deduplication.

All methods share the same backbone, the same known/unknown splits, the same LLM and prompt, and the same budget $B$ in LLM calls. Each gets an equal hyperparameter search budget on the withheld-class validation split.

To count as a win, the method must beat both entropy selection and the best single-band ablation in AUROC and known/unknown macro-F1 at budgets of 1–5% of nodes, across seeds. On Cora, Citeseer, WikiCS and DBLP, it must recover at least 90% of full CFC's detection accuracy at 5% of CFC's LLM calls. On ogbn-arxiv, where full CFC is impractical and we report CFC only on a sampled subgraph, it must clearly exceed MSP's roughly 68% AUROC.

Why not just…?

Why not just propagate the OOD score, as GNNSafe does? This is the most serious threat. If novelty really is smooth, a single low-pass smoothing might capture most of the benefit. Our reason to expect more is that one fixed scale cannot adapt to how large the novel-class patches are, which varies from Cora-sized topics to arxiv sub-fields, and pure low-pass smoothing also blurs the patch boundaries where known and unknown nodes meet. The low-pass-only ablation settles this directly. If it matches the multi-band version, we will report that the gain comes from graph-aware query placement, not from multi-scale decomposition, and simplify the method accordingly.

Why not just cluster node embeddings and query one representative per cluster? Clustering in the embedding space can also find coherent groups of novel nodes cheaply. However, it ignores edges, and ProxRouter's result that proximity-based methods degrade by up to 15% on outlier queries suggests that flat embedding neighborhoods are unreliable exactly where novelty lives. We add k-means representative querying at a matched budget as an extra baseline. A tie there would mean the graph adds nothing beyond the embeddings.

Why not just generate synthetic outliers with an LLM once, offline? PromptMix and TrueTeacher show that synthetic boundary data carries a relabeling tax. Offline generation also cannot anticipate which novel class actually appears in a given graph, and CFC reports that real in-graph outliers work better than synthetic noise. We test this with a PromptMix-style variant that spends the same number of LLM calls on generating and relabeling synthetic "unknown" node texts.

Why not just ask the LLM about every node, but with a cheaper model? Using a smaller model is complementary, not a substitute. The number of calls still grows with the number of nodes, and UnLLM notes that closed-set-prompted LLMs are overconfident on unknowns, which small models are likely to make worse. We report full-coverage querying with the same open-weight model as the cost-unconstrained ceiling.

Proposed Experiments

The decisive checks come in order. The first is the band-profile diagnostic described above, which checks whether novel-class nodes and injected anomalies separate by frequency. The second is accuracy-versus-budget curves on Cora, Citeseer, WikiCS and DBLP at 0.5%, 1%, 2%, 5% and 10% of nodes, measuring AUROC, known/unknown macro-F1, and unknown-class naming accuracy scored as CFC does. The third is the ogbn-arxiv scale test, which also records the wall-clock cost of the polynomial filters relative to LLM calls; BWGNN's 32-second training on T-Finance suggests the filters themselves will be cheap. The fourth is the band-ablation grid, which is what separates the multi-scale claim from the simpler story that "any graph smoothing helps."

The main limitation is that the method needs text attributes for the LLM step, as CFC does. The wavelet selector itself does not need text, but testing it on purely structural graphs is left to follow-up work.