MCMC equilibrate recommendations for large graphs

I’m trying to perform sampling from the posterior distribution of a graph as outlined here: Inferring modular network structure — graph-tool 2.65 documentation

However, my graph is a somewhat large knn graph with 80 thousand vertices and k=50.

The example recommends using wait=1000, but it seems unreasonable for me. I’m running the code using the verbose=True option and the output is given below. It looks like there is usually some improvement after around 1100 iterations, but they are somewhat small. But this is after running the code for 28 hours so I do not expect it to finish anytime soon.

Is there some compromise in this position? Is it reasonable to set wait=10 (or even lower) in this scenario or would I not get a good result at all until it has not progressed for a thousand iterations?

I don’t have the intuition for why wait=1000 is expected. Sorry if this is explained somewhere else, but I want to understand what would be a standard way to approach this.

niter:     1  count:    0  breaks:  0  min_S: 1.9902840e+08  max_S: 2.1560877e+08  S: 1.9902840e+08  ΔS: -1.65804e+07  moves: 5701241 
niter:     2  count:    0  breaks:  0  min_S: 1.8910007e+08  max_S: 2.1560877e+08  S: 1.8910007e+08  ΔS: -9.92833e+06  moves: 2764201 
niter:     3  count:    0  breaks:  0  min_S: 1.8436646e+08  max_S: 2.1560877e+08  S: 1.8436646e+08  ΔS: -4.73361e+06  moves: 1116982 
niter:     4  count:    0  breaks:  0  min_S: 1.7815211e+08  max_S: 2.1560877e+08  S: 1.7815211e+08  ΔS: -6.21436e+06  moves: 1423478 
niter:     5  count:    0  breaks:  0  min_S: 1.7267725e+08  max_S: 2.1560877e+08  S: 1.7267725e+08  ΔS: -5.47486e+06  moves: 1112525 
niter:     6  count:    0  breaks:  0  min_S: 1.7075400e+08  max_S: 2.1560877e+08  S: 1.7075400e+08  ΔS: -1.92325e+06  moves: 232455 
niter:     7  count:    0  breaks:  0  min_S: 1.6914178e+08  max_S: 2.1560877e+08  S: 1.6914178e+08  ΔS: -1.61222e+06  moves: 221383 
niter:     8  count:    0  breaks:  0  min_S: 1.6700370e+08  max_S: 2.1560877e+08  S: 1.6700370e+08  ΔS: -2.13808e+06  moves: 322598 
niter:     9  count:    0  breaks:  0  min_S: 1.6549863e+08  max_S: 2.1560877e+08  S: 1.6549863e+08  ΔS: -1.50507e+06  moves: 189690 
niter:    10  count:    0  breaks:  0  min_S: 1.6418982e+08  max_S: 2.1560877e+08  S: 1.6418982e+08  ΔS: -1.30881e+06  moves: 156191 
niter:    11  count:    0  breaks:  0  min_S: 1.6251294e+08  max_S: 2.1560877e+08  S: 1.6251294e+08  ΔS: -1.67689e+06  moves: 299596 
niter:    12  count:    0  breaks:  0  min_S: 1.6095325e+08  max_S: 2.1560877e+08  S: 1.6095325e+08  ΔS: -1.55969e+06  moves: 157615 
niter:    13  count:    0  breaks:  0  min_S: 1.5935544e+08  max_S: 2.1560877e+08  S: 1.5935544e+08  ΔS: -1.59781e+06  moves: 438920 
niter:    14  count:    0  breaks:  0  min_S: 1.5800240e+08  max_S: 2.1560877e+08  S: 1.5800240e+08  ΔS: -1.35303e+06  moves: 177592 
niter:    15  count:    0  breaks:  0  min_S: 1.5566459e+08  max_S: 2.1560877e+08  S: 1.5566459e+08  ΔS: -2.33781e+06  moves: 714831 
niter:    16  count:    0  breaks:  0  min_S: 1.5464088e+08  max_S: 2.1560877e+08  S: 1.5464088e+08  ΔS: -1.02371e+06  moves: 64782 
niter:    17  count:    0  breaks:  0  min_S: 1.5316267e+08  max_S: 2.1560877e+08  S: 1.5316267e+08  ΔS: -1.47821e+06  moves: 128609 
niter:    18  count:    0  breaks:  0  min_S: 1.5157728e+08  max_S: 2.1560877e+08  S: 1.5157728e+08  ΔS: -1.58539e+06  moves: 263014 
niter:    19  count:    0  breaks:  0  min_S: 1.5039887e+08  max_S: 2.1560877e+08  S: 1.5039887e+08  ΔS: -1.17841e+06  moves: 253748 
niter:    20  count:    0  breaks:  0  min_S: 1.4864670e+08  max_S: 2.1560877e+08  S: 1.4864670e+08  ΔS: -1.75217e+06  moves: 249024 
niter:    21  count:    0  breaks:  0  min_S: 1.4699752e+08  max_S: 2.1560877e+08  S: 1.4699752e+08  ΔS: -1.64918e+06  moves: 264039 
niter:    22  count:    0  breaks:  0  min_S: 1.4617827e+08  max_S: 2.1560877e+08  S: 1.4617827e+08  ΔS:     -819253.  moves: 63270 
...
niter:  1161  count:    2  breaks:  0  min_S: 1.1101243e+08  max_S: 2.1560877e+08  S: 1.1101243e+08  ΔS:     -61.0937  moves: 25732 
niter:  1162  count:    0  breaks:  0  min_S: 1.1101238e+08  max_S: 2.1560877e+08  S: 1.1101238e+08  ΔS:     -41.7203  moves: 51686 
niter:  1163  count:    0  breaks:  0  min_S: 1.1101238e+08  max_S: 2.1560877e+08  S: 1.1101238e+08  ΔS:     -5.15840  moves: 48550 
niter:  1164  count:    0  breaks:  0  min_S: 1.1101221e+08  max_S: 2.1560877e+08  S: 1.1101221e+08  ΔS:     -165.699  moves: 23315 

You need to experiment, there’s no universally correct value. The mixing time of the distribution will depend heavily on the data.

If you want to understand how fast the chain is equilibrating, you’re better off plotting the description length over time and inspecting visually. This will give you an idea of how long you need to wait.

1 Like