Approximate Forest Completion and Learning-Augmented Algorithms for Metric Minimum Spanning Trees
Authors: Nate Veldt
Thomas Stanley
Benjamin W Priest
Trevor Steil
Keita Iwabuchi
T.S. Jayram
Geoffrey Sanders
Venue: ICML 2025 poster (2025)
Keywords: minimum spanning trees
learning-augmented algorithms
general metric spaces
graph algorithms
Primary area: general_machine_learning->scalable_algorithms
TL;DR: We design learning-augmented algorithms for metric minimum spanning trees based on growing a spanning tree from an initial forest

Abstract: Finding a minimum spanning tree (MST) for $n$ points in an arbitrary metric space is a fundamental primitive for hierarchical clustering and many other ML tasks, but this takes $\Omega(n^2)$ time to even approximate. We introduce a framework for metric MSTs that first (1) finds a forest of trees using practical heuristics, and then (2) finds a small weight set of edges to connect disjoint components in the forest into a spanning tree. We prove that optimally solving step (2) still takes $\Omega(n^2)$ time, but we provide a subquadratic 2.62-approximation algorithm. In the spirit of learning-augmented algorithms, we then show that if the heuristic forest found in step (1) overlaps with an optimal MST, we can approximate the original MST problem in subquadratic time, where the approximation factor depends on a measure of overlap. In practice, we find nearly optimal spanning trees for a wide range of metrics, while being orders of magnitude faster than exact algorithms.

Approximate Forest Completion and Learning-Augmented Algorithms for Metric Minimum Spanning Trees
Nate Veldt Thomas Stanley'
Benjamin W. Priest 2 Trevor Steil? Keita Iwabuchi 2 Geoffrey Sanders?
T.S. Jayram
Abstract
problems (Held & Karp, 1970), and feature selection (Labbé et al., 2023). The problem also has a very well-known con- nection to hicrarchical clustering (Gower & Ross, 1969) and has been used as key step in clustering astronomical data (Barrow al., 1985; March et al., 2010), analyzing gene expression data (Xu et al., 2002), document cluster- ing (Xu & Uberbacher, 1997), and various image segmenta- tion and classification tasks (Xu & Uberbacher, 1997; An et al., 2000; La Grassa et al., 2022).
Finding minimum spanning tree (MST) for points in an arbitrary metric space is funda- mental primitive for hierarchical clustering and many other ML tasks, but this takes ((n²) time to even approximate. We introduce a framework for metric MSTs that first (I) finds forest of trees using practical heuristics, and then (2) finds small weight set of edges to connect disjoint components in the forest into spanning tree. We prove that optimally solving step (2) still takes ((n²) time, but we provide a subquadratic 2.62- approximation algorithm. In the spirit of learning- augmented algorithms, we then show that if the heuristic forest found in step (1) overlaps with an optimal MST, we approximate the original MST problem in subquadratic time, where the approximation factor depends on a measure of overlap. In practice, we find nearly optimal span- ning trees for a wide range of metrics, while being orders of magnitude faster than exact algorithms.
This paper is motivated by challenges in efficiently com- puting metric MSTs modern machine learning (ML) and data mining applications. The most fundamental challenge is simply the massive size of modern datasets. In theory one can always find an MST for n points by computing all O(n²) distances and running an existing MST algorithm. However, this quadratic complexity is far too expensive both in terms of runtime and memory for massive datasets. A sec- ond challenge handling complicated metric spaces. Most existing algorithms for metric MSTs are designed for Eu- clidean distances or other simple metric spaces, often with particular focus small-length feature vectors (March et al., 2010; Agarwal et al., 1990; Shamos & Hoey, 1975; Vaidya, 1988; Arya & Mount, 2016; Wang et al., 2021). While useful in certain settings, these are limited their ap- plicability to high-dimensional feature spaces and complex distance functions. Many modern ML tasks focus on non- Cartesian data (e.g.. videos, images, text, nodes in graph, entire graphs) which must be classified, clustered, or otherwise compared, possibly after being embedded into some metric space. In these settings, even querying the distance score between two data points becomes non-trivial and often involves some level of uncertainty. Computing distances for popular non-Euclidean metries like Leven- shtein distance or graph kernels is far more expensive than computing Euclidean distances. This motivates body of research minimizing the number of queries needed to find minimum spanning tree (Bateni et al., 2024; Erlebach et al., 2022; Hoffmann et al., 2008; Megow et al., 2017).
1. Introduction
Finding minimum spanning tree of a graph is classical combinatorial problem with well-known algorithms dating back to the early and mid 1900s (Borûvka, 1926; Prim, 1957; Kruskal, 1956). widely-studied special case in the- ory and practice is the metric MST problem, where each node corresponds
point in a metric space and every pair of points defines an edge with weight equal the distance between points. Finding metric MST has widespread appli- cations including network design (Loberman & Weinberger, 1957), approximation algorithms for traveling salesman
'Department of Computer Science and Engineering, Texas A&M University *Center for Applied Scientific Computing, Lawrence Livermore National Laboratory. Correspondence to: Nate Veldt enveldt@tamu.edur
These applications and challenges motivate new approaches for efficiently finding good spanning trees for set of points in an arbitrary metric space. Idcally, we would like an
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Approximate Forest Complction for Metric Minimum Spanning Trees
algorithm whose memory, runtime, and distance query com- plexity are all o(n²), while still being able to find spanning trees with strong theoretical guarantees in arbitrary metric spaces. Unfortunately, there are known hardness results that pose challenges for obtaining meaningful subquadratic algorithms. In particular, it is known that finding any con- stant factor approximation for an MST in an arbitrary metric space requires knowing ((n2)) edges in the underlying met- ric graph (Indyk, 1999). Overcoming this inherent challenge requires exploring additional assumptions and alternative types of theoretical approximation guarantees.
summarize, we have the following contributions.
New algorithmic framework. We introduce METRIC FOREST COMPLETION for large-scale metric MST prob- lems, along with strategies for computing an initial forest and a discussion of how our problem fits into the recent framework of
algorithms.
Approximate completion algorithm. We prove that optimally solving MFC requires Q(n²)) edge queries, but provide an approximation algorithm with approximation factor = 2.62. Our algorithm has a query complexity of o(n²) as long as the initial forest has o(n) components. Learning-augmenter approximation guarantees. We prove that if the initial forest y-overlaps with an optimal MST, then our algorithm is (27 + 1-aaprroximation algorithm for the metric MST problem. If y = 1, this means all edges in the forest are contained in an optimal MST. A precise definition for y > 1 is given in Section 3. Experiments. We show that our method is extremely scalable and obtains very good results synthetic and real datasets. We also show that simple heuristics provide initial forests with 7-overlap values that are typically smaller than 2 on various datasets and distance functions, including many non- -on-Euclidean metrics.
The present work: metric forest completion. To achieve our design goals and overcome existing hardness results, we take our inspiration from the nascent field of learning- augmented algorithms, also known as algorithms with predictions (Mitzenmacher & Vassilvitskii, 2022). The augmente paradigm assumes access to an ML heuristic that provides prediction or "wwarm start" that is useful in practice but does not come with a priori theoreti- cal guarantees. The goal is to design an algorithm that (1) comes with improved theoretical guarantees when the ML heuristic performs well, and (2) recovers similar worst-case guarantees if the ML. heuristic performs poorly. Improved theoretical guarantees can take various forms, including faster runtimes (e.g., for sorting (Bai & Coester, 2023), bi- nary search (Lin et al., 2022) or maximum s-t flows (Davies et al., 2023)), improved approximation factors (e.g., for NP-hard clustering problems (Ergun et al., 2022; Nguyen et al., 2023)), better competitive ratios for online algorithms (c.g., for ski rental problems (Shin et al., 2023)), or some combination of the above (e.g., better trade-offs for space re- quirements vs. false positive rates for Bloom filters (Kraska et al., 2018)). These improved guarantees given in terms of some parameter measuring the quality of the prediction, which is typically not known in practice but provides a concrete measure of error that can be used in theoretical analysis.
2. Technical Preliminaries and Related Work
We cover several technical preliminaries to set the stage for our new MFC problem and algorithms. Additional related work can be found in Section 5.
Graph notation and minimum spanning trees. For an undirected graph G = (V, E)) and weight function w: E -+ R+, we denote the weight of an edge (u, v) as w(u, v). Wav; We- The weight of edge set F C E is denoted by w(F)= = Eeer We. We frequently use w(G) = w(E) to denote the weight of all edges in G = (V, E).
The minimum spanning tree problem on G with respect to weight function w seeks a spanning tree T = (V, Er) of G that minimizes w(Er). When w is clear from context we will refer to T simply as an MST of G. We do often consider multiple spanning trees of the same graph, each optimal for different weight function. In these cases we explicitly state the weight function associated with an MST.
In this paper we specifically assume access to fragments of a spanning tree for metric MST problem (called the initial initial forest), that takes the form of spanning tree for each component of some partitioning of the data objects. This input can be interpreted as heuristic approximation for the forest that would be obtained by running a few iterations of a classical MST algorithm such as Kruskal's (Kruskal, 1956) or Boruvka's 's (Borůvka, 1926). Given this input, we formal- ize the METRIC FOREST COMPLETION problem (MFC), whose goal is to find minimum- mniimu set of edges that connects disjoint components to produce a full spanning tree. Although optimally solving MFC takes 2(n²) distance queries, we design a subquadratic approximation algorithm for MFC and prove a learning-augnnn augmented style approxima- tion guarantee for the original metric MST problem. To
There are many well-known greedy algorithms for opti- mally constructing an MST. We review Kruskal's (Kruskal, 1956) and Boruvka's (Borûvka, 1926) algorithms as their mechanics are relevant for understanding our approach and results. These methods first place all nodes into singleton components. Each iteration of Kruskal's 's algorithm iden- tifies a minimum weight edge that connects two nodes in different components, and adds it to a forest of edges (ini- tialized to the empty set at the outset of the algorithm) that is guaranteed to be part of some MST. This proceeds until
2

---

Approximate Forest Complction for Metric Minimum Spanning Trees
matic closest pair problem (BCP) is a particularly relevant computational primitive for metric MSTs. The input BCP is two sets of points A and B in a metric space. The goal is then to find pair of opposite-set points (one from A and one from B) with smallest distance. One can implicitly apply a classical MST algorithm such as Kruskal's or Boruvka's 's al algorithm to Gx by repeatedly solving BCP problems. In more detail, these algorithms must find one or more discon- nected components in an intermediate forest (see Figure 1b) to join at each step via minimum weight edges. Finding minimum weight edge between two components exactly corresponds to a BCP problem. This connection between metric MSTs and BCP is well known and has been leveraged in many prior works on metric MSTs (Agarwal et al., 1990; Callahan & Kosaraju, 1993; Narasimhan & Zachariasen, 2001; Chatterjee et al., 2010).
(a) Optimal metric MST
(b) Forest from Kruskal's
Figure 1: (a) An MST for an implicit graph Gx defined by 75 points in 2D Euclidean space. (b) The forest at intermediate step of Kruskal's algorithm.
all components of the forest have been merged into one tree. The method is equivalent to ordering all edges based on weight and visiting them in order, greedily adding the ith edge to the spanning tree if and only if its endpoints are in different components. Boruvka's algorithm (Borûvka, 1926) is similar, but instead identifies a minimum weight edge incident to each component, adding all of them to the growing forest. Both algorithms can be implemented to run in (m log time where n = |V| and m = [E.. Faster algorithms, often based on one of these algorithms, have been developed. The fastest deterministic algorithm has a runtime of O(m- (m, n1) where a is the inverse of the Ackerman function (Chazelle, 2000). For this paper it suf- fices to know that finding MST takes ((m) time where Ô hides factors that are logarithmic (or smaller) in n.
3. Metric Forest Completion
We now formalize our METRIC FOREST COMPLETION (MFC) framework, which assumes access to an initial forest that then grown into a full spanning tree.
Defining the initial forest. As starting point for the metric MST problem on (X, d), we assume access to partitioning P = (P,, P2..... Pt}} where X = U._11 P. and P. n 0 for i * j. For each component P. we have partition spanning tree T; = (P,, Frr;) for that component. See Figure 2a for an illustration. Let G. = (X, Es) represent the union of these trees, which has the same node set as Gx, and edge set F. = U._1 Fr, Fach set P, for i E [t] defines group of points in X' as well as a connected component of G.. We refer to this as the initial forest for MFC. To provide intuition, the initial forest can be viewed as proxy for the forest obtained at an intermediate step of Kruskal's or Boruvka's algorithm (see Figure lb). While this serves as useful analogy, we stress that the partitioning will typically be obtained using much cheaper methods and will not satisfy any formal approximation guarantees.
The metric MST problem. Throughout the paper we let (X, d) be a finite metric space where X =
p.. a set of data points and d(xr, 227) is the distance between the ith and jth points. In order to be metric space, d must satisfy the triangle inequality: d(I;;, x.y) S d(s,, + d(zx,, xT)) ) for all triplets j, k E [m] = (1, n). Aside from this we make no formal assumptions about the points or d. The space is associated with a complete graph Gx= = (X, Ex) where we treat X' as a node set and the edge set Ex = (2)
(() includes all pairs of nodes. The weight function wx for Gx is defined by 5
Our theoretical analysis requires very few assumptions about the partitioning P and partition spanning trees (initial forest) {T;: i = 1,2....t) .t] that are given as input to the METRIC FOREST COMPLETION problem. In particular, we need not assume that T, is a minimum spanning tree or even good spanning tree of P.. Similarly, the components are not required to be sets of points that are close together in the metric space in order for the problem to be well-defined. Nevertheless, in practice the hope is that P identifies groups of nearby points in X' and that T; is reasonably good spanning tree for P. for each i E [t] = {1.2..... .t. Ap- pendix covers two practical strategies and corresponding runtimes for finding an initial forest. In summary these are:
d(x,, 22). This graph Gx is implicit; in order know the weight of an edge we must query the distance function d. We make assumptions regarding the complexity of querying distances. Rather, we will give the complexity of our algorithms both in terms of the runtime and number of queries.
The metric minimum spanning tree problem is simply the MST problem applied Gx (see Figure 1a). This can be solved by querying the distance function O(n²) times to form Gr, and then applying an existing MST algorithm. We show it is more practical to implicitly deal with Gx via edge queries, while solving different types of nearest neighbor problems over subsets of X.
Strategy 1: k-centering. Apply fast k-centering heuristic
Metric MSTs and bichromatic closest pairs. The bichro-
3

---

Approximate Forest Complction for Metric Minimum Spanning Trees
to X' form P. e.g., using simple 2-approximation (Gon- zalez, 1985) or fast distributed methods (Malkomes al., 2015; McClintock & Wirth, 2016).
k-NN graph. Compute an approximate k-nearest neighbor graph of X for reasonably small hi, e.g.. via the scalable k-NN descent algorithm (Dong et al., 2011) or its distributed generalization (lwabuchi et al., 2023).
Strategy 2:
(a) Initial forest (P; (2:})
(b) M (in orange)
Similar but more restrictive strategies have been used by previous heuristics for Euclidean MSTs (see Section 5).
V/
4/
Defining the MFC problem. METRIC FOREST COMPLE- TION seeks to connect an initial forest into a spanning tree for Gx. Let P(x) E P denote the component that x E X belongs to. The set of inter-component edges
V/2
V/s
3/1
V/
(c) Gp w.E.t w
(d) MST of Gp w.r.t. w²
I= ((.,)) E X X: P(z) * P(y)).
We wish find minimum weight set of edges M C I so that M U E, defines connected graph on X. If M satisfies these constraints we say it is a valid completion set and that M completes P. The MFC problem can then be written as
minimize
(x(M) + wx( subject to M completes P.
(L)
(c) True metric MST
(f) MST overlap with P
Figure 2: (a) An initial forest for small metric MST prob-
Let M* denote an optimal completion set. The graph T (X, E,UM)) is then guaranteed to be a tree (see Figure 2b); if not we could remove edges to decrease the weight while still spanning X' If the forest G, is in fact contained in some optimal spanning tree of Gx (which would be the case if were obtained by running a few iterations of Kruskal's or Boruvka's is algorithm), then solving MFC would produce an MST of Gx. In practice this will typically not be the case, but the problem remains well-defined regardless of any assumptions about the quality of the initial forest.
lem. (b) The optimal solution to MFC. (c) The coarsened graph Gp with respect to optimal weight function wt. (d) An MST of Gp with respect to w², which can in theory be used to find M (e) A true MST of the data points. (f) The overlap between the initial forest and this true MST, which can be used to certify y S 1.12 for this example.
p 1 (not necessarily constant), any algorithm that finds a set M C. I that is feasible for (1) and satisfies wx (M) S p wx (x requires Q(n²) queries.
The objective function in Eq. (1) includes the weight of the initial forest wx (Er). Although this is constant with respect to M and does not affect optimal solutions, there are several reasons to incorporate this term explicitly. Most importantly, our ultimate goal is to obtain good spanning tree for all of Gr, and thus the weight of the full spanning tree (i.e., the objective in Eq. 1) is a more natural measure. Considering the weight of the full spanning tree also makes more sense augmentd algorithm analysis,
Proof of Theorem 3.1. Let be a set of n points that are partitioned into two sets P1 and P2 of size n/2. Define a distance function d such that d(a, b) 1 for a randomly chosen pair (a, b) E P1 x Po. and such that d(x,, v) 2p for all other pairs (x,, v) E (*) (((a b)). Note that this dl is metric. The MFC problem on this instance is identical to solving BCP on P1 and Ps. The unique optimal solution is exactly M = (a, b), and no other choice of M C I comes within a factor p of this solution. Thus, any p-approximation algorithm must find the pair (a, b) with distance I among a collection of A(n²)) pairs, where all other pairs have distance 2p. This requires M(n²) queries.
in the context of our where the goal is to approximate the original metric MST problem on Gx. under different assumptions about the ini- tial forest. We note finally that excluding the term wx (F2) rules out the possibility of any meaningful approximation results. We prove the following result using a reduction from BCP to MFC, combined with slight variation of a simple lower bound for monochromatic closest pair that was shown in Section 9 of Indyk (1999).
The MFC coarsened graph. The MFC problem is equiv- alent to finding a minimum spanning tree in a coars- ened graph Gp = (Vp, Ep) with node set Vp = (U1, o2,..., v.) where v represents component P.. We
Theorem 3.1. Every optimal algorithm for MFC has (2n²²) query complexity. Furthermore, for any multiplicative factor

---

Approximate Forest Completion for Metric Minimum Spanning Trees
U3
U
4
2/2
V1
(a) Computing diy
(b) Gp w.r.t.
(c) MFC-Approx output
Figure 3: (a) Finding the minimum distance between components P. and P, (dashed line) is an expensive bichromatic closest pair problem. MFC-Approx instead performs a cheaper nearest neighbor query for a representative point in each component (s, and 8j. shown as stars). (b) Applying this each pair of components produces a weight function w for the coarsened graph Gp. Finding an MST of Gp with respect to i yields (c) 2.62 aa.p-pppxoiiiiiinn for MFC.
refer to as the ith component node. This graph is com- plete: Ep includes all pairs of component nodes. Figure 2c provides an illustration of the coarsened graph. Finding an MFC solution M S I is equivalent to finding an MST in Gp (see Figure 2d) with respect to the weight function w": Ep + R defined for every j, E (1,2......)) by d(x,y). (2)
places inside P. relative to the weight of edges an optimal MST places inside P. When d is clear from context we will simply write 7. Lower ratios for 7 are better. Because of the minimizing property of any MST, and because E, is fully connected within each P; even though an MST need not be, we always have (P)) > This bound is tight exactly when the initial forest is contained in some optimal MST. For reasonable initial forest where each P. is set of nearby points and T; is reasonably good spanning tree for Pt, we would expect to be larger than 1 but still not too large. Figure 2 provides an example where we can certify that y S 1.12 by comparing against one optimal MST. We later show experimentally that we can quickly obtain initial forests with small 7-overlap for a wide range of datasets and metrics. In practical applications we typically would not compute 7, as this is more computationally expensive that solving the original metric MST problem. However, using Y as a theoretical measure of quality, we will design a carning-augmenter algorithm that improves on worst- case results when the quality good, while still recovering standard worst-case results when the quality is bad.
min w/y wn (va, = d(P.. sEP..EP,
Computing wi, exactly requires solving a bichromatic clos- est pair problem over sets P; and P,. A straightforward approach for computing wiy is to check all [Pal [Pyl pairs of points in P3 x Py. However, in the worst case where cluster sizes are balanced, computing all of wn requires ((n?) queries, which is not surprising given Theorem 3.1. Nevertheless, this notion of coarsened graph will be very useful in developing approximation algorithms for MFC.
MFC as a learning-augmented framework. Our approach fits the framework of the initial forest can be viewed as prediction for a partial metric MST, such as the forest obtained by running several iterations of classical MST algorithm. In ideal set- ting, the initial forest would be subset of an optimal MST. If so, then an optimal solution to MFC would produce an optimal metric MST. We relax this by introducing a more general way to measure how much an optimal MST "over- laps" with initial forest components. Let Tx represent the set of minimum spanning trees of Gx. and T Tx denote an arbitrary MST. For components P (P1, P2..... P.). let T(P.) denote the induced subgraph of T on P.. and let T(P)- = U T(P:) denote the edges of T contained inside components P. Larger values of wx(T(P)) indi- cate better initial forests, since this means an optimal MST places a larger weight of edges inside these components. We define the y-overlap for the initial forest to be the ratio
algorithms in that
4. Approximate Completion Algorithm
We now present an algorithm that approximates MFC to within a factor c < 2.62. We also prove it can be viewed as algorithm for metric MST, where the approximation factor depends on the 7-overlap of the initial forest. Pseudocode for our algorithm is provided in the appendix. Here in the main text we give a full description of the algorithm along with visual aids in Figure 3. Due to space constraints, proofs are relegated to the appendix.
Algorithm description. Our algorithm starts by choosing an arbitrary point s; E P. for each i E {1, 21,2...., .} to be the component's representative (starred nodes in Figure 3). The algorithm computes the distance between every point E X' and all of the other representatives. For every pair of
(P) wx wx((E))
max ux (P)). /
(3)
TETx
This measures the weight of edges that the initial forest
5

---

Approximate Forest Complction for Metric Minimum Spanning Trees
distinct components and j we compute the weights:
The total runtime of MFC-Approx is Ó(n/Qx + (2) where Qx is the complexity for one distance query in X. This is subquadratic as long 12x o(n). When 2x = Ó(1), the memory, runtime, and query complexity are all sub- quadratic as long as = o(n). We emphasize that this is the runtime just for the MFC problem, and does not incorporate the time takes to compute an initial forest. Appendix C provides a more detailed runtime analysis that also consid- ers one strategy for finding initial forests. The appendix also addresses ways to improve the algorithm in practice with little to no change in approximation guarantee.
Wi--j min d d(z;;; 83) s.E
(the closest P: node to 8z) (4)
Wj-z = min d(zz st) -,
(the closest P3 node to s;). (5)
We then define the approximate edge weight between com- ponent nodes Uú and By to be:
ز min ( Wi-+jj (.
This upper bounds the minimum distance wiy between the two components (Figure 3a). Computing this for all pairs of components creates a new weight function v for the coarsened graph Gp (Figure 3b). The algorithm keeps track of the points in that define these edge weights in Gp. It then computes an MST in Gp with respect to wi, then identifies the corresponding edges in Gx, produce a feasible solution for MFC (Figure 3c). We refer to this algorithm as MFC-Approx.
5. Related Work
The most relevant related work is discussed within context throughout the manuscript. Here we discuss connections to other relevant work on MST algorithms.
MST algorithms with predictions. Our work shares simi- larities, though ultimately orthogonal goals and results, with other work on leamiig--ugmmetedd and query-minimizing algorithms for MSTs. Erlebach et al. (2022) assume access to (possibly erroneous) predictions for each edge weight in a graph (not necessarily a metric graph) and the goal is to minimize the number of (non-erroneous) edge-weight queries in order to compute an exact MST. Berg et al. (2023) considered an online setting where adge-weight predictions are all provided a priori but true weights are only revealed in online fashion. After revealing a true weight, irrevoca- ble decision must be made about including excluding the edge from a spanning tree. Bateni et al. (2024) considered MST computations in metric graphs, in settings where one has access both to a weak oracle (providing a similar type of edge-weight prediction) and a strong oracle giving true distances. They focus on bounding the number of strong oracle queries needed to find an exact or approximate MST. These prior works share similarities with our work in their goal to minimize certain types of queries. However, they differ in that the form of edge- predictions, rather than an initial forest. These works also perform ((n)) queries in the worst case, which is prohibitive for large n. Our work is distinctive in its focus on subquadratic algorithms for approximate MSTs.
Approximation guarantees. For our analysis we separate edges of the coarsened graph Gp = (Vp, Ep) into two cate- gories. For an arbitrary constant 3 > I, edge (v,, 0z) E Ep 3-bounded if vhi S fwity, otherwise it is B-umbounded. The following Lemma bounds the weight of 3-unbounded edges in terms of the initial forest.
Lemma 4.1. Let 8 >> 1 be arbitrary. frey > Bwey then kij- < min(wx (T.), (x(), B/(3 1).
Lemma 4.1 aids in proving the following guarantee.
Theorem 4.2. MFC-approx is B B-approximation algo- rithm for MFC for B = (3 + / < 2.62.
The key proof idea is to separately bound the weight of /3- bounded and (-unbbunded edges. If MFC-Approx includes a [B-bounded edge in its MST of Gp, the weight of this edge is bounded in terms of the optimal edge weights w". Our analysis then uses Lemma 4.1 to bound the cost of 3- unbounded edges in terms of the weight of the initial forest.
information takes the
The approximation factor in Theorem 4.2 is obtained by choosing value of B that best balances these two types of costs. While this provides rough intuition, the full proof requires many additional details and some other supporting results, in order to ensure we can properly bound the weight of all f-bounded and (-unbounded edges in the resulting spanning tree at once. Appendix B provides full details. With similar proof technique, we prove MFC-Approx is a performance depends on the quality of the initial forest.
A Algorithms for metric MST. Many previous papers fo- cus on improving algorithmic guarantees for variants of the metric MST problem, especially for the special case of Euclidean distances. For d-dimensional Euclidean space when d = O(1), an exact MST can be computed in 2
algorithm for metric MST whose
Theorem 4.3. Let Gx be implicit metric graph and P be an initial partitioning with 7-overlap 7 = =(PP). MFC-Approx returns a spanning tree of Gx that approx- imates the optimal metric MST to within a factor 3
time (Agarwal et al., 1990), and a (1 + approxxmie solution can be found in time O(n logn n + (e log2 :))) time, where the big-O nota- tion hides constants of the form O(1)d (Arya & Mount, 2016). For high-dimensional spaces, there are also known
(2 + 1 + +1) S 27 +1.
6

---

Approximate Forest Complction for Metric Minimum Spanning Trees
approaches for obtaining c-approximate Euclidean MSTs where subquadratic runtimes depend on the value of the desired approximation factor с > 1 (Har-Peled et al., 2013; 2012). There are also many recent improved theoretical results for parallel and streaming variants of the metric MST problem (Jayaram et al., 2024; Chen et al., 2022; 2023; Wang et al., 2021; Azarmehr et al., 2025; March et al., 2010), most of which again focus on the Euclidean case.
to address the following questions:
Q1. How does this framework perform in terms of runtime and spanning tree cost?
Q2. What 7-overlap (see Eq. 3) can be achieved in practice by scalable partitioning heuristies?
Q3. How does practical performance compare with the the- oretical bound in Theorem 4.3?
Q4. How do differences in the structure of the data and choice of distance metric affect performance?
Partitioning heuristics for MSTs, There are several ex- isting divide-and- techniques for finding an approx- imate Euclidean MST (Chen, 2013; Zhong et al., 2015; Mishra & Mohanty, 2020; Jothi et al., 2018). Similar to our approach, these methods begin by partitioning the data into smaller components, using methods such as k- means (Zhong et al., 2015; Jothi et al., 2018), finding com- ponents of a k-NN graph (Chen, 2013), or using recursive partitioning techniques (Mishra & Mohanty, 2020). An MST for the entire dataset is obtained using various heuris- ties for connecting components internally and then connect- ing disjoint components. This often involves computing an MST on some form of coarsened graph as a substep. De- spite high-level similarities, these methods differ from our forest completion framework in that they focus exclusively on Euclidean space, an assumption that is essential for the partitioning schemes used and the techniques for connect- ing components. The other major difference is that these approaches do not attempt to provide any type of approxi- mation guarantee, which is our main focus.
Implementation details and experimental setup. We im- plemented our algorithms in templated C++ code which allows for easy specialization of different distance metrics. Experiments were run on a research server with two AMD EPYC 7543 32-Core Processors and 1 TB of RAM running Ubuntu 20.04.1. The code was compiled with clang version 20.0.0 with O3 using libc++ version 20.0.0.
To generate an initial forest, we partition data points using a simple k-center algorithm and compute an exact MST for each component using Kruskal's 's algorithm. The runtimes we report include the time it takes to compute an initial forest with this approach. See Appendix C.2 for details on how this initial forest computation affects runtimes. We compare against an exact MST for all of X. computed by generating all (?) edge weights then running Kruskal's algo- rithm. We evaluate our framework in terms of runtime and cost ratio (i.e., the spanning tree cost divided by the weight of an optimal MST). We also compute a bound 2 (P) on "-overlap for our initial forest, obtained by computing the overlap between the initial forest and the one optimal MST we compute for our comparisons. Appendix D pro- vides additional details about our experimental setup, design choices, and evaluation techniques.
Alternate uses of the acronym MFC. Liu et al. (2014) used MFC denote a feature selection technique they called MST-based Feature Clustering. This involves computing an MST, but does not involve any notion of forest completion. Kor et al. (2011) studied distributed algorithms for verifying whether a tree is minimum spanning tree of a graph. Their problem assumes an input graph is partitioned among many processors, and the candidate tree consists of marked edges that are partitioned into so-called MST fragment collection (MFC). These fragments bear a cursory resemblance with the forest used as input to METRIC FOREST COMPLEEIOON problem, but Kor et al. (2011) do not focus metric graphs or completing initial forests. Furthermore, their problem and approach rely on evaluating a full graph in memory, which is intractable in our setting.
Uniform random data. We run large number of experi- ments on uniform random data in d-dimensional Euclidean space to illustrate the strong performance of our MFC frame- work in terms of runtime and spanning tree quality (address- ing Q1 and Q2) in a simple controlled setting. Figure 4 shows results for d E {8. 256) as n increases across a range of choices for component number l. See Appendix D for results wider range of dimensions d.
As increases, we see improvements in asymptotic speedups over the exact baseline algorithm (up to a 300x speedup for d = 8 and 30x speedup for = 256). As increases the quality of the approximate spanning tree also decreases slightly, but the cost approximation ratio still remains very good (i.e., close to 1) in all cases. The 7-overlap bound 7 tend to be small for low dimensions, but gets large d increases (e.g., 7 close to 30 for d 256). For given 5, Theorem 4.3 guarantees roughly a (25 + -)-aprroximation For d = 8 this approximation ranges from 3 to 6, while for d = 256 it ranges from to around 60. Despite this, the cost ratios obtained remain very close to 1, and even improve
6. Experiments
We run large number of numerical experiments syn- thetic and real-world datasets to show the practical utility of our MFC framework. The overall utility of our approach relies both on the performance of MFC-Approx as well as our ability to obtain good initial forests. We therefore evalu- ate both aspects in practice. Our experiments are designed
7

---

Approximate Forest Complction for Metric Minimum Spanning Trees
Unitorm Random Points d=B
Unitorm Random Points d=256
Fashion-MNIST d = 784
2.4-
30-
1.7-
1.05
2.2-
2.0-
25-
1.6
Costratio ratio
1.04
Yuppar
1.8-
20-
1.5
1.6-
15-
1.4
1.03
1.4-
10-
1.3-
1.02-
1.2-
1.2-
1.01
10000
20000
30000
10000
20000
30000
0 10000 20000'
30000
0
10000
20000'
30000
n
1.14-
1.05-
== 16 === 32
66
+t= 128
X t 256
1.12-
1.04
Cool 1ed1o
1.10-
Figure 5: Results for Fashion-MNIST. Each point is the average of 16 samples for fixed n and t.
1.08
1.03-
1.06-
1.02-
1.04-
Gaussian Random Points d d 8 1,100
1.01-
1.02-
2.00-
10000
20000 30000
10000
20000
30000
Vupper hound
1.75-
1.075-
ratio rato
25h
35-
1.50-
1,050-
Pumfime ratio
400-
30
300-
25-
1.25-
1.025-
20-
200-
15-
1.00-
1.000-
10-
32 64
128
256
32 64
128
256
100-
Number of Gaussians (g)
Number of Gaussians (g)
0-
0'
10000'
20000
30000
1000d
20000' 30000'
Figure 6: Results on synthetic data with clustering structure: mixtures of g Gaussians. Cost ratio and y-overlap bound 7 is minimized when g roughly matches the number of components /. in our MFC framework.
n
t- 16 A = 32
+ 128
X = 256
Figure 4: Results on synthetic uniform random data for dimensions d E {8, 256). Each point represents the average of 16 samples of the data for fixed and choice of com- ponent number t for our framework. Runtime ratio is the ratio between the runtime of the optimal MST divided by the runtime of our method. See main text for discussion.
clothing items, Although images do not perfectly cluster into different classes, there is still clear underlying structure (c.g., we expect images of sneakers to look different from images of trousers). Figure shows that for this dataset, our MFC framework achieves slightly better cost ratios and far better "-overlap bounds than for uniform random data (Figure 4), even though the dimension of Fashion-MNIST points (d = 784) is much larger than the dimensions we con- sidered for uniform data. We also observed similar trends in runtime improvements as in Figure 4 (see Appendix D).
slightly as d increases. This tells us first of all that in actual numerical experiments, our approach greatly exceeds our theoretical bounds (addressing Q3). We conjecture that for these high-dimensional point clouds (which lack any underlying structure), there are a large number of spanning trees that are nearly optimal in terms of weight but are structurally very different from optimal spanning tree (which may be unique). This could lead to high y values despite our good cost ratios.
We further examine the effect of clustering structure in a controlled setting by generating mixtures of g Gaussians in 8-dimensional Euclidean space, where parameters are selected to produce good (even if imperfect) clustering struc- ture. For each Gaussian we generate [20000/g] /g] points, so that n R 20000 for each dataset. Figure 6 shows fy values and cost ratios for a range of component numbers as g varies. Significantly, the quality of our spanning trees gets better and better as the number of components gets closer to the number of Gaussians g (i.e., true number of clusters in the data). This is illustrated by sharp valleys in the plots for 7 and cost ratio when R g. Furthermore, even when and g are not close to each other, 7 values and cost ratios are still smaller than the ones obtained on uniform random data with the same dimension d (see Figure 4). This
Improved results on clustered data. Although 7 is large for high-dimensional uniform random data, the lack of struc- ture in this synthetic data is atypical for most applications. For example, metric spanning trees are often computed as the first step in clustering data. Therefore, as part of our answers to Questions Q2 (on y values) and Q4 (on the struc- ture of the data), we explore how our framework performs on datasets with some level of clustering structure. We be- gin by running a similar set of experiments as in Figure 4, but we instead sample points uniformly at random from the Fashion- -NNIS dataset, where points represent images of
8

---

Table displays cost ratios, runtimes, and 7-overlap bound 7 for our MFC framework. For some datasets, we unable to compute the exact minimum spanning tree in reason- able amount of time and space, so we subsample the data Approximate Forest Complction for Metric Minimum Spanning Trees
Table I: Results on real-world datasets.
t
Dataset
OPT
16
32
128
Cooking
?
1.77
2.01
2.42
16 times for a fixed value of n and report mean results (see Appendix D for standard deviations). The fy values tend to be very good in practice (nearly always below 2), rein- forcing the observation that our framework and theoretical guarantees are better when there is structure in the data.
Cost Ratio
1
1.04
1.05
1.07
Run Ratio
1
4.39
6.52
9.97
40k
Run (min)
23.1
5.3
3.5
2.3
Movie
7
1.40
1.51
1.95
Cost Ratio
1.01
1.01
1.02
In some cases, runtimes get worse as / increases too much, but this matches expectations and can be guarded against in practice. For example, for the GreenGenes- Unnaligne (GG- unalign) dataset we consider small subsets of size n = 2500 since data objects are long strings, and computing Leven- shtein distances is expensive. When t 256, the average partition size for the initial forest is roughly 10 points. In this case, the MFC step is extremely expensive. Our frame- work is designed for situations where is asymptotically much smaller than n, hence Table 1 illustrates the decrease in performance we would naturally expect when is too large. Another observation is that we only see runtime im- provements for the Names dataset for larger t. It turns out this is because of extreme outliers in the Names dataset causing our clustering approach to create one large cluster containing most names. This can be guarded against by improving the initial clustering on the data. Appendix D provides additional details, including a breakdown of the time spent on each step of the MFC framework.
Run Ratio
1
4.03
5.01
9.34
33k
Run (min)
484.2
120.3
96.6
51.9
Kosarak
?
1.29
1.74
2.79
Cost Ratio
1.01
1.01
1.03
Run Ratio
1
2.68
5.99
18.17
32k
Run (min)
182.3
68.0
30.4
10.0
Names
7
1.02
1.06
1.22
Cost Ratio
1.01
1.02
1.05
Run Ratio
1
0.92
0.95
1.03
=30k
Run (min)
2.0
2.1
2.1
1.9
GG-
7
1.39
1.46
1.40
unalign.
Cost Ratio
1.09
1.10
1.07
Run Ratio
1
2.56
3.27
2.12
2.5k
Run (min)
239.3
98.0
74.9
113.2
GG-
7
1.22
1.37
1.51
aligned
Cost Ratio
1.07
1.12
1.15
Run Ratio
1
1.60
2.38
5.85
=30k
Run (min)
33.1
22.1
15.1
6.7
7. Conclusions and Discussion
Fashion
7
1.17
1.24
1.41
Cost Ratio
1
1.01
1.02
1.03
We have presented a new framework for finding spanning trees in arbitrary metric spaces, which is highly scalable and grounded in rigorous approximation guarantees. This frame- work is based on completing an initial forest, which can be obtained efficiently using practical heuristics. This paper fo- cuses on serial implementations and theoretical guarantees, as framework already provides many advantages in this setting. At the same time, our work is strongly motivated by massive-scale clustering applications that require high- performance computing capabilities, and the algorithm we developed is highly parallelizable. A natural direction for further research to develop parallel versions of our algo- rithm that can be run on a much larger scale. There are also many remaining questions in the serial setting. One direc- tion is to try to improve on the (v5 + 3 /2/apppoxiimiiionn guarantee while still using subquadratic time, or obtain an approximation with better dependence on the 7-overlap pa- rameter. Another direction is to prove lower bounds for the best possible approximation guarantees for subquadratic algorithms. There are also many opportunities explore more efficient and practical methods for obtaining the initial forest that serves as the input to the MFC problem.
Run Ratio
1
4.67
7.18
12.13
=30k
Run (min)
11.4
2.7
1.8
1.0
indicates that clustering structure helps our framework even when the number of underlying clusters is unknown. See Appendix D for additional plots, including runtimes.
Additional results on real data. We continue to address Q4 by running experiments on 7 real-world datasets and cor- responding metries, which have often been used as bench- marks for similarity search algorithms and clustering al- gorithms. Cooking (Kaggle. 2015; Amburg et al., 2020), Kosarak (Bodon; Aumueller et al., 2024), and MovieLens (Movie) (Harper& & Konstan, 2015; Aumueller et al., 2024) are set data so we use Jaccard distance. Names (Remy, 2021) and ErrennGenes-Unallinne (GG-umalign.) (DeSantis et al., 2006) contain variable-length strings use Leven- shtein edit distance. SerenGGnnes-Algnnee (GG-align) (De- Santis et al., 2006) consists of fixed-length strings (all with 7682 characters) so we use Hamming distance. For Fashion- MINST (Xiao et al., 2017) we use Euclidean distance. See Appendix D for additional details on datasets.
9

---

Approximate Forest Completion for Metric Minimum Spanning Trees
Acknowledgements
Notices of the Royal Astronomical Society, 216(1): 1985.
This work was performed under the auspices of the U.S. Department of Energy by Lawrence Livermore National Laboratory under Contract DE-AC52-07NA27344 (LLNL- CONF-2002129), and was supported by LLNL LDRD project 24-ERD-024.
Bateni, M., Dharangutte, P., Jayaram, R., and Wang. C. Metric clustering and MST with strong and weak distance oracles. In Proceedings of the Conference on Learning Theory, pp. 498-550. PMLR, 2024.
Berg, M., Boyar, J.. Favrholdt, L. M., and Larsen, K. S.
Impact Statement
Online minimum spanning trees with weight predictions. Proceedings of the International Algorithms and Data Structures Symposium, pp. 136-148. Springer-Vere 2023.
This paper presents work whose goal advance the field of Machine Learning. There are many potential societal consequences of our work, none of which feel must be specifically highlighted here.
Bodon, F. Kosarak Dataset (Frequent Itemset Mining www.:iiununtwweebbbniio.... be/data/.
Dataset Repository).
References
Borúvka, O. O jistém problému minimálním. 1926.
Agarwal, P. K., Edelsbrunner, H., Schwarzkopf, O., and Welzl, E. Euclidean minimum spanning trees and bichro- matic closest pairs. In Proceedings of the Symposium on Computational Geometry, pp. 203-210, 1990.
Callahan, P. B. and Kosaraju, S. R. Faster algorithms for some geometric graph problems in higher dimensions. In Proceedings of the Symposium on Discrete Algorithmss, volume 93, pp. 291-3000 1993.
Almansoori, M. K., Meszaros, A., and Telek, M. Fast and Semory-efficienn approximate minimum spanning tree generation for large datasets. Arabian Journal for Science and Engineering, pp. 1-14, 2024.
Chatterjee, S., Connor, M., and Kumar, P. Geometric mini- mum spanning trees with GeoFilerKruskal. In Proceed- ings of the International Symposium on Experimental Algorithms, pp. 486-500. Springer. 2010.
Amburg, I., Veldt, N., and Benson, A. Clustering in graphs and hypergraphs with categorical edge labels. In Proceed- ings of The Web Conference, pp. 706-717. Association for Computing Machinery, 2020.
Chazelle, B. A minimum spanning tree algorithm with inverse-ackerman type complexity. Journal of the ACM (JACM), 1728)))122--144 2000.
An, I.,, Xiang, Q.-S., and Chavez, A fast implemen- tation of the minimum spanning tree method for phase unwrapping. IEEE transactions medical imaging, 19 (8):805-808 2000.
Chen, X.
Clustering based on a near neighbor graph and grid cell graph. Journal of Intelligent Information Sys- tems, 00:529-554,, 2013.
Chen, X., Jayaram, R., Levi, A., and Waingarten, E. New streaming algorithms for high dimensional EMD and MST. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory Computing, pp. 222-233, 2022.
Arya, S. and Mount, D. M. A fast and simple algorithm for computing upproximate Euclidean minimum span- ning trees. In Proceedings of the Symposium on Discrete Algorithms,, pp. 1220-1233 SIAM, 2016.
Chen, X., Cohen-Addad V., Jayaram, R., Levi, A., and Waingarten, E. Streaming Euclidean MST to constant factor. Proceedings of the Symposium on Theory of Computing, pp. 156-169. Association for Computing Machinery, 2023.
Aumueller, M., Bernhardsson, E., and Faitfull, A. Ann benchmarks. https:/ /gghhbb...b/../////////...... www/co/e////ieeeeee heimm/rikkerr//// ann-benchmarks, 2024.
Azarmehr, A., Behnezhad, S., Jayaram, R., Lącki, J., Mir- rokni, V., and Zhong, P. Massively parallel minimum spanning tree general metric spaces. In Proceedings of the Symposium on Discrete Algorithms, pp. 143-174. SIAM, 2025.
Davies, S., Moseley, B., Vassilvitskii, S., and Wang, Y. Predictive flows for faster Ford-Fulkerson. In Interna- tional Conference on Machine Learning, pp. 7231-7248. PMLR, 2023.
Bai, X. and Coester, C. Sorting with predictions. Advances in Neural Information Processing Systems, 36:26563- 26584, 2023.
DeSantis, T. Z.,, Hugenholtz, P., Larsen, N., Rojas, M., Brodie, E. L.. Keller, K., Huber, T., Dalevi, D., Hu. P., and Andersen, G. L. Greengenes, a chimera-checked 16S iRNA gene database and workbench compatible with ARB. Appl Environ Microbiol, 72(7):5069-500 Jul
Barrow, J. D., Bhavsar, P., and Sonoda, D. Minimal spanning trees, filaments and galaxy clustering. Monthly
10

---

Approximate Forest Complction for Metric Minimum Spanning Trees
2006. ISSN 0099-2240 (Print); 1098-5336 (Electronic); 0099-2240 (Linking). doi: 10.1 128///2.. 03006005.
Computing, Network, Storage, and Analysis, pp. 730-738.
2023.
Dong, W., Moses, C., and Li, K. Efficient k-nearest neighhor graph construction for generic similarity measures. In Proceedings of the International Conference on World Wide Web, pp. 577-586, 2011.
Jayaram, R., Mirrokni, V., Narayanan, S., and Zhong, P. Massively parallel algorithms for high-dimensional Euclidean minimum spanning tree. In Proceedings of the Symposium on Discrete Algorithms, pp. 3960-3996. SIAM, 2024.
Ergun, J., Feng, Z., Silwal, S., Woodruff, D. P., and Zhou, S. Learning-aughnn aaggmenedd h-means clustering. Machine learning, 2022.
Jothi, R., Mohanty, S. K., and Ojha, A. Fast approximate minimum spanning tree based clustering algorithm. Neu- rocomputing, 272:542-557, 2018.
Erlebach, T., de Lima, M. S., Megow, N., and Schlöter, J. dearning-augmenter query policies for minimum span- ning tree with uncertainty. In Proceedings of the Euro- pean Symposium on Algorithms, 2022.
Kaggle. What's cooking? https: htops:///www.. https://www.kagglee. kaggle. com/ h/whhtts-coole 2015.
Kor; L.,, Korman, A., and Peleg. D. Tight bounds for dis- tributed MST verification. In Proceedings of the Interna- tional Symposium Theoretical Aspects of Computer Science. Schloss-Dagsuhl-Leibne Zentrum für Infor- matik, 2011.
Gonzalez, T. F. Clustering to minimize the maximum in- tercluster distance. Theoretical computer science, 38: 293-306, 1985.
Gower, J. C. and Ross, G. J. Minimum spanning trees and single linkage cluster analysis. Journal of the Royal Statistical Society: Series C (Applied Statistics), 18(1): 54 64, 1969.
Kraska, T., Beutel, A., Chi, E. H., Dean, J., and Polyzotis, N. The case for learned index structures. In Proceedings of the International Conference Management of Data, pp. 489-404444 309-504, 2018.
Har-Peled, S., Indyk, P., and Motwani, R. Approximate nearest neighbor: Towards removing the curse dimen- sionality. Theory of Computing, 8(14):321-355 2012.
Kruskal, J. B. On the shortest spanning subtree of graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7(1):48-50, 1956.
Har-Peled, S., Indyk, P., and Sidiropoulos, A. Euclidean spanners in high dimensions. In Proceedings of the Sym- posium on Discrete Algorithms, pp. 804-809. SIAM, 2013.
La Grassa, R., Gallo, I., and Landro, N. Ocmst: One-class novelty detection using convolutional neural network and minimum spanning trees. Pattern Recognition Letters, 155:114-122 2022.
Harper, F. M. and Konstan, J. A. The movielens datasets:
History and context. ACM Trans. Interact. Intell. Syst. 5
Labbé, M., Landete, M., and Leal, M. Dendrograms, min- imum spanning trees and feature selection. European Journal of Operational Research, 308(2):555-567, 2023.
(4), 2015. ISSN 2160-6455, doi: 10.1145/2827872. URL
https: / /ooiooi../////// .rgg C /
Held, M. and Karp, R. M. The traveling-salesman problem and minimum spanning trees. Operations research, 18 11s1138-116,, 1970.
Lin, H., Luo, T., and Woodruff, D. Learning augmented binary search trees. In International Conference on Ma- chine Learning, pp. 13431-13440, PMLR, 2022.
Hoffmaan,, M., Erlebach, T., Krizanc, D., Mihalák, M., and Raman, Computing minimum spanning trees with uncertainty. In Proceedings of the Symposium on Theoretical Aspects of Computer Science, pp. 277-288, 2008.
Liu, Q., Zhang, J., Xiao, J., Zhu, H., and Zhao, Q. A su- pervised feature selection algorithm through minimum spanning tree clustering. In Proceedings of the Interna- tional Conference on Tools with Artificial Intelligence, pp. 264-271. IEEE, 2014.
Indyk, P. Sublinear time algorithms for metric space prob- lems. In Proceedings of the Symposium on Theory of Computing, pp. 428-434, 1999.
Loberman, H. and Weinberger, A. Formal procedures for connecting terminals with a minimum total wire length. Journal of the ACM (JACM), 4(4):428-437, 1957.
Iwabuchi, K., Steil, T., Priest, B., Pearce, R., and Sanders, G. Towards a massive-scale distributed neighborhood graph construction. In Proceedings of the SC'23 Workshops of The International Conference on High Performance
Malkomes, G., Kusner, M. J., Chen, w., Weinberger, K. Q. and Moseley, B. Fast distributed k-center clustering with outliers on massive data. Advances in Neural Information Processing Systems, 28, 2015.

---

Approximate Forest Complction for Metric Minimum Spanning Trees
March, W. B., Ram, P., and Gray, A. G. Fast Euclidean mini- mum spanning tree: algorithm, analysis, and applications. In Proceedings of the SIGKDD international conference on Knowledge Discovery and Data mining, pp. 603-612, 2010.
Xiao, H., Rasul, K., and Vollgraf, R. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms, 2017.
Xu, Y. and Uberbacher, C. 2D image segmentation using minimum spanning trees. Image and Vision Computing, 15(1):77-57, 1997.
McClintock, and Wirth, A. Efficient parallel algorithmss for k-center clustering. Proceedings of the Interna- tional Conference on Parallel Processing, pp. 133-138.
Xu, Y. Olman, V., and Xu, D. Clustering gene expression data using a graph graph-theoretic approach: an application of minimum spanning trees. Bioinformatics, 18(4):53--545 2002.
IEEE, 2016.
Megow, N., Meißner, J., and Skutella, M. Randomization helps computing minimum spanning tree under uncer- tainty. SIAM Journal on Computing, 16(4):1217-1240, 2017.
Zhong, C., Malinen, M., Miao, D., and Fränti, P. fast minimum spanning tree algorithm based on k-means. In- formation Sciences, 295:1-17 2015.
Mishra, G. and Mohanty, S. Efficient construction of an approximate similarity graph for minimum spanning tree based clustering. Applied Soft Computing, 97:106676, 2020.
Mitzenmacher, M. and Vassilvitskii, S. Algorithms with predictions. Communications of the ACM, 65(7):33-35, 2022.
Narasimhan, G. and Zachariasen, M. Geometric minimum spanning trees via well-separated pair decompositions. Journal of Experimental Algorithmics, 6, 2001.
Nguyen, T., Chaturvedi, A., and Nguyen, H. L. Im- algorithms for k-means and k-medians clustering. In International Conference Learning Representations, 2023.
proved
Prim, R. C. Shortest connection networks and some gen- cralizations. The Bell System Technical Journal, 36(6): 1389-1401, 1957.
Remy, P Name dataset. httpp:: com/ philipperree http://ammmmdast....maaaaaa 2021.
Shamos, M. I. and Hoey, D. Closest-point problems. In Pro- ceedings of the Symposium Foundations of Computer Science, pp. 1-2- IEEE, 1975.
Shin, Y., Lee, C., Lee, G., and An, H.-C. Improved learning- augmented algorithms for the multi-option ski rental problem via best-possible competitive analysis. In In- ternational Conference on Machine Learning, pp. 31539- 31561. PMLR, 2023.
Vaidya, M. Minimum spanning trees in k-dimensional space. SIAM Journal Computing, 17(3):572-582, 1988.
Wang, Y., Yu, S., Gu, Y., and Shun, J. Fast parallel algo- rithms for Euclidean minimum spanning tree and hier- archical spatial clustering. In Proceedings of the Inter- national Conference on Management of Data, pp. 1982- 1995, 2021.
12

---

Approximate Forest Complction for Metric Minimum Spanning Trees
A. Strategies for Finding an Initial Forest
In order for our approach to be meaningful for large-scale metric MST problems, we must be able to obtain a reasonably good initial forest without this dominating our overall algorithmic pipeline. Here we discuss two specific strategies for initial forest computations, both of which are fast, easy to parallelize, and motivated by techniques that are already being used in practice in large-scale clustering pipelines. In particular, there already a number of existing heuristics for finding MSTs and hierarchical clusters that rely in some way on partitioning an initial dataset and then connecting or merging components (Zhong et al., 2015; Jothi et al., 2018; Mishra & Mohanty, 2020; Chen, 2013). These typically focus only on point cloud data, do not apply to arbitrary metric spaces, and do not come with any type of approximation guarantee. Nevertheless, they provide examples of fast heuristics for large-scale metric spanning tree problems, and serve as motivation for our more general strategies below.
Strategy 1: Components of a N-NN graph. A natural way to obtain an initial forest for Gx is to compute approximate k-nearest neighbor graph for a reasonably small k, which can be accomplished with the k--N descent algorithm (Dong et al., 2011) or a recent distributed generalization of this method (Iwabuchi et al., 2023). This efficiently connects a large number of points using seall-weight edges. The k-NN graph will often be disconnected, and we can use the set of connected components as our initial components P {Pi, Pg.... ........P. Pt). The exact number of components will depend on the distribution of the data and the number of nearest neighbors computed. For larger values of k. the k-NN graph is more expensive to compute, but then there are fewer components to connect, so there are trade-off's to consider. The components of the k-NN graph will typically not be trees but will be sparse (the average degree is (k))). so we can use classical MST algorithms to find spanning trees for all components in Ei= Ö(k (PP.)) (kk) time. The exact runtime of the k--N descent algorithm depends on various parameters settings, but prior work reports an empirical runtime of O(1!-14) (Dong et al., 2011), 1), with strong empirical performance across a range of different metrics and dataset sizes. We remark that k-NN computations have already been used elsewhere as subroutines for large-scale Euclidean MST computations (Almansoori al., 2024; Chen, 2013).
Strategy 2: Fast clustering heuristics. Another approach is to form components P= ( PP....... P..} by applying a fast clustering heuristic to X such as a distributed k-center algorithm (Malkomes et al., 2015; McClintock & Wirth, 2016). Even the simple sequential greedy 2-approximation algorithm for k-center can produce an approximate clustering using O(nk) queries (Gonzalez, 1985). Approximate exact minimum spanning trees for each P; can be found in parallel. The remaining step is to find good way to connect the forest. Similar approaches that partition the initial dataset using k-means clustering also exist (Zhong et al., 2015; Jothi et al., 2018), though this inherently forms clusters based on Euclidean distances. For all of these clustering- -aaeed approaches, the number of components t for the initial forest is easy to control since it exactly corresponds to the number of clusters k. Smaller leads to larger clusters, and hence finding an MST of each Pj is harder. However, there are then fewer components to connect, so there is again a trade-off to consider. We remark that may seem counterintuitive to use clustering method as a subroutine for finding an MST, since one of the main reasons to compute an MST is perform clustering. We stress that Strategy uses cheap and fast clustering method that identifies sets of points that are somewhat close in the metric space, without focusing on whether they good clusters for downstream application. These cheaper clusters are then just part of broader and more sophisticated hierarchical clustering pipeline.
B. Proofs
We now provided full details for proving the main approximation results in Section 4 for MFC-Approx. Pseudocode is shown in Algorithm 1.
Lemma 4.1. Let P. and P3 be arbitrary pair of components and let B > 1. If Wuy Butz, then
wij < 3 3-1
min
Proof. For each i E (1,2....,
.2....,t], t). we denote the maximum distance between a point in P. and its component representative
8t by 0; = maxzer; d(z, 8:). Let at E P, and x" E P, be points satisfying (()7,;)) = d(P., P,) = wiy. We use the
13

---

Approximate Forest Completion for Metric Minimum Spanning Trees
Algorithm 1 MFC-Approx
Input: X' {#1 #2. Fn ). components P {Pi, ..,..., , Pt), component spanning trees (Ti, :.. TT}
Output: Spanning tree for implicit metric graph of X'
for i 1, 2, .... do
Select arbitrary component represettttve 8; E P.
5: end for for
= 1, 1,,,,... . do for j = + ......t : do
,i = EP. d(z,, 83) w min d(zz,, 8i) Kijj min WW Wz-si)
// closest a P. node comes to sj
// closest P3 node comes to 8 // set weight for edge (v))
end for end for
Tp = OPTIMALMST hije(t)
// find optimal MST on complete t-node graph Return spanning tree i of Gx by combining U T, with edges from Pp.
(reverse) triangle inequality and the definition of a, to see that:
d( m3) = min my)) 2 EyEP,
min d(s), d(s.,2))2 2 min d(st, - a; Wy-si aa Wij ai. 2yEP,
zjEP,
Similarly can show that
25) min 25) 2
min d(s;, d(s). x)) 2 min d(sj, -a, aj Wi-+j - -a 2 1ū.j aj. zEP
z,E
s.P.;
In other words, we have the bound wiy ووj min aj}. Combining this with the assumption that dug > Buiy gives
B
Byy > Buly 2 Būh min(as,
3-1 minfa a,} > uig.
The proof follows from the observation that 04 I wx(().. To see why, note that there exists some E P, such that d(z, s,) a; Since T; is spanning tree of P,, it must contain path from to with sum of edge weights at least aq O
In addition to Lemma 4. I, our main approximation guarantees rely on two other simple supporting observations. We include full proof here for completeness. The first amounts to the observation that tree has arboricity and degeneracy 1. The second supporting observation deals with MSTs a graph that includes edges weight zero.
Observation 1. If T = (V, FT)) is an undirected tree, there is way to orient edges in such way that every node has at most one outgoing edge.
Proof. The proof is constructive. Define an iterative algorithm that removes minimum degree node at each step and deletes all its incident edges. Orient the deleted edges so that they start at the node that was removed. Note that a tree always contains node degree I, and removing such a node leads to another tree with one fewer node. Thus, this procedure will orient edges of the original graph in such a way that each node has at most one outgoing edge.
+ and (2) ; E + R be two nonnegative weight functions for an undirected graph G = (V, E). Assume there is an edge set C E such that
Observation 2.
Let (1) + RR
e (i.j) = w (2) (i.j) = 0 for every (i,j)= E Z.
Then there exist spanning trees Mj and M2 for such that Mj is an MST for G with respect to w(() for E (1,2), and Mj 2 M2 Z.
Proof. The proof is constructive. Recall that Kruskal's 's algorithm finds an MST by ordering edges by weight (starting with the smallest and breaking ties arbitrarily the ordering) and then greedily adds each edge a growing spanning tree if and
14

---

Approximate Forest Complction for Metric Minimum Spanning Trees
only if it connects two previously disconnected components. Fix an arbitrary ordering oz of edges in Z. When applying Kruskal's algorithm to find minimum spanning trees of G with respect w(1) and w(2), we can choose orderings for these functions that exactly coincide for the first [Z] edges visited. Namely, we place edges in Z first, using the order given by oz The first |Z| steps of Kruskal's 's algorithm will be identical when building MSTs with respect to w()) and w(?) Thus, if M1 and M2 are the spanning trees obtained for (1) and (2(2) respectively using this approach, we know these trees will include the same set edges from Z and discard the same set edges from Z, i.c., M1 n = M2 0 Z.
To aid in proving our main approximation results, we first cover some useful notation. Let Tpp represent an MST of Gp with respect the optimal weight function w²: Ep + I and Tp represent an MST of Gp with respect to the approximate weight function : Ep + R+ The edges of Tp map to set of edges M in Gx that optimally solves the METRIC FOREST COMPLETION problem, and the edges in Tp map to an edge set M. The weight of these edges given by (x w² (T²) and (x(M) ((Tx)), respectively. Let ' be the spanning tree of Gx defined by combining U T3 with M and T be the spanning tree (returned by MFC-Approx) that combines U Ti with M. These have weights given by
wx(T*) = (T3) +
wx
(8)
1=1
=x( = w(Tp) +
wxx (T.).
(9)
We now restate and then prove Theorems 4.2 and 4.3 using the new notation above.
Theorem 4.2 The spanning tree / returned by Algorithm 1 satisfies
(T') S xx (T) S Buxx
for 3 (3+ /5)/2 < 2.62, where 7 a solution to the MFC problem. other words, T is a spanning tree of Gx with minimum weight among spanning trees that complete the initial forest U Ti.
Proof. For our analysis we consider two hypothetical weight functions w and th for Gp (Vp, Ex), defined by zeroing out the 3-unbounded edges in w" and w:
wiy
if (vi, vy) is 3-bounded, i.e., thes S Buis
w (1i, uz))
otherwise
Waj 0
if (vs, vy) is 3-bounded, i.e., thi I Bulj otherwise.
vo Uz))
By Observation 2, there exist spanning trees T and To for Gpp that are optimal with respect to w and dhg respectively, which contain the same exact set of f--unbuudddd edges. Let U represent this set of 3-unbounded edges in To and T Let be the set 3-bounded edges in TV and / be the set of 3-bounded edges in To. Because Tp is an MST with respect to we know that:
w ((p) S (To) = (U) + @(B).
(10)
We will use this to upper bound the weight of 7p in terms of T First we claim that
x(B) < Bw" (Tz).
(11)
15

---

Approximate Forest Completion for Metric Minimum Spanning Trees
This follows from the following sequence of inequalities:
iBB) wh (B)
since it and wo coincide on 3-bounded edges since wo is zero on G-unbounded edges since To UU since To is optimal for do since wh is zero on 3-unbounded edges since uh I BBoj on 3-bounded edges since Tú B3 U U and wū( since TV is optimal for wi since w I w" for all edges.
rb (B) + (U)
vho (To)
S (Tō)
wo(BB)
S Bwi (B))
Bwg (TP)
Bw" (Tp)
Next we bound vU). From Lemma 4.1, we know that dis S m) (T;() ux(T;)} for every (v;, ey) E U. Because Tp is tree Gp, we know by Observation that Vp = fer, .2...... 3 has at most one outgoing edge. We can therefore assign each (2; Uy) E U to one of its nodes in such a way that each node in Vp is assigned at most one edge from U. Assume without loss of generality that we write edges in such a way that edge (v,, vy) E U is assigned to node U/s. Thus,
orient its edges in such way that each node in
(U)
Σ
Wij
Σ
3 ux (Ti)
B
wx (Ti).
(12)
3-1
2=1
Combining these gives our final bound
= (x
wx (Ti)
by Eq. (9)
S cb(B) + (U)) + Σ
wx (Ti)
by Eq. (10)
i=1
(33
(
S 3Bw" (T²) +
+1
Σ w
by Eqs. (11) and (12)
B -
1=1
< maxx {
B
+1]
w (TT(T)) Σ wx(Ti)
3- 3-1
(T"
by Eq. (8) and our choice of 3
For the last step that we have specifically chosen 3 = (3 + v5)/2 to ensure that B =1 8/(B - 1), as this leads to the best approximation guarantee using the above inequalities.
Theorem 4.3 Let Gx be an implicit metric graph and be an initial partitioning with 7-overlap = (P)). Algorithm returns a spanning tree of f of Gx that satisfies
wx(Tx) S wx (T) I Buxx (Tx)
(13)
where Tx is an MST of Gx and | 1 (2 +1+ 44 S 2n 1.
Proof. We use the same terminology and notation as in the proof of Theorem 4.2. The only difference is that we do not necessarily use (3 + /2) For an arbitrary 3 2 1, we still prove in the same way that
wx( < Bw" (wT(TT)
3 3-1 +1
B
Σ
wx (T,).
(14)
16

---

Approximate Forest Complction for Metric Minimum Spanning Trees
The 7-overlap of the initial forest implies there exists an MST Tx of Gx satisfying:
( y (Ix),
(15)
where Lx is the set of edges of Tx inside components P of the initial forest. Let Bx be the set of edges in Tx that cross between components, so that wx(xx) = wx (Bx) + (xxx)). Since Tx is a spanning tree, Bx must contain a path between every pair of components, meaning that Bx corresponds to a spanning subgraph of the coarsened graph Gp. Since Tp defines an MST of Gp with respect to w", which captures the minimum distances between pairs of components, we know
w" (I3) I wx wx(Bx).
(16)
Putting the pieces together we see that
3 3-1 111 (wx((x) S max {3.7 1 B -
} wx (xx(xx)
Ex (T) S (Bx(Bx) + (1
(17)
This will hold for any choice of 3 2 1. In order to prove the smallest approximation guarantce, we choose 3 satisfying:
B= 7 (1 8 8-1
B
The solution for this equation under constraint B 2 1 and y 2 1 is
B = 2 27 + v 44 27 +1
C. Additional Details for MFC Framework
This section of the appendix provides additional details about our algorithm MFC-Approx and our broader framework for metric MST computation. This includes a more detailed runtime analysis and several practical considerations about computing initial forests.
C.1. Runtime analysis for MFC-Approx
MFC-Approx finds the distance between each point in X' and each of the I component representatives, for a total of ((n))
distance queries. It then finds an MST of a dense graph with (9) edges, which has runtime and space requirements of (
Thus, the algorithm has subquadratic memory and query complexity long as l o(n). The runtime is Ó(n12x + (2)
where Qx is the complexity for one distance query in X, which also is subquadratic as long 1Qx o(n). In settings
where Qx Ō(1) the memory, runtime, and query complexity are all subquadratic as long as t = o(n).
C.2. Practical considerations for our MFC framework
The practical utility of the MFC framework will also depend on the time it takes to find an initial forest. The precise runtime for computing such a forest depends on various design choices and trade-offs when using any strategy. To provide some intuition for the overall cost of applying the MFC framework, we provide a rough complexity analysis for the k-center strategy (see Appendix A) assuming an idealized case of balanced clusters. The simple 2-approximation for k-center chooses an arbitrary first cluster center, and chooses the ith cluster center be the point with maximum distance from the first i 1 centers (Gonzalez, 1985). This requires (nd) distance queries. For this strategy, we can use the cluster centers as the component representatives for MFC-Approx, which allows us to compute á without any additional queries. If clusters are balanced in size, we can compute minimum spanning trees for all clusters using Onn² /t) queries and a runtime of Ó(2xn² /t), simply by querying all inner-cluster edges and running a standard MST algorithm. In this balanced-clustee case, combining the initial forest complexity with the complexity of our MFC algorithm, the entire pipeline for finding a spanning tree takes (n2x(n//t + nt) + 2)). This is minimized by choosing t = vn clusters, leading to a complexity that grows as 1.5, For unbalanced clusters, one must consider different trade-offs for claster-balancing strategies, which could
17

---

Approximate Forest Complction for Metric Minimum Spanning Trees
be beneficial for runtime but may affect initial cluster quality. We could also improve the runtime the expense of initial forest quality by not computing an exact MST for each cluster. For example, we could recursively apply entire MFC framework to find a spanning tree of each cluster. We cover other practical considerations and runtimes for certain ways of computing initial forests in Appendix A.
There are several other ways to relax our overall MFC framework and algorithm to make our approach faster while still satisfying strong approximation guarantees. For metrics with high query complexity, we can use approximate queries with only minor degradation in approximation guarantees. For example, for high-dimensional Euclidean distance we can apply Linnsson-inddenttaauss transformations to reduce the query complexity while approximately maintaining distances, As another relaxation, can replace the exact nearest neighbor search steps in MFC-Approx (to find the minimum distance between a representative 8; in an entire cluster P;) with an approximate nearest neighbor search. If for some >> 0 we find a (1 + apprrxxmme nearest neighbor in each component for every component representative 8;, this will make our approximation guarantees worse by at most a factor (1 + E). There are also numerous opportunities for parallelization, such as parallelizing distance queries and MST computation for components.
There are also several ways in which we could potentially improve the spanning tree quality of our algorithm in practice with little effect on runtime. As one specific example, when approximating the distance between components P. and P3 of the initial forest, we could compute ã; argmin d(z, 8z) and ãy argminzer, d(x, st) and then use the following weight for the coarsened graph:
Wi min [d(E,, 8y), d(īj, 8,), d()
This differs from Algorithm 1 only in that it additionally checks the distance d(ēj, 2.) to see if this provides even closer pair of points between P. and P3. Although this does not always improve results, it can never be worse in terms of approximations. Figure 3a provides an example where úij is noticeably better than dūzj. An interesting future direction is to implement this and also explore other heuristics that could improve the practical performance of our method without affecting our theoretical guarantees.
D. Additional Details on Empirical Results
In this section we provide more in-depth explanations behind our experimental setup, implementations, evaluation, and empirical results.
Generating initial forests. To generate initial forests, we first partition data points using the standard greedy 2- approximation algorithm for k-center clustering (Gonzalez, 1985), as this is simple, fast, and works for arbitrary metrics. We consider results for a range of different component numbers = k. After partitioning the data, we compute an exact minimum spanning tree for each component, mirroring an approach used by previous divide-and and-conquer algorithms for large-scale Euclidean MST approximations (Jothi et al., 2018; Zhong et al., 2015; Mishra & Mohanty, 2020). Computing exact MSTs for all components is often the most expensive step of our MFC framework as requires generating all edges inside each component. Even so, find this leads significant runtime improvements over applying the exact algorithm the entire dataset, while achieving extremely good approximation ratios.
Baseline and evaluation criteria. We compare against an exact MST computed by generating all (*) edge weights then running Kruskal's algorithm. The bottleneck in Kruskal's algorithm is sorting the O(n²) edge weights, leading to an (n² l) runtime. Although more sophisticated algorithms could achieve runtime of O for arbitrary metrics, Kruskal's 's algorithm is still fast (optimal up to log factor in terms of runtime) and has the added benefit of being simple to implement and work with in practice. We note furthermore that any speed-up in our baseline algorithm for the full MST would also instantly improve the runtime of our MFC framework, since we use the same solver to find MSTs for the partitions in the initial forest.
We evaluate our MFC framework (both the initial forest generation and the completion step) in terms of runtime, a bound on y-overlap, and cost ratio (i.e., the spanning tree cost divided by the weight of the optimal MST). To find our upper bound for y, which we denote as 7, we compute the overlap between the initial forest and the MST found by the baseline. This amounts to computing the ratio in Eq. (3), except without optimizing over all possible minimum spanning trees in the denominator. When all edge weights are unique, this produces the exact value of y. We therefore expect this to be an especially good approximation of y for our Euclidean point cloud datasets, since distances between random points tend to be unique (or nearly all unique).
18

---

Approximate Forest Complction for Metric Minimum Spanning Trees
Real-world datasets. We run experiments on several real-world datasets that have been used as benchmarks for similarity search algorithms (e-g., k-NN search benchmarks) and clustering algorithms. These serve well as benchmarks for metric MST computations since they involve variety of different types of data (e.g., numerical data, sets, strings) and distance functions (e.g., Euclidean, Jaccard, Hamming, Levenshtein edit distance). In some cases we used the entire dataset in our numerical experiments, whereas in other cases we subsample a larger dataset. We run experiments on implicit graphs with up to n = 39,774 nodes, which means we are considering graphs with over 700 million edges. Our MFC framework in fact scales up to even larger graphs, but we restrict to graphs with under I billion edges since in this regime we are still able to compute an optimal MST to use as a point of comparison. We summarize the dataset type and distance metric in Table 2. and provide more details for each dataset below.
Cooking, Each data object is a set of food ingredients defining a recipe. There are 6714 ingredients and 39,774 recipes. We use Jaccard distance as this is set data. The original raw data comes from the What's 's Cooking? Kaggle dataset (Kaggle, 2015), which was parsed into the current set of sets by Amburg et al. (2020).
MovieLens-10M.
This is a set of sets derived from movie ratings (Harper & Konstan, 2015). We consider subset of the parsed dataset provided on the ANN Benchmarks Repository (Aumueller et al., 2024), restricting to sets with 64 items or more, in order to work with a dataset where n is slightly larger than 30,000. We apply Jaccard distance.
Kosarak.
This dataset is derived from click-stream data from a Hungarian news portal (Bodon) and is standard bench- mark for nearest neighbor algorithms (Aumueller et al., 2024). The original data (available from the Frequent Itemset Mining Dataset Repository at httpp:/ //ffftt /fimii... wantwe rpen be / /atta / kosarak datt comprises 990,002 sets defined over a collection of 41,270 items. We restricted to sets of size at least 40, leading to a set of 32,295 sets. We apply Jaccard distance.
Fashion-MNIST. Each point in the Fashion-MNIST dataset represents a 28 x 28 grayscale image of an item of clothing (e.g., sneakers, trousers), encoded as a vector of size = 784. The total number of class labels is 10. We use Euclidean distance for this dataset, following the ANN Benchmarks Repository (Aumueller et al., 2024).
US. Each data object is last name for someone in the United States, obtained from the Names dataset available online at https: / /gg/ttttta github.. com/ph 1illipppp iipe r remy/ / aataet.. We consider this dataset as it provides a natural benchmark for computing spanning trees on short sequence data using Levenshtein edit distance. Each UTF-8 code point was treated as a separate character for the purpose of the edit distance. Last names the dataset vary in length from 0 to 252 characters where indicates no last name. The average length of the last names is 6.67 with a standard deviation of 2.470. Computing an exact minimum spanning tree for the entire (very large) dataset is infeasible. our experimental results consider samples of names of size n 30,000.
CeennGGenn--nnllinnee and GreenGenes-Aligneee GreenGenes is a chimera-checked 16S megagenomic sequence dataset (DeSantis et al., 2006), which is frequently used as benchmark for sequence clustering. We use version 13.5 of the data, accessed by following instructions on the USEARCH benchmarks website (https: / //www dr ve5. com/ http//searcc//a hwttt//bwnhnmaa...eeeeeemm Berrrkkgglllsss html).. The data is provided in two formats: unaligned variable length sequences (ranging from 1111 to 2368 characters; mean length is 1401.06 with a standard deviation of 57.083), and as aligned sequences of a fixed length of 7682. Following a standard and natural approach, we used Levenshtein edit distance for the unaligned sequences and Hamming distance for the aligned sequences. Since the dataset is far too large to compute a full spanning tree, we subsample groups of sequences at a time. Computing Levenshtein distances on unaligned sequences is very expensive, so we restrict to n 2500 for this case.
D.I. Additional details for uniform random data
For our uniform random data experiments we consider random point clouds of size n in d-dimensional Euclidean space where the value for point in each dimension is drawn uniformly from [-1, The first two columns of Figure 4 show results for d E {8, 256} as n increases from 1000 to 30000, using a different color for each choice of component number &. E (16, 32, 64, 128, 256} for which we ran our MFC framework. Here in Figure 7 we show results for for d E {4, 16, 64, 128), which show the same basic trends.
As increases, we see larger and larger speedups over the exact baseline algorithm, with up to a 300x speedup for d = 8 and up to a 30x speedup for d 256. Our results match the asymptotic behavior we would expect from simple runtime
19

---

Approximate Forest Completion for Metric Minimum Spanning Trees
Table 2: List of different datasets used for real world experiments.
Dataset
Type of Data
Distance Metric
Cooking (Amburg et al., 2020)
Sets
Jaccard distance
Kosarak (Bodon)
Sets
Jaccard distance
MovieL 10M (Harper & Konstan, 2015)
Sets
Jaccard distance
Fashion-MNIST (Xiao et al., 2017)
784 dimensional points
Euclidean distance
Names- US (Remy. 10
Short variable-length strings
Levenshtein edit distance
GreenGienes-Unnliineed (DeSantis et al., 2006)
Long variable-length strings
Levenshtein edit distance
GreenGenes-Aligned (DeSantis et al., 2006)
7682 character strings
Hamming distance
Uniform Random Points d=4
1.7
1.14
800
Yupper bound
1.6-
1.12
Runtime rabio
1.5
Cost. ratio
1.10-
600
1.4
1.08-
400
1.06
200
1.04
1.02
0
10000
20000
30000
10000
20000
30000
0
10000
20000'
30000
Uniform Random Points d=16
1.14
350
Vupper bound
4.0
1.12
Runfi rabio
300
3.5
Cost rañio
1.10
250
3.0
1.08
200
2.5
1.06
150
2.0
1.04
100
50-
1.5
1.02
10000
20000
30000
10000
20000'
30000
10000'
20000'
30000
Uniform Random Points d=64
/upparbourx
12
14
Cost ratio
1.08
Runtime ratio
80
10
1.06
60
40
1.04
20
1.02
0
10000'
20000'
30000
10000
20000'
30000
0
10000'
20000
30000
Uniform Random Points d=128
Yupper bound
20
1.06
Runtime ratio
50
Coss ratio
1.05
40
15-
1.04-
30
10-
1.03
20
5-
1.02
10
1.01
0
10000
20000
30000
10000
20000
30000
0
10000'
20000
30000
t= 16
=
32
t=
+t= 128 X t = 256
Figure 7: Results on synthetic uniform random data for dimensions d (4, 16, 64, 128). Each point in each plot represents an average over 16 sampled point clouds for fixed n and choice of component number t. Runtime ratio is the ratio between the runtime for the optimal MST algorithm divided by the runtime of our MFC framework (including initial forest generation). Cost ratio is the ratio between the spanning tree weight for our method and the optimal MST weight. The upper bound computed by comparing the initial forest overlap with the one optimal MST computed.
20

---

Approximate Forest Complction for Metric Minimum Spanning Trees
analysis: for a fixed value of L the ratio between the exact algorithm runtime and the runtime of the MFC framework converges to a constant as n increases. As t or d increases, need larger value of n to reach this asymptotic speedup. As t increases and the asymptotic runtime improves, the quality of the approximate spanning tree decreases slightly, but the cost approximation ratio still remains very good (i.e., close to 1) in all cases. The 7-overlap bound 7 tend to be small for low dimensions, but gets large as d increases (e.g.. 7 close to 30 for d = 256). Nevertheless, cost ratios remain very close to 1, and even improve slightly as d increases.
D.2. Additional details for clustered data
For our experiments on Gaussian synthetic data (Figure 6), we generate a mixture of g Gaussians in d-dimensional Euclidean space with g ranging from 8 to 300. For each Gaussian we generate [20000/g] points, so that n R 20000 for each dataset. The mean of each Gaussian is chosen uniformly at random from an 8-dimensional box where each axis ranges from -5 to 5. The standard deviation of each dimension of each Gaussian is chosen uniformly at random between 0.5 and 0.8. In practice these parameters generate good (but not perfect) clustering structure. We then run our MFC framework for each choice of initial component number i E {16, 32, 64, 128, 256}.
Figure& 8 shows results for wider range of d values and includes runtime ratio plots as well. We see good performance in runtime improvements, with larger values of t leading to a larger asymptotic speedup (up to a 400x speedup for = 256 and = 8). The cost ratio and 7 values show the same basic trend for all dimensions: the quality of the spanning tree returned by our method the best when I Rs g. Thus, when we have good estimate of the number of number of true underlying clusters in a dataset, we can leverage this information when generating an initial forest and running our MFC framework.
D.3. Additional details and results for real-world data
In Table 3 we include expanded results for the real-world datasets. This includes results for a wider range of values (number of components generated for the initial forest), and details for the proportion of time spent on the three main steps of our MFC framework:
1. k-centering: obtaining the initial partitioning P using a greedy 2- 2-approximaton for k-centering (Gonzalez, 1985).
2. Sub-MST: Using Kruskal's algorithm to find optimal MSTs (T.) for the components of P.
3. MFC-Approx:
Approximating the MFC problem using MFC-Approx.
As anticipated, the most expensive step in this pipeline is typically computing optimal MSTs for the components (Sub-MST step). However, as increases, the k-centering step and the MFC-Approx algorithm become significant portion of the overall runtime, and even dominate in extreme cases. We remark that the MFC-Approx step is always dominated by the time it takes to form the coarsened graph Gp. The time spent finding MST of Gp is negligible for all datasets and choices of t we considered.
We note several trends in the performance of our MFC framework from Table 3. Across all datasets (and corresponding distance metrics), the y values tend to be very good: usually below and never above 3.2. As expected, 7 values get slightly worse as increases. This is also true for cost ratios, but cost ratios nevertheless remain very good in all cases (always below 1.2 and typically much better). In general, runtimes improve as increases up to a certain point. Once becomes too large, computing MSTs for the components found by k-centering is longer the bottleneck. When the number of components becomes too large, the k-centering step and building the coarsened graph become too expensive. This is especially clear on the GreenGenes-Unaal Unaligeed dataset, but the same behavior can be observed in other cases as well.
Names-US Dataset One exception to the general runtime trends is that running the MFC framework on the Names-US dataset, for small values of t. in fact slower than computing an optimal MST. On this dataset, we found that the k-centering step in our MFC framework tends to form a disproportionately large component, and finding an MST of very large component takes nearly as long as finding MST of the entire dataset. Combining this with the time taken on other steps in our MFC framework can lead to larger overall runtime. This behavior (having single large cluster) is likely tied to the fact that the Names-US dataset contains extreme outlier strings which causes our simple k-centering implementation to create tiny clusters for these outliers, while grouping most other non-outlier strings into a single large cluster. Despite this bad behavior, we note that runtime ratios do continue to increase as t increases and our MFC framework is faster for the largest values.
21

---

Approximate Forest Complction for Metric Minimum Spanning Trees
Gaussian Random Points d-4
1.40
1.09
600
1.35
1.08
500
Yupper bound
1.30
Cost ratio
1.07
Runtimo ratio
400
1.25
1.06
1.05
300
1.20
1.15
1.04
200
1.03
1.10
100
1.02
1.05
0
32
64
128
256
32
64
128
256
100'
200
300
Gaussian Random Points d=8
2.0
1.10
500
/upperbound
Yupper bound
1.8-
1.08
Runtime ratio
400
Cost Costratio ratio
1.6
1.06
300
1.4
1.04
200
1.2-
1.02-
100
1.0
1.00
0
32
64
128
256
32
128
256
100
200
300
Gaussian Random Points d=32
4.0
1.10-
200
Yupper bound
3.5
1.08
Runtime ratio
3.0
Cost ratio
150
1.06-
Yuppar
2.5
100
1.04
2.0
1.5
1.02
50
1.0-
1.00
0g
32
64
128
256
32
64
128
256
100"
200
300
Number of Gaussians (g)
Number of Gaussians (g)
Number of G Gaussians (g)
16
A
32
64
128
Rt= 256
Figure 8: Results synthetic data with clustering structure: mixtures of Gaussians for various d. Cost ratio and y-overlap bound 7 is typically minimized when the number of Gaussians y roughly matches the number of components & used by our MFC framework.
Fashion-MNIST 784
1.7-
1.05
12-
bound
1.6-
1.04
Runtime ratio
10-
1.5-
8-
1.4
Cost
1.03
1.3
1.02
4
2-
1.2
1.01-
0
0
10000
20000
30000
0
10000
20000'
30000
10000
20000
30000
m
n
= 16
32
1=64
+ 128
X
256
Figure 9: Results for Pashion-MNIST Each point is the average of 16 samples for fixed and t.
22

---

Approximate Forest Complction for Metric Minimum Spanning Trees
Names-US Modified k-centering t 255
Maximum Compunen Sizo
5-
1.20-
20000
Runtinee Ratio
10
Cost CastRattin Ratio
1.15-
3
10000
1.10-
2-
1.05-
0-
0
10000
20000
30000
0
10000
20000
30000
10000
20000'
30000
Original k-centering Modified k-centering
Figure 10: Results comparing a slightly modified version of k-centering to the unmodified version on the Names-US dataset when 256. The r-axis reports the number of names n sampled from the larger dataset. The modified version of k-centering first runs normal k-centering with k t/2, then it further refines the largest cluster by running k-centering on that cluster with & t/2 + 1, resulting in total of t components. Additionally, when the distance between point and multiple cluster centers is equal, the point is added to the smallest of those clusters. This reduces the size of the largest component (left plot), resulting in slightly worse cost ratios (middle plot) but better runtime improvements (right plot).
Uniform Random Points d=8
Uniform Random Points d=256
Names-UP
MFCA Approcimation Retio
1.025
1.0025-
1.020
1.0020-
1.03-
1.015
1.0015-
1.02-
1.010
1.0010-
1.01-
1.005
1.0005-
1.000-
1.0000-
1.00
10000
20000
30000
0
10000'
20000'
30000'
0
10000
20000
n
I
16
= 32 64
+t=
128 Xt= 256
Figure 11: Results showing the MFC approximation ratio achieved on both synthetic and real world data. The MFC approximation ratio equals the weight of the spanning tree produced using our MFC approximation divided by the weight of the spanning tree produced by optimally completing the initial forest (i.e., optimally solving MFC). The input to the MFC algorithm here is produced using the same process previous experiments, using k-centering for clustering and optimally solving the MST problem on individual components.
We found that slightly modified version of our k-centering step provides a simple way to improve results on the Names-US dataset. This modified version first runs normal k-centering to form = t/2 initial clusters, then runs the k-centering algorithm again on the largest cluster to break it into 1/2 + components. This creates the same number of components as running k-centering once with parameter k f on the dataset. Additionally, when iterating through points to assign them to clusters after the centers have been chosen, if point has the same distance multiple cluster centers, this modified k-centering algorithm assigns the point to the cluster with the current fewest number of points. Figure 10 shows results for the full MFC pipeline on the US dataset when we used this modified version of k-centering for t 256. We also show results in a new entry at the end of Table 3. We can see that this simple modification to the k-centering algorithm improves the results significantly on the Names- US dataset for both small and large values of t.
D.4. Approximation for MFC Problem
Our previous results all focused on approximations for the MST problem using our MFC framework, i.e., comparing in in-practice approximations against the bound in Theorem 4.3 given in terms of yf Figure 11 shows approximation ratios for just the METRIC FOREST COMPLETION problem. other words, we compare against the weight of the best spanning tree that completes the initial forest, rather than against the weight of an optimal spanning tree for the original dataset. Theorem 4.2 shows this ratio must be less than 2.62. In practice, are consistently under 1-1, far better than the theoretical guarantee.
23

---

Approximate Forest Completion for Metric Minimum Spanning Trees
Table 3: Results for real-world datasets using various types of metrics. Runtimes are in minutes. For the last 5 datasets we report averages and standard deviations for 16 different samples of size The last three rows for each dataset report the proportion of time spent on each step of the MFC framework.
Dataset
OPT
16
32
t
t
t 256
Cooking
1.770
2.014
2.222
2,421
3. 3.144
Cost Ratio
1.040
1.051
1.059
1.069
1.089
39774
Runtime Ratio
4.391
6.524
8.689
9.966
15.598
Runtime (mins)
24.2+0.61
5.3
3.5
2.7
2.3
1.5
k-centering %
0.006
0.016
0.038
0.082
0.321
Sub-MST %
0.989
0.971
0.923
0.826
0,355
MFC-approx %
0.004
0.013
0.038
0.092
0.324
MovieLens
7 Cost Ratio
1.395
1.513
1.690
1.955
2.283
1.010
1.012
1.017
1.022
1.028
33240
Runtime Ratio Runtime (mins)
4.026
5.014
6,287
9.337
9.529
136.0115.3e
120.3
96.6
77.0
51.9
50.8
k-centering %
0.016
0.028
0.054
0.130
0.238
Sub-MST
0.978
0.959
0.912
0.765
0.508
MFC-approx %
0.006
0.013
0.034
0.104
0.253
Kosarak
+ Cost Ratio
1.289
1.737
2,281
2.788
3.129
1.007
1.013
1.020
1.025
1.029
w = 32295
Runtime Ratio
2.682
5.994
15.159
18.174
12.583
Runtime (mins)
182.2#0.26
68.0
30.4
12.0
10.0
14.5
k-centering %
0.010
0.036
0.146
0.363
0.464
Sub-MST %
0.985
0.935
0.725
0.339
0,138
MPC-approx
0.005
0.028
0.128
0,297
0.397
SeenGGenes-nnalige
1.388=0.06
1.460=0.07
1.460=0.08
1.402+0.04
1.31420.02
Cost Ratio Runtime Ratio Runtime (mins)
1.092=0.02
1.104_0.01
1.05520.01
1.075+0.01
1.055+0.00
2500
2.555=10.55
3.270=0.32
3.156=0.30
2.116+#0.u
1.159+0.04
239.3#6.22
98. 08800
74.9+11.99
76.7+8.8
113.2+4..0
206.5+6.0
k-centering %
0.068
0.172_0.00
0.331:0003
1..48
0.49210.01
Sub-MST %
0.885_0.03
0.692_.0.0
0.377..0.0
0.134.10.0
0.04710.01
MFC-approx %
0.047=0.01
0.136=0.0x
0.292=a.05
0.418+00.1
0.46140.01
GreenGenes-Alignaal
4 Cost Ratio Runtime Ratio Runtime (mins) 13.1
1.224=0.07
1.368
1.466=0.06
1.51 220005
1.531 +0.03
1.074=0.02
1.117
1.04
1..47
1.14110.01
30000
1.604=0.31
2.375
3.918=1.99
5.849
7. 7,026+1.69
22. 1::.9
15.1
9.9.3..1
6.712.6
5.0=1.3
k-centering %
0.003 000
0.010 00
0.033=0.02
0.098
0.23220.05
Sub-MST
0.994=0.00
0.983=0.01
0.940=0.ox
0.817#0.01
0.550+0.12
MFC-approx %
0.002=0.00
0.007=0.00
0.027=0.02
0.084+0.05
0.216+0.07
Fashion-MNIST
1.173_00.02
1.237_0.00
1 1.32010.05
1.405
1.52710.05
Cost Ratio
1.013
1.017=0.00
1.023
1.020
1.03611.000
a = 30000
Runtime Ratio
4.675=1.42
7.176=2.55
10.027 85
12. 12942.64
12.698
Runtime (mins)
11.4:0.31
2.7.+0.8
1.840.7
1.240.4
1.0+0.2
0.9
k-centering %
0.008=0.00
0.024=0.01
0.067=0.02
0.16240.18
0.339
Sub-MST %
0.986=0.00
0.963_0.01
0.896=0.03
0.746 06
0.46220.07
MFC-approx
0.004 00
0.013=0001
0.036=0.01
0.090 02
0.197.0.03
Names-US
5
1.020=0.02
1.059=0.0r
1.139=0.04
1.219+0.06
1.322+0.07
Cost Ratio
1.005=0.00
1.015=0.01
1.044=0.11
1.05
1.07 L00710000
30000
Runtime Ratio Runtime (mins)
0.923-0.16
0.954_0.18
0.93
1.02710.19
1,13810.21
2.0.1.28
2.110.2
2.110.2
2.110.2
1,910,2
1.7
k-centering %
0.003=0.00
0.005=0.00 00
0.009=0.00
0.019:20.00
0.03840.00
Sub-MST %
0.995=0.00
0.992 00
0.985=0.00
0.970
0.937
MFC-upprox %
0.001=0.00
0.003
=..00
0.01140.00
0.0244
Names-US Reclustered
YY Cost Ratio
1.034=0.02
1.100
1.224=0.04
1.479++0.16
2.080+0.22
1.008_...0
1.026_o..1
1.054.1..01
10.00
1.170.0.02
N = 30000
Runtime Ratio
1
1.074_0..1
1.114_0011
1.2466.0.25
1. 1.389
2. 688811.81
Runtime (mins)
1.940.31
1.8
1.7+0.1
1.5
1.4+0.2
0.7
k-centering % Sub-MST
0.003=0.00
0.006
0.012=0.00
0.024+0.00
0.083+0.02
0.994_0.00
0.990
0.981.20.0
0.96110.01
0.86040.04
MFC-approx %
0.002=00.0
0.003=0.00
0.007:20.00
0.015
0.057
24


Reviews:
[{"review_id": "vZX8yCsCTw", "reviewer": "Reviewer_udd8", "summary": "This paper considers the problem of finding subquadratic algorithms for metric MST (minimum spanning tree in a metric space) by leveraging learning-augmented algorithms. The goal is to break through strong lower bounds on runtime: the authors motivate the present work with the result that in an arbitrary metric space, it is impossible to achieve *any* constant factor approximation without knowing $\\Omega(n^2)$ edges. In practice, such algorithms are not scalable. To this end, they assume an algorithm has access to an initial forest (on the whole vertex set) that can be thought of as an approximation to a spanning tree (e.g., the output of the first few iterations of Kruskal's algorithm). Given this, the goal is to find an algorithm that solves the Metric Forest Completion problem (MFC), which is to find a minimum-weight set of edges to add to the forest to produce a full spanning tree. This is a connectivity augmentation problem that, to solve to optimality, again requires $\\Omega(n^2)$ queries. However, the approach taken here is to instead look for an approximation algorithm that takes subquadratic time. It is important to note that the objective used for computing the approximation ratio is the weight of all edges in the final tree (that of the initial forest and the augmenting set); the authors note that, without counting the initial forest, one cannot achieve good approximations. \n\nThere are three main contributions:\n\n- For initial forests with $o(n)$ components, a 2.62 approximation algorithm for MFC with query complexity $o(n^2)$. \n- A notion of error (coined $\\gamma$-overlap) between the initial forest and the optimal MST, and an analysis that the above algorithm's approximation for the MST problem (not the MFC problem) can be parameterized by $\\gamma$: specifically, it achieves a $(2\\gamma + 1)$. In particular, for perfect overlap ($\\gamma = 1$, meaning all edges in the initial forest are in an optimal MST), this algorithm is a 3-approximation for MST. \n- Experiments on real and synthetic datasets (with Euclidean and non-Euclidean metrics) showing that fast heuristics like the $k$-center algorithm can be used to generate an initial forest, and, for datasets with underlying structure, with small $\\gamma$. They also show that the approximation ratio tends to be notably better than the theoretical bound.\n\n\n## update after rebuttal:\n The authors answered the questions well and I maintain my evaluation.", "questions": "", "limitations": "", "rating": 4, "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": "Thank you for your feedback on our manuscript!\n\nRegarding the section in the appendix on MSTs with predictions, we agree that this related work provides good context for our work and would be nice to include in the main text. Ultimately we moved this to the appendix because of space constraints. However, if the manuscript is accepted this will allow 1 additional page of space, which we would use to elaborate on related work in the main text.\n\nWe agree that comparing our approach against other heuristics would be interesting, but the main issue is that only existing heuristics that we are aware of apply only to Euclidean metrics. Our manuscript focuses on algorithms that work for arbitrary metric spaces, and hence we felt that the best experiment section for this paper would provide a concrete comparison between methods that come with theoretical guarantees for arbitrary metric spaces, which in this case amounts to comparing our new approach against the naive quadratic approach.\n\nFinally, regarding your question about analogues of the MFC problem for other combinatorial problems—at present we are not aware of any, but we think this is a very interesting direction to consider in future work. Thanks for the suggestion!", "claims_and_evidence": "Yes, theoretical claims are supported with proofs (deferred to Appendix), and experimental claims are supported with a detailed explanation of dataset construction and analysis.", "methods_and_evaluation_criteria": "Yes, in addition to proof-of-concept synthetic datasets, the authors use a number of real-world datasets that are used as benchmarks in the clustering literature, and standard measures of distance on that data.", "theoretical_claims": "I did not check proofs, which are all deferred to the appendix.", "experimental_designs_or_analyses": "I read through the experimental design and analyses included the appendix, and found the methods completely reasonable.", "relation_to_broader_scientific_literature": "This paper contributes to the recently popular framework of algorithms with predictions -- a type of beyond-worst-case approach to algorithm design that seeks to improve algorithmic performance by augmenting algorithms with a (often machine-learned) \"prediction\" of some parameter of the input (in this case, the initial forest is a \"prediction\" of the MST). A number of prior works have considered, as the authors do here, this framework for improving *runtime* for popular algorithmic problems (e.g., binary search, min-cost perfect matching, maximum flow). The MST problem has also been considered in the predictions framework, but with different models for what information is learning-augmented, specifically, they all consider predictions on edge weight. The authors here are also distinct in their goal of obtaining subquadratic  algorithms.", "essential_references_not_discussed": "I did not notice any important related works that are missing.", "other_strengths_and_weaknesses": "There are several interesting contributions here. One is the metric forest completion problem (MFC), which is a model admitting an informative analysis even when $\\lambda$ is potentially large (the only assumption is that the initial forest has a sufficiently small number of components). Another is the learning-augmented framework. While previous papers have considered MSTs with predictions, the present framework is distinct, as it is practically and conceptually of interest to obtain subquadratic algorithms for this problem. What is further interesting and distinct here is that the warm-start initial forest is not necessarily some black-box, machined-learned prediction (although it could be), but can be generated from the data itself (e.g., by performing the $k$-center heuristic), and indeed the authors show that doing so is effective in practice. Finally, the authors devise a novel error metric ($\\gamma$-overlap) for the \"distance\" between a spanning forest and an optimal MST that is amenable to analysis; this is interesting as there seemingly isn't a natural / obvious one here.", "other_comments_or_suggestions": "While the paper is very well-written and has very nice figures, I think the related work in the appendix on MSTs with predictions is important context with which to situate the present contribution, and therefore should be promoted to the main body. \n\nYou may also consider including additional references of results on using the predictions framework to improve runtime.", "questions_for_authors": "Did you consider comparing the performance of your algorithm against heuristics that compute a full MST in subquadratic time (e.g., if there are any common ones used in practice to overcome the runtime bottleneck)?\n\nAre there any analogues of your MFC problem for other combinatorial problems? Particularly, the idea of computing the approximation ratio with respect to the total cost rather than just the cost of the new edges $M$ (which as you point out is necessary in order to obtain meaningful results)?", "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": "7MwTX1pub9", "reviewer": "Reviewer_29qN", "summary": "The paper considers the problem of building Spanning tree of a set of points in a metric space. The goal is to have a tree that is a good approximation of the MST without querying all the Theta(n^2) pairwise distances. The approach proposed is to have an algorithm that starts from an initial forest and then merges the trees building an overall spanning tree. The algorithm proposed achieves constant approximation if the initial forest has a good \"overlap\"with some optimal MST. In this sense the approach falls in the category of learning-augmented algorithm, i.e., if by some predicting strategy a good initial partial solution is provided, then the remaining steps have good performance guaratee---not achievable in general because of well known hardness results implying Omega(n^2) queries for any constant approximation.\n\n## Update after rebuttal\nI kept my positive score. The rebuttal  didn't need to bring any further information.", "questions": "", "limitations": "", "rating": 4, "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": "Thank you for the review and helpful feedback on our manuscript!", "claims_and_evidence": "The theoretical part appear to be sound.", "methods_and_evaluation_criteria": "The experimental analysis of the practical efficacy of the approach is well structured. The authors design and uses different sets of tests with both synthetic (uniformly sampled) and data from real databases. The experiments address 4 questions (runtime, the initial overlap achievable in practice, theoretical bounds vs performance in practice, effect of different datasets and metrics on performance) and the results are convincing.", "theoretical_claims": "I checked some of the lemmas' and theorems' proofs also in the appendix.", "experimental_designs_or_analyses": "See above", "relation_to_broader_scientific_literature": "The approximation guarantee in the framework of general metric speces is to my knowledge new.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strenghts: \nTheoretical guarantees conditional to the goodness of the initial forest.\nA significant set of experimental analyses addressing the individual parts of the approach and how internal (initial setting) and external (dataset structure) affect the performance.", "other_comments_or_suggestions": "-", "questions_for_authors": "-", "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": "05xAUIpOcb", "reviewer": "Reviewer_C5ud", "summary": "The paper presents a new framework for computing approximate minimum spanning trees (MSTs) in arbitrary metric spaces, improving the time complexity compared to traditional exact MST algorithms. The exact MST algorithms require $\\tilde{O}(m)$ time complexity, where $m$ is the number of edges. For a complete graph over $n$ vertices, it requires $O(n^2)$ time.\n\nThe authors propose the Metric Forest Completion (MFC) problem, which assumes access to an initial forest obtained via heuristics or exact algorithms, and aims to find a set of edges to complete it into a spanning tree. They show that optimally solving MFC still requires $\\Omega(n^2)$ queries in the worst case, but they provide a 2.62-approximation algorithm in subquadratic time as long as the number of components $t = o(n)$. Additionally, in the learning-augmented setting, they prove that if the initial forest has a sufficient overlap with an optimal MST, the approximation factor improves based on the overlap parameter $\\gamma$. Experimental results on synthetic and real-world datasets demonstrate that the proposed approach finds near-optimal spanning trees significantly faster than exact methods.", "questions": "", "limitations": "", "rating": 4, "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": "Thank you for the feedback on our manuscript! We appreciate the open question you posed. In response to those questions:\n\n1. This is an interesting question. As potential follow-up work, we have indeed wondered whether we could use assumptions or parameters relating to the structure of the initial forest to further improve our guarantees (e.g., parameters or structures that results from specifically using a k-centering approximation algorithm or another method to form the initial forest). \n\n\n2. This is a very interesting question and we do have at least a partial answer with regard to the effect of balancedness on runtime. The answer is a little nuanced because it depends on whether you consider the method used to form the initial forest. If we focus solely on the MFC problem with a given forest, it turns out that unbalanced clusters lead to faster runtimes, even for optimally solving the MFC problem. Note that the $\\Omega(n^2)$ lower bound on runtime we give in Theorem 3.1 is assuming a worst-case scenario of balanced clusters. It is an interesting open direction to explore more concrete results if we assume a certain level of balance or imbalance.   \nThe answer changes slightly if you also consider the method used to construct the initial forest. In our experiments we computed the MSTs of our components optimally. Because of this, having unbalanced clusters means computing an optimal MST for a large component, which is computationally expensive and ends up outweighing the runtime benefit we get for solving the MFC step of the overall MST pipeline. Conversely, for balanced clusters the runtimes tend to be much better, and we still obtain good approximation guarantees. These tradeoffs are highlighted in Table 3 of our paper, where we include runtimes for the different steps of the full MFC framework (including forming the initial forest). These observations are all based on one approach for forming an initial forest (k-centering + optimally finding MSTs of components). Continuing to explore tradeoffs using this or other approaches for forming the initial forest is a very interesting open future direction.", "claims_and_evidence": "The claims are well-supported by theoretical proofs and empirical results.", "methods_and_evaluation_criteria": "Their methods make sense for the MST problem. Their evaluation criteria are comprehensive, including the approximation factor, runtime, and an upper bound on overlap parameter $\\gamma$ given by the overlap with the MST solution over various synthetic datasets and real-world datasets.", "theoretical_claims": "I checked the correctness of all proofs including Theorem 3.1, Theorems 4.2 and 4.3 and all relevant Lemmas.", "experimental_designs_or_analyses": "Yes, the experimental designs and analysis are sound and valid.", "relation_to_broader_scientific_literature": "This paper is related to a broad scientific literature including MST, clustering, graph algorithms, learning augmented algorithms, etc. The MST algorithm is also widely used in many machine learning and graph algorithms. This paper has also a great impact on these research as well.", "essential_references_not_discussed": "No, as far as I know, the related works are discussed adequately in this paper.", "other_strengths_and_weaknesses": "Strengths: \nThis paper introduces a new framework for finding approximate MST for arbitrary metric space, making a meaningful contribution to scalable MST computation. The connection to learning-augmented algorithms is well-motivated. The experiments across multiple datasets show their method provides nearly-optimal MST (with approximation factor close to 1) with 30 to 400 times speed up compared to the traditional exact algorithms. Furthermore, the proposed framework is particularly relevant for large-scale clustering and similarity-based learning tasks.\n\nOverall, I think the framework and analysis in the paper are quite interesting and the experiments are surprisingly good and show the efficiency and effectiveness of their methods.", "other_comments_or_suggestions": "I don't have any further comments.", "questions_for_authors": "I only have some open-ended questions:\n\n1. In your experiments, the datasets with cluster structures show smaller upper bound on the overlap parameter $\\gamma$. In the approximation analysis, would it be possible to have some explicit parameters other than $\\gamma$, like a separation parameter, to improve the approximation factor?\n\n2. It is nice that the analysis even does not rely on any balanceness of the forest partition. Would it be possible to get a better approximation factor or trade-off depending on the balanceness of the partition?", "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": "ZCCKO9Blkd", "reviewer": "Reviewer_ki5g", "summary": "The paper considers Metric Forest Completion (MFC) problem. \nLet $G$ be an edge-weighted complete graph whose weights satisfy the triangle inequality (it induces a metric space).\nGiven a forest $F \\subseteq G$, the MFC asks for the set of edges with a minimum sum of weights that connects the components of $F$. \nThey prove that  $\\Omega(n^2)$ query edges are required to optimally solve MFC  and present a subquadratic algorithm with an approximation factor $2.62$. In addition, they report an experimental study that shows that their approach provides gains in terms of  scalability without significantly compromising the quality of the produced solutions (spanning trees)", "questions": "", "limitations": "", "rating": 4, "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": "Thank you for your feedback on our manuscript!\n\nThanks for your question about the parameter t, which we agree can be better clarified. As you noticed, the apparent discrepancy comes from whether or not one incorporates the time taken to form the initial forest. The theoretical analysis in lines 315-319 (left column) focuses on our algorithm for the MFC problem specifically, which assumes the initial forest is given. However, because computing initial forests is an important consideration in practice, our runtimes in the experiments include the time for computing an initial forest. We originally wanted to include a full runtime analysis that included the initial forest computation (using the k-centering approach), but were space constrained (hence the reference to Appendix D in line 319 left column). In the appendix, we also include runtimes in Table 3 for each step of the pipeline individually, but again for space constraints we were unable to include this in the main text. Again though, we agree that this could be confusing and we will update the text to better clarify this point.\n\nRegarding algorithm comparisons, we agree that comparing our approach against other heuristics could be interesting. The main issue, as you highlight, is that existing methods are focused only on Euclidean metrics, and we are focused on algorithms that apply to general metric spaces and have theoretical guarantees. With this in mind, we felt that the best experiments section for this paper would be to provide an extensive comparison between our approach and the optimal quadratic algorithm for arbitrary metric spaces, across a wide range of datasets and metrics. \n\nRegarding your question about Theorem 4.2, note that this is a result purely about an approximation for the MFC problem, not the MST problem on the original dataset. As such there is no defined $\\gamma$ parameter here since it is a result independent of the overlap between the initial forest and some optimal MST. However, if we did assume that $\\gamma = 1$ as you suggest, note that the optimal solution for MFC coincides with the optimal solution to the MST problem on the full dataset. Hence a corollary of this theorem is that if $\\gamma = 1$ for the initial forest, we get a 2.62 approximation for the MST problem (not just the MFC problem).\n\nThanks for your point about the use of “in practice”. We agree and will update this.", "claims_and_evidence": "I think they are clear", "methods_and_evaluation_criteria": "Yes, they make sense", "theoretical_claims": "I have not checked them.", "experimental_designs_or_analyses": "Yes, I checked the experimental designs and analyses and found no major issues. \n\nThat said,  I think the behavior of $t$ needs some additional explanation. The time complexity (line 315, left) increases with $t$  but in the experimental results (line 317-319, Right), the speed up increases for larger $t$, which is not in line with the theoretical analysis. \nI believe the reason is that in the time complexity analysis, one does not take into account the construction of the initial forest, while in the running times reported in Section 5, it is taken.  In any event, I think it should be clarified. Maybe adding an extra parameter in the time complexity analysis to represent the time taken by the initial heuristic should be helpful.", "relation_to_broader_scientific_literature": "Most of the algorithms available for building MST in metric spaces (lines 29-33 and 119-121, right) are only suitable for Euclidean distance.\nThis work differs from previous work since it handles general metric spaces that include, for instance, edit distance.\n\nFor this more general setting, there are lower bounds (Indyk 99) which show that any algorithm with constant approximation for building an MST needs to query/know   $n^2$ edges. To overcome this obstacle (prove theoretical bounds), the algorithm takes the approach of the (recent) field of learning-augmented algorithms,  assuming the availability of a prediction/warm start, obtained via a heuristic or a prediction method. Under this assumption, they obtain an algorithm with an approximation factor that depends on how good the prediction is (parameter $\\gamma$).", "essential_references_not_discussed": "I'm not aware of essential related work that was not cited in the paper.", "other_strengths_and_weaknesses": "My positive score is based on \n\nStrengths\n\n* The design of scalable algorithms for MST, in metric space, with provable guarantees is a relevant topic  As the authors mention, and I agree,  for many tasks (some in the Machine Learning domain) the construction of an MST is an important step.\n\n* The paper is, in general, very well written. \n\n*  The proposed framework is simple enough so that one would not have problems reproducing it. \n\n*  Both the improvement in terms of time complexity and the approximation bounds are interesting enough.\n\n* The experiments were well designed \n\n\nWeakness\n\n* Lack of comparison with other available methods to build MST for metric spaces (even in Euclidean space). I think the paper can be accepted without that, but adding these comparisons would make the paper stronger and more informative regarding what should be used in practice.", "other_comments_or_suggestions": "Some points:\n\n* For Theorem 4.2, I understand you are assuming that $\\gamma=1$. Is this correct? In the positive case, you shoud state that. \n\n* line (329, right). I would avoid in \"practice\" since I do not see  uniform random data as a typical case that occur in practical applications.", "questions_for_authors": "No relevant 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": {}}]

Author rebuttal:

Meta-review: All reviewers like the results of this submission and are convinced that approximating a minimum spanning tree of a point set by a learning-augmented algorithm in subquadratic time is an important result, which has applications for various problems (e.g. hierarchical clustering). Also the technical contribution is interesting and non-trivial and in the experiments the proposed method performed even better than in the worst case. Overall, I consider this to be a strong contribution to ICML.
Decision: Accept (poster)