mlsanityData to 14 Oct 2026

Efficiently matching random inhomogeneous graphs via degree profiles

arXiv 2310.10441 ↗First posted 16 Oct 2023cs.DS math.PR math.STcited by 5

Not on the map. Why?

Abstract (arXiv)

In this paper, we study the problem of recovering the latent vertex correspondence between two correlated random graphs with vastly inhomogeneous and unknown edge probabilities between different pairs of vertices. Inspired by and extending the matching algorithm via degree profiles by Ding, Ma, Wu and Xu (2021), we obtain an efficient matching algorithm as long as the minimal average degree is at least Omega(log2 n) and the minimal correlation is at least 1 - O(log-2 n).

Key facts. Cited by 5 papers in the map (data through 14 Oct 2026). Builds on 32 of its 64 references that are in the map. First posted on arXiv 16 Oct 2023.

Builds on

32 of 64 references.

References · 32

  1. 2018Efficient random graph matching via degree profilescited by 48
  2. 2013Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodelcited by 45
  3. 2021Settling the Sharp Reconstruction Thresholds of Random Graph Matchingcited by 45
  4. 2017Exact alignment recovery for correlated ErdHos-R'enyi graphscited by 38
  5. 2016Community Detection in Degree-Corrected Block Modelscited by 36
  6. 2016Improved Achievability and Converse Bounds for ErdHos-R'enyi Graph Matchingcited by 30
  7. 2018(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphscited by 29
  8. 2018Seeded Graph Matching via Large Neighborhood Statisticscited by 27
  9. 2019Spectral Graph Matching and Regularized Quadratic Relaxations II: ErdHos-R'enyi Graphs and Universalitycited by 27
  10. 2020Partial Recovery in the Graph Alignment Problemcited by 27
  11. 2020From tree matching to sparse graph alignmentcited by 26
  12. 2020Testing correlation of unlabeled random graphscited by 26
20 more
  1. 2018Partial Recovery of ErdHos-R'enyi Graph Alignment via k-Core Alignmentcited by 25
  2. 2022Random graph matching at Otter's threshold via counting chandelierscited by 25
  3. 2021Exact Matching of Random Graphs with Constant Correlationcited by 23
  4. 2021Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communitiescited by 22
  5. 2021Testing network correlation efficiently via counting treescited by 22
  6. 2022Random Graph Matching in Geometric Models: the Case of Complete Graphscited by 22
  7. 2021Impossibility of Partial Recovery in the Graph Alignment Problemcited by 21
  8. 2013Seeded graph matching for correlated ErdHos-R'enyi graphscited by 20
  9. 2015Convexified Modularity Maximization for Degree-corrected Stochastic Block Modelscited by 16
  10. 2022Matching recovery threshold for correlated random graphscited by 16
  11. 2022Detection threshold for correlated ErdHos-R'enyi graphs via densest subgraphscited by 13
  12. 2020Correlated randomly growing graphscited by 12
  13. 2022Statistical limits of correlation detection in treescited by 12
  14. 2019Seedless Graph Matching via Tail of Degree Distribution for Correlated Erdos-Renyi Graphscited by 9
  15. 2023A polynomial-time iterative algorithm for random graph matching with non-vanishing correlationcited by 9
  16. 2022A polynomial time iterative algorithm for matching Gaussian matrices with non-vanishing correlationcited by 8
  17. 2021The Power of D-hops in Matching Power-Law Graphscited by 7
  18. 2023Matching Correlated Inhomogeneous Random Graphs using the k-core Estimatorcited by 6
  19. 2023The Algorithmic Phase Transition of Random Graph Alignment Problemcited by 4
  20. 2022A polynomial-time approximation scheme for the maximal overlap of two independent ErdHos-R'enyi graphscited by 3

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 4.

5 papers.

  1. 2024The Umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regimecited by 6
  2. 2024Efficient Graph Matching for Correlated Stochastic Block Modelscited by 5
  3. 2023Robust Point Matching with Distance Profilescited by 1
  4. 2024Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphscited by 0
  5. 2024Robust Random Graph Matching in Dense Graphs via an Approximate Message Passing Type Algorithmcited by 0