Detecting data points deviating from the training distribution is pivotal for
ensuring reliable machine learning. Extensive research has been dedicated to
the challenge, spanning classical anomaly detection techniques to contemporary
out-of-distribution (OOD) detection approaches. While OOD detection commonly
relies on supervised learning from a labeled in-distribution (ID) dataset,
anomaly detection may treat the entire ID data as a single class and disregard
ID labels. This fundamental distinction raises a significant question that has
yet to be rigorously explored: when and how does ID label help OOD detection?
This paper bridges this gap by offering a formal understanding to theoretically
delineate the impact of ID labels on OOD detection. We employ a graph-theoretic
approach, rigorously analyzing the separability of ID data from OOD data in a
closed-form manner. Key to our approach is the characterization of data
representations through spectral decomposition on the graph. Leveraging these
representations, we establish a provable error bound that compares the OOD
detection performance with and without ID labels, unveiling conditions for
achieving enhanced OOD detection. Lastly, we present empirical results on both
simulated and real datasets, validating theoretical guarantees and reinforcing
our insights. Code is publicly available at
this https URL

本研究通过图论方法对数据表示进行谱分解，建立一种理论上对内部标签对外部数据检测性能的影响有较好界定的方法。实验结果验证了理论保证和观点，展示了内外标签对提高外部数据检测能力的条件。