Pith. sign in

REVIEW 1 major objections 86 references

Diffusion-Network Alignment: An Efficient Algorithm and Explicit Probability Bounds

T0 review · 1 major / 0 minor · reviewed 2026-06-27 · grok-4.3

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

Pith's one-line read An efficient algorithm aligns vertices of a diffusion tree to a network correctly with high probability using correlation tests.

desk verdict The paper defines an asymmetric diffusion-tree to network alignment task and supplies an efficient correlation-test algorithm with explicit depth-dependent probability lower bounds under sparse-regime assumptions. read the letter →

arxiv 2606.12879 v1 pith:TBSW4V3G submitted 2026-06-11 cs.DS math.STstat.MLstat.TH

Ziao Wang , Lei Ying This is my paper · ORCID
classification cs.DSmath.STstat.MLstat.TH
keywords diffusion-networkalignmentnetworkcorrelationtestssparsegraphsprobabilityboundstreematchinggraphalgorithmsinformationasymmetry
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 addresses diffusion-network alignment, where a rooted diffusion tree must be matched to vertices in a larger network. It develops an algorithm that uses tree correlation tests on local neighborhoods to identify correct alignments. In the sparse graph regime, the method ensures that all matched pairs are correct with high probability. Explicit lower bounds are derived for the success probability of each vertex, and these bounds increase for vertices nearer the root of the tree.

What carries the argument

Tree correlation tests applied to local neighborhoods to extract alignment information.

What would settle it

Running the algorithm on a sparse graph instance where the observed matching error rate exceeds the derived lower bounds or fails to approach zero as the graph size grows.

Watch

Extended reading notes

Core claim

The paper presents an efficient algorithm based on tree correlation tests for diffusion-network alignment. It proves that in the sparse graph regime, the algorithm matches all pairs correctly with high probability. For each vertex, it establishes explicit depth-dependent lower bounds on the probability of correct matching, with higher probabilities closer to the root.

Load-bearing premise

The sparse graph regime allows local neighborhoods to provide sufficient information for correct alignment via correlation tests.

Editorial extensions

If this is right

  • All matched pairs are correct with high probability.
  • Each vertex on the diffusion tree has an explicit lower bound on its correct matching probability.
  • These probability bounds are depth-dependent and increase closer to the root.
  • The algorithm is efficient for the alignment task.

Reading between the lines

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

  • The approach may extend to real-world scenarios like aligning contact tracing data to social networks.
  • Prioritizing matches from the root could improve overall alignment accuracy in practice.
  • Testing in denser graph regimes could reveal the limits of the correlation test method.
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

1 major / 0 minor

Summary. The manuscript introduces the diffusion-network alignment problem, which aligns vertices of a rooted diffusion tree (e.g., from a communication trace) to vertices in a host network under information asymmetry. It presents an efficient algorithm based on tree correlation tests applied to local neighborhoods and analyzes its performance in the sparse graph regime, claiming that all matched pairs are correct with high probability. The paper further derives explicit, depth-dependent lower bounds on the per-vertex probability of correct matching, with these bounds increasing for vertices closer to the root.

Significance. If the claims hold, the work supplies an efficient method for a practically relevant variant of network alignment together with explicit (rather than purely asymptotic) probability bounds that vary with tree depth. The explicit per-vertex bounds constitute a concrete strength relative to typical high-probability statements in the literature.

major comments (1)
  1. [Abstract] Abstract (performance analysis paragraph): the central claims of high-probability correctness and explicit depth-dependent lower bounds rest on the assumption that local neighborhoods admit reliable alignment signals via correlation tests in the sparse regime. No quantitative threshold on sparsity parameters (maximum degree, edge probability, etc.) is supplied under which the requisite concentration holds uniformly across depths; if variance of the test statistic grows with depth, the lower bounds may cease to be positive even in a marginally sparse host graph.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for highlighting the need for explicit sparsity conditions in the abstract. We address the comment below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Abstract] Abstract (performance analysis paragraph): the central claims of high-probability correctness and explicit depth-dependent lower bounds rest on the assumption that local neighborhoods admit reliable alignment signals via correlation tests in the sparse regime. No quantitative threshold on sparsity parameters (maximum degree, edge probability, etc.) is supplied under which the requisite concentration holds uniformly across depths; if variance of the test statistic grows with depth, the lower bounds may cease to be positive even in a marginally sparse host graph.

    Authors: We agree that the abstract would be strengthened by an explicit reference to the sparsity thresholds. The body of the paper (Theorems 3–5 and the concentration arguments in Section 4) establishes that the required uniform concentration holds when the host graph is G(n,p) with p = o(1/log n) (or equivalently bounded maximum degree in the sparse regime); under these conditions the local neighborhoods are trees with high probability and the variance of the tree-correlation statistic remains O(1) independent of depth. Consequently the explicit per-vertex lower bounds stay positive for all depths. We will add a concise clause to the abstract performance paragraph that points to these conditions. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity detected

full rationale

The paper introduces an algorithm using tree correlation tests for diffusion-network alignment and derives explicit performance guarantees (high-probability correct matching and depth-dependent per-vertex probability lower bounds) under stated sparse-regime model assumptions about extractable local alignment signals. No quoted steps reduce by construction to inputs: there are no self-definitional loops, fitted parameters renamed as predictions, load-bearing self-citations, uniqueness theorems imported from prior author work, smuggled ansatzes, or renamings of known results. The derivation chain is self-contained against the model premises without circular reduction.

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

The central claims rest on the diffusion-network alignment model definition and the sparse graph regime assumption that enables local neighborhood correlation tests to extract alignment information; these are domain assumptions not detailed beyond the abstract.

assumptions (2)
  • domain assumption The diffusion tree is generated from the underlying network such that local neighborhoods contain alignment information extractable via correlation tests.
    Implicit in the problem setup and algorithm description in the abstract.
  • domain assumption Analysis holds in the sparse graph regime.
    Explicitly stated as the setting for the performance guarantees in the abstract.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Diffusion-Network Alignment: An Efficient Algorithm and Explicit Probability Bounds." pith.science (2026). https://pith.science/paper/TBSW4V3G

@misc{pith2026260612879,
  author       = {Pith},
  title        = {Pith review of: Diffusion-Network Alignment: An Efficient Algorithm and Explicit Probability Bounds},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TBSW4V3G}},
  note         = {Machine review of arXiv:2606.12879}
}
read the original abstract

This paper studies a variation of the classic network alignment problem, named diffusion-network alignment. The goal is to align the vertices of a rooted diffusion tree to the vertices of a network, where the diffusion tree could be from a communication trace or contact tracing, and the network could be an online or offline social network. Different from the classic network alignment where both networks are fully observed, this model captures the information asymmetry of two networks. To solve this problem, this paper presents an efficient algorithm based on tree correlation tests to extract alignment information from local neighborhoods. We analyze the performance of the algorithm in the sparse graph regime and show that with high probability, all matched pairs are correct. Furthermore, for each vertex on the diffusion tree, this paper establishes an explicit lower bound on the probability that the vertex is correctly matched. These lower bounds are depth-dependent and increase as vertices get closer to the root.

Figures

Figures reproduced from arXiv: 2606.12879 by the authors.

Figure 1
Figure 1. An example of the IC model and its corresponding diffusion tree. [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Illustration of the four matching criteria. [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. An example of the sequence (pd)d≥0. The parameters are set to λ = 4, s = q = 0.7 and ϵ ′ = 0.1 in the example. With the sequence (pd)d≥0 in hand, we are now ready to state the performance guarantee of the proposed algorithm. Recall that Mu is the set of matching candidates for vertex u in T IC that Algorithm 1 outputs. Accordingly, for an individual vertex v, the event Mv = {π ∗ (v)} means that v is correctly matche… view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: Intersection patterns of the two paths corresponding to cases (i), (ii) and (iii). The desired path [PITH_FULL_IMAGE:figures/full_fig_p022_4.png]
Figure 5
Figure 5. Figure 5: Two examples of the overlap between p and p ′ . In both examples, we take k = d = 6. On the left-hand side, we have d ∗ = 4. The three black vertices are shared by p and p ′ , and the red (resp. blue) vertices are exclusive to p (resp. p ′ ). The union graph Hp,p′ is c…
Figure 6
Figure 6. Figure 6: An illustration of the notations defined. The vertex with index [PITH_FULL_IMAGE:figures/full_fig_p035_6.png]
Figure 7
Figure 7. Figure 7: An illustration of the events we defined. In the figure, the black (resp. red and blue) vertices are from the set [PITH_FULL_IMAGE:figures/full_fig_p047_7.png]
Figure 8
Figure 8. Figure 8: Illustration of events defined above. In the figure, the conditioned graph [PITH_FULL_IMAGE:figures/full_fig_p056_8.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

86 extracted references · 6 canonical work pages

  1. [1]

    De-anonymizing social networks,

    A. Narayanan and V . Shmatikov, “De-anonymizing social networks,” inProc. IEEE Symp. Security and Privacy. Oakland, CA, USA: IEEE, 2009, pp. 173–187

    2009

  2. [2]

    An efficient reconciliation algorithm for social networks,

    N. Korula and S. Lattanzi, “An efficient reconciliation algorithm for social networks,”Proc. VLDB Endow., vol. 7, no. 5, p. 377–388, Jan. 2014

    2014

  3. [3]

    Pairwise global alignment of protein interaction networks by matching neighborhood topology,

    R. Singh, J. Xu, and B. Berger, “Pairwise global alignment of protein interaction networks by matching neighborhood topology,” inAnnual International Conference on Research in Computa- tional Molecular Biology. Berlin, Heidelberg: Springer, 2007, pp. 16–31

    2007

  4. [4]

    Robust textual inference via graph matching,

    A. D. Haghighi, A. Y . Ng, and C. D. Manning, “Robust textual inference via graph matching,” inHuman Lang. Technol. and Empirical Methods in Natural Lang. Process.Vancouver, British Columbia, Canada: Association for Computational Linguistics, 2005, p. 387–394

    2005

  5. [5]

    On the privacy of anonymized networks,

    P. Pedarsani and M. Grossglauser, “On the privacy of anonymized networks,” inProc. Ann. ACM SIGKDD Conf. Knowledge Discovery and Data Mining (KDD). New York, NY , USA: Association for Computing Machinery, 2011, pp. 1235–1243

    2011

  6. [6]

    Improved achievability and converse bounds for Erd ˝os-R´enyi graph matching,

    D. Cullina and N. Kiyavash, “Improved achievability and converse bounds for Erd ˝os-R´enyi graph matching,”ACM SIGMETRICS Perform. Evaluation Rev., vol. 44, no. 1, pp. 63–72, 2016

    2016

  7. [7]

    Exact alignment recovery for correlated Erd\H{o}s-R\'enyi graphs

    ——, “Exact alignment recovery for correlated Erd ˝os-R´enyi graphs,”arXiv preprint arXiv:1711.06783, 2017

    work page Pith review arXiv 2017

  8. [8]

    Settling the sharp reconstruction thresholds of random graph matching,

    Y . Wu, J. Xu, and S. H. Yu, “Settling the sharp reconstruction thresholds of random graph matching,” IEEE Trans. Inf. Theory, vol. 68, no. 8, pp. 5391–5417, 2022

    2022

Show all 86 references
  1. [9]

    Matching recovery threshold for correlated random graphs,

    J. Ding and H. Du, “Matching recovery threshold for correlated random graphs,”The Annals of Statistics, vol. 51, no. 4, pp. 1718–1743, 2023

    2023

  2. [10]

    The number of trees,

    R. Otter, “The number of trees,”Annals of Mathematics, vol. 49, no. 3, pp. 583–599, 1948

    1948

  3. [11]

    Random graph matching at otter’s threshold via counting chandeliers,

    C. Mao, Y . Wu, J. Xu, and S. H. Yu, “Random graph matching at otter’s threshold via counting chandeliers,”Operations Research, vol. 74, no. 1, pp. 430–445, 2026. [Online]. Available: https://doi.org/10.1287/opre.2023.0574

    2026 doi

  4. [12]

    Correlation detection in trees for planted graph alignment,

    L. Ganassali, M. Lelarge, and L. Massouli ´e, “Correlation detection in trees for planted graph alignment,”The Annals of Applied Probability, vol. 34, no. 3, pp. 2799 – 2843, 2024

    2024

  5. [13]

    Statistical limits of correlation detection in trees,

    L. Ganassali, L. Massouli ´e, and G. Semerjian, “Statistical limits of correlation detection in trees,” The Annals of Applied Probability, vol. 34, no. 4, pp. 3701–3734, 2024

    2024

  6. [14]

    Algorithmic contiguity from low-degree conjecture and applications in correlated random graphs,

    Z. Li, “Algorithmic contiguity from low-degree conjecture and applications in correlated random graphs,” inApproximation, Randomization, and Combinatorial Optimization. Algorithms and Tech- niques (APPROX/RANDOM 2025). Schloss Dagstuhl–Leibniz-Zentrum f ¨ur Informatik, 2025, pp. 30–1

    2025

  7. [15]

    Maximizing the spread of influence through a social network,

    D. Kempe, J. Kleinberg, and E. Tardos, “Maximizing the spread of influence through a social network,” inProceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ser. KDD ’03. New York, NY , USA: Association for Computing Machinery, 2...

    2003 doi

  8. [16]

    Asymmetric graph alignment and the phase transition for asymmetric tree correlation testing,

    J. Maier and L. Massouli ´e, “Asymmetric graph alignment and the phase transition for asymmetric tree correlation testing,”arXiv preprint arXiv:2504.02299, 2025

    2025

  9. [17]

    Ix. on the problem of the most efficient tests of statistical hypotheses,

    J. Neyman and E. S. Pearson, “Ix. on the problem of the most efficient tests of statistical hypotheses,” Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character, vol. 231, no. 694-706, pp. 289–337, 1933

    1933

  10. [18]

    E. L. Lehmann and J. P. Romano,Testing statistical hypotheses. Springer, 2005. 15

    2005

  11. [19]

    Frieze and M

    A. Frieze and M. Karo ´nski,Introduction to random graphs. Cambridge University Press, 2015

    2015

  12. [20]

    Optimal recovery of correlated erd ˝os–r´enyi graphs,

    H. Du, “Optimal recovery of correlated erd ˝os–r´enyi graphs,”arXiv preprint arXiv:2502.12077, 2025

    2025

  13. [21]

    Partial recovery of erd ˝os-r´enyi graph alignment via k-core alignment,

    D. Cullina, N. Kiyavash, P. Mittal, and H. V . Poor, “Partial recovery of erd ˝os-r´enyi graph alignment via k-core alignment,”Proceedings of the ACM on Measurement and Analysis of Computing Systems, vol. 3, no. 3, pp. 1–21, 2019

    2019

  14. [22]

    Impossibility of partial recovery in the graph alignment problem,

    L. Ganassali, L. Massoulie, and M. Lelarge, “Impossibility of partial recovery in the graph alignment problem,” inProceedings of Thirty Fourth Conference on Learning Theory, ser. Proceedings of Machine Learning Research, vol. 134. PMLR, 15–19 Aug 2021, pp. 2080–2102

    2021

  15. [23]

    Partial recovery in the graph alignment problem,

    G. Hall and L. Massouli ´e, “Partial recovery in the graph alignment problem,”Operations Research, vol. 71, no. 1, pp. 259–272, 2023

    2023

  16. [24]

    Spectral graph matching and regularized quadratic relaxations: Algorithm and theory,

    Z. Fan, C. Mao, Y . Wu, and J. Xu, “Spectral graph matching and regularized quadratic relaxations: Algorithm and theory,” inProceedings of the 37th International Conference on Machine Learning, ser. Proceedings of Machine Learning Research, vol. 119. PMLR, 13–18 Jul 2020, pp. ...

    2020

  17. [25]

    Analysis of a canonical labeling algorithm for the alignment of correlated erd ˝os-r´enyi graphs,

    O. Dai, D. Cullina, N. Kiyavash, and M. Grossglauser, “Analysis of a canonical labeling algorithm for the alignment of correlated erd ˝os-r´enyi graphs,”ACM SIGMETRICS Perform. Evaluation Rev., vol. 47, pp. 96–97, 12 2019

    2019

  18. [26]

    Exact matching of random graphs with constant correlation,

    C. Mao, M. Rudelson, and K. Tikhomirov, “Exact matching of random graphs with constant correlation,”Probability Theory and Related Fields, vol. 186, no. 1-2, pp. 327–389, 2023

    2023

  19. [27]

    A polynomial-time iterative algorithm for random graph matching with nonvanishing correlation,

    J. Ding and Z. Li, “A polynomial-time iterative algorithm for random graph matching with nonvanishing correlation,”Mathematics of Operations Research, 2025

    2025

  20. [28]

    Exact community recovery in correlated stochastic block models,

    J. Gaudio, M. Z. Racz, and A. Sridhar, “Exact community recovery in correlated stochastic block models,” inConference on Learning Theory. PMLR, 2022, pp. 2183–2241

    2022

  21. [29]

    Efficient graph matching for correlated stochastic block models,

    S. Chai and M. Z. R ´acz, “Efficient graph matching for correlated stochastic block models,”Advances in Neural Information Processing Systems, vol. 37, pp. 116 388–116 461, 2024

    2024

  22. [30]

    Attributed graph alignment,

    N. Zhang, Z. Wang, W. Wang, and L. Wang, “Attributed graph alignment,”IEEE Trans. Inf. Theory, vol. 70, no. 8, pp. 5910–5934, 2024

    2024

  23. [31]

    On the feasible region of efficient algorithms for attributed graph alignment,

    Z. Wang, N. Zhang, W. Wang, and L. Wang, “On the feasible region of efficient algorithms for attributed graph alignment,”IEEE Trans. Inf. Theory, vol. 70, no. 5, pp. 3622–3639, 2024

    2024

  24. [32]

    Efficient algorithms for attributed graph alignment with vanishing edge correlation,

    Z. Wang, W. Wang, and L. Wang, “Efficient algorithms for attributed graph alignment with vanishing edge correlation,”IEEE Transactions on Information Theory, vol. 71, no. 6, pp. 4556–4580, 2025

    2025

  25. [33]

    Exact graph matching in correlated gaussian-attributed erd ˝os-r´enyi model,

    J. Yang and H. W. Chung, “Exact graph matching in correlated gaussian-attributed erd ˝os-r´enyi model,” in2024 IEEE International Symposium on Information Theory (ISIT). IEEE, 2024, pp. 3450–3455

    2024

  26. [34]

    Information-theoretic thresholds for the alignments of partially correlated graphs,

    D. Huang, X. Song, and P. Yang, “Information-theoretic thresholds for the alignments of partially correlated graphs,” inThe Thirty Seventh Annual Conference on Learning Theory. PMLR, 2024, pp. 2494–2518

    2024

  27. [35]

    Aligning multiple inhomogeneous random graphs: Fundamental limits of exact recovery,

    T. Ameen and B. Hajek, “Aligning multiple inhomogeneous random graphs: Fundamental limits of exact recovery,”arXiv preprint arXiv:2405.12293, 2024

    2024

  28. [36]

    Taming verification hardness: an efficient algorithm for testing subgraph isomorphism,

    H. Shang, Y . Zhang, X. Lin, and J. X. Yu, “Taming verification hardness: an efficient algorithm for testing subgraph isomorphism,”Proceedings of the VLDB Endowment, vol. 1, no. 1, pp. 364–375, 2008

    2008

  29. [37]

    Graphs-at-a-time: query language and access methods for graph databases,

    H. He and A. K. Singh, “Graphs-at-a-time: query language and access methods for graph databases,” inProceedings of the 2008 ACM SIGMOD International Conference on Management of Data, ser. SIGMOD ’08. New York, NY , USA: Association for Computing Machinery, 2008, p. 405–418. 16

    2008

  30. [38]

    On the information-theoretic limit of subgraph alignment,

    C. H. M. Shiu, H. V . Cheng, and L. Wang, “On the information-theoretic limit of subgraph alignment,” in2025 IEEE International Symposium on Information Theory (ISIT). IEEE, 2025, pp. 1–6

    2025

  31. [39]

    Cliques in random graphs,

    B. Bollob ´as and P. Erd ¨os, “Cliques in random graphs,” inMathematical Proceedings of the Cambridge Philosophical Society, vol. 80, no. 3. Cambridge University Press, 1976, pp. 419– 427

    1976

  32. [40]

    Finding a large hidden clique in a random graph,

    N. Alon, M. Krivelevich, and B. Sudakov, “Finding a large hidden clique in a random graph,” Random Structures & Algorithms, vol. 13, no. 3-4, pp. 457–466, 1998

    1998

  33. [41]

    Sharp thresholds in inference of planted subgraphs,

    E. Mossel, J. Niles-Weed, Y . Sohn, N. Sun, and I. Zadik, “Sharp thresholds in inference of planted subgraphs,”The Annals of Applied Probability, vol. 35, no. 1, pp. 523–563, 2025

    2025

  34. [42]

    The fundamental limits of recovering planted subgraphs (extended abstract),

    D. Z. Lee, F. Pernice, A. Rajaraman, and I. Zadik, “The fundamental limits of recovering planted subgraphs (extended abstract),” inProceedings of Thirty Eighth Conference on Learning Theory, ser. Proceedings of Machine Learning Research, N. Haghtalab and A. Moitra, Eds., vol. ...

    2025

  35. [43]

    A lower bound for the critical probability in a certain percolation process,

    T. E. Harris, “A lower bound for the critical probability in a certain percolation process,” in Mathematical Proceedings of the Cambridge Philosophical Society, vol. 56, no. 1. Cambridge University Press, 1960, pp. 13–20

    1960

  36. [44]

    A. Blum, J. Hopcroft, and R. Kannan,Foundations of data science. Cambridge University Press, 2020

    2020

  37. [45]

    Probability inequalities for the sum of independent random variables,

    G. Bennett, “Probability inequalities for the sum of independent random variables,”Journal of the American Statistical Association, vol. 57, no. 297, pp. 33–45, 1962

    1962

  38. [46]

    D. P. Dubhashi and A. Panconesi,Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, 2009

    2009

  39. [47]

    Reconstruction and estimation in the planted partition model,

    E. Mossel, J. Neeman, and A. Sly, “Reconstruction and estimation in the planted partition model,” Probability Theory and Related Fields, vol. 162, pp. 431–461, 2015

    2015

  40. [48]

    The poisson approximation to the poisson binomial distribution,

    J. L. Hodges and L. Le Cam, “The poisson approximation to the poisson binomial distribution,” The Annals of Mathematical Statistics, vol. 31, no. 3, pp. 737–740, 1960. APPENDIXA RELATEDWORK Diffusion-network alignment is closely related to the classic network alignment problem...

    1960

  41. [49]

    Recall the correlated Erd ˝os–R´enyi graph pair model defined in Section II. From the subsampling process of generatingG ′ 1 fromG 1, we know that for each pair of indices(i, j)∈[n]×[n], the pair of edge indicators (G′ 1(i, j), ˜G2(˜i, ˜j))has distribution (G′ 1(i, j), ˜G2(˜i,...

  42. [50]

    Moreover, the canonical order of vertices at each depth in the two trees are defined in the same way

    This shows that for eachd≥0, the set of vertices at depthdofT IC is the same as the set of vertices at depthdofT G′ 1 1 . Moreover, the canonical order of vertices at each depth in the two trees are defined in the same way. Therefore,T IC andT G′ 1 1 choose the same unique par...

  43. [51]

    ,˜z˜t)of length ˜t∈[l]withz 1 =j 1 andz ˜t =xin graph ˜G2

    Similarly, because˜x∈V ˜T \˜j ˜j1 ,l−1 , there exists a path( ˜j,˜z1,˜z2, . . . ,˜z˜t)of length ˜t∈[l]withz 1 =j 1 andz ˜t =xin graph ˜G2. From this we are going to argue that there exists a path (¯p0,¯p1, . . . ,¯p¯t)of length ¯t∈[2l]in ¯Gthat satisfies the following two prop...

  44. [52]

    , d}and depthd∈[d max], P(E c 1 |v∈V d) =O(n −ϵ/3).(15) Lemma 4.Supposeλsq >1

    =O(n −ϵ/3).(14) Moreover, for any vertexv∈ {2, . . . , d}and depthd∈[d max], P(E c 1 |v∈V d) =O(n −ϵ/3).(15) Lemma 4.Supposeλsq >1. We have P(E c

  45. [53]

    , d}and depthd∈[d max], P(E c 2 |v∈V d) = ˜O(n−1/3).(17) We prove these two propositions in the next two subsections respectively

    = ˜O(n−4/3).(16) 24 Moreover, for any vertexv∈ {2, . . . , d}and depthd∈[d max], P(E c 2 |v∈V d) = ˜O(n−1/3).(17) We prove these two propositions in the next two subsections respectively. B. Proof of Lemma 3 We first establish the conditional probability bound in (15). The unc...

  46. [54]

    By Lemma 1, we know thatV ≤d =N G′ 1(1, d)for eachd≥0

    Proof of the conditional probability bound(15):Recall that we defined E1 ={∄i∈V ≤dmax :the2l-neighborhood of ¯iin ¯Gcontains a cycle}. By Lemma 1, we know thatV ≤d =N G′ 1(1, d)for eachd≥0. So we can equivalently writeE 1 as E1 ={∄i∈N G′ 1(1, dmax) :the2l-neighborhood of ¯iin ...

  47. [55]

    For eachk∈ {0, . . . , d max}, define Ak ={|N G′ 1(1, k)| ≤K(λq) k logn} whereK:= λq λq−1 Q∞ h=0(1 + (λq)−h/2)(1 + (λq)−h).By the assumption thatλsq >1, we have ∞Y h=0 (1 + (λq)−h/2)(1 + (λq)−h)≤exp ∞X h=0 (λq)−h/2 + (λq)−h ! <∞. This shows thatKis a constant. It follows by Le...

  48. [56]

    , vd)and 26 p′ = (v′ 0, v′ 1,

    The total order of the elements inP d 1,v is defined as follows: For two distinct pathsp= (v 0, v1, . . . , vd)and 26 p′ = (v′ 0, v′ 1, . . . , v′ d)withv 0 =v ′ 0 = 1andv d =v ′ d =v. We sayphas a higher order thanp ′, denoted p≺p ′, if there exists an indexd ′ ∈[d−1]such tha...

  49. [57]

    With the definitions of these two collections and their corresponding total ordering, we have the following lemma

    The total order of the elements in P k 1,i is analogously defined. With the definitions of these two collections and their corresponding total ordering, we have the following lemma. Lemma 5.Supposev∈V d andi∈V k. Assumep∈ P d 1,v is the highest orderd-path between1andv inG ′ 1...

  50. [58]

    ThenH p,p′ must satisfy the following two properties: 1)H p,p′ is a tree

    LetH p,p′ denote the union graph of the two pathpandp ′. ThenH p,p′ must satisfy the following two properties: 1)H p,p′ is a tree

  51. [59]

    Proof of Lemma 5.To prove the lemma, we consider two separate case:k=dandk̸=d

    For eachh≥0, the number of vertices inH p,p′ that are at distancehfromiis at most2. Proof of Lemma 5.To prove the lemma, we consider two separate case:k=dandk̸=d. Casek=d: We denotep= (v 0, v1, . . . , vd)andp ′ = (v′ 0, v′ 1, . . . , v′ d). Herev 0 =v ′ 0 = 1,v d =vand v′ d =...

  52. [60]

    Then we have P(Ci | Ak, v∈V d, i∈V k) = X p∈P d 1,v,p′∈P k 1,i (p,p′)admissible P(Ci ∩ D(1,v,d) p ∩ D(1,i,k) p′ | Ak, v∈V d, i∈V k) ≤max p∈P d 1,v,p′∈P k 1,i (p,p′)admissible P(Ci | D(1,v,d) p ,D (1,i,k) p′ ,A k, v∈V d, i∈V k) = max p∈P d 1,v,p′∈P k 1,i (p,p′)admissible P(Ci |...

  53. [61]

    Then we have P(the2 p logn-neighborhood ofiinGcontains a cycle| H ⊂ G) =O(n −1+γ)(23) for any constantγ >0

    There exists a constantC >0such that the number of vertices inHat distancedfromiis at most Cfor everyd≥0. Then we have P(the2 p logn-neighborhood ofiinGcontains a cycle| H ⊂ G) =O(n −1+γ)(23) for any constantγ >0. By Lemma 5 and the fact thatd, k≤d max =⌊ (1−ϵ) logn log(λq) ⌋,...

  54. [62]

    , d max}, we define event Ak ={|N G′ 1(1, k)| ≤K(λq) k logn} and E1,k ={∄i∈[n] :i∈S G′ 1(1, k)and the2l-neighborhood of ¯iin ¯Gcontains a cycle}

    Proof of the unconditional probability bound(14):Recall that for eachk∈ {0, . . . , d max}, we define event Ak ={|N G′ 1(1, k)| ≤K(λq) k logn} and E1,k ={∄i∈[n] :i∈S G′ 1(1, k)and the2l-neighborhood of ¯iin ¯Gcontains a cycle}. By Lemma 10 in Appendix H, we have P(∩dmax k=0 Ak...

  55. [63]

    It now suffices to show that for eachk∈ {0,

    =P(∪ dmax k=0 E c 1,k) ≤P((∪ dmax k=0 E c 1,k)∩(∩ dmax k=0 Ak)) +P((∩ dmax k=0 Ak)c) ≤P((∩ dmax k=0 Ak)c) + dmaxX k=0 P(E c 1,k|Ak) = ˜O(n−1/3) + dmaxX k=0 P(E c 1,k|Ak). It now suffices to show that for eachk∈ {0, . . . , d max} P(E c 1,k|Ak)≤K(logn)(λq) k ·O(n −1+ϵ/4).(31) T...

  56. [64]

    To simplify the notation, we useθto denote the likelihood thresholdexp (λsq)l−1 logn in this proof

    Proof of the unconditional probability bound(16):Recall that we definedE 2 as the event that there exist no triplets(i, j, k)∈[n] 3 withj̸=kthat satisfy all of the following properties: 1)i∈V ≤dmax+1; 2)L l−1(T IC i,l−1, ˜T \˜j ˜k,l−1)>exp (λsq)l−1 logn ; 3)V T IC i,l−1 ∩V ˜T ...

  57. [65]

    Event{T=t}implies{C d,r =c d,r}for everydandr

  58. [66]

    EventNimpliesX d,r ≤n 1−ϵ/2 for everydandr. 35 Fig. 6. An illustration of the notations defined. The vertex with index1at the top is the root the diffusion treeT IC. The red vertex with indexi(also vertexv 0,1 under our notation), is the root of the subtreeT. The eleven vertex...

  59. [67]

    EventNOimpliesA d,r for everydandr. By these properties, we have P NO∩ {T ∼= t} ∩ N { ˜T ∼= ˜t} ∩IN ≤P ∩(d,r) Ad,r ∩ {Cd,r =c d,r} ∩ {Xd,r ≤n 1−ϵ/2} { ˜T ∼= ˜t} ∩IN = Y (d,r) P Ad,r ∩ {Cd,r =c d,r} ∩ {Xd,r ≤n 1−ϵ/2} { ˜T ∼= ˜t} ∩IN∩ ∩(d′,r′)≺(d,r)Ad′,r′ ∩ {Cd′,r′ =c d′,r′} ∩ {...

  60. [68]

    We have P(E c 2 |V d ̸=∅)≥P(E c 2 ∩ {v∈V d} |V d ̸=∅) =P(v∈V d |V d ̸=∅)·P(E c 2 |v∈V d) ≥ 1 n ·P(E c 2 |v∈V d), where the last inequality follows by symmetry

    Proof of the conditional probability bound(17):To bound the conditional probabilityP(E c 2 |v∈V d), we first connect it to a relevant quantityP(E c 2 |V d ̸=∅). We have P(E c 2 |V d ̸=∅)≥P(E c 2 ∩ {v∈V d} |V d ̸=∅) =P(v∈V d |V d ̸=∅)·P(E c 2 |v∈V d) ≥ 1 n ·P(E c 2 |v∈V d), whe...

  61. [69]

    Therefore, to complete the proof of (17), it suffices to show thatP(V d ̸=∅) = Θ(1)

    = ˜O(n−4/3)in the previous subsection. Therefore, to complete the proof of (17), it suffices to show thatP(V d ̸=∅) = Θ(1). This is implied by the following technical lemma, 37 which is proven in Appendix H. Lemma 7.Consider an Erd ˝os–R´enyi random graphG ∼ER(n, µ n), whereµ ...

  62. [70]

    Two verticesi∈V T and ˜j∈V ˜T satisfy Criterion1 ′ if there exist three childreni 1, i2, i3 ofiinT and three children ˜j1, ˜j2, ˜j3 of ˜jin ˜Tsuch that Ll−1(Tik,l−1, ˜T˜jk,l−1)>exp (λsq)l−1 logn ,∀k∈[3]. 38 Algorithm 2:Auxiliary algorithm for matching two correlated Galton–Wat...

  63. [71]

    Two verticesi∈V T and ˜j∈V ˜T satisfy Criterion2 ′ if there exist two childreni 1, i2 ofiinTand two children ˜j1, ˜j2 of ˜jin ˜Tsuch that ˜j1 ∈ M i1 andL l−1(Ti2,l−1, ˜T˜j2,l−1)>exp (λsq)l−1 logn

  64. [72]

    This algorithm starts at depthdof both trees

    Two verticesi∈V T and ˜j∈V ˜T satisfy Criterion3 ′ if there exist two childreni 1, i2 ofiinTand two neighbors ˜j1, ˜j2 of ˜jin ˜Tsuch that ˜jk ∈ M ik,∀k∈[2]. This algorithm starts at depthdof both trees. For eachi∈V T,d and ˜j∈V ˜T,d , we add ˜jto the setM ′ i if iand ˜jsatisf...

  65. [73]

    3)H=T IC v,dmax−d+l, whereT IC v,dmax−d+l is the subtree inT IC rooted atvwith depth up tod max −d+l

    In graph ˜G2, there exist no edges between the set ˜N ↑ and any non-root vertex of ˜H. 3)H=T IC v,dmax−d+l, whereT IC v,dmax−d+l is the subtree inT IC rooted atvwith depth up tod max −d+l. 41 Proof of the claim: To prove the claim, we essentially want to show that if running A...

  66. [74]

    LetA={|N ↑| ≤ n1−2ϵ/3}

    Proof of(44):We first provide a high probability upper bound on the size ofN ↑. LetA={|N ↑| ≤ n1−2ϵ/3}. It follows by Lemma 11 that P(Ac |v∈V d) =O(n −ϵ/3).(47) Now suppose we are given a specific realization of the setN ↑. We use ˆP\N ↑ dmax−d+l to denote the joint law of the...

  67. [75]

    Notice thatd max −d+l=o(logn)

    Proof of(45):Recall that we defined eventA={|N ↑| ≤n 1−2ϵ/3}, and we haveP(A c |v∈V d) = O(n−ϵ/3). Notice thatd max −d+l=o(logn). We can apply Lemma 10 to get P(|V ˜H| ≥n ϵ/8 | {v∈V d} ∩ A) =O(n −4/3). Between a vertex in ˜N ↑ and a non-root vertex in ˜H, the probability of ha...

  68. [76]

    DefineS=∪ i∈Vd\{v}Si

    Proof of(46):For each vertexi∈V d \ {v}, letS i denote the set of vertices within distance dmax −d+lin the graphG ′ 1 \(V ≤d \ {i}). DefineS=∪ i∈Vd\{v}Si. We claimH=T IC dmax−d+l if the following two properties hold: 1)His a tree; 2)V H ∩S=∅. To see why these two properties im...

  69. [77]

    3)H=T IC v,l+l+, whereT IC i,l+l+ is the subtree inT IC rooted atiwith depth up tod max −d+l

    In graph ˜G2, there exist no edges between the set ˜N ↑ and any non-root vertex of ˜H. 3)H=T IC v,l+l+, whereT IC i,l+l+ is the subtree inT IC rooted atiwith depth up tod max −d+l. Using the same argument as in the proof of equations (44), (45) and (46) in the previous section...

  70. [78]

    48 Since we want to find a coupling under whichP(H ∼= T, ˜H ∼= ˜T)≥1− ˜O(n−3γ/4)

    The two bijectionsϕ k and ˜ϕk satisfyϕ k(∪k h=0H ∗ h) =∪ k h=0T ∗ h andϕ k(j) = ˜ϕk(˜j)for everyj∈ ∪k h=0H ∗ h; 3)(∪ k h=0Hh)∩(∪ k h=0 ˜Hh) =∅. 48 Since we want to find a coupling under whichP(H ∼= T, ˜H ∼= ˜T)≥1− ˜O(n−3γ/4). It suffices to lower bound the probability of the e...

  71. [79]

    eventsA c k,B c k,C c k,D c k andE k−1 all hold, 2)d j =c ϕk−1(j) for everyj∈H k−1,

  72. [80]

    Proof of Lemma 9.Notice that under eventsE k−1,A c k andB c k, bothH k and ˜Hk are trees

    ˜dj = ˜c˜ϕk−1(˜j) for everyj∈ ˜Hk−1, 4)d j =c ϕk−1(j), ˜dj = ˜cϕk−1(j) andd ∗ j =c ∗ ϕk−1(j) for everyj∈H ∗ k−1, then eventE k holds. Proof of Lemma 9.Notice that under eventsE k−1,A c k andB c k, bothH k and ˜Hk are trees. This is because Ek−1 guarantees thatH k−1 and ˜Hk−1 a...

  73. [81]

    Then we have P(the2 p logn-neighborhood ofiinGcontains a cycle| H ⊂ G) =O(n −1+γ)(23) for any constantγ >0

    There exists a constantC >0such that the number of vertices inHat distancedfromiis at most Cfor everyd≥0. Then we have P(the2 p logn-neighborhood ofiinGcontains a cycle| H ⊂ G) =O(n −1+γ)(23) for any constantγ >0. Proof.Throughout this proof, we omit the subscriptGin notations...

  74. [82]

    SampleX 1 ∼Binom(m, c 1/n)

  75. [83]

    GivenX 1, sampleX 2 ∼Binom(m−X 1, c2 n−c1 )

  76. [84]

    GivenX 1 andX 2, sampleX 3 ∼Binom(m−X 1 −X 2, c3 n−c1−c2 ). By Lemma 15, we can coupleX 1 andX ′ 1 such that P(X1 ̸=X ′ 1)≤O 1 n +O mc1 n −c 1 =O 1 +|m−n| n .(86) By the Chernoff–Hoeffding bound, we know that P(X1 ≥log 2 n)≤exp(−Clog 2 n),(87) for some constantC >0. Conditione...

  77. [85]

    Meanwhile, since constantCdepends only onλ, sandq, there exists a constantn ′′ 0 depending only onλ, sandqsuch that 1 logn ≤Cfor alln > n ′′

  78. [86]

    Finally, by settingn 0 = max{n′ 0, n′′ 0}, we get P(λ/s,qs,s) l−1 L(λ/s,qs,s) l−1 (T, ˜T)>exp (λsq)l−1 logn ≥1−p ext λsq −ϵ ′, for alln > n 0

Pith tools

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