Shotgun Assembly of Labeled Graphs

We consider the problem of reconstructing graphs or labeled graphs from neighborhoods of a given radius $r$r. Special instances of this problem include the well-known: DNA shotgun assembly; the lesser-known: neural network reconstruction; and a new problem: assembling random jigsaw puzzles. We provide some necessary and some sufficient conditions for correct recovery both in combinatorial terms and for some generative models including random labelings of lattices, Erdős-Rényi random graphs, and a random jigsaw puzzle model. Many open problems and conjectures are provided.

• Publication year

  2015

• Venue

  IEEE Transactions on Network Science and Engineering

• Publication date

  2015-04-28

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/TNSE.2017.2776913arXiv 1504.07682
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Reconstructing Random Jigsaws

  2017cited by this paper
• A Linear Threshold for Uniqueness of Solutions to Random Jigsaw Puzzles

  2017cited by this paper
• Shotgun assembly of random jigsaw puzzles

  2016cited by this paper
• Unique reconstruction threshold for random jigsaw puzzles

  2016cited by this paper
• Shotgun edge assembly of random jigsaw puzzles

  2016cited by this paper
• Efficient "Shotgun" Inference of Neural Connectivity from Highly Sub-sampled Activity Data

  2015cited by this paper
• Shotgun assembly of random regular graphs

  2015cited by this paper
• Transitive graphs uniquely determined by their local structure

  2014cited by this paper
• A shotgun sampling solution for the common input problem in neural connectivity inference

  2013cited by this paper
• Information Theory of DNA Shotgun Sequencing

  2012cited by this paper
• The continuum limit of critical random graphs

  2009influential reference
• The diameter of sparse random graphs

  2007cited by this paper
• Critical random graphs: Diameter and mixing time

  2007cited by this paper
• Processes on Unimodular Random Networks

  2006cited by this paper
• Random trees and random graphs

  1998cited by this paper
• Random trees and random graphs

  1998cited by this paper
• Probabilistic Bounds on the Coefficients of Polynomials with Only Real Zeros

  1997cited by this paper
• Poisson Process Approximation for Sequence Repeats, and Sequencing by Hybridization

  1996cited by this paper
• The Probability of Unique Solutions of Sequencing by Hybridization

  1994cited by this paper
• An optimal lower bound on the number of variables for graph identification

  1992cited by this paper
• The Diameter of Random Graphs

  1981cited by this paper
• Random Graph Isomorphism

  1980cited by this paper
• A survey of the reconstruction conjecture

  1974cited by this paper
• A congruence theorem for trees.

  1957cited by this paper

• Shotgun assembly of unlabeled Erdős–Rényi graphs

  2025cites this paper
• Not every graph can be reconstructed from its boundary distance matrix

  2025cites this paper
• Reconstructing a graph from the boundary distance matrix

  2025cites this paper
• Relational Learning in Pre-Trained Models: A Theory from Hypergraph Recovery Perspective

  2024cites this paper
• Reconstruction of shredded random matrices

  2024cites this paper
• HOPE: Shape Matching Via Aligning Different K-hop Neighbourhoods

  2024cites this paper
• Reconstructing Graphs from Connected Triples

  2023cites this paper
• Graph reconstruction from connected triples

  2023cites this paper
• Average-case and smoothed analysis of graph isomorphism

  2022influential citation
• Shotgun assembly of random graphs

  2022influential citation
• Reconstructing Random Pictures

  2022influential citation
• Shotgun Assembly of Random Geometric Graphs

  2022cites this paper
• Shotgun Assembly of Linial-Meshulam Model

  2022cites this paper
• Shotgun assembly threshold for lattice labeling model

  2022influential citation
• Shotgun Threshold for Sparse Erdős–Rényi Graphs

  2022influential citation
• A Probabilistic Analysis of Shotgun Sequencing for Metagenomics

  2022cites this paper
• Graph Reconstruction from Random Subgraphs

  2022cites this paper
• Shotgun assembly of unlabeled Erdos-Renyi graphs

  2021cites this paper
• Selected Neighbor Degree Forest Realization

  2021cites this paper
• Realization Problems on Reachability Sequences

  2020cites this paper
• Reconstructing in the Constraint Satisfaction Problem

  2020cites this paper
• Minimum Neighboring Degree Realization in Graphs and Trees

  2020cites this paper
• Computing and Combinatorics: 26th International Conference, COCOON 2020, Atlanta, GA, USA, August 29–31, 2020, Proceedings

  2020influential citation
• Shotgun identification on groups

  2020influential citation
• Shotgun Assembly of Erd\H{o}s-R\'enyi Random Graphs.

  2020influential citation
• Shotgun assembly of Erdős-Rényi random graphs

  2020influential citation
• Graph matching beyond perfectly-overlapping Erdős–Rényi random graphs

  2020cites this paper
• Graph Realizations: Maximum and Minimum Degree in Vertex Neighborhoods

  2019cites this paper
• Reconstructing Trees from Traces

  2019cites this paper
• Shotgun reconstruction in the hypercube

  2019influential citation
• Localizing the Source of an Epidemic Using Few Observations

  2018cites this paper
• Realizability of Graph Specifications: Characterizations and Algorithms

  2018cites this paper
• Efficient random graph matching via degree profiles

  2018cites this paper
• Graph Profile Realizations and Applications to Social Networks

  2018cites this paper
• Solving Jigsaw Puzzles By the Graph Connection Laplacian

  2018cites this paper
• Topics in extremal graph theory and probabilistic combinatorics

  2018cites this paper
• Alignment and Assembly - Inferring Networks from Noisy Observations

  2017cites this paper
• Subsampling large graphs and invariance in networks

  2017cites this paper
• Reconstructing Random Jigsaws

  2017influential citation
• A Linear Threshold for Uniqueness of Solutions to Random Jigsaw Puzzles

  2017influential citation
• Shotgun assembly of random jigsaw puzzles

  2016influential citation
• Unique reconstruction threshold for random jigsaw puzzles

  2016influential citation
• MIT Open Access Articles Shotgun assembly of Erdős-Rényi random graphs

  year unknowninfluential citation
• Shotgun Assembly of the Linial–Meshulam model

  year unknowninfluential citation