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
X^=UΛ1/2∈Rn×r,
Algorithm 1 Adjacency Spectral Embedding (ASE)
Figure 1: Left: the top 100 eigenvalues of the adjacency matrix, A , of the Bristol Road Network (see Section 5.2 for details of the dataset), where n=3857 . Right: the top 20 eigenvalues of W1/2AW1/2 , where W is a diagonal matrix of weights w1,…,wn>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).
X^=W−1/2UwΛw1/2∈Rn×r,
Algorithm 2 Local Adjacency Spectral Embedding (LASE)
X^n+1⊤=a~⊤UwΛw−1/2.
Algorithm 3 Inductive LASE
Figure 2: First two dimensions of the Mercer feature map ϕ (leftmost column) and the locally weighted feature map ϕw for increasing localisation (subsequent columns), controlled by the concentration parameter τ . We use μ=Uniform[0,10] and f(x,y)=exp(−21(x−y)2) . Top row: localisation around z≈1.5 . Bottom row: localisation around z≈7.5 . In each row, z⋆ is indicated by a red circle and latent positions z⋆±0.5 are indicated by red crosses. As τ increases, ϕw “zooms in” and better represents inner products for points likely under μw . All plots align ϕw(z⋆) to ϕ(z⋆) using Procrustes analysis.
Figure 3: The top 6 eigenvalues of P are plotted as the measure μw concentrates about a point. In each plot, the dimension d of the latent space 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(Zi) with varying concentration parameters τ∈{1,…,10} , centered at x=4 . Top right: RMSE of reconstructed probabilities P^ij versus true Pij , computed over nodes with latent positions in [3.5,4.5] , for each τ . 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 ±1 SE over 10 sampled graphs.
Figure 5: Column 1 : Latent positions within radius 1 of a central point, z⋆ . We call this the neighbourhood of z⋆ , and represent it by Nz⋆ . Column 2 : ASE is performed on the full graph into 3D, followed by PCA into 2D on embeddings of nodes in Nz⋆ . Column 3 : Subgraph SE is performed into 3D on the subgraph consisting of at least the nodes in Nz⋆ , followed by PCA into 2D on embeddings of nodes in Nz⋆ . Column 4 : LASE is performed into 3D on the full graph, with weights corresponding to latent position x∈Z set to exp(−0.4×∥x−z⋆∥2 ), followed by PCA into 2D on embeddings of nodes in Nz . The reconstruction RMSE associated with each embedding is recorded in the titles.
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 R2 statistic ( ± 1 SE) over 10 randomly selected neighbourhood centres. The right-hand plots show the mean-squared error ( ± 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.
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.
Zeyang Huang, Angelos Chatzimparmpas, Thomas Höllt +1
Linköping University, Sweden · Utrecht University, The Netherlands · University of Bergen, Norway +1
Two of the most widely used methods for analysing graph data, Adjacency Spectral Embedding and Laplacian Spectral Embedding, often produce different results when applied to the same graph. Yet the structural reasons behind this disagreement remain incompletely understood. This paper provides an end-to-end account of ASE-LSE latent subspace disagreement. We first prove that the two methods produce identical latent subspaces for every embedding dimension whenever the Laplacian is a scalar multiple of the adjacency matrix, and show that this scalar relationship holds if and only if the graph is either regular or bipartite biregular. This anchor result identifies a sufficient condition for perfect agreement that pins down the floor of the disagreement spectrum and supplies the baseline for the perturbation analysis. We then prove that no maximal-disagreement graph or family of graphs exists: the disagreement is always strictly below its theoretical ceiling, and we exhibit a witness family demonstrating that no finite maximum is attainable, so the disagreement landscape has no maximiser. With both endpoints established, we derive a Regularity Departure Bound whose two terms isolate degree heterogeneity and eigengap as the primary structural factors influencing disagreement in the middle regime. Empirical validation across thousands of simulated graphs confirms the mechanisms predicted by the bound: heterogeneity pushes disagreement up, eigengap suppresses it, and their joint ratio emerges as a unified predictor of ASE-LSE disagreement, suggesting when the two embeddings can be treated as interchangeable and when they cannot.
Minh Triet Pham, Ian Gallagher
School of Mathematics and Statistics The University of Melbourne, Australia
Nonlinear dimensionality-reduction methods such as UMAP and PaCMAP adaptively normalize local distances during graph construction, erasing neighborhood scale from the data. This distorts more than relative cluster sizes: sparse structures like bridges between transitioning cell types and narrow spectral spikes in hyperspectral images can be suppressed or lost entirely. DensMAP adds a density penalty to correct this, but this penalty competes with UMAP's attraction-repulsion forces, scattering points far from their neighborhoods. ScaleMAP takes a different approach: each pairwise embedding displacement is divided by the geometric mean of the two endpoints' original-space local radii, re-injecting scale information as a change of variables rather than as a competing objective. Across standard benchmarks and scientific datasets from transcriptomics, hyperspectral imaging, and flow cytometry, ScaleMAP matches DensMAP on density preservation while maintaining UMAP-level neighborhood preservation. In transcriptomic data, it recovers sparse bridges between cell populations that UMAP collapses; in flow cytometry, it faithfully represents density structure across 17 orders of magnitude. The same principle applied to PaCMAP yields consistently improved density preservation, suggesting the approach generalizes beyond UMAP.
Rajas Poorna, Marcus T. Cicerone
Georgia Institute of Technology · School of Chemical and Biomolecular Engineering Georgia Institute of Technology · School of Chemistry and Biochemistry Georgia Institute of Technology