ML p(r)ior | Improved Achievability and Converse Bounds for Erdős-Rényi Graph Matching

### 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.

Highlights - Most important sentences from the article

# 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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

2017-05-05
1705.02294 | math.ST

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

Highlights - Most important sentences from the article

2014-06-10
1406.2587 | cs.SI

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

2018-11-16
1811.06931 | cs.LG

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

Highlights - Most important sentences from the article

2018-01-12
1801.04339 | math.ST

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

2019-03-04
1903.01342 | math.PR

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article