Research map / Graph learning / Graph algorithms and clustering

Euclidean Embedding of Data Using Local Distances

NeurIPS 2026 · Graph learning › Graph algorithms and clustering · approach: Graph embedding and spectral sparsification · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes a variational, representation-free Euclidean embedding from a local distance graph, solved by an iterative sparse-linear scheme that aligns local frames with functional differentials.

Problem

Recovering a globally consistent Euclidean embedding of data using only local (neighborhood) distance graph information, without feature vectors, while approximating IsoMap's global isometry.

Approach

Formulates embedding as a functional optimization matching on-graph differentials of embedding functions to metric-trivializing 1-form transports; Euler-Lagrange equations are coupled with an SVD-based orthogonal alignment, solved by alternating sparse Laplacian solves with a convergence guarantee.

Key results

• On the RNA-seq lung cancer data, the proposed method achieves ACC 0.7126, NMI 0.3298 and ARI 0.3821, the best of the compared methods including UMAP (ACC 0.7040).
• On RNA-seq, the proposed method reaches the highest local F1 (0.7698) while its global stress (0.1589) is close to IsoMap's (0.1519).
• On the Klein's bottle, the proposed method attains Lcl-F1 0.91 and Glbl-Pearson 0.95, versus IsoMap's 0.81 and 0.98.

Surprising findings

• On MNIST, t-SNE and UMAP outperform the proposed method in clustering accuracy despite lower neighborhood preservation, as the paper attributes this to density-based arrangement.

Limitations

• Only local symmetric relations are used, so global shape and non-neighbor relations are not captured; out-of-sample extension requires recomputation with Nystrom.
• Operators are second-order approximations, so outliers in neighborhoods can degrade the operator estimates.
• Method is non-parametric and recursive, lacking a functional mapping for new points.

Experimental setup

Datasets: swiss roll difficult 5-manifold in R^10 (Hessian/benchmark set) flat torus Klein's bottle MNIST test set FMNIST test set RNA-seq lung cancer dataset (1625 cases)

Benchmarks: swiss roll unfolding Klein's bottle torus MNIST FMNIST RNA-seq lung cancer

Metrics: Lcl-mtrc Lcl-F1 Glbl-Pearson Glbl-mtrc stress Glbl-prm procrustes error ACC NMI ARI

Baselines: LLE LTSA Laplacian Eigenmaps Hessian Eigenmaps IsoMap Diffusion Maps t-SNE UMAP

Builds on: IsoMap UMAP Locally Linear Embedding Laplacian Eigenmaps

Closest papers by meaning

• Weighted Embeddings for Low-Dimensional Graph Representation (AAAI 2025 · similarity 0.88)
• Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimization (NeurIPS 2024 · similarity 0.88)
• Finsler Multi-Dimensional Scaling: Manifold Learning for Asymmetric Dimensionality Reduction and Embedding (CVPR 2025 · similarity 0.88)
• Graph Geometry-Preserving Autoencoders (ICML 2024 · similarity 0.87)
• MetricEmbedding: Accelerate Metric Nearness by Tropical Inner Product (ICML 2025 · similarity 0.87)
• Aligning Embeddings and Geometric Random Graphs: Informational Results and Computational Approaches for the Procrustes-Wasserstein Problem (NeurIPS 2024 · similarity 0.87)