Proves detection of RGG vs. ER is impossible for d ≫ (n h(p))^3 and d ≥ (1+ε)n, resolving the detection threshold conjecture in the regime p ≳ n^{-2/3}/log n.
Exact alignment recovery for correlated Erd\H{o}s-R\'enyi graphs
7 Pith papers cite this work. Polarity classification is still indexing.
7
Pith papers citing it
abstract
We consider the problem of perfectly recovering the vertex correspondence between two correlated Erd\H{o}s-R\'enyi (ER) graphs on the same vertex set. The correspondence between the vertices can be obscured by randomly permuting the vertex labels of one of the graphs. We determine the information-theoretic threshold for exact recovery, i.e. the conditions under which the entire vertex correspondence can be correctly recovered given unbounded computational resources.
verdicts
UNVERDICTED 7representative citing papers
A consistent estimator for the correlation parameter alpha is constructed for a new model of correlated uniform attachment trees as their size tends to infinity.
Proves all-or-nothing exact alignment threshold in Gaussian multi-graph model and partial alignment impossibility threshold in sparse ER model, via a Bayesian estimation framework over metric spaces.
GRAMPA recovers exact vertex correspondence in the Gaussian Wigner model with high probability for σ = O(1/log n) via a regularized quadratic relaxation using all eigenvector pairs.
The paper characterizes exact and partial recovery thresholds in the featured correlated Gaussian Wigner model and proposes the QPAlign quadratic programming algorithm with theoretical guarantees.
Develops a tree-correlation algorithm for diffusion-network alignment with high-probability correctness guarantees and explicit depth-dependent probability bounds in sparse graphs.
Umeyama algorithm achieves exact recovery of latent permutation π* in correlated Gaussian geometric models for σ = o(d^{-3}n^{-2/d}) and almost exact for σ = o(d^{-3}n^{-1/d}) when d = O(log n).
citing papers explorer
-
Resolution of the Detection Threshold Conjecture for Random Geometric Graphs in the $d>n$ Regime
Proves detection of RGG vs. ER is impossible for d ≫ (n h(p))^3 and d ≥ (1+ε)n, resolving the detection threshold conjecture in the regime p ≳ n^{-2/3}/log n.
-
Correlated uniform attachment trees
A consistent estimator for the correlation parameter alpha is constructed for a new model of correlated uniform attachment trees as their size tends to infinity.
-
The feasibility of multi-graph alignment: a Bayesian approach
Proves all-or-nothing exact alignment threshold in Gaussian multi-graph model and partial alignment impossibility threshold in sparse ER model, via a Bayesian estimation framework over metric spaces.
-
Spectral Graph Matching and Regularized Quadratic Relaxations I: The Gaussian Model
GRAMPA recovers exact vertex correspondence in the Gaussian Wigner model with high probability for σ = O(1/log n) via a regularized quadratic relaxation using all eigenvector pairs.
-
Attributed Network Alignment: Statistical Limits and Efficient Algorithm
The paper characterizes exact and partial recovery thresholds in the featured correlated Gaussian Wigner model and proposes the QPAlign quadratic programming algorithm with theoretical guarantees.
-
Diffusion-Network Alignment: An Efficient Algorithm and Explicit Probability Bounds
Develops a tree-correlation algorithm for diffusion-network alignment with high-probability correctness guarantees and explicit depth-dependent probability bounds in sparse graphs.
-
The Umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regime
Umeyama algorithm achieves exact recovery of latent permutation π* in correlated Gaussian geometric models for σ = o(d^{-3}n^{-2/d}) and almost exact for σ = o(d^{-3}n^{-1/d}) when d = O(log n).