REND: Reject-Encoder Novelty Diffusion for Out-of-Distribution Detection on Graphs

Existing methods for out-of-distribution (OOD) detection on graphs read their score from a representation that was trained for another purpose, namely classifier logits, classifier embeddings, or diffused class evidence. When the observed classes are fewer than the embedding dimensions, every score read from the logits is invariant along a residual subspace of the embedding. Scores that read the whole embedding escape this invariance, but classification training never requires any direction of the representation to separate novel nodes from familiar ones, so whatever novelty structure a borrowed representation retains is incidental. We propose REND (Reject-Encoder Novelty Diffusion), in which a dedicated reject encoder reads the raw features and the graph structure directly and is trained by novelty objectives alone. Since OOD labels are not available at training time, a self-supervised surrogate-outlier loss supplies the missing supervision, and stop-gradients keep the reject branch from reaching the classifier, which leaves the accuracy unchanged. A personalized-PageRank kernel then smooths the learned reject propensity, and its teleport floor guarantees that every node keeps a fixed share of its own novelty. REND shows excellent performance on twelve homophilous, heterophilous, and heterogeneous benchmarks.