{"id":"c9418674-7669-47db-8d9a-48ebbaf71da3","arxiv_id":"1908.03519","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":1,"one_line_summary":"The authors formulate two types of inconsistent path-weight correction in network tomography as least-squares projections and derive closed-form solutions using Moore-Penrose inverses.","lead":"This paper gives a mathematical recipe for fixing inconsistent network measurements before merging them into a single network map. It uses least squares to adjust edge weights so that all paths agree, and tests the recipe in simulations.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The closed-form least-squares solutions solve only the unconstrained problem; positivity is part of the stated problem, and the positivity step is heuristic, so the claimed 'optimal consistent adjustment' is not established for admissible nonnegative edge weights.","rationale":"The reader's verdict is CONDITIONAL, and my concern reinforces that conditionality rather than overturning it. The reader identified the weakest assumption as the standing path-set model (uniqueness, no interior boundaries, path consistency) and flagged the missing baseline comparison and unspecified positivity-constrained pruning as empirical issues. My stress-test goes one step further: the positivity gap is not just an empirical reporting problem, it is a mismatch between the paper's stated optimization problem and the theorems that solve it. Section 1.5(1) and problem (3)-(5) include nonnegativity, but Theorem 3.1 and Theorem 3.8 provide closed-form solutions only for the unconstrained least-squares problem. Example 2 shows explicitly that the unconstrained solution can be negative for sufficiently large inconsistencies, and Section 3.3 offers only heuristics without optimality guarantees. Therefore the central claim that inconsistent path weights are 'optimally adjusted' under consistency and positivity conditions is not fully established by the mathematical results. I do not believe this invalidates the paper's useful and apparently correct unconstrained least-squares framework, nor does it demand rejection; it does strengthen the need for a conditional acceptance with clarification or revision of the claims about positivity. The proposed concrete test would settle whether the practical algorithm matches the stated optimization target. I also verified the core linear algebra: Theorem 3.1 is a standard Moore-Penrose projection; the full-row-rank argument in Theorem 3.8 is sound under the stated tree/path assumptions, with each tree's leaf edges providing an identity decomposition; and the error bound ||AW||^2/2 follows from AAT >= 2I, with the tightness argument for tree networks appearing correct. Thus the mathematical core is solid for the relaxed problem, and the load-bearing concern is specifically about the positivity gap and the resulting lack of a verifiable optimality guarantee for the practical method.","tokens_in":19715,"tokens_out":28642,"duration_ms":282270,"concrete_test":"Reproduce Example 2 with all weights 1 except wR_a,1 = 1 + 90. Compute the closed-form solution from equation (15), noting entries 1 + (90/90)*(-19) = -18 and 1 + (90/90)*(-5) = -4 are negative, making the solution infeasible for the nonnegativity constraint. Then solve the constrained quadratic program (17) with H = 2I, c = -2W, B = A, b = 0, x >= 0 using a standard QP solver, and compare its optimum to the output of the Section 3.3 iterative negative-edge pruning algorithm on the same instance. If the iterative output is not within a small tolerance of the true constrained optimum, the paper's practical algorithm does not deliver the claimed optimal positivity-constrained adjustment.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central optimality claim is undercut by the gap between the problem as stated and the problem solved by the main theorems. Section 1.5(1) says the paper seeks to minimize squared distance 'under consistency and positivity conditions', and the optimization (3)-(5) includes the explicit constraint ~W >= 0. However, Theorem 3.1 and Theorem 3.8 solve only the unconstrained problems (3)-(4) and (13)-(14), respectively. The solutions are Moore-Penrose projections and, as the paper itself notes in Section 3.3, they are not guaranteed to be nonnegative. Example 2 makes this concrete: for a 3-star with one perturbed edge weight 1+epsilon, the closed-form solution has entries 1 + (epsilon/90)*c with c = -19 and c = -5, which become negative for epsilon > 90/19 and epsilon > 18, respectively. Thus for moderate perturbation sizes, the 'consistent' edge weights produced by Theorem 3.8 are not admissible edge weights under the paper's own model W:E -> R>=0. The subsequent treatment of positivity (Section 3.3) is heuristic: iterative pruning of negative edges is described without an optimality guarantee, and the interior-point method is only sketched. Consequently, the composite simulation in Section 4, which relies on unspecified positivity-constrained pruning, does not demonstrate that the final output is the claimed least-squares optimum of the stated problem. This is a load-bearing gap in the central claim, not merely a reporting issue.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper addresses the problem of inconsistent edge/path weight estimates in network tomography. It formulates two least-squares adjustment problems: extrinsic consistency, where adjusted edge weights must reproduce (or best fit) a target set of end-to-end path weights; and intrinsic consistency, where the weights of common paths across source and receiver trees must agree so that the trees can be fused by the reconstruction algorithm of [3]. The main theoretical results are closed-form solutions via the Moore-Penrose inverse (Theorem 3.1 and Theorem 3.8), full-row-rank results for tree incidence matrices (Corollary 3.4 and Theorem 3.8), and an error bound for the intrinsic consistency adjustment (Eq. (16)). The paper also presents a composite five-stage inference pipeline and evaluates it in a model-based simulation. A substantial part of the paper is concerned with positivity of edge weights, but the main theorems solve only the equality-constrained problems and the positivity treatment is heuristic or only sketched.","tokens_in":19947,"tokens_out":6213,"duration_ms":71228,"significance":"If the central claim were fully established, the paper would supply a principled projection step for making inconsistent tomography measurements usable in the graph-reconstruction framework of [3]. The linear algebra is clean and self-contained: Theorem 3.1 is a standard least-squares projection, the full-row-rank arguments in Corollary 3.4 and Theorem 3.8 are genuinely useful structural results, and the tight error bound ||W~−W||^2 ≤ ||AW||^2/2 is proved carefully. The practical motivation is clear and the composite evaluation addresses a real pipeline. However, the gap between the problems as stated (with nonnegativity constraints) and the problems solved by the theorems (without them) directly limits the force of the paper's main optimization claim. The significance of the work currently depends on either solving the constrained problem explicitly or substantially reframing the contribution.","major_comments":[{"comment":"The contribution statement says the paper solves the consistency problems 'under consistency and positivity conditions,' but Theorems 3.1 and 3.8 minimize the squared distance subject only to the equality constraints (4) and (14), respectively. The nonnegativity constraint ~W ≥ 0 is not enforced in either theorem, and Section 3.3 explicitly acknowledges that the closed-form solutions are not guaranteed to be nonnegative. Example 2 makes this concrete: entries of the form 1 + (ε/90)(−19) and 1 + (ε/90)(−5) become negative for ε > 90/19 and ε > 18, respectively. Since the network model takes W : E → R_{≥0}, those outputs are not admissible edge weights. The central claim in contribution (1) is therefore not established for the constrained problem. The authors should either solve the constrained problem with a fully specified algorithm and verify optimality, or clearly reframe the theorems as solving only the unconstrained projection and treat positivity as an additional heuristic step.","section":"§1.5(1), §§3.1–3.2, Eq. (3)–(5), Theorems 3.1 and 3.8"},{"comment":"The positivity treatment does not support the numerical evaluation. Section 3.3 says of the naive iterative pruning approach that 'There is no guarantee that such naive approach would result in an optimal or nearly optimal solution.' The interior-point method is only sketched as a general convex-QP scheme; it is not specialized to the matrices from Corollaries 3.4–3.5 or Theorem 3.8, and no convergence or optimality checks are reported. Section 4.4 states that the final pruning step is 'achieved by applying the result of Corollary 3.5 along with positivity constraint,' but does not identify the constrained solver used, its stopping criterion, or whether the KKT conditions were verified. As a result, the simulation results in Figures 6–7 do not demonstrate that the reported inference accuracy corresponds to the claimed least-squares optimum of the constrained problem.","section":"§3.3 and §4.4"}],"minor_comments":[{"comment":"The sentence 'We represent the communications network by a a directed edge-weighted graph G = (V,E,W) be with vertices...' contains a duplicated 'a' and an ungrammatical 'be'; please rephrase.","section":"§1.2"},{"comment":"In the phrase 'Due to statistical node, a non-binary node...', 'node' should be 'noise'.","section":"§2.4"},{"comment":"There are typos such as 'in the our problem' and 'constrains'; these should be corrected to 'in our problem' and 'constraints'.","section":"§3.3"},{"comment":"The path generation uses shortest paths with respect to the random weights; if equal-weight shortest paths exist, the standing assumption (i) of path uniqueness can be violated. The tie-breaking rule should be specified.","section":"§4.1"},{"comment":"Contribution (5) mentions 'naive pruning' and 'non-optimal averaging' as baselines, but the non-optimal averaging method is not defined anywhere in Section 4; please specify it explicitly so the comparison is reproducible.","section":"§4.4"}],"recommendation":"major_revision","confidential_remarks":"The mathematical core is sound and the paper is a plausible candidate for publication after revision. The main risk is the gap between the unconstrained problems solved in the theorems and the constrained problems asserted in the contribution statement; the simulation section should be made reproducible by specifying the positivity-constrained solver actually used. The reliance on the authors' prior work [3] is appropriate and not a concern."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The core of this paper is real: it turns the messy problem of fusing inconsistent weighted trees into two least-squares projections. Theorem 3.1 is the standard Moore-Penrose answer to AW=Z, and Theorem 3.8 gives a closed-form intrinsic consistency solution with a tight error bound. The full-row-rank proof for the signed incidence matrix over source and receiver trees is well done; the unique leaf-edge column argument works, and the tightness construction for at least four boundary vertices plus the 3-star check is convincing. That part deserves a serious referee. I also see no citation red flags; reliance on the authors' earlier reconstruction work [3] is appropriate because that paper supplies the fusion algorithm this one feeds into.\n\nThe soft spot is the gap between the problem as stated and the problem solved. The paper advertises minimization under consistency and positivity, but the theorems solve only the unconstrained projections. As the paper itself notes in Section 3.3, negative entries can appear, and Example 2 shows this concretely. The iterative pruning of negative edges is heuristic with no optimality guarantee, and the interior-point sketch is not proved to be the method used in the evaluation. So the phrase \"optimal consistent adjustment\" is too strong for the actual admissible edge weights. This is a substantive gap, but it does not invalidate the unconstrained results; it is a claim that needs repositioning.\n\nThe empirical section is weaker. The contribution list promises comparison against naive pruning and non-optimal averaging, but the figures show no baseline curves, no error bars, and no edge-weight accuracy. The pruning factor selection is an ad hoc heuristic. Without code or data, the simulation is hard to interpret. That is a reporting weakness, not a mathematical flaw.\n\nThe standing assumptions—unique path per boundary pair, no interior boundaries, path consistency—are strong, but they are stated up front and are standard for this area. The paper is for network tomography readers who need a principled way to adjust inconsistent inferred trees; the general optimization audience will find the machinery standard. Bottom line: the theory is solid and useful, but the paper needs revision on the positivity claim and the experiments. I would send it to a competent referee rather than desk reject it.","headline":"Clean least-squares consistency results for fusing inferred trees, with a real but fixable gap between the unconstrained theorems and the positivity-constrained problem as advertised.","tokens_in":20535,"tokens_out":3162,"would_cite":true,"duration_ms":34374,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C20","05C50","90C90"],"pacs":[],"model":"deepseek-v4-flash","headline":"Inconsistent network path weights can be optimally repaired by a least-squares projection onto consistent sets.","keywords":["network tomography","path correlation data","least-squares optimization","Moore-Penrose inverse","graph merging","tree pruning","asymmetric routing","additive path metrics"],"falsifier":"Compute $\\|\\tilde W-W\\|^2$ and $\\|AW\\|^2/2$ for tree instances generated under the standing assumptions: any instance exceeding the bound, or any tree whose signed incidence matrix has dependent rows, would break Theorem 3.8, as would a network with equal-cost multipath routing where two distinct simple paths make $(AA^T)^{-1}$ undefined.","tokens_in":19435,"feed_emoji":"🌐","tokens_out":7064,"duration_ms":70468,"temperature":0.7,"pith_summary":"Network tomography reconstructs edge-by-edge performance from end-to-end path measurements, but noise, clock skew, and model violations make the same path look different from different endpoints. This paper treats those inconsistencies as a constrained least-squares problem: find the edge weights closest to the measured ones that satisfy the consistency the fusion algorithm needs. For extrinsic consistency (matching known end-to-end path weights, e.g., after pruning low-weight edges) the optimal adjustment is $\\tilde W = W + A'(Z - AW)$. For intrinsic consistency (making all source and receiver trees agree on common path weights) the adjustment is $\\tilde W = W - A^T(AA^T)^{-1}AW$, with squared error at most $\\|AW\\|^2/2$. If correct, this lets noisy inferred subgraphs be merged and pruned in a principled way, restoring the exactness that graph-reconstruction algorithms require.","feed_headline":"A formula repairs inconsistent network path weights","feed_subtitle":"Least-squares projections make measured trees agree before fusion, with a proven error bound for pruning noise.","key_machinery":"The load-bearing object is the (signed) incidence matrix $A$ that maps edge weights to path weights: $A_{(u,v),e}=1$ when edge $e$ lies on path $P_{u,v}$, and $A_{(v,u),i}=\\pm 1$ according to whether edge $i$ belongs to the receiver or source tree. The Moore-Penrose inverse $A'$ (or $(AA^T)^{-1}$ when rows are independent) projects the measured weights onto the affine subspace of consistent weights with minimum squared displacement. The paper proves the row-rank condition in the tree setting—each leaf edge gives an independent row—and the eigenvalue argument $\\lambda_{\\min}(AA^T)\\ge 2$ that yields the $\\|AW\\|^2/2$ error bound.","core_discovery":"The paper claims that both kinds of inconsistency in weighted path data—internal disagreement among inferred trees and disagreement with known end-to-end metrics—can be removed optimally in squared distance by linear projections determined by the routing incidence matrix. Theorem 3.1 gives the least-squares consistent weights for arbitrary target path weights, and Theorem 3.8 specializes to tree-based inference and proves that the signed incidence matrix has full row rank, so the explicit formula with $(AA^T)^{-1}$ applies and the adjustment cost is bounded by $\\|AW\\|^2/2$, a bound that is tight for trees. Together these results turn the practical steps of pruning low-weight edges and fusing source and receiver trees into well-posed optimization problems with closed-form solutions, and the paper demonstrates the composite pipeline on simulated unicast measurements.","pith_inferences":["A natural extension would run the same $\\ell^2$ projection in a weighted or robust form, so that measurements known to be more reliable move less; the paper does not address measurement-specific confidence.","The $\\|AW\\|^2/2$ bound reads as a model-selection score: among candidate prunings, the one that minimizes projection cost is preferable, connecting pruning to standard information criteria; the paper only uses the bound for a heuristic threshold.","The machinery should carry over to non-additive monotone metrics approximated by logs or variances, since only the linear incidence structure is used; one could test this by feeding covariance-based path correlation data through the same pipeline."],"forward_implications":["Corollary 3.5 gives a closed-form way to redistribute the weight of pruned edges so that surviving edges stay as close as possible to their measurements while reproducing the original end-to-end path weights.","Theorem 3.8 makes source and receiver trees from different roots mutually consistent with minimal total squared weight change, so the graph-reconstruction algorithm of [3] can be applied even when raw measurements disagree.","The error bound $\\|\\tilde W-W\\|^2\\le\\|AW\\|^2/2$ is tight for trees, so users can prune the largest set of small-weight edges whose squared weights do not exceed the bound while knowing the worst-case adjustment cost.","The complete five-stage pipeline—merge binary trees, prune, enforce intrinsic consistency, fuse, prune again—reduces topological inference error as the number of averaging windows grows in the paper's simulations.","Edge weights can be kept nonnegative by adding a log-barrier and solving the resulting quadratic program with an interior-point method, at iteration complexity $O(\\sqrt n \\log(n/\\varepsilon))$."],"supporting_citations":[{"why":"Provides the graph-reconstruction algorithm from path correlation data whose consistent weight input this paper prepares.","marker":"[3]"},{"why":"Supplies the Moore-Penrose inverse characterization of the minimal-norm least-squares solution used in Theorems 3.1 and 3.8.","marker":"[15]"},{"why":"Gives the iteration complexity guarantee for the interior-point method used to enforce positivity constraints.","marker":"[7]"},{"why":"Establishes loss-based multicast topology inference and the small-weight edge pruning practice this paper formalizes.","marker":"[5]"},{"why":"Provides maximum-likelihood edge loss estimation on multicast trees, the measurement baseline for extrinsic consistency.","marker":"[6]"},{"why":"Introduces striped unicast probing whose pairwise packet correlations yield the path-intersection metric estimates.","marker":"[11]"},{"why":"Shows how second-order statistics of end-to-end unicast flows estimate weights of path intersections for the path correlation data.","marker":"[14]"}],"fun_headline_variants":["Least-squares projection reconciles path measurements","Closed-form fix for noisy network path weights","Optimal reconciliation of inconsistent path weights","Matrix formula makes path data consistent","Merge trees with reconciled weights via least squares"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole construction rests on the standing path-set model: each pair of endpoints is connected by exactly one route, no endpoint lies inside another measured route, and any two routes that share two points share the same stretch between them—only then is the routing matrix guaranteed to have the independence needed for the closed-form formulas.","fun_headline_variants_meta":{"raw":{"variants":["Least-squares projection reconciles path measurements","Closed-form fix for noisy network path weights","Optimal reconciliation of inconsistent path weights","Matrix formula makes path data consistent","Merge trees with reconciled weights via least squares"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000542,"raw_usage":{"total_tokens":2614,"prompt_tokens":979,"completion_tokens":1635,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":595,"completion_tokens_details":{"reasoning_tokens":1572}},"tokens_in":595,"tokens_out":1635,"duration_ms":14161,"temperature":1.0,"reasoning_tokens":1572,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:11:19.616889+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute $\\|\\tilde W-W\\|^2$ and $\\|AW\\|^2/2$ for tree instances generated under the standing assumptions: any instance exceeding the bound, or any tree whose signed incidence matrix has dependent rows, would break Theorem 3.8, as would a network with equal-cost multipath routing where two distinct simple paths make $(AA^T)^{-1}$ undefined.","supporting_citations":[{"cited_title":"Berkolaiko, N","cited_arxiv_id":null,"evidence_quote":"Provides the graph-reconstruction algorithm from path correlation data whose consistent weight input this paper prepares."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the Moore-Penrose inverse characterization of the minimal-norm least-squares solution used in Theorems 3.1 and 3.8."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the iteration complexity guarantee for the interior-point method used to enforce positivity constraints."},{"cited_title":"Caceres, N","cited_arxiv_id":null,"evidence_quote":"Establishes loss-based multicast topology inference and the small-weight edge pruning practice this paper formalizes."},{"cited_title":"Caceres, N","cited_arxiv_id":null,"evidence_quote":"Provides maximum-likelihood edge loss estimation on multicast trees, the measurement baseline for extrinsic consistency."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces striped unicast probing whose pairwise packet correlations yield the path-intersection metric estimates."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Shows how second-order statistics of end-to-end unicast flows estimate weights of path intersections for the path correlation data."}],"review_version":1}