Shotgun assembly of Erdős-Rényi random graphs

Julia Gaudio, Elchanan Mossel

Abstract

Graph shotgun assembly refers to the problem of reconstructing a graph from a collection of local neighborhoods. In this paper, we consider shotgun assembly of Erdős–Rényi random graphs $G(n,p_n)$, where $p_n=n^{-\alpha}$ for $0<\alpha<1$. We consider both reconstruction up to isomorphism as well as exact reconstruction (recovering the vertex labels as well as the structure). We show that given the collection of distance-1 neighborhoods, $G$ is exactly reconstructable for $0<\alpha<1/3$, but not reconstructable for $1/2<\alpha<1$. Given the collection of distance-2 neighborhoods, $G$ is exactly reconstructable for $\alpha \in (0,1/2) \cup (1/2,3/5)$, but not reconstructable for $3/4<\alpha<1$.

Introduction

The concept of "shotgun assembly" is a direct analogy to DNA sequencing techniques, where a long genomic sequence is reconstructed from a vast collection of short, overlapping fragments. In the context of graph theory, this problem asks whether a global graph structure can be uniquely recovered from a multiset of its local neighborhoods.

This research focuses on the Erdős-Rényi random graph model $G(n, p_n)$, where $n$ is the number of vertices and $p_n = n^{-\alpha}$ is the probability of an edge existing between any two vertices. The primary goal is to identify the density thresholds (defined by $\alpha$) where a graph can be reconstructed from its $r$-neighborhoods—the subgraphs induced by vertices within distance $r$ of a central node.

Problem Formulation

We distinguish between two types of reconstruction:

  1. Exact Reconstruction: Recovering the original vertex labels and the complete edge set.
  2. Reconstruction up to Isomorphism: Recovering the structural topology of the graph without necessarily identifying the original vertex labels.

For random graphs in the regimes studied, these two goals often coincide because the graphs are typically asymmetric, meaning each vertex has a unique structural role.

Methodology

The authors employ several sophisticated probabilistic and combinatorial methods to establish the boundaries of reconstructability:

1. The Fingerprinting Method

To prove that a graph is reconstructable, the authors look for unique "fingerprints" for every edge. For example, if every pair of connected nodes $(u, v)$ possesses a unique number of common neighbors or a unique internal structure within their shared neighborhood, this signature allows an algorithm to uniquely identify which local snapshots should be joined. This is particularly effective in denser regimes.

2. The Overlap Method

This technique involves using information from a smaller neighborhood (radius $r-1$) to uniquely label the vertices within a larger neighborhood (radius $r$). If the internal vertices of a snapshot can be uniquely identified relative to the center, the global graph can be assembled by "crawling" through overlapping snapshots and stitching them together systematically.

3. The First Moment Method and Counting Arguments

To prove non-reconstructability, the authors demonstrate that in sparse regimes, the number of possible graph configurations is significantly larger than the number of possible neighborhood collections. By showing that different graphs can produce the exact same set of local neighborhoods with high probability, they prove that unique reconstruction is information-theoretically impossible.

Key Results

The study identifies critical phase transitions for $\alpha$ based on the radius $r$ of the provided neighborhoods:

Distance-1 Neighborhoods ($r=1$)

  • Success: Graphs are exactly reconstructable when $0 < \alpha < 1/3$. In this regime, the graph is dense enough that local neighborhoods provide sufficient unique information.
  • Failure: Reconstruction is impossible when $1/2 < \alpha < 1$. In these sparser regimes, the neighborhoods become too generic (often resembling simple trees) to allow for unique assembly.

Distance-2 Neighborhoods ($r=2$)

  • Success: Graphs are exactly reconstructable for $\alpha \in (0, 1/2) \cup (1/2, 3/5)$. Increasing the radius of observation allows the assembly process to succeed on much sparser graphs.
  • Failure: Reconstruction is impossible when $3/4 < \alpha < 1$.

Discussion and Future Work

While this paper provides rigorous bounds, several open questions remain. There are "gray areas" in the $\alpha$ ranges (such as $1/3 \leq \alpha \leq 1/2$ for $r=1$) where the exact threshold is not yet determined. Concurrent research suggests the true transition for $r=1$ may occur at $p \approx n^{-1/2}$.

Furthermore, while the paper proves that reconstruction is information-theoretically possible, it does not always provide a computationally efficient (polynomial-time) algorithm for every regime. Future work is needed to bridge the gap between mathematical possibility and algorithmic efficiency, as well as to extend these findings to non-random, real-world network topologies.

Summary updated

Abstract

Graph shotgun assembly refers to the problem of reconstructing a graph from a collection of local neighborhoods. In this paper, we consider shotgun assembly of Erdős–Rényi random graphs G(n,pn), where pn=n−α for 0<α<1. We consider both reconstruction up to isomorphism as well as exact reconstruction (recovering the vertex labels as well as the structure). We show that given the collection of distance-1 neighborhoods, G is exactly reconstructable for 0<α<1 3, but not reconstructable for 1 2<α<1. Given the collection of distance-2 neighborhoods, G is exactly reconstructable for α∈0,1 2∪1 2,3 5, but not reconstructable for 3 4<α<1.
BibTeX
@inproceedings{gaudio2022shotgun,
  author = {Julia Gaudio and Elchanan Mossel},
  title = {{Shotgun assembly of Erdős-Rényi random graphs}},
  booktitle = {Electronic},
  year = {2022},
  doi = {10.1214/22-ecp445},
}
Figure