acceptodds
Under review as a conference paper at ICLR 2027

Dynamic Local Search Under Distance Updates for -Clustering

Abstract

Machine learning systems often cluster data that keep changing, such as embeddings that drift during training or networks that keep gaining connections. We introduce a model of dynamic metric spaces in which the point set is fixed and distances only decrease, as happens for example when edges are inserted into a graph and shortest paths shrink. In this model we study a local search approach for -clustering, a generalization of -median and -means objectives. The main computational cost of local search is finding an improving swap, a pair of one center and one non-center whose exchange lowers the value of the objective function. We give a deterministic dynamic algorithm that maintains the best improving swap in time per distance update, instead of from scratch. Building on this data structure, we design an algorithm that maintains a constant factor approximate -clustering with total update time , matching (up to lower order terms) one single run of the fastest deterministic static local-search based approximation algorithm. On the metric space induced by two real evolving graphs with up to 55,000 vertices, our algorithm matches the quality of full recomputation to within 0.25 percent, while running far faster: it handles 1,000 edge insertions in about 10 s, compared to the roughly 5,100 s of a warm start approach which uses the previously computed solution, and to over a week through a naive full recomputation from scratch.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
local search, dynamic algorithm, clustering, k-median, k-means

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_PaaoOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This manuscript studies dynamic local search for (k,z)-clustering (z=1 is k-median and z=2 is k-means) in dynamic metric spaces subject to monotonic distance decreases.

To get over the static O(n^2) bottleneck of finding improving center/non-center swaps in local search, the paper designs a deterministic dynamic swap-table data structure. It maintains the best improving swap in worst-case time O(k log k + log n) when the updated pair is disjoint from the current centers, and O(n log n) otherwise, with O(nk) preprocessing.

The paper proves that this data structure maintains a O(1) approximate clustering with total update time O~(k n^2) across all adversarial distance decreases, which matches the runtime of one static local search.

The method is evaluated on temporal graph snapshots (DBLP & Stack Overflow, up to 55K vertices) for k-median, against FastPAM1 (cold start or with warmup).

Critical strengths

S1. Proving that an arbitrary sequence of distance decreases can be maintained in total update time O~(k n^2) is a notable theoretical achievement in dynamic algorithms, as this matches up to polylog factors the runtime of one static local search.

S2. Algorithm is fully deterministic, and provides worst-case guarantees against adaptive adversaries.

Critical weaknesses

W1. Motivating monotonic distance decreases with "embedding drift" is incorrect. The dynamic model is limited strictly to distance decreases. This is well-motivated for shortest-path graph growth (with edge insertion), but it cannot accommodate metric fluctuations where distances increase, edges are deleted, or points are dynamically added/removed.

W2. Isolating swap-table maintenance while ignoring the Omega(n^2) cost of dynamic APSP distance maintenance gives a false impression of real-world speedups on evolving graphs.

W3. Edge insertions rarely trigger any swap improvements. So comparing solely against FastPAM1 methods (which rebuild swap tables from scratch at every insertion) constructs an artificial baseline advantage. A simple lazy threshold baseline (e.g., recompute only after objective drift exceeds some epsilon) must be benchmarked.

W4. Extending local search approximation guarantees via rho-relaxed triangle inequalities introduces large constant factors into the approximation that are not properly discussed in the paper.

Questions for authors

Q1. What is the exact numerical constant-factor approximation ratio resulting from the proof in Appendix B when instantiated for k-median (z=1) and k-means (z=2) in a \rho-relaxed metric space?

Q2. How does your dynamic local search compare in wall-clock time and objective cost against a lazy baseline that triggers local search only when cumulative edge insertions modify vertex neighborhoods of existing centers?

Q3. If an incremental APSP data structure (like Ramalingam-Reps or Even-Shiloach) is integrated to supply the distance updates, what is the net wall-clock throughput per edge insertion?

1 comment

\paragraph{Motivation and scope beyond graphs (qVXZ; Paao: W1).} We agree that the embedding example may only apply to very specific settings in which the drift is of a form that makes points move closer but not apart. We will state this limitation more explicitly.

However, we would like to stress that our contribution is not limited to dynamic graphs. Our model and algorithms apply to any fixed point set whose pairwise distances only decrease; graphs under edge insertions are just one such instance. Another example is when distances are estimates that are refined as new measurements arrive: the latency between two servers is commonly estimated by the minimum round-trip time observed so far, which can only decrease. We ran our experiments on graphs because in this setting natural update sequences from real data are readily available.

\paragraph{Recompute only after objective drift exceeds some epsilon (Paao: W3, Q2).} This criterion does not guarantee detection of improving swaps, since objective drift alone does not determine whether such a swap exists. Notice that these two scenarios are possible:

  1. The cost remains the same, but a new improving swap becomes available (because OPT decreases sufficiently). By applying the suggestion, we would miss this case.
  2. The cost decreases, but no improving swap exists.

Therefore, we use the swap table algorithm to efficiently detect whether a sufficiently improving swap exists. Regarding (Q2), we would politely like to note that we do not see the intuition why this would be a good baseline.

\paragraph{APSP maintenance cost (Paao: W2, Q3).} In our theoretical result for graphs (Theorem 1.5), we account for the cost of maintaining distances. In the experiments, we assume that the distance matrix is given, since the model of our main contribution works with given distances rather than computing them from a graph. Our goal was to clearly isolate the performance of the local search aspect instead of benchmarking the full pipeline.

\paragraph{Approximation constants (Paao: W4, Q1).} After every adversarial update, the maintained solution satisfies the same condition that static local search guarantees at termination. By choosing ρ\rho sufficiently close to 11 and δ\delta sufficiently small, the approximation bound can be made arbitrarily close to the corresponding static bound.

Reviewer_qVXZOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies weighted (k,z)(k,z)-clustering, which is a generalization of the well studied k-median and k-means objectives for clustering (kk is the number of centers in the clustering, zz is the exponent for the point-center distance in the objective - higher zz penalizes larger distances more heavily). In their setting, the underlying pointset we wish to cluster is fixed, but the distances between the points themselves evolve over time. They consider the decrease-only setting, where the distances can only decrease with time (if the distances are obtained from an underlying graph, this corresponds to adding new edges which can decrease shortest path lengths). They also assume that the points satisfy the triangle inequality (upto a factor of ρ≥1\rho \geq 1).

Their algorithm uses a deterministic local-search approach, as it is known that a local optimal solution to this problem (when there is no improving swap between a center and non-center) is also globally optimal up to constant factors for fixed zz. Recomputing the best improving swap takes O(n2)O(n^2) time using FastPAM (Schubert & Rousseeuw, 2021) and they improve this subroutine to O(nlog⁡n)O(n \log n) for their distance-decrease only model (Note that FastPAM can handle both distance decreases and increases, as it recomputes the entire swap table). In particular, their algorithm takes O(nlog⁡n)O(n \log n) time when the update involves a center, and O(klog⁡k+log⁡n)O(k \log k + \log n) time when it involves two non-centers. They do this by using segment trees with lazy propagation, as entire ranges of the swap table change by the same amount under distance decreases. The main idea behind their algorithm to handle a (batch of) distance updates is as follows:

  1. Use their new subroutine to maintain the best improving swap for each distance update.
  2. Then, perform the best swap if it improves the objective sufficently (the decrease in cost is at least Ω(1/k)\Omega(1/k) times the current cost)
  3. Recompute the swap table in O(n2)O(n^2) time using FastPAM, and check the best swap again - do this until the best swap no longer improves the objective sufficiently.

Since the total number of sufficiently improving swaps across the execution is bounded by O~(k)\tilde{O}(k), the total time spent for the expensive recomputations of the swap tables is O~(kn2)\tilde{O}(kn^2). Since only O~(k)\tilde{O}(k) points ever become centers, the effective number of updates involving a center is O~(kn)\tilde{O}(kn) as they use geometric rounding for the distances between points. Similarly, there are O~(n2)\tilde{O}(n^2) effective updates that don't involve a center. Thus, the time taken for maintaining the best improving swap is O~(nk)⋅O(nlog⁡n)+O~(n2)⋅(klog⁡k+log⁡n)=O~(kn2)\tilde{O}(nk) \cdot O(n \log n) + \tilde{O}(n^2)\cdot (k \log k + \log n) = \tilde{O}(kn^2).

Consequently, they achieve O~(kn2)\tilde{O}(kn^2) total update time, which matches (upto polylog factors) the running time of the fastest deterministic static local-search algorithm for (k,z)(k,z)-clustering. They also give a randomized algorithm for the (k,z)(k,z) clustering problem on weighted undirected graphs under edge insertions, which maintains an O(1)O(1)-approximate solution with high probability, and a total update time of O~(km1+o(1)+k3)\tilde{O}(km^{1 + o(1)} +k^3) which is an improvement on prior results when k≤mk \leq \sqrt{m}.

Critical strengths

The paper gives a unified deterministic framework to approximate well-studied clustering objectives like kk-median and kk-means when distances only decrease. Their O~(kn2)\tilde{O}(kn^2) total update time bound matches the best deterministic local-search based algorithm for the static variant of the problem (where distances are fixed and we just wish to compute an approximate solution), and they maintain O(1)O(1)-approximation after each (batched) update.

Their experiments on large real evolving graphs also demonstrate significant improvements in running time compared to naive recomputation after each update, while maintaining solutions of similar quality.

Critical weaknesses

While their O~(kn2)\tilde{O}(kn^2) total update time bound matches the runtime of the best static deterministic local-search algorithm, there are better algorithms for the static case that do not use local search. For instance, for fixed zz, a deterministic constant factor approximation is possible for the (k,z)(k,z) clustering problem in O~(n2)\tilde{O}(n^2) time (Mettu & Plaxton, 2003). Similarly, a randomized constant factor approximation is possible (with high probability) in O(nk)O(nk) time (Mettu & Plaxton, 2004) when Ω(log⁡n)≤k≤O(n/log⁡2n)\Omega(\log n) \leq k \leq O(n/\log^2n).

The distance-decrease only assumption is natural for graphs with edge-insertions, but I'm not sure how applicable it is for more general real-world settings. For embeddings that change over time over the course of training, while some pairs of points might grow closer, some might grow further apart.

Questions for authors

Is there any reason you don't compare with static constant-factor baselines that do not use local search (like the ones mentioned above) in the experiments?

Could you highlight which parts of the analysis fail when distance increases are also allowed? For example, I think the subroutine that maintains the best-improving swap can still be made to work with distance increases.

1 comment

\paragraph{Motivation and scope beyond graphs (qVXZ; Paao: W1).} We agree that the embedding example may only apply to very specific settings in which the drift is of a form that makes points move closer but not apart. We will state this limitation more explicitly.

However, we would like to stress that our contribution is not limited to dynamic graphs. Our model and algorithms apply to any fixed point set whose pairwise distances only decrease; graphs under edge insertions are just one such instance. Another example is when distances are estimates that are refined as new measurements arrive: the latency between two servers is commonly estimated by the minimum round-trip time observed so far, which can only decrease. We ran our experiments on graphs because in this setting natural update sequences from real data are readily available.

\paragraph{Static algorithms that do not use local search (qVXZ).} Indeed, there are faster static algorithms that do not use local search. Nevertheless, local search is a highly relevant algorithmic paradigm used in clustering. We therefore believe it is valuable to restrict our focus to this paradigm.

From the theoretical side, we can add that the two algorithms of Mettu and Plaxton have larger constants in their approximation guarantees, while local search admits a substantially smaller approximation ratio. For example as we write in Line 1421, for the kk-median objective with ρ=1\rho = 1, our analysis can be adapted to yield an approximation ratio close to 55---which is substantially smaller than the factors guaranteed by the two algorithms of Mettu and Plaxton. How all these static algorithms compare in terms of solution quality on general metrics is an interesting question; we are not aware of any thorough experimental studies investigating this question.

\paragraph{Distance increases (qVXZ).} Theorem 1.3 can be extended to distance increases by adapting the algorithm and its analysis. Theorem 1.4 relies on the fact that the cost decreases with each improving swap and cannot increase after distance decreases. Since distance increases can raise the cost, the current analysis does not extend the total update time guarantee of Theorem 1.4 to distance increases.

Reviewer_rM21OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies dynamic ((k,z))-clustering in a model where the point set is fixed while pairwise distances can decrease over time. The main technical contribution is a data structure that maintains the exact best improving swap under distance decreases in (O(n\log n)) worst-case update time, improving over recomputing the swap table from scratch in (O(n^2)) time.

Building on this data structure, the authors develop a deterministic algorithm that maintains an (O(1))-approximate ((k,z))-clustering with (\widetilde O(kn^2)) total update time, essentially matching the running time of a single execution of the fastest known deterministic static local-search-based algorithm. The authors also apply their technique to incremental graph clustering, improving the approximation/runtime tradeoff of a recent result. Experiments demonstrate substantial speedups compared to recomputation-based baselines.

Critical strengths
  • A clean and meaningful theoretical guarantee. The (\widetilde O(kn^2)) total update bound is appealing, as it allows a potentially long sequence of distance decreases to be handled at essentially the cost of a single static local-search computation. This is a substantial improvement over straightforward approaches that explicitly update the swap table after each distance change.

  • A simple and elegant algorithmic approach. The structural observation underlying Theorem 1.3 enables efficient implicit maintenance of the swap table. Combined with the monotonicity of the objective under distance decreases, it yields a clean amortized analysis. I particularly like the interpretation of local search as a single process continuing across the entire update sequence.

  • Deterministic guarantees and generality. The algorithm is deterministic and thus robust against adaptive adversaries. The swap-table data structure works without the triangle inequality, while the approximation algorithm accommodates relaxed metric spaces.

Critical weaknesses
  • The novelty of the model seems overstated. The claim in Lines 58–59 that clustering with a fixed point set and changing distances has not been studied before seems too broad. For example, dynamic graph clustering already considers fixed vertices whose shortest-path distances change under edge updates. The distinction appears to be that this paper directly handles arbitrary pairwise distance updates. The authors should clarify this distinction and position their contribution more carefully.

  • The main technical observation is relatively simple and closely related to existing techniques. The key property in Lemma 3.1, that the change in swap gain is identical across most rows of a column, seems closely related to the decomposition already exploited by FastPAM. While the dynamic extension is useful, the conceptual novelty and technical depth seem somewhat limited. It would be helpful to clarify the main technical difficulty beyond the existing FastPAM decomposition.

  • A natural baseline is missing. By Lemma A.4, one can explicitly update all entries of the swap table in (O(kn)) time after a single distance decrease. Thus, the proposed (O(n\log n)) update time is advantageous for sufficiently large (k), but not necessarily for small (k). A comparison with this straightforward incremental baseline would better establish the significance of the improvement.

  • The total update-time guarantee needs some clarification. Theorem 1.4 states a total update time of (\widetilde O(kn^2)), apparently independent of the number of adversarial updates. However, an arbitrary number of small distance decreases may occur without changing the rounded distances. It seems that processing the raw update sequence would require an additional term depending on its length, unless such updates are excluded by the model. The authors should clarify how these updates are accounted for.

Questions for authors

I would appreciate the authors' response to the weaknesses raised above.

1 comment

\paragraph{Novelty of the model (rM21).} The reviewer is right that our model builds on results for dynamic graphs where the vertex set is fixed and shortest-path distances change under edge updates. Our sentence in lines 58--59 was too broad, and we rephrase it. Our goal is to be more general than the graph setting: in our model an adversary directly updates arbitrary pairwise distances of a fixed point set, and graphs under edge insertions are a special case of this.

\paragraph{Relation to FastPAM and Lemma 3.1 (rM21).} The FastPAM algorithm is static, whereas in the dynamic setting we must analyze the swap gains before and after an adversarial distance update. A brief explanation of the proof of Lemma 3.1 is given in Lines 353--360, and its consequences for efficient maintenance of the swap table are described in Lines 1027--1032. Although the underlying decomposition is related to FastPAM, the additional challenge is to update the swap gains efficiently when distances change.

\paragraph{Comparison with the straightforward baseline (rM21).} By explicitly updating all entries of the swap table in O(kn)O(kn) time after a single distance decrease, the total update time would be O(kn)⋅O~(n2)=O~(kn3)O(kn) \cdot \tilde{O}(n^2) = \tilde{O}(kn^3). Even if we take advantage of the fact that some entries can remain unchanged (using Observation A.5), the total update time would be O(kn)⋅O~(kn)+O(k)⋅O~(n2)=O~(k2n2)O(kn) \cdot \tilde{O}(kn) + O(k) \cdot \tilde{O}(n^2) = \tilde{O}(k^2n^2) (see Lemma A.12). Therefore, our~O~(kn2)\tilde{O}(kn^2) theoretical bound improves the dependence on kk by a factor of kk, up to logarithmic factors.

\paragraph{Total update time in Theorem 1.4 (rM21).} An additive term O(O(number of adversarial updates$)$ is missing from the total update time bound. However, we emphasize that this term is natural, as it accounts for reading and filtering the incoming adversarial updates. We will include it explicitly in the revised theorem statement.

Comments on the paper

1 comment

Each paragraph addresses comments, weaknesses (W), or explicit questions (Q) from the reviewers named in parentheses.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.