Spectral partitioning for $k$-block averaging kernels of finite Markov chains
Michael C. H. Choi, Youjia Wang
stat.ML, cs.IT, cs.LG, math.OC, math.PR, stat.CO
2026-08-21
NUS rounds P² bottom eigenfunctions into Gibbs blocks for MCMC. On a 40-state dumbbell, worst-case TV at t=10 falls from 0.652 to 1.01e-11; BVS at T=5000 cuts ePIP 10.4× vs P.
Local MCMC updates stall on bottlenecks and on tightly correlated coordinates. One fix is to cut the state space into k blocks, resample from the stationary conditional inside the current block, then compose that update with the baseline kernel P, or mix the two as (P+GO)/2. The block-conditional update is a Gibbs kernel GO. Earlier papers by Choi, Lim, and Wang already showed that a good partition can kill stubborn modes. The combinatorial problem is how to pick the partition: the number of set partitions is a Bell number, so brute force is out.
Lim and Choi (2026) gave combinatorial approximations for the two-block case. This paper turns partition search into a matrix objective with a spectral relaxation, then rounds the bottom eigenfunctions. The algorithms cover two-block threshold sweeps, k-block weighted k-means, additive mixtures, and multi-horizon rescoring.
F(O) is the squared π-weighted Frobenius distance between the composed kernel GO P and the stationary kernel Π. Three identities say the same thing: a matrix norm, the complement of a multiway normalized cut of P², and the Pearson χ² mutual information between the initial block label Z and the state X1 after one transition. Smaller F means one step forgets the starting block more thoroughly. Minimizing F is maximizing two-step cross-block flow of P².
That is the reverse of classical spectral clustering. Shi-Malik and Ng-Jordan-Weiss use the low-frequency modes of I-P² (the largest nonconstant eigenfunctions of P²) to find sticky communities with small boundary. Here the smallest nonconstant eigenfunctions of P² are used on purpose, to cut where normalized two-step flow is large.
Three algorithmic settings.
Two blocks: sort states by the bottom eigenfunction of P² and sweep thresholds, scoring each cut by the original F. The sweep solves the associated one-dimensional weighted two-means rounding exactly. If the eigenfunction takes only two values, the cut meets the spectral lower bound and is optimal.
k blocks: embed states with the bottom k-1 eigenfunctions of P², run π-weighted k-means to generate candidates, then rescore those candidates by F. The rounding error δ is both the weighted k-means distortion of the embedding and the sum of squared sines of principal angles between the spectral subspace and the block-constant subspace. A spectral sandwich converts δ into a suboptimality bound on F: larger eigengap and narrower spectral width make rounding safer.
Additive mixture AO=(P+GO)/2: the objective becomes H(O)=||AO-Π||²{F,π}. The relaxation uses the algebraically smallest eigenfunctions of P, so negative eigenvalues keep their sign. P² folds a large positive eigenvalue and a large negative one into the same bin; the mixture objective does not.
Finite-horizon and discounted infinite-horizon variants reuse the P² embedding and only change the final score. With discount γ=0.9 the mean geometric horizon is 10 steps. The lag-t quantity F(P^t, O) averages inside the block once, then runs the original chain for t steps. That is not the same as iterating GO P t times.
The method only lands if the block-conditionals can be sampled. A beautiful partition with an intractable GO is not a kernel you can run.
Three exactly enumerable experiments. Code is at mchchoi/spectral-partitioning. Multiway runs use 80 weighted k-means++ starts by default and pick the best original-objective value in the candidate pool; that is not a claim of global discrete optimality.
Controlled-spectrum dumbbell: two 20-cycles, 40 states. Bridge weight ε sets a slow positive mode; laziness α sets a large negative eigenvalue. At α=0.08, ε=0.03 one has λ1=-0.84 and λ{n-1}=0.998748. Worst-case total variation at repeated-kernel time 10:
| kernel | d^{wc}{TV}(K,10) |
| original P | 0.652 |
| two-block GO P | 1.01×10^{-11} |
| four-block F-selected GO P | 6.55×10^{-7} |
| additive mixture AO | 0.129 |
| multi-horizon GO P | 6.55×10^{-7} |
Across a 48-point (α,ε) grid, the largest weighted disagreement between F-selected and H-selected partitions is 0.725; between F and Fγ^∞ it is 0.550. The most horizon-sensitive cell is α=0.16, ε=0.006: multi-horizon rescoring drops Fγ^∞ from 3.4202 to 1.5517 and lag-10 F from 0.3002 to 0.05818. Repeated-kernel TV at time 10 also falls from 1.10×10^{-6} to 3.61×10^{-8} in that cell. The last improvement is empirical; the objective does not imply it.
Exact Curie-Weiss Ising, d=8, 256 states, k=4, heat-bath dynamics. At (β,h)=(1.5,0) versus magnetization bins and coordinate blocks:
| objective | spectral sweep | magnetization bins | coordinate blocks |
| F | 0.7454 | 2.4185 | 2.3616 |
| H | 19.4566 | 20.1889 | 20.1833 |
| Fγ^∞ | 1.7356 | 12.9934 | 11.4684 |
F is 69.2% below the magnetization baseline; Fγ^∞ is 86.6% below. The raw H reduction is only 3.63% because H contains a large partition-independent constant. Worst-case TV at t=10: 0.5277 for P, about 2.46×10^{-4} for four-block GO P, 0.0820 for the additive mixture. The selected blocks are badly unbalanced: the largest block has stationary mass about 0.96, the smallest about 0.012. Averaging kernels are supposed to kill persistent modes, not preserve communities.
Bayesian variable selection: 12 binary inclusion indicators, 4096 models, six highly correlated proxy pairs (ρ=0.995). A single-toggle Metropolis chain can move between 10 and 01 only through the disfavoured 00 or 11 patterns. Unconstrained rounding collapses block masses to about (1.00, 7.3×10^{-29}, 1.1×10^{-33}, 2.4×10^{-39}), so the Gibbs update is nearly a direct posterior draw. After imposing 0.15≤π(Oi)≤0.35, the balanced multi-horizon kernel at T=5000 reduces ePIP, epair, esize, and eBMA by factors 10.4, 8.4, 2.5, and 9.5 versus P. A mass-matched random partition, rescored by F, already sits close to the spectral outputs. Most of the gain in this experiment comes from a nondegenerate conditional-averaging step with controlled block masses; spectral candidate generation adds a modest extra.
For finite-state MCMC, eigenfunctions stop being only a diagnostic and become coordinates for building a new, simulable kernel. If block-conditional Gibbs updates are already available (enumerated variable selection, small-lattice Ising, group-averaged chains with tractable orbits), this is a partition tuner with approximation bounds.
For people who ship spectral clustering, the orientation flip is the usable takeaway: sticky communities and fast-forgetting averaging blocks want different ends of the spectrum. Additive mixtures keep signed modes; P²-based F treats a large negative eigenvalue like a large positive one. That distinction is real on lazy walks that still carry a near-minus-one mode.
This is not a drop-in accelerator. GO must be sampleable. All three experiments are exact small chains. Unconstrained rounding can collapse to an oracle posterior draw. On the variable-selection benchmark, random balanced partitions already do most of the work. Treat it as spectral search over averaging partitions, not as a general MCMC algorithm.
The authors say this plainly. The first two experiments have 40 and 256 states. Unconstrained objectives produce unbalanced blocks. Larger systems would need sparse eigensolvers, approximate scoring, or symmetry reduction. The TV plots count kernel iterations, not equal wall-clock work. Frobenius objectives do not give a universal total-variation mixing guarantee, and (GO P)^t is generally not GO P^t, so a smaller Fγ^∞ need not mean a better TV curve.
In the variable-selection experiment, exact GO sampling is possible only because all 4096 models are enumerated. A scalable version needs blocks whose conditional posteriors can be sampled without listing the whole model space. The mass constraint controls posterior mass, not simulation cost. The mass-matched random baseline is already close to the spectral output, so the extra value of spectral rounding is modest in this setting.
For the Ising run at k=4, the cutoff sits inside a sevenfold eigenvalue. The three procedures share one three-dimensional subspace so that scoring rules can be compared; a different basis inside the tie would change the candidate pool.