Document Open Access Logo

Fast and Perfect Sampling of Subgraphs and Polymer Systems

Authors Antonio Blanca, Sarah Cannon, Will Perkins

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2022.4.pdf
  • Filesize: 0.68 MB
  • 18 pages

Document Identifiers

Author Details

Antonio Blanca
  • Department of Computer Science and Engineering, Pennsylvania State University, University Park, PA, USA
Sarah Cannon
  • Department of Mathematical Sciences, Claremont McKenna College, CA, USA
Will Perkins
  • Department of Computer Science, Georgia Institute of Technology, Atlanta, GA, USA

Funding

  • Cannon, Sarah: Supported in part by NSF grants DMS-1803325 and CCF-2104795.
  • Perkins, Will: Supported in part by NSF grant DMS-1847451.

Acknowledgements

This work was carried out as part of the AIM SQuaRE workshop "Connections between computational and physical phase transitions." We thank Tyler Helmuth, Alexandre Stauffer, and Izabella Stuhl for many helpful conversations.

Cite AsGet BibTex

Antonio Blanca, Sarah Cannon, and Will Perkins. Fast and Perfect Sampling of Subgraphs and Polymer Systems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 4:1-4:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.4

Abstract

We give an efficient perfect sampling algorithm for weighted, connected induced subgraphs (or graphlets) of rooted, bounded degree graphs. Our algorithm utilizes a vertex-percolation process with a carefully chosen rejection filter and works under a percolation subcriticality condition. We show that this condition is optimal in the sense that the task of (approximately) sampling weighted rooted graphlets becomes impossible in finite expected time for infinite graphs and intractable for finite graphs when the condition does not hold. We apply our sampling algorithm as a subroutine to give near linear-time perfect sampling algorithms for polymer models and weighted non-rooted graphlets in finite graphs, two widely studied yet very different problems. This new perfect sampling algorithm for polymer models gives improved sampling algorithms for spin systems at low temperatures on expander graphs and unbalanced bipartite graphs, among other applications.

Subject Classification

ACM Subject Classification
  • Theory of computation → Randomness, geometry and discrete structures
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Random walks and Markov chains
Keywords
  • Random Sampling
  • perfect sampling
  • graphlets
  • polymer models
  • spin systems
  • percolation

Metrics

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

Related Versions

References

  1. Matteo Agostini, Marco Bressan, and Shahrzad Haddadan. Mixing time bounds for graphlet random walks. Information Processing Letters, 152:105851, 2019. Google Scholar
  2. Konrad Anand and Mark Jerrum. Perfect sampling in infinite spin systems via strong spatial mixing. arXiv preprint, 2021. URL: http://arxiv.org/abs/2106.15992.
  3. Nima Anari, Kuikui Liu, and Shayan Oveis Gharan. Spectral independence in high-dimensional expanders and applications to the hardcore model. SIAM Journal on Computing: Special Section, FOCS 2020, pages FOCS20:1-FOCS20:37, 2022. Google Scholar
  4. Kim Baskerville, Peter Grassberger, and Maya Paczuski. Graph animals, subgraph sampling, and motif search in large networks. Physical Review E, 76(3):036107, 2007. Google Scholar
  5. Mansurul A Bhuiyan, Mahmudur Rahman, Mahmuda Rahman, and Mohammad Al Hasan. Guise: Uniform sampling of graphlets for large graph analysis. In 2012 IEEE 12th International Conference on Data Mining, pages 91-100. IEEE, 2012. Google Scholar
  6. Antonio Blanca, Sarah Cannon, and Will Perkins. Fast and perfect sampling of subgraphs and polymer systems. arXiv preprint, 2022. URL: http://arxiv.org/abs/2202.05907.
  7. Christian Borgs, Jennifer Chayes, Tyler Helmuth, Will Perkins, and Prasad Tetali. Efficient sampling and counting algorithms for the Potts model on ℤ^d at all temperatures. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 738-751, 2020. Google Scholar
  8. Christian Borgs, Jennifer Chayes, Jeff Kahn, and László Lovász. Left and right convergence of graphs with bounded degree. Random Structures & Algorithms, 42(1):1-28, 2013. Google Scholar
  9. Marco Bressan. Efficient and near-optimal algorithms for sampling connected subgraphs. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1132-1143, 2021. Google Scholar
  10. Marco Bressan, Flavio Chierichetti, Ravi Kumar, Stefano Leucci, and Alessandro Panconesi. Counting graphlets: Space vs time. In Proceedings of the tenth ACM International Conference on Web Search and Data Mining (WSDM), pages 557-566, 2017. Google Scholar
  11. Marco Bressan, Flavio Chierichetti, Ravi Kumar, Stefano Leucci, and Alessandro Panconesi. Motif counting beyond five nodes. ACM Transactions on Knowledge Discovery from Data (TKDD), 12(4):1-25, 2018. Google Scholar
  12. Marco Bressan, Stefano Leucci, and Alessandro Panconesi. Faster motif counting via succinct color coding and adaptive sampling. ACM Transactions on Knowledge Discovery from Data (TKDD), 15(6):1-27, 2021. Google Scholar
  13. Sarah Cannon and Will Perkins. Counting independent sets in unbalanced bipartite graphs. In Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1456-1466, 2020. Google Scholar
  14. Charlie Carlson, Ewan Davies, and Alexandra Kolla. Efficient algorithms for the Potts model on small-set expanders. arXiv preprint, 2020. URL: http://arxiv.org/abs/2003.01154.
  15. Xiaowei Chen, Yongkun Li, Pinghui Wang, and John CS Lui. A general framework for estimating graphlet statistics via random walk. Proceedings of the VLDB Endowment, 10(3), 2016. Google Scholar
  16. Zongchen Chen, Andreas Galanis, Leslie A Goldberg, Will Perkins, James Stewart, and Eric Vigoda. Fast algorithms at low temperatures via Markov chains. Random Structures & Algorithms, 58(2):294-321, 2021. Google Scholar
  17. Zongchen Chen, Andreas Galanis, Daniel Štefankovič, and Eric Vigoda. Sampling colorings and independent sets of random regular bipartite graphs in the non-uniqueness region. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2198-2207. SIAM, 2022. Google Scholar
  18. Zongchen Chen, Kuikui Liu, and Eric Vigoda. Rapid mixing of Glauber dynamics up to uniqueness via contraction. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1307-1318. IEEE, 2020. Google Scholar
  19. Zongchen Chen, Kuikui Liu, and Eric Vigoda. Optimal mixing of glauber dynamics: Entropy factorization via high-dimensional expansion. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1537-1550, 2021. Google Scholar
  20. Matthew Coulson, Ewan Davies, Alexandra Kolla, Viresh Patel, and Guus Regts. Statistical physics approaches to unique games. In 35th Computational Complexity Conference (CCC), 2020. Google Scholar
  21. Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill, and Mark Jerrum. The relative complexity of approximate counting problems. Algorithmica, 38(3):471-500, 2004. Google Scholar
  22. Sacha Friedli and Yvan Velenik. Statistical mechanics of lattice systems: a concrete mathematical introduction. Cambridge University Press, 2017. Google Scholar
  23. Tobias Friedrich, Andreas Göbel, Martin S Krejca, and Marcus Pappik. Polymer dynamics via cliques: New conditions for approximations. arXiv preprint, 2020. URL: http://arxiv.org/abs/2007.08293.
  24. Andreas Galanis, Leslie Ann Goldberg, and James Stewart. Fast algorithms for general spin systems on bipartite expanders. ACM Transactions on Computation Theory (TOCT), 13(4):1-18, 2021. Google Scholar
  25. Andreas Galanis, Leslie Ann Goldberg, and James Stewart. Fast mixing via polymers for random graphs with unbounded degree. Information and Computation, 285:104894, 2022. Google Scholar
  26. Andreas Galanis, Daniel Štefankovič, and Eric Vigoda. Inapproximability of the partition function for the antiferromagnetic ising and hard-core models. Combinatorics, Probability and Computing, 25(4):500-559, 2016. Google Scholar
  27. Oded Goldreich and Dana Ron. Property testing in bounded degree graphs. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing (STOC), pages 406-415, 1997. Google Scholar
  28. Joshua A Grochow and Manolis Kellis. Network motif discovery using subgraph enumeration and symmetry-breaking. In Annual International Conference on Research in Computational Molecular Biology, pages 92-106. Springer, 2007. Google Scholar
  29. Christian Gruber and Hervé Kunz. General properties of polymer systems. Communications in Mathematical Physics, 22(2):133-161, 1971. Google Scholar
  30. Olle Haggstrom and Karin Nelander. On exact simulation of Markov random fields using coupling from the past. Scandinavian Journal of Statistics, 26(3):395-411, 1999. Google Scholar
  31. Tyler Helmuth, Matthew Jenssen, and Will Perkins. Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs. Annales de l’Institut Henri Poincaré B. To appear, 2022. Google Scholar
  32. Tyler Helmuth, Will Perkins, and Guus Regts. Algorithmic Pirogov-Sinai theory. Probability Theory and Related Fields, 176(3):851-895, 2020. Google Scholar
  33. Mark Huber. Perfect sampling using bounding chains. The Annals of Applied Probability, 14(2):734-753, 2004. Google Scholar
  34. Svante Janson, Andrzej Rucinski, and Tomasz Luczak. Random graphs. John Wiley & Sons, 2011. Google Scholar
  35. Matthew Jenssen, Peter Keevash, and Will Perkins. Algorithms for #BIS-hard problems on expander graphs. SIAM Journal on Computing, 49(4):681-710, 2020. Google Scholar
  36. Matthew Jenssen, Aditya Potukuchi, and Will Perkins. Approximately counting independent sets in bipartite graphs via graph containers. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 499-516. SIAM, 2022. Google Scholar
  37. Madhav Jha, C Seshadhri, and Ali Pinar. Path sampling: A fast and provable method for estimating 4-vertex subgraph counts. In Proceedings of the 24th International Conference on World Wide Web (WWW), pages 495-505, 2015. Google Scholar
  38. Nadav Kashtan, Shalev Itzkovitz, Ron Milo, and Uri Alon. Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs. Bioinformatics, 20(11):1746-1758, 2004. Google Scholar
  39. Roman Koteckỳ and David Preiss. Cluster expansion for abstract polymer models. Communications in Mathematical Physics, 103(3):491-498, 1986. Google Scholar
  40. Chao Liao, Jiabao Lin, Pinyan Lu, and Zhenyu Mao. Counting independent sets and colorings on random regular bipartite graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. Google Scholar
  41. Xuesong Lu and Stéphane Bressan. Sampling connected induced subgraphs uniformly at random. In International Conference on Scientific and Statistical Database Management, pages 195-212. Springer, 2012. Google Scholar
  42. Ryuta Matsuno and Aristides Gionis. Improved mixing time for k-subgraph sampling. In Proceedings of the 2020 SIAM International Conference on Data Mining, pages 568-576. SIAM, 2020. Google Scholar
  43. Kirill Paramonov, Dmitry Shemetov, and James Sharpnack. Estimating graphlet statistics via lifting. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 587-595, 2019. Google Scholar
  44. James Gary Propp and David Bruce Wilson. Exact sampling with coupled Markov chains and applications to statistical mechanics. Random Structures & Algorithms, 9(1-2):223-252, 1996. Google Scholar
  45. Andrew Read-McFarland and Daniel Štefankovič. The hardness of sampling connected subgraphs. In Latin American Symposium on Theoretical Informatics, pages 464-475. Springer, 2021. Google Scholar
  46. Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt. Efficient graphlet kernels for large graph comparison. In Artificial intelligence and statistics, pages 488-495. PMLR, 2009. Google Scholar
  47. Allan Sly. Computational transition at the uniqueness threshold. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS), pages 287-296. IEEE, 2010. Google Scholar
  48. Allan Sly and Nike Sun. The computational hardness of counting in two-spin models on d-regular graphs. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 361-369. IEEE, 2012. Google Scholar
  49. Dror Weitz. Counting independent sets up to the tree threshold. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 140-149, 2006. 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