Robust Regularized Locality Preserving Indexing for Fiedler Vector Estimation

The Fiedler vector is the eigenvector associated with the algebraic connectivity of the graph Laplacian. It is central to graph analysis as it provides substantial information to learn the latent structure of a graph. In real-world applications, however, the data may be subject to heavy-tailed noise and outliers which deteriorate the structure of the Fiedler vector estimate and lead to a breakdown of popular methods. Thus, we propose a Robust Regularized Locality Preserving Indexing (RRLPI) Fiedler vector estimation method that approximates the nonlinear manifold structure of the Laplace Beltrami operator while minimizing the impact of outliers. To achieve this aim, an analysis of the effects of two fundamental outlier types on the eigen-decomposition of block affinity matrices is conducted. Then, an error model is formulated based on which the RRLPI method is developed. It includes an unsupervised regularization parameter selection algorithm that leverages the geometric structure of the projection space. The performance is benchmarked against existing methods in terms of detection probability, partitioning quality, image segmentation capability, robustness and computation time using a large variety of synthetic and real data experiments.