Fully Dynamic Embedding into $\ell_p$ Spaces
Authors: Kiarash Banihashem
Xiang Chen
MohammadTaghi Hajiaghayi
Sungchul Kim
Kanak Mahadik
Ryan A. Rossi
Tong Yu
Venue: ICML 2025 poster (2025)
Keywords: Dynamic algorithms
Embedding
Primary area: theory->everything_else

Abstract: Metric embeddings are fundamental in machine learning, enabling similarity search, dimensionality reduction, and representation learning. They underpin modern architectures like transformers and large language models, facilitating scalable training and improved generalization.
Theoretically, the classic problem in embedding design is mapping arbitrary metrics into $\ell_p$ spaces while approximately preserving pairwise distances. We study this problem in a fully dynamic setting, where the underlying metric is a graph metric subject to edge insertions and deletions.
Our goal is to maintain an efficient embedding after each update.
We present the first fully dynamic algorithm for this problem, achieving $O(\log(n))^{2q} O(\log(nW))^{q-1}$ expected distortion with $O(m^{1/q + o(1)})$ update time and $O(q \log(n) \log(nW))$ query time, where $q \ge 2$ is an integer parameter.

Fully Dynamic Embedding into lp Spaces
Kiarash Banihashem Xiang Chen
Mohammad Taghi Hajiaghayi Sungchul Kim Kanak Mahadik 2
Ryan A. Rossi
Tong Yu
Abstract
done in many ways, the usual goal in embedding design is to ensure small distortion, i.e., we make sure that the distances are approximately preserved.
Metric embeddings are fundamental in machine learning, enabling similarity search, dimensional- ity reduction, and representation learning. They underpin modern architectures like transform- ers and large language models, facilitating scal- able training and improved generalization. The- oretically, the classic problem in embedding de- sign is mapping arbitrary metrics into lp spaces while approximately preserving pairwise dis- tances. We study this problem in a fully dy- namic setting, where the underlying metric a graph metric subject to edge insertions and deletions. Our goal is to maintain an effi- cient embedding after each update. We present the first fully dynamic algorithm for this prob- lem, achieving
Low-distortion embeddings with "simple" target metric spaces V' effectively simplify the original metric while ap- proximately preserving distances. This can be useful from an algorithm design perspective as quite often, the problem is much more approachable the simpler metric, especially from a computational perspective. Because of this, many works have previously studied such embeddings for a va- riety of target metrics such as ly spaces (Bourgain, 1985) and hierarchical trees (Bartal, 1996a; 1998; Fakcharoenphol et al., 2004). closely related line of work also examines the problem of maintaining low-stretch spanning tree of graph (Alon al., 1995; Elkin et al., 2008). These em- beddings have been used to obtain algorithms for variety of problems such as sparsest cut (Linial al., 1995), net- work design (Awerbuch & Azar, 1997; Garg al., 2000), minimum bandwidth (Blum et al., 1998), and metric label- ing (Kleinberg & Tardos, 2002)
(log)))((())))))) ex- pected distortion with ((m-/4+o(1) update time and Og (nn(n) Iog(nW)) query time, where 2 2 is integer parameter.
1. Introduction
Embeddings are a cornerstone of modern machine learning, powering models from word2vec large language mod- els (LLMs). These methods represent discrete data-sud as words, entities, tokens continuous metric spaces, enabling geometric reasoning about semantic relationships. This makes embeddings useful for tasks such as node classi- fication, link prediction, and community detection (Zhang & Chen, 2018; Abu-El-Haija et al., 2018; Yun et al., 2021; Davison et al., 2024) Among embedding targets, lp spaces (especially f2) have emerged as the standard representation space in much of modern machine learning. This due to (a) their aaterpretabliiyyddsttae distances and angles have clear geometric meaning- and (b) the fact that many key com- putational primitives are substantially more efficient Ep spaces. For example, nearest neighbor search in high dimen- sions is routinely performed using locality-sensitive sensitive hashing (LSH), technique specifically designed for lg and other vector norms.
Metrie embeddings are fundamental computer science, with applications in machine learning, databases, and net- work design. In ML, they are critical for tasks like similarity search, dimensionality reduction, and representation learn- ing, underpinning modern architectures such as transform- ers and large language models (Vaswani, 2017; Kenton & Toutanova, 2019). By enabling efficient and context-aware representations of high-dimenn sigh-dimensional data, embeddings drive scalable training and task generalization, making them es- sential for advancing state-of-the-att models.
From theoretical perspective, the classic formulation of metric embedding problem is as follows. We are given a set of points in an input metric space M = (V, d), and we want to map (i.c., embed) each point E V to point o' e V' in a target metric space M' = (V', (V',d') d'). While this can be
University of Maryland, College Park è Adobe research. Cor- respondence to: Kiarash Banihashem <kiarash @ edu.
In the past decade, motivated by the surge of interest in mod- ern Big Data applications, there has been a renewed interest in studying classical problems in a dynamic setting, where the underlying input is constantly changing and the goal is to
Proceedings of the ndd International Conference on Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Fully Dynamic Embedding into Ep Spaces
always maintain good solution. This is considerably more difficult than the static setting, where the entire input is fixed and given upfront, the algorithm needs to quickly adapt to (adversarial) changes in the data. For dynamic mainte- nance of low-stretch spanning trees, (Forster & Goranci, 2019) obtained an algorithm for unweighted graphs with n1/2+o((1) update time and (1 average stretch. The update time was further improved to o)) by (Chechik & Zhang, 2020). This was achieved by developing new pruning tech- nique for obtaining Low Diameter Decompositions (I.DDs), which partition the graph into clusters with bounded di- ameter such that the number of inter-cluster edges is low. Building on this pruning technique, (Forster et al., 2021) ob- tained a dynamic algorithm for embeddings into probabilis- tic trees which has distortion and Omm-/9+o0)) update time where q 2 is an integer parameter. A separate line of work studies online algorithms for embeddings, where the focus is generally on making irrevocable decisions rather than minimizing com- putation (Indyk al., 2010; Barta et al., 2020; Newman & Rabinovich, 2023).
contractive with high probability, showing that efficient algorithm with these properties cannot be obtained in the fully dynamic model.
1.1. Our Results
We study a fully dynamic setting in which the edges of a graph = (V, E) are inserted and deleted, and each edge has some weight in the range {1..... W]. Since we study low-distortion embeddings into the lp metric where the dis- tance between any two points is never +o0, we will assume that any two vertices in different connected components are in distance W" >> nW (whereas normally one would assume that their distance is +00). Intuitively, this is assum- ing that there is always "default" edge between any two vertices with very high weight, even if there is no edge E E connecting them.
(Iog( - expected
Our goal is to randomly maintain a low-distortion embed- ding function p:: V + R that can efficiently calculate the embedding of a queried vertex. We note that, while our choice of the embedding function is random, the function itself is a deterministic mapping. In other words, while changing the random seed of the algorithm will change the function p but for any fixed seed, the function p will not change unless the graph changes.
In this work, we focus on the problem of dynamically em- bedding into ép spaces. In the static setting, the seminal result of (Bourgain, 1985) shows that any metric can be embedded into l, space with O(log n) distortion and using Olog" n) dimensions. This was later shown to be tight by (Linial al., 1995). Recently, (Banihashem et al., 2024) studied this problem in restricted dynamic setting, referred to the decremental setting, which only allows for the edge weights to be increased. They obtained an algorithm log(n)) lo)(nW)) total update
Our main result is the following theorem.
Theorem 1.1. Let G EV) be a weighted undirected graph undergoing edge insertions and deletions. For any q 2 2, there exists algorithm A (see Algorithm 1) that randomly maintains an embedding function p : V + R with the following properties:
((m ((m)/2+0(1) log" (W)+ (W)) time and (log" r)) expected distortion, where W refers to the largest weight in the graph and Q denotes the number of updates. Their techniques do not generalize to the fully dynamic setting, where distances can both increase and de- crease; the main idea behind their approach is to directly turn the information provided by the decremental L.Ds of (Forster et al., 2021) into coordinates for the lp space and it is not clear whether a fully dynamic version of these LDDs can be obtained. They additionally obtain a lower bound showing that any algorithm that maintains an embedding that has low distortion with high probability, and explicitly outputs all changes the embedding of each vertex, cannot be fully dynamic.
Low expected distortion and non-contractivity. For any two vertices u, U,
E (ll(u)) - p(u)ll S ((Dog(n))*0(((gguuu)))++)
1 1
du(
where the expectation is over the randomness in choos- ing P. Furthermore, with high probability", the embed-
'In this work, we consider the oblivious adversary model, in which the updates are specified by an adversary who knows algorithms but does not have access to the random bits we use; see Section 2 for more details.
In this paper, we circumvent this negative result by pro- viding a fully dynamic algorithm for the problem which maintains the changes implicitly via a function p that can efficiently be queried, and has low expected distortion. Our embedding has the additional guarantee that it is non- contractive with high probability. We further strengthen the lower bound of (Banihashem et al., 2024) by extending to embeddings with low expected distortion that are non-
"The infinite distances is also noted by (Banihashem et al., 2024), who study the decremental case. They handle this issue by assuming that the input graph is originally connected and only allowing edge weight increases (and not deletions) ensure the graph remains connected.
'Thoougoou the paper, we use the term with high probability to denote prohabilities 1 1- 1/n" where a arbitrarily large constant.
2

---

Fully Dynamic Embedding into Ep Spaces
ding is non-contractivee i.e.,
The upper bound follows from the triangle inequality for the metric de. Fix any vertices u and v. For any E [h] we have
Ilp(u)= p(c))l 2 do(u, v) for all U.
Efficient update time. the amortized update time of the algorithm is m /l)oo((1) with high probability.
dd u) - (s, w)] - Ido(u, w)
(3)
by the triangle inequality; summing over all i we obtain Il(()) - -(x) s lIl(2) - p(v) - hlda(u, w)|-
Efficient query time. For any vertex V E V, we can calculate p(v) in time O(g log(nW) log(n)..
The proof of the lower bound is more involved. The main idea is to show that the sets S, are likely to be "close" to one of u and v and "far" from the other. Specifically, let ry to be the smallest radius such that [B rz)), (B 2 2 where Bax, r) denotes the (closed) ball with radius r with center x. If 2 da uc)u,)),, then reduce it to da(u, e)/2, i.e., set r, the minimum of the two mentioned values. We note that P4 dc v)/2 because the minimum radius to include all the points is at least da(u, v). and To O because E (2,, 0) for any vertex E [Ida(S., u) da (S:, w)l] 2 c c(r; -r-1) for some con- stant c. We note that this implies the lower bound because
We further show that if we require that each update to the embedding is explicitly outputted, then no such result can be obtained, even if the expected distortion is only required to be sublinear.
Theorem 1.2. Assume that the algorithm A is a fully dy- namic algorithm for maintaining a random embedding p: V + Re with the following guarantees:
1. Sublinear expected distortion and non-contractivity: da(u, v) < E [p(u)- p(u)]= S ((W))dc(u, v) and the embedding is non-contractive with probability at least 3/4.
We claim that
2. Explicit changes: any change to the embedding of a vertex v is explicitly outpulted by the algorithm.
[1l((u)) p(o)))(())))))))
Σ (d. u) -d)(Ss))
The amortized update time of the algorithm A is at least Mn).
h
c c(rs - r2-1) crb. Σ
1.2. Overview of Techniques
which is at least M(dc(u,)) To prove the claim, we assume that Ti > Ti-1 since otherwise holds trivially.
We next present an overview of our proofs. We start by briefly recapping the standard approach for constructing l embeddings in the static setting. We then examine a natural algorithm based on this approach and explain why fails in the dynamic setting. Finally, we present a new algorithm based on these failures and briefly outline its proof of correctness.
By definition of ris we have min (I - 1)1, 1)1) < 2 assume w.l.o.g that [B(u, - 1)] < 2'. Since r. + fi-1 1 < 2r, - < dg v), the sets B₁ == B(v,r=-1) and Bg =
do not intersect. Furthermore, |B| > 2 and [2 < 2', Therefore, with constant probability, the set 5 intersects B1 but does not intersect By, the probability of each of the two events are constants given the size of the sets and the events are independent because B, n B2 = 0. When this happens, we have do(S;, u) 2 rs and do(S v) S ri-1, finishing the proof.
Recap of static approach. We start by briefly recapping the standard approach for embedding into Ep spaces. Set h [l. For each E [h], we obtain the set St by uniformly sampling the vertices in V with probability p; := $. For any vertex v, define its embedding to be the concatenation of its distances from S,* Formally, p(r) := (da(S), v), (Sh, v)), where (s v) de- notes the distance between v and the closest vertex in S; i.e., (o, v)= == minngges do(us, v). We claim that sat- isfies the desired bounds for the expected distortion. We focus on the & norm for simplicity; the results for the other norms follow directly at the cost of an additional log factor given the incquality (p(u)) - p(u)) < [Ip(u)) - p(v)]l1 < log(n) (lp(u) - p(v)]lp-
Candidate dynamic algorithm. To implement this algo- rithm dynamically, a natural approach is to use dynamic distance oracles, which can calculate the distance between any two vertices, to obtain da(S; (S;..) u). Note that while S; is set of vertices and not single vertex, we can contract the set St into single vertex and run the distance oracle on the contracted graph. The problem with this approach however is that dynamic distance oracles only obtain approximate dis- tances and the approximation breaks the triangle inequality in Equation (3). Specifically, denoting the distance esti- mates with d(.,,), if u and are close to each other but are both far from S., then a (1 + apprroixiee distance oracle
"The standard construction uses log n independent copies for each St to ensure high probability bounds; for simplicity we skip this step as our main focus is on expectation bounds.
3

---

Fully Dynamic Embedding into Ep Spaces
has an error up to (S, u) when calculating dS(S, u) and de (St; v), which means (d,, u) (S, r)] can be much larger than da u). The proof for the lower bounds also breaks down; the approximation error for the distance oracle changes the bound on Ida(S, u) (S, e) to - (1 + e)r; which is not desirable and may even be nega- tive.
of (u, = (EeEP... wr)² which we require for the proofs. To solve this issue, we will rely on a property of existing dynamic tree embeddings which, the best of our knowledge, was not previously noted. Specifically, show that the path between any two vertices in V contains "heavy" edge whose weight is within a small factor of dr(u, v) itself. This allows us to show that the (undesired) concentration effects do not hold here and we can still re- cover the lower bound.
Low-distortion trees. Our solution to the above issues is to obtain the distance estimates by calculating distances in another metrie; specifically, distance in trees." This allows us to circumvent the issue with Equation (3) by invoking the triangle inequality in the new metric. Specifically, let be some fixed vertex in the tree (e.g., the root), and consider the embedding p(u) == (s, u). Then for any two vertices and v.
Lower bound. The proof for the lower bound uses a "bridge graph" which was also used by (Banihashem et al., 2024). Specifically, we consider a graph with two separate cliques of size n/2, which we repeatedly connect and dis- connect. The fact that the embedding is non-contractive with high probability means that each time the edge is re- moved, the two sides need to be in distance W'. When the edge is added back however, the two sides need to be close again. Using the expected distortion guarantee and Markov's inequality, we conclude that for any fixed u and e that are in different components, with high probability, pl(()) - p(v)]] must change after each update, which can only happen if at least one of p(u) and p(v) change. Since there are ((n2) pairs, this means that we require at least (()) changes.
(p(u)- p(v)) = [dr u) dr(s, S dr(u,, v),
which is small in expectation provided the tree T itself has low expected distortion. This fixes the issue with the proof for the upper bound.
For the lower bound proof, our key insight is to, somewhat counter-intuitivelyy inject noise into the distance estimates. Specifically, instead of working with the tree 7 directly, we modify it by multiplying the weight for each edge by a random number taken uniformly from {1, 2). The main idea here is that if u and v are far from each other, then their path to the root must be very different. Since the multiplication factor chosen independently for each edge, this means that the noises themselves ensure that the lower bound holds.
2. Preliminaries
Notation. For any positive integer kt we use [k]] de- note the set (l. We use G = (V, E) to denote the weighted graph being updated and use p denote the em- bedding we maintain. We use and m to denote the number of vertices and edges in G respectively and the weights are assumed to be integers in the range [1, W]. For any edge E G. we use (e(e) to denote its weight. We drop the de- pendence on G when it is clear from context. For any graph G, we use (c....) to denote the shortest path metric in the graph. If two vertices u and v are not in the same connected component, we set da(u, v) = W' where W' > nW is a large integer. For any two vertices u and v and a tree T we will use p", to denote the (unique) path between u and v (assuming both vertices are in the same component), dropping the dependence on T when it clear from the context.
Formally, as we show in Section 4, one can break the path Pa.e between u and in the tree T into two parts P and Py such that
us) - (s, =3 Σ (e)
Σ (e), EEP:
eEP:
where 7" refers to the new tree obtained after randomly modifying edge weights. We note that our choice of P and Pr does not depend on the scaling factors for T" If the independent noises for the scaling of each edge simply combined, they would equate to Eeep, (r) 2 dr(u, (u, v). which would give the desired lower bound. This is not the case in general however because of concentration; the vari- ance in the above difference equals Eeer... Var Bar(wr:(4 (e))
Given a graph G', we will often use V(G') and E(G') to de- note the vertices and edges of the graph respectively. Unless otherwise stated, V and E refer to the vertices and edges of the input graph G which is undergoing edge insertions and edge deletions.
which is (EeEP... (e)(e) given the choice of scaling factors. This can be much less than the desired variance
'Technically, since the graph G can be disconnected, we will be considering forests. Since any forest is simply a collection of separate trees however, we use the terms interchangeably unless the distinction is important (in which case we point this out).
Embedding. We use p: V + V to denote an embedding from a metric space (V, d) to a metric space (V,d') In this paper, we will generally work with random embeddings.
4

---

Fully Dynamic Embedding into E Spaces
These are embedding functions p that are chosen, randomly, from larger set P. Importantly, the function p itself is deterministic. i.e., querying p(v) multiple times will always lead to the same answer. Our choice of the function p will be random.
value changed and what the new value is. In fact, our lower bounds show that, in the model we are considering, explic- itly maintaining low-distortion embedding is not possible. Note that explicit maintenance is possible in a variant of the decremental model where the edge weights increase but there are no deletions (Banihashem et al., 2024).
We say a (randomly chosen) embedding p has expected distortion a if, for any u, U. e V,
3. Fully Dynamic Embedding
d(u, v) S E (dd'(p(() I ud(
In this section, we present our dynamic algorithm for the problem. Our algorithm assumes access to a fully dynamic algorithm for embedding the metric into trees in which the path between each two vertices contains a heavy edge with length comparable to the total path length. Formally, we define the concept of edge-dominant trees below.
and say it non-contractive if
Vu, v: :d''d (o(()),((v)) 2 d(u,v).
In this paper, we will consider mainly two target metric spaces V" for the output embedding, The first choice metric embedding into trees, or more generally forests. The second choice is the set of real-valued vectors Hº with the ep norm 1/r || - vllp == (E (x]li] - -(il)²) where rii] denotes the i-th coordinate of x. We note that distances can be infinite for graphs and forests if two vertices are not in the same connected component. However, for any two points x, y in RR,, we have || ullp < +oc. Given this discrepancy, when considering embedding into lp spaces, we define the input metric -c)..-) as the shortest path metric for any two vertices that are in the same component, and define it as W" for any two vertices that are not in the same connected component of G. This is essentially stating that even if there is no edge e E E between two vertices, one can still move from one to the other with weight W'. Note that, since W >> nW and edge weights are in range [W], the distance between any two vertices that are the same component is less than the distance between two different components.
Definition 3.1 (edge-dominant trees). We say a tree T is edge dominant with parameter 8 < 1 if for any path (uI....,uy) in the tree, where eú are vertices of the tree, there exists an edge (e;, 1,+1) in the path satisfying wr Ut+1) 2 3dr(v1, We say a forest T is edge dominant if all the trees in the forest are edge dominant.
The following lemma shows that an edge dominant forest with low distortion can be maintained dynamically. In order to effectively leverage the existing results for embeddings into trees, for this lemma we assume that the forest maps different connected components of the input graph to sep- arate trees; i.e., we do not assume that there is a "default" edge of weight W' between any two vertices. We will later add these default edges in our algorithm to connect different components.
Lemma 3.2. For any q 2 2, There exists an algorithm which has m 1/100(11) amortized update time with high prob- ability and embeds the graph into a rooted forest T with the following properties.
Dynamic model. We consider fully dynamic model in which the edges of graph G = E) are inserted and deleted, and the goal is to always maintain an embedding into the ly space. In this work, we operate in the oblivious adversary model for dynamic algorithms which is stan- dard model for dynamic algorithms (Henzinger al., 2018; Forster et al., 2021; Banihashem et al., 2024). This means that an adversary chooses the update stream with knowledge of our algorithm, but without knowing the random bits we use or the output embedding we maintain. This is equivalent to assuming that the adversary specifies all of the updates before our algorithm is started.
1. Each tree in the forest has height at most Olg log(nW)).
2. For any two vertices u and u, we have dr(u, v) 2 (u v) and E [dr(u, w)] < a,da(u, v) where ag S
([oog))))++>((log( (Olog(WW)))>> Here do(u, v) is set to too if and v are in different components of G.
3. The forest is edge dominant with parameter By = 4 3-9.
Throughout its running time, the algorithm outputs all changes made to the forest.
Our algorithm will maintain an embedding function o which can efficiently be queried. This is in contrast to explicit maintenance of an embedding where the algorithm is re- quired to explicitly output all changes to the embeddings of the vertices, i.e., which vertices have had their embedding
We refer to Section C for the proof of the lemma which is based on the dynamic embedding of (Forster et al., 2021). While the depth of the tree and the upper bound on expected distances have already been established, our result on the existence of a heavy edge in each path is, to the best of our
5

---

Fully Dynamic Embedding into Ep Spaces
knowledge, novel.
n vertices and no edges to be mapped to tree T with vertices and no edges, this is not the case. In order the tree embedding algorithm in Lemma 3.2 to avoid making (n) operations at initialization due to outputting the "new" ver- tices V added to the tree, the algorithm does not explicitly create vertex in the tree for each vertex in the graph at the start of the algorithm. Rather, it only creates corre- sponding vertex in the tree once there is an edge connected to the vertex. As such, technically the value Te may not be available for a vertex v: if it is isolated, prohibiting us from calculating p(v); specifically, we run into an error in Line 19. This issue can be easily fixed however; if such a value is not available, we sample the value Yo at the query time and add it to the hash table. If a corresponding vertex is created later on, we simply replace the value. Since the operation is (1), it does not affect the update time bounds.
To simplify the presentation, we will actually build an embedding that satisfies a scaled version of the guaran- tees in Theorem 1.1; specificallly, we will ensure that 9e 2 da((u, v) I E [llp(u) p(u))lz] S ag (og(()))((( dd (u, v), where ag. Sg are chosen in Lemma 3.2. Additionally, we will show that [lo(u) - plu)ll 2 f da v) with high probability. Scaling the embedding by 8,/2 proves Theo- rem 1.1.
Given the forest obtained from Lemma 3.2, our algorithm works as follows. We first create a new vertex and connect the root of each tree in the forest to s with weight W This effectively turns the forest into a tree, where vertices that used to be in separate components are now in distance @(W"). We then multiply each edge e in the tree by random number Ye chosen uniformly at random from {1,2], obtaining new tree T".
A Algorithm 1: Dynamic embedding into Ep metric.
In order to obtain the embedding p(.) of vertex v, we repeat this procedure k (logn) n) times and set p(t) to 2 Set k (log
Function Init ():
be the concatenation of the distances of v to the root in each of these trees. As we will see in the analysis, the exact choice of constant behind log n. for choosing k will control the high probability guarantees we provide for non- contractivity; for any a 2 1, we can ensure that the tree is non-contractive with probability 1 - 1/n² by choosing a large enough constant.
3
Initialize dynamic forest embeddings Ti...., Th
(See Section C) and empty hash tables
HI...., H3:
Function Update (u):
// Insertion or Deletion
s
for i E [k] do
(Vnas, Vremove; + Update(Zi,
// Forward to T; and store new and deleted vertices in Tj
For simplicity, we will not store T' directly and make the following changes. Firstly, instead of storing a value Ye for each edge, we store a value Yo for each vertex u o s in the tree T". This is clearly equivalent because we can associate each edge in the tree with its lower vertex. Secondly, we store the value of Yo in a hash table, adding and removing values as vertices are created and deleted in T. In order to obtain the distance of vertex from 8, we simply traverse the path from the node to its root, summing up the weight of the edges multiplied by Yv. A formal pseudocode is provided in Algorithm 1.
for each v in Vremove do Remove (v, Yo) from H;; for each v in Vadi do Sample Yo uniformly at random from {1,2} 2]: Add (v, (v) to H;;
10
II
12 Function Query (u):
for i E { do
13
14
p f- u. (u) + 0;
As we will see in the next section, the multiplication by To plays a crucial role in the analysis. In the original tree T, it is possible that two vertices have similar distances to the root, even if they are far from each other. This is not acceptable however as we require vertices u and v that are far from each other two have accordingly far values in the embedding. By multiplying Ye. we are effectively adding noise to the distances. The size of this noise is roughly equal to dr(u, v) itself, ensuring that the embedded values are far as well. Furthermore, repeating the procedure k times allows us to ensure that the embedding is non-contractive with high probability.
15
while p $ root(T)) do
16
Retrieve 7pp from H;;
(v())= + p((u)) + ur; (p. parenty, (p)) 7pp
17
18
p parenty; (p):
(1(u) + p.(u) + w" .7p:
19
return p(u) =
pb (u))
4. Analysis
In this section, we prove our main result, i.c., Theorem 1. The update time analysis of the algorithm follows by charg- ing each operation to corresponding tree operation; since the update time of the trees is bounded as in Lemma 3.2, the
Remark 3.3. While ideally we would want a graph G with
6

---

Fully Dynamic Embedding into Ep Spaces
claim follows. Since we maintain (1log(n) trees, our up- date times are factor (og(n) higher than that of Lemma 3.2, but this is absorbed by the m²(1) term in the updates. The only extra operation we make is maintaining Ye, which can be charged to the running time of the tree embedding algo- rithm the changes to I are directly outputted. Since sam- pling, storing, and removing each Te) pair is O(1), this only affects the update time by constant. As for the query time, since the height of tree is at most Og (og(n)),, we can output the embedding in time Oig log(nW)) as well. Note that the extra samplings of T/e specified in Remark 3.3 do not affect this as sampling only takes (1) time.
where we have used, respectively, the definition of p and the triangle inequality. Since "e 2, this is most 2dr v). Therefore, E [lp(()) p(e)]] - 21E (u, u)] is at most
(loog())) (- ([log(n))<<=(((g(((())))))) do(u.
where the inequality follows from Lemma 3.2
Lower bound on expected distance To establish the lower bound, we begin by observing that since T is a tree, p(u) - p(v) can be obtained by breaking the path between u and v into two parts and taking the difference between the length of these parts. Formally, let Pu and P. denote the paths from the root denote the longest sub-path appearing in both Pa and P.. Let Pa = PP and P = PpY denote the remainder of the paths for and v.
We now focus on the analysis of the distortion for our embed- ding. We will show that for any two vertices u and v and any coordinate i [k]. the expected difference between pi(u) and (1()) satisfies the following upper and lower bounds.
and e respectively and let p
Bg do u) - (1) p:(1)]]] S vd)
Observe however that P := P', + P/ (i.e., the concatena- tion of P and Pt) is the unique path from u to v. Formally, letting ū denote the last vertex in P', one can get from the vertex u to û by following P", and get from i to v by follow- ing P/ This is indeed a path (i.e., does not contain repeated vertices) because if a vertex, say ö, appears in both P. and Ph, then there is a sub-path in both Pa and P. from ū to ē. Since the tree does not contain any cycles, this sub-path must be the same in both P and PV, contradicting the as- sumption that pr is the longest shared sub-path in P. and P..
(4)
2 It follows that, for E oo).
8g da((,,),, v),
E [lllp(u) - p(u)]la 2 2 Blll((u) - p(u))l=) 2
and
E [lll((u) - p(u)) S E [1l((u)- [())lla] = og log(n)do (u, v).
As mentioned in Section 3, rescaling the tree proves The- orem 1.1. We will now separately prove the upper and lower bounds in Equation (4). To keep the notation simple, throughout the proof we will omit the dependence on i and simply write p(u), T, T' instead of p=()), T,, Ty; this is es- sentially the same as focusing on the special case k 1, where is always 1 and p(.) (.).
We can therefore rewrite pp(u) p(u) as
uer WT (Pa)
|TT (P') WT (Pr) - (P') wT (Pt)l
WW (P.) WT (Pr)l.
(5)
The first equality holds by the definition of Pa. and P. and the second equality follows from the definition of P where (-) denotes the weight function in the tree TV. Let cu,v denote the edge in Pu,e whose weight (in T) is at least 8, r); such edge is guaranteed to exist by Lemma 3.2. We will use the noise obtained from multiply- ing w((n,,)) by Ye... to prove the lower bound. Formally, fix the tree T as well as all values Ye for e # Eu Set Oe (--) are in the same part of Pi,, as Cu,w and is for all other e. Since P" PP' = Pa.us we can rewrite |WT (P:)) - wT (P!)) as
To avoid complicating the argument with corner cases, we assume throughout the proof that u and e are in the same connected component; this allows us to directly leverage the guarantees from Lemma 3.2 without running into the +o0 issue discussed earlier. In Appendix B, we separately handle the case where u and v are in different components.
i.e., ag is -1 for all e that
Upper bound on expected distance To establish the up- per bound, we note that by the triangle inequality in the tree T", the difference between distances of two vertices from the root at most their distances in T'. We know from Lemma 3.2 however that distances in T (and there- fore in T") can be bounded in terms of distances in G. As such, E [[p(()) p(v)[] is can also be bounded in terms of do (u.0 v). Formally,
|WT (P:) - WT (Pt)) = (wrrr(ee
Σ c Cur.
Oeweel- (6)
Since we have fixed the graph T' and (Te)eyteun the only randomness in the above expression is Yeu.." It is well- known that for random variable X, the value a minimizing
Ip(u) p(u) = -ddT (s, u) (s, v) S dr ()
7

---

Fully Dynamic Embedding into Ep Spaces
E [| - ail is the median of X and since (r(ee,.) is fixed, the median of Yeu.. (wr (u, v)) is Swr(u v)). Therefore,
Proof. Consider the following "bridge" graph example. We first partition the set of vertices into two parts Vi and V2 with sizes [n/ and [n/2] respectively. We then connect all of the vertices that are in the same partition using edges of weight 1. Let T denote the time step at which all the vertices in the same partition are connected. After this step we repeatedly insert and delete a "bridge" edge with weight 1 between the two components. We repeat this step for T" times where T" > T is an arbitrary parameter (see A Algorithm 2).
E I (P()) WT (P:)
E
(Ca,,))
Σ
aeWeel
efeu.
3 WT urru, u)}l
2 E New.. WT (ew,v)
2
where the inequality holds by the definition of the median and the second equality holds since Ye... Uniform (1, Using the definition of Cu,e and the fact that T is non- contractive, we can further bound this with
Fix any two vertices u E V1 and v E V2. Recall that a denotes the expected distortion of the embedding. When the two components are connected, we have do(u, v) S 3. Applying Markov's inequality and using the expected distortion guarantee we obtain
1 (ey 2 Sgdr u) 2 (ud
2
Since the values of T and (Tie (TeJeste.. were assumed to be fixed in the above derivation, we have shown that
2E [ll(()) p(u)ll
Pr Pr(lpp()- - -(()) 2 W S
W
[lp(u)- - p(u)] T, (7ee [%elefeu.. 2 da(u, v). Taking it-
6a
erated expectation we conclude that E [lo(u) p(u)]) 2 da(u, v), finishing the proof.
W
which is at most 1/4. When the components are not con- nected, with probability at least 3/4 the embedding is non- contractive and therefore we have |lp()) p(v)ll > W'. Taking a union bound, we conclude that for any two consec- utive time steps, with probability at least 1/2, the value of Il(x)) p(v) || needs to change. This in turn means that at least one of the values p(u) and p(v) needs to change.
Non-contractivity. It remains to show that (lp(u) p(t)]l 2 Byda(u, v) holds with high probability, where note that we are once again considering the vectorized embedding p(.)
(P)....... (.)) where & = (log rt). To prove this, it suffices to show that, for all i, with probabil- ity at least 1/2 we have (p;(u) (w)-p;(v)) [x)] 2 d, (u, Since k Olog n), this would imply that with high probability, [p:(u) (+)) 2 3, v) for some i E [k:. finishing the proof.
For any t 2 T, let Vt. denote the indicator random variable that takes the value if the embedding p(v) changes after time t and let 14 = Σ. V4,, denote the number of vertices whose embedding changes. Let pr(.) denote the value of p right after the update. We can therefore write [n/2] E [v.] as
To prove the above claim, we once again fix the value of T and fNelezze.... Since Ye takes the values and 2 with prob- ability 1/2 each, Equations (5) and (6) imply that dr(u, v) takes the values d1 == |wT (Cu,v) - Eefeu. ae We and d2 (2wr(eu,e) Eefen. @eWel with probability 1/2 each. We note however that max (d1, d is at least du and d1 - d2 is at least
[n/2]
Σ E
[Pr.c]
2 Σ
1 + Σ
[V
V
(wT(Eu.)) - Σ
a.wel 12WT( - Σ a.wel
Σ
E Put + Mt,ll
WEV, V
exon
efon
2 (e(,w,))
2
Σ
Σ
Pr [ven + Me 2 2]
WEV: VEV2
where the second inequality follows from the fact that |a| + [b] 2 la b) for all a, b E IR. By definition of Cu,v. we have wr (Ca,v) 2 Byda(u, v), finishing the proof.
Σ
Σ
Pr ((l((u)) + (p--1(w)
weVi weV,
Σ Σ
Pr Prllee(u) pc(x)) + f1pp-1(w) - ( (o)l
5. Lower Bound
WEV: VEV.
1
In this section, we prove Theorem 1.2. We note that the proof also works for the more general setting where p(.) maps the vertices to "labels" that are used to calculate dis- tances via some function.
| 2'
where the second equality uses the fact that [Vi,, < [n/2], the third equality uses the definition of v and the final
8

---

Fully Dynamic Embedding into Ep Spaces
inequality uses the previously proved claim that the distance
Barta, Y., Fandina, N., and Umboh, S. W. Online probabilis- tic metric embedding: general framework for bypassing inherent bounds. In Proceedings of the Fourteenth An- nual ACM-SIAM Symposium on Discrete Algorithms, pp. 1538-1557. SIAM, 2020.
[[(()) - (()]l needs to change with probability least 1 1/2. It follows that, for any 2 T, we have E [ur] 2 (n()). This
in turn implies that the expected number of changes to the embedding in the first 7" steps is at least Q2n(T" - T)). Therefore, the expected amortized update time is at least (n(TT' - T)/T") which is ((n) for T' 2 27.
Bartal, Y. Probabilistic approximations of metric spaces and its algorithmic applications. In 37th Annual Sympo- sium on Foundations of Computer Science, FOCS '96, Burlington, Vermont, USA, 14-16 October, 1996, pp. 184- 193. IEEE Computer Society, 1996a. doi: 10.1 109/SFSS 1996. 548477. URL https: www.oi..o...oooooooooeeeoooo.... 1109/ SFCS 1
6. Conclusion
We presented the first efficient fully dynamic algorithm for embedding graph metrics into &p spaces, supporting both edge insertions and deletions with efficient update times. Our algorithm has low expected distortion, non- contractive, and allows efficient retrieval of a queried ver- tex's embedding. Additionally. we established lower bound showing that any algorithm explicitly outputting em- bedding updates cannot simultaneously be non-contractive and achieve low expected distortion, highlighting the neces- sity of our assumptions.
Bartal, Y. Probabilistic approximation of metric spaces and its algorithmic applications. In Proceedings of 37th Conference on Foundations of Computer Science, pp. 184- 193. IEEE, 1996b.
Bartal, Y. On approximating arbitrary metrices by tree metries. In Vitter, J. S. (ed.), Proceedings of the Thir- tieth Annual ACM Symposium
Impact Statement
the Theory of Com- puting, Dallas, Texas, USA, May 23-26, 1998, pp. 161- 168. ACM, 1998. doi: 10.1 10.1145/27666982777222 URL https:/ ptteps://doi.. http://ioooogo/////////oo/oo /ttp//11.11122226699
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Baswana, S., Khurana, S., and Sarkar, S. Fully dynamic randomized algorithms for graph spanners. ACM Trans- actions on Algorithmss (TALGG), 8(4):1-31,201
References
Abraham, I., Chechik, S., and Gavoille, C. Fully dy- namic approximate distance oracles for planar graphs via forbidden-set distance labels. In Proceedings of the forty-fourth annual ACM symposium on Theory of com- puting, pp. 1199-1218, 2012.
Bernstein, A., Gutenberg, M. P., and Saranurak, T. Deter- ministic decremental sssp and approximate min-cost flow in almost- linear time. In 202/ IEEE 62nd Annual Sympo- sium on Foundations of Computer Science (FOCS), pp. 1000-1008. IEFF, 2022.
Abu-El-Haija, S., Perozzi, B., Al-Rfou, R., and Alemi, A. A. Watch your step: Learning node embeddings via graph attention. Advances in neural information processing systems, 31, 2018.
Blelloch, G. E.,, Gu, Y., and Sun, Y. Efficient construc- tion of probabilistic tree embeddings. arXiv preprint /rXiv:/605.000 2016
Alon, N., Karp, R. M., Peleg. D., and West, D. B. A graph- theoretic game and its application to the k-server problem. SIAM J. Comput., 24(1):78-100 100, 1995. doi: 10.1137/ 500975397992224474. URL https: /ttp:://dddoioooe org/10.
Blum, A., Konjevod, G., Ravi, R., and Vempala, S. Semi- definite relaxations for minimum bandwidth and other vertex-ordering problems. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pp. 100-105, 1998.
Awerbuch, B. and Azar, Y. Buy-at-bulk network design. In Proceedings 38th Annual Symposium on Foundations of Computer Science, pp. 542-547, 1997. doi: 10.1 CCCCS.199.66400
Bodwin, G. and Krinninger, S. Fully dynamic spanners with worst-case update time. arXiv preprint arXiv:1606.07860 078644 2016.
Banihashem, K., Hajiaghayi, M., Kowalski, D. R., Olkowski, J., and Springer, M. Dynamic metric em- bedding into lp space. ICML, 2024. URL https: //openrevien www.eeewwwwwwweeeeeeeeeeeeeeeeee wwwntee/forumee 3
Bourgain, J. On lipschitz embedding of finite metric spaces in hilbert space. Israel Journal of Mathematics, 52:46- 52, 1985. URL https: / /api. deemanticscho 121 649019.

---

Fully Dynamic Embedding into Ep Spaces
Chechik, S. and Zhang, T. Dynamic low-stretch spanning trees in subpolynomial time. In Chawla, S. (ed.), Pro- ceedings of the 2020 ACM-SIAM Symposium on Dis- crete Algorithms, SODA 2020. Salt Lake City, UT. USA, January 5-8. 2020, pp. 463-475, SIAM, 2020. doi: URL https: /doi. org/10. 11.1001113//11 9781 611975994, .8.
Hanauer, K., Henzinger, M., and Schulz, C. Recent ad- vances in fully dynamic graph algorithms. arXiv preprint 2rXiv:212.111666 2021.
Henzinger, M., Krinninger, S., and Nanongkai, D. deter- ministic almost-tight distributed algorithm for approxi- mating single-source shortest paths. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pp. 489-498, 2016.
11113771.97811111959999
Chuzhoy, J. Decremental all all-pairs shortest paths in determin- istic near-linear time. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 626 639, 2021.
Henzinger, M., Krinninger, S., and Nanongkai, D. Decre- mental single-source shortest paths on undirected graphs in near-linear total update time. Journal of the ACM (JACM), 65(6):1 40, 2018.
Davison, A., Morgan, S. C., and Ward, O. G. Commu- nity detection guarantees using embeddings learned by node2vec. Advances in Neural Information Processing Systems, 37:685 738, 2024.
Indyk, P., Magen, A., Sidiropoulos, A., and Zouzias, A. Online embeddings. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Tech- niques: 13th International Workshop, APPROX 2010, and 14th International Workshop, RANDOM 2010, Barcelona, Spain, September 1-3, 2010. Proceedings, pp. 246-259. Springer, 2010.
Elkin, M., Emek, Y., Spielman, D. A., and Teng, S. Lower- stretch spanning trees. SIAM J. 38 38(2))608-622) 2008. doi: 1661. URL https: org/10. 1137 00007//0566646666
Kenton, J. D. M.-W. C. and Toutanova, L. K. Bert: Pre- training of deep bidirectional transformers for language understanding, Proceedings of naacL-HLT, volume 1.
Fakcharcenphol, J., Rao, S., and Talwar, K. A tight bound on approximating arbitrary metrics by tree metrics. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pp. 448-455, 2003.
Minneapolis, Minnesota, 2019.
Kleinberg, J. and Tardos, E. Approximation algorithms for classification problems with pairwise relationships: Metric labeling and markov random fields. Journal of the ACM (JACM), 49(5):616 669,,,,,,,,, 2002.
Fakcharoenphol, J., Rao, S., and Talwar, K. A tight bound on approximating arbitrary metries by tree metrics. J. Comput. Syst. Sci., 69(3):485-497, 2004. doi: 10.1016/ URL ptttps://doi.oo 101 /016// jcss 2004. 04. 011.
Eacki, J. and Nazari, Y. Near-optimal decremental hopsets with applications. arXiv preprint arXiv:2009.084/ 2020.
Forster, S. and Goranci, G. Dynamic low-stretch trees via dynamic low-diameter decompositions. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 377-388, 2019.
Linial, N., London, E., and Rabinovich, Y. The geome- try of graphs and some of its algorithmic applications. 1995.
Combinatorica,
Forster, S., Goranci, G., and Henzinger, M. Dynamic maintenance of low-stretch probabilistic tree embed- dings with applications. In Marx, D. (ed.), Proceed- ings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 13, 2021, pp. 1226-1245. SIAM, 2021. doi: 10. 00.113777.9771611196465... org/ htg/10.220 11/1101111 1..0.1137//1 9781611976651.....1
Linial, N., Magen, A., and Saks, M. E. Low distortion euclidean embeddings of trees. Israel Journal of Mathe- matics, 106(1):339-34)) 1998.
Newman, I. and Rabinovich, Y. Online embedding of met- rics. arXiv preprint arXiv:2303. /55.555 2023.
URL soctts://doo.
Roditty, L. and Zwick, U. On dynamic shortest paths prob- lems. In Algorithms-ESS 2004: /2th Annual European Symposium, Bergen, Norway, September 14-17, 2004. Proceedings 12, pp. 580-591. Springer, 2004.
Forster, S., Goranci, G., Nazari, Y., and Skarlatos, A. Bootstrapping dynamic distance oracles. arXiv preprint arXiv:2303.06612, 2023.
Thorup, M. and Zwick, U. Approximate distance oracles.
Journal of the ACM (JACM), 52(1):1-24, 2005.
Garg, N., Konjevod, G., and Ravi, R. A polylogarithmic ap- proximation algorithm for the group steiner tree problem. Journal of Algorithms, 37(1 37(1):66-888)) (66-844 2000.
Vaswani, A. Attention all you need. Advances Neural
Information Processing Systems, 2017.
10

---

Fully Dynamic Embedding into E. Spaces
Yun, S., Kim, S., Lee, J., Kang, J., and Kim, H. J. Neo-gnns: Neighborhood overlap-aware graph neural networks for link prediction. Advances in Neural Information Process- ing Systems, 34:13683-13694 2021.
Zhang, M. and Chen, Y. Link prediction based on graph neu- ral networks, Advances in neural information processing systems, 31, 2018.

---

Fully Dynamic Embedding into E Spaces
A. Further Related Work
Static algorithms. As mentioned earlier Given the importance of embeddings into lp spaces, many previous works have studied the problem of low-distortion embeddings in the statics setting; we here highlight few works that are more closely related to our problem. Most notably, (Bourgain, 1985) obtained an algorithm for embedding into an lp space with O n) distortion, which is tight (Linial et al., 1995). For embedding into trees, the seminal work of (Bartal, 1996b) obtained an algorithm with Ollog" n) distortion, which was later improved to Ollog n) by (Fakcharoenphol et al., 2003). Additionally, it is possible to obtain an embedding directly from trees into Eg with vlog log n distortion (Linial et al., 1998).
While these works and the techniques they introduce are the main inspiration behind the ideas used in our paper, they do not have any direct implications for our problem because they consider a static setting whereas we study a dynamic setting in which the graph is constantly changing. Rerunning a static algorithm after each update is possible but not efficient; in contrast, we show how to maintain a low-distortion embedding efficiently.
Dynamic embeddings. Recent works have studied dynamic embeddings into simple metric spaces. In this line of work, (Forster et al., 2021) obtained a decremental algorithm with O(m +o(1)) update time and O(log" (n) log(nW)) expected distortion, as well as a fully dynamic algorithm with (mm/o+)()) update time and expected distortion. One of the key tools they developed to obtain these results is an efficient decremental algorithm for maintaining Low Diameter Decompositions (LDDs) for a graph. This construction was later used by (Banihashem et al., 2024) who obtained a decremental algorithm for embedding into lp spaces with O(log" n) expected distortion and O(m +1)) log" W + Q (log(n)) log(nW)) total update time, where Q refers to the total number of updates. They also showed that efficiently maintaining a low-distortion embedding not possible if we require that the embedding has low distortion with high probability, and each change to the embedding of vertex is explicitly outputted by the algorithm. Our work extends these results by obtaining the first fully dynamic algorithm for embedding into Ep spaces. Note that the negative result of (Banihashem et al., 2024) does not apply to our setting because (a) we do not output changes to the embedding of each vertex and (b) our distortion guarantees only hold in expectation. We further strengthen this negative result by showing that even if a fully dynamic algorithm only preserves distances in expectation, as long as the embedding is non-contractive, explicitly outputting changes cannot be done efficiently.
Dynamic spanning trees. A closely related line of work considers the problem of maintaining spanning tree of graph with low average stretch. For unweighted graphs, was first studied by (Forster & Goranci, 2019), who obtained an algorithm for with n n1/2+((1) update time and (1) average stretch. The update time was later improved to (1 by (Chechik & Zhang, 2020). In addition, (Chechik & Zhang, 2020) obtained an algorithm for the problem in a decremental setting. A key contribution of this work was a novel pruning technique for obtaining Low Diameter Decompositions (LDDs), which was later leveraged by the aforementioned work of (Forster et al., 2021) to obtain a dynamic embedding into trees.
Dynamic shortest paths. Many works have considered dynamic algorithms for maintaining information about distances in the graph in some form. This includes single source shortest paths (Roditty & Zwick, 2004; Henzinger et al., 2016; 2018), distance oracles (Thorup & Zwick, 2005; Abraham et al., 2012; Forster et al., 2023). spanners (Baswana et al., 2012; Bodwin& & Krinninger, 2016), and hopsets (Lacki & Nazari, 2020) to name a few. These tools have proved to be instrumental in the development of dynamic embeddings; e.g., the decremental LDD of (Forster et al., 2021) uses the decremental SSSP of (Henzinger et al., 2018). 8). We refer to (Hanauer et al., 2021) for a comprehensive survey. We note that while randomness is crucial for many of the developments in the field, many works have studied deterministic algorithms for these problems as well (Chuzhoy, 2021; Bernstein et al., 2022).
Online embeddings. A closely related line of work is online embeddings where the elements of a metric arrive sequentially and we need to assign an embedding to them (Indyk et al., 2010; Barta et al., 2020; Newman & Rabinovich, 2023). While the problem statement is similar to the dynamic setting, especially the insertion-only case, the two problems are fundamentally different. For dynamic algorithms, the main focus is on having a low update time and as such the problem is mainly computational. In contrast, the key issue for designing online embeddings, and online algorithms in general, is that the algorithm is obtaining information incrementally, but needs to make decisions irrevocably.
12

---

Fully Dynamic Embedding into f Spaces
B. Omitted Proofs
B.1. Proof of Theorem 1.1
Distortion across different components, We now handle the case where u and v are in different components of the graph
G. Given Lemma 3.2, this means that the two vertices will be in separate trees in each of the forests Ti,... Tr. The upper bound on the distortion follows fairly easily, the difference between the embedding of any two vertices is at most
(lp(u) p(o)]l - (p((u) pr(1)l
& 1 (a(4))+ Σ A(o1
S (K) max E (w)i))
where for the final inequality we have used the fact that Ti.... Tk are all sampled from the same distribution and as such pa(u) are all i.i.d. Given our construction of T; however, for any u, the distance to the root of the tree is at most 0(1)nnW= & a, this follows from the recursive nature of the tree construction which, in each iteration, can increase the maximum distance by at most a constant factor. This means we can bound the distance of p(u) and p(v) with (llg((n),, W"), which finishes the upper bound proof because da(u, v) = W".
As for the lower bounds, we note that since the two same argument as before applies; specifically, if we do not apply the scaling by Ye. the path connecting u and v in the tree T" contains two edges that are of weight W The exact same argument as before implies that the random scaling causes the vertices to in distance at least W in both expectation and high probability.
B.2. Pseudocode for Theorem 1.2
Algorithm 2: Bridge Edge Update Process
Input: Vertex set V of size n, number of bridge toggles 7" Output: Sequence of graph updates
Partition V into V1 and V/2 such that Ví1= [n/2]. 1V22 = [n/2];
Add all edges of weight 1 between pairs in Vi and between pairs in V2;
Let T + time step when intra patra-patiiionn edges are fully added;
Fix any u E V12 and u E V2;
for t = T' + 1 to T' + 7" do
if t is odd then
Insert bridge edge (u, v) of weight 1;
else
Delete bridge edge (u, v);
C. Constructing Edge Dominant Trees
In this section, we prove Lemma 3.2. The proof uses the recursive approach of (Forster et al., 2021) for constructing fully dynamic trees. The approach starts with (slow) fully dynamic algorithm and "bootstraps" it using decremental algorithm and obtains a speedup. (See also (Abraham et al., 2012; Forster et al., 2023) for similar applications of this technique) If we simply rerun a static algorithm after each update for the fully dynamic algorithm and use the decremental algorithm of (Forster et al., 2021), this leads to an algorithm with update time m 1/2-o(1) Repeating this approach with the new dynamic algorithm, we can further improve the running time, at the cost of worse expected distortion. As we show in this section, this fully dynamic algorithm satisfies the edge dominant guarantees required by Lemma 3.2.
The remainder of the section is organized as follows. We first provide the boosting reduction of (Forster et al., 2021) and state the reduction we use from prior work (Section C.I). We then show that the tree obtained from the boosted algorithm satisfies the edge dominant guarantee required Lemma 3.2, provided that the original algorithms used for boosting satisfied the property (Section C.2). Finally, we state a specific instantiation of the boosting framework using the decremental algorithm of (Forster et al., 2021) and the static algorithm of (Blelloch et al., 2016) (Section C.3).
13

---

Fully Dynamic Embedding into E Spaces
C.I. Tree Construction
We now present the fully dynamic reduction of (Forster et al., 2021) for boosting a slow fully dynamic algorithm into a faster one by combining it with a decremental algorithm. Specifically, given decremental algorithm A and a (slower) fully dynamic algorithm B, we obtain a new fully dynamic algorithm C' whose update time improves on that of B.
Overview of approach. We the algorithm A in phases of length E, restarting the algorithm the beginning of each phase. In each time step, let E denote the set of edges together with their weight and F denote the same set at the start of the current phase. We will use I F to denote the set of edges that have been inserted since the beginning of the phase but have not yet been deleted and use D F to denote the set of edges that have been deleted since the beginning of the phase.
Let U denote the of endpoints of edges in I; i.e. U = {u: (u, v) E I for some v). Let TA denote the tree maintained by the decremental algorithm and define P.. be the path from the root to u in Tx- Define := Uueu Pa and H == P U. Let T3 be the graph obtained by maintaining a fully dynamic embedding of H using the algorithm B. Consider the graph (Ta\Ht) U TT obtained by replacing H in TA with the tree TB, and let Tc be the resultig graph.
Dynamic maintenance. We next state lemma form (Forster et al., 2021) that shows the aforementioned values can be maintained efficiently in a dynamic setting. We begin with some definitions. Let a and 8A denote upper bounds on the height of Ta and the expected distortion of TA respectively. Let hg and sg denote the corresponding values for Tg. Let XA denote an upper bound on the number of times the path from a fixed vertex to the root can change during a run of algorithm A. Let & (m, n) and ug (m, n) denote upper bounds on, respectively, the total time of algorithm and amortized update time of algorithm B when run on a graph with n vertices and at most m edges.
Lemma C.1 ((oorster et al., 2021)). The graph To is a non-contractive forest with expected stretch bounded by SASB, and has height at most h + hB. Additionally, for any integer 8 2 1, there exists a fully dynamic algorithm that maintains the tree Te with amortized update time (m, n) log(n)/{) such assuming at least updates are performed.
C.2. Edge Dominant Property
We now show that the tree To is edge dominant. On a very high level, this seems reasonable since static embeddings into trees use the framework of Bartal's embedding which is Hierarchical and weights multiply by two when traveling from a leaf towards the root. This idea more or less extends to decremental dynamic algorithms as well.
For the fully dynamic case however, the proof is more subtle since the output tree is actually obtained by combining two separate trees in the algorithm. To prove the lemma, we will show that the path connecting any two vertices in a tree can be divided into at most three parts such that each part lies entirely in one tree (Lemma C.5). This implies the Lemma's statement by considering the maximum edge in each of these parts.
Lemma C.2. Assume that the trees TA and TB are edge dominant with parameter and assume the algorithms A and B preserve connectivity, Then the tree To is edge dominant with scaling a/3.
We say a tree embedding T preserves connectivity for G if for any pair of vertices are connected in G if and only if they are connected in T. We next show that the tree Tc preserves connectivity. This can be obtained from the distortion guarantees of the forest; since the forest is con-contra, any two vertices that are not in the same component of the graph should not be in the same component of the tree. As for vertices that are not in the same component, if they fall in different components with non-zero probability, then their expected distortion would be +oc, contradicting Lemma C.I. We provide a simple proof for completeness however as it provides a nice intuition for the remaining proofs.
Lemma C.3. A and Ta preserve connectivity then so does To-
Proof. First note that if u and are in different components in the input, then they must be in different trees in the output since To is non-contractive. Now, assume that and u are in the same connected component in G. Consider the path connecting and in G and label each vertex with number indicating the component of that vertex in Tc. Since and have different labels, there must be an edge in the path such that the label of its endpoints is different.
There are now two cases:
14

---

Fully Dynamic Embedding into E Spaces
1. The edge is in F. In this case, since Ta A preserves connectivity, the endpoints must be in the same component of Ta- This means that they are connected in Te well however. Specifically, get from one endpoints to another, we can follow the path connecting them in Ta and for any edge that is in P (and therefore is not in Tc), we can just go through "detour" path in TB. Such detour must exist since TB preserves connectivity.
2. The edge is not in F. In this case, the edge must be in the set I which means it appears in H. Since TB preserves connectivity, the endpoints of the edge are connected in TB, which in turn means that they must be in the same connected component of Tc.
In both cases, have shown that the endpoints of the edge were in the same component of Tc, contradicting the choice of the edge. It follows that and are in the same component, finishing the proof.
The following lemma states that the tree TAY P does not connect different components of T' together. We note that the converse is not true and Ta can connect different components of Ta together; indeed, if an edge is inserted in G connecting two different components, then the components of A are unchanged (assuming the f-length phase has not ended), and Ta necessary for connecting the two components in Tc.
Lemma C.4. ufu, u E V (TBB) then u and e are in the same connected component in TB if and only if they are in the same connected component Te.
Proof. Assume that u and v are in the same component of TB; then they are clearly in the same connected component in To as well since E(TB) C ETTc). Conversely, assume that V E V{TB) are connected in Te; we will show that they are connected in I'g as well. The key insight we rely upon is that if a vertex e E V (TTA) appears in U, then so does the entirety of its path to the root. Therefore, the graph U cannot put two vertices in the same component of TA in different components. Since Ta preserves connectivity, this means that Ta cannot do this either.
Formally, let Ef denote the edges of the path connecting them. If all the edges are in E(Ta). then the claim clearly holds. Otherwise, let e denote the first edge not in E(Ta). Since the edge is not in Tn. it must be in Ta P. Continue along the path until we once again reach a vertex in TB. Let (u', v²) denote the vertices in Tg that are connected via this sub-path. Since u' and o' are connected via Ta. they are connected in P because P contains the path from both of these endpoints to the root. Since TB preserves connectivity, this means that these endpoints are in the same component of TB as well. Therefore, there must be path connecting them in TB. This a contradiction as such a path would form a cycle with the path in P, contradicting the fact that Te a tree.
Lemma C.5. Fix two verlices E V(Tc) and let ey denote the edges of the path connecting them. There exists indices 0 < i S j < f + such that 61, .1, and e.. are in E(TxAP) and eit1,-.., Gj-1 1 are in F(TB)).
Proof. The key insight behind the proof is that since (TA)P) cannot connect two components of TB. any path in Tc cannot enter TB after leaving it. This means that we can break the path into three parts representing before TB, during Tg, and after TB respectively. Formally, let V(P) denote the set of vertices in P. If there PC n Vp empty, then the path must entirely lie in either T''s P or in TB. This is because in order to get from any vertex in T' \P to TB, we need to first go through some vertex in (P). In this case, the lemma clearly holds. Otherwise, let U2, Vj denote the first and last vertices for the path in (P). Since the vertices lemma, implies they are in the same connected component in Tg. Therefore, the path connecting them lies entirely in TB. finishing the proof. (see Figure I for an illustration).
connected, they are in the same connected component in Tc which, by the previous
We can now prove Lemma C.2
Proof of Lemma C.2. Fix the vertices u, E (TTc). ej ei, ey denote the edges of the path connecting them. We need to show that there exists a value i' e [f] such that
a w(ee)) >
z (u, v)
15

---

Fully Dynamic Embedding into E. Spaces
a b
X
y
Figure 1. Example for Lemma C.5. The blue vertices and edges denote the tree Ta. Edges (a, b) and (x,, y) have been inserted after the start the current phase. The dashed edges denote the edges of graph U and the green vertices and edges denote the tree Tc; note that the leaves Te are in Ta. In order to get from u to v, start from the vertex u and following the path to the root until reaching the vertex in TB. Next, follow the path in T3 the appropriate leaf and go downwards until reaching e.
Let and j be the indices specified by Lemma C.5. Define the sub-paths Pıς E (e1....,e;) Pa, E (c....., ey), and Pa.s E (ci....,e:) ,,). Let ii,i Ei and f denote the heaviest edges in each sub-path; if any sub-path is empty, set the corresponding edge to an arbitrary value such as Null and define weight to O.
Since TA and TB are edge dominant with parameter a, and each of the three uub-paths is entirely contained in either Ta or TB, we have (ee,s) 2 aw(() and similarly for eij and ej Therefore,
max (wr(), s) w(er)): w(e,r))
(w(e),) w(es)) - w(e,,))
(w((1, wr (Paj) w( (P3s)) drc (u,v)
where the first inequality holds because max average and the second inequality holds by Edge-dominance of TA, To.
C.3. Proof of Lemma 3.2
Combining the above results, we obtain Lemma 3.2. The lemma follows using the same proof as Theorem 4.2 in (Forster et al., 2021). We sketch the proof for completeness, emphasizing the edge-dominant property.
Proof. We can firstly assume that an upper bound on m because we can start with the value and, each time the upper bound violated, multiply it by and restart the procedure; since the upper bounds increase exponentially, the restarting cost can always be charged back the previous updates the cost of constant factor.
Assuming upper bound is known, the proof follows by induction on i. The base case follows from (Blelloch al., 2016) who obtain efficient algorithm for calculating the FRT tree of (Fakcharoenphol al., 2003). We note that the tree is edge-dominant with parameter 1/4. For 2, we use Lemma C. Specifically, set A to be the decremental algorithm of (Forster et al., 2021) and set B to be the fully dynamic algorithm obtained by induction for 1. As long there are less than f = m 1-1/ updates, we can simply run the fully dynamic algorithm. Afterwards, we run the recursive algorithm of Section C.
The stretch dominant property holds before we reach updates because of the induction hypothesis. As for after the updates, the fully dynamic algorithm satisfies the property with By-1- Additionally, the decremental algorithm satisfies with parameter 1/4. Lemma C.2 now implics that the recursive algorithm satisfies the property with parameter min (1/4,3-0 1) 3- 2 3-9,
16


Reviews:
[{"review_id": "GBJ53PpBhb", "reviewer": "Reviewer_kd5G", "summary": "This paper is about dynamic maintenance of Bourgain embeddings (a.k.a. Embedding metric spaces into low-dimensional l_p spaces) with low distortion for undirected graphs with polynomial bounded lengths that undergo edge insertions and deletions. The main result is dynamic Bourgain embedding for graphs that achieve expected stretch O(log n)^{2q} O(log (nW))^{q-1} with O(m^{1/q+o(1)}) update time and O(q \\log n \\log nW) query time, where is a positive integer larger than 2. \n\nNote here that the embedding of each vertex is maintained only *implicitly*; if one would like to report all the necessary changes to the embedding after each edge update, then there are simple, strong lower-bound that show that even achieving sub-linear expected stretch is out of the question. Just think of a dumbbell graph consisting of two cliques sitting on ~ n/2 vertices, connected by a few edges. One can that simply insert/delete these edges alternatively, which would result in expensive changes in the underlying embedding.\n\nPrevious works in the literature could only maintain *explicit* embeddings in the decremental setting, where only length increases are allowed. \n\nThe technical contribution of the paper can be viewed as reducing the dynamic Bourgain embeddings to the dynamic tree embedding work of Forster et al. SODA’21 with few additional technical observations: (1) in the trees constructed on these works, the path between any two nodes contains an edge that is *heavy* compared to the shortest path between u and v; (ii) adding some *noise* to the distance estimates, which help to resolve some technical issues about proving that that the embedding is non-contractive.\n\n## update after rebuttal\n\nI appreciate the authors' effort in compiling a very detailed rebuttal. As my score indicates, I'm generally positive about the paper and the paper could be accepted. However, despite the importance of the problem and the strong theoretical guarantees, it is still unclear to me (and to some other reviewers) how dynamic tree embeddings fit within the ICML literature.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful and detailed review. We are particularly grateful for the positive assessment that the paper is \"well written\" and that the problem is \"of fundamental importance to many communities.\" We're also glad that the reviewer appreciated the elegance and care in our technical approach, particularly the reduction to dynamic tree embeddings.\n\nBelow we respond to the specific points raised:\n\n> Maybe discussing the applications where implicit embeddings would make sense?\n\nThank you for this helpful suggestion. \nIn many practical settings, maintaining **explicit embeddings** is either infeasible or\nunnecessary. For example:\n- In large-scale systems, memory constraints often prevent storing the entire\n  embedding, and only **pointwise access** to node embeddings is needed at\n  query time.\n- Many downstream tasks—like nearest neighbor search, link prediction, or\n  routing—only require **on-demand access** to distances or individual\n  coordinates, not the full embedding at once.\n\nIn such scenarios, **implicit embeddings** provide a flexible and scalable alternative, and our work offers strong theoretical guarantees for maintaining them efficiently in dynamic settings.\n\n> Section Embedding in Page 4, I think you have messed up rho with d' — please double check.\n\nThank you for catching this. You are correct; the equations should say $d'(\\rho(u), \\rho(v))$ instead as\nwe are calculating the distance of the embedded points in the embedding space.\nWe have revised the paper accordingly.\n\nIf you feel that our response has adequately addressed your major concerns, we would appreciate it if you possibly adjust your score accordingly.", "claims_and_evidence": "The paper is well written. Also, the claims are supported by convincing evidence.", "methods_and_evaluation_criteria": "This is a theory paper, so there is nothing to discuss about the evaluation criteria.\n\nThe dynamic model studied in this paper is the standard one in the literature.", "theoretical_claims": "I think all proofs look reasonable to me. I haven't done thorough checks, but at at several places I stopped and tried to follow the math, and it seems correct to me. The overall idea is also sound.", "experimental_designs_or_analyses": "No experiments so nothing to comment here.", "relation_to_broader_scientific_literature": "Metric embeddings are at the core of many communities without computer science, including image retrieval, computer vision, theory and more recently, machine learning. Dynamic algorithms can be viewed as an effort to design algorithms that are closer to real-world data. Questions at the intersection of both of these topics should be relevant to many communities.", "essential_references_not_discussed": "I didn't find any.", "other_strengths_and_weaknesses": "Strengths: a simple reduction for dynamic Bourgain embedding with some technical additions which seem to require care. I haven't thought a lot about the problem myself to judge the technical novelty here, but I'd like to emphasize that the paper also uses a quite strong hammer. From that perspective, the paper is not as easy as it may seem. I like the simplicity of the reduction.\nThe problem is of fundamental important to many communities. \n\nWeaknesses: Maybe discussing the applications where implicit embeddings would make sense?\n\nI lean towards acceptance.", "other_comments_or_suggestions": "Well written paper, and didn't have a hard time to follow.\n\nSection *Embedding* in Page 4, I think you have messed up *rho* with *d'* -- please double check.", "questions_for_authors": "None.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0bPeD5CxjC", "reviewer": "Reviewer_RMLF", "summary": "The paper presents a fully dynamic algorithm for embedding graph metrics into ℓp spaces, supporting edge insertions and deletions. The algorithm achieves low expected distortion, non-contractivity, and efficient query and update times. Key results include maintaining low-distortion embeddings with O(log(n)) expected distortion and O(m1/q+o(1)) update time. It also demonstrates the impossibility of achieving such properties with explicit update outputs.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful and constructive review. We appreciate the positive assessment that our results\nare \"significant contributions to the field\" and that \"The clarity and precision of the theoretical analysis are well\".\n\nBelow, we respond to the reviewer’s specific concerns:\n\n> ... the distinction between the static and dynamic settings ...\n\nThank you for the suggestion. We have revised **paragraph 4** of the Introduction to further clarify this. \nIn short, **static settings** assume the input data is fixed, whereas in the **dynamic setting**, the data changes over time via updates.\nIn our model, these updates take the form of insertions and deletions of edges in the underlying graph, which is the standard\nmodel used in dynamic graph theory.\nThe goal is to maintain a good output—here, a low-distortion embedding—even as the input graph evolves.\n\n> The use of $\\ell_p$ spaces ...\n\nIn practice, $\\ell_2$ embeddings are a standard representation in many ML tasks—including **word2vec**, **LLMs**, **kernel-based models**, and **LSH-based nearest-neighbor search**—due to their interpretability and computational efficiency. These embeddings underpin similarity search, clustering, and classification across numerous applications. By focusing on $\\ell_p$ spaces, we aim to provide theoretical tools directly aligned with this widely used embedding paradigm.\n\n> ... empirical results ...\n\nWe have performed experiments evaluating our embeddings here: dropmefiles.com/dfsfg\n\nWe emphasize however that the main focus of our paper is providing a **theoretical understanding** of dynamic embeddings, akin to the role that **PAC learning theory** plays in understanding classification. \nJust as PAC models offer deep insights into learning even when they abstract away the full complexity of modern neural networks, our model—though idealized—helps clarify the possibilities and limitations of embedding dynamic structures. \n\n> ... including pseudocode \n\nWe have aimed to provide pseudocode or detailed algorithmic descriptions for all major components in the main body—particularly for **Algorithm 1**. Additionally, we have now included **pseudocode in the appendix for the lower bound construction used in the proof of Theorem 1.2**, to further aid readability.\n\n> ... exploration of other dynamic graph problems, such as dynamic shortest path problems ...\n\nWe thank the reviewer for this suggestion and have expanded on this in Appendix A.\n\nIf you feel that our response has adequately addressed your major concerns, we would appreciate it if you possibly adjust your score accordingly.", "claims_and_evidence": "The claims made in the paper are generally supported by clear evidence. The theoretical results and algorithmic steps are well-explained, and the authors provide proofs to support their findings. The primary challenge of maintaining low-distortion embeddings in a dynamic setting is tackled effectively with new techniques. However, the distinction between the static and dynamic settings could be elaborated more clearly for readers unfamiliar with this field.", "methods_and_evaluation_criteria": "The methods are appropriate for the problem at hand.  The algorithm efficiently handles dynamic edge insertions and deletions, which is a challenge in metric embeddings.  The evaluation criteria, such as expected distortion and update time, are well-defined and relevant to the problem.  However, the use of ℓp spaces should be further evaluated by specifical real-world task.", "theoretical_claims": "The paper presents theoretical foundation for the problem. The proofs of expected distortion, non-contractivity, and update/query times are argued. There are no apparent flaws in the theoretical claims, and the methodology for bounding the distortion and ensuring non-contractivity is sound.", "experimental_designs_or_analyses": "The paper does not provide empirical results, which is a limitation. Although the theoretical analysis is thorough, real-world validation of the algorithm's performance in dynamic graphs would strengthen the claims. Including some practical experiments would help in assessing the feasibility of the approach in real applications.", "relation_to_broader_scientific_literature": "The paper positions itself within the existing body of work on metric embeddings, dynamic graph algorithms, and low-distortion embeddings. It builds on the works of Bourgain, Bartal, and Forster, among others.", "essential_references_not_discussed": "There are no major gaps in the references, but a more thorough discussion on the limitations of dynamic embeddings, particularly in the context of real-world applications, would improve the paper's relevance. The exploration of other dynamic graph problems, such as dynamic shortest path problems, could also add depth.", "other_strengths_and_weaknesses": "The primary strength of the paper is its novel contribution to dynamic metric embedding, specifically for ℓp spaces. The theoretical guarantees of low-distortion and non-contractivity are significant contributions to the field. The clarity and precision of the theoretical analysis are well. However, the lack of experimental validation and real-world application examples reduces the impact of the work.", "other_comments_or_suggestions": "Including some empirical results or case studies showing the algorithm's performance on real-world dynamic graphs would improve the paper’s impact and reliability.", "questions_for_authors": "see above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "y1wo6GvvHD", "reviewer": "Reviewer_vp4D", "summary": "This paper studies the problem of maintaining a low-distortion embedding from the shortest path metric on a graph into $\\ell_p$ metric, where the graph undergoes edge insertions and deletions. Given a parameter $q$, the paper presents an algorithm that dynamically maintains an embedding that is non-contractive with high probability and admits an expected distortion of $O(\\log(n))^{2q} O(\\log(nW))^{q - 1}$, where $W$ is the maximum edge weight. Moreover, the algorithm admits an amortized update time of $m^{1/q + o(1)}$ with high probability and only maintains the embedding implicitly with the time of querying the embedding of each vertex equal to $O(q \\log (nW) \\log n)$. On the other hand, this paper establishes the corresponding negative result, showing that any algorithm that achieves non-contractivity with a constant probability and a sublinear expected distortion and maintains the embedding explicitly must have $\\Omega(n)$ amortized update time.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful reading of our paper.\nWe are glad that the reviewer believes our \"expositions are clear\" and \nthat \"the ideas of maintaining edge-dominant trees and randomly perturbing the edge weights are interesting\".\nWe address the reviewer's concerns and comments below.\n\n> Discussion of most relevant literature ...\n\nWe thank the reviewer for this suggestion. In the current submission, our goal was to introduce the most relevant prior work directly in the **Introduction** as part of the motivation, and then focus the main body of the paper on our technical contributions. Given space constraints, we chose to defer the more exhaustive **Related Work** section to the appendix, as is common in theory papers. That said, we understand the reviewer’s concerns and have revised the paper to ensure that key citations now appear in the main text. Specifically, we now include a concise summary of relevant prior work in the **fourth paragraph of the Introduction**, giving a briefer description of low-stretch spanning trees (which are less central to our contributions), and adding a short discussion of **online embeddings**, which are thematically related.\n\n> Proofreading and typos.\n\nWe thank the reviewer for bringing this to our attention. We have corrected the noted issues in the revised version and will continue to carefully proofread the paper to catch any remaining small errors.\n\n> Negative result is less interesting.\n\nWe respectfully disagree with this assessment. As we explain in the paper, the **negative result serves an important role**: it demonstrates the **tightness of the assumptions** underlying our positive result. While the lower bound builds on prior ideas, our version extends the result to a more general setting, in particular to **embeddings with low expected distortion that are non-contractive with high probability**. This generalization is not only technically meaningful, but also conceptually clarifying—it helps justify the constraints and guarantees we adopt in our main algorithmic result.\n\n> ... relies heavily on prior work.\n\nWhile our construction draws on prior work on **tree embeddings**, we do not view this reliance as a weakness. On the contrary:\n- Our analysis of **vector embeddings** uncovers **nontrivial properties** of the tree embeddings used in dynamic settings—properties that, to the best of our knowledge, have not been explicitly documented before. Given the technical depth of the underlying work, these observations are subtle and require careful reasoning.\n- In addition, our paper **establishes a conceptual and technical connection** between dynamic tree embeddings and **vector embeddings into ℓₚ spaces**, which had not previously been explored in this context. While such a connection may seem plausible in hindsight, it is far from obvious, especially given the nontrivial obstacles highlighted in the \"Low-distortion trees\" paragraph of Section 1.2.\n- Finally, we note that prior constructions—such as low-stretch spanning trees—are themselves composed of incremental innovations on existing techniques. In this spirit, our work **adds new insights** and **extends the applicability** of known ideas to a new and natural problem setting.\n\n\nIf you feel that our response has adequately addressed your major concerns, we would appreciate it if you possibly adjust your score accordingly.", "claims_and_evidence": "The claims are all supoprted with proofs.", "methods_and_evaluation_criteria": "The methods make sense.", "theoretical_claims": "The proofs are correct to the extent that I have checked (all the proofs in the main body).", "experimental_designs_or_analyses": "There is no experiment in the paper.", "relation_to_broader_scientific_literature": "This paper gives the first algorithm that maintains a low-distortion embedding from a graph to $\\ell_p$ metric in the fully dynamic setting, whereas the algorithms in prior work are only for the decremental setting. This paper also extends the lower bound in prior work, which holds for algorithms that have high-probability distortion guarantees, to hold for algorithms that only have expected distortion guarantees. Moreover, the proof of this paper relies heavily on the dynamic tree embedding of prior work.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "This paper is well-structured and the expositions are clear, although it deserves another round of proofreading. Also, the paper defers the discussion of most relevant literature to the appendix, which is an inappropriate use of the appendix.\n\nThis paper generalizes the result in prior work to the fully dynamic setting, and the ideas of maintaining edge-dominant trees and randomly perturbing the edge weights are interesting. However, the negative result is less interesting as the proof inherits the instance from prior work and the analysis is quite straightforward. Overall, the technical contribution of this paper is limited.", "other_comments_or_suggestions": "Minors:\n- It's not stated in the introduction that the original metric is induced by the shortest path metric on the graph.\n- In Line 350, the definition of $\\alpha_e$ should instead be $-\\alpha_e$.\n- In Line 370-372, the second equality is missing.\n- In Line 436, should $\\leq W' / 2$ be $> W'$?\n\nTypos:\n- Line 22: \"problem problem\"\n- Line 115: $d_G(u, v) / 2$ -> $d_G(u, v)$\n- Line 138: $s_i$ -> $S_i$.\n- Line 184: \"note\" -> \"not\"\n- Line 198: \"as\" -> \"a\"\n- Line 176: \"$u$ and $v$ not in\"\n- Line 267: $\\beta^{-1}$ -> $\\beta$\n- Line 291: $E_{add}$ -> $V_{add}$\n- Line 343: \". where\"\n- Line 359: $\\gamma_{e, v}$ -> $\\gamma_{e_{u, v}}$\n- Line 367: $w_T(u, v)$ -> $w_T(e_{u, v})$\n- Line 435: $7/8$ -> $3/4$", "questions_for_authors": "I don't have further questions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tjyL99VFrV", "reviewer": "Reviewer_srig", "summary": "The Authors presented an algorithm to embed dynamic weighted graph to $\\\\ell\\_p$ space, achieving $O(\\\\log(n))^{2q} O (\\\\log (nW))^{q-1}$ expected distortion with $O(m^{1/q + o(1)})$ update time and $O(q \\\\log (n) \\\\log (n W))$ query time.\n\n## update after rebuttal\nFirst, I appreciate the authors' sincere responses. However, regrettably, I have decided to keep the original score.\n- The authors have failed to answer my crucial concern directly: *why can converting a dynamic graph to $\\ell^p$ representations contribute to the ICML community?* The paper [1] is an ICML paper, but this paper again does not explain why they are meaningful in the machine learning community. Moreover, to the best of our knowledge, the paper has not been cited well in the community, which implies that the paper failed to explain its contributions in the ICML community. By the way, the current manuscript cites the arxiv version of [1], which I recommend you modify so that it cites the ICML version, as citing conference or journal versions (if exist) is a convention in the machine learning community.\n- The authors try to provide examples [2]-[5]. However, though they are dynamic OR graph embedding, they are not dynamic graph embedding, i.e., not dynamic and graph embedding simultaneously, so they do not explain the importance of the object of the authors' analysis.\n- The authors provided experimental results, but they are not designed to answer my question. Although the authors stressed that the distortion was low and the percentage of non-contractive node pairs was also low, they can be zero if we simply use the original graph without embedding. Hence, they do not explain why we need to embed a dynamic graph, unfortunately.\n\nWhether the paper is accepted to this ICML or not, I encourage the authors to clarify before its publication how dynamic graph embedding can contribute to the machine learning community. If you spend time, you may find good application areas where dynamic graph embedding plays a crucial role. Such explanations are necessary to accept theory papers, as analysis on useless things is again useless (One possible exception is where we rigorously prove that something is useless, even though it looks useful.). \n\n[1] Banihashem, Kiarash, MohammadTaghi Hajiaghayi, Dariusz Rafal Kowalski, Jan Olkowski, and Max Springer. Dynamic Metric Embedding into lp Space. ICML 2024\n\n[2] Cohen-Addad, V., Lattanzi, S., Maggiori, A., & Parotsidis, N. (2024). Dynamic correlation clustering in sublinear update time. ICML 2024\n\n[3] Bhattacharya, S., Lattanzi, S., & Parotsidis, N. (2022). Efficient and stable fully dynamic facility location. NeurIPS 2022\n\n[4] Lattanzi, S., Mitrović, S., Norouzi-Fard, A., Tarnawski, J. M., & Zadimoghaddam, M. (2020). Fully dynamic algorithm for constrained submodular optimization. NeurIPS 2020\n\n[5] Cohen-Addad, V., Hjuler, N. O. D., Parotsidis, N., Saulpic, D., & Schwiegelshohn, C. (2019). Fully dynamic consistent facility location. NeurIPS 2019", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed reading of our paper.\nWe are glad that the reviewer found our theoretical analysis \"interesting\" and \"elegant\".\nWe address the reviewer's concerns and comments below.\n\n> how the paper contributes to the ICML community ... require rewriting ..\n\nWe have discussed these motivations in the first 3 paragraphs of the introduction.  \nWe understand the reviewer's concerns and have revised the paper by incorporating the following text.  \n(To keep the paper within the page limit, we have slightly shortened the overview of techniques section and deferred the proof of non-contractivity to the appendix.)\n\n**Embeddings** are a cornerstone of modern machine learning, powering models from **word2vec** to **large language models (LLMs)**. These methods embed discrete data—like words or tokens—into continuous spaces, enabling geometric reasoning about semantics. **Embedding-based architectures** have driven advances in language understanding and generation.\n\nAmong embedding targets, $\\ell_p$ spaces (especially $\\ell_2$) have emerged as the **standard representation space** in modern ML. This is due to (a) their **interpretability**—distances and angles have clear geometric meaning—and (b) the fact that many key primitives are **much more efficient** in $\\ell_p$ spaces. For example, **nearest neighbor search** in high dimensions is routinely performed using **locality-sensitive hashing (LSH)**, designed specifically for $\\ell_2$ and other vector norms. Similarly, fast kernel approximations, attention mechanisms, and geometric reasoning in LLMs all leverage the vector structure of $\\ell_p$ spaces.\n\nDespite their practical dominance, **our theoretical understanding of\nembeddings remains limited**. Data in domains like NLP is **high-dimensional**,\n**structurally complex**, and hard to formalize. Theoretical work addresses\nthis via clean abstractions like **graph metrics**.\nSuch abstractions play a role similar to that of **PAC learning** in classification theory: while not modeling every\nneural detail, they offer a principled framework for understanding fundamental capabilities and limits.\n\nThe **dynamic nature** of data in modern systems further motivates our work. In applications involving **LLMs**, the relevant context or knowledge can shift rapidly. **Embedding methods must therefore adapt efficiently**. Traditional techniques, however, are typically **static** and require expensive recomputation. Our work initiates the study of **fully dynamic embeddings into $\\ell_p$ spaces**, a widely used metric class in ML. Modeling data changes via a **dynamic graph** lets us explore embeddings with **provable guarantees** on **distortion**, **non-contractivity**, and **efficiency**. While theoretical, our formulation reflects real challenges in streaming or interactive systems—where representations must update continually without compromising structure or tractability.\n\n> ... empirical evaluations would be necessary ... \n\nWe have performed experiments evaluating our embeddings here:  dropmefiles.com/dfsfg\n\nWe emphasize again that the main focus of our paper is providing a **theoretical understanding** of dynamic embeddings.\n\n> What oracle is available? ... How many edges are allowed to be appended at once?\n\nWe assume that the graph is stored in memory using a standard **adjacency list** representation. **Edge updates (insertions or deletions) occur one at a time**, and the embedding is updated immediately after each modification. That said, our algorithm and analysis are robust enough to conceptually handle **small batches of updates**—for instance, a **polylogarithmic number of changes**—without meaningfully affecting guarantees.\n\n> Current version of Theorem 1.1\n\nWhile we believe our current phrasing follows standard presentation in the literature, we **agree that explicitly associating Theorem 1.1 with Algorithm 1** would improve clarity.  \nThe paper has been revised accordingly.\n\n> Could Theorem 1.2 not be generalized ...\n\nWe thank the reviewer for this excellent question! Indeed, the lower bound in Theorem 1.2 applies to any class of embeddings based on **labeling**—that is, embeddings where each point is mapped to a label (e.g., a coordinate vector or symbolic descriptor), and distances are computed solely from these labels. For example, points could be mapped to coordinates on a sphere, with distances measured via **spherical distance**.  \nWe will apply the generalization in our revision.\n\nIf you feel our response has adequately addressed your major concerns, we would appreciate it if you possibly adjust your score accordingly.", "claims_and_evidence": "Despite the interesting and solid theorems, the current manuscript has significant issues, which makes the claims of the paper vague.\n- Is considering $\\\\ell\\_p$ included the motivation of the paper, or is it just a tool to achieve a low distortion with small update and query time complexities? The abstract says that \"Theoretically, the classic problem in embedding design is mapping arbitrary metrics into $\\\\ell\\_p$ spaces while approximately preserving pairwise distances.\" The first sentence of the fourth paragraph of the Introduction section says \"In this work, we focus on the problem of dynamically embedding into $\\\\ell\\_p$ spaces\" without saying like \"To solve the ... issues,\" so I assume that considering $\\\\ell\\_p$ space is also included in the motivation. If so, the paper should have clarified why we are interested in $\\\\ell\\_p$ space. In other words, why are we dissatisfied with just having the graph itself? Or, why do we not consider other spaces, like hyperbolic space? I understand the advantages of using $\\\\ell\\_p$ space from time complexity and low distortion perspectives, but the motivation description in the Introduction section does not say it is the reason why the Authors focus on the $\\\\ell^p$ space.\n- Problem setting is not clearly formulated. Hence, it is hard for readers to judge whether the Authors' claims are sound or not. What oracle is available? Do we know the full vertices and edges and weights initially? How many edges are allowed to be appended at once? We can guess those problem settings by reading the whole paper, but such workloads would not be needed with clear problem-setting descriptions in one place, before mentioning the proposed algorithm.\n- One fatal issue of the current manuscript is that it does not clarify how the paper contributes to the ICML community, where machine learning is the main focus, as its name suggests. What do we learn by obtaining the distorted metric, e.g., in $\\\\ell\\_p$ from fully available weighted graph data? Why are we dissatisfied with the graph? In some representation learning settings, like TransE (Bordes et al., 2013) or Poincare embeddings (Nickel & Kiela, 2017), we assume the graph is somewhat noisy or incomplete, but through representation learning, they can correct or complete the original data. This procedure can be called \"learning.\" However, regrettably, from a machine learning viewpoint, the Authors' proposed method **just distorts the original graph without providing any beneficial information**, although the method is still interesting as a *data structure*. I do not dare to call it \"machine learning\" if it just converts the original data to another form with distortion. Of course, even if it does not directly solve a machine learning problem, the ICML would accept the work that has the potential to contribute to the machine learning community, provided that the paper explains the potential. However, the current manuscript does not clarify the potential. Actually, the proposed \"data structure\" may have the strong potential to accelerate machine learning on weighted graph data. However, such perspectives are not included in the Introduction section. For the current manuscript to be accepted to the ICML, it would require rewriting from scratch, which is not what the rebuttal period aims at.\n- Even as a data structure paper, it needs to be clarified in what application situations we prioritize the update speed and space complexity by sacrificing the accuracy and query time complexity, since 0 distortion and constant query time can be achievable by the (possibly lazy-updated) distance matrix.\n\nBordes, Antoine, et al. \"Translating embeddings for modeling multi-relational data.\" Advances in neural information processing systems 26 (2013).\n\nNickel, Maximillian, and Douwe Kiela. \"Poincaré embeddings for learning hierarchical representations.\" Advances in neural information processing systems 30 (2017).", "methods_and_evaluation_criteria": "In this paper's case, empirical evaluations would be necessary, while no empirical evaluations are included in the paper. The paper is not like a theoretical analysis of existing established methods or problem settings, where empirical evaluations are not effective. Rather, the Authors have introduced a new problem setting, where edges can both increase and decrease. Hence, the authors are responsible for showing some machine learning problem instances that can demonstrate that the new problem setting is worth considering and that the proposed method works.", "theoretical_claims": "I could not check the details of the proof since even the problem setting is not formulated in the paper. However, I could not find absurd results as far as I checked.", "experimental_designs_or_analyses": "In this paper, Theorems work as verifications of the superiority of the proposed method.\n- This is also a presentation issue, but the current version of Theorem 1.1. is too weak and has no practical implications. The existence of something does not imply we can construct or implement it. To claim that we have solved some issues in computer science, including machine learning, we need to state that like \"Algorithm 1 satisfies ...\" instead of \"there exists an Algorithm A that...\"\n- Having said that, the coexistence of Theorem 1.1 and Theorem 1.2 is a strong point of this paper in that it makes the reason for the choice of Algorithm 1 convincing.", "relation_to_broader_scientific_literature": "Nothing to note here.", "essential_references_not_discussed": "Mentioned in other parts.", "other_strengths_and_weaknesses": "- Theoretical analyses of this paper are interesting and may lead to the proof of upper bound/lower bound in other settings in the field. Especially, the proof of the lower bound, similar to that of the No Free Lunch theorem (in statistical learning theory) seems elegant to me.", "other_comments_or_suggestions": "- Define $m$ and $n$.\n- As discussed above, the current manuscript does not clarify the potential of the paper to contribute to the ICML community. However, as a general computer science (not machine learning but data structure) paper, the theoretical contributions are solid and almost complete. Specifically, providing a data structure and its distortion bound, update complexity, and query complexity are attractive. I would like to humbly suggest the following:\n  - If the Authors still want to aim to submit the work to the machine learning community, please rewrite the paper from scratch to clarify its benefit to the community. For example, (Jain et al., 2016) and (Suzuki et al., 2023), published in the machine-learning context, discussed the embedding problem theoretically in the machine-learning context by formulating it as a prediction problem, a typical machine-learning setting. The latter paper even discusses $\\\\ell\\_p$ embedding. Associating the Authors' work with those studies could make your work's contributions in the machine learning context convincing. Note that those papers discuss static cases only, so the Authors' contribution, which discusses dynamic cases, would still be significant.\n  - Having said that, let me humbly suggest the possibility of submitting the Authors' work to another venue that can appreciate the Authors' work better. In any case, I encourage you to upload your work to some online repositories to secure your priority rights if you have not.\n\nJain, Lalit, Kevin G. Jamieson, and Rob Nowak. \"Finite sample prediction and recovery bounds for ordinal embedding.\" Advances in neural information processing systems 29 (2016).\n\nSuzuki, Atsushi, et al. \"Tight and fast generalization error bound of graph embedding in metric space.\" International Conference on Machine Learning. PMLR, 2023.", "questions_for_authors": "- Could Theorem 1.2. not be generalised to a (general) metric space? If we can generalize it, it would strongly motivate the choice of $\\\\ell\\_p$ space against all the other metric spaces, including sphere, torus, hyperbolic space, etc.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies the problem of maintaining an implicit embedding of a graph metric into $$\ell_p$$, under edge insertions and deletions into the graph. The authors achieve this by exploiting work on dynamic tree based embeddings. 

The reviewers agree that the results and techniques are interesting, and that this paper makes a valuable contribution to the literature on metric embeddings and dynamic graph algorithms. The authors, however, did not make a convincing case for the relevance of the results to ICML - while embeddings are important to ML, it is not clear that this specific problem of maintaining an embedding of a graph metric under insertions and deletions has any connection to ML.
Decision: Accept (poster)