Robust Random Walk Based on Natural Neighbors for Outlier Detection

Outlier detection serves as an effective technique for identifying anomalous samples in complex data. Existing methods are often disturbed by noise and boundary samples, which degrade the quality of sample relationships. Moreover, traditional random walk approaches are vulnerable to weak and spurious connections that can mislead the walking process. To address these issues, this paper proposes a robust random walk based on natural neighbors for outlier detection (RWNOD) method. First, an adaptive smoothing mechanism is proposed to leverage natural neighbors to actively adjust sample positions, reducing local noise while preserving structural information. Then, a robust random walk strategy is developed to incorporate shadowed sets into the transition matrix, preserving reliable connections while suppressing unreliable ones. At the same time, a corresponding outlier detection algorithm is proposed. Experiments on datasets are conducted to compare the proposed algorithm with seven other algorithms. The experimental results demonstrate that the proposed algorithm achieves superior performance and strong robustness.