Inference on the History of a Randomly Growing Tree



  1. Jean-Gabriel YoungMay 21st, 2020 at 08:44 pm

    Prof. Xu,

    Thank you very much updating the references so quickly. I agree, your frequentist perspective is indeed complementary, I will follow this line of research closely with interest.

    All the best,

  2. Min XuMay 21st, 2020 at 03:19 pm

    Dear Jean-Gabriel,

    Thank you very much for bringing this to our attention! We were not aware of these independent lines of work in the physics and CS community. We approach the problem from a Frequentist inference perspective but agree that this other work by you and others is very relevant. We have edited the paper to properly cite and attribute the references that you have listed.

  3. Jean-Gabriel YoungMay 20th, 2020 at 12:45 am

    (Apologize for the comments, I meant to upload as a report.. getting the hang of this platform!)

  4. Jean-Gabriel YoungMay 20th, 2020 at 12:34 am

    Thanks for the upload.

    My main comment is that the literature review is inadequate. Quite a few of the methods and results are given elsewhere.

    The forward sampling algorithm (Sec. 4.1.1) is already derived by my collaborators and I in The importance sampling algorithm (Sec. 4.2) is given, again by myself and co-authors, in In fact, we use a slight generalization and use adaptive resampling, to improve convergence. This second algorithm builds explicitly on the work of Bloem-Reddy and Orbanz: who introduced a sequential Monte-Carlo method for a random-walk based model of growth. They themselves built on earlier work by Wiuf (2006):

    A notion equivalent to shape exchangeability is introduced by Timar et al. in They call it the "equiprobable sequence property," and show that a few other models have this property, including shifted PA trees and negative linear preferential attachment trees. And this notation was used before, say in Bubek's work as well as our own (c.f. appendix B of Drmota, in his 2009 book, uses the fact that PA and linear attachment trees are “shape-exchangeable” many times — although it is not phrased as an exchangeability principle.

    Finally, there are also some methods in this space, in CS, by Magner, Sreedharan, Grama, and Szpankowski. They looked mainly at:

    I’d recommend looking at the introduction of this paper by myself and collaborators goes in some length reviewing this literature.

    On the topic of contact tracing data. There is an interesting subtlety here. The tree inference methods are appropriate if we believe that the contact trace grows "in a vacuum." However, it is reasonable to believe that an epidemic trace unfolds on a network. And as a result, the transitions are rate-limited by the latent degree of a node. Someone who self-isolates can never "grow" an out-going edge. Lohkov, Mézard, Ohta, and Zdeborová (2014) introduce a dynamical message-passing approach that accounts for this latent graph I have not done systematic testing, but I believe that one will obtain different inferences once the rate-limits are taken into account.

Add to the Conversation


The spread of infectious disease in a human community or the proliferation of fake news on social media can be modeled as a randomly growing tree-shaped graph. The history of the random growth process is often unobserved but contains important information such as thesource of the infection. We consider the problem of statistical inference on aspects of the latent history using only a single snapshot of the final tree. Our approach is to apply random labels to the observed unlabeled tree and analyze the resulting distribution of the growth process, conditional on the final outcome. We show that this conditional distribution is tractable under a shape-exchangeability condition, which we introduce here, and that this condition is satisfied for many popular models for randomly growing trees such as uniform attachment, linear preferential attachment and uniform attachment on a D-regular tree. For inference of the rootunder shape-exchangeability, we propose computationally scalable algorithms for constructing confidence sets with valid frequentist coverage as well as bounds on the expected size of the confidence sets. We also provide efficient sampling algorithms which extend our methods to a wide class of inference problems.


➤  Version 1 (2020-05-14)


Harry Crane and Min Xu (2020). Inference on the History of a Randomly Growing Tree. Researchers.One,

© 2018-2020 Researchers.One