Research map / Graph learning / Graph algorithms and clustering
Dynamic Metric Embedding into lp Space
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.
Gives the first decremental dynamic embedding of weighted undirected graphs into l_p space with O(log^3 n) expected distortion, built from a dynamically maintained weak decomposition, and shows fully dynamic explicit maintenance with high-probability low distortion is infeasible.
Problem
Maintaining a low-distortion randomized embedding of a weighted undirected graph's shortest-path metric into l_p space under a sequence of edge weight increases (decremental) or both increases and decreases (fully dynamic).
Approach
Replaces Frechet-style embeddings with a characteristic embedding built from random distance-preserving cuts (each coordinate is R_i if the vertex lies on the cut side, else 0), where the cuts are obtained from a random clustering (weak decomposition) with random side assignments; the cuts are then maintained decrementally by extending a deletion-only weak-decomposition algorithm to edge weight in
Key results
- Dynamic embedding into l_p with expected distortion O(log^3 n) and total update time O((m^{1+o(1)} log^2 W + Q log n) log(nW)) under edge weight increases.
- Fully dynamic explicit maintenance with distortion o(W) whp requires Omega(n) update time per step (lower bound via two cliques joined by an edge whose weight is toggled).
- Empirical experiments on LastFM subgraphs show the average-distance ratio is within a constant factor of exact averages, per the authors.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Maintain distance-preserving cuts at multiple scales and use them for a characteristic embedding | Dynamic metric embedding · Decremental weighted graph | expected distortion: O(\log^{3}{n}) | Helped |
| Allow edge-weight increases and decreases rather than increases only | Explicit dynamic \ell_p embedding · Fully dynamic weighted graph | update time: \Omega(n) | Hurt |
Surprising findings
- Fully dynamic explicit embeddings with low whp distortion are infeasible, requiring Omega(n) updates per step, although expected-distortion guarantees avoid this lower bound.
Limitations
- Only edge weight increases are supported; decreases (and fully dynamic setting) are not handled with low distortion whp.
- Expected distortion only; the embedding is not contractive deterministically.
- Empirical validation is small-scale (150-600 node subgraphs) and the paper does not report compute details.
Experimental setup
Datasets: LastFM Asia social network (SNAP)
Benchmarks: LastFM Asia subgraphs of 150, 300, 600 nodes
Metrics: ratio of average pairwise distance under embedding to exact
Baselines: Frechet embeddings FRT embedding dynamic APSP oracles
Builds on: Bourgain embedding Bartal probabilistic decomposition Forster-Goranci-Henzinger-type decremental clustering Johnson-Lindenstrauss lemma FRT embedding
Closest papers by meaning
- Fully Dynamic Embedding into $\ell_p$ Spaces (ICML 2025 · similarity 0.95)
- Weighted Embeddings for Low-Dimensional Graph Representation (AAAI 2025 · similarity 0.85)
- Beyond Vector Spaces: Compact Data Representation as Differentiable Weighted Graphs (NeurIPS 2019 · similarity 0.85)
- Quality Measures for Dynamic Graph Generative Models (ICLR 2025 · similarity 0.84)
- Dynamic Facility Location in High Dimensional Euclidean Spaces (ICML 2024 · similarity 0.83)
- Euclidean Embedding of Data Using Local Distances (NeurIPS 2026 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.