{"id":"5b834d27-e368-4a9d-b0bb-1032718d1882","arxiv_id":"1908.08183","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For unrooted phylogenetic networks, the new agreement and endpoint agreement distances are metrics that bound the TBR-distance by a factor of two and the PR-distance by a factor of three.","lead":"This paper introduces agreement graphs that measure how much two unrooted phylogenetic networks agree, and proves the resulting agreement distance stays within a factor of two of the harder-to-compute TBR distance. It gives researchers a simpler metric for comparing evolutionary networks and a basis for future approximation algorithms.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Endpoint ordered agreement embeddings are asserted by analogy and outline only; the EAD metric and Theorem 5.10 depend on them, so a full proof or a counterexample is required.","rationale":"The reader's weakest assumption identifies precisely the place where the manuscript explicitly supplies only an outline and a reference to an analogous proof. I agree this is the most load-bearing missing support. The main TBR bound in Theorem 5.7 is otherwise supported by a full proof of Lemma 3.1 and by the detailed constructions in Lemmas 5.5 and 5.6; the reverse phase of Lemma 5.6 is terse and would benefit from being made explicit, but I do not see a concrete defect in its counting or in its use of ordered agreement embeddings. The typo in Lemma 5.3 (the sum is written as dAD(T,T') + dAD(T,N)) is clearly a slip in an auxiliary lemma and is not load-bearing for Theorem 5.7 or Corollary 5.8. The EAD concern matters because Corollary 4.2 and Theorem 5.10 both build on ordered endpoint agreement embeddings, and the endpoint setting genuinely adds sprouts inside agreement subgraphs, so the transfer from the rooted case is not automatic. If the missing proof can be completed, the results stand; if a counterexample exists, the EAD metric and the PR-factor bound fail. The current conditional verdict is therefore appropriate; my read does not change it.","tokens_in":19541,"tokens_out":16546,"duration_ms":167280,"concrete_test":"Complete the missing lemma in the unrooted setting by adapting the induction in Lemma 3.1, explicitly handling sprouts that lie inside endpoint agreement subgraphs, and check that neither enforcing the first ordered-embedding property nor reordering disagreement edges destroys the other property or the edge cover. As a computational complement, enumerate all pairs of proper binary networks on n <= 5 leaves, enumerate their endpoint agreement graphs, and search by embedding changes for a pair whose MEAG admits no ordered agreement embedding into both networks. A counterexample would refute Corollary 4.2; if all instances pass and the proof completes, the concern reduces to a presentation gap.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 4 does not contain a proof that ordered agreement embeddings exist for endpoint agreement graphs. The text says the proof works analogously to Theorem 3.1 and Lemma 3.2 of Klawitter (2019) and gives a two-sentence outline. This is load-bearing: Corollary 4.2 (EAD is a metric) is obtained from Proposition 4.1, whose second inequality requires fixing ordered agreement embeddings of a MEAG into both N and N'; Theorem 5.10 also fixes such embeddings to drive the PR construction. The unrooted endpoint setting differs from the cited rooted lemma in a relevant way: endpoint agreement subgraphs may themselves carry sprouts, so the condition that no sprout of an agreement subgraph is attached to a disagreement edge interacts with the ordering condition on disagreement edges. The outline (apply embedding changes to sprouts attached to disagreement edges, then reorder E_i attached to E_j with j > i) does not demonstrate that both conditions can be enforced simultaneously while preserving the agreement-embedding coverage. If such embeddings sometimes fail to exist, dEAD may not satisfy the triangle inequality and the upper bound dPR <= 3 dEAD in Theorem 5.10 is unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces maximum agreement graphs (MAGs) and maximum endpoint agreement graphs (MEAGs) for unrooted, binary, proper phylogenetic networks, generalizing maximum agreement forests from trees. It defines the agreement distance dAD and the endpoint agreement distance dEAD, proves that both are metrics, and studies their relations to the TBR and PR distances. The main results are dAD(N,N') ≤ dTBR(N,N') ≤ 2 dAD(N,N') (Theorem 5.7), the resulting bound dAD ≤ dPR ≤ 4 dAD (Corollary 5.8), and dEAD ≤ dPR ≤ 3 dEAD (Theorem 5.10), together with dAD ≤ dEAD ≤ 2 dAD (Proposition 5.9). The paper also shows that dAD coincides with the TBR-distance on unrooted trees and on tree/network pairs, and gives an example where the two distances differ for networks. The overall contribution is a constant-factor approximation framework for rearrangement distances on unrooted phylogenetic networks.","tokens_in":19751,"tokens_out":16146,"duration_ms":154708,"significance":"If the results hold, this is a meaningful step: it provides the first constant-factor bounds relating agreement-type distances to TBR and PR distances on unrooted networks, and the chain dAD ≤ dPR ≤ 4 dAD gives a single proxy for two rearrangement metrics. The constructions in Lemma 5.5 and Lemma 5.6 are detailed and nontrivial, and the paper is generally careful in building on published results rather than re-deriving them. However, the endpoint version of ordered agreement embeddings is only asserted by analogy with prior work and a short outline, and this lemma is load-bearing both for the metric property of dEAD and for the upper bound in Theorem 5.10. The main ideas are credible, but the manuscript is not fully vetted until that gap is closed.","major_comments":[{"comment":"The existence of ordered agreement embeddings for endpoint agreement graphs is asserted without a complete proof. The text says the proof works analogously to Theorem 3.1 and Lemma 3.2 of Klawitter (2019) and gives a two-sentence outline. This existence is load-bearing: Corollary 4.2 obtains the metric property of dEAD from Proposition 4.1, whose reverse inequality fixes ordered embeddings of a MEAG into N and N′, and Theorem 5.10 fixes such embeddings and uses the ordering of disagreement edges when adding edges by PR+. The outlined argument does not show that the two conditions—no sprout of an agreement subgraph attached to a disagreement edge, and the ordering condition Ej may be attached to Ei only for i ≤ j—can be enforced simultaneously in the unrooted endpoint setting, where agreement subgraphs may themselves carry sprouts. An embedding change that detaches a sprout from a disagreement edge can alter which disagreement edges are attached to which, and the interaction with the ordering condition is not addressed. I request a full proof of the existence of ordered agreement embeddings for endpoint agreement graphs, or an explicit reduction to the rooted lemma that accounts for sprouts in agreement subgraphs.","section":"Section 4, ordered agreement embedding; used in Proposition 4.1 and Theorem 5.10"},{"comment":"The converse direction of Lemma 5.3 contains the displayed inequality dAD(T,N) ≥ dAD(T,T′) + dAD(T,N) = dTBR(T,N). The middle term dAD(T,N) makes the inequality self-referential and cannot be correct; the intended second summand is presumably dAD(T′,N), which equals r when T′ is displayed by N. As printed, the proof of the lower bound dAD(T,N) ≥ dTBR(T,N) is invalid, although the surrounding argument suggests a straightforward repair by replacing the erroneous term and justifying why the ordered embedding of G into N yields an agreement graph of T and T′ with k−r disagreement edges. Please correct the equation and expand this step.","section":"Section 5, Lemma 5.3"}],"minor_comments":[{"comment":"Several cross-references use the wrong kind of label: 'Theorem 3.1' should be Lemma 3.1, 'Theorem 2.1' should be Observation 2.1, 'Theorem 3.3' should be Proposition 3.3, 'Theorem 5.2' should be Lemma 5.2, and 'Theorem 4.1' should be Proposition 4.1. Please harmonize the references.","section":"Throughout"},{"comment":"The outline begins 'Starting with an agreement embedding of G into N′', but the object being embedded is the endpoint agreement graph, which has been called H; the symbol G is not defined in this paragraph.","section":"Section 4, proof sketch after the definition of ordered agreement embedding"},{"comment":"The text says 'maximum endpoint agreement graphs (MAEGs)', whereas the body of the paper consistently uses the abbreviation MEAG. Please make the abbreviation uniform.","section":"Concluding remarks"},{"comment":"The sentence 'Since ¯v is either a degree vertex or a labelled leaf' should state the degree explicitly, presumably 'degree-three vertex'; as written it is ambiguous.","section":"Section 5, proof of Proposition 5.9"},{"comment":"The phrase 'maximum agreement graphs as a generalisations' should be 'as a generalization' or 'as generalizations'.","section":"Abstract"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a solid, well-scoped paper that introduces a useful new notion and proves the right bounds. It won't change how everyone thinks about phylogenetics, but it deserves a serious referee and probably a round of revision.\n\nWhat is actually new: maximum agreement graphs and maximum endpoint agreement graphs for unrooted proper binary networks, plus the constant-factor comparisons to TBR and PR distances — Theorem 5.7 (dAD ≤ dTBR ≤ 2 dAD) and Theorem 5.10 (dEAD ≤ dPR ≤ 3 dEAD). The Figure 12 example separating AD from TBR is nice, and the NP-hardness result follows cleanly from the tree case. The writing is clear, the citation pattern is normal (the borrowings from Klawitter 2019 are published and legitimate), and most of the proofs are detailed.\n\nSoft spots, in proportion. There is a typo in the proof of Lemma 5.3: the displayed inequality dAD(T,N) ≥ dAD(T,T') + dAD(T,N) is self-referential and can't be what the author meant. As printed it proves nothing; presumably it should be dAD(T,T') + dAD(T',N) or something equivalent. That is a fixable typo, but it is in a lemma used later.\n\nThe bigger issue is Section 4. Ordered agreement embeddings for endpoint agreement graphs are asserted to exist by analogy with Theorem 3.1 and Lemma 3.2 of Klawitter (2019), with only a two-sentence outline. This is load-bearing: the proof that EAD is a metric (Corollary 4.2, via Proposition 4.1) and the upper bound in Theorem 5.10 both assume ordered embeddings. The unrooted endpoint setting differs from the rooted one in a real way: agreement subgraphs can have sprouts, so the condition that no sprout of an agreement subgraph attaches to a disagreement edge interacts with the ordering condition on disagreement edges. The outline does not show both can be enforced simultaneously. I don't think the claim is false — it probably goes through with a real argument — but a referee should require a full proof or a counterexample.\n\nVerdict: give it a serious peer review. It is a genuine extension with useful bounds, not a paradigm shift. The soft spots are fixable, not fatal. I would cite Theorem 5.7 and would bring it to reading group if anyone in the group works on network rearrangement distances.","headline":"A solid unrooted-network extension of agreement forests with useful constant-factor bounds on TBR and PR distances; mostly right, but the endpoint ordered-embedding proof is a genuine gap.","tokens_in":20266,"tokens_out":3809,"would_cite":true,"duration_ms":35444,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C05","05C90","92D15"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that the agreement distance between two unrooted phylogenetic networks is within a factor of two of their TBR distance and within a factor of four of their prune-and-regraft distance.","keywords":["phylogenetic network","rearrangement operation","agreement distance","maximum agreement graph","endpoint agreement distance","TBR distance","PR distance"],"falsifier":"Run a brute-force check over small proper binary networks, testing whether every maximum endpoint agreement graph admits an ordered agreement embedding; a single failure would supply a counterexample to the proof of the upper bound $d_{\\mathrm{PR}} \\le 3\\,d_{\\mathrm{EAD}}$ as written.","tokens_in":19321,"feed_emoji":"🧬","tokens_out":6593,"duration_ms":59229,"temperature":0.7,"pith_summary":"The paper extends the classical maximum agreement forest idea to unrooted phylogenetic networks, defining a maximum agreement graph whose minimal number of disagreement edges forms the agreement distance. It proves this distance is a metric, agrees with the TBR distance on trees and on tree-network pairs, and bounds the TBR distance of any two proper binary networks within a factor of two. A second construction, maximum endpoint agreement graphs, gives an endpoint agreement distance that bounds the prune-and-regraft distance within a factor of three. This matters because rearrangement distances are NP-hard to compute and previously lacked a graph-based certificate for networks; a single shared structure that approximates these distances is a step toward algorithms and heuristic searches.","feed_headline":"Agreement distance approximates network TBR cost within factor 2","feed_subtitle":"One shared graph structure bounds both TBR and prune-and-regraft distances, giving a handle on NP-hard network comparisons.","key_machinery":"The maximum agreement graph (MAG): a graph whose connected components split into agreement subgraphs—parts that embed identically into both networks—and disagreement edges, single edges on unlabelled vertices that account for edges moved or added when passing from one network to the other. A MAG is an agreement graph with the fewest disagreement edges, and the count of those edges defines $d_{\\mathrm{AD}}$. For endpoint agreement, a maximum endpoint agreement graph is the same idea but with one-ended sprouts that model prune-and-regraft moves; the endpoint agreement distance counts sprouts on agreement subgraphs plus disagreement edges. The argument that these counts are metrics and that they sandwich the rearrangement distances runs through ordered agreement embeddings, which fix a systematic ordering of disagreement edges, and through explicit constructions that turn a rearrangement sequence into an agreement graph and vice versa.","core_discovery":"The central claim is Theorem 5.7: for any two proper unrooted binary phylogenetic networks on the same taxa, $d_{\\mathrm{AD}}(N,N') \\le d_{\\mathrm{TBR}}(N,N') \\le 2\\,d_{\\mathrm{AD}}(N,N')$. The agreement distance is therefore not just a lower bound; it is a constant-factor approximation of the TBR distance, and through the known two-sided comparison between PR and TBR it also satisfies $d_{\\mathrm{AD}}(N,N') \\le d_{\\mathrm{PR}}(N,N') \\le 4\\,d_{\\mathrm{AD}}(N,N')$. The paper also proves that the endpoint agreement distance is a metric and satisfies $d_{\\mathrm{EAD}}(N,N') \\le d_{\\mathrm{PR}}(N,N') \\le 3\\,d_{\\mathrm{EAD}}(N,N')$. For trees, and whenever one network is displayed by the other, the agreement distance coincides with the TBR distance; the gap between the distances is a genuinely network phenomenon, exhibited by a pair of tier-seven networks with agreement distance $2$ and TBR distance $3$.","pith_inferences":["A practical reading of Theorem 5.7 is that an exact or approximate solver for maximum agreement graphs would immediately yield approximation algorithms for TBR and PR distances; the paper stops short of proposing such an algorithm.","The gap between $d_{\\mathrm{AD}}$ and $d_{\\mathrm{TBR}}$ is not known to be tight, since the only exhibited separation is $2$ versus $3$; tightening the factor-two bound would likely require understanding when ordered agreement embeddings force extra rearrangement moves.","For search heuristics, the endpoint agreement distance looks more natural than the ordinary agreement distance for prune-and-regraft moves because its sprouts model one-ended pruning; that analogical advantage is not tested in this paper.","The tier-seven separating example leaves open whether agreement distance and TBR distance coincide on low-tier networks; checking tiers one through six directly would be a small computational experiment."],"forward_implications":["Because $d_{\\mathrm{AD}}(N,N') \\le d_{\\mathrm{TBR}}(N,N') \\le 2\\,d_{\\mathrm{AD}}(N,N')$, any algorithm that computes $d_{\\mathrm{AD}}$ gives a 2-approximation of the TBR distance and, through Corollary 5.8, a 4-approximation of the PR distance.","The agreement distance equals the TBR distance on trees and on tree-network pairs, so in those settings there is no approximation loss at all.","Both $d_{\\mathrm{AD}}$ and $d_{\\mathrm{EAD}}$ are metrics, so they give network comparison scores that obey the triangle inequality, a property useful for clustering or outlier detection among inferred networks.","Computing the agreement distance is NP-hard, so the new constant-factor bounds are structural certificates rather than immediate practical algorithms."],"supporting_citations":[{"why":"Supplies maximum agreement forests and the theorem that their component count equals TBR distance on trees, which Proposition 3.3 uses to identify the two distances on trees.","marker":"Allen and Steel, 2001"},{"why":"Defines PR and TBR on unrooted networks, proves NP-hardness of the TBR distance, and gives the two-sided comparison between PR and TBR used in Corollary 5.8.","marker":"Janssen and Klawitter, 2019"},{"why":"Earlier paper introducing maximum agreement graphs for rooted networks; its Lemma 3.2 is invoked as the analogous proof for ordered endpoint agreement embeddings.","marker":"Klawitter, 2019"},{"why":"Introduced maximum endpoint agreement forests and the replug distance for unrooted trees, which the paper generalizes to networks and uses to prove the endpoint agreement distance is a metric.","marker":"Whidden and Matsen, 2019"},{"why":"Defines proper unrooted phylogenetic networks, a standing assumption throughout the paper.","marker":"Francis et al., 2018a"}],"fun_headline_variants":["Agreement distance gives 2-approximation for TBR on networks","Constant-factor bounds link agreement and TBR distances","Agreement graphs approximate network rearrangement distances","New metric approximates phylogeny network TBR cost","Agreement distance bounds network TBR and PR within constants"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The metric property of the endpoint agreement distance and the factor-three PR bound both depend on the claim that every maximum endpoint agreement graph admits an ordered agreement embedding; that existence is asserted by analogy to an earlier result rather than proven in this paper.","fun_headline_variants_meta":{"raw":{"variants":["Agreement distance gives 2-approximation for TBR on networks","Constant-factor bounds link agreement and TBR distances","Agreement graphs approximate network rearrangement distances","New metric approximates phylogeny network TBR cost","Agreement distance bounds network TBR and PR within constants"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000577,"raw_usage":{"total_tokens":2737,"prompt_tokens":978,"completion_tokens":1759,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":594,"completion_tokens_details":{"reasoning_tokens":1682}},"tokens_in":594,"tokens_out":1759,"duration_ms":11591,"temperature":1.0,"reasoning_tokens":1682,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:47:00.147500+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run a brute-force check over small proper binary networks, testing whether every maximum endpoint agreement graph admits an ordered agreement embedding; a single failure would supply a counterexample to the proof of the upper bound $d_{\\mathrm{PR}} \\le 3\\,d_{\\mathrm{EAD}}$ as written.","supporting_citations":[],"review_version":1}