{"id":"74b639b9-5a44-43ab-a590-d01aa68ec17c","arxiv_id":"2507.14261","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A three-phase approximate MST algorithm using ANN graphs, random component linking, and local edge refinement achieves near-linear scaling with small error on large high-dimensional data.","lead":"This paper introduces FAMST, a fast approximate algorithm for building minimum spanning trees on large, high-dimensional datasets. It builds a sparse nearest-neighbor graph, connects its separated pieces, and refines those connections, reporting up to 1000 fold speedups over exact methods with very small approximation errors.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 3 adds λ edges per component pair, so the inter-component edge set is Θ(t²λ), not Θ(tλ); Section 4.1's complexity breakdown and the O(dn log n) claim therefore require t = O(√n), a condition never stated or proven.","rationale":"The central claim is an unconditional O(dn log n) complexity for FAMST. The proof in Section 4.1 is internally inconsistent: Algorithm 3 explicitly iterates over all C(t,2) component pairs and inserts λ edges per pair, so the inter-component edge count is Θ(t²λ), not Θ(tλ). This error propagates into the Kruskal and refinement bounds and into the space bound. The only way the simplified O(dn log n) can hold is if t = O(√n) for constant k, λ. The paper neither proves this nor states it as an assumption; 't ≪ n' is too weak. The reported experiments show small t for a handful of datasets, but they do not cover worst-case component structures, and the paper does not record t for most of Table 1. A synthetic test with t ≈ n^{3/4} well-separated clusters directly targets this gap: it either demonstrates superlinear scaling and falsifies the headline complexity, or it shows the concern is benign. Because the problem is a fixable but central flaw in the theoretical analysis, the reader's CONDITIONAL verdict is appropriate; no verdict change is needed.","tokens_in":14568,"tokens_out":9000,"duration_ms":101672,"concrete_test":"Run FAMST with k=10, λ=5 on synthetic data with n = 16k, 32k, 64k, 128k points arranged into t = n^{3/4} well-separated Gaussian clusters (each cluster ~n^{1/4} points, far apart so the kNN graph has one component per cluster). Record the actual component count t', the number of inter-component edges output by Algorithm 3, and total wall-clock time. If |E_inter| scales as t'^2 and runtime grows superlinearly (e.g., > n^{1.1}) while t' stays ~n^{3/4}, the O(dn log n) claim is falsified. If runtime remains near-linear despite this adversarial component structure, the concern does not land.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Algorithm 3, every component pair (i,j) yields λ best edges after sampling λ² candidates, so the inter-component edge set has size Θ(t²λ) and candidate generation costs Θ(t²λ²) distance evaluations plus sorting. Section 4.1 nevertheless writes the Kruskal edge count as E = O(kn + tλ) and the refinement loop as processing O(tλ) inter-component edges, undercounting by a factor of t. With the correct E = Θ(kn + t²λ), the overall time becomes O(k²dn log n + r t²λ k + (kn + t²λ) log(kn + t²λ)) and space becomes O(dn + kn + t²λ). The simplified O(dn log n) follows only under t = O(√n) for constant k and λ; the paper only asserts 't ≪ n,' which is insufficient (t = n^{3/4} is still ≪ n but makes t²λ superlinear). No theorem or experiment in the paper establishes t = O(√n), so the central near-linear complexity claim is not proven.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes FAMST, a three-phase approximate MST algorithm: construct a k-ANN graph via PyNNDescent, identify connected components, add λ random edges per component pair, iteratively refine inter-component edges through neighbor-of-neighbor exploration, and finally run Kruskal's algorithm. It claims O(dn log n) time and O(dn + kn) space, and reports experiments on 14 datasets with mean relative error 0.44% and speedups up to roughly 1000× against the exact EMST implementation in mlpack.","tokens_in":14804,"tokens_out":6443,"duration_ms":69951,"significance":"If the complexity claim held, this would be a practically valuable contribution for high-dimensional MST construction, combining an off-the-shelf ANN builder with a lightweight refinement heuristic and validating against an independent exact MST implementation. The empirical evaluation is reasonably careful: it uses mlpack EMST as ground truth, averages over 10 runs, and includes phase-by-phase scaling experiments. However, the complexity analysis undercounts the inter-component edge set by a factor of t, and the headline O(dn log n) is conditional both on the typical-case (not worst-case) behavior of NN-Descent and on unstated assumptions about the number of disconnected components. Until these issues are resolved, the central theoretical claim is not established. No code or reproducibility artifact is provided.","major_comments":[{"comment":"The analysis undercounts the inter-component edge set by a factor of t. Algorithm 3 loops over all O(t²) component pairs and inserts the λ best of λ² sampled edges per pair, so |E| = Θ(t²λ), not Θ(tλ). Consequently, the refinement step processes Θ(t²λ) edges (its cost is O(r t² λ k), not O(r t λ k)), and Kruskal's input has Θ(kn + t²λ) edges (so the final term is O((kn + t²λ) log(kn + t²λ))). With these corrections, the overall time is O(k² d n log n) + O(t² λ² log λ) + O(r t² λ k) + O((kn + t²λ) log(kn + t²λ)), and the simplified O(dn log n) claim requires t = O(√n) for constant k, λ, and r. The paper only states that t ≪ n empirically; that is insufficient (e.g., t = n^{3/4} still satisfies t ≪ n but makes the t²λ term superlinear). Since no theorem or experiment establishes t = O(√n), the central near-linear complexity claim is not proven.","section":"Section 4.1, Algorithm 3"},{"comment":"The asserted O(dn log n) complexity rests on the 'typical' runtime of NN-Descent/PyNNDescent from [24], which the paper itself notes has no strict worst-case guarantee. The abstract and conclusion present O(dn log n) as an achieved complexity; the authors should either provide a worst-case bound for the chosen ANN construction method or explicitly label the headline complexity as expected/heuristic, stating the additional assumptions on k, t, and r under which it holds.","section":"Section 4.1, ANN graph construction"},{"comment":"The space accounting for inter-component edges is inconsistent with the algorithm: Section 4.2 states a total of O(tλ²) inter-component edges, but Algorithm 3 stores λ edges per component pair, i.e., Θ(t²λ) edges. This should be corrected to Θ(t²λ); the term is negligible only under the same t = O(√n) condition needed for the time analysis. As written, both the time and space summaries in the abstract rely on an unstated condition on t.","section":"Section 4.2, Space complexity"}],"minor_comments":[{"comment":"The line 'for λ2 times' should read 'for λ² times'; the superscript appears to have been lost in typesetting.","section":"Algorithm 3, line 7"},{"comment":"The roadmap says 'Section 1 reviews related work,' but related work is presented in Section 2; the cross-reference is off by one.","section":"Section 1, last paragraph"},{"comment":"The entry in the n column for Birch1 appears malformed ('10 5'); please clarify the intended sample size.","section":"Table 1, Birch1 row"},{"comment":"The captions report \\bar{t} as the average number of components; please add a note that these averages are over the same 10 random runs used for the error and time metrics, since the random initialization affects both t and the final results.","section":"Figures 5 and 6, captions"},{"comment":"The recommendation 'keep λ ≤ k' is supported only by the displayed datasets; adding a sentence about the range of n and d for which this guideline is intended would improve its practical utility.","section":"Section 6, hyperparameter guidelines"}],"recommendation":"major_revision","confidential_remarks":"The main issue is the t-dependence in the complexity analysis. If the authors can either prove a bound on t for a relevant class of inputs or present experiments showing that t remains O(√n) across a wide range of n, I would be willing to revisit the paper. The current version also leans on a heuristic ANN method's typical-case performance without clearly separating worst-case guarantees from empirical behavior, so the framing should be adjusted accordingly. The self-citation [16] is not problematic by itself, but the authors should double-check that it is the most appropriate reference for the WSPD complexity statement."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know about 2507.14261. The empirical case is genuinely good: 14 datasets, mean relative error 0.44%, speedups up to 1000x, and the neighbor-of-neighbor refinement loop is a real addition over MFC and FISHDBC. The theory section, however, has a concrete undercount, and the headline O(dn log n) is not proven as written.\n\nThe issue is exactly what the stress-test note says. Algorithm 3 adds λ edges for every component pair, so the inter-component edge set is Θ(t²λ), not Θ(tλ). That mistake propagates: Section 4.1 writes the Kruskal edge count as O(kn + tλ), and the refinement loop as processing O(tλ) edges. With the correct count, both become O(kn + t²λ), and the simplified O(dn log n) requires t = O(√n) for constant k and λ. The paper only asserts t ≪ n \"in practice,\" which is not a theorem and not tied to any data property. Their own figures show t collapses to 1 or a handful for their benchmarks once k is large enough, so the empirical regime may satisfy the bound, but it is never stated or tested as a condition. Section 4.2's space claim of O(tλ²) is similarly odd, since the algorithm actually keeps t²λ edges after selection.\n\nOther soft spots are minor but worth listing. No code is provided, so repro is hard. The reported times are means over 10 runs with no variance, which matters for a randomized algorithm. And the relationship to the authors' own earlier work (reference [16]) is not clarified; a reader cannot tell how much of the three-phase pipeline is already there. I do not see a circularity problem: the error is measured against an independent exact MST implementation, and hyperparameter tuning is standard.\n\nThis is a useful paper for practitioners who need a fast approximate MST for high-dimensional data and are willing to treat the complexity analysis as heuristic. The theory reader should be cautious. It deserves a serious referee, but the referee should demand a corrected complexity accounting, an explicit condition on t, and preferably a code release. My recommendation: send it to review, conditional on those fixes.\n\nFor your reading group: maybe. It is a decent engineering contribution, but not a conceptual breakthrough.","headline":"Solid practical approximate-MST paper with strong experiments, but its central O(dn log n) claim rests on an unstated and unverified bound on the number of components.","tokens_in":15348,"tokens_out":2368,"would_cite":true,"duration_ms":28473,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims FAMST constructs approximate minimum spanning trees in near-linear time with mean relative error 0.44 percent, making exact-scale MST analysis feasible on large high-dimensional datasets.","keywords":["approximate minimum spanning tree","nearest neighbor graph","high-dimensional data","large-scale data","graph refinement","Kruskal's algorithm","MST approximation"],"falsifier":"Build a dataset whose $k$-nearest-neighbor graph breaks into many components, for instance $n$ points arranged into $t \\approx n^{3/4}$ well-separated clusters, run FAMST with fixed $k$ and $\\lambda$, and measure the wall-clock time spent by the inter-component sampling step. If that time grows like $t^2\\lambda$ rather than staying within a near-linear envelope, the simplified $O(dn\\log n)$ statement fails on that input.","tokens_in":14356,"feed_emoji":"🌲","tokens_out":10690,"duration_ms":110723,"temperature":0.7,"pith_summary":"FAMST sets out to make minimum spanning trees computable at scales where exact algorithms stop: millions of points in hundreds or thousands of dimensions. It replaces the complete distance graph with a sparse approximate-nearest-neighbor graph, reconnects disconnected components by sampling candidate edges between component pairs, and then iteratively shortens those inter-component edges through local neighborhood exploration before Kruskal's algorithm extracts the tree. The paper claims this pipeline runs in $O(dn\\log n)$ time and $O(dn+kn)$ space, and reports a mean relative error of 0.44 percent with speedups of up to 1000 times over exact Euclidean MST on large high-dimensional benchmarks. If true, MST-based clustering, outlier detection, and manifold learning become practical at scales previously considered infeasible.","feed_headline":"Near-linear MST hits 0.44 percent mean error","feed_subtitle":"Sparse neighbor graphs plus smart reconnection make MST practical at million-point scale.","key_machinery":"The load-bearing mechanism is the iterative inter-component edge refinement loop: for every edge $(u,v)$ joining components $C_i$ and $C_j$, it searches the neighbors of $u$ inside $C_i$ and the neighbors of $v$ inside $C_j$, and whenever a neighboring vertex yields a shorter crossing distance it slides the edge endpoint to that vertex. Repeating this until no edge changes turns cheap random bridges between components into shorter, more MST-like bridges, which is what keeps the approximation error low. The sparse ANN graph provides the local neighborhoods, and the randomized component-pair sampling in Algorithm 3 provides the initial bridges; together they avoid all-pairs distance computation.","core_discovery":"On the paper's own terms, the discovery is that a three-phase pipeline can produce near-exact MSTs from a sparse neighborhood graph. Starting from a directed $k$-nearest-neighbor graph, FAMST symmetrizes it, finds its connected components, and for each pair of components randomly samples $\\lambda^2$ candidate edges and keeps the $\\lambda$ shortest. It then repeatedly examines, for each inter-component edge, the neighbors of both endpoints within their own components and replaces the edge with a shorter crossing edge when such a neighbor exists, until no replacement occurs. The resulting connected sparse graph is handed to Kruskal's algorithm, yielding an approximate MST whose total weight in the reported experiments is typically within 0.44 percent mean relative error, with median error 0.07 percent. The claimed complexity is near-linear in the number of points and dimensions, a qualitative improvement over the $O(n^2)$ cost of exact complete-graph methods.","pith_inferences":["Because ANN construction dominates measured runtime and FAMST treats that phase as a replaceable module, swapping in faster GPU-accelerated nearest-neighbor search would likely yield an almost proportional end-to-end speedup.","The refinement loop is generic: any initial sparse graph with disconnected components could be fed through the same endpoint-neighborhood shortening before MST extraction, so the technique may serve as a post-processor for other approximate graph-forest methods.","A natural next step would be to prove a bound on the number of refinement iterations $r$; the near-linear complexity claim currently treats $r$ and the component count $t$ as small constants observed in practice."],"forward_implications":["MST-based clustering, outlier detection, and manifold learning become usable on datasets with millions of points and thousands of dimensions, where complete-graph methods previously ran out of time or memory.","Because the sparse graph has $O(kn)$ edges rather than $O(n^2)$, memory use grows linearly with $n$ and $d$, so MST analysis can run on ordinary workstations.","Several reported near-zero errors (0.049 percent on MNIST, 0.045 percent on Shuttle) suggest the approximation is often indistinguishable from the exact MST in downstream analyses.","The experiments support concrete hyperparameter guidance: keep $\\lambda \\leq k$, choose $k$ around 10 for a balance of accuracy and speed, and expect ANN construction rather than refinement to dominate the runtime."],"supporting_citations":[{"why":"Supplies the approximate-nearest-neighbor graph primitive on which Phase 1 is built; its typical runtime is what the claimed near-linear time leans on.","marker":"[21]"},{"why":"Introduces the neighbor-graph construction strategy that the Phase 1 implementation follows.","marker":"[20]"},{"why":"Gives the $O(k^2 d n \\log n)$ typical runtime pattern cited for the ANN construction step.","marker":"[24]"},{"why":"Provides the exact dual-tree Euclidean MST baseline and motivates the need to avoid tree-based search in high dimensions.","marker":"[3]"},{"why":"Defines the Metric Forest Completion baseline and the inter-component connection problem that FAMST addresses directly.","marker":"[4]"},{"why":"Represents the kNN-graph-based MST approach that does not guarantee connectivity, against which FAMST's connection phase is a contrast.","marker":"[23]"}],"fun_headline_variants":["Approximate MST hits 1000x speedup, 0.44% error","Near-linear MST for millions of points, high-dim data","Fast approximate MST: near-linear time, small error","MST at scale: 1000x faster with minimal error","FAMST: near-linear MST for large-scale data"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The claimed $O(dn\\log n)$ bound holds only if the number of disconnected components $t$ stays small enough that the $O(t^2\\lambda)$ work in the inter-component sampling stays within the near-linear budget, and if the approximate-nearest-neighbor construction finishes in its typical rather than worst-case time.","fun_headline_variants_meta":{"raw":{"variants":["Approximate MST hits 1000x speedup, 0.44% error","Near-linear MST for millions of points, high-dim data","Fast approximate MST: near-linear time, small error","MST at scale: 1000x faster with minimal error","FAMST: near-linear MST for large-scale data"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000308,"raw_usage":{"total_tokens":1764,"prompt_tokens":951,"completion_tokens":813,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":567,"completion_tokens_details":{"reasoning_tokens":725}},"tokens_in":567,"tokens_out":813,"duration_ms":8029,"temperature":1.0,"reasoning_tokens":725,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T16:15:10.040943+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Build a dataset whose $k$-nearest-neighbor graph breaks into many components, for instance $n$ points arranged into $t \\approx n^{3/4}$ well-separated clusters, run FAMST with fixed $k$ and $\\lambda$, and measure the wall-clock time spent by the inter-component sampling step. If that time grows like $t^2\\lambda$ rather than staying within a near-linear envelope, the simplified $O(dn\\log n)$ statement fails on that input.","supporting_citations":[{"cited_title":"Pynndescent: A python nearest neighbor descent for approximate nearest neighbors,","cited_arxiv_id":null,"evidence_quote":"Supplies the approximate-nearest-neighbor graph primitive on which Phase 1 is built; its typical runtime is what the claimed near-linear time leans on."},{"cited_title":"Efficient k-nearest neighbor graph construction for generic similarity measures,","cited_arxiv_id":null,"evidence_quote":"Introduces the neighbor-graph construction strategy that the Phase 1 implementation follows."},{"cited_title":"K-Nearest Neighbor Approximation Via the Friend-of-a-Friend Principle","cited_arxiv_id":"1908.07645","evidence_quote":"Gives the $O(k^2 d n \\log n)$ typical runtime pattern cited for the ANN construction step."},{"cited_title":"Fast euclidean minimum spanning tree: algorithm, analysis, and applications,","cited_arxiv_id":null,"evidence_quote":"Provides the exact dual-tree Euclidean MST baseline and motivates the need to avoid tree-based search in high dimensions."},{"cited_title":"Approximate Tree Completion and Learning-Augmented Algorithms for Metric Minimum Spanning Trees","cited_arxiv_id":"2502.12993","evidence_quote":"Defines the Metric Forest Completion baseline and the inter-component connection problem that FAMST addresses directly."},{"cited_title":"Mistree: a python package for constructing and analysing minimum spanning trees,","cited_arxiv_id":null,"evidence_quote":"Represents the kNN-graph-based MST approach that does not guarantee connectivity, against which FAMST's connection phase is a contrast."}],"review_version":1}