Pith. sign in

REVIEW 1 major objections 4 minor 71 references

Efficient Graph Matching for Correlated Stochastic Block Models

T0 review · 1 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 For correlated two-community stochastic block models with logarithmic average degree, a polynomial-time algorithm matches all but a vanishing fraction of vertices correctly when the squared edge correlation exceeds α≈0.338, and matches…

desk verdict Solid theorem, overclaimed abstract: exact matching is proved only under s^2 > alpha, not literally whenever information theory allows. read the letter →

arxiv 2412.02661 v1 pith:DF7V67AM submitted 2024-12-03 cs.DS cs.SImath.PRmath.STstat.MLstat.TH

Shuwen Chai , Miklós Z. Rácz This is my paper · ORCID
classification cs.DScs.SImath.PRmath.STstat.MLstat.TH MSC 05C8068R1068W2062H30
keywords graphmatchingcorrelatedstochasticblockmodelschandeliersubgraphcountsexactcommunityrecoveryinformation-computationgapOtterconstantlogarithmicaveragedegreerandomalignment
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 claims that the vertex correspondence between two correlated two-community stochastic block models can be recovered by a polynomial-time algorithm in the logarithmic-average-degree regime whenever the squared edge correlation exceeds Otter's tree-counting constant α≈0.338. In that regime the algorithm matches all but a vanishing fraction of vertices correctly with high probability; if in addition s²(a+b)/2>1, which is the information-theoretic threshold for exact matching, it recovers the full latent permutation exactly. The result resolves the previously open problem of whether efficient exact graph matching is possible whenever information-theoretic exact matching is possible. The proof carries the chandelier-counting strategy for correlated random graphs over to community-structured graphs, and its main technical work is controlling the estimation errors that arise because the community partition cannot be exactly recovered from a single graph in the relevant parameter regimes. A direct application is an efficient algorithm for exact community recovery from two correlated graphs in regimes where a single graph provably cannot achieve it.

What carries the argument

The paper's central object is a chandelier, a rooted tree built from L branches, each a path of M edges (the wire) ending in a distinct rooted tree of K edges (the bulb), with all bulbs pairwise non-isomorphic, at most R rooted automorphisms, and maximum degree at most D. Signed subgraph counts count rooted copies of each chandelier in the approximately centralized adjacency matrix, where the expected edge probability is subtracted using a community-label estimate. The signature vector stacks these counts over the full chandelier family; the similarity score is the automorphism-weighted inner product of two signatures. The family is sized so that true-pair scores concentrate around μ=|T| n^N ρ^N $σ_eff^{{2N}}$ while fake-pair scores have mean o(μ) and variance o(μ²/n²), which is what lets a simple threshold separate correct from incorrect matches. A final seeded matching step uses common-neighbor counts under the partial matching to reach the exact permutation.

What would settle it

Simulate the community-recovery step in the regime sD+(a,b)<1 and estimate, for a fixed set S of O(log n) vertices, the probability that every vertex of S is misclassified; finding that this probability is not O($n^{{-|S|(sD+(a,b)-ε|log(a/b)|)}}$) for arbitrarily small ε,δ>0 would violate Lemma 3.6 and undo the variance bound that supports almost-exact matching.

Watch

Extended reading notes

Core claim

The central claim is that, for two correlated balanced two-community stochastic block models on n vertices with p=a log n/n and q=b log n/n, the unknown vertex permutation π* can be recovered by a polynomial-time algorithm whenever the squared edge correlation s² exceeds α≈0.338. The algorithm first runs an almost-exact community-recovery routine on each graph to estimate the latent labels, centers each adjacency matrix by subtracting the estimated p/q edge probabilities, and computes a signature of signed subgraph counts of chandeliers rooted at each vertex. The weighted inner product of two signatures has expectation (1+o(1))μ for true correspondences and o(μ) for false ones, with variance small enough to threshold correctly on (1−o(1))n vertices; a seeded common-neighbor step then upgrades the partial matching to the exact permutation whenever s²(a+b)/2>1, which is the information-theoretic threshold. This positively resolves the open problem of efficient exact graph matching in this model and yields, as a black-box application, efficient exact community recovery from two correlated graphs in regimes where a single graph cannot achieve it.

Load-bearing premise

The load-bearing premise is that the community-recovery estimate misclassifies different vertices almost independently, with each misclassification probability inverse-polynomial in n; if the misclassification events are correlated more strongly than the paper's Lemma 3.6 allows, the variance of the similarity score is no longer negligible against its squared mean and the thresholding proof collapses.

Editorial extensions

If this is right

  • For any two distinct positive community densities a and b, almost-exact graph matching is polynomial-time once s²≥α+ε for any ε>0.
  • Exact graph matching is achieved efficiently at the same threshold where information-theoretic exact matching first becomes possible, namely s²(a+b)/2>1.
  • Exact community recovery from two correlated graphs becomes efficiently possible in regimes where exact recovery from a single graph is information-theoretically impossible.
  • The same matching algorithm yields efficient exact community recovery from K correlated graphs above the corresponding threshold.
  • The regime s²<α is left open and is conjectured to be computationally hard, giving a conjectured information-computation gap.

Reading between the lines

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

  • Because the chandelier size N is Θ(log n/ε), the runtime exponent in the polynomial bound grows as ε shrinks; near the threshold the algorithm is polynomial but practically slow, a cost the paper does not quantify.
  • The entire score-separation analysis rests on the approximate independence of community-recovery errors, so the natural way to attack the result is to test the joint distribution of misclassification events; a correlation structure stronger than inverse-polynomial independence would break the variance computation before any other step.
  • The same signature-counting scheme should extend to degree-corrected or k-community block models as long as a community-recovery subroutine provides inverse-polynomial, approximately independent error rates, although the paper only conjectures the k-community extension.
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

1 major / 4 minor

Summary. The paper studies graph matching on correlated stochastic block models (CSBMs) with two balanced communities in the logarithmic average degree regime. Its main result, Theorem 1.1, gives a polynomial-time algorithm that, when s^2 >= alpha + eps, correctly matches all but a vanishing fraction of vertices, and when additionally s^2(a+b)/2 > 1, outputs the exact latent permutation. The algorithm combines community recovery (Mossel–Neeman–Sly), signed chandelier subgraph counts (Mao–Wu–Xu–Yu), and a seeded matching step. The paper also derives an application to exact community recovery from multiple correlated graphs (Theorem 1.2). The proofs are extensive, with explicit moment, variance, and probability bounds for two parameter regimes separated by whether single-graph exact community recovery is possible.

Significance. If the technical claims are correct, this is a substantial contribution: it provides the first efficient graph matching algorithm for logarithmic-degree correlated SBMs, reaching the information-theoretic threshold for exact matching in the regime s^2 > alpha, and it makes progress on an open problem of Rácz and Sridhar. The proof is unusually detailed and self-contained, including explicit chandelier parameter choices, moment calculations for approximately centered adjacency matrices, and a seeded matching analysis. The paper honestly discusses the conjectured information-computation gap at s^2 = alpha and the limitations of the approach.

major comments (1)
  1. [Abstract and Section 1.2] The abstract states that the paper gives an efficient algorithm for exact graph matching 'whenever this is information-theoretically possible' and that it positively resolves the open problem of Rácz and Sridhar. This overstates the proven result. Theorem 1.1(b) requires both s^2 >= alpha + eps and s^2(a+b)/2 > 1, whereas the information-theoretic threshold from [57] is s^2(a+b)/2 > 1 alone. For example, with (a,b,s) = (100,1,0.2), we have s^2 = 0.04 < alpha = 0.338 while s^2(a+b)/2 = 2.02 > 1, so exact matching is information-theoretically possible but Theorem 1.1 provides no algorithm. Section 1.5 itself conjectures hardness in the regime s^2 < alpha. The abstract and the opening paragraph of Section 1.2 should be corrected to state the s^2 > alpha condition and to qualify the claimed resolution of the open problem as conditional on that condition; the same caveat applies to the 'Tightness' paragraph on page 5, which should not imply that exact matching holds for all s^2 > alpha.
minor comments (4)
  1. [Lemma 6.1 and Theorem 2.7] The condition in Lemma 6.1 is written as 'a+b/2 >= 1 + eps' and the proof says 'a+b/2 >= 1 + eps'. This should be '(a+b)/2 >= 1 + eps', consistent with the average degree (p+q)/2 = ((a+b)/2) log n / n used in the proof.
  2. [Section 10, proof of Proposition 4.4, case (b)] The algebra after inequality (10.1) is hard to follow: the bound contains an n^N factor that is later cancelled by the n^{-N} from (rho sigma_eff^2)^N, but the cancellation is not shown. Please spell out the steps so that the final o(mu/n^2) conclusion is transparent.
  3. [Lemma 2.3] The asymptotic formula for alpha_D is garbled: it should read alpha_D = alpha + C alpha^D + o(alpha^D) rather than 'alpha_D = alpha + Calpha D + o(alphaD)'. The condition for K alpha^D -> 0 follows from D >= C' log K with C' > 1/log(1/alpha), but the current notation obscures this.
  4. [Section 4.3, proof of Theorem 2.5] The line 's^2 >= alpha + eps iff rho^2 >= alpha + eps_prime' is an asymptotic equivalence (since rho = (1 + Theta(log n/n)) s), not an exact equivalence for fixed n. It would be clearer to state that the former condition implies the latter for sufficiently large n.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the matching algorithm is proved from explicit moment bounds and prior external results; the abstract's overclaim is a correctness/presentation issue, not a circularity.

full rationale

The derivation chain is self-contained rather than circular. The algorithm's threshold uses the theoretical quantity μ = |T| n^N ρ^N σ_eff^{2N}, which is computed from the model parameters and tree-counting constants, not fitted to the data whose matching is being predicted; the separation of true-pair and fake-pair score distributions is then proved via Propositions 4.1-4.6, whose moment calculations are derived from the CSBM distribution and standard binomial/tail bounds. The community-recovery input from Mossel-Neeman-Sly [47] and the inverse-polynomial error/approximate-independence property in Lemma 3.6 are either prior external results or proved in the paper; they are used as ingredients, not as the target conclusion. The information-theoretic thresholds quoted from Racz-Sridhar [57] and Gaudio-Racz-Sridhar [25] enter as external benchmarks or as sufficient conditions in Theorem 1.1(b) and Theorem 1.2, but no step sets the output matching equal to an input assumption. Self-citations appear, but they are not load-bearing reductions: the paper's own proofs of the chandelier moment bounds and seeded matching do not invoke the claimed theorem. The abstract's phrase 'whenever this is information-theoretically possible' overstates Theorem 1.1's additional s^2 > α condition, and the advertised resolution of the open problem is conditional; that is a correctness/overclaim issue, not a circularity, and does not affect the score under the circularity rubric.

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

No new physical or conceptual entities are introduced. The chandelier variant with a maximum degree constraint is a combinatorial object inherited and modified from [41], not an entity requiring independent evidence.

free parameters (2)
  • Chandelier parameters (L, M, K, R, D) and threshold c = L=C1/epsilon, K=C2 log n, M=C3K/log(ns(p∧q)), R=exp(C4K), D=C5 log n/(log log n)^2, c in (0,1)
    Hand-chosen in Theorem 2.5 to satisfy moment conditions (4.1)-(4.4). They are analytic design choices, not fitted to data, but the theorem depends on their existence.
  • Community recovery partition size m in Algorithm 3 = m chosen so (log(epsilon m (2 max(a,b) log^2 n)^{-1}) - 1) epsilon / 2 > 1
    From [47]; controls the per-vertex error probability and supports the approximate-independence Lemma 3.6 used throughout Regime II.
assumptions (6)
  • standard math Otter's tree enumeration and asymptotic (alpha+o(1))^{-K}; Goh-Schmutz bound on alpha_D; Olsson-Wagner CLT for automorphism counts of random rooted trees
    Used in Lemmas 2.3 and 2.4 to keep the chandelier family exponential with rate alpha, which sets the s^2 > alpha threshold.
  • standard math Chernoff and multiplicative Chernoff bounds, and stochastic dominance for SBM edge indicators
    Repeated tail bounds in Sections 3 and 6; standard.
  • domain assumption The Mossel-Neeman-Sly spectral community recovery algorithm [47] achieves almost exact recovery with per-vertex error n^{-sD+(a,b)} and approximately independent error events
    Invoked in Section 1.2 and Lemmas 3.5-3.6; the Regime II variance analysis would fail without this assumption.
  • domain assumption The information-theoretic threshold for exact graph matching in correlated SBMs is s^2(a+b)/2 = 1 [57]
    Used to frame Theorem 1.1(b) as resolving the open problem and to state tightness.
  • domain assumption Generative model CSBM(n, a log n/n, b log n/n, s) with iid balanced labels and edge subsampling
    Defines the scope; results do not extend to arbitrary inhomogeneous graphs.
  • standard math Color-coding: for random (N+1)-colorings, colorful occurrences have probability r = (N+1)!/(N+1)^(N+1), giving unbiased estimators
    Section 5, Algorithm 4; converts exponential-time counting to polynomial time.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Efficient Graph Matching for Correlated Stochastic Block Models." pith.science (2026). https://pith.science/paper/DF7V67AM

@misc{pith2026241202661,
  author       = {Pith},
  title        = {Pith review of: Efficient Graph Matching for Correlated Stochastic Block Models},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DF7V67AM}},
  note         = {Machine review of arXiv:2412.02661}
}
abstract

We study learning problems on correlated stochastic block models with two balanced communities. Our main result gives the first efficient algorithm for graph matching in this setting. In the most interesting regime where the average degree is logarithmic in the number of vertices, this algorithm correctly matches all but a vanishing fraction of vertices with high probability, whenever the edge correlation parameter $s$ satisfies $s^2 > \alpha \approx 0.338$, where $\alpha$ is Otter's tree-counting constant. Moreover, we extend this to an efficient algorithm for exact graph matching whenever this is information-theoretically possible, positively resolving an open problem of R\'acz and Sridhar (NeurIPS 2021). Our algorithm generalizes the recent breakthrough work of Mao, Wu, Xu, and Yu (STOC 2023), which is based on centered subgraph counts of a large family of trees termed chandeliers. A major technical challenge that we overcome is dealing with the additional estimation errors that are necessarily present due to the fact that, in relevant parameter regimes, the latent community partition cannot be exactly recovered from a single graph. As an application of our results, we give an efficient algorithm for exact community recovery using multiple correlated graphs in parameter regimes where it is information-theoretically impossible to do so using just a single graph.

Figures

Figures reproduced from arXiv: 2412.02661 by the authors.

Figure 1
Figure 1. Schematic illustrating two-community correlated SBMs; see the text for details. (Figure [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Phase diagram for graph matching on (G1, G2) ∼ CSBM(n, a log n n , b log n n , s). The red diagonal line depicts a = b, which is an Erd˝os–R´enyi graph. Black regions: exact graph matching is possible and can be done efficiently for each community separately by applying the graph matching algorithm for correlated Erd˝os–R´enyi graphs; Green regions: exact graph matching is possible and can be done efficiently; Light… view at source ↗
Figure 3
Figure 3. Phase diagram for exact community recovery with fixed [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: A chandelier. as D → ∞, for some constant C > 0, αD = α + CαD + o(α D). Immediately we can see that |J (K,∞,D)| |J (K,∞,∞)| = (1 + O(α D))−K = 1 − o(1) if KαD → 0. Let C ′ > 1 log(1/α) , choosing D ≥ C ′ log K satisfies KαD → 0. Lemma 2.4. Let K be the number of vertic…
Figure 5
Figure 5. Figure 5: Decomposition of a decorated tree into three sequences of trees. Edges that are 2, 3, [PITH_FULL_IMAGE:figures/full_fig_p022_5.png]
Figure 6
Figure 6. Figure 6: Left: The simplest example of two rooted trees T1 and T2 satisfying p aut(T1)aut(T2) > aut(T1 ∪ T2); here T1 is induced by the blue and green edges, T2 is induced by the blue and red edges, and both trees are rooted at the vertex at the top. Middle: Example that shows …
Figure 7
Figure 7. Figure 7: Illustration on the impact of incorrect community labels on adjacency matrix centraliza [PITH_FULL_IMAGE:figures/full_fig_p029_7.png]
Figure 8
Figure 8. Figure 8: Left: One possible labeling such that all edges are centralized incorrectly, with the colored vertices indicating those that are labeled incorrectly and the black vertices indicating those that are labeled correctly. Right: Another possible labeling such that all edges…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

71 extracted references · 64 canonical work pages

  1. [57]

    R´ acz and Anirudh Sridhar

    Mikl´ os Z. R´ acz and Anirudh 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

    work page 2021

  2. [1]

    Community Detection and Stochastic Block Models: Recent Developments

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

    work page 2018

  3. [2]

    Bandeira, and Georgina Hall

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

    work page 2016

  4. [3]

    Entrywise eigenvector analysis of random matrices with low expected rank.The Annals of Statistics, 48(3):1452–1474, 2020

    Emmanuel Abbe, Jianqing Fan, Kaizheng Wang, and Yiqiao Zhong. Entrywise eigenvector analysis of random matrices with low expected rank.The Annals of Statistics, 48(3):1452–1474, 2020

    work page 2020

  5. [4]

    Community detection in general stochastic block mod- els: Fundamental limits and efficient algorithms for recovery

    Emmanuel Abbe and Colin Sandon. Community detection in general stochastic block mod- els: Fundamental 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

  6. [5]

    (Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs

    Boaz Barak, Chi-Ning Chou, Zhixian Lei, Tselil Schramm, and Yueqi 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. [6]

    Constant Time Generation of Rooted Trees

    Terry Beyer and Sandra Mitchell Hedetniemi. Constant Time Generation of Rooted Trees. SIAM Journal on Computing , 9(4):706–712, 1980

    work page 1980

  8. [7]

    Vec-sbm: Optimal community detection with vec- torial edges covariates

    Guillaume Braun and Masashi Sugiyama. Vec-sbm: Optimal community detection with vec- torial edges covariates. In Proceedings of The 27th International Conference on Artificial In- telligence and Statistics (AISTATS), volume 238 of Proceedings of Machine Learning Research (PMLR), pages 532–540, 2024

    work page 2024

Show all 71 references
  1. [8]

    De-anonymization of heterogeneous random graphs in quasilinear time

    Karl Bringmann, Tobias Friedrich, and Anton 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

    2014

  2. [9]

    Testing for high-dimensional geometry in random graphs

    S´ ebastien Bubeck, Jian Ding, Ronen Eldan, and Mikl´ os Z R´ acz. Testing for high-dimensional geometry in random graphs. Random Structures & Algorithms , 49(3):503–532, 2016. 68

    2016

  3. [10]

    A computational transition for detecting correlated stochastic block models by low-degree polynomials

    Guanyi Chen, Jian Ding, Shuyang Gong, and Zhangsong 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

  4. [11]

    Social Network De- Anonymization Under Scale-Free User Relations

    Carla-Fabiana Chiasserini, Michele Garetto, and Emilio Leonardi. Social Network De- Anonymization Under Scale-Free User Relations. IEEE/ACM Transactions on Networking , 24(6):3756–3769, 2016

    2016

  5. [12]

    Colbourn and Kellogg S

    Charles J. Colbourn and Kellogg S. Booth. Linear Time Automorphism Algorithms for Trees, Interval Graphs, and Planar Graphs. SIAM Journal on Computing , 10(1):203–225, 1981

    1981

  6. [13]

    Thirty years of graph matching in pattern recognition

    Donatello Conte, Pasquale Foggia, Carlo Sansone, and Mario Vento. Thirty years of graph matching in pattern recognition. International Journal of Pattern Recognition and Artificial Intelligence, 18(03):265–298, 2004

    2004

  7. [14]

    Improved Achievability and Converse Bounds for Erd˝ os- R´ enyi Graph Matching

    Daniel Cullina and Negar Kiyavash. Improved Achievability and Converse Bounds for Erd˝ os- R´ enyi Graph Matching. InACM SIGMETRICS, volume 44, pages 63–72, 2016

    2016

  8. [15]

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

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

    2018 arXiv

  9. [16]

    Vincent Poor

    Daniel Cullina, Negar Kiyavash, Prateek Mittal, and H. Vincent Poor. Partial Recovery of Erd˝ os-R´ enyi Graph Alignment viak-Core Alignment. In ACM SIGMETRICS Performance Evaluation Review, volume 48, pages 99–100. ACM, 2020

    2020

  10. [17]

    Matching recovery threshold for correlated random graphs

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

    2023

  11. [18]

    Low-Degree Hardness of Detection for Correlated Erd˝ os-R´ enyi Graphs

    Jian Ding, Hang Du, and Zhangsong Li. Low-Degree Hardness of Detection for Correlated Erd˝ os-R´ enyi Graphs. Preprint available athttps://arxiv.org/abs/2311.15931, 2023

    2023

  12. [19]

    Efficiently matching random inhomogeneous graphs via degree profiles

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

    2023 arXiv

  13. [20]

    A polynomial-time iterative algorithm for random graph match- ing with non-vanishing correlation

    Jian Ding and Zhangsong Li. A polynomial-time iterative algorithm for random graph match- ing with non-vanishing correlation. Preprint available at https://arxiv.org/abs/2306. 00266, 2023

    2023

  14. [21]

    Efficient random graph matching via degree profiles

    Jian Ding, Zongming Ma, Yihong Wu, and Jiaming Xu. Efficient random graph matching via degree profiles. Probability Theory and Related Fields , 179(1):29–115, 2021

    2021

  15. [22]

    Spectral graph matching and regularized quadratic relaxations: Algorithm and theory

    Zhou Fan, Cheng Mao, Yihong Wu, and Jiaming Xu. Spectral graph matching and regularized quadratic relaxations: Algorithm and theory. In Proceedings of the 37th International Confer- ence on Machine Learning (ICML) , volume 119 of Proceedings of Machine Learning Research (PMLR)...

    2020

  16. [23]

    From tree matching to sparse graph alignment

    Luca Ganassali and Laurent 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

  17. [24]

    Impossibility of Partial Recovery in the Graph Alignment Problem

    Luca Ganassali, Laurent Massouli´ e, and Marc 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. 69

    2021

  18. [25]

    R´ acz, and Anirudh Sridhar

    Julia Gaudio, Mikl´ os Z. R´ acz, and Anirudh Sridhar. Exact community recovery in corre- lated stochastic block models. In Proceedings of Thirty Fifth Conference on Learning Theory (COLT), volume 178 of Proceedings of Machine Learning Research, pages 2183–2241. PMLR, 02–05 Jul 2022

    2022

  19. [26]

    Goh and Eric Schmutz

    William M.Y. Goh and Eric Schmutz. Unlabeled Trees: Distribution of the Maximum Degree. Random Structures & Algorithms , 5(3):411–440, 1994

    1994

  20. [27]

    Partial recovery in the graph alignment problem

    Georgina Hall and Laurent Massouli´ e. Partial recovery in the graph alignment problem. Op- erations Research, 71(1):259–272, 2023

    2023

  21. [28]

    Consistent estimation of dynamic and multi- layer block models

    Qiuyi Han, Kevin Xu, and Edoardo Airoldi. Consistent estimation of dynamic and multi- layer block models. In International Conference on Machine Learning (ICML) , volume 37 of Proceedings of Machine Learning Research (PMLR), pages 1511–1520, 2015

    2015

  22. [29]

    Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt

    Paul W. Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social Networks, 5(2):109–137, 1983

    1983

  23. [30]

    Network-adjusted covariates for community detection

    Yaofang Hu and Wanjie Wang. Network-adjusted covariates for community detection. Biometrika, page asae011, 2024

    2024

  24. [31]

    Random Graphs

    Svante Janson, Tomasz Luczak, and Andrzej Rucinski. Random Graphs. John Wiley & Sons, 2000

    2000

  25. [32]

    An efficient reconciliation algorithm for social networks

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

    2014

  26. [33]

    Consistent community detection in multi-layer net- work data

    Jing Lei, Kehui Chen, and Brian Lynch. Consistent community detection in multi-layer net- work data. Biometrika, 107(1):61–73, 2020

    2020

  27. [34]

    Information recovery in shuffled graphs via graph matching

    Vince Lyzinski. Information recovery in shuffled graphs via graph matching. IEEE Transac- tions on Information Theory , 64(5):3254–3273, 2018

    2018

  28. [35]

    Sussman, Donniell E

    Vince Lyzinski, Daniel L. Sussman, Donniell E. Fishkind, Henry Pao, Li Chen, Joshua T. Vogelstein, Youngser Park, and Carey E. Priebe. Spectral clustering for divide-and-conquer graph matching. Parallel Computing , 47:70–87, 2015

    2015

  29. [36]

    Image matching from handcrafted to deep features: A survey

    Jiayi Ma, Xingyu Jiang, Aoxiang Fan, Junjun Jiang, and Junchi Yan. Image matching from handcrafted to deep features: A survey. International Journal of Computer Vision , 129:23–79, 2021

    2021

  30. [37]

    Community detection with contextual multilayer networks

    Zongming Ma and Sagnik Nandy. Community detection with contextual multilayer networks. IEEE Transactions on Information Theory , 69(5):3203–3239, 2023

    2023

  31. [38]

    Maximum quadratic assignment problem: Reduction from maximum label cover and lp-based approximation al- gorithm

    Konstantin Makarychev, Rajsekar Manokaran, and Maxim Sviridenko. Maximum quadratic assignment problem: Reduction from maximum label cover and lp-based approximation al- gorithm. In International Colloquium on Automata, Languages, and Programming (ICALP) , pages 594–604. Springer, 2010

    2010

  32. [39]

    Random Graph Matching with Im- proved Noise Robustness

    Cheng Mao, Mark Rudelson, and Konstantin Tikhomirov. Random Graph Matching with Im- proved 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. 70

    2021

  33. [40]

    Exact matching of random graphs with constant correlation

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

    2023

  34. [41]

    Cheng Mao, Yihong Wu, Jiaming Xu, and Sophie 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

  35. [42]

    Cheng Mao, Yihong Wu, Jiaming Xu, and Sophie H. Yu. Testing network correlation efficiently via counting trees. The Annals of Statistics , to appear, 2024+

    2024

  36. [43]

    Community detection thresholds and the weak Ramanujan property

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

    2014

  37. [44]

    Mutual information in community detection with co- variate information and correlated networks

    Vaishakhi Mayya and Galen Reeves. Mutual information in community detection with co- variate information and correlated networks. In 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton) , pages 602–607. IEEE, 2019

    2019

  38. [45]

    Probability and Computing: Randomized Algorithms and Probabilistic Analysis

    Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005

    2005

  39. [46]

    Stochastic block models and reconstruction

    Elchanan Mossel, Joe Neeman, and Allan Sly. Stochastic block models and reconstruction. arXiv preprint arXiv:1202.1499 , 2012

    2012 arXiv

  40. [47]

    Consistency thresholds for the planted bisection model

    Elchanan Mossel, Joe Neeman, and Allan Sly. Consistency thresholds for the planted bisection model. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing , pages 69–75, 2015

    2015

  41. [48]

    A proof of the block model threshold conjecture

    Elchanan Mossel, Joe Neeman, and Allan Sly. A proof of the block model threshold conjecture. Combinatorica, 38(3):665–708, 2018

    2018

  42. [49]

    Seeded graph matching via large neighborhood statistics

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

    2020

  43. [50]

    Faster algorithms for the alignment of sparse cor- related Erd˝ os–R´ enyi random graphs

    Andrea Muratori and Guilhem Semerjian. Faster algorithms for the alignment of sparse cor- related Erd˝ os–R´ enyi random graphs. Preprint available athttps://arxiv.org/abs/2405. 08421, 2024

    2024

  44. [51]

    De-anonymizing social networks

    Arvind Narayanan and Vitaly Shmatikov. De-anonymizing social networks. In Proceedings of the 30th IEEE Symposium on Security and Privacy , pages 173–187. IEEE Computer Society, 2009

    2009

  45. [52]

    Hardness of robust graph iso- morphism, lasserre gaps, and asymmetry of random graphs

    Ryan O’Donnell, John Wright, Chenggang Wu, and Yuan Zhou. Hardness of robust graph iso- morphism, lasserre gaps, and asymmetry of random graphs. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1659–1677. SIAM, 2014

    2014

  46. [53]

    Automorphisms of Random Trees

    Christoffer Olsson and Stephan Wagner. Automorphisms of Random Trees. In 33rd Interna- tional Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022) , volume 225 of Leibniz International Proceedings in Informatics (LIPIcs),...

    2022

  47. [54]

    Optimal de-anonymization in random graphs with community structure

    Efe Onaran, Siddharth Garg, and Elza Erkip. Optimal de-anonymization in random graphs with community structure. In 2016 50th Asilomar Conference on Signals, Systems and Com- puters, pages 709–713. IEEE, 2016

    2016

  48. [55]

    The Number of Trees

    Richard Otter. The Number of Trees. Annals of Mathematics , 49(3):583–599, 1948

    1948

  49. [56]

    On the privacy of anonymized networks

    Pedram Pedarsani and Matthias 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

  50. [58]

    R´ acz and Anirudh Sridhar

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

    2022

  51. [59]

    R´ acz and Anirudh Sridhar

    Mikl´ os Z. R´ acz and Anirudh 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

  52. [60]

    R´ acz and Jifan Zhang

    Mikl´ os Z. R´ acz and Jifan Zhang. Harnessing Multiple Correlated Networks for Exact Commu- nity Recovery. In Advances in Neural Information Processing Systems (NeurIPS) , volume 38, 2024

    2024

  53. [61]

    Global alignment of multiple protein interac- tion networks with application to functional orthology detection

    Rohit Singh, Jinbo Xu, and Bonnie Berger. Global alignment of multiple protein interac- tion networks with application to functional orthology detection. Proceedings of the National Academy of Sciences, 105(35):12763–12768, 2008

    2008

  54. [62]

    Massucci, Roger Guimer` a, and Marta Sales-Pardo

    Toni Vall` es-Catal` a, Francesco A. Massucci, Roger Guimer` a, and Marta Sales-Pardo. Multilayer Stochastic Block Models Reveal the Multilayer Structure of Complex Networks. Physical Review X, 6(1):011036, 2016

    2016

  55. [63]

    Random Graph Matching in Ge- ometric Models: the Case of Complete Graphs

    Haoyu Wang, Yihong Wu, Jiaming Xu, and Israel Yolou. Random Graph Matching in Ge- ometric 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

  56. [64]

    Efficient Algorithms for Attributed Graph Alignment with Vanishing Edge Correlation

    Ziao Wang, Weina Wang, and Lele Wang. Efficient Algorithms for Attributed Graph Alignment with Vanishing Edge Correlation. In Proceedings of the 37th Conference on Learning Theory (COLT), volume 247 of Proceedings of Machine Learning Research (PMLR), pages 4889–4890, 2024

    2024

  57. [65]

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

    2022

  58. [66]

    Graph matching in correlated stochastic block models for improved graph clustering

    Joonhyuk Yang and Hye Won Chung. Graph matching in correlated stochastic block models for improved graph clustering. In Proceedings of the 2023 59th Annual Allerton Conference on Communication, Control, and Computing (Allerton) , pages 1–8. IEEE, 2023

    2023

  59. [67]

    Efficient Algorithms for Exact Graph Matching on Correlated Stochastic Block Models with Constant Correlation

    Joonhyuk Yang, Dongpil Shin, and Hye Won Chung. Efficient Algorithms for Exact Graph Matching on Correlated Stochastic Block Models with Constant Correlation. In Proceedings 72 of the 40th International Conference on Machine Learning (ICML) , volume 202 of Proceedings of Machi...

    2023

  60. [68]

    Fundamental limits of community detection from multi-view data: multi-layer, dynamic and partially labeled block models

    Xiaodong Yang, Buyu Lin, and Subhabrata Sen. Fundamental limits of community detection from multi-view data: multi-layer, dynamic and partially labeled block models. Preprint available at https://arxiv.org/abs/2401.08167, 2024

    2024 arXiv

  61. [69]

    On the Performance of Percolation Graph Matching

    Lyudmila Yartseva and Matthias Grossglauser. On the Performance of Percolation Graph Matching. In Proceedings of the First ACM Conference on Online Social Networks (COSN) , pages 119–130, 2013

    2013

  62. [70]

    The Power of D-hops in Matching Power-Law Graphs

    Liren Yu, Jiaming Xu, and Xiaojun 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

    2021

  63. [71]

    Consistent community detection in inter- layer dependent multi-layer networks

    Jingnan Zhang, Junhui Wang, and Xueqin Wang. Consistent community detection in inter- layer dependent multi-layer networks. Journal of the American Statistical Association , pages 1–11, 2024. 73

    2024

Pith tools

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