Research map / Learning theory and algorithms / Prediction and decision losses
Fully Dynamic Embedding into $\ell_p$ Spaces
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 fully dynamic algorithm that maintains a random embedding of edge-weighted graph metrics into ℓp spaces under edge insertions and deletions, with low expected distortion, non-contractivity w.h.p., and a lower bound showing explicit maintenance of such embeddings is impossible efficiently.
Problem
Maintaining low-distortion embeddings of dynamic graph metrics into ℓp spaces under fully dynamic edge insertions and deletions, where each embedding update must be efficient.
Approach
Embed via distances in a dynamic low-distortion tree (with edge-dominant property) whose edges are randomly scaled by factors in {1,2} to add noise, repeated Θ(log n) times and queried implicitly via root-path sums, avoiding explicit output of embedding changes.
Key results
- Achieves O(log n)^2 * 2^{O(log(nW))^{q-1}} expected distortion with O(m^{1/q+o(1)}) amortized update time and O(q log n log(nW)) query time for integer q≥2.
- Embedding is non-contractive with high probability, in contrast to the decremental predecessor's O(log^3 n) distortion.
- Lower bound: any fully dynamic algorithm explicitly outputting embedding changes while keeping sublinear expected distortion and non-contractivity requires amortized update time Ω(n).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Maintain a fully dynamic ℓp embedding using dynamic edge-dominant tree embeddings and randomized edge weights | Fully Dynamic Embedding into ℓp Spaces · Fully dynamic weighted graph metrics | expected distortion: O(log(n))2qO(log(nW))q−1 | Helped |
| Maintain a fully dynamic ℓp embedding using dynamic edge-dominant tree embeddings and randomized edge weights | Fully Dynamic Embedding into ℓp Spaces · Fully dynamic weighted graph metrics | amortized update time: m1/q+o(1) | Helped |
| Maintain a fully dynamic ℓp embedding using dynamic edge-dominant tree embeddings and randomized edge weights | Fully Dynamic Embedding into ℓp Spaces · Fully dynamic weighted graph metrics | query time: O(q log(nW) log(n)) | Helped |
| Explicitly output every vertex embedding change | Dynamic embedding algorithms with sublinear expected distortion and non-contractivity · Explicitly maintained dynamic embeddings | amortized update time: Ω(n) | Hurt |
Surprising findings
- Explicitly maintaining a non-contractive, low-distortion embedding under fully dynamic updates is impossible efficiently, motivating implicit query-based maintenance.
Limitations
- Distortion bound is exponential in (log(nW))^{q-1} and polylogarithmic factors are large in practice.
- Theory-only; no empirical evaluation reported.
- Embedding is only implicitly maintained; explicit output of changes is provably impossible efficiently.
Experimental setup
Metrics: expected distortion non-contractivity amortized update time query time
Baselines: Banihashem et al. 2024 decremental embedding
Builds on: Bourgain embedding Forster et al. 2021 dynamic tree embedding Banihashem et al. 2024 decremental embedding Low diameter decomposition pruning (Chechik & Zhang)
Closest papers by meaning
- Dynamic Metric Embedding into lp Space (ICML 2024 · similarity 0.95)
- Euclidean Embedding of Data Using Local Distances (NeurIPS 2026 · similarity 0.86)
- Weighted Embeddings for Low-Dimensional Graph Representation (AAAI 2025 · similarity 0.86)
- How Low Can You Go? Searching for the Intrinsic Dimensionality of Complex Networks using Metric Node Embeddings (ICLR 2025 · similarity 0.85)
- Embedding Dimension of Contrastive Learning and $k$-Nearest Neighbors (NeurIPS 2024 · similarity 0.85)
- MetricEmbedding: Accelerate Metric Nearness by Tropical Inner Product (ICML 2025 · similarity 0.85)
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.