Pith. sign in

REVIEW 2 major objections 5 minor 20 references

Optimizing Consistent Merging and Pruning of Subgraphs in Network Tomography

T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Inconsistent network path weights can be optimally repaired by a least-squares projection onto consistent sets.

desk verdict 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. read the letter →

arxiv 1908.03519 v1 pith:UTUKVFE2 submitted 2019-08-09 math.OC cs.DS

Mahmood Ettehad , Nick Duffield , Gregory Berkolaiko This is my paper · ORCID
classification math.OCcs.DS MSC 90C2005C5090C90
keywords networktomographypathcorrelationdataleast-squaresoptimizationMoore-Penroseinversegraphmergingtreepruningasymmetricroutingadditivemetrics
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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))$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

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.

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 (2)
  1. [§1.5(1), §§3.1–3.2, Eq. (3)–(5), Theorems 3.1 and 3.8] 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.
  2. [§3.3 and §4.4] 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.
minor comments (5)
  1. [§1.2] 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.
  2. [§2.4] In the phrase 'Due to statistical node, a non-binary node...', 'node' should be 'noise'.
  3. [§3.3] There are typos such as 'in the our problem' and 'constrains'; these should be corrected to 'in our problem' and 'constraints'.
  4. [§4.1] 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.
  5. [§4.4] 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.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity; the least-squares consistency derivations are self-contained, with self-citations only contextual and a non-circular positivity gap.

full rationale

The derivation chain for the two main theorems is self-contained linear algebra. Theorem 3.1 (Eq. 8) is the Moore-Penrose solution of A~W = Z minimizing ||W-~W||^2, proved in Section 6 from Aδ = η and the minimal-norm property of A' without using any fitted data or output-dependent quantity. Theorem 3.8 (Eq. 15) solves A~W = 0 for the signed incidence matrix; its full-row-rank proof uses only Corollary 3.4's row-rank argument for tree incidence matrices, and its error bound follows from the spectral bound ||A A^T|| ≥ 2 proved from the tree incidence structure. No parameter entering the objective (W, Z, A) is derived from the output ~W; consistency is defined by the very constraints being solved. The cited reconstruction paper [3] supplies the downstream fusion algorithm and the motivating reconstruction conditions, but it is not used to prove Equations (8), (12), or (15); the self-citations in Sections 1 and 4 are therefore contextual rather than load-bearing. The one clear limitation is the positivity constraint (5): Section 3.3 explicitly states 'There is no guarantee that such naive approach would result in an optimal or nearly optimal solution' and offers only a sketched interior-point method, while Example 2 shows that Theorem 3.8's closed form produces negative entries. This is a genuine gap between the problem as stated and the problem actually solved, so it affects the strength of the paper's optimality claim; however, it is a correctness/scope limitation, not circularity, because the unconstrained closed forms do not depend on positivity for their derivation. Accordingly, no step in the claimed derivation reduces to its own input, and no prediction is forced from a fitted quantity.

Assumptions & free parameters 1 free parameters · 5 assumptions · 0 invented entities

The central derivation is self-contained linear algebra and has no fitted parameters. The consistency constraints assume the path model in Section 1.2 and additive edge weights. The simulation uses several hand-set parameters, such as Poisson window counts, loss probabilities, packet counts, and the pruning factor, but these are evaluation choices rather than inputs to the theorems.

free parameters (1)
  • pruning factor delta and delta* selection heuristic = selected per experiment as the largest gap in pruning density (Section 4.4)
    Hand-chosen threshold that determines which edges are pruned in the simulation; it affects reported reconstruction accuracy but is not part of the theoretical consistency solution.
assumptions (5)
  • domain assumption The path set P satisfies uniqueness, no interior boundaries, and path consistency (Section 1.2).
    These assumptions define the partial network graph and guarantee that each boundary pair has exactly one path and that source and receiver trees describe the same physical paths. The full-row-rank proofs rely on them.
  • domain assumption Edge weights are additive: the weight of a path is the sum of its edge weights.
    All consistency conditions are linear equations of the form sum of edge weights equals path weight; the least-squares formulation and the routing matrix A require this linearity.
  • standard math Standard Moore-Penrose inverse and least-squares projection properties for real matrices.
    Theorem 3.1 and Corollary 3.5 are direct applications of the known fact that the minimal-norm least-squares solution of A*delta = eta is delta = A'*eta, cited to Penrose [15].
  • domain assumption Path correlation data can be estimated from covariance of path sums, Cov(X_P, X_P') = Var(X_{P cap P'}) (Eq. 2).
    This model motivates how path intersection weights are obtained from unicast packet measurements; it assumes i.i.d. edge random variables across time slots. It is background for the application, not an input to the optimization theorems.
  • domain assumption The graph reconstruction algorithm and identifiability conditions of [3] are correct.
    The composite pipeline uses [3] to merge intrinsically consistent trees into a network; this paper does not re-derive those conditions and its practical value is tied to their validity.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimizing Consistent Merging and Pruning of Subgraphs in Network Tomography." pith.science (2026). https://pith.science/paper/UTUKVFE2

@misc{pith2026190803519,
  author       = {Pith},
  title        = {Pith review of: Optimizing Consistent Merging and Pruning of Subgraphs in Network Tomography},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UTUKVFE2}},
  note         = {Machine review of arXiv:1908.03519}
}
read the original abstract

A communication network can be modeled as a directed connected graph with edge weights that characterize performance metrics such as loss and delay. Network tomography aims to infer these edge weights from their pathwise versions measured on a set of intersecting paths between a subset of boundary vertices, and even the underlying graph when this is not known. Recent work has established conditions under which the underlying directed graph can be recovered exactly the pairwise Path Correlation Data, namely, the set of weights of intersection of each pair of directed paths to and from each endpoint. Algorithmically, this enables us to consistently fused tree-based view of the set of network paths to and from each endpoint to reconstruct the underlying network. However, in practice the PCD is not consistently determined by path measurements. Statistical fluctuations give rise to inconsistent inferred weight of edges from measurement based on different endpoints, as do operational constraints on synchronization, and deviations from the underlying packet transmission model. Furthermore, ad hoc solutions to eliminate noise, such as pruning small weight inferred links, are hard to apply in a consistent manner that preserves known end-to-end metric values. This paper takes a unified approach to the problem of inconsistent weight estimation. We formulate two type of inconsistency: \textsl{intrinsic}, when the weight set is internally inconsistent, and \textsl{extrinsic}, when they are inconsistent with a set of known end-to-end path metrics. In both cases we map inconsistent weight to consistent PCD within a least-squares framework. We evaluate the performance of this mapping in composition with tree-based inference algorithms.

Figures

Figures reproduced from arXiv: 1908.03519 by the authors.

Figure 1
Figure 1. Source tree T S b1 rooted at vertex b1, receiver tree T R b2 rooted at vertex b2 both having version of direct path Pb1,b2 [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Left: merged graph G under equal path weights w1 + w2 = v1 + v2 for directed path P1,2. WNLOG assume v1 < w1 and hence v2 > w2. Right: Pruned graph Ge after removal of edge (c, c0 ) from G. 1.4. Problem Statement. Motivated by the problems inherent in graph merging and graph pruning described above, we abstract two variant problems in treating inconsistency, as follows: Extrinsic Consistency Let G = (G, VB,P) be a p… view at source ↗
Figure 3
Figure 3. Inconsistency occurs by pruning the edges. Left: the original par￾tial graph, right: the pruned representation. 3.2. Intrinsic consistency in Tree-Based Network Inference. In the section we ad￾dress the question of intrinsic consistency (see Section 1.4) in the setting of our intended application, when the graphs G (i) are trees. More precisely, we assume to be give the set VB and, for any b ∈ VB, two directed trees… view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: Example on randomly generated source T S b1 and receiver T R b1 trees at vertex b1. See Section 1 for the definition of source and receiver trees at vertex b ∈ VB. 4.2. Generating Measurements. In this part we will discuss the process of generating end-to-end measureme…
Figure 5
Figure 5. Figure 5: Alternation of edges state and measured end-to-end averaged packet fraction over time [PITH_FULL_IMAGE:figures/full_fig_p016_5.png]
Figure 6
Figure 6. Figure 6: Dependence of topological inference error on the number of averag￾ing windows evaluated based on metric TM1 and TM2. Left: network graphs graph with |VB| = 6 and right: |VB| = 12 [PITH_FULL_IMAGE:figures/full_fig_p019_6.png]
Figure 7
Figure 7. Figure 7: Left: Dependence of topological inference error on fraction of lossy edges. Right: Sample on dependence of density of pruned edges on pruning factor for different number of averaging windows. The vertical dashed lines are the selected pruning factor for the correspondi…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

  1. [3]

    Berkolaiko, N

    G. Berkolaiko, N. Duffield, M. Ettehad, and K. Manousakis. Graph reconstruction from path correlation data. Inverse Problems, 35:1–25, 2018

    work page 2018

  2. [1]

    Antoniou and W

    A. Antoniou and W. S. Lu. Practical optimization: Algorithms and engineering applications. Springer, 2007

    work page 2007

  3. [2]

    Battacharaya, N

    A. Battacharaya, N. Duffield, M. Ettehad, and K. Manousakis. Manuscript in preparation. 2019

    work page 2019

  4. [4]

    T. Bu, N. G. Duffield, F. L. Presti, and D. F. Towsley. Network tomography on general topologies. In Proceedings of the International Conference on Measurements and Modeling of Computer Systems, SIGMETRICS 2002, June 15-19, 2002, Marina Del Rey, California, USA , pages 21–30, 2002

    work page 2002

  5. [5]

    Caceres, N

    R. Caceres, N. G. Duffield, J. Horowitz, F. L. Presti, and D. Towsley. Loss-based inference of mul- ticast network topology. In Proceedings of the 38th IEEE Conference on Decision and Control (Cat. No.99CH36304), volume 3, pages 3065–3070, Dec 1999

    work page 1999

  6. [6]

    Caceres, N

    R. Caceres, N. G. Duffield, J. Horowitz, and D. F. Towsley. Multicast-based inference of network-internal loss characteristics. IEEE Transactions on Information Theory , 45(7):2462–2480, Nov 1999

    work page 1999

  7. [7]

    X. Cai, G. Wang, and Z. Zhang. Complexity analysis and numerical implementation of primal-dual interior-point methods for convex quadratic optimization based on a finite barrier.Numerical Algorithms, 62:289–306, 2013

    work page 2013

  8. [8]

    Coates, M

    M. Coates, M. Rabbat, and R. Nowak. Merging logical topologies using end-to-end measurements. In Proceedings of the 3rd ACM SIGCOMM Conference on Internet Measurement , IMC ’03, pages 192–203, New York, NY, USA, 2003. ACM

    work page 2003

Show all 20 references
  1. [9]

    N. G. Duffield, J. Horowitz, F. L. Presti, and D. Towsley. Multicast topology inference from measured end-to-end loss. IEEE Transactions on Information Theory , 48(1):26–45, Jan 2002

    2002

  2. [10]

    N. G. Duffield and F. L. Presti. Multicast inference of packet delay variance at interior network links. In Proceedings IEEE INFOCOM 2000. Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (Cat. No.00CH370...

    2000

  3. [11]

    N. G. Duffield, F. L. Presti, V. Paxson, and D. Towsley. Inferring link loss using striped unicast probes. In Proceedings IEEE INFOCOM 2001. Conference on Computer Communications. Twentieth Annual CONSISTENT MERGING AND PRUNING OF SUBGRAPHS 25 Joint Conference of the IEEE Comput...

    2001

  4. [12]

    Horaud and T

    R. Horaud and T. Skordas. Stereo correspondence through feature grouping and maximal cliques. IEEE Transactions on Pattern Analysis and Machine Intelligence , 11(11):1168–1180, Nov 1989

    1989

  5. [13]

    Lopresti, N

    F. Lopresti, N. G. Duffield, J. Horowitz, and D. Towsley. Multicast-based inference of network-internal delay distributions. IEEE/ACM Trans. Netw. , 10(6):761–775, Dec. 2002

    2002

  6. [14]

    H. X. Nguyen and P. Thiran. Network loss inference with second order statistics of end-to-end flows. In Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement , IMC ’07, pages 227–240, New York, NY, USA, 2007. ACM

    2007

  7. [15]

    R. Penrose. On best approximate solution of linear matrix equations. Proceedings of the Cambridge Philosophical Society, 52:17–19, 1956

    1956

  8. [16]

    Rabbat, R

    M. Rabbat, R. Nowak, and M. Coates. Multiple source, multiple destination network tomography. In IEEE INFOCOM 2004 , volume 3, pages 1628–1639, March 2004

    2004

  9. [17]

    Sabnis, R

    A. Sabnis, R. K. Sitaraman, and D. Towsley. OCCAM: An Optimization-Based Approach to Network Inference. ArXiv e-prints, page arXiv:1806.03542, June 2018

    2018 arXiv

  10. [18]

    Sattari, M

    P. Sattari, M. Kurant, A. Anandkumar, A. Markopoulou, and M. G. Rabbat. Active learning of multiple source multiple destination topologies. IEEE Transactions on Signal Processing , 62(8):1926–1937, April 2014

    1926

  11. [19]

    L. G. Shapiro and R. M. Haralick. Structural descriptions and inexact matching. IEEE Transactions on Pattern Analysis and Machine Intelligence , PAMI-3(5):504–519, Sept 1981

    1981

  12. [20]

    S. J. Wright. Primal-dual interior-point method. SIAM Philadelphia , 1997. Department of Mathematics, Texas A&M University, College Station, TX 77843-3368, USA Department of Electrical and Computer Engineering, Texas A&M University, College Sta- tion, TX 77843, USA Department ...

    1997

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.