Outlier detection in eigenvalue spaces based on spectral analysis of KNN graphs

Outlier detection is a critical method in data mining as it has a wide range of practical uses in various fields. Spectral clustering has attracted much attention for its advantage in coping with the curse of dimensionality in high-dimensional spaces. While spectral clustering has been applied to outlier detection, existing methods typically rely on eigenvectors and lack a unified mechanism to simultaneously address both local and global outliers. This paper presents a new spectral analysis based outlier detection (SAOD) framework. We first construct the k-nearest neighbors (kNN) graphs of each sample and compute the eigenvalues of the Laplacian matrices of these graphs. Our findings demonstrate that the distribution of eigenvalues for outliers differs from that of inliers. Based on this observation, we employ the multivariate Gaussian kernel density estimation to empirically estimate the eigenvalue distribution of a given data set. We then introduce a new outlier factor, based on the eigenvalue probabilities of samples to assess their degree. The experimental results, obtained from both synthetic and real-world data sets, show that our spectral analysis based outlier detection method outperforms the state-of-the-art approaches. The code for these experiments is made available at: https://github.com/laetella/SAOD.