Pith. sign in

REVIEW 3 major objections 4 minor 51 references

Harnessing Multiple Correlated Networks for Exact Community Recovery

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

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

Pith's one-line read Exact community recovery from a constant number of correlated networks is characterized by two sharp inequalities, and for K≥3 extra graphs can succeed where any K−1 fail.

desk verdict Sharp multi-graph community recovery threshold for K>=3 is likely right, but the general-K impossibility proof is asserted, not supplied, so the if-and-only-if claim is not yet established as written. read the letter →

arxiv 2412.02796 v1 pith:GJA2RDVP submitted 2024-12-03 math.ST cs.ITcs.LGcs.SImath.ITmath.PRstat.TH

Miklós Z. Rácz , Jifan Zhang This is my paper · ORCID
classification math.STcs.ITcs.LGcs.SImath.ITmath.PRstat.TH MSC 05C8062H30
keywords correlatedstochasticblockmodelsexactcommunityrecoverygraphmatchingk-coreinformation-theoreticthresholdmultiplenetworksphasetransition
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 determines the exact information-theoretic threshold for recovering two latent communities from a constant number K of correlated networks. Each network is an edge-subsampled, independently permuted copy of one stochastic block model, and the communities are planted before the copies are made. The result is a pair of strict inequalities: the union graph must be identifiable, and a weighted combination of a graph-matching term and a community-recovery term must exceed one. For every K≥3 the second inequality can hold even when no pairwise latent matching is exactly recoverable, so several graphs genuinely add information. This answers the open K-graph question raised by the two-graph analysis.

What carries the argument

The load-bearing object is the pairwise $k$-core matching with $k=13$: for each pair of graphs, take the permutation whose intersection graph has the largest 13-core, and match only the vertices in that core. Each such matching misses about $n^{1-s^2T_c(a,b)+o(1)}$ vertices. For $K$ graphs a vertex is called good when the graph whose edges are its pairwise matchings connects all $K$ graphs, and bad otherwise. The central estimate, Lemmas 4.7 and 7.4, bounds the intersection of the bad sets $F^*_{ij}$ over cross pairs by $n^{1-s(1-(1-s)^{K-1})T_c(a,b)+o(1)}$, and this exponent is exactly what the cleanup majority vote needs. The argument also uses the Łuczak expansion to show vertices outside the cores have only weakly connected neighborhoods.

What would settle it

For $K=3$, $s=0.2$, $a=16$, $b=1$, estimate the number of vertices missed by the true 13-core matchings in both $(G_1,G_2)$ and $(G_1,G_3)$. The proof requires this intersection to grow no faster than $n^{1-s(1-(1-s)^2)T_c(a,b)+o(1)}=n^{0.388+o(1)}$; an observed exponent clearly above $0.388$ would break the majority-vote cleanup and refute the claimed threshold.

Watch

Extended reading notes

Core claim

With $K$ correlated SBMs, each marginally $\mathrm{SBM}(n, s a \log n/n, s b \log n/n)$, exact community recovery is possible if and only if $(1-(1-s)^K)D_+(a,b)>1$ and $s(1-(1-s)^{K-1})T_c(a,b)+s(1-s)^{K-1}D_+(a,b)>1$, where $D_+(a,b)=(\sqrt a-\sqrt b)^2/2$ and $T_c(a,b)=(a+b)/2$. The first condition is the union-graph threshold: it is what would suffice if all latent vertex alignments were known. The second condition is the new content for $K\ge 3$. Its matching term uses pairwise 13-core matchings, whose error sets are controlled by intersection size $n^{1-s(1-(1-s)^{K-1})T_c(a,b)+o(1)}$, and its recovery term uses edges that appear only in the first graph, giving the factor $s(1-s)^{K-1}$. The same machinery gives the sharp exact graph matching threshold $s(1-(1-s)^{K-1})T_c(a,b)>1$.

Load-bearing premise

The proof stands on the claim that the small sets of vertices left unmatched by pairwise matchings do not overlap much across different pairs; if those overlaps were materially larger than the stated bound, the cleanup majority vote would fail and the claimed threshold could not be reached.

Editorial extensions

If this is right

  • For every $K\ge 3$ there is a parameter region where exact community recovery is possible with $K$ graphs although it is impossible with $K-1$ graphs and no latent matching is exactly recoverable.
  • Exact graph matching from $K$ graphs is possible exactly when $s(1-(1-s)^{K-1})T_c(a,b)>1$, which is strictly weaker for $K>2$ than the two-graph matching threshold.
  • When the true alignments are known, condition (1.8) alone suffices; without them, the matching term $s(1-(1-s)^{K-1})T_c(a,b)$ is the price of not knowing the alignments.
  • The threshold interpolates cleanly from the single-graph threshold $sD_+(a,b)>1$ to the fully aligned union-graph threshold $(1-(1-s)^K)D_+(a,b)>1$ as the matching information improves.
  • Each additional graph weakens the effective matching exponent from $s^2T_c$ toward $sT_c$, which is why several graphs help even when pairwise matchings fail.

Reading between the lines

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

  • A likely general principle: when several partial pairwise alignments are aggregated, the relevant error term is the intersection of their failure sets, not their union; this may transfer to other joint recovery problems such as multiple-community SBMs or attributed graphs.
  • The paper leaves open whether the $K$-graph threshold can be met in polynomial time; if a polynomial-time partial $k$-core matching is found at these densities, the recovery algorithm becomes efficient.
  • Under the alternative construction $G'_i=G_0\vee H_i$ with independent $H_i$, thresholds will generally differ for $K\ge 3$, and the same question is naturally posed there.
  • A direct testable prediction: algorithms that first build a partial matching per pair and then majority-vote on the induced union graph should succeed exactly in the claimed regime; failures would show up first as bad-set intersections exceeding the bound.
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 / 4 minor

Summary. This paper studies exact community recovery and exact graph matching from K edge-correlated stochastic block models with two balanced communities, in the logarithmic-degree regime. The main results are Theorems 1–4: for any constant K, exact community recovery is claimed to be possible exactly when the union-graph divergence (1-(1-s)^K)D_+(a,b) exceeds 1 and the combined matching-and-recovery expression s(1-(1-s)^{K-1})T_c(a,b)+s(1-s)^{K-1}D_+(a,b) exceeds 1; exact graph matching is claimed to be possible exactly when s(1-(1-s)^{K-1})T_c(a,b)>1. The achievability proof uses pairwise 13-core matchings, a metagraph criterion to split vertices into 'good' and 'bad' sets, and majority-vote cleanup; the converse uses MAP-type arguments. The K=3 case is worked out in full detail in Sections 5 and 6, and the positive direction for general K is presented in Section 7. The general-K impossibility proof, however, is only sketched in Section 8.

Significance. If valid, the threshold answers the open question from Gaudio, Racz, and Sridhar and identifies a region where K graphs jointly enable exact community recovery even though no K-1 graphs do and no pairwise matching is exactly recoverable. The paper contains no fitted parameters, and the main technical quantities are explicit functions of a, b, s, and K. The k-core intersection bounds (Lemmas 4.7 and 7.4) are the key new technical content and appear plausible for K=3 and for the positive direction for general K. The K=3 converse in Section 6 is substantial and detailed. However, the claimed if-and-only-if characterization for all constant K is not currently established, because the converse for K≥4 is omitted rather than proved.

major comments (3)
  1. [Section 8] The proof of Theorem 2 for general K is not present. The section states that the proof follows by generalizing the K=3 argument and then says 'we omit the details,' listing only formal substitutions such as replacing (2s^2-s^3) by s(1-(1-s)^{K-1}) and s(1-s)^2 by s(1-s)^{K-1}. It also refers back to condition (6.1), which is the K=3 condition, rather than to the general condition (1.11). Since Theorem 2 provides the converse half of the if-and-only-if threshold (1.7), the main theorem is not established for K≥4 without a complete argument. The missing work is not merely notational: the K-way posterior over (A,B_2,...,B_K), the correct analogue of the set S*, and the variance estimate for the bad-set sum must be written out.
  2. [Section 9.2] The impossibility proof for Theorem 4 invokes [16, Theorem 1] with the condition stated as s(1-(1-s)^{K-1})<1. The theorem being invoked has the condition s_1 s_2 T_c(a,b)<1 for impossibility of exact graph matching, so the displayed inequality is missing the T_c(a,b) factor. As written, the contradiction step does not follow; the correct condition is s(1-(1-s)^{K-1})T_c(a,b)<1.
  3. [Section 9.1 and Lemma 7.6] The proof of Theorem 3 relies on the bad-vertex count tending to zero, but the text says 'When 1 - s(1-(1-s)^{K-1})T_c(a,b) > 1', which cannot hold for positive s; the intended condition is s(1-(1-s)^{K-1})T_c(a,b)>1, equivalently 1 - s(1-(1-s)^{K-1})T_c(a,b)<0. In addition, the statement of Lemma 7.6 omits the exponent 1 in the bound and writes n^{-s(1-(1-s)^{K-1})T_c(a,b)+o(1)} instead of n^{1-s(1-(1-s)^{K-1})T_c(a,b)+o(1)}. These are likely typos, but because they occur in the proof of a main theorem they should be corrected.
minor comments (4)
  1. [Section 7.4, Lemma 7.7] The statement of Lemma 7.7 assumes (1-(1-s)^3)D_+(a,b)>1+2ε|log(a/b)|, while the proof and the surrounding general-K argument use (1-(1-s)^K); the exponent 3 should be replaced by K.
  2. [Section 7.3, proof of Lemma 7.4] The proof says 'degree of vertex v in the graph G1 ∨ G3 . . .∨ GL'; the intended union is over the first L graphs, so the notation should be G1∨G2∨...∨GL or an explicit statement that the indexing is over the L chosen graphs.
  3. [Section 1.6] The definition of the inter-community vertex pairs uses the symbol E^+(σ) for both intra-community and inter-community sets; the second occurrence should be E^-(σ).
  4. [Lemma 4.7 and surrounding text] The statement and proof index the unmatched sets inconsistently: Lemma 4.7 states |F*_ij ∩ F*_jk|, while the proof writes |F*_12 ∩ F*_23| = |F*_21 ∩ F*_23| = |F*_12 ∩ F*_13|. The sets should be explicitly pulled back to a common vertex set, presumably that of G1, so that the intersection is well defined.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity; the derivation relies on independent prior K=2 results and a new K-graph analysis, though the general-K impossibility proof is omitted.

full rationale

The paper's central derivation is not circular. The threshold conditions in Theorems 1 and 2 are obtained by combining new K-graph k-core matching bounds (Lemmas 4.7 and 7.4) with Chernoff/Hoeffding estimates of majority-vote failure probabilities; no fitted parameter is renamed as a prediction, and no quantity is defined in terms of the target result. The imported tools from prior work are independent inputs: the k-core matching lemmas from Gaudio, Racz, and Sridhar (COLT 2022) concern the K=2 setting and do not assume the K-graph threshold; the single-graph SBM results of Mossel, Neeman, and Sly are external to the paper. The general-K threshold reduces to the known K=1 and K=2 thresholds in boundary cases, which is consistency rather than circularity. The paper does contain a significant proof gap unrelated to circularity: Section 8 sketches the general-K impossibility proof and states 'The proof follows the same arguments with more involved notation, and hence we omit the details,' so Theorem 2 for K>=4 is not established by the submitted text. This is an omitted proof and a correctness risk, not a circular step, because the claimed reduction is not present. Accordingly, no circular step is scored, and the circularity score is 0.

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

The central claim rests on several imported rigorous results from the SBM and graph matching literature. None are fitted or derived from the target claim. The paper's own technical lemmas are proved for K=3 and partially sketched for general K.

assumptions (4)
  • standard math Exact recovery threshold for a single SBM: D_+(a,b) > 1 implies recoverable, D_+(a,b) < 1 implies impossible.
    Used for recovery from G1 alone and for recovery from the union graph (Section 1.1). Cited to [2, 37, 3].
  • standard math Pairwise exact graph matching threshold for two correlated SBMs: s^2 T_c(a,b) > 1 is achievable and s^2 T_c(a,b) < 1 is impossible; for unequal subsampling probabilities s1, s2 the threshold is s1 s2 T_c(a,b).
    Used in Theorems 3-4 and in the impossibility reduction of Section 9.2. Cited to [43] and [16].
  • domain assumption The k-core matching estimator for two graphs is correct on the matched set, and the number of unmatched vertices is at most n^{1 - s^2 T_c(a,b) + o(1)}.
    The algorithm uses 13-core matchings as a subroutine; Lemmas 4.5 and 4.6 are imported from [24] and control the F*_ij sets.
  • standard math The Mossel-Neeman-Sly almost exact recovery algorithm for a single SBM outputs a labeling correct on all but a small set I_epsilon(G), with controlled neighborhood intersections.
    Used in Step 1 of the recovery algorithm and in Lemmas 3.5-3.8, following [37] and [24].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Harnessing Multiple Correlated Networks for Exact Community Recovery." pith.science (2026). https://pith.science/paper/GJA2RDVP

@misc{pith2026241202796,
  author       = {Pith},
  title        = {Pith review of: Harnessing Multiple Correlated Networks for Exact Community Recovery},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GJA2RDVP}},
  note         = {Machine review of arXiv:2412.02796}
}
abstract

We study the problem of learning latent community structure from multiple correlated networks, focusing on edge-correlated stochastic block models with two balanced communities. Recent work of Gaudio, R\'acz, and Sridhar (COLT 2022) determined the precise information-theoretic threshold for exact community recovery using two correlated graphs; in particular, this showcased the subtle interplay between community recovery and graph matching. Here we study the natural setting of more than two graphs. The main challenge lies in understanding how to aggregate information across several graphs when none of the pairwise latent vertex correspondences can be exactly recovered. Our main result derives the precise information-theoretic threshold for exact community recovery using any constant number of correlated graphs, answering a question of Gaudio, R\'acz, and Sridhar (COLT 2022). In particular, for every $K \geq 3$ we uncover and characterize a region of the parameter space where exact community recovery is possible using $K$ correlated graphs, even though (1) this is information-theoretically impossible using any $K-1$ of them and (2) none of the latent matchings can be exactly recovered.

Figures

Figures reproduced from arXiv: 2412.02796 by the authors.

Figure 1
Figure 1. Schematic showing the construction of multiple correlated SBMs (see text for details). [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Phase diagram for exact community recovery for three graphs with fixed [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Schematic landscape of partial matchings over three graphs. [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Schematic showing the meta graph MGv when K = 5. k-core are only weakly connected with “bad” vertices. Another hurdle needed to overcome, as stated in [24], concerns the almost exact community recovery in Step 1 which is subsequently used for majority votes. Therefore,…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

51 extracted references · 44 canonical work pages

  1. [1]

    E. Abbe. Community Detection and Stochastic Block Models: Recent Developments. Journal of Machine Learning Research, 18(177):1–86, 2018

    work page 2018

  2. [2]

    E. Abbe, A. S. Bandeira, and G. Hall. Exact Recovery in the Stochastic Block Model. IEEE Transactions on Information Theory , 62(1):471–487, 2016

    work page 2016

  3. [3]

    Abbe and C

    E. Abbe and C. Sandon. Community detection in general stochastic block models: Funda- mental limits and efficient algorithms for recovery. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS) , pages 670–688. IEEE, 2015

    work page 2015

  4. [4]

    Robust Graph Matching when Nodes are Corrupt

    T. Ameen and B. Hajek. Robust Graph Matching when Nodes are Corrupt. Preprint available at https://arxiv.org/abs/2310.18543, 2023

    work page Pith review arXiv 2023

  5. [5]

    Ameen and B

    T. Ameen and B. Hajek. Exact Random Graph Matching with Multiple Graphs. Preprint available at https://arxiv.org/abs/2405.12293, 2024. 50

    arXiv 2024

  6. [6]

    Barak, C.-N

    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 (NeurIPS), volume 32, pages 9190–9198, 2019

    work page 2019

  7. [7]

    Bordenave, M

    C. Bordenave, M. Lelarge, and L. Massouli´ e. Non-backtracking Spectrum of Random Graphs: Community Detection and Non-regular Ramanujan Graphs. In Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS) , pages 1347–1357. IEEE, 2015

    work page 2015

  8. [8]

    Bringmann, T

    K. Bringmann, T. Friedrich, and A. Krohmer. De-anonymization of Heterogeneous Random Graphs in Quasilinear Time. In Proceedings of the 22nd Annual European Symposium on Algorithms (ESA) , pages 197–208, 2014

    work page 2014

Show all 51 references
  1. [9]

    Chai and M

    S. Chai and M. Z. R´ acz. Efficient Graph Matching for Correlated Stochastic Block Models. In Advances in Neural Information Processing Systems (NeurIPS) , volume 38, 2024

    2024

  2. [10]

    G. Chen, J. Ding, S. Gong, and Z. Li. A computational transition for detecting correlated stochastic block models by low-degree polynomials. Preprint available at https://arxiv. org/abs/2409.00966, 2024

    2024

  3. [11]

    Chiasserini, M

    C.-F. Chiasserini, M. Garetto, and E. Leonardi. Social Network De-Anonymization Under Scale-Free User Relations. IEEE/ACM Transactions on Networking , 24(6):3756–3769, 2016

    2016

  4. [12]

    T. Cour, P. Srinivasan, and J. Shi. Balanced Graph Matching. In Advances in Neural Infor- mation Processing Systems (NeurIPS) , volume 19, 2006

    2006

  5. [13]

    Cullina and N

    D. Cullina and N. Kiyavash. Improved Achievability and Converse Bounds for Erd˝ os-R´ enyi Graph Matching. In ACM SIGMETRICS, volume 44, pages 63–72, 2016

    2016

  6. [14]

    Cullina and N

    D. Cullina and N. Kiyavash. Exact alignment recovery for correlated Erd˝ os-R´ enyi graphs. Preprint available at https://arxiv.org/abs/1711.06783, 2018

    2018 arXiv

  7. [15]

    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 ACM SIGMETRICS Performance Evaluation Review , volume 48, pages 99–100. ACM, 2020

    2020

  8. [16]

    Cullina, K

    D. Cullina, K. Singhal, N. Kiyavash, and P. Mittal. On the Simultaneous Preservation of Privacy and Community Structure in Anonymized Networks. Preprint available at https: //arxiv.org/abs/1603.08028, 2016

    2016 arXiv

  9. [17]

    Decelle, F

    A. Decelle, F. Krzakala, C. Moore, and L. Zdeborov´ a. Asymptotic analysis of the stochas- tic block model for modular networks and its algorithmic applications. Physical Review E , 84(6):066106, 2011

    2011

  10. [18]

    Ding and H

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

    2023

  11. [19]

    J. Ding, Y. Fei, and Y. Wang. Efficiently matching random inhomogeneous graphs via degree profiles. Preprint available at https://arxiv.org/abs/2310.10441, 2023

    2023 arXiv

  12. [20]

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

    2021

  13. [21]

    Z. Fan, C. Mao, Y. Wu, and J. Xu. Spectral Graph Matching and Regularized Quadratic Relaxations: Algorithm and Theory. In Proc. of the 37th Int. Conf. on Machine Learning (ICML), volume 119 of Proc. of Machine Learning Research (PMLR), pages 2985–2995, 2020

    2020

  14. [22]

    Ganassali and L

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

    2020

  15. [23]

    Ganassali, L

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

    2021

  16. [24]

    Gaudio, M

    J. Gaudio, M. Z. R´ acz, and A. Sridhar. Exact Community Recovery in Correlated Stochastic Block Models. In Proceedings of the 35th Conference on Learning Theory (COLT) , volume 178 of Proceedings of Machine Learning Research (PMLR), pages 2183–2241, 2022

    2022

  17. [25]

    Girvan and M

    M. Girvan and M. E. J. Newman. Community structure in social and biological networks. Proceedings of the National Academy of Sciences , 99(12):7821–7826, 2002

    2002

  18. [26]

    Hall and L

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

    2023

  19. [27]

    P. W. Holland, K. B. Laskey, and S. Leinhardt. Stochastic blockmodels: First steps. Social Networks, 5(2):109–137, 1983

    1983

  20. [28]

    Korula and S

    N. Korula and S. Lattanzi. An efficient reconciliation algorithm for social networks.Proceedings of the VLDB Endowment , 7(5):377–388, 2014

    2014

  21. [29]

    T. Luczak. Size and connectivity of the k-core of a random graph. Discrete Mathematics , 91(1):61–68, 1991

    1991

  22. [30]

    Lyzinski

    V. Lyzinski. Information Recovery in Shuffled Graphs via Graph Matching. IEEE Transactions on Information Theory , 64(5):3254–3273, 2018

    2018

  23. [31]

    Lyzinski, D

    V. Lyzinski, D. L. Sussman, D. E. Fishkind, H. Pao, L. Chen, J. T. Vogelstein, Y. Park, and C. E. Priebe. Spectral clustering for divide-and-conquer graph matching. Parallel Computing, 47:70–87, 2015

    2015

  24. [32]

    C. Mao, M. Rudelson, and K. Tikhomirov. Random Graph Matching with Improved Noise Robustness. In Proceedings of the 34th Conference on Learning Theory (COLT) , volume 134 of Proceedings of Machine Learning Research (PMLR), pages 3296–3329, 2021

    2021

  25. [33]

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

    2023

  26. [34]

    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, 2023

    2023

  27. [35]

    Massouli´ e

    L. Massouli´ e. Community detection thresholds and the weak Ramanujan property. In Proc. of the 46th Annual ACM Symposium on Theory of Computing (STOC) , pages 694–703, 2014

    2014

  28. [36]

    Mossel, J

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

    2015

  29. [37]

    Mossel, J

    E. Mossel, J. Neeman, and A. Sly. Consistency thresholds for the planted bisection model. Electronic Journal of Probability , 21(none):1 – 24, 2016

    2016

  30. [38]

    Mossel, J

    E. Mossel, J. Neeman, and A. Sly. A proof of the block model threshold conjecture. Combi- natorica, 38(3):665–708, 2018

    2018

  31. [39]

    Mossel and J

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

    2020

  32. [40]

    Narayanan and V

    A. Narayanan and V. Shmatikov. De-anonymizing Social Networks. In Proceedings of the 30th IEEE Symposium on Security and Privacy , pages 173–187. IEEE Computer Society, 2009

    2009

  33. [41]

    Onaran, S

    E. Onaran, S. Garg, and E. Erkip. Optimal de-anonymization in random graphs with commu- nity structure. In 2016 50th Asilomar Conference on Signals, Systems and Computers , pages 709–713. IEEE, 2016

    2016

  34. [42]

    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 (KDD), pages 1235–1243, 2011

    2011

  35. [43]

    M. Z. R´ acz and A. Sridhar. Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities. In Advances in Neural Information Processing Systems (NeurIPS) , volume 34, pages 22259–22273, 2021

    2021

  36. [44]

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

    2022

  37. [45]

    M. Z. R´ acz and A. Sridhar. Matching Correlated Inhomogeneous Random Graphs using the k-core Estimator. In 2023 IEEE International Symposium on Information Theory (ISIT) , pages 2499–2504, 2023

    2023

  38. [46]

    Singh, J

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

    2008

  39. [47]

    H. Wang, Y. Wu, J. Xu, and I. Yolou. Random Graph Matching in Geometric Models: the Case of Complete Graphs. In Proceedings of the 35th Conference on Learning Theory (COLT), volume 178 of Proceedings of Machine Learning Research (PMLR), pages 3441–3488, 2022

    2022

  40. [48]

    Y. Wu, J. Xu, and S. H. Yu. Settling the Sharp Reconstruction Thresholds of Random Graph Matching. IEEE Transactions on Information Theory , 68(8):5391–5417, 2022

    2022

  41. [49]

    Yang and H

    J. Yang and H. W. Chung. Graph Matching in Correlated Stochastic Block Models for Im- proved Graph Clustering. In Proceedings of the 2023 59th Annual Allerton Conference on Communication, Control, and Computing (Allerton) , pages 1–8. IEEE, 2023

    2023

  42. [50]

    J. Yang, D. Shin, and H. W. Chung. Efficient Algorithms for Exact Graph Matching on Correlated Stochastic Block Models with Constant Correlation. In Proceedings of the 40th International Conference on Machine Learning (ICML), volume 202 of Proceedings of Machine Learning Resea...

    2023

  43. [51]

    L. Yu, J. Xu, and X. Lin. The Power of D-hops in Matching Power-Law Graphs. Proceedings of the ACM on Measurement and Analysis of Computing Systems , 5(2):1–43, 2021. 53

    2021

Pith tools

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