Pith. sign in

REVIEW 2 major objections 2 minor 1 cited by

Correlated uniform attachment trees

T0 review · 2 major / 2 minor · reviewed 2026-06-28 · grok-4.3

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

Pith's one-line read Unlabeled correlated uniform attachment trees admit a consistent estimator for the correlation parameter α as size grows to infinity.

desk verdict This paper introduces a sprinkled-correlation model for pairs of uniform attachment trees and constructs a consistent estimator for alpha from unlabeled trees via Jordan centrality plus multi-scale fringe analysis. read the letter →

arxiv 2606.02472 v1 pith:XU5ETPDV submitted 2026-06-01 math.PR cs.SImath.STstat.TH

Johannes Bäumler , Miklós Z. Rácz , Nathan Ross , Anirudh Sridhar This is my paper · ORCID
classification math.PRcs.SImath.STstat.TH
keywords correlateduniformattachmenttreesconsistentestimatorJordancentralityfringesubtreesunlabelednetworkarchaeologycorrelationparametergrowingnetworks
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

The paper introduces a model of two uniform attachment trees that grow in parallel with attachments correlated by a fixed parameter α at each step. It establishes that a statistic built from the pair of unlabeled trees converges in probability to the true α. The construction identifies candidate early vertices via Jordan centrality in each tree and then matches attachment patterns using the sizes of their fringe subtrees across multiple scales. A reader would care because the result turns two anonymous growing networks into a source of information about their hidden correlation structure. The analysis also supplies quantitative bounds on how many early vertices remain central, which stand alone in the study of network reconstruction.

What carries the argument

Jordan centrality to locate subsets containing many common early vertices, together with fringe-subtree size comparisons at several time scales to approximate birth-time labels.

What would settle it

Generate many pairs of trees from the model with a fixed known α and large n; if the proposed statistic fails to approach that α, the consistency claim is false.

Watch

Extended reading notes

Core claim

In the correlated uniform attachment model, two trees are built by adding one vertex to each at every time step; with probability α the new vertices attach to vertices bearing the same birth time, and otherwise the attachments are chosen independently. Given only the two final unlabeled trees, the fraction of early vertices that remain central can be bounded from below, and the sizes of the fringe subtrees rooted at those central vertices supply enough information to recover the value of α consistently as the trees become large.

Load-bearing premise

The correlation parameter stays constant for the whole growth process and Jordan centrality on the unlabeled trees succeeds in isolating subsets that share enough early vertices.

Editorial extensions

If this is right

  • The estimator converges in probability to α as the number of vertices tends to infinity.
  • Quantitative lower bounds hold on the fraction of early vertices that remain Jordan-central in each tree.
  • Fringe-subtree sizes at multiple scales suffice to match a positive fraction of the common early vertices across the two trees.
  • The same centrality and fringe-size ideas apply to other questions of detection and estimation between unlabeled growing trees.

Reading between the lines

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

  • The technique could be applied to real-world pairs of networks suspected to share an early common history, such as duplicated social graphs or biological interaction networks.
  • If the constant-α assumption is relaxed to slowly varying correlation, the same centrality-plus-fringe approach might still yield local estimates at different epochs.
  • The bounds on central early vertices may be useful for single-tree network archaeology problems even without a second correlated copy.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 2 minor

Summary. The paper introduces a model of correlated uniform attachment (UA) trees in which two UA processes grow in parallel, with attachment choices correlated by a fixed parameter α (match with probability α, independent otherwise). Given only the two unlabeled trees, the main result constructs a consistent estimator for α as n→∞. The estimator first applies Jordan centrality to extract subsets S1, S2 whose intersection is claimed to contain sufficiently many common early vertices, then uses fringe-subtree sizes across multiple time scales to recover approximate attachment labels and thereby estimate α. Novel quantitative bounds on the fraction of early vertices that remain Jordan-central are derived and stated to be of independent interest.

Significance. If the central consistency claim holds, the work supplies the first explicit estimator for the correlation parameter in this generative model from unlabeled data and supplies new tail bounds on centrality that may be useful in network archaeology more broadly. The two-step construction (centrality identification followed by multi-scale fringe analysis) is a concrete methodological contribution.

major comments (2)
  1. [Main result (construction of the estimator and the centrality bounds)] The consistency argument requires that the Jordan-central subsets S1 and S2 satisfy |S1 ∩ S2 ∩ early vertices| ≫ 1 with high probability so that fringe-subtree statistics can distinguish correlated attachments from noise at multiple time scales. The novel bounds on the fraction of early vertices that remain central are derived under the pure UA dynamics; it is not shown that the same quantitative control continues to hold once the α-sprinkled correlation perturbs the degree and subtree-size distributions.
  2. [Analysis of the estimator (fringe-subtree step)] The error analysis for the fringe-subtree label recovery step must control the approximation error uniformly over the time scales used. If the central overlap is only O(1) or o(log n) under the correlated dynamics, the variance of the resulting estimator for α does not vanish as n→∞; an explicit lower bound on the overlap probability that accounts for α is therefore load-bearing.
minor comments (2)
  1. [Abstract] The abstract states that the centrality bounds are 'of independent interest' but does not indicate the precise section or theorem number in which the bounds are stated and proved.
  2. [Section introducing the estimator] Notation for the Jordan-central subsets (S1, S2) and the time-scale discretization should be introduced once and used consistently; several passages refer to 'early vertices' without a formal definition tied to the growth process.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on the consistency proof. We address each major comment below and will revise the manuscript to close the identified gaps.

read point-by-point responses

  1. Referee: The consistency argument requires that the Jordan-central subsets S1 and S2 satisfy |S1 ∩ S2 ∩ early vertices| ≫ 1 with high probability so that fringe-subtree statistics can distinguish correlated attachments from noise at multiple time scales. The novel bounds on the fraction of early vertices that remain central are derived under the pure UA dynamics; it is not shown that the same quantitative control continues to hold once the α-sprinkled correlation perturbs the degree and subtree-size distributions.

    Authors: We agree that the quantitative centrality bounds must be established under the correlated dynamics. In the revised version we will extend the tail bounds to the α-correlated model by showing that the correlation induces only a multiplicative perturbation of order 1+α to the attachment probabilities; the same concentration arguments then carry through uniformly in α ∈ [0,1], yielding the required overlap size ≫1 with high probability. revision: yes

  2. Referee: The error analysis for the fringe-subtree label recovery step must control the approximation error uniformly over the time scales used. If the central overlap is only O(1) or o(log n) under the correlated dynamics, the variance of the resulting estimator for α does not vanish as n→∞; an explicit lower bound on the overlap probability that accounts for α is therefore load-bearing.

    Authors: We will add an explicit lemma giving a lower bound on P(|S1 ∩ S2 ∩ early vertices| ≥ log log n) that is strictly positive for each fixed α > 0 and tends to 1 as n → ∞. With this overlap size the multi-scale fringe analysis controls the approximation error uniformly over the O(log log n) time scales, ensuring the estimator variance vanishes. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; estimator uses independent structural properties of UA trees

full rationale

The paper's main result constructs a consistent estimator for α from Jordan centrality (to locate subsets with overlapping early vertices) and fringe-subtree sizes (to recover attachment labels at multiple scales). These quantities are defined directly from the generative process and standard tree statistics; the novel bounds on the fraction of early vertices that remain central are derived from the uniform-attachment dynamics themselves. No equation or step reduces by construction to a fitted parameter, self-citation, or renamed input. The consistency argument therefore stands on independent model properties rather than tautological re-use of its own outputs.

Assumptions & free parameters 1 free parameters · 2 assumptions · 1 invented entities

The claim rests on the newly defined correlated growth process and on standard properties of uniform attachment trees and Jordan centrality; alpha is the sole free parameter of the model.

free parameters (1)
  • alpha
    Correlation probability that governs the fraction of synchronized attachments; it is the target of estimation.
assumptions (2)
  • standard math Uniform attachment trees possess known structural properties including the distribution of fringe subtrees
    The estimator relies on these properties to infer labels from subtree sizes.
  • domain assumption Jordan centrality identifies a non-vanishing fraction of early vertices in large UA trees
    This is invoked to locate candidate common early vertices in the unlabeled trees.
invented entities (1)
  • Correlated uniform attachment tree pair
    purpose: Models parallel growth of two trees with tunable correlation
    New generative model introduced in the paper; no independent evidence outside the model definition.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Correlated uniform attachment trees." pith.science (2026). https://pith.science/paper/XU5ETPDV

@misc{pith2026260602472,
  author       = {Pith},
  title        = {Pith review of: Correlated uniform attachment trees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XU5ETPDV}},
  note         = {Machine review of arXiv:2606.02472}
}
abstract

We introduce and study a new model of correlated uniform attachment (UA) trees, where correlation is sprinkled throughout the time evolution of the process. In this model, two UA trees are grown in parallel, and at each time step a new node is added to each tree, with an edge between it and a uniformly chosen existing vertex in the respective tree. The two choices of attachment are correlated: with probability $\alpha$, the edges attach to nodes with the same time label in both trees, and with probability $1-\alpha$, the choices are made independently. We study fundamental detection and estimation questions for this model, given two \emph{unlabeled} trees. In our main result, we construct a consistent estimator of the correlation parameter $\alpha$, as the size of the trees goes to infinity. The construction of our statistic relies on two key ideas. First, we use Jordan centrality to identify subsets of vertices of each tree whose intersection has a sufficient number of common early vertices. The second idea is that, across multiple time scales, it is possible to approximately determine the labels of vertices that have attached to these early vertices, using the sizes of fringe subtrees. Our analysis includes novel quantitative bounds on the fraction of early vertices that remain central, which are of independent interest in the network archaeology literature.

Figures

Figures reproduced from arXiv: 2606.02472 by the authors.

Figure 1
Figure 1. An illustration of one step in the model. Before this step, the two trees with nodes [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. A simulation of a UA tree with 1000 vertices illustrating Theorem [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. History estimation in random recursive trees: Pointwise approach via iterated Jordan centralities

    math.PR 2026-06 unverdicted novelty 6.0 of 10

    Derives uniform tail bounds for arrival-time estimation error in random recursive trees via Jordan centralities and a refined variant attaining optimal risk order.

Reference graph

Works this paper leans on

20 extracted references · 6 canonical work pages · cited by 1 Pith paper

  1. [1]

    ets arefixedfor all large enoughn. It is then possible to estimate the mean and variance of the separating statistic (1.3), and, if there is enough overlap between the setsA 1 Kj(n) andA 2 Kj(n), we expect the mean of the separating statistic to be smaller for the correlated case. This is because in the independent model, Cov(S 1 Kj(n), S2 Kj(n)) = 0, whi...

    2018

  2. [2]

    Noticing that the mean is smaller when the vertices are the same, we should then take the minimum over a fixed set of vertices of each tree that have at least one vertex in common. As with our previous proof, this is accomplished with the setsA 1 K andA 2 K, which, with good probability, can be thought of as fixed after some large timeM, using (Jog and Lo...

    2017

  3. [3]

    double cycles

    See Appendix A for more details. Another approach to the detection problem is to consider the size of the largest common subtree of the two trees. However, even studying this statistic for two independent UA trees is interesting and challenging; see the forthcoming work by B¨ aumler, Kerriou, Lodewijks, Martin, Powierski, R´ acz, and Sridhar (2026+). •(Pr...

    2026

  4. [4]

    Theorem 2.1.LetT n ∼UA(n)and recall thatA K :=A K(n)denotes the set of theKmost central vertices inT n

    2 Finding early vertices The goal of this section is to prove Corollary 1.6 via the following result, which both implies, and is a more detailed version of Theorem 1.5 from Section 1.2. Theorem 2.1.LetT n ∼UA(n)and recall thatA K :=A K(n)denotes the set of theKmost central vertices inT n. There exists a universal constantC <∞such that for everyK∈N,c >1, a...

    1965

  5. [5]

    Dividing both sides by log(n) proves the result

    2 Kj , where the first equality is because of (3.17), the second equality is because of (a), the second to last inequality is because of (3.18) and the elementary inequality (x+y) 2 ≥x 2 −2|xy| −y 2, and the last inequality follows from (b) and (c). Dividing both sides by log(n) proves the result. To prove Lemma 3.3 (respectively Lemma 3.4) we show that w...

    2018

  6. [6]

    2(0.01α)2 ≤ 40 (ℓ+ 1)(0.01α) 2 ≤ ε 5 , where we have usedK j =K2 j in the first inequality, an easy direct calculation in the second, and (3.19) in the third. Using again that conditional onD, we may apply Lemma 3.1 to (3.24), a union bound and (3.9) witht= log(n) 2/3 imply P(Bc|D)≤ 4 log(n)1/3 ℓX j=0 K2j ≤ ε 5 , where we have used (3.22) and thatn≥min th...

    2018

  7. [7]

    , Rmℓ+1)g(Rm1,

    For the induction step fromℓtoℓ+ 1, the law of total expectation gives that ∞X t=1 E f(R m1, . . . , Rmℓ+1)g(Rm1, . . . , Rmℓ)|Rm1 =t,∩ a∈ADa P(R m1 =t| ∩ a∈A Da). 36 Conditioned onR m1 =t(and any other events involving timesm≤m 1), the process (R m)m≥m1 evolves like a standard P´ olya urn started withtred balls andr+b+m 1 −tblue at timem 1, so that the i...

    2017

  8. [8]

    Addario-Berry, C

    6 Bibliography L. Addario-Berry, C. Fontaine, R. Khanfir, L.-R. Langevin, and S. Tˆ etu. Optimal root recovery for uniform attachment trees andd-regular growing trees. Preprint available athttps://arxiv. org/abs/2411.18614,

    work page Pith review arXiv

Show all 20 references
  1. [9]

    Ameen and B

    2 T. Ameen and B. Hajek. Aligning Multiple Inhomogeneous Random Graphs: Fundamental Limits of Exact Recovery. Preprint available athttps://arxiv.org/abs/2405.12293,

  2. [10]

    B¨ aumler, C

    1 38 J. B¨ aumler, C. Kerriou, B. Lodewijks, J. Martin, E. Powierski, M. Z. R´ acz, and A. Sridhar. On the largest common subtree of uniform attachment trees. In preparation, 2026+. 10 J. Bj¨ orklund, C. Holmgren, S. Janson, and T. Y. Y. Lo. Approximation of subgraph counts in...

    2026

  3. [11]

    2 G. Chen, J. Ding, S. Gong, and Z. Li. A computational transition for detecting correlated stochastic block models by low-degree polynomials.Ann. Statist., 54(1):226–251, 2026a. 2 G. Chen, J. Ding, S. Gong, and Z. Li. Detecting correlation efficiently in very supercritical st...

    2026

  4. [12]

    Cullina and N

    2 D. Cullina and N. Kiyavash. Exact alignment recovery for correlated Erd˝ os-R´ enyi graphs. Preprint available athttps://arxiv.org/abs/1711.06783,

    arXiv

  5. [13]

    Ganassali, L

    2 L. Ganassali, L. Massouli´ e, and M. Lelarge. Impossibility of Partial Recovery in the Graph Align- ment Problem. InProceedings of the 34th Conference on Learning Theory (COLT), volume 134 ofProceedings of Machine Learning Research (PMLR), pages 2080–2102,

  6. [14]

    2, 5, 7, 8, 23, 29 R. C. Josifov, L. Devroye, and G. Lugosi. A study of centrality measures in random recursive trees. Preprinthttps://arxiv.org/abs/2603.19493,

  7. [15]

    2, 5, 6, 7 V

    URLhttps://doi.org/10.1214/19-EJP268. 2, 5, 6, 7 V. Lyzinski. Information Recovery in Shuffled Graphs via Graph Matching.IEEE Transactions on Information Theory, 64(5):3254–3273,

    doi

  8. [16]

    doi: 10.1109/SP.2009.22. 1 M. Newman.Networks. Oxford University Press, 07

    2009 doi

  9. [17]

    2 M. Z. R´ acz and A. Sridhar. Matching Correlated Inhomogeneous Random Graphs using thek-core Estimator. InProc. of the 2023 IEEE International Symposium on Information Theory,

    2023

  10. [18]

    Yang and H

    2 J. Yang and H. W. Chung. Graph Matching in Correlated Stochastic Block Models for Improved Graph Clustering. InProceedings of the 2023 59th Annual Allerton Conference on Communica- tion, Control, and Computing (Allerton), pages 1–8. IEEE,

    2023

  11. [19]

    2 . (A.3) Asymptotic normality.Well-established results on stochastic approximation such as Fabian (1968) and Hernandez and Spall (2019) allow us to characterize the limiting distribution of the iterates|S 11(n)|/n,|S 1×(n)|/n, and|S ×1(n)|/n. By applying known results to the ...

    1968

  12. [20]

    44 The form of the matrixQis computed based on the stochastic approximation results of Hernandez and Spall (2019)

    12(4−α)(3−α) 2(5−2α) Q11 =− (1−α)(2α 3 −23α 2 + 105α−192) 12(4−α)(3−α) 2(5−2α) . 44 The form of the matrixQis computed based on the stochastic approximation results of Hernandez and Spall (2019). At a high level, the calculation first involves computing the covariance matrix o...

    2019

Pith tools

Reviewed June 28, 2026 · model on record in the stance chip above.