Localization on low-order eigenvectors of data matrices
Preprint
Abstract
Eigenvector localization refers to the situation when most of the components of an eigenvector are zero or near-zero. This phenomenon has been observed on eigenvectors associated with extremal eigenvalues, and in many of those cases it can be meaningfully interpreted in terms of "structural heterogeneities" in the data. For example, the largest eigenvectors of adjacency matrices of large complex networks often have most of their mass localized on high-degree nodes; and the smallest eigenvectors of the Laplacians of such networks are often localized on small but meaningful community-like sets of nodes. Here, we describe localization associated with low-order eigenvectors, i.e., eigenvectors corresponding to eigenvalues that are not extremal but that are "buried" further down in the spectrum. Although we have observed it in several unrelated applications, this phenomenon of low-order eigenvector localization defies common intuitions and simple explanations, and it creates serious difficulties for the applicability of popular eigenvector-based machine learning and data analysis tools. After describing two examples where low-order eigenvector localization arises, we present a very simple model that qualitatively reproduces several of the empirically-observed results. This model suggests certain coarse structural similarities among the seemingly-unrelated applications where we have observed low-order eigenvector localization, and it may be used as a diagnostic tool to help extract insight from data graphs when such low-order eigenvector localization is present.Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Extracting spatial information from networks with low-order eigenvectorsPhysical Review E, 2013
- Spectral and dynamical properties in classes of sparse networks with mesoscopic inhomogeneitiesPhysical Review E, 2009
- CUR matrix decompositions for improved data analysisProceedings of the National Academy of Sciences, 2009
- Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined ClustersInternet Mathematics, 2009
- Spectral partitioning works: Planar graphs and finite element meshesLinear Algebra and its Applications, 2007
- Finding community structure in networks using the eigenvectors of matricesPhysical Review E, 2006
- Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion mapsProceedings of the National Academy of Sciences, 2005
- Spectra of complex networksPhysical Review E, 2003
- Spectra and eigenvectors of scale-free networksPhysical Review E, 2001
- Spectra of “real-world” graphs: Beyond the semicircle lawPhysical Review E, 2001