Pith. sign in

REVIEW 3 major objections 6 minor 46 references

Strong Detection Threshold for Correlated Erd\H{o}s-R\'enyi Graphs with Constant Average Degree

T0 review · 3 major / 6 minor · reviewed 2026-08-07 · 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 strong detection between two graphs subsampled from a common parent and two independent graphs with the same marginals is information-theoretically possible exactly when the subsampling probability exceeds…

desk verdict A sharp and essentially correct resolution of the strong detection threshold for sparse correlated Erdős-Rényi graphs, held back only by two typos that must be fixed. read the letter →

arxiv 2506.12752 v1 pith:3JXTBXWU submitted 2025-06-15 math.PR

Chenxu Feng This is my paper · ORCID
classification math.PR MSC 05C8060C05
keywords correlatedErdős-Rényigraphsstrongdetectioninformation-theoreticthresholdOtter'sconstantsecondmomentmethodtotalvariationdistancegraphmatchingaveragedegree
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

Two sparse random graphs that are subsampled from a single parent graph carry a hidden shared origin; the statistical question is whether an observer who sees only the two copies can tell that they are correlated rather than independent with the same edge density. This paper establishes the exact boundary for that question in the constant-average-degree regime: strong detection is possible if and only if the subsampling probability $s$ exceeds $\min\{1/\sqrt{\lambda}, \sqrt{\alpha}\}$, where $\alpha\approx 0.338$ is Otter's constant, the growth rate of unlabeled trees. The result closes a constant-factor gap between previously known upper and lower bounds. The proof contributes a conditional second-moment technique that controls the likelihood ratio on a high-probability acyclic event, which should be useful for other sparse alignment problems.

What carries the argument

The proof is carried by the permutation-averaged likelihood ratio $L(A,B)=\frac{1}{n!}\sum_{\pi}\prod_e \ell(A_e,B_{\pi(e)})$, where $\ell$ is the per-edge likelihood ratio. Fixing the latent alignment $\pi^*$ and writing $\sigma=(\pi^*)^{-1}\circ\pi$, the product splits over the edge orbits of $\sigma$; the short orbits, of length one, require a sharper estimate than previous work, which removes the earlier constant slack. On the event that the intersection graph is acyclic, the truncated second moment of the likelihood ratio collapses to a weighted forest count: each forest $J$ contributes $s^{2|E(J)|}$. Otter's constant $\alpha\approx 0.338$ is the radius of convergence of the unlabeled-tree generating function, and the classical asymptotic $f_k=O(\alpha^{-k}/k^{1.5})$ makes the forest series converge precisely for $s^2<\alpha$; the $1/\sqrt{\lambda}$ term in the threshold comes from requiring $\lambda s^2<1$ so the intersection graph is subcritical and the acyclic event has positive probability.

What would settle it

For a fixed constant $\lambda$ such as $\lambda=2$, simulate graph pairs at $s$ just below and just above $\sqrt{\alpha}\approx 0.581$ and estimate the total variation distance; the theorem predicts $\mathrm{TV}(P,Q)$ stays bounded away from $1$ below the boundary and tends to $1$ above it. A more direct check is to estimate the truncated second moment $\mathbb{E}_P[(P/Q)\mathbf{1}_A]$: the proof requires it to stay $O(1)$ for $s<\min\{1/\sqrt{\lambda},\sqrt{\alpha}\}$ and to diverge above, so a single parameter value that violates this would refute the claimed threshold.

Watch

Extended reading notes

Core claim

The central discovery is a sharp phase transition for the total variation distance between the correlated model $P$ and the independent model $Q$ with the same marginals. For any constant $\epsilon>0$, if $s<\min\{1/\sqrt{\lambda},\sqrt{\alpha}\}-\epsilon$ then $\mathrm{TV}(P,Q)=1-\Omega(1)$, so no test can strongly distinguish the two distributions; if $s>\min\{1/\sqrt{\lambda},\sqrt{\alpha}\}+\epsilon$ then $\mathrm{TV}(P,Q)=1-o(1)$, so strong detection is possible. The upper direction is assembled from existing statistics, densest subgraphs when $\lambda s^2>1$ and tree counting when $s^2>\alpha$. The lower direction is new: conditioning on the event $A$ that the intersection graph, the edges present in both copies under the latent alignment, is a forest, which occurs with probability bounded below by a constant, the proof shows $\mathbb{E}_P[(P/Q)\mathbf{1}_A]=O(1)$, which forces $\mathrm{TV}(P,Q)=1-\Omega(1)$. The calculation reduces to a weighted sum over forests $J$ of $s^{2|E(J)|}$, and Otter's asymptotic $f_k=O(\alpha^{-k}/k^{1.5})$ for unlabeled trees makes this series converge exactly when $s^2<\alpha$; the condition $s<1/\sqrt{\lambda}$ enters through the positivity of the acyclic event.

Load-bearing premise

The proof imports the classical asymptotic $f_k=O(\alpha^{-k}/k^{1.5})$ for the number of unlabeled trees, and the entire lower bound rests on the forest generating function converging at the radius this asymptotic dictates; if that asymptotic were inaccurate, the threshold $\min\{1/\sqrt{\lambda},\sqrt{\alpha}\}$ would shift.

Editorial extensions

If this is right

  • The constant-factor gap between the previous best upper and lower bounds is closed: the sharp threshold is the minimum of $1/\sqrt{\lambda}$ and $\sqrt{\alpha}$.
  • For $\lambda>1/\alpha\approx 2.96$, the detection threshold $1/\sqrt{\lambda}$ is smaller than $\sqrt{\alpha}$, so strong detection becomes possible exactly when partial recovery of the latent matching becomes possible.
  • For $\lambda<1/\alpha$, detection is possible once $s>\sqrt{\alpha}$ while recovery of the matching remains impossible until $s>1/\sqrt{\lambda}$, leaving a constant-factor detection-recovery gap.
  • Above the threshold, known efficient algorithms succeed (densest subgraphs when $\lambda s^2>1$, tree counting when $s^2>\alpha$); below it, no algorithm, efficient or not, can strongly detect the correlation.
  • In the regime $n^{-1+o(1)}\le \lambda=o(1)$, the threshold reduces to $\sqrt{\alpha}$, matching the tree-counting upper bound.

Reading between the lines

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

  • The conditional-second-moment technique, which works on a positive-probability acyclic event rather than a high-probability one, is likely transferable to other alignment problems on sparse random graphs, such as partially correlated Erdős-Rényi graphs where only constant-factor bounds are currently known.
  • The appearance of Otter's constant in the statistical limit for all $\lambda<1/\alpha$ suggests that tree counting is not just an algorithmic heuristic but captures the fundamental information-theoretic boundary whenever the intersection graph is subcritical; a testable extension is whether decorated-tree statistics can close the remaining gap for $\lambda>1/\alpha$.
  • Because the paper shows the impossibility region extends to $s<\sqrt{\alpha}$ for $\lambda<1/\alpha$, it implies that any future robust detector that survives $o(n)$ edge corruptions would have to beat the tree-counting statistic in the window $1/\sqrt{\lambda}<s<\sqrt{\alpha}$, or the robust and non-robust thresholds must separate there.
  • The same min-formula might generalize to other correlated latent-permutation models with binomial edges, such as sparse correlated stochastic block models, where the analogous threshold would be determined by the subcriticality of the shared-edge graph and the tree-counting radius.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 6 minor

Summary. The paper studies the information-theoretic detection problem between a pair of correlated Erdős-Rényi graphs formed by subsampling a common parent G(n, λ/n) with probability s, and a pair of independent Erdős-Rényi graphs with matching marginals. The main result, Theorem 1.1, asserts a sharp threshold: strong detection is possible if and only if s > min{1/√λ, √α}, where α ≈ 0.338 is Otter's constant. The paper proves the lower bound (impossibility below threshold) by a conditional second-moment calculation: it conditions on the acyclic event A in the intersection graph, decomposes the likelihood ratio over permutation orbits, and reduces the second moment to a forest-counting sum that converges below the Otter threshold. The upper bound (achievability) is not proved in the paper but is cited to [11] and [31].

Significance. If the proof is repaired, the result closes a constant gap in the detection threshold for constant-degree correlated Erdős-Rényi graphs, improving the previous lower bound of [44] (s < min{1/√λ, 0.1}) to the conjectured sharp value. The lower-bound argument is self-contained and parameter-free, using FKG, Cauchy-Schwarz, and Otter's tree enumeration, and it exposes the detection-recovery and information-computation gaps discussed in Section 1.1. However, as submitted the proof contains a load-bearing typo in the running assumption and a few incorrect intermediate estimates, so the theorem is not yet verified as written.

major comments (3)
  1. [§2, Eq. (2.1)] The proof assumes λ²s < 1−ε and s < √α − ε, but the lower-bound hypothesis of Theorem 1.1 is s < min{1/√λ, √α} − ε. For λ > 1 these conditions are not equivalent: taking λ = 2 and s = 0.5 gives s < √α and s < 1/√λ, yet λ²s = 2. The only smallness condition actually needed by the proof is λs² < 1−ε, which appears in Lemma 2.1 (the event A requires cycle probability λs²/n), in Lemma 2.4, and in the short-orbit factor of (2.16)–(2.17). As printed, the proof leaves the interval s ∈ (1/λ², min{1/√λ, √α}) uncovered for every λ > 1, so the claimed impossibility range is unproved. The assumption should be corrected to λs² < 1−ε, and the proof re-verified under that condition.
  2. [§2, Lemma 2.3, Eq. (2.11)] The bound for |O| ≥ 2 is stated as 1 + O(n^{-2}). Expanding (2.10) to first order gives 1 − 2|O| s^{2|O|} λ(1−s)/n + O(n^{-2}), which is strictly smaller than 1 for large n, not 1 + O(n^{-2}). The displayed inequality is therefore false as written. Since the exact formula (2.10) actually implies the factor is < 1 for all |O| ≥ 2, the subsequent step can be repaired by bounding the product over non-full long orbits by 1, but the current text needs correction.
  3. [§2, Eqs. (2.16)–(2.17)] The passage from the conditional expectation to (2.16) is not valid as written. For a permutation σ with many fixed edges (e.g., σ = identity), |O1(J)| can be Θ(n²), and the product ∏_{O1}(1 + λs²(2s−1)/n) in (2.16) can be exponential in n when s > 1/2; this cannot be absorbed into the leading O(1) factor. The proof should multiply the O1 factor by the corresponding (1 − λs²/n)^{|O1|} from Lemma 2.4 before discarding it; the combined per-orbit factor is 1 − 2λs²(1−s)/n + O(n^{-2}) ≤ 1, so the final bound (2.17) is still within reach. As written, however, the intermediate inequality (2.16) does not follow from (2.15) and Lemma 2.4.
minor comments (6)
  1. [Abstract] The null model is described as two independent Erdős-Rényi graphs G(n, λ/n), but the body correctly defines Q as two independent G(n, λs/n) graphs; the abstract should be corrected.
  2. [Introduction, first paragraph] The parameters are introduced as λ, s ∈ (0, 1), but Theorem 1.1 allows λ > 1; the notation should read λ > 0, s ∈ (0, 1).
  3. [§2, just before Eq. (2.13)] The phrase "in the second inequality" should be "in the second equality", since the passage is an equality.
  4. [Lemma 2.5] The indexing in the list of unlabeled trees is written as "1 ≤ i ≤ k"; it should be "1 ≤ i ≤ f_k".
  5. [Lemma 2.5] Otter's asymptotic for unlabeled free trees is usually quoted with exponent k^{-5/2}; the displayed k^{-3/2} is harmless for the convergence argument, but the reference should be checked for accuracy.
  6. [Throughout] "Cauchy-Schwartz" should be "Cauchy-Schwarz".

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the lower-bound proof is self-contained and the upper bound is cited from independent prior work.

full rationale

The paper's central lower-bound result is proved by a conditional second-moment calculation with no fitted parameters and no quantity defined in terms of the target threshold. The only external input in the lower bound is Otter's classical asymptotic f_k = O(alpha^{-k}/k^{1.5}) for unlabeled trees, cited as [36]; this is an independent classical result, not derived from the theorem and not authored by the present author. The upper bound is explicitly assembled in Remark 1.2 from [11] and [31], which are works by other author groups, so there is no self-citation load-bearing chain. The apparent mismatch between assumption (2.1), which states lambda^2 s < 1 - epsilon, and the theorem's lower regime s < min{1/sqrt(lambda), sqrt(alpha)} is a correctness or proof-gap concern rather than circularity: even if the printed assumption is stronger than the theorem's hypothesis, the proof does not reduce any output to an input by construction. No fitted parameter is renamed as a prediction, and no self-cited uniqueness theorem is used to force the form of the threshold. Therefore the derivation chain is not circular.

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

The proof relies only on standard probabilistic inequalities, the classical Otter asymptotic, and the definition of the correlated ER model. No ad hoc parameters are introduced; the threshold arises from the radius of convergence of the forest generating function.

assumptions (3)
  • standard math Otter's asymptotic formula for the number of unlabeled trees: f_k = Θ(α^{-k}/k^{1.5})
    Used in Lemma 2.5 to bound the forest generating function; cited to [36] (Otter 1948).
  • standard math FKG inequality for decreasing events on a product probability space
    Used in Lemma 2.1 to lower bound the probability of the no-cycle event.
  • domain assumption The correlated Erdős-Rényi model with uniform random permutation π*
    This is the statistical model under study; the detection problem is defined with respect to this model.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Strong Detection Threshold for Correlated Erd\H{o}s-R\'enyi Graphs with Constant Average Degree." pith.science (2026). https://pith.science/paper/3JXTBXWU

@misc{pith2026250612752,
  author       = {Pith},
  title        = {Pith review of: Strong Detection Threshold for Correlated Erd\Hos-R\'enyi Graphs with Constant Average Degree},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3JXTBXWU}},
  note         = {Machine review of arXiv:2506.12752}
}
abstract

Consider a pair of correlated Erd\H{o}s-R\'enyi graphs $\mathcal G(n,\tfrac{\lambda}{n};s)$ that are subsampled from a common parent Erd\H{o}s-R\'enyi graph with average degree $\lambda$ and subsampling probability $s$. We establish a sharp information-theoretic threshold for the detection problem between this model and two independent Erd\H{o}s-R\'enyi graphs $\mathcal G(n,\tfrac{\lambda}{n})$, showing that strong detection is information-theoretically possible if and only if $s>\min\{ \tfrac{1}{\sqrt{\lambda}}, \sqrt{\alpha} \}$ where $\alpha\approx 0.338$ is the Otter's constant. Our result resolves a constant gap between arXiv:2203.14573 and arXiv:2008.10097.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

46 extracted references · 36 canonical work pages

  1. [11]

    Ding and H

    J. Ding and H. Du. Detection threshold for correlated Erd˝ os-R´ enyi graphs via densest sub- graph. In IEEE Transactions on Information Theory , 69(8):5289–5298, 2023

    work page 2023

  2. [31]

    C. Mao, Y. Wu, J. Xu, and S. H. Yu. Testing network correlation efficiently via counting trees. In Annals of Statistics , 52(6):2483–2505, 2024. 13

    work page 2024

  3. [44]

    Y. Wu, J. Xu and S. H. Yu. Testing correlation of unlabeled random graphs. In Annals of Applied Probability, 33(4): 2519–2558, 2023

    work page 2023

  4. [1]

    Barak, C

    B. Barak, C. N. Chou, Z. Lei, T. Schramm, and Y. Sheng. (Nearly) efficient algorithms for the graph matching problem on correlated random graphs. In Advances in Neural Information Processing Systems (NIPS), volume 32. Curran Associates, Inc., 2019

    work page 2019

  5. [2]

    A. Berg, T. Berg, and J. Malik. Shape matching and object recognition using low distortion correspondences. In 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), volume 1, pages 26–33, 2005

    work page 2005

  6. [3]

    Bozorg, S

    M. Bozorg, S. Salehkaleybar, and M. Hashemi. Seedless graph matching via tail of degree distribution for correlated Erd˝ os-R´ enyi graphs. arXiv, preprint, arXiv:1907.06334

    arXiv 1907

  7. [4]

    G. Chen, J. Ding, S. Gong, and Z. Li. A computational transition for detecting correlated stochastic block models by low-degree polynomials. arXiv preprint, arXiv:2409.00966

    work page arXiv

  8. [5]

    G. Chen, J. Ding, S. Gong, and Z. Li. Detecting correlation efficiently in stochastic block mod- els: breaking Otter’s threshold by counting decorated trees. arXiv preprint, arXiv:2503.06464

    work page arXiv

Show all 46 references
  1. [6]

    T. Cour, P. Srinivasan, and J. Shi. Balanced graph matching. In Advances in Neural Infor- mation Processing Systems (NIPS) , volume 19. MIT Press, 2006

    2006

  2. [7]

    Cullina and N

    D. Cullina and N. Kiyavash. Exact alignment recovery for correlated Erd˝ os-R´ enyi graphs. arXiv preprint, arXiv:1711.06783

    arXiv

  3. [8]

    Cullina and N

    D. Cullina and N. Kiyavash. Improved achievability and converse bounds for Erd˝ os-R´ enyi graph matching. In Proceedings of the ACM International Conference on Measurement and Modeling of Computer Science (SIGMETRICS) , pages 63–72. ACM, 2016

    2016

  4. [9]

    Cullina, N

    D. Cullina, N. Kiyavash, P. Mittal, and H. V. Poor. Partial recovery of Erd˝ os-R´ enyi graph alignment via k-core alignment. In Proceedings of the ACM International Conference on Mea- surement and Modeling of Computer Science (SIGMETRICS) , pages 99–100. ACM, 2020

    2020

  5. [10]

    O. E. Dai, D. Cullina, N. Kiyavash, and M. Grossglauser. Analysis of a canonical labeling algorithm for the alignment of correlated Erd˝ os-R´ enyi graphs. InProceedings of the ACM on Measurement and Analysis of Computing Systems , 3(2), jun 2019

    2019

  6. [12]

    Ding and H

    J. Ding and H. Du. Matching recovery threshold for correlated random graphs. In Annals of Statistics, 51(4): 1718-1743, 2023

    2023

  7. [13]

    J. Ding, H. Du and Z. Li. Low-Degree Hardness of Detection for Correlated Erd˝ os-R´ enyi Graphs. to appear in Annals of Statistics

  8. [14]

    Ding and Z

    J. Ding and Z. Li. A polynomial time iterative algorithm for matching Gaussian matrices with non-vanishing correlation. to appear in Foundations of Computational Mathematics . 12

  9. [15]

    Ding and Z

    J. Ding and Z. Li. A polynomial-time iterative algorithm for random graph matching with non-vanishing correlation. arXiv preprint, arXiv:2306.00266

    arXiv

  10. [16]

    J. Ding, Z. Ma, Y. Wu, and J. Xu. Efficient random graph matching via degree profiles. In Probability Theory and Related Fields , 179(1-2):29–115, 2021

    2021

  11. [17]

    H. Du. Optimal recovery of correlated Erd˝ os-R´ enyi graphs. arXiv preprint, arXiv:2502.12077

    arXiv

  12. [18]

    Z. Fan, C. Mao, Y. Wu, and J. Xu. Spectral graph matching and regularized quadratic relax- ations I: Algorithm and theory. In Foundations of Computational Mathematics , 23(5):1511- 1565, 2023

    2023

  13. [19]

    Z. Fan, C. Mao, Y. Wu, and J. Xu. Spectral graph matching and regularized quadratic relax- ations II: Erd˝ os-R´ enyi graphs and universality. InFoundations of Computational Mathematics, 23(5):1567-1617, 2023

    2023

  14. [20]

    Ganassali and L

    L. Ganassali and L. Massouli´ e. From tree matching to sparse graph alignment. In Proceedings of 33rd Conference on Learning Theory (COLT) , pages 1633–1665. PMLR, 2020

    2020

  15. [21]

    Ganassali, L

    L. Ganassali, L. Massouli´ e, and M. Lelarge. Impossibility of Partial Recovery in the Graph Alignment Problem. In Proceedings of 34th Conference on Learning Theory (COLT) , pages 2080–2102. PMLR, 2021

    2021

  16. [22]

    Ganassali, L

    L. Ganassali, L. Massouli´ e, and M. Lelarge. Correlation detection in trees for planted graph alignment. In Annals of Applied Probability , 34(3):2799–2843, 2024

    2024

  17. [23]

    Ganassali, L

    L. Ganassali, L. Massouli´ e, and G. Semerjian. Statistical limits of correlation detection in trees. In Annals of Applied Probability , 34(4):3701–3734, 2024

    2024

  18. [24]

    Gong and Z

    S. Gong and Z. Li. The Umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regime. arXiv preprint, arXiv:2402.15095

    arXiv

  19. [25]

    Haghighi, A

    A. Haghighi, A. Ng, and C. Manning. Robust textual inference via graph matching. In Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (EMNLP) , pages 387–394, 2005

    2005

  20. [26]

    Huang, X

    D. Huang, X. Song, and P. Yang. Information-theoretic thresholds for the alignments of partially correlated graphs. In Proceedings of 37th Conference on Learning Theory (COLT) . PMLR, 2024

    2024

  21. [27]

    Z. Li. Algorithmic contiguity from low-degree conjecture and applications in correlated random graphs. arXiv preprint, arXiv:2502.09832

  22. [28]

    Hall and L

    G. Hall and L. Massouli´ e. Partial recovery in the graph alignment problem. In Operations Research, 71(1):259–272, 2023

    2023

  23. [29]

    C. Mao, M. Rudelson, and K. Tikhomirov. Random Graph Matching with Improved Noise Robustness. In Proceedings of Thirty Fourth Conference on Learning Theory (COLT) , pages 3296–3329. PMLR, 2021

    2021

  24. [30]

    C. Mao, M. Rudelson, and K. Tikhomirov. Exact matching of random graphs with constant correlation. In Probability Theory and Related Fields , 186(2):327–389, 2023

    2023

  25. [32]

    C. Mao, Y. Wu, J. Xu, and S. H. Yu, Random graph matching at Otter’s threshold via counting chandeliers. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC), pages 1345–1356. ACM, 2023

    2023

  26. [33]

    Mossel and J

    E. Mossel and J. Xu. Seeded graph matching via large neighborhood statistics. In Random Structures and Algorithms , 57(3):570–611, 2020

    2020

  27. [34]

    Narayanan and V

    A. Narayanan and V. Shmatikov. Robust de-anonymization of large sparse datasets. In IEEE Symposium on Security and Privacy , pages 111–125. IEEE, 2008

    2008

  28. [35]

    Narayanan and V

    A. Narayanan and V. Shmatikov. De-anonymizing social networks. In IEEE Symposium on Security and Privacy (ISSP) , pages 173–187. IEEE, 2009

    2009

  29. [36]

    R. Otter. The number of trees. In Annals of Mathematics , pages 583–599, 1948

    1948

  30. [37]

    Pedarsani and M

    P. Pedarsani and M. Grossglauser. On the privacy of anonymized networks. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , pages 1235–1243. ACM, 2011

    2011

  31. [38]

    M. Z. Racz and A. Sridhar. Correlated randomly growing graphs. In Annals of Applied Probability, 32(2):1058–1111, 2022

    2022

  32. [39]

    M. Z. Racz and A. Sridhar. Correlated stochastic block models: Exact graph matching with applications to recovering communities. In Advances in Neural Information Processing Systems (NIPS), volume 34. Curran Associates, Inc., 2021

    2021

  33. [40]

    Shirani, S

    F. Shirani, S. Garg, and E. Erkip. Seeded graph matching: Efficient algorithms and theoretical guarantees. In 2017 51st Asilomar Conference on Signals, Systems, and Computers , pages 253–257, 2017

    2017

  34. [41]

    Singh, J

    R. Singh, J. Xu, and B. Berger. Global alignment of multiple protein interaction networks with application to functional orthology detection. In Proceedings of the National Academy of Sciences of the United States of America , 105:12763–12768, 10 2008

    2008

  35. [42]

    J. T. Vogelstein, J. M. Conroy, V. Lyzinski, L. J. Podrazik, S. G. Kratzer, E. T. Harley, D. E. Fishkind, R. J. Vogelstein, and C. E. Priebe. Fast approximate quadratic programming for graph matching. In PLOS ONE , 10(4):1–17, 2015

    2015

  36. [43]

    H. Wang, Y. Wu, J. Xu, and I. Yolou. Random graph matching in geometric models: the case of complete graphs. In Proceedings of 35th Conference on Learning Theory (COLT) . PMLR, 2022

    2022

  37. [45]

    Y. Wu, J. Xu and S. H. Yu. Settling the sharp reconstruction thresholds of random graph matching. In IEEE Transactions on Information Theory , 68(8):5391–5417, 2022

    2022

  38. [46]

    Yartseva and M

    L. Yartseva and M. Grossglauser. On the performance of percolation graph matching. In Proceedings of the 1st ACM Conference on Online Social Networks (COSN) , pages 119–130. ACM, 2013. 14

    2013

Pith tools

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