Metastable mixing of Markov chains: efficiently sampling low temperature exponential random graphs. (English) Zbl 1536.60063

Bresler, Guy; Nagaraj, Dheeraj; Nichani, Eshaan

Ann. Appl. Probab. 34, No. 1A, 517-554 (2024).

Summary: In this paper, we consider the problem of sampling from the low-temperature exponential random graph model (ERGM). The usual approach is via Markov chain Monte Carlo, but Bhamidi et al. showed that any local Markov chain suffers from an exponentially large mixing time due to metastable states. We instead consider metastable mixing, a notion of approximate mixing relative to the stationary distribution, for which it turns out to suffice to mix only within a collection of metastable states. We show that the Glauber dynamics for the ERGM at any temperature – except at a lower-dimensional critical set of parameters – when initialized at \({G}(n, p)\) for the right choice of \(p\) has a metastable mixing time of \(O(n^2 \log n)\) to within total variation distance \(\exp(- \Omega(n))\).

MSC:

60J10	Markov chains (discrete-time Markov processes on discrete state spaces)
68Q87	Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
05C80	Random graphs (graph-theoretic aspects)

Keywords:

exponential random graphs; efficient sampling; Markov chain; Glauber dynamics

References:

[1]	BHAMIDI, S., BRESLER, G. and SLY, A. (2011). Mixing time of exponential random graphs. Ann. Appl. Probab. 21 2146-2170. Digital Object Identifier: 10.1214/10-AAP740 Google Scholar: Lookup Link MathSciNet: MR2895412 · Zbl 1238.60011 · doi:10.1214/10-AAP740
[2]	BORGS, C., CHAYES, J., LOVÁSZ, L., SÓS, V. T., SZEGEDY, B. and VESZTERGOMBI, K. (2006). Graph limits and parameter testing. In STOC’06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing 261-270. ACM, New York. Digital Object Identifier: 10.1145/1132516.1132556 Google Scholar: Lookup Link MathSciNet: MR2277152 · Zbl 1301.68199 · doi:10.1145/1132516.1132556
[3]	BRESLER, G. and NAGARAJ, D. (2018). Optimal single sample tests for structured versus unstructured network data. In Conference on Learning Theory 1657-1690. PMLR.
[4]	BURDA, Z., JURKIEWICZ, J. and KRZYWICKI, A. (2004). Network transitivity and matrix models. Phys. Rev. E 69 026106.
[5]	CHATTERJEE, S. (2007). Stein’s method for concentration inequalities. Probab. Theory Related Fields 138 305-321. Digital Object Identifier: 10.1007/s00440-006-0029-y Google Scholar: Lookup Link MathSciNet: MR2288072 · Zbl 1116.60056 · doi:10.1007/s00440-006-0029-y
[6]	CHATTERJEE, S. and DIACONIS, P. (2013). Estimating and understanding exponential random graph models. Ann. Statist. 41 2428-2461. Digital Object Identifier: 10.1214/13-AOS1155 Google Scholar: Lookup Link MathSciNet: MR3127871 · Zbl 1293.62046 · doi:10.1214/13-AOS1155
[7]	ELDAN, R. and GROSS, R. (2018). Exponential random graphs behave like mixtures of stochastic block models. Ann. Appl. Probab. 28 3698-3735. Digital Object Identifier: 10.1214/18-AAP1402 Google Scholar: Lookup Link MathSciNet: MR3861824 · Zbl 1407.62226 · doi:10.1214/18-AAP1402
[8]	Fienberg, S. E. (2010). Introduction to papers on the modeling and analysis of network data. Ann. Appl. Stat. 4 1-4. Digital Object Identifier: 10.1214/10-AOAS346 Google Scholar: Lookup Link MathSciNet: MR2758081 · doi:10.1214/10-AOAS346
[9]	FIENBERG, S. E. (2010). Introduction to papers on the modeling and analysis of network data—II. Ann. Appl. Stat. 4 533-534. Digital Object Identifier: 10.1214/10-AOAS365 Google Scholar: Lookup Link MathSciNet: MR2744531 · doi:10.1214/10-AOAS365
[10]	Frank, O. and Strauss, D. (1986). Markov graphs. J. Amer. Statist. Assoc. 81 832-842. MathSciNet: MR0860518 · Zbl 0607.05057
[11]	GANGULY, S. and NAM, K. (2019). Sub-critical Exponential random graphs: Concentration of measure and some applications. Trans. Amer. Math. Soc. To Appear. Preprint arXiv:1909.11080.
[12]	GELMAN, A. and MENG, X.-L. (1998). Simulating normalizing constants: From importance sampling to bridge sampling to path sampling. Statist. Sci. 13 163-185. Digital Object Identifier: 10.1214/ss/1028905934 Google Scholar: Lookup Link MathSciNet: MR1647507 · Zbl 0966.65004 · doi:10.1214/ss/1028905934
[13]	GEYER, C. J. and THOMPSON, E. A. (1992). Constrained Monte Carlo maximum likelihood for dependent data. J. Roy. Statist. Soc. Ser. B 54 657-699. MathSciNet: MR1185217
[14]	GHEISSARI, R. and SINCLAIR, A. (2022). Low-temperature Ising dynamics with random initializations. In STOC’22—Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing 1445-1458. ACM, New York. MathSciNet: MR4490091 · Zbl 07774429
[15]	GUO, H. and JERRUM, M. (2017). Random cluster dynamics for the Ising model is rapidly mixing. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms 1818-1827. SIAM, Philadelphia, PA. Digital Object Identifier: 10.1137/1.9781611974782.118 Google Scholar: Lookup Link MathSciNet: MR3627847 · Zbl 1419.82013 · doi:10.1137/1.9781611974782.118
[16]	HOLLAND, P. W. and LEINHARDT, S. (1981). An exponential family of probability distributions for directed graphs. J. Amer. Statist. Assoc. 76 33-65. MathSciNet: MR0608176 · Zbl 0457.62090
[17]	JERRUM, M. and SINCLAIR, A. (1993). Polynomial-time approximation algorithms for the Ising model. SIAM J. Comput. 22 1087-1116. Digital Object Identifier: 10.1137/0222066 Google Scholar: Lookup Link MathSciNet: MR1237164 · Zbl 0782.05076 · doi:10.1137/0222066
[18]	KOU, S. C., ZHOU, Q. and WONG, W. H. (2006). Equi-energy sampler with applications in statistical inference and statistical mechanics. Ann. Statist. 34 1581-1652. Digital Object Identifier: 10.1214/009053606000000515 Google Scholar: Lookup Link MathSciNet: MR2283711 · Zbl 1246.82054 · doi:10.1214/009053606000000515
[19]	LEVIN, D. A., LUCZAK, M. J. and PERES, Y. (2010). Glauber dynamics for the mean-field Ising model: Cut-off, critical power law, and metastability. Probab. Theory Related Fields 146 223-265. Digital Object Identifier: 10.1007/s00440-008-0189-z Google Scholar: Lookup Link MathSciNet: MR2550363 · Zbl 1187.82076 · doi:10.1007/s00440-008-0189-z
[20]	LEVIN, D. A. and PERES, Y. (2017). Markov Chains and Mixing Times, 2nd ed. Amer. Math. Soc., Providence, RI. Digital Object Identifier: 10.1090/mbk/107 Google Scholar: Lookup Link MathSciNet: MR3726904 · Zbl 1390.60001 · doi:10.1090/mbk/107
[21]	LINDSEY, M., WEARE, J. and ZHANG, A. (2022). Ensemble Markov chain Monte Carlo with teleporting walkers. SIAM/ASA J. Uncertain. Quantificat. 10 860-885. Digital Object Identifier: 10.1137/21M1425062 Google Scholar: Lookup Link MathSciNet: MR4535507 · Zbl 1493.65013 · doi:10.1137/21M1425062
[22]	LUBETZKY, E. and SLY, A. (2021). Fast initial conditions for Glauber dynamics. Probab. Theory Related Fields 181 647-667. Digital Object Identifier: 10.1007/s00440-020-01015-3 Google Scholar: Lookup Link MathSciNet: MR4341083 · Zbl 1477.60112 · doi:10.1007/s00440-020-01015-3
[23]	MUKHERJEE, S. and XU, Y. (2023). Statistics of the two star ERGM. Bernoulli 29 24-51. Digital Object Identifier: 10.3150/21-bej1448 Google Scholar: Lookup Link MathSciNet: MR4497238 · Zbl 07634383 · doi:10.3150/21-bej1448
[24]	PARK, J. and NEWMAN, M. E. J. (2004). Solution of the two-star model of a network. Phys. Rev. E (3) 70 066146, 5. Digital Object Identifier: 10.1103/PhysRevE.70.066146 Google Scholar: Lookup Link MathSciNet: MR2133810 · doi:10.1103/PhysRevE.70.066146
[25]	PARK, J. and NEWMAN, M. E. J. (2005). Solution for the properties of a clustered network. Phys. Rev. E 72 026136.
[26]	RADIN, C. and YIN, M. (2013). Phase transitions in exponential random graphs. Ann. Appl. Probab. 23 2458-2471. Digital Object Identifier: 10.1214/12-AAP907 Google Scholar: Lookup Link MathSciNet: MR3127941 · Zbl 1278.05225 · doi:10.1214/12-AAP907
[27]	REINERT, G. and ROSS, N. (2019). Approximating stationary distributions of fast mixing Glauber dynamics, with applications to exponential random graphs. Ann. Appl. Probab. 29 3201-3229. Digital Object Identifier: 10.1214/19-AAP1478 Google Scholar: Lookup Link MathSciNet: MR4019886 · Zbl 1447.60010 · doi:10.1214/19-AAP1478
[28]	SINCLAIR, A. and JERRUM, M. (1989). Approximate counting, uniform generation and rapidly mixing Markov chains. Inform. and Comput. 82 93-133. Digital Object Identifier: 10.1016/0890-5401(89)90067-9 Google Scholar: Lookup Link MathSciNet: MR1003059 · Zbl 0668.05060 · doi:10.1016/0890-5401(89)90067-9
[29]	SWENDSEN, R. H. and WANG, J.-S. (1987). Nonuniversal critical dynamics in Monte Carlo simulations. Phys. Rev. Lett. 58 86.
[30]	ULLRICH, M. (2014). Swendsen-Wang is faster than single-bond dynamics. SIAM J. Discrete Math. 28 37-48. Digital Object Identifier: 10.1137/120864003 Google Scholar: Lookup Link MathSciNet: MR3148642 · Zbl 1294.60120 · doi:10.1137/120864003
[31]	WASSERMAN, S. and FAUST, K. (1994). Social network analysis: Methods and applications.
[32]	YIN, M. and ZHU, L. (2017). Asymptotics for sparse exponential random graph models. Braz. J. Probab. Stat. 31 394-412. Digital Object Identifier: 10.1214/16-BJPS319 Google Scholar: Lookup Link MathSciNet: MR3635912 · Zbl 1365.05264 · doi:10.1214/16-BJPS319