REVIEW 4 cited by
Efficiently matching random inhomogeneous graphs via degree profiles
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
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(\log^{2} n)$ and the minimal correlation is at least $1 - O(\log^{-2} n)$.
Forward citations
Cited by 4 Pith papers
-
Harnessing Multiple Correlated Networks for Exact Community Recovery
For any fixed K, exact community recovery from K edge-correlated stochastic block models is characterized by a two-part inequality combining graph matchability and single-graph community signal.
-
Efficient Graph Matching for Correlated Stochastic Block Models
A polynomial-time algorithm matches two correlated stochastic block models of logarithmic average degree almost exactly for s^2 > 0.338, and exactly whenever s^2(a+b)/2 > 1.
-
Sample Complexity of Correlation Detection in the Gaussian Wigner Model
The optimal induced-subgraph sample size for detecting correlation in the Gaussian Wigner model is s ≈ sqrt(max(n log n / log(1/(1-ρ^2)), n)).
-
Robust Random Graph Matching in Dense Graphs via an Approximate Message Passing Type Algorithm
An approximate message passing algorithm provably recovers the latent matching between correlated Gaussian matrices under adversarial principal-minor corruption of size n/(log n)^20.
Discussion (0). Continue with ORCID to comment.