Pith. sign in

REVIEW 3 major objections 3 minor 2 cited by

Optimal root recovery for uniform attachment trees and $d$-regular growing trees

T0 review · 3 major / 3 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read This paper proves that the optimal root-finding algorithm can return a candidate set of size $\\exp(O(\\sqrt{\\log(1/\\varepsilon)}))$ while keeping failure probability below $\\varepsilon$ for uniform attachment and $d$-regular growing…

desk verdict The main result is very likely correct and the proof machinery is impressive, but the theorems assert all-n bounds while the written proofs only establish limsup bounds, so the paper needs a revision before the claims as stated are reliable. read the letter →

arxiv 2411.18614 v2 pith:CRRIHP2J submitted 2024-11-27 cs.DS cs.SImath.PRmath.STstat.TH

Louigi Addario-Berry , Catherine Fontaine , Robin Khanfir , Louis-Roy Langevin , Simone Têtu This is my paper · ORCID
classification cs.DScs.SImath.PRmath.STstat.TH MSC 60C0505C8062M0594C15
keywords uniformattachmenttreerandomrecursiverumorcentralityrootreconstructionnetworkarchaeologyd-regulargrowingcompetitiveratioPólyaurn
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

This paper aims to settle the size–error tradeoff for root finding in uniform attachment trees and $d$-regular growing trees. It proves that the centrality-based algorithm that outputs the nodes with the smallest product-of-subtree-sizes needs at most $K=C_*\\exp(c_*\\sqrt{\\log(1/\\varepsilon)})$ nodes to contain the true root with probability at least $1-\\varepsilon$, for every tree size $n$. Because an earlier lower bound [7] showed no algorithm can use substantially fewer nodes, this identifies the optimal candidate-set size up to constant factors and answers the open question posed there. For $d$-regular uniform attachment trees the same rate holds, improving the earlier $O(1/\\varepsilon)$ bound [15]; the paper also sketches how to remove the $d$-dependence of the constant in the exponential.

What carries the argument

The argument is carried by three quantitative ingredients. First, the 'heavy' nodes—those whose rooted subtree contains at least a third of the tree—have exponentially decaying depth/weight tails (Lemma 3.3 and Lemma 4.2). Second, the competitive ratio $\\Phi(T)=\\varphi_T(\\emptyset)/\\min_u\\varphi_T(u)$ has polynomial upper tails (Proposition 3.6 and Proposition 4.7). Third, inside any small subtree the number of nodes more central than the root is $\\exp(O(\\sqrt{\\log\\Phi(T)}))$ (Proposition 3.5) in the deterministic $d$-ary setting, and a probabilistic analogue (Proposition 4.5) in the unbounded-degree UA setting. The counting uses a 'preflow' $p(u)=|\\theta_u T|/|T|$ compared with the geometrically decaying flow $\\gamma(u)=\\alpha^{-\\sum_i(u_i-1)}$; the count $N_x(\\gamma)$ is controlled by a non-asymptotic partition-counting bound [12]. In the UA case the random flow coming from a Pólya-urn representation is stochastically dominated by such a geometric flow through an explicit random bijection, and the multiplicities behave like Geometric random variables in the number of non-first-born ancestors.

What would settle it

Run the centrality algorithm on uniform attachment trees of many sizes n for fixed epsilon and the constants C*, c*; if any single n yields a failure probability above epsilon (within simulation error), the theorem's 'for all n' statement fails. The analogous check for d-regular trees settles Theorem 1.2.

Watch

Extended reading notes

Core claim

The paper's central claim is that the lower bound from [7] is tight. Define the centrality $\\varphi_T(u)=\\prod_{v\\ne u}|(T,u)_{v\\downarrow}|$; the algorithm $A_k$ returns the $k$ nodes of smallest $\\varphi_T$. The paper shows that for $K=C_*\\exp(c_*\\sqrt{\\log(1/\\varepsilon)})$, we have $\\mathbb{P}(\\emptyset\\notin A_K(T_n))\\le\\varepsilon$ for every $n$, both when $T_n\\sim\\mathrm{UA}(n)$ (Theorem 1.1) and when $T_n\\sim\\mathrm{UA}_d(n)$ (Theorem 1.2, with constants depending on $d$, and a sketched argument for a universal constant). Since $A_k$ is known [10] to have minimal error among size-$k$ algorithms, the size of the candidate set is optimal up to constants. The proof works by bounding the random set $B_n=\\{v:\\varphi_{T_n}(v)\\le\\varphi_{T_n}(\\emptyset)\\}$ of nodes at least as central as the root.

Load-bearing premise

The load-bearing premise is that the bounds proved only in the limit as the tree size goes to infinity can be applied to every individual tree size; the paper does not supply the argument that would rule out isolated intermediate sizes where the failure probability spikes above the tolerance.

Editorial extensions

If this is right

  • If Theorem 1.1 is correct, the size–error tradeoff for uniform attachment trees is known: no algorithm can beat $\\exp(\\Omega(\\sqrt{\\log(1/\\varepsilon)}))$ and $A_K$ achieves $\\exp(O(\\sqrt{\\log(1/\\varepsilon)}))$, up to constants.
  • The same rate for $d$-regular uniform attachment trees shows the earlier $O(1/\\varepsilon)$ confidence sets are far from optimal, and the near-optimal size is achieved by the same centrality ranking.
  • The tail bounds for the competitive ratio and for the depth/weight of heavy subtrees are model facts that can be reused when analyzing other inference tasks on these trees.
  • Because $A_k$ is optimal among size-$k$ algorithms, the result identifies the minimax candidate-set size, not just the performance of one heuristic.

Reading between the lines

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

  • The proofs are mostly asymptotic in nature; if one wants a fully uniform-in-$n$ theorem, the missing step would be to control the rate at which subtree proportions converge to their Pólya-urn limits, so intermediate-$n$ spikes in failure probability are not ruled out by the written argument.
  • The same proof template—exponential tails for heavy subtrees, polynomial tails for a competitive ratio, and a flow-counting bound—may transfer to other growing-tree models whose subtree proportions are built from independent stick-breaking variables; testing it on preferential attachment would be a concrete next step.
  • If the sketched removal of the $d$-dependence in Theorem 1.2 is filled in, the same bound with a universal constant would hold for all $d\\ge 3$ simultaneously, giving a single algorithm whose candidate-set size does not degrade with degree.
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

3 major / 3 minor

Summary. The paper studies root-finding for two families of random trees: uniform attachment (UA) and d-regular uniform attachment (UAd). For the centrality-based algorithm A_k of Bubeck, Devroye and Lugosi, it claims that an output set of size K(eps)=C* exp(c* sqrt(log(1/eps))) recovers the root with probability at least 1-eps, uniformly in the tree size n, for UA(n); an analogous statement holds for UAd(n) with d-dependent constants. The proof strategy is to bound the number of nodes at least as central as the root by combining a deterministic bound on the competitive ratio, a deterministic or probabilistic count of 'competitors' in small subtrees, and a tail bound for the count set N_x(P) built from the asymptotic subtree proportions P_u. The paper also sketches an argument to make the UAd constants independent of d.

Significance. If the main upper bounds are correct, Theorem 1.1 resolves the open question from Bubeck, Devroye and Lugosi (2017) by matching their lower bound up to the constant in the exponent. The paper's technical machinery, especially the nested Polya-urn description of subtree proportions (Propositions 3.1 and 4.1), the flow-counting bound (Proposition 2.4), and the probabilistic tail bound for N_x(P) (Proposition 4.5), is substantial and likely to be useful beyond this paper. The authors are careful with distributional identities and do not fit parameters to data; the lower bound for UA is external, and the optimality theorem of Crane and Xu is used as a black box. The main reservation is that both main theorems are stated for every n, while the written proofs deliver only limsup estimates.

major comments (3)
  1. [Section 4.4 (Proof of Theorem 1.1)] The proof establishes only limsup bounds, not the stated all-n bound. Equations (4.7) and (4.8) are limsup estimates, and the final displayed inequality is of the form limsup_n P(|B_n| >= ...) <= (8+C)eps. The theorem asserts P(root not in A_K(T_n)) <= eps for every n. The passage from finite-n subtree counts to the limiting quantities P_u relies on almost-sure convergence |theta_u T_n|/n -> P_u, so the limsup bound holds only for n >= n_0(eps); no quantitative rate or monotonicity is supplied, and the intermediate values K(eps) < n < n_0(eps) are uncontrolled. The text explicitly says it avoids proving rate-of-convergence bounds, which confirms that this is not merely a presentational issue.
  2. [Section 1.1 (Proof of Theorem 1.2)] The proof of Theorem 1.2 concludes an all-n probability bound from Lemma 3.3 and Proposition 3.6, but both are stated only as limsup bounds. In the displayed computation P(|B_n| >= ...) <= P(D >= log_{3/2}(1/eps)) + P(Phi(T_n) >= eps^{-1/a}), the two summands are limsup bounds, not uniform-in-n bounds. The random time n_0 in the proof of Proposition 3.6 depends on almost-sure convergence of |theta_u T_n|/n to P_u, and no quantitative control is given. Thus Theorem 1.2, as stated for all n in N_1, is not derived.
  3. [Section 1, paragraph after Theorem 1.2] The optimality claim for the d-regular model, namely that 'the bound in Theorem 1.2 is optimal up to the value of c_d^*', is supported only by a reference to an adaptation of a construction from [7] whose details are omitted. Since the lower bound in [7] is for the UA model, not for UAd, this is not a direct citation. The theorem's optimality assertion is therefore not established in the manuscript. Please either provide the construction or modify the claim.
minor comments (3)
  1. [Section 4.5] The text contains the typo 'Lemmma 4.9'; it should read 'Lemma 4.9'.
  2. [Section 4.5] The text refers to 'Remark 3.4', but Section 3.4 is not a remark; the cross-reference should be corrected.
  3. [Proof of Proposition 4.5] The constant c is reused with different meanings in Lemma 4.6, Proposition 2.4, and the final inequality of Proposition 4.5; using distinct labels such as c_1, c_2, c_3 consistently would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the upper bounds are derived from in-paper probabilistic estimates and independent external results, not from the paper's own conclusion.

full rationale

The derivation chain is self-contained with respect to the claims it proves. Theorem 1.1 bounds the size of the set B_n of nodes at least as central as the root using deterministic properties of the centrality measure (Lemmas 2.2-2.4), the Pólya-urn asymptotics of uniform attachment (Proposition 4.1), a probabilistic bound on the number of competitors in small subtrees (Proposition 4.5), and a polynomial tail for the competitive ratio (Proposition 4.7), all proved in the paper from standard urn, Dirichlet, Beta, and Hardy-Ramanujan partition facts. The external inputs invoked for context and optimality are Bubeck-Devroye-Lugosi [7] and Crane-Xu [10]; these are independent published results, not self-citations, and neither is used to define the target bound. No parameter is fitted to data and no prediction is a renamed input: the size K(epsilon) is constructed from the constants in the proof, and the lower bound comes from an external construction. The only notable issue is that Section 4.4 proves limsup bounds (e.g., limsup_n P(|B_n| >= ...) <= (8+C)epsilon) and then asserts the all-n bound of Theorem 1.1; that is a quantitative proof-strength gap, not a circular reduction, because the asserted result is not assumed or encoded in the hypotheses. Accordingly, no circular step reaches the threshold required for a nonzero score.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No free parameters are fitted to data; the paper is a pure proof. It relies on standard urn, Dirichlet, partition, and branching-process facts, and on two external results: the known lower bound and the optimality of A_k. Proof devices such as the Q-flow and the map chi are internal mathematical constructions, not independently evidenced physical entities.

assumptions (6)
  • standard math Almost sure convergence of Polya urns to Dirichlet limits
    Used in Sections 3.1 and 4.1 to define asymptotic subtree proportions P_u and their distributions.
  • standard math Erdos non-asymptotic Hardy-Ramanujan bound on the number of integer partitions
    Used in Proposition 2.4 to bound the number of nodes in geometrically decaying preflows.
  • standard math Beta stochastic domination criterion
    Used in Proposition 3.8 to bound the tail of the maximum Dirichlet component.
  • domain assumption Uniform attachment model definitions, UA and UA_d
    Theorems 1.1 and 1.2 are stated for these specific growing-tree models, which are not derived from anything more basic.
  • domain assumption Crane-Xu optimality theorem for A_k
    Used to describe A_k as the optimal algorithm among size-k algorithms; cited as [10, Theorem 3] and not reproved.
  • domain assumption Bubeck-Devroye-Lugosi lower bound for uniform attachment trees
    Used to assert that the new upper bound is sharp; cited as [7] and not reproved.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimal root recovery for uniform attachment trees and $d$-regular growing trees." pith.science (2026). https://pith.science/paper/CRRIHP2J

@misc{pith2026241118614,
  author       = {Pith},
  title        = {Pith review of: Optimal root recovery for uniform attachment trees and $d$-regular growing trees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CRRIHP2J}},
  note         = {Machine review of arXiv:2411.18614}
}
abstract

We consider root-finding algorithms for random rooted trees grown by uniform attachment. Given an unlabeled copy of the tree and a target accuracy $\varepsilon > 0$, such an algorithm outputs a set of nodes that contains the root with probability at least $1 - \varepsilon$. We focus on the algorithm introduced by Bubeck, Devroye and Lugosi (2017) and proved to be optimal by Crane and Xu (2021). We prove that, for the optimal algorithm, an output set of size $\exp(O(\log^{1/2}(1/\varepsilon)))$ suffices; this bound is sharp and answers a question of Bubeck, Devroye and Lugosi (2017). We prove similar bounds for random regular trees that grow by uniform attachment, strengthening a result of Khim and Loh (2017).

Figures

Figures reproduced from arXiv: 2411.18614 by the authors.

Figure 1
Figure 1. Illustration of the map χ and of the variables Zu. The colour of each edge indicates the ratios of the values taken by the flow between the upper-end and the lower-end of the edge. Two vertices a and b are marked in the tree at the top. In the tree at the bottom, three nodes have a as their χ-image (marked with squares), meaning that Za = 3. Four nodes have b as their χ-image (marked with triangles), meaning that Zb… view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

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

  1. Finding Adam in noisy trees

    math.PR 2026-07 conditional novelty 7.0 of 10

    A uniform random recursive tree polluted by an Erdős–Rényi graph with p=o(log n/n) still admits a root confidence set of size depending only on ε, not on n.

  2. Subcritical percolation and network archaeology on random recursive tree substrate networks

    math.PR 2026-07 accept novelty 5.0 of 10

    For random recursive trees with independent Erdős–Rényi shortcut edges, subcritical bond percolation exposes a decorated tree structure on which Jordan centrality recovers the root within a deterministic-size confidence set.

Reference graph

Works this paper leans on

19 extracted references · 14 canonical work pages · cited by 2 Pith papers

  1. [7]

    Finding Adam in random growing trees

    S´ ebastien Bubeck, Luc Devroye, and G´ abor Lugosi. Finding Adam in random growing trees. Random Structures & Algorithms , 50(2):158 – 172, 2017. doi: https://doi.org/10.1002/rsa.20649. URL https://onlinelibrary.wiley.com/doi/ abs/10.1002/rsa.20649

    doi:10.1002/rsa.20649 2017

  2. [1]

    Convex transform order of beta distributions with some consequences

    Idir Arab, Paulo Eduardo Oliveira, and Tilo Wiklund. Convex transform order of beta distributions with some consequences. Statistica Neerlandica, 75(3):238 – 256, 2021. doi: https://doi.org/10.1111/stan.12233. URL https://onlinelibrary. wiley.com/doi/abs/10.1111/stan.12233

    work page doi:10.1111/stan.12233 2021

  3. [2]

    Krishna B. Athreya. On a characteristic property of P´ olya’s urn. Studia Sci. Math. Hungar, 4:31 –– 35, 1969

    work page 1969

  4. [3]

    Root finding algorithms and persistence of Jordan centrality in growing random trees

    Sayan Banerjee and Shankar Bhamidi. Root finding algorithms and persistence of Jordan centrality in growing random trees. The Annals of Applied Probability , 32 (3):2180 – 2210, 2022. doi: 10.1214/21-AAP1731. URL https://doi.org/10.1214/ 21-AAP1731

    work page doi:10.1214/21-aap1731 2022

  5. [4]

    Degree centrality and root finding in growing random networks

    Sayan Banerjee and Xiangying Huang. Degree centrality and root finding in growing random networks. Electronic Journal of Probability , 28(none):1 – 39, 2023. doi: 10.1214/23-EJP930. URL https://doi.org/10.1214/23-EJP930

    work page doi:10.1214/23-ejp930 2023

  6. [5]

    Archaeology of random recursive dags and cooper-frieze random networks

    Simon Briend, Francisco Calvillo, and G´ abor Lugosi. Archaeology of random recursive dags and cooper-frieze random networks. Combinatorics, Probability and Computing , 32(6):859 –– 873, 2023. doi: 10.1017/S0963548323000184

    work page doi:10.1017/s0963548323000184 2023

  7. [6]

    S´ ebastien Bubeck, Elchanan Mossel, and Mikl´ os Z. R´ acz. On the influence of the seed graph in the preferential attachment model. IEEE Transactions on Network Science and Engineering, 2(1):30 – 39, 2015. doi: 10.1109/TNSE.2015.2397592

    work page arXiv 2015

  8. [8]

    Smoothing Equations for Large P´ olya Urns

    Brigitte Chauvin, C´ ecile Mailler, and Nicolas Pouyanne. Smoothing Equations for Large P´ olya Urns. Journal of Theoretical Probability , 28(3):923 – 957, 09 2015. doi: 10.1007/s10959-013-0530-z. URL https://ideas.repec.org/a/spr/jotpro/ v28y2015i3d10.1007_s10959-013-0530-z.html

    work page doi:10.1007/s10959-013-0530-z 2015

Show all 19 references
  1. [9]

    Eve, Adam and the preferential attachment tree

    Alice Contat, Nicolas Curien, Perrine Lacroix, Etienne Lasalle, and Vincent Rivoirard. Eve, Adam and the preferential attachment tree. Probability Theory and Related Fields, 190:321 – 336, 01 2024. doi: 10.1007/s00440-023-01253-1

    2024 doi

  2. [10]

    Inference on the history of a randomly growing tree

    Harry Crane and Min Xu. Inference on the history of a randomly growing tree. Journal of the Royal Statistical Society Series B: Statistical Methodology , 83(4):639 – 668, 07 2021. ISSN 1369-7412. doi: 10.1111/rssb.12428. URL https://doi.org/10. 1111/rssb.12428

    2021 doi

  3. [11]

    Scaling limits and influence of the seed graph in preferential attachment trees

    Nicolas Curien, Thomas Duquesne, Igor Kortchemski, and Ioan Manolescu. Scaling limits and influence of the seed graph in preferential attachment trees. Journal de l’ ´Ecole polytechnique — Math´ ematiques, 2:1 – 34, 2015. doi: 10.5802/jep.15. URL https://jep.centre-mersenne.or...

    2015 doi

  4. [12]

    On an elementary proof of some asymptotic formulas in the theory of partitions

    Paul Erd¨ os. On an elementary proof of some asymptotic formulas in the theory of partitions. Annals of Mathematics , 43(3):437 – 450, 1942. ISSN 0003486X, 19398980. URL http://www.jstor.org/stable/1968802

    1942

  5. [13]

    Looking for vertex number one

    Alan Frieze and Wesley Pegden. Looking for vertex number one. The Annals of Applied Probability, 27(1):582 – 630, 2017. doi: 10.1214/16-AAP1212. URL https: //doi.org/10.1214/16-AAP1212. OPTIMAL ROOT RECOVERY FOR RANDOM TREES 27

    2017 doi

  6. [14]

    Theodore E. Harris. The Theory of Branching Processes . RAND Corporation, Santa Monica, CA, 1964

    1964

  7. [15]

    Confidence sets for the source of a diffusion in regular trees

    Justin Khim and Po-Ling Loh. Confidence sets for the source of a diffusion in regular trees. IEEE Transactions on Network Science and Engineering , 4(1):27 – 40, 2017. doi: 10.1109/TNSE.2016.2627502

    2017

  8. [16]

    Comparability of special distributions

    Bernd Lisek. Comparability of special distributions. Series Statistics , 9(4):587 – 598, 1978. doi: 10.1080/02331887808801456. URL https://doi.org/10.1080/ 02331887808801456

    1978 doi

  9. [17]

    On the discovery of the seed in uniform attachment trees

    Tommy Reddad and Luc Devroye. On the discovery of the seed in uniform attachment trees. Internet Mathematics , 1(1), 02 2019. doi: 10.24166/im.02.2019

    2019 doi

  10. [18]

    Persistence of hubs in growing random networks

    Banerjee Sayan and Bhamidi Shankar. Persistence of hubs in growing random networks. Probability Theory and Related Fields , 180(3-4):891 – 953, 08 2021. URL https://proxy.library.mcgill.ca/login?url=https://www.proquest.com/ scholarly-journals/persistence-hubs-growing-random-n...

    2021

  11. [19]

    Rumors in a network: Who’s the culprit? IEEE Transactions on Information Theory , 57(8):5163 – 5181, 2011

    Devavrat Shah and Tauhid Zaman. Rumors in a network: Who’s the culprit? IEEE Transactions on Information Theory , 57(8):5163 – 5181, 2011. doi: 10.1109/TIT. 2011.2158885. Department of Mathematics and Statistics, McGill University Email address : louigi.addario@mcgill.ca Email...

    2011

Pith tools

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