### Improved Achievability and Converse Bounds for Erdős-Rényi Graph Matching

**2016-02-02**

1602.01042 | cs.IT

We consider the problem of perfectly recovering the vertex correspondence
between two correlated Erd\H{o}s-R\'enyi (ER) graphs. For a pair of correlated
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. In some
cases, the structural information in the graphs allow this correspondence to be
recovered. We investigate 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.
Pedarsani and Grossglauser provided an achievability result of this type.
Their result establishes the scaling dependence of the threshold on the number
of vertices. We improve on their achievability bound. We also provide a
converse bound, establishing conditions under which exact recovery is
impossible. Together, these establish the scaling dependence of the threshold
on the level of correlation between the two graphs. The converse and
achievability bounds differ by a factor of two for sparse, significantly
correlated graphs.

**Login to like/save this paper, take notes and configure your recommendations**

# Related Articles

**2019-04-05**

1904.03313 | math.PR

We consider the problem of estimating a vector of discrete variables
$(\theta_1,\cdots,\theta_n)$, b… show more

**2018-05-07**

1805.02349 | cs.DS

We give a quasipolynomial time algorithm for the graph matching problem (also
known as noisy or robu… show more

**2018-03-06**

1803.02423 | stat.ML

The problem of finding the vertex correspondence between two noisy graphs
with different number of v… show more

**2017-05-05**

1705.02294 | math.ST

We consider the problem of graph matchability in non-identically distributed
networks. In a general … show more

**2014-06-10**

1406.2587 | cs.SI

This research establishes that many real-world networks exhibit bounded
expansion, a strong notion o… show more

**2018-12-26**

1812.10519 | stat.ML

Given a pair of graphs with the same number of vertices, the inexact graph
matching problem consists… show more

**2018-11-16**

We consider the exact recovery problem in the hypergraph stochastic block
model (HSBM) with $k$ bloc… show more

**2018-01-12**

1801.04339 | math.ST

Learning properties of large graphs from samples has been an important
problem in statistical networ… show more

**2018-10-31**

1810.13347 | cs.CR

In this paper, matching pairs of random graphs under the community structure
model is considered. Th… show more

**2018-06-10**

1806.03571 | stat.ML

We consider the problem of model selection in Gaussian Markov fields in the
sample deficient scenari… show more

**2018-10-02**

1810.01111 | math.CO

Given a loop-free graph $H$, the reconfiguration problem for homomorphisms to
$H$ (also called $H$-c… show more

**2017-05-22**

1705.07997 | math.ST

We formulate and analyze a novel hypothesis testing problem for inferring the
edge structure of an i… show more

**2019-03-04**

1903.01342 | math.PR

We establish and generalise several bounds for various random walk quantities
including the mixing t… show more

**2018-07-24**

1807.08886 | cs.DS

Any graph with maximum degree $\Delta$ admits a proper vertex coloring with
$\Delta + 1$ colors that… show more

**2018-04-12**

1804.05013 | cs.DM

We provide new connectivity results for {\em vertex-random graphs} or {\em
random annulus graphs} wh… show more

**2018-09-26**

1809.09879 | math.PR

Suppose that there is a family of $n$ random points $X_v$ for $v \in V$,
independently and uniformly… show more