Document Open Access Logo

Graph Reconstruction from Random Subgraphs

Authors Andrew McGregor, Rik Sengupta

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.96.pdf
  • Filesize: 0.73 MB
  • 18 pages

Document Identifiers

Author Details

Andrew McGregor
  • University of Massachusetts, Amherst, MA, USA
Rik Sengupta
  • University of Massachusetts, Amherst, MA, USA

Funding

  • McGregor, Andrew: Work supported in part by NSF CCF-1934846, CCF-1908849, and CCF-1637536.

Acknowledgements

We thank the reviewers for numerous helpful suggestions.

Cite AsGet BibTex

Andrew McGregor and Rik Sengupta. Graph Reconstruction from Random Subgraphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 96:1-96:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ICALP.2022.96

Abstract

We consider the problem of reconstructing a graph G in two natural sampling models: 1) each sample corresponds to a random induced subgraph and 2) for a fixed adjacency matrix A_G for G, each sample corresponds to a random principal submatrix (i.e., a submatrix formed by deleting the same set of rows and columns) of A_G. We refer to these models as the "unordered" and "ordered" models respectively. The two models are motivated by work on the reconstruction conjecture in combinatorics and trace reconstruction in theoretical computer science. Despite the superficial similarities between the models, we show that the sample complexity of reconstruction can be exponentially different. Our main results are as follows: - In the unordered model, we show that almost all graphs can be reconstructed with Θ(p^{-2} log n) samples if each node is included in the random subgraph with any constant probability p; this is optimal. We show our upper bound extends to smaller values of p as well. In contrast, for arbitrary graphs, we show that exp(Ω(n)) samples are required for reconstruction even for 2-regular graphs. One of the key technical steps in the first result is showing that, with high probability, any subgraph isomorphism in a random graph has at most O(log n) non-fixed points. - In the ordered model, we show that any graph with constant arboricity or degeneracy (i.e., every induced subgraph has constant average degree) can be reconstructed with exp(Õ(n^{1/3})) samples and that arbitrary graphs can be reconstructed with exp(Õ(n^{1/2})) samples. The results about almost all graphs in the first model carry over to the second. One of the key technical steps in the first result is showing that reconstruction of low degeneracy graphs can be reduced to learning a small number of moments of sets of the form {i-j: j < i,(i,j) ∈ E} and {j-i: i < j,(i,j) ∈ E} where G = ([n],E) is the unknown graph.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Probability and statistics
Keywords
  • graph reconstruction
  • sample complexity
  • deletion channel

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Frank Ban, Xi Chen, Adam Freilich, Rocco A. Servedio, and Sandip Sinha. Beyond trace reconstruction: Population recovery from the deletion channel. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 745-768, 2019. URL: https://doi.org/10.1109/FOCS.2019.00050.
  2. Tugkan Batu, Sampath Kannan, Sanjeev Khanna, and Andrew McGregor. Reconstructing strings from random traces. In Symposium on Discrete Algorithms, 2004. Google Scholar
  3. Bela Bollobas. Almost every graph has reconstruction number three. Journal of Graph Theory, 14(1):1-4, 1990. Google Scholar
  4. Tatiana Brailovskaya and Miklós Z. Rácz. Tree trace reconstruction using subtraces. CoRR, abs/2102.01541, 2021. URL: http://arxiv.org/abs/2102.01541.
  5. Joshua Brakensiek, Ray Li, and Bruce Spang. Coded trace reconstruction in a constant number of traces. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 482-493, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00052.
  6. Zachary Chase. New lower bounds for trace reconstruction. Annales de l'Institut Henri Poincaré, Probabilités et Statistiques, 57(2):627-643, 2021. URL: https://doi.org/10.1214/20-AIHP1089.
  7. Zachary Chase. Separating words and trace reconstruction. In STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, June 2021, pages 21-31, 2021. Google Scholar
  8. Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, and Sandip Sinha. Polynomial-time trace reconstruction in the smoothed complexity model. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 54-73. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.5.
  9. Mahdi Cheraghchi, Ryan Gabrys, Olgica Milenkovic, and Joao Ribeiro. Coded trace reconstruction. IEEE Transactions on Information Theory, PP:1-1, May 2020. URL: https://doi.org/10.1109/TIT.2020.2996377.
  10. Sami Davies, Miklos Z. Racz, and Cyrus Rashtchian. Reconstructing trees from traces. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirty-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 961-978, Phoenix, USA, 25-28 June 2019. PMLR. URL: http://proceedings.mlr.press/v99/davies19a.html.
  11. Anindya De, Ryan O'Donnell, and Rocco A. Servedio. Optimal mean-based algorithms for trace reconstruction. In Symposium on Theory of Computing, 2017. Google Scholar
  12. Simon Foucart and Holger Rauhut. A Mathematical Introduction to Compressive Sensing. Birkhäuser, 2013. URL: https://doi.org/10.1007/978-0-8176-4948-7.
  13. Lisa Hartung, Nina Holden, and Yuval Peres. Trace reconstruction with varying deletion probabilities. In Workshop on Analytic Algorithmics and Combinatorics, 2018. Google Scholar
  14. Nina Holden and Russell Lyons. Lower bounds for trace reconstruction. The Annals of Applied Probability, 30(2):503-525, 2020. URL: https://doi.org/10.1214/19-AAP1506.
  15. Nina Holden, Robin Pemantle, and Yuval Peres. Subpolynomial trace reconstruction for random strings and arbitrary deletion probability. In Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018., pages 1799-1840, 2018. Google Scholar
  16. Thomas Holenstein, Michael Mitzenmacher, Rina Panigrahy, and Udi Wieder. Trace reconstruction with constant deletion probability and related results. In Symposium on Discrete Algorithms, 2008. Google Scholar
  17. Paul J. Kelly. A congruence theorem for trees. Pacific Journal of Mathematics, 7(1):961-968, 1957. URL: https://doi.org/pjm/1103043674.
  18. Géza Kós, Péter Ligeti, and Péter Sziklai. Reconstruction of matrices from submatrices. Mathematics of Computation, 2009. URL: https://doi.org/10.1090/S0025-5718-09-02210-8.
  19. I. Krasikov and Y. Roditty. On a reconstruction problem for sequences. Journal of Combinatorial Theory, Series A, 1997. Google Scholar
  20. Akshay Krishnamurthy, Arya Mazumdar, Andrew McGregor, and Soumyabrata Pal. Trace reconstruction: Generalized and parameterized. IEEE Trans. Inf. Theory, 67(6):3233-3250, 2021. URL: https://doi.org/10.1109/TIT.2021.3066010.
  21. Thomas Maranzatto and Lev Reyzin. Reconstructing arbitrary trees from traces in the tree edit distance model. CoRR, abs/2102.03173, 2021. URL: http://arxiv.org/abs/2102.03173.
  22. Andrew McGregor, Eric Price, and Sofya Vorotnikova. Trace reconstruction revisited. In European Symposium on Algorithms, 2014. Google Scholar
  23. Elchanan Mossel and Nathan Ross. Shotgun assembly of labeled graphs. IEEE Transactions on Network Science and Engineering, 6(2):145-157, 2019. URL: https://doi.org/10.1109/TNSE.2017.2776913.
  24. Vladimír Müller. Probabilistic reconstruction from subgraphs. Commentationes Mathematicae Universitatis Carolinae, 017(4):709-719, 1976. URL: http://eudml.org/doc/16787.
  25. Shyam Narayanan. Improved algorithms for population recovery from the deletion channel. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 1259-1278. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.77.
  26. Shyam Narayanan and Michael Ren. Circular Trace Reconstruction. In James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), volume 185 of Leibniz International Proceedings in Informatics (LIPIcs), pages 18:1-18:18, Dagstuhl, Germany, 2021. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ITCS.2021.18.
  27. Fedor Nazarov and Yuval Peres. Trace reconstruction with exp(O(n^1/3) samples. In Symposium on Theory of Computing, 2017. Google Scholar
  28. Jaroslav Nesetril. Graph theory and combinatorics. Fields Institute Summer Thematic Program on the Mathematics of Constraint Satisfaction, 2011. Google Scholar
  29. Yuval Peres and Alex Zhai. Average-case reconstruction for the deletion channel: Subpolynomially many traces suffice. In Symposium on Foundations of Computer Science, 2017. Google Scholar
  30. Hannah Spinoza and Douglas West. Reconstruction from the deck of k‐vertex induced subgraphs. Journal of Graph Theory, 90(4):497-522, 2019. Google Scholar
  31. S. M. Ulam. A collection of mathematical problems. Interscience Tracts in Pure and Applied Mathematics, no. 8. Interscience Publishers, New York-London, 1960. Google Scholar
  32. Krishnamurthy Viswanathan and Ram Swaminathan. Improved string reconstruction over insertion-deletion channels. In Symposium on Discrete Algorithms, 2008. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact