Generalized Laplacian in Spectral Seriation on Manifold Data

We study high-dimensional observations $Z_i \in \mathbb{R}^p$ satisfying that $E[Z_i] = X(t_i)$, where $X(t)$ parameterizes a manifold on $0 \le t < 2\pi$, with the goal of recovering the latent phases $t_i$; a motivating example is estimating object-viewing angles from photographs. Spectral seriation is a standard phase-recovery method: given a similarity matrix $S$ with degree matrix $D$, it uses the leading eigenvectors of the normalized Laplacian $D^{-1/2} S D^{-1/2}$, whose continuum limit is linked to the manifold Laplacian, to estimate $t_i$. Recent applications show that generalized Laplacians involving $D^{-\alpha}$ can outperform the normalized Laplacian on graphs with heterogeneous degrees, raising the central question of whether the same advantage holds for spectral seriation. We address such question by introducing and comparing three principled generalizations drawn from manifold learning and spectral seriation: a shifted generalized Laplacian, a graph-difference Laplacian, and an extra-normalized generalized Laplacian. The extra-normalized generalized Laplacian is the most robust to $\alpha$ and achieves the highest recovery accuracy, identifying extra normalization as the key stabilizing step. We establish a consistency result unveiling that eigenspace perturbation controls the estimation error up to rotation and reflection, giving a theoretical basis for the method. Experiments on noisy closed curves confirm more accurate phase recovery under a suggested choice of $\alpha$; on image data, the method recovers photo angles with the best accuracy. Our results demonstrate that extra normalization is a key component for stable generalized spectral seriation in closed-curve recovery problems.