Papers › Scalability and robustness of spectral embedding: landmark diffusion is all you need
Scalability and robustness of spectral embedding: landmark diffusion is all you need
Chao Shen, Hau-Tieng Wu
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
While spectral embedding is a widely applied dimension reduction technique in various fields, so far it is still challenging to make it scalable to handle ``big data''. On the other hand, the robustness property is less explored and there exists only limited theoretical results. Motivated by the need of handling such data, recently we proposed a novel spectral embedding algorithm, which we coined Robust and Scalable Embedding via Landmark Diffusion (ROSELAND). In short, we measure the affinity between two points via a set of landmarks, which is composed of a small number of points, and ``diffuse'' on the dataset via the landmark set to achieve a spectral embedding. Roseland can be viewed as a generalization of the commonly applied spectral embedding algorithm, the diffusion map (DM), in the sense that it shares various properties of DM. In this paper, we show that Roseland is not only numerically scalable, but also preserves the geometric properties via its diffusion nature under the manifold setup; that is, we theoretically explore the asymptotic behavior of Roseland under the manifold setup, including handling the U-statistics-like quantities, and provide a L^∞ spectral convergence with a rate. Moreover, we offer a high dimensional noise analysis and show that Roseland is robust to noise. We also compare Roseland with other existing algorithms with numerical simulations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections