Uncovering Locally Low-dimensional Structure in Networks by Locally Optimal Spectral Embedding

Hannah Sansford; Nick Whiteley; Patrick Rubin-Delanchy

stat.MLMar 12, 2026

Uncovering Locally Low-dimensional Structure in Networks by Locally Optimal Spectral Embedding

Authors: Hannah Sansford, Nick Whiteley, Patrick Rubin-Delanchy

Organizations: School of Mathematics, University of Bristol, UK · School of Mathematics, University of Edinburgh, UK

Abstract

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.

Figures & tables

\hat{\mathbf{X}}=\mathbf{U}\mathbf{\Lambda}^{1/2}\in\mathbb{R}^{n\times r},

Algorithm 1 Adjacency Spectral Embedding (ASE)

Figure 1: Left: the top 100 eigenvalues of the adjacency matrix, $\mathbf{A}$ , of the Bristol Road Network (see Section 5.2 for details of the dataset), where $n=3857$ . Right: the top 20 eigenvalues of $\mathbf{W}^{1/2}\mathbf{A}\mathbf{W}^{1/2}$ , where $\mathbf{W}$ is a diagonal matrix of weights $w_{1},\ldots,w_{n}>0$ selected to ‘localise’ LASE (Algorithm 2 ) around a node of interest, $z$ , based on the graph distance from $z$ (see Section 4.7 - graph-distance-based weighting).

\hat{\mathbf{X}}=\mathbf{W}^{-1/2}\mathbf{U}_{w}\mathbf{\Lambda}_{w}^{1/2}\in\mathbb{R}^{n\times r},

Algorithm 2 Local Adjacency Spectral Embedding (LASE)

\hat{X}_{n+1}^{\top}=\tilde{\mathbf{a}}^{\top}\mathbf{U}_{w}\mathbf{\Lambda}_{w}^{-1/2}.

Algorithm 3 Inductive LASE

Figure 2: First two dimensions of the Mercer feature map $\phi$ (leftmost column) and the locally weighted feature map $\phi_{w}$ for increasing localisation (subsequent columns), controlled by the concentration parameter $\tau$ . We use $\mu=\text{Uniform}[0,10]$ and $f(x,y)=\exp(-\tfrac{1}{2}(x-y)^{2})$ . Top row: localisation around $z\approx 1.5$ . Bottom row: localisation around $z\approx 7.5$ . In each row, $z^{\star}$ is indicated by a red circle and latent positions $z^{\star}\pm 0.5$ are indicated by red crosses. As $\tau$ increases, $\phi_{w}$ “zooms in” and better represents inner products for points likely under $\mu_{w}$ . All plots align $\phi_{w}(z^{\star})$ to $\phi(z^{\star})$ using Procrustes analysis.

Figure 3: The top 6 eigenvalues of $\mathbf{P}$ are plotted as the measure $\mu_{w}$ concentrates about a point. In each plot, the dimension $d$ of the latent space $\mathcal{Z}$ is identified in the plot subtitle. Notice the distinct change in rate of decay between eigenvalues $d+1$ and $d+2$ .

Figure 4: Comparison of reconstruction accuracy under different LASE weighting strategies. Top left: Continuous weighting functions $w(Z_{i})$ with varying concentration parameters $\tau\in\{1,\dots,10\}$ , centered at $x=4$ . Top right: RMSE of reconstructed probabilities $\hat{\mathbf{P}}_{ij}$ versus true $\mathbf{P}_{ij}$ , computed over nodes with latent positions in $[3.5,4.5]$ , for each $\tau$ . Bottom left: Top-hat weighting functions of varying width, also centered at $x=4$ , corresponding to subgraph ASE on different-sized subgraphs. Bottom right: RMSE of reconstructed probabilities for each top-hat width. Shaded regions indicate $\pm 1$ SE over 10 sampled graphs.

Panel of Figure 5 — Figure 5: Column 1 : Latent positions within radius 1 of a central point, $z^{\star}$ . We call this the neighbourhood of $z^{\star}$ , and represent it by $\mathcal{N}_{z^{\star}}$ . Column 2 : ASE is performed on the full graph into 3D, followed by PCA into 2D on embeddings of nodes in $\mathcal{N}_{z^{\star}}$ . Column 3 : Subgraph SE is performed into 3D on the subgraph consisting of at least the nodes in $\mathcal{N}_{z^{\star}}$ , followed by PCA into 2D on embeddings of nodes in $\mathcal{N}_{z^{\star}}$ . Column 4 : LASE is performed into 3D on the full graph, with weights corresponding to latent position $x\in\mathcal{Z}$ set to $\exp(-0.4\times\|x-z^{\star}\|^{2}$ ), followed by PCA into 2D on embeddings of nodes in $\mathcal{N}_{z}$ . The reconstruction RMSE associated with each embedding is recorded in the titles.

Panel of Figure 6 — Figure 6: Linear regression of the true latitude and longitude coordinates of nodes onto embeddings (LASE, Subgraph ASE and Full ASE) of dimension $d=3$ (top row) and $d=20$ (bottom row). For all plots, the x-axis is the size of local neighbourhood (number of nodes) considered for the regression - see the main text for how this is determined. The left-hand plots show the mean $R^{2}$ statistic ( $\pm$ 1 SE) over 10 randomly selected neighbourhood centres. The right-hand plots show the mean-squared error ( $\pm$ 1 SE) for 10 randomly selected test points in the 100-node neighbourhood of the centres.

Figure 7: Global embeddings of the Bristol road network ( $n=3857$ ), with true coordinates in the right-most column. The first two columns show UMAP applied to ASE embeddings of the full network in $d=3$ and $d=20$ dimensions. The third column shows UMAP-LASE using $m=10$ and $d=3$ . Rows indicate colouring by longitude, latitude, and selected regions, respectively.

Figure 8: Global embeddings of the London road network ( $n=9478$ ), analogous to Figure 7 . UMAP-LASE yields improved geometric fidelity of geographic features such as the River Thames.

Network	UMAP-ASE ( $d=3$ )	UMAP-ASE ( $d=20$ )	UMAP-LASE ( $d=3$ )
Bristol	17.3	16.9	5.7
London	26.8	13.9	19.9

Table 1: Run-times (in seconds) for UMAP applied to different embeddings of the Bristol and London road networks.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 9: Global embeddings of the Bristol road network, analogous to Figure 7 , with an additional column for UMAP applied to a 3-dimensional Node2Vec embedding.

Figure 10: Global embeddings of the London road network, analogous to Figure 8 , with an additional column for UMAP applied to a 3-dimensional Node2Vec embedding.

Method	Bristol	London
UMAP-ASE ( $d=3$ )	17.3	26.8
UMAP-ASE ( $d=20$ )	16.9	13.9
UMAP-LASE ( $d=3$ )	5.7	19.9
UMAP-Node2Vec ( $d=3$ )	122.5	308.5

Appendix

Table 2: Run-times (in seconds) for UMAP applied to different embeddings of the Bristol and London road networks.

Spectral Graph Embedding

See all 16 papers

A Spectral Decomposition Framework for Multiscale Nonlinear Dimensionality Reduction
Apr 2, 2026Zeyang Huang, Angelos Chatzimparmpas, Thomas Höllt +1Dimensionality Reduction Spectral Methods
Linköping University, Sweden · Utrecht University, The Netherlands · University of Bergen, Norway +1
The ASE-LSE Disagreement Landscape: An End-to-End Characterisation of Extremes and Structural Drivers
May 21, 2026Minh Triet Pham, Ian GallagherGraph Embedding Spectral Methods
School of Mathematics and Statistics The University of Melbourne, Australia
ScaleMAP: Preserving Local Density and Neighborhood Structure in Low-Dimensional Embeddings
May 28, 2026Rajas Poorna, Marcus T. CiceroneData Visualization Manifold Learning
Georgia Institute of Technology · School of Chemical and Biomolecular Engineering Georgia Institute of Technology · School of Chemistry and Biochemistry Georgia Institute of Technology

Apr 2, 2026J/K move · Enter open · S save

A Spectral Decomposition Framework for Multiscale Nonlinear Dimensionality Reduction

Zeyang Huang, Angelos Chatzimparmpas, Thomas Höllt, Takanori Fujiwara

Linköping University, Sweden · Utrecht University, The Netherlands · University of Bergen, Norway+1

Dimensionality Reduction Spectral Methods

Open paper AskPDF arXiv

Dimensionality reduction (DR) involves two longstanding trade-offs. First, preserving local neighborhoods can come at the cost of global structure. Neighbor embedding methods such as t-SNE and UMAP prioritize local similarity preservation but do not explicitly constrain global organization, whereas standard spectral methods such as Laplacian Eigenmaps capture smooth, coarse-scale graph structure but offer limited flexibility to depict finer local structure. Second, the flexibility of nonlinear DR methods often comes at the cost of analytical transparency. Many methods do not explicitly reveal how high-dimensional structure produces patterns in the embedding. We introduce SDMP (Spectral Decomposition for Multiscale Projection), a nonlinear DR framework built on an explicit spectral decomposition. In this formulation, each embedding dimension is expressed as a weighted combination of Laplacian eigenvectors derived from a neighborhood graph, with the weights learned via a UMAP-style cross-entropy objective. By progressively expanding the spectral subspace to capture increasingly fine graph structure, SDMP produces a sequence of embeddings, making the evolving balance between global organization and local detail explicit, controllable, and inspectable. The explicit decomposition also reveals which spectral scales shape the overall embedding and how individual eigenvectors influence point positions. Quantitative evaluations on synthetic, image, and single-cell data show competitive local and global structure preservation, while case studies illustrate how the decomposition supports interpretation of clusters and developmental trajectories across spectral scales.

Abstract

Spectral Graph Embedding

Explore similar work

A Spectral Decomposition Framework for Multiscale Nonlinear Dimensionality Reduction

The ASE-LSE Disagreement Landscape: An End-to-End Characterisation of Extremes and Structural Drivers

ScaleMAP: Preserving Local Density and Neighborhood Structure in Low-Dimensional Embeddings