{"id":"c0bb341e-28a7-4233-8362-453a66999a2f","arxiv_id":"2501.05529","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A user-chosen look-ahead parameter turns the expensive stable deformation-based merge tree edit distance into a family of polynomial-time approximations.","lead":"This paper introduces a faster way to compute a stable distance between merge trees, structures that describe how features of a scalar field connect. The new method adds a user-tunable 'look-ahead' knob that trades run time for accuracy, making previously impractical comparisons feasible on medium-sized data.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 2's claimed exact equivalence to the restricted look-ahead edit distance is asserted without proof; a brute-force exact check on small trees would verify or falsify it.","rationale":"The reader's weakest_assumption identifies exactly the gap I consider most load-bearing: the unproven equivalence between the recursive algorithm and the stated look-ahead edit-distance model. This is not a manufactured concern; the paper itself frames the model as a contribution and uses it to explain interpolation and monotonicity, so a counterexample would directly undermine the central claim. The concern is addressable: because the algorithm is implemented and datasets are public, one can compute δh and a brute-force restricted distance on small trees and compare. The paper has real independent support: the implementation is provided, the runtime scaling experiments are reproducible, and the complexity analysis is plausible. The auction-solver approximation is a secondary issue because it affects accuracy but not the structural identity of δh, and the bounded-degree assumption for the complexity bound is explicitly stated as a practical assumption. I therefore do not move the verdict; CONDITIONAL remains appropriate pending the proposed validation.","tokens_in":26596,"tokens_out":14594,"duration_ms":140782,"concrete_test":"Run an exact branch-and-bound or dynamic-programming solver for the restricted look-ahead-h edit distance (min cost over edit sequences with no block of more than h consecutive edge contractions) on all pairs of merge trees with up to 8 vertices from the TOSCA/MVK preprocessed data, for h=1,2,3, and compare every value to δh from the provided TTK implementation. Any mismatch shows Algorithm 2 does not compute the Section 4.3 model.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central theoretical claim in Section 4.3 is that δh(T1,T2) equals the cost of an optimal edit sequence in which deletions/insertions never contract more than h consecutive edges, with the recursion of Algorithm 2 computing this value exactly. This equivalence is stated only intuitively ('We restrict to an intuitive description'), and no proof appears in the main text or the appendix excerpt. The recursion adds a single OptCollapse case to the path-mapping DP, and correctness requires showing that every restricted edit sequence can be reorganized so that all non-leaf deletions occur as strongly connected edge sets inside the look-ahead region at the recursion level where they are considered, and that the assignment over the resulting leaf subtrees finds the optimal such reorganization. This is nontrivial for a tree edit distance with deletions at arbitrary depths; analogous DP correctness arguments are usually proved by induction over the edit sequence. If the equivalence fails, δh is not the advertised restricted deformation distance, the monotonicity and h=depth interpolation properties are unsupported, and the experimentally observed convergence toward δE could be coincidental for these four datasets rather than structural. The runtime claim is less at risk because it only requires the algorithm to terminate in the stated complexity, which it does; the mathematical identity of the computed distance is the load-bearing piece.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a parameterized heuristic for computing a stable edit distance on merge trees. The authors extend the polynomial-time path mapping distance with a user-chosen look-ahead parameter h, adding a recursive 'OptCollapse' case (Algorithm 1 and line 22 of Algorithm 2) that contracts strongly connected edge sets within distance h of the current nodes. They claim that the resulting distance δh interpolates between the path mapping distance (h=0) and the unconstrained deformation-based edit distance (h=depth), that the algorithm runs in time polynomial in the input size for fixed h (FPT-like), and that small h values produce distance matrices quantitatively close to the exact NP-complete distance while reducing runtime from days to seconds. The paper reports experiments on four datasets (TOSCA, MVK, ionization front, vortex street), including convergence measurements against the exact deformation distance and qualitative/quantitative stability assessments.","tokens_in":26781,"tokens_out":4564,"duration_ms":46806,"significance":"The practical contribution is substantial: if the algorithmic claims are correct, the paper opens a route to using a stable, NP-complete merge tree distance on trees with dozens to hundreds of nodes, whereas the previous exact MIP implementation is infeasible beyond about 30 vertices. The paper provides an open-source implementation and reproducible experiments, and the convergence numbers in Table 1 are compared against the independent exact distance δE from prior work, so there is no circularity in the experimental evaluation. The central theoretical claim, however—that Algorithm 2 computes the optimum over the described class of look-ahead edit sequences—is asserted without proof, and the experiments use an approximate auction solver for the inner assignment problems, leaving the connection between the implemented heuristic and the claimed distance model unquantified. The significance hinges on that theoretical gap, which is fixable in principle but is currently load-bearing.","major_comments":[{"comment":"The central claim that δh equals the cost of an optimal edit sequence whose deletions/insertions never contract more than h consecutive edges is not proved. The text explicitly says 'We restrict to an intuitive description,' and neither the main text nor the appendix provides an induction or any formal equivalence argument. To support the claim one must show that (a) every restricted edit sequence can be reorganized so that all non-leaf deletions occur as strongly connected edge sets within the look-ahead region at the recursion level where they are handled, and (b) the assignment over the resulting leaf subtrees in line 22 (and lines 7–9 of Algorithm 1) finds the optimum over all such reorganizations. Without this, the advertised properties—monotonicity in h, δh=δ0 at h=0, and δh=δE when h equals tree depth—are not established for the computed function. Since these properties are stated in the abstract and in Section 4.3 as the paper's main theoretical contribution, this missing proof is load-bearing.","section":"Section 4.3, 'Edit Operation Model'; Algorithm 2 line 22"},{"comment":"The implementation uses the approximate auction solver for the assignment instances, and the paper acknowledges that this yields a heuristic solution, while the theoretical runtime bounds and the distance characterization implicitly assume exact assignment via the Hungarian method. No quantification of the approximation error is provided. Consequently, the convergence values in Table 1 and the stability comparisons are for the auction-based heuristic, not necessarily for the exact recursion defined by δh. The authors should either modify the experiments to use an exact assignment solver (the trees are small, so this may be feasible), or add a validation of the auction solver on the actual instances, e.g., comparing auction and Hungarian on a representative subset and reporting the frequency and magnitude of suboptimality.","section":"Section 4.2, 'Parallelization & Optimal Assignment Algorithm'"},{"comment":"The claimed fixed-parameter running time is not supported by a concrete upper bound. The text defines f(h) as f′(h)^2 · d^{3h}, where f′(h) is described as the number of d-ary trees of depth h, and then states that no closed form is known. This leaves the exponential dependence on h essentially unspecified: without an upper bound on f′(h) (e.g., f′(h) ∈ O(d^{O(h)}) or a double exponential), the statement 'polynomial in the size of the input but exponential in the look-ahead value' is not a rigorous complexity result. Additionally, the claim that the dynamic programming optimization reduces the runtime from n^4·f(h) to n^4 + n^2·f(h) is stated without a detailed argument; since the recursion's base values δh still depend on the parent-edge choices p1,p2, the memoization of OptCollapse alone does not obviously eliminate the depth factors from the first term. Please provide a precise accounting of all terms in the runtime bound.","section":"Section 4.3, 'Complexity'; Equation (1)"}],"minor_comments":[{"comment":"Typo: 'consectuive' should be 'consecutive'.","section":"Section 4.3"},{"comment":"Typo: 'Alogirthm 2' should be 'Algorithm 2'.","section":"Appendix A.1"},{"comment":"Typo: 'integrate the the adapted module' should be 'integrate the adapted module'.","section":"Appendix F"},{"comment":"The phrase 'within look-ahead h of v' is initially defined with the condition depthT(x) − depthT(v) <= h, but it is clearer to explicitly state that the edge (x,y) is directed with x being the parent of y; please add a small note to avoid ambiguity between the two endpoints.","section":"Section 3, definition of SCESh"},{"comment":"The text says the runtime grows exponentially at first but then saturates; a logarithmic y-axis would make this clearer, and the hypothesis about the asymptotics taking effect late is informal. Consider adding a brief explanation of saturation in terms of tree depth.","section":"Section 5.5, 'Look-ahead Scaling'"}],"recommendation":"major_revision","confidential_remarks":"The paper's experimental work and reproducibility are strong, and the idea of a look-ahead parameter interpolating between the path mapping and the full deformation distance is attractive. The blocking issue is the missing proof of the equivalence between the recursion and the claimed edit-sequence model; without it, the main abstract and Section 4.3 claims are not supported. This is a correctness gap rather than a disagreement with consensus, and I believe it is addressable in revision by inserting a formal induction proof or by explicitly rephrasing the claims as a conjecture and reframing the paper as a heuristic study. The auction-solver issue is also important for the experimental interpretation. I recommend major revision rather than rejection because the core algorithm and data are valuable and the missing pieces are concrete rather than fatal."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper introduces a look-ahead parameter for the deformation-based edit distance on merge trees, defining a family of distances δh that interpolate between the path mapping distance (h=0) and the unconstrained deformation distance (h=depth). That is genuinely new, and the experimental payoff is real: on TOSCA and MVK, small look-ahead values get within a couple of percent of the exact NP-complete distance while cutting runtime from days to seconds. The implementation is in TTK with source code provided, and the experiments are on established datasets with public preprocessing. This is a useful enabling tool for anyone who needs stable merge tree distances on medium-sized trees.\n\nThe main soft spot is exactly where the stress-test note points. Section 4.3 says δh equals the cost of an optimal edit sequence that never contracts more than h consecutive edges, but this is asserted, not proved. The recursion in Algorithm 2 adds an OptCollapse case and the text says \"we restrict to an intuitive description\"—which is honest but leaves a load-bearing claim unsupported. Monotonicity and the h=depth interpolation are argued from that model, so if the model is wrong those properties are not established. The good news is that this is fixable: either provide a proper induction proof that the recursion is exact for that restricted edit class, or formally verify it, or—simplest—downshift the claim and present δh as an algorithmically defined distance with empirical convergence to δE. The experiments would still stand.\n\nTwo smaller issues. The runtime tables use the auction solver for the assignment subproblems, which is heuristic; the reported convergence to δE therefore includes an unquantified approximation. That is minor because the comparison is against the exact MIP solution, but a few runs with the Hungarian method would confirm the numbers. And the complexity bound assumes bounded-degree trees and uses a rough exponential factor f(h); the authors already acknowledge this is a crude estimate, so it is not a serious flaw.\n\nOverall, the paper is an honest, well-scoped algorithmic contribution with convincing experiments. The missing proof is the one real gap, and it is addressable. I would send this to peer review and ask the authors to either prove the characterization or soften it. If they do, this is a solid paper for TVCG or a TopoInVis venue.","headline":"A useful and well-engineered heuristic for the NP-hard merge tree edit distance, with strong experiments; the central formal claim about what the heuristic computes is stated without proof.","tokens_in":27324,"tokens_out":2337,"would_cite":true,"duration_ms":25663,"reading_group":"yes","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 that a user-chosen look-ahead parameter makes the NP-complete deformation-based merge tree edit distance computable in polynomial time for fixed look-ahead, with small values closely approximating the exact distance on…","keywords":["merge trees","edit distance","deformation-based distance","look-ahead parameter","fixed-parameter tractability","saddle swaps","stability","topological data analysis"],"falsifier":"Take all pairs of labeled merge trees with up to ten nodes, compute δh with h=1 and h=2 using the open-source implementation, and compare with the exact δE obtained by brute-force enumeration of edit sequences. If any pair has δh > δE while the optimal sequence uses no more than h consecutive deletions or insertions, then the recursion fails to capture the advertised edit model.","tokens_in":26326,"feed_emoji":"⚡","tokens_out":5481,"duration_ms":50704,"temperature":0.7,"pith_summary":"This paper aims to make the stable, deformation-based edit distance for merge trees practical. That distance, which correctly handles saddle swaps, is NP-complete, and the exact solver becomes infeasible beyond about 30 vertices; the fast path mapping distance is computable in polynomial time but misses saddle swaps. The authors propose a heuristic that adds a user-chosen look-ahead parameter h to the path mapping recursion: with h=0 it reduces to path mapping, with h equal to tree depth it becomes the full deformation distance, and for intermediate h it runs in time polynomial in tree size and exponential only in h. Experiments on four established datasets show that small values (2 to 4) already produce distance matrices nearly identical to the exact distance, while cutting computation from five days to seconds.","feed_headline":"Look-ahead parameter turns an NP-hard tree distance computable in seconds","feed_subtitle":"Small look-ahead values match the exact stable distance on real data while cutting runtimes from days to seconds.","key_machinery":"The load-bearing object is the look-ahead recursion itself: the path mapping dynamic program is extended by a fourth case, OptCollapse, which enumerates all strongly connected edge sets within look-ahead h below the nodes being matched, contracts them, and then computes the optimal assignment between the remaining leaf subtrees using the Hungarian or auction solver. The strongly connected edge sets, denoted SCESh, capture the consecutive inner-edge deletions that effect saddle swaps. This machinery is what makes the running time O($n^{4}$ + $n^{2}$ f(h)), polynomial in input size with an exponential factor in h.","core_discovery":"The central claim is that the recursively defined distance δh, which allows collapsing strongly connected sets of up to h consecutive edges below matched nodes before solving an optimal assignment between the resulting subtrees, is a valid interpolation between the path mapping distance δ0 and the unconstrained deformation distance δE. The paper argues that such collapses correspond exactly to edit sequences whose deletions and insertions never involve more than h consecutive edges, so δh is a restricted deformation distance; as h grows to tree depth, every deletion is allowed and δh equals δE. On the TOSCA, MVK, ionization front, and vortex street datasets, the heuristic converges quickly to δE, with mean relative differences of 0.8% (TOSCA) and 2.7% (MVK) at h=2 and below 1% by h=3 to 6, while matrix runtimes drop from days to seconds.","pith_inferences":["The observed convergence suggests that saddle swaps in real scalar fields are usually shallow and local; if true, small look-ahead values should suffice broadly, but this is a conjecture beyond the paper's evidence.","A formal proof that δh equals the cost of optimal edit sequences with at most h consecutive deletions or insertions would turn the heuristic into an exact parameterized distance; the paper only sketches the model.","The collapse enumeration could likely be replaced by dynamic programming over tree shapes, which might remove the exponential dependence on h for bounded-degree trees; this is not proposed by the authors.","Combining δh with ε-preprocessing may give a monotone stability parameter, since the paper notes ε-preprocessing alone is not monotone; this combination is mentioned as future work."],"forward_implications":["For any fixed look-ahead h, the runtime is polynomial in the size of the merge trees, so stable distance matrices become feasible for trees with up to roughly 100 vertices.","δh is monotone in h: increasing the look-ahead can only reduce the distance, so a user can push h as high as computational budget allows.","At h=0 the method reproduces the path mapping distance, and at h=depth it reproduces the unconstrained deformation distance, giving a continuous spectrum of trade-offs.","On the tested datasets, look-ahead values of 2 to 4 reproduce the exact stable distance matrices closely enough for clustering and periodicity detection, and the resulting t-SNE embeddings show the expected smooth periodic structure.","The speedup enables stable comparisons on data with low simplification thresholds, where the exact solver cannot run at all."],"supporting_citations":[{"why":"Defines the deformation-based edit distance, proves NP-hardness, and provides the MIP solver whose infeasibility motivates the heuristic.","marker":"[40]"},{"why":"Defines the path mapping distance and its O(n^4) recursive dynamic program that the look-ahead extension modifies.","marker":"[41]"},{"why":"Supplies the underlying unordered tree edit model (relabel, delete, insert) that merge tree edit operations adapt.","marker":"[50]"},{"why":"Auction algorithm used to solve the assignment instances in the recursion, chosen for speed over optimality.","marker":"[3]"},{"why":"Hungarian method, the optimal assignment solver that determines the cubic factor in the theoretical runtime bound.","marker":"[24]"},{"why":"Defines the merge tree edit distance, an unstable baseline used for comparison in experiments.","marker":"[34]"},{"why":"Defines the merge tree Wasserstein distance, another baseline and the source of ε-preprocessing.","marker":"[28]"}],"fun_headline_variants":["Look-ahead parameter speeds NP-hard merge tree distance","Trading accuracy for speed: look-ahead fix for merge tree distance","Merge tree distance made practical with look-ahead heuristic","New parameter speeds up stable merge tree edit distance","Look-ahead trades accuracy for speed on NP-hard tree distance"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that every edit sequence whose deletions and insertions never touch more than h consecutive edges can be reproduced by the three original recursive cases plus the collapse of strongly connected edge sets within look-ahead h; the paper states this model intuitively rather than proving the equivalence.","fun_headline_variants_meta":{"raw":{"variants":["Look-ahead parameter speeds NP-hard merge tree distance","Trading accuracy for speed: look-ahead fix for merge tree distance","Merge tree distance made practical with look-ahead heuristic","New parameter speeds up stable merge tree edit distance","Look-ahead trades accuracy for speed on NP-hard tree distance"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000568,"raw_usage":{"total_tokens":2623,"prompt_tokens":816,"completion_tokens":1807,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":432,"completion_tokens_details":{"reasoning_tokens":1726}},"tokens_in":432,"tokens_out":1807,"duration_ms":12310,"temperature":1.0,"reasoning_tokens":1726,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T21:12:52.658399+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take all pairs of labeled merge trees with up to ten nodes, compute δh with h=1 and h=2 using the open-source implementation, and compare with the exact δE obtained by brute-force enumeration of edit sequences. If any pair has δh > δE while the optimal sequence uses no more than h consecutive deletions or insertions, then the recursion fails to capture the advertised edit model.","supporting_citations":[{"cited_title":"Zhang, R","cited_arxiv_id":null,"evidence_quote":"Supplies the underlying unordered tree edit model (relabel, delete, insert) that merge tree edit operations adapt."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Hungarian method, the optimal assignment solver that determines the cubic factor in the theoretical runtime bound."}],"review_version":1}