Pith. sign in

REVIEW 2 major objections 4 minor 56 references

Achieving Almost Exact Recovery in Almost Quadratic Time: Rank-Based Graph Matching via Local Tree Correlation Tests

T0 review · 2 major / 4 minor · reviewed 2026-08-02 · deepseek-v4-flash

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

Pith's one-line read A rank-based algorithm using local tree correlation tests recovers all but O(n/log n) vertices of correlated Erdős–Rényi graph pairs in n^{2+o(1)} time when the correlation exceeds the tree-counting threshold.

desk verdict The first almost-quadratic-time algorithm for almost exact recovery in the correlated ER regime; main proof hinges on a cited moment-bound lemma whose diverging-regime uniformity should be checked. read the letter →

arxiv 2607.09087 v3 pith:JWJIFYH5 submitted 2026-07-10 cs.DS math.STstat.MLstat.TH

Jiale Cheng , Ziao Wang , Lei Ying This is my paper · ORCID
classification cs.DSmath.STstat.MLstat.TH MSC 05C8068Q2562F03
keywords graphmatchingcorrelatedErdős–Rényipairalmostexactrecoverynear-quadratictimelocaltreecorrelationtestsrank-baseddiverging-degreeregimetree-countingthreshold
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 tackles graph matching: recovering the hidden correspondence between vertices of two random graphs built from the same base graph. It proves that in the correlated Erdős–Rényi model with average degree (log n)^{α+o(1)}, a rank-based algorithm can correctly label all but O(n/log n) vertices in n^{2+o(1)} time, whenever the edge correlation is above the tree-counting threshold √C_Otter ≈ 0.581. The key move is to avoid computing an explicit likelihood threshold, which is hard, and instead sort all candidate local-tree pairs by their likelihood ratios and greedily match in that order. A sympathetic reader should care because this is the first almost-quadratic-time algorithm for almost exact recovery in this regime; earlier methods had running-time exponents that blow up as the correlation approaches the threshold.

What carries the argument

The engine is the local tree likelihood ratio L_d between the correlated and independent Poisson Galton–Watson tree-pair distributions. For each directed edge, RBAlign extracts the depth-d tree neighborhood with degree bound τ, builds a bipartite witness graph between the neighborhoods of candidate vertex pairs, and declares a match when greedy matching finds three edges whose likelihood ratios clear the current rank threshold—the 3-dangling-tree criterion. The proof additionally constructs an auxiliary correlation test with iterative boosting that is statistically tractable but computationally infeasible; the likelihood-ratio optimality lemma transfers its type-I and power guarantees to the

What would settle it

Simulate RBAlign on CER(n,λ,s) with n=10^5, α=0.5, and s=0.6; if the number of correctly and uniquely matched vertices is not at least n−Cn/log n for a fixed constant C with probability close to 1, the claimed coupling fails.

Watch

Extended reading notes

Core claim

Under the CER(n, λ, s) model with λ = (log n)^{α+o(1)}, α ∈ (0,1), and s ∈ (√C_Otter, 1], the RBAlign algorithm outputs a matching matrix with at least n − O(n/log n) correct unique row entries with probability 1 − O(exp(−½(log n)^{α/2})), and runs in n^{2+o(1)} time with probability 1 − o(e^{−n}). The proof first establishes the existence of a threshold θ* for a threshold-based counterpart TBAlign, then couples the rank-based algorithm to TBAlign so that every match it accepts is also accepted by the threshold-based version, and shows it terminates with the right number of matched rows. Along the way, the paper supplies a new analysis of local tree correlation tests in the diverging-degree

Load-bearing premise

The argument treats moment inequalities previously proved for fixed mean degree as still valid when both the mean degree μ=(log n)^{α+o(1)} and the tree depth k=(log n)^γ grow with n; if those inequalities degrade in this joint-growth regime, the auxiliary test, the existence of the threshold, and the coupling to the rank-based algorithm all collapse.

Editorial extensions

If this is right

  • This is the first almost-quadratic-time algorithm achieving almost exact recovery in the diverging-degree sparse regime, with a running-time exponent independent of the correlation s.
  • The rank-based formulation removes the need to compute an explicit threshold, which was the computational bottleneck in previous tree-correlation methods.
  • The new diverging-degree analysis of tree correlation tests extends a previously constant-degree-only technique to settings where both mean degree and depth grow with n.
  • The coupling between rank-based and threshold-based algorithms shows that any future improvement in threshold existence transfers automatically to the implementable rank-based variant.
  • The error probability 1 − O(exp(−½(log n)^{α/2})) is stronger than any polynomial failure bound, so the guarantee is highly robust for large n.

Reading between the lines

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

  • The threshold-free ranking principle suggests a template for other graph-matching models where likelihood ratios are computable but thresholds are analytically inaccessible.
  • If the transferred moment bounds survive, the leftover O(n/log n) unmatched vertices could likely be cleaned up by a local search, since the proof already isolates vertex degeneracies as the only obstruction in this regime.
  • The existence proof relies on a computationally infeasible auxiliary test, leaving open whether the promised threshold can be approximated in practice without re-examining the full space of tree pairs.
  • Optimizing the parameters τ=(log n)^t and d=(log n)^γ could push the regime toward α closer to 1 or reduce the n^{o(1)} runtime factor.
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 / 4 minor

Summary. The paper studies graph matching under the correlated Erdős–Rényi model CER(n,λ,s) with λ=(log n)^{α+o(1)}, α∈(0,1), and s∈(√C_Otter,1]. It proposes RBAlign, a rank-based algorithm built on local tree likelihood-ratio tests. The main claims (Theorems 1 and 2) are that RBAlign outputs a matrix with at least n−O(n/log n) correctly and uniquely matched vertices with probability 1−O(exp(−½(log n)^{α/2})), and runs in n^{2+o(1)} time with probability 1−o(e^{−n}). The proof route is: construct a threshold-based algorithm TBAlign; prove that a threshold θ* exists via an infeasible auxiliary tree-correlation test Φ and the Neyman–Pearson lemma; then couple the rank-based algorithm to TBAlign.

Significance. If the main theorems are correct, this is a substantial advance: it is the first algorithm with almost quadratic time achieving almost exact recovery in the sub-logarithmic degree regime, improving on the chandelier-counting algorithm whose exponent diverges as s approaches √C_Otter. The paper also contributes a new analysis of tree correlation tests in a diverging-degree regime, which may be of independent interest. The rank-based formulation that avoids computing an explicit threshold is conceptually elegant, and the paper is unusually detailed: it includes explicit complexity accounting, a construction of the tie-breaking map f, and machine-checkable-style appendices. These strengths are real. However, two load-bearing points are not fully established as written: the transfer of moment bounds from [29] to the diverging regime, and the tie-breaking comparison in the coupling lemma.

major comments (2)
  1. [§V and Appendix B-D, Lemma 11] Proposition 3 and hence Theorem 3 rest on the three moment bounds (106)–(108) in Lemma 11, stated for 'any k≥1 and μ>1' and attributed to [29, Lemma B.1]. The application requires μ=λ=(log n)^{α+o(1)} and k up to d=(log n)^γ, both diverging, while the manuscript itself describes [29] as a constant-degree analysis. The paper does not prove these bounds nor does it point to the precise statement in [29] that covers this uniformity. The induction in Lemma 5 and the choice of σ_k in (38) depend on the constants 36 and 13 in (108) not degrading with k and μ. If the cited lemma was proved only for fixed μ or under extra conditions, the auxiliary test Φ, the Neyman–Pearson step, and hence Theorems 1–2 collapse. Please supply a proof of Lemma 11 in the diverging regime or an exact citation to the uniform version in [29].
  2. [§IV-D, Lemma 1] The coupling argument compares GreedyMatching at θ_e and θ* by monotonicity in the threshold, but the two algorithms use different tie-breaking sets at equal likelihood ratios. When θ_e=θ*, the rank-prefix available to RBAlign is {L>θ*} ∪ {L=θ*, f≤f_{k_e}}, whereas TBAlign accepts {L>θ*} ∪ {L=θ*, f>κ*}. These sets are not nested: an edge with L=θ* and f<κ* can be accepted by RBAlign but rejected by TBAlign. Thus the claimed implication M_RB(u,v)=1 ⇒ M_TB(u,v)=1 is not established, and this implication is used to bound the number of incorrect rows in Theorem 1. The gap can likely be closed by choosing the target so that termination occurs strictly above θ*, or by using a strict-threshold version of TBAlign whose per-edge power is the same up to O((log n)^{−α/4}), but as written the proof is incomplete.
minor comments (4)
  1. [Algorithm 2, line 9] The text says 'Rank all the entries in L_d'; this should be the matrix L, not the likelihood-ratio function L_d.
  2. [Appendix B-B, Lemma 7 proof] In the proof of (96), the base case k=0 is misstated: φ_0(1/(3μ^{l-1})) = 1/(3μ^{l-1}), not 1/(3μ^{l-k}) + (k−1)/(3μ^{l-k+1}). The induction is understandable but should be cleaned up.
  3. [Appendix F] The tie-breaking map f is constructed to take values in [0,1), while Theorem 3 and the main text say [0,1]. This is immaterial but should be made consistent.
  4. [Section IV-A] The notation L_d(t,~t) is used for both the likelihood ratio and, in Algorithm 2, for the matrix of all likelihood ratios. Please disambiguate to avoid confusion.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proof chain rests on external [29] moment bounds and a constructed auxiliary test; the only self-citation is a technical non-load-bearing lemma.

full rationale

The derivation chain is a standard reduction: Theorems 1–2 follow from coupling RBAlign to TBAlign (Lemma 1) and from Proposition 1; Proposition 1 follows from Theorem 3's existence of thresholds plus degree-concentration lemmas; Theorem 3 is derived from the auxiliary test Φ (Proposition 2) via the Neyman–Pearson lemma; Proposition 2 is derived from Proposition 3; and Proposition 3 is an induction using Lemma 4 (initialization) and Lemma 5 (iterative boosting). The moment Lemmas 9, 10, and 11 are quoted from Ganassali–Massoulié–Semerjian [29], an external source with no author overlap, and are stated as holding for all k≥1 and μ>1, i.e., their stated assumptions cover the diverging μ and k regime used here. The threshold θ* is not an input to RBAlign and is never computed by the algorithm; it is a consequence of the Neyman–Pearson lemma, not an assumed quantity. No constants are fitted to data, and no equation equates a derived result to its own input by construction. The only self-citation is [41] for the technical Poisson/binomial ratio Lemma 18; that lemma is parameter-free, auxiliary, and not the load-bearing graph-matching step, so it is real evidence rather than circular support. The dependence of Theorem 3 on the uniformity of [29]'s moment bounds is a genuine proof-transfer assumption, but if those bounds failed the proof would be incorrect, not circular; it is a correctness risk, not a self-referential derivation.

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

No data-fitting and no new physical or model-level entities are introduced. The algorithm parameters and proof constants are chosen by hand but are not fitted to observations. The central claim rests mainly on the CER model, the [11,29] tree-correlation machinery, and the transfer of moment bounds to the diverging-degree regime.

free parameters (4)
  • Tree depth d=(logn)^γ = γ∈(1−α,1)
    Testing depth chosen in Proposition 1. Must stay below the acyclicity scale of ER neighborhoods; not fitted to data.
  • Degree cap τ=(logn)^t = t∈(max{α,γ},1)
    Local-tree degree bound; controls the n^{o(1)} runtime factor. Chosen by hand to satisfy theorem assumptions.
  • RBAlign target unmatched n/log n = n−⌈n/log n⌉
    Termination threshold; chosen smaller than the TBAlign guarantee so the coupling argument works.
  • Boosting constants C1, C2, β, dbar, λbar = C1=2×10^6; C2=exp((γ−α−η+1)/(2β)); β chosen in Proof of Prop. 2; dbar, λbar exist via Lemmas 4/8
    Hand-chosen constants in the auxiliary test Φ and iterative boosting. Independent of n; not fitted to data, but the proof depends on satisfying several inequalities.
assumptions (6)
  • domain assumption CER(n,λ,s) generative model with independent subsampling of a base ER graph
    Model definition in Section III-B; all analysis assumes this generative process.
  • standard math Poisson Galton–Watson tree likelihood-ratio recursion (Lemma 2.1 of [11])
    Used in Eq. (7) as the computational method for L_d; an external prior result.
  • domain assumption Moment bounds for the boosting statistic (Lemma 11, [29, Lemma B.1]) hold for all μ>1 and k≥1
    Load-bearing transfer of constant-degree tree analysis to the diverging-degree/depth regime; Appendix A-E relies on it.
  • standard math Otter's tree-counting asymptotics: number of unlabeled trees of size k grows like C5 k^{-3/2} C_Otter^{-k}
    Used to prove χ_dbar grows when s²>C_Otter (Lemma 6/8), which underlies the whole Otter-condition.
  • standard math Neyman–Pearson lemma for finite simple hypotheses
    Used in Appendix A-F to pass from the auxiliary test Φ to the existence of the likelihood-ratio threshold θ*.
  • standard math Poisson approximation and concentration inequalities (Bennett, Chernoff, maximal coupling lemmas)
    Used throughout Appendices C-E to compare graph neighborhoods with Galton–Watson trees and to control atypical events.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Achieving Almost Exact Recovery in Almost Quadratic Time: Rank-Based Graph Matching via Local Tree Correlation Tests." pith.science (2026). https://pith.science/paper/JWJIFYH5

@misc{pith2026260709087,
  author       = {Pith},
  title        = {Pith review of: Achieving Almost Exact Recovery in Almost Quadratic Time: Rank-Based Graph Matching via Local Tree Correlation Tests},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JWJIFYH5}},
  note         = {Machine review of arXiv:2607.09087}
}
abstract

This paper studies graph matching under the correlated $\text{Erd\H{o}s-R\'{e}nyi}$ (ER) graph pair model. This model first samples an $\mathrm{ER}(n,\frac{\lambda}{ns})$ base graph, whose edges are then independently subsampled twice with probability $s$ to produce two correlated $\mathrm{ER}(n,\frac{\lambda}{n})$ graphs. We propose a graph matching algorithm that has $n^{2+o(1)}$ time complexity and achieves almost exact recovery with high probability under the assumptions $\lambda=(\log n)^{\alpha+o(1)}$ for some $\alpha\in(0,1)$ and $s\in(\sqrt{C_{\mathrm{Otter}}},1]$, where $C_{\mathrm{Otter}}\approx 0.338$ is Otter's tree-counting constant. This is the first algorithm with almost quadratic time complexity in this regime of $\lambda$, while the best known result in this regime is the chandelier-counting algorithm with time complexity $O(n^{c(s)})$, where $c(s)\rightarrow \infty$ as $s$ approaches $\sqrt{C_\mathrm{Otter}}$ from above. The proposed algorithm is based on local tree correlation tests. It uses a rank-based algorithm to match the vertex pairs instead of threshold-based rules in the literature. This avoids the need of computing an explicit threshold, which is computationally difficult to obtain. To prove the almost exact recovery result, we establish a new analysis of tree correlation tests in the diverging-degree regime, where both the mean degree and the tree depth grow with $n$. Based on this new result, we establish the existence of a threshold for a threshold-based graph matching algorithm via local tree correlation tests. Finally, we couple the performance of the rank-based algorithm with the threshold-based algorithm to show almost exact recovery.

Figures

Figures reproduced from arXiv: 2607.09087 by the authors.

Figure 1
Figure 1. Comparison of the time-complexity exponents between our algorithm and the chandelier-counting [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. An example of CER(n, λ, s) model with n = 9. While this paper focuses on the canonical correlated Erdos–R ˝ enyi graph pair model, we expect that the ´ tree correlation test analysis developed here may also be useful for designing low-complexity algorithms in some of these broader graph matching models. III. MODEL AND MAIN RESULTS A. Notation Given a simple graph H, we use V(H) to denote its vertex set and E(H) to d… view at source ↗
Figure 3
Figure 3. Relationships among the main theoretical results in the paper. A.E.R. - Almost Exact Recovery; [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: An example of GreedyMatching with θ ∗ = 4. The number next to each edge represents its weight. In this example, we obtain a matching of size 3, and hence the subroutine outputs 1. If θ ∗ is instead chosen to be 6, then the edge (u1, v˜2) cannot be included, and hence t…
Figure 5
Figure 5. Figure 5: An example of constructing bipartite graph W from trees (t,t˜) ∈ Z4 × Z4 when l = 1. The red nodes in both tree t and t˜ are roots, while the blue nodes in t and t˜ denote the two parts in W. The green dashed line between two subtrees denotes that they appear in set F3…
Figure 6
Figure 6. Figure 6: Examples of constructing path P¯ i in Case (i) (top), Case (ii) (middle) and Case (iii) (bottom). In each case, the red edges denotes path P¯ i . The black notations next to each node represents the nodes of path (y (0) i , y (1) i , . . . , y (t) i ) in G, while the b…
Figure 7
Figure 7. Figure 7: An illustration of the relabeling mapping [PITH_FULL_IMAGE:figures/full_fig_p053_7.png]
Figure 8
Figure 8. Figure 8: An example of calculating f(t,t˜). Each vertex in t is attached with a code. The three leaves get 0 in Step 1. The child carrying two leaves gets 2 0 0 in Step 2. At the root the two children are labelled 2 0 0 and 0, so in decreasing order the root’s label is 2 2 0 0 …

Review history (3 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

56 extracted references · 9 canonical work pages

  1. [29]

    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. [Online]. Available: https://doi.org/10.1214/23-AAP2048

    work page doi:10.1214/23-aap2048 2024

  2. [1]

    De-anonymizing social networks,

    A. Narayanan and V . Shmatikov, “De-anonymizing social networks,” in2009 30th IEEE Symposium on Security and Privacy. Oakland, CA, USA: IEEE, 2009, pp. 173–187

    2009

  3. [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. [Online]. Available: https: //doi-org.proxy.lib.umich.edu/10.14778/2732269.2732274

    arXiv 2014

  4. [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 (RECOMB). Berlin, Heidelberg: Springer, 2007, pp. 16–31

    2007

  5. [4]

    Progressive graph matching: Making a move of graphs via probabilistic voting,

    M. Cho and K. M. Lee, “Progressive graph matching: Making a move of graphs via probabilistic voting,” in2012 IEEE Conference on Computer Vision and Pattern Recognition. Providence, RI, USA: IEEE, 2012, pp. 398–405

    2012

  6. [5]

    Robust textual inference via graph matching,

    A. D. Haghighi, A. Y . Ng, and C. D. Manning, “Robust textual inference via graph matching,” in Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP). Vancouver, British Columbia, Canada: Association for Computational Linguistics, 2005, pp. 387–394

    2005

  7. [6]

    The quadratic assignment problem,

    R. E. Burkard, E. C ¸ ela, P. M. Pardalos, and L. S. Pitsoulis, “The quadratic assignment problem,” inHandbook of Combinatorial Optimization: Volume 1–3, D.-Z. Du and P. M. Pardalos, Eds. Boston, MA: Springer US, 1998, pp. 1713–1809. [Online]. Available: https://doi.org/10.1007/978-1-4613-0303-9 27

    work page doi:10.1007/978-1-4613-0303-9 1998

  8. [7]

    Maximum quadratic assignment problem: Reduction from maximum label cover and lp-based approximation algorithm,

    K. Makarychev, R. Manokaran, and M. Sviridenko, “Maximum quadratic assignment problem: Reduction from maximum label cover and lp-based approximation algorithm,”ACM Trans. Algorithms, vol. 10, no. 4, Aug. 2014. [Online]. Available: https://doi.org/10.1145/2629672

    work page doi:10.1145/2629672 2014

Show all 56 references
  1. [8]

    On the privacy of anonymized networks,

    P. Pedarsani and M. Grossglauser, “On the privacy of anonymized networks,” inProceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ser. KDD ’11. New York, NY , USA: Association for Computing Machinery, 2011, p. 1235–1243. [Online]....

    2011

  2. [9]

    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

  3. [10]

    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 Transactions on Information Theory, vol. 68, no. 8, pp. 5391–5417, 2022

    2022

  4. [11]

    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. [Online]. Available: https://doi.org/10.1214/23-AAP2020

    2024 doi

  5. [12]

    The number of trees,

    R. Otter, “The number of trees,”Annals of Mathematics, vol. 49, no. 3, pp. 583–599, 1948. [Online]. Available: http://www.jstor.org/stable/1969046

    1948

  6. [13]

    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,”SIGMETRICS Perform. Eval. Rev., vol. 44, no. 1, p. 63–72, Jun. 2016. [Online]. Available: https://doi.org/10.1145/2964791.2901460

    2016

  7. [14]

    Exact alignment recovery for correlated Erd ˝os–R´enyi graphs,

    ——, “Exact alignment recovery for correlated Erd ˝os–R´enyi graphs,” 2018. [Online]. Available: https://arxiv.org/abs/1711.06783

    2018 arXiv

  8. [15]

    Partial recovery of Erd˝os-R´enyi graph alignment viak-core alignment,

    D. Cullina, N. Kiyavash, P. Mittal, and H. V . Poor, “Partial recovery of Erd˝os-R´enyi graph alignment viak-core alignment,”Proceedings of the ACM on Measurement and Analysis of Computing Systems, vol. 3, no. 3, pp. 54:1–54:21, 2019. [Online]. Available: https://doi.org/10.11...

    2019 doi

  9. [16]

    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, M. Belkin and S. Kpotufe, Eds., vol. 134. 22 Boulder, Co...

    2021

  10. [17]

    Partial recovery in the graph alignment problem,

    G. Hall and L. Massouli ´e, “Partial recovery in the graph alignment problem,”Oper. Res., vol. 71, no. 1, p. 259–272, Jan. 2023. [Online]. Available: https://doi.org/10.1287/opre.2022.2355

    2023

  11. [18]

    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. [Online]. Available: https: //doi.org/10.1214/23-AOS2305

    2023 doi

  12. [19]

    Optimal recovery of correlated Erd ˝os–R´enyi graphs,

    H. Du, “Optimal recovery of correlated Erd ˝os–R´enyi graphs,” 2025. [Online]. Available: https://arxiv.org/abs/2502.12077

    2025 arXiv

  13. [20]

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

    O. E. Dai, D. Cullina, N. Kiyavash, and M. Grossglauser, “Analysis of a canonical labeling algorithm for the alignment of correlated erdos-r ´enyi graphs,”Proc. ACM Meas. Anal. Comput. Syst., vol. 3, no. 2, Jun. 2019. [Online]. Available: https://doi-org.proxy.lib.umich.edu/10...

    2019

  14. [21]

    Efficient random graph matching via degree profiles,

    J. Ding, Z. Ma, Y . Wu, and J. Xu, “Efficient random graph matching via degree profiles,” Probability Theory and Related Fields, vol. 179, no. 1–2, p. 29–115, Sep. 2021. [Online]. Available: http://dx.doi.org/10.1007/s00440-020-00997-4

    2021 doi

  15. [22]

    Spectral graph matching and regularized quadratic relaxations i algorithm and gaussian analysis,

    Z. Fan, C. Mao, Y . Wu, and J. Xu, “Spectral graph matching and regularized quadratic relaxations i algorithm and gaussian analysis,”Found. Comput. Math., vol. 23, no. 5, p. 1511–1565, Jun

  16. [23]

    Spectral graph matching and regularized quadratic relaxations II: Erd ˝os-R´enyi graphs and universality,

    ——, “Spectral graph matching and regularized quadratic relaxations II: Erd ˝os-R´enyi graphs and universality,”Foundations of Computational Mathematics, vol. 23, no. 5, pp. 1567–1617, 2023. [Online]. Available: https://doi.org/10.1007/s10208-022-09575-7

    2023 doi

  17. [24]

    From tree matching to sparse graph alignment,

    L. Ganassali and L. Massouli ´e, “From tree matching to sparse graph alignment,” inProceedings of Thirty Third Conference on Learning Theory, ser. Proceedings of Machine Learning Research, J. Abernethy and S. Agarwal, Eds., vol. 125. Virtual: PMLR, 09–12 Jul 2020, pp. 1633–166...

    2020

  18. [25]

    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,” 2025. [Online]. Available: https://arxiv.org/abs/2504.02299

    2025

  19. [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, p. 327–389, Jan. 2023. [Online]. Available: http://dx.doi.org/10.1007/s00440-022-01184-3

    2023 doi

  20. [27]

    Random graph matching with improved noise robustness,

    ——, “Random graph matching with improved noise robustness,” inProceedings of Thirty Fourth Conference on Learning Theory, ser. Proceedings of Machine Learning Research, M. Belkin and S. Kpotufe, Eds., vol. 134. Boulder, Colorado, USA: PMLR, 15–19 Aug 2021, pp. 3296–3329. [Onli...

    2021

  21. [28]

    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, 2026, articles in Advance, published online 29 December 2025. [Online]. Available: https://doi.org/10.1287/moor.2024.0487

    2026

  22. [30]

    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 Techniques (APPROX/RANDOM 2025), ser. Leibniz International Proceedings in Informatics (LIPIc...

    2025 doi

  23. [31]

    Correlated stochastic block models: Exact graph matching with applications to recovering communities,

    M. Z. R ´acz and A. Sridhar, “Correlated stochastic block models: Exact graph matching with applications to recovering communities,”Advances in Neural Information Processing Systems, 23 vol. 34, pp. 22 259–22 273, 2021

    2021

  24. [32]

    Efficient graph matching for correlated stochastic block models,

    S. Chai and M. Z. R ´acz, “Efficient graph matching for correlated stochastic block models,” in Advances in Neural Information Processing Systems 37 (NeurIPS 2024), A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. M. Tomczak, and C. Zhang, Eds., vol. 37. Vancouver, ...

    2024

  25. [33]

    Efficient algorithms for exact graph matching on correlated stochastic block models with constant correlation,

    J. Yang, D. Shin, and H. W. Chung, “Efficient algorithms for exact graph matching on correlated stochastic block models with constant correlation,” inProceedings of the 40th International Conference on Machine Learning, ser. ICML’23. Honolulu, HI, USA: JMLR.org, 2023, pp. 39 4...

    2023

  26. [34]

    Random graph matching in geometric models: the case of complete graphs,

    H. Wang, Y . Wu, J. Xu, and I. Yolou, “Random graph matching in geometric models: the case of complete graphs,” inProceedings of the Thirty-Fifth Conference on Learning Theory, ser. Proceedings of Machine Learning Research, P.-L. Loh and M. Raginsky, Eds., vol. 178. London, UK...

    2022

  27. [35]

    Attributed graph alignment,

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

    2024

  28. [36]

    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 Transactions on Information Theory, vol. 70, no. 5, pp. 3622– 3639, 2024

    2024

  29. [37]

    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

  30. [38]

    Attributed network alignment: Statistical limits and efficient algorithm,

    D. Huang, C. Tian, and P. Yang, “Attributed network alignment: Statistical limits and efficient algorithm,” 2026. [Online]. Available: https://arxiv.org/abs/2604.04365

    2026 arXiv

  31. [39]

    Exact random graph matching with multiple graphs,

    T. Ameen and B. Hajek, “Exact random graph matching with multiple graphs,” in2025 IEEE International Symposium on Information Theory (ISIT). Ann Arbor, MI, USA: IEEE, 2025, pp. 1–6

    2025

  32. [40]

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

    ——, “Aligning multiple inhomogeneous random graphs: Fundamental limits of exact recovery,” arXiv preprint arXiv:2405.12293, 2024

    2024 arXiv

  33. [41]

    Diffusion-network alignment: An efficient algorithm and explicit probability bounds,

    Z. Wang and L. Ying, “Diffusion-network alignment: An efficient algorithm and explicit probability bounds,” inProceedings of Thirty Ninth Conference on Learning Theory, ser. Proceedings of Machine Learning Research, S. Hanneke and T. Lattimore, Eds., vol. 336. San Diego, CA, U...

    2026

  34. [42]

    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). Ann Arbor, MI, USA: IEEE, 2025, pp. 1–6. [Online]. Available: https://doi.org/10.1109/ISIT63088.2025.11195708

    2025

  35. [43]

    N. L. Johnson, S. Kotz, and A. W. Kemp,Univariate Discrete Distributions, 2nd ed. New York, NY , USA: John Wiley & Sons, 1992

    1992

  36. [44]

    E. L. Lehmann and J. P. Romano,Testing statistical hypotheses. New York, NY , USA: Springer, 2005

    2005

  37. [45]

    D. A. Levin, Y . Peres, and E. L. Wilmer,Markov Chains and Mixing Times, 2nd ed. Providence, RI: American Mathematical Society, 2017

    2017

  38. [46]

    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

    1960

  39. [47]

    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

  40. [48]

    Mitzenmacher and E

    M. Mitzenmacher and E. Upfal,Probability and Computing: Randomization and Probabilistic 24 Techniques in Algorithms and Data Analysis, 2nd ed. Cambridge, UK: Cambridge University Press, 2017. 25 The appendix is organized as follows: Appendix A proves Theorem 3, our guarantee f...

    2017

  41. [50]

    In particular, ¯dis given by ¯d=   max   k0 −1, 3 log s2 COtter !2 , 2 log s2 COtter 2C6 + log 2s2 C5      , wherek 0 andC 5 are constants indicated by Lemma 6

    If we further assume thats 2 > COtter, then for any constantC 6 >0, there exists an integer ¯dsuch thatχ ¯d > C6. In particular, ¯dis given by ¯d=   max   k0 −1, 3 log s2 COtter !2 , 2 log s2 COtter 2C6 + log 2s2 C5      , wherek 0 andC 5 are constants indicated ...

  42. [51]

    , y(t) i )inGfromutox i withy (0) i =u,y (1) i =u i,y (t) i =x i, and t≤d+ 1,

    there is a path(y (0) i , y(1) i , . . . , y(t) i )inGfromutox i withy (0) i =u,y (1) i =u i,y (t) i =x i, and t≤d+ 1,

  43. [52]

    ,˜z(˜t) i )in ˜Gfrom˜vtox i with˜z(0) i = ˜v,˜z(1) i = ˜vi,˜z(˜t) i =x i, and ˜t≤d+ 1

    there is a path(˜z (0) i ,˜z(1) i , . . . ,˜z(˜t) i )in ˜Gfrom˜vtox i with˜z(0) i = ˜v,˜z(1) i = ˜vi,˜z(˜t) i =x i, and ˜t≤d+ 1. Passing to the union graph, we obtain two paths (¯y(0) i ,¯y(1) i , . . . ,¯y(t) i )and(¯z (0) i ,¯z(1) i , . . . ,¯z(˜t) i ), where¯y(0) i = ¯u,¯y(...

  44. [53]

    Coupling(T k, ˜Tk)with(H k, ˜Hk)givenℓ(T k−1, ˜Tk−1) = (Hk−1, ˜Hk−1): For each depthk≥ 1, we recursively define three sets of vertices:COM k,EXC k, and gEXCk

    =O λ3 log2 n n .(138) Step 2. Coupling(T k, ˜Tk)with(H k, ˜Hk)givenℓ(T k−1, ˜Tk−1) = (Hk−1, ˜Hk−1): For each depthk≥ 1, we recursively define three sets of vertices:COM k,EXC k, and gEXCk. The setCOM k consists of the vertices at depthkthat appear in both local trees under the...

  45. [54]

    SampleX 1 ∼Binom(m, λs/n)

  46. [55]

    GivenX 1, sampleX 2 ∼Binom m−X 1, λ(1−s) n−λs

  47. [56]

    GivenX 1 andX 2, sampleX 3 ∼Binom m−X 1 −X 2, λ(1−s) n−λ . By Lemma 19, we can coupleX 1 andX ′ 1 such that under the coupling, P(X1 ̸=X ′ 1)≤ λ2s2 + (n−m)λs n =O (n−m)λ+ log 2 n n .(152) 60 By the Chernoff bound (equation (159) in Lemma 22), we know that P(X1 >logn) =n −ω(1)....

  48. [2023]

    Available: https://doi.org/10.1007/s10208-022-09570-y

    [Online]. Available: https://doi.org/10.1007/s10208-022-09570-y

    doi

Pith tools

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