Uncovering Locally Low-dimensional Structure in Networks by Locally Optimal Spectral Embedding
This addresses the issue of global low-rank assumptions smearing local features in network analysis, though it is incremental as it builds on existing spectral embedding methods.
The paper tackles the problem of standard Adjacency Spectral Embedding (ASE) being incompatible with sparse, real-world networks by introducing Local Adjacency Spectral Embedding (LASE), which uncovers locally low-dimensional structure and improves local reconstruction and visualization over baselines.
Standard Adjacency Spectral Embedding (ASE) relies on a global low-rank assumption often incompatible with the sparse, transitive structure of real-world networks, causing local geometric features to be 'smeared'. To address this, we introduce Local Adjacency Spectral Embedding (LASE), which uncovers locally low-dimensional structure via weighted spectral decomposition. Under a latent position model with a kernel feature map, we treat the image of latent positions as a locally low-dimensional set in infinite-dimensional feature space. We establish finite-sample bounds quantifying the trade-off between the statistical cost of localisation and the reduced truncation error achieved by targeting a locally low-dimensional region of the embedding. Furthermore, we prove that sufficient localisation induces rapid spectral decay and the emergence of a distinct spectral gap, theoretically justifying low-dimensional local embeddings. Experiments on synthetic and real networks show that LASE improves local reconstruction and visualisation over global and subgraph baselines, and we introduce UMAP-LASE for assembling overlapping local embeddings into high-fidelity global visualisations.