Pith. sign in

REVIEW 3 major objections 5 minor 43 references

Exact Matching in Correlated Networks with Node Attributes for Improved Community Recovery

T0 review · 3 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

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

Pith's one-line read This paper establishes that two correlated networks with shared node attributes can be exactly matched and merged, making exact community recovery feasible in regimes where a single network provably cannot.

desk verdict Neat extension of correlated-graph matching to attributed SBMs with a clean additive threshold, but the central achievability proof has a load-bearing union-bound gap that needs fixing. read the letter →

arxiv 2501.02851 v2 pith:BFLIWOUH submitted 2025-01-06 cs.SI cs.ITmath.ITstat.ML

Joonhyuk Yang , Hye Won Chung This is my paper · ORCID
classification cs.SIcs.ITmath.ITstat.ML MSC 05C8062H3094A15
keywords correlatedcontextualstochasticblockmodelexactcommunityrecoverygraphmatchingnodeattributesk-coreGaussianmixturedatabasealignmentinformation-theoreticthresholds
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 asks whether a shared set of users appearing in two correlated social networks, with correlated friendships and correlated profile attributes, can be exactly matched even when community memberships are unknown, and whether that alignment then improves community detection. It introduces two models: a correlated Gaussian Mixture Model for attributes alone and a correlated Contextual Stochastic Block Model for edges plus attributes. The central claim is that exact node matching is feasible when the edge correlation signal and the attribute correlation signal add up to a single threshold, and that after exact matching the merged network has a higher effective signal-to-noise ratio. In parameter regimes where exact community recovery is provably impossible from one graph alone, the paper shows that two correlated graphs can succeed.

What carries the argument

The load-bearing object is the two-step matching procedure. First, $k$-core matching on the intersection graph $G_1 \wedge_{\pi_*} G_2$ uses only edge correlations to align all but about $n^{1 - ns^2(p+q)/(2\log n)}$ nodes, while certifying which nodes are matched. Second, the minimum-distance estimator $\hat\pi = \arg\min_\pi \sum_i \lVert x_i - y_{\pi(i)}\rVert^2$ aligns the residual nodes using correlated attributes, a step justified by treating the residual as a correlated Gaussian mixture. Once matching succeeds, the paper merges the pair into one annotated graph: the union of edges has edge probability $p(1-(1-s)^2)$ within communities, and the averaged attributes have covariance $\frac{1+\rho}{2}I_d$, which raises the effective signal-to-noise ratio used in the community-recovery thresholds.

What would settle it

Fix a regime allowed by Theorem 5, say $n=10^5$, $d=n^{0.6}$, $\rho=0.5$, and $R=O(\log n)$, with edge parameters chosen so that $ns^2(p+q)/2$ contributes a small but positive share of the required $\log n$; run the two-step k-core-plus-distance estimator on many CCSBM samples. If exact matching fails with probability bounded away from zero, the achievability condition (23) is not sufficient as stated, while repeated success would support the paper's threshold.

Watch

Extended reading notes

Core claim

The paper claims that in the correlated Contextual Stochastic Block Model, exact matching between the two graphs is achievable with high probability whenever $ns^2 \frac{p+q}{2} + \frac{d}{4} \log\frac{1}{1-\rho^2} \ge (1+\epsilon)\log n$, provided the graph is sufficiently sparse and either the attribute norm or dimension is not too small. It then shows that once matching is achieved, exact community recovery reduces to a single-network problem on the merged graph, with threshold $\frac{(1-(1-s)^2)(\sqrt{a}-\sqrt{b})^2 + c'}{2} > 1$. The same logic applied to attributes alone gives a matching threshold $\frac{d}{4} \log\frac{1}{1-\rho^2} \ge (1+\epsilon)\log n$. The paper also proves converse thresholds for matching and community recovery, leaving a gap that it attributes to not using community labels during matching.

Load-bearing premise

The proof of the two-step matching theorem assumes that the set of nodes left unmatched by k-core matching is itself a correlated Gaussian mixture, statistically independent of the edge realization that selected it; if that set is label-biased or otherwise dependent on the graphs, the additive matching condition (23) could fail.

Editorial extensions

If this is right

  • If the matching condition holds, the exact-community-recovery threshold for two correlated attributed graphs becomes $\frac{(1-(1-s)^2)(\sqrt{a}-\sqrt{b})^2 + c'}{2} > 1$, compared with $\frac{s(\sqrt{a}-\sqrt{b})^2 + c}{2} > 1$ for one graph.
  • Exact community recovery becomes possible in regimes where a single graph is information-theoretically unable to recover communities, provided exact matching is feasible.
  • The matching threshold combines edge and attribute signals additively, so weak correlation in one modality can be compensated by strong correlation in the other.
  • For attributes alone, the matching threshold $\frac{d}{4}\log\frac{1}{1-\rho^2} \ge (1+\epsilon)\log n$ matches the known database-alignment limit, showing that hidden community labels need not hurt exact alignment.
  • The same two-step procedure recovers the edge-only and attribute-only results as limiting cases, with $d=0$ giving correlated SBM matching and $p=q=0$ giving correlated GMM matching.

Reading between the lines

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

  • A directly testable corollary is that in the unresolved low-dimensional gap, where $d=O(\log n)$ and $\lVert\mu\rVert$ is below $2\log n$, exact matching may still occur at the thin threshold $\frac{d}{4}\log\frac{1}{1-\rho^2} \approx \log n$; the paper itself leaves this as a hypothesis, and Monte Carlo experiments there would show whether the extra conditions are an artifact of the proof or a re
  • The sequential k-core-then-attributes design suggests that any polynomial-time matching algorithm that both matches nodes and certifies which nodes it is confident about could replace k-core in the first step, since the bottleneck is certification rather than accuracy alone.
  • If exact matching is replaced by partial matching, the union-graph and averaged-attribute argument may still yield exact community recovery with a weakened SNR gain, paralleling what partial matching achieves in the correlated SBM setting without node attributes.
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 / 5 minor

Summary. The paper introduces two new models, correlated Gaussian Mixture Models (CGMMs) and correlated Contextual Stochastic Block Models (CCSBMs), in which two networks share both correlated edges and correlated Gaussian node attributes with a hidden community structure. For CGMMs it analyzes a minimum-distance estimator for exact node matching (Theorem 1) and gives a matching converse (Theorem 2), followed by exact community recovery results (Theorems 3 and 4). For CCSBMs it proposes a two-step algorithm that first applies k-core matching on edge information and then matches the residual nodes by attributes, claiming the sharp matching threshold ns²(p+q)/2 + d/4 log(1/(1-ρ²)) ≥ (1+ε) log n (Theorem 5), with a converse (Theorem 6) and exact community recovery conditions (Theorems 7 and 8). The central message is that after exact alignment, merging edges and averaging attributes improves the effective SNR, making exact community recovery possible in regimes where a single graph is information-theoretically insufficient.

Significance. If the technical gaps are repaired, this is a valuable contribution. It is, to my knowledge, the first model to jointly treat edge correlation and attribute correlation with latent community structure, and the claimed additive matching threshold naturally interpolates between the known edge-only and attribute-only baselines (correlated SBMs and correlated Gaussian databases). The paper also provides converses for matching and recovery and gives explicit two-step algorithmic guarantees, building on the k-core framework of Gaudio–Racz–Sridhar and the database-alignment results of Dai–Cullina–Kiyavash. The treatment of community recovery after matching, including the merged-graph SNR expressions, is a meaningful extension of the correlated-SBM results of Racz–Sridhar and subsequent work. However, the main matching proof in Theorem 1 contains a load-bearing union-bound gap, and the reduction from k-core residual sets to a fresh CGMM is not justified as written. These issues are addressable but must be fixed before the central claims can be accepted.

major comments (3)
  1. [Section VI, Eqs. (44) and (52)] The step from Lemma 1's bound P(F_t) ≤ exp(-d/2 S(α,t)) + P(A^c) to the chain in (44) and (52), where the P(A^c) term is absorbed into an exp(o(1)) factor before multiplying by the n^t cycle count, is not valid. Under condition (7), P(A1^c) ≤ 2n exp(-||µ||²/2); even when ||µ||² = 2 log n + ω(1) with ω(1) = 2 log log n, the t=2 contribution alone is at least n² P(A1^c), which diverges. The same issue occurs for A2 under condition (8). Consequently, the displayed bound E|M| = o(1) is not established. Since Theorem 5 invokes Theorem 1 on the residual unmatched set, the central matching threshold (23) is not proven as written. This is a genuine, load-bearing gap, though it may be fixable by controlling the bad-event contribution separately or by strengthening the conditions on ||µ|| and d.
  2. [Section IV-B and Section IX-A (around Eqs. (66)-(67))] The assertion that the residual unmatched set F after k-core matching 'forms a correlated Gaussian Mixture Model' is not justified. The set F is a function of the edge realization, so conditioning on F can bias the community composition of F; the global balance event B (Eq. (74)) does not by itself imply that the labels in F are i.i.d. uniform or that the attribute noise is independent of the selection event. Theorem 1 is stated for a fresh CGMM with n i.i.d. labels, and the paper does not prove the conditional distribution of the attributes on F matches those assumptions. This is load-bearing for the application of Theorem 1 in (67). The authors should either provide a conditional-distribution argument, or prove explicitly that the proof of Theorem 1 is label-agnostic and applies to a random set F of random size with arbitrary labels.
  3. [Section IX-B, proof of Theorem 12] The sentence 'If ns²(p+q) = o(log n), the right-hand side converges to 0, making the result trivial' is inaccurate: the right-hand side n^{1 - ns²(p+q)/(2 log n)} is n^{1-o(1)}, which is o(n) but not 0. More importantly, the proof of (80) does not appear to hold uniformly in the regime where nps² is very small relative to log n, since k is then dominated by log n/(log log n)² while the right-hand side of (80) is of order n e^{o(1)}. Please clarify the range of parameters for which the k-core bound (63) is actually derived and whether the subsequent use in Theorem 5 requires an additional case split.
minor comments (5)
  1. [Section X, definitions of χ±] The definition of χ⁻(π) sums over E⁺(σ₂) instead of E⁻(σ₂); this appears to be a typo and should be corrected, since χ⁻ is meant to count inter-community pairs.
  2. [Table II and Section I-C] The constants c and c′ are used in Table II before they are defined in the text; please define them at first use or add a pointer to Eq. (27).
  3. [Eq. (9)] In the derivation of the MAP estimator, the notation f(σ, σπ) is introduced only after it appears in the displayed formula; please define it before the display and clarify the constant factors dropped in the equivalence between the MAP rule and the distance minimizer.
  4. [Section VI, Eq. (44) step (d)] The algebraic justification of inequality (d) is lengthy and hard to follow; it would improve readability to state the resulting bound as a separate lemma or move the algebra to an appendix.
  5. [Section V, open problem 1] The conjecture that 'higher-dimensional attributes should make exact matching progressively easier' is vague; the converse in Theorem 2 only covers d = O(log n), so specifying a concrete conjectured threshold for d = ω(log n) would make the open problem more precise.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main theorems are derived from explicit probabilistic bounds and independent external prior results, not from the conclusions being assumed.

full rationale

The paper's central claims are not circular. Theorem 1 is proved directly in Section VI via Lemma 1 and Lemma 2, with the two high-probability events A1 and A2; the conditions (7) and (8) are obtained from explicit tail bounds, not from the conclusion. Theorem 5 combines a k-core matching step, proved in Section IX-C using external k-core results (Lemma 3 from Gaudio–Racz–Sridhar, Lemma 4 from Racz–Sridhar), with Theorem 1 applied to the residual nodes. The additive threshold (23) arises as the composition of the residual-size bound (35) and the attribute-matching condition, rather than being a fitted parameter renamed as a prediction. The self-citations to the authors' earlier work [7], [13] appear as methodological precedents and consistency checks in the d=0 or p=q=0 special cases, not as load-bearing substitutions for the proofs given here. External benchmarks such as Dai–Cullina–Kiyavash for database alignment, Ndaoud and Abbe–Fan–Wang for single-graph recovery, and Racz–Sridhar for k-core matching are independent of the target results. Section V explicitly acknowledges the achievability–converse gaps, and the proof does contain nontrivial gaps (the residual set F after k-core matching is asserted rather than proven to form an independent CGMM, and the union bound in Eq. (44) drops P(A^c) before multiplying by the n^t cycle count), but these are correctness concerns about the displayed proof, not circular reductions of the conclusions to the inputs.

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

The paper does not introduce new physical entities; the correlated GMM and CCSBM are statistical models built from existing SBM, CSBM, and correlated Gaussian database ingredients. The main external dependencies are the k-core matching theory, database alignment converse, and single-graph community recovery thresholds from other groups. One home-grown assumption, the independence of the residual unmatched set F, is not fully justified.

free parameters (2)
  • k-core size parameter k = log n/(log log n)^2 or nps^2/(log(nps^2))^2, whichever is larger
    Chosen by hand in Theorem 5 to balance the size and accuracy of the k-core matching step. The final theorem is not tuned to data, but the choice of k is a proof device.
  • lambda = r*rho for a constant r in (0,1)
    Introduced in Lemma 1 and Theorem 1's second branch to tighten the Gaussian tail bound through the event A2. The existence of such an r depends on the margin epsilon in condition (8).
assumptions (5)
  • standard math Standard Gaussian tail bounds, chi-squared MGF and Laplacian eigenvalue facts (Lemmas 18-22) are used without proof.
    These are standard tools invoked throughout Section VI and XIII.
  • domain assumption The k-core matching results of Gaudio et al. [8] and Racz-Sridhar [35] hold for correlated SBMs with two communities and the stated p, q, s regime.
    Theorem 12 and Lemma 4 are imported from these references and are load-bearing for the first step of the CCSBM matching algorithm.
  • domain assumption The database alignment impossibility results of Dai et al. [9] and Wang et al. [36] apply to the reduced problem in the proof of Theorems 2 and 6.
    The converses reveal partial ground-truth permutation and community labels, then cite these prior impossibility results directly.
  • domain assumption The single-graph exact recovery thresholds for GMM and CSBM from Ndaoud [14] and Abbe-Fan-Wang [5] remain valid when applied to the averaged attributes and union graph.
    Theorem 3 and Theorem 7 invoke these external results after constructing the merged database/graph.
  • ad hoc to paper The residual unmatched set F after k-core matching is itself a correlated Gaussian Mixture Model, independent of the edge-dependent selection of F.
    Sections IV-B and IX-A use this assumption to apply Theorem 1 to the remaining nodes, but conditional independence of F given edge realization is not proven.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Exact Matching in Correlated Networks with Node Attributes for Improved Community Recovery." pith.science (2026). https://pith.science/paper/BFLIWOUH

@misc{pith2026250102851,
  author       = {Pith},
  title        = {Pith review of: Exact Matching in Correlated Networks with Node Attributes for Improved Community Recovery},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BFLIWOUH}},
  note         = {Machine review of arXiv:2501.02851}
}
abstract

We study community detection in multiple networks with jointly correlated node attributes and edges. This setting arises naturally in applications such as social platforms, where a shared set of users may exhibit both correlated friendship patterns and correlated attributes across different platforms. Extending the classical Stochastic Block Model (SBM) and its contextual counterpart (Contextual SBM or CSBM), we introduce the correlated CSBM, which incorporates structural and attribute correlations across graphs. To build intuition, we first analyze correlated Gaussian Mixture Models, wherein only correlated node attributes are available without edges, and identify the conditions under which an estimator minimizing the distance between attributes achieves exact matching of nodes across the two databases. For the correlated CSBMs, we develop a two-step procedure that first applies $k$-core matching to most nodes using edge information, then refines the matching for the remaining unmatched nodes by leveraging their attributes with a distance-based estimator. We identify the conditions under which the algorithm recovers the exact node correspondence, enabling us to merge the correlated edges and average the correlated attributes for enhanced community detection. Crucially, by aligning and combining graphs, we identify regimes in which community detection is impossible in a single graph but becomes feasible when side information from correlated graphs is incorporated. Our results illustrate how the interplay between graph matching and community recovery can boost performance, broadening the scope of multi-graph, attribute-based community detection.

Figures

Figures reproduced from arXiv: 2501.02851 by the authors.

Figure 1
Figure 1. Conditions for exact community recovery ( [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. The region in blue indicates where exact matching is possible in correlated CSBMs, and the gray region shows where matching is infeasible. The red dashed line (d = 0) captures the special case of correlated SBMs, while the yellow dashed line (p = q = 0) represents correlated GMMs. Each dashed line intersects the boundary of the blue region at its respective matching threshold, thus recovering the known results for c… view at source ↗
Figure 3
Figure 3. visualizes the parameter ranges under which community recovery is possible or impossible in correlated CSBMs. It highlights how adding correlated node attributes and edges can expand the regime where exact community detection succeeds [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

43 extracted references · 39 canonical work pages

  1. [1]

    Stochastic blockmodels: First steps,

    P. W. Holland, K. B. Laskey, and S. Leinhardt, “Stochastic blockmodels: First steps,” Social networks, vol. 5, no. 2, pp. 109–137, 1983

    1983

  2. [2]

    Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery,

    E. Abbe and C. Sandon, “Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery,” in 2015 IEEE 56th Annual Symposium on Foundations of Computer Science . IEEE, 2015, pp. 670–688

    work page 2015

  3. [3]

    Exact recovery in the stochastic block model,

    E. Abbe, A. S. Bandeira, and G. Hall, “Exact recovery in the stochastic block model,” IEEE Transactions on information theory , vol. 62, no. 1, pp. 471–487, 2015

    work page 2015

  4. [4]

    Community detection and stochastic block models: recent developments,

    E. Abbe, “Community detection and stochastic block models: recent developments,” The Journal of Machine Learning Research , vol. 18, no. 1, pp. 6446–6531, 2017

    work page 2017

  5. [5]

    An ℓp theory of pca and spectral clustering,

    E. Abbe, J. Fan, and K. Wang, “An ℓp theory of pca and spectral clustering,” The Annals of Statistics , vol. 50, no. 4, pp. 2359–2385, 2022

    work page 2022

  6. [6]

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

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

    work page 2021

  7. [7]

    Graph matching in correlated stochastic block models for improved graph clustering,

    J. Yang and H. W. Chung, “Graph matching in correlated stochastic block models for improved graph clustering,” in 2023 59th Annual Allerton Conference on Communication, Control, and Computing (Allerton) . IEEE, 2023

    work page 2023

  8. [8]

    Exact community recovery in correlated stochastic block models,

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

    work page 2022

Show all 43 references
  1. [9]

    Database alignment with gaussian features,

    O. E. Dai, D. Cullina, and N. Kiyavash, “Database alignment with gaussian features,” in The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 2019, pp. 3225–3233

    2019

  2. [10]

    Strong recovery of geometric planted matchings,

    D. Kunisky and J. Niles-Weed, “Strong recovery of geometric planted matchings,” in Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2022, pp. 834–876

    2022

  3. [11]

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

    D. Cullina, N. Kiyavash, P. Mittal, and H. V . Poor, “Partial recovery of erd˝os-r´enyi graph alignment via k-core alignment,”ACM SIGMETRICS Performance Evaluation Review, vol. 48, no. 1, pp. 99–100, 2020

    2020

  4. [12]

    Settling the sharp reconstruction thresholds of random graph matching,

    Y . Wu, J. Xu, and H. Y . Sophie, “Settling the sharp reconstruction thresholds of random graph matching,” IEEE Transactions on Information Theory , vol. 68, no. 8, pp. 5391–5417, 2022

    2022

  5. [13]

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

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

    2024

  6. [14]

    Sharp optimal recovery in the two component gaussian mixture model,

    M. Ndaoud, “Sharp optimal recovery in the two component gaussian mixture model,” The Annals of Statistics , vol. 50, no. 4, pp. 2096–2126, 2022

    2022

  7. [15]

    On the privacy of anonymized networks,

    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 , 2011, pp. 1235–1243

    2011

  8. [16]

    Improved achievability and converse bounds for erd ˝os-r´enyi graph matching,

    D. Cullina and N. Kiyavash, “Improved achievability and converse bounds for erd ˝os-r´enyi graph matching,” ACM SIGMETRICS performance evaluation review, vol. 44, no. 1, pp. 63–72, 2016

    2016

  9. [17]

    Exact alignment recovery for correlated erd ˝os-r´enyi graphs,

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

    2017 arXiv

  10. [18]

    Seeded graph matching via large neighborhood statistics,

    E. Mossel and J. Xu, “Seeded graph matching via large neighborhood statistics,” Random Structures & Algorithms , vol. 57, no. 3, pp. 570–611, 2020

    2020

  11. [19]

    (nearly) efficient algorithms for the graph matching problem on correlated random graphs,

    B. Barak, C.-N. Chou, Z. Lei, T. Schramm, and Y . Sheng, “(nearly) efficient algorithms for the graph matching problem on correlated random graphs,” Advances in Neural Information Processing Systems , vol. 32, 2019. 33

    2019

  12. [20]

    Efficient random graph matching via degree profiles,

    J. Ding, Z. Ma, Y . Wu, and J. Xu, “Efficient random graph matching via degree profiles,” Probability Theory and Related Fields , vol. 179, pp. 29–115, 2021

    2021

  13. [21]

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

    Z. Fan, C. Mao, Y . Wu, and J. Xu, “Spectral graph matching and regularized quadratic relaxations ii: Erd ˝os-r´enyi graphs and universality,” Foundations of Computational Mathematics , vol. 23, no. 5, pp. 1567–1617, 2023

    2023

  14. [22]

    Random graph matching with improved noise robustness,

    C. Mao, M. Rudelson, and K. Tikhomirov, “Random graph matching with improved noise robustness,” in Conference on Learning Theory . PMLR, 2021, pp. 3296–3329

    2021

  15. [23]

    Exact matching of random graphs with constant correlation,

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

    2023

  16. [24]

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

    C. Mao, Y . Wu, J. Xu, and S. H. Yu, “Random graph matching at otter’s threshold via counting chandeliers,” in Proceedings of the 55th Annual ACM Symposium on Theory of Computing , 2023, pp. 1345–1356

    2023

  17. [25]

    Optimal de-anonymization in random graphs with community structure,

    E. Onaran, S. Garg, and E. Erkip, “Optimal de-anonymization in random graphs with community structure,” in 2016 50th Asilomar conference on signals, systems and computers . IEEE, 2016, pp. 709–713

    2016

  18. [26]

    On the simultaneous preservation of privacy and community structure in anonymized networks,

    D. Cullina, K. Singhal, N. Kiyavash, and P. Mittal, “On the simultaneous preservation of privacy and community structure in anonymized networks,” arXiv preprint arXiv:1603.08028 , 2016

    2016 arXiv

  19. [27]

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

    J. Yang, D. Shin, and H. W. Chung, “Efficient algorithms for exact graph matching on correlated stochastic block models with constant correlation,” in International Conference on Machine Learning . PMLR, 2023, pp. 39 416–39 452

    2023

  20. [28]

    Efficient graph matching for correlated stochastic block models,

    S. Chai and M. Z. Racz, “Efficient graph matching for correlated stochastic block models,” in The Thirty-eighth Annual Conference on Neural Information Processing Systems

  21. [29]

    Achievability of nearly-exact alignment for correlated gaussian databases,

    O. E. Dai, D. Cullina, and N. Kiyavash, “Achievability of nearly-exact alignment for correlated gaussian databases,” in 2020 IEEE International Symposium on Information Theory (ISIT) . IEEE, 2020, pp. 1230–1235

    2020

  22. [30]

    Fundamental limits of database alignment,

    D. Cullina, P. Mittal, and N. Kiyavash, “Fundamental limits of database alignment,” in 2018 IEEE International Symposium on Information Theory (ISIT). IEEE, 2018, pp. 651–655

    2018

  23. [31]

    Gaussian database alignment and gaussian planted matching,

    O. E. Dai, D. Cullina, and N. Kiyavash, “Gaussian database alignment and gaussian planted matching,” arXiv preprint arXiv:2307.02459 , 2023

    2023 arXiv

  24. [32]

    Attributed graph alignment,

    N. Zhang, W. Wang, and L. Wang, “Attributed graph alignment,” in 2021 IEEE International Symposium on Information Theory (ISIT) . IEEE, 2021, pp. 1829–1834

    2021

  25. [33]

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

    Z. Wang, N. Zhang, W. Wang, and L. Wang, “On the feasible region of efficient algorithms for attributed graph alignment,” IEEE Transactions on Information Theory, 2024

    2024

  26. [34]

    Harnessing multiple correlated networks for exact community recovery,

    M. Z. Racz and J. Zhang, “Harnessing multiple correlated networks for exact community recovery,” in The Thirty-eighth Annual Conference on Neural Information Processing Systems

  27. [35]

    Matching correlated inhomogeneous random graphs using the k-core estimator,

    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) . IEEE, 2023, pp. 2499–2504

    2023

  28. [36]

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

    H. Wang, Y . Wu, J. Xu, and I. Yolou, “Random graph matching in geometric models: the case of complete graphs,” in Conference on Learning Theory . PMLR, 2022, pp. 3441–3488

    2022

  29. [37]

    Exact random graph matching with multiple graphs,

    T. Ameen and B. Hajek, “Exact random graph matching with multiple graphs,” arXiv preprint arXiv:2405.12293 , 2024

    2024 arXiv

  30. [38]

    Exact community recovery in the geometric sbm,

    J. Gaudio, X. Niu, and E. Wei, “Exact community recovery in the geometric sbm,” in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) . SIAM, 2024, pp. 2158–2184

    2024

  31. [39]

    Sharp exact recovery threshold for two-community euclidean random graphs,

    J. Gaudio and C. K. Guan, “Sharp exact recovery threshold for two-community euclidean random graphs,” arXiv preprint arXiv:2501.14830 , 2025

    2025 arXiv

  32. [40]

    Stochastic blockmodels and community structure in networks,

    B. Karrer and M. E. Newman, “Stochastic blockmodels and community structure in networks,” Physical Review E?Statistical, Nonlinear, and Soft Matter Physics, vol. 83, no. 1, p. 016107, 2011

    2011

  33. [41]

    Size and connectivity of the k-core of a random graph,

    T. Łuczak, “Size and connectivity of the k-core of a random graph,” Discrete Mathematics, vol. 91, no. 1, pp. 61–68, 1991

    1991

  34. [42]

    Supplementary material for correlated stochastic block models: Exact graph matching with applications to recovering communities

    M. Racz and A. Sridhar, “Supplementary material for correlated stochastic block models: Exact graph matching with applications to recovering communities.”

  35. [43]

    An alternative point of view on lepski’s method,

    L. Birg ´e, “An alternative point of view on lepski’s method,” Lecture Notes-Monograph Series , pp. 113–133, 2001

    2001

Pith tools

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