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
新加坡国立大学用P²底部特征函数做加权k-means选出Gibbs划分，复合基线MCMC；40态哑铃图最坏TV从0.65降至10⁻¹¹，变量选择T=5000时ePIP相对P降10.4倍。
MCMC 的局部更新在瓶颈或相关变量上会走得很慢。一个补救是把状态空间切成 k 块，在当前块里按平稳条件分布重采样，再跟原来的转移核 P 复合，或做加法混合 (P+GO)/2。这个块内平均核叫 Gibbs 核 GO。Choi、Lim、Wang 前面几篇已经说明，合适的划分能压掉麻烦模态。真正卡住的是怎么选划分：全集划分数量是 Bell 数，穷举不现实。
Lim and Choi 2026 对两块情形给过组合近似。这篇把选划分收成一个可谱松弛的矩阵目标，用底部特征函数做 rounding，给出两块阈值扫描、k 块加权 k-means、加法混合和多时域打分四套算法。
目标 F(O) 是加权 Frobenius 意义下，复合核 GO P 离平稳核 Π 的一步距离平方。它有三个等价写法：矩阵范数、P² 上多路归一化割的补、以及初始块标签 Z 与一步后状态 X1 之间的 Pearson χ² 互信息。F 越小，走一步之后越记不住自己刚从哪一块来。最小化 F 等于最大化 P² 的跨块流量。
这和经典谱聚类方向相反。Shi-Malik / Ng-Jordan-Weiss 用 I-P² 的低频模态（P² 的最大非平凡特征函数）找边界小、内部粘的社区。这里用 P² 的最小非平凡特征函数，刻意找跨块流量大的切法。论文把这叫反向谱聚类。
算法分三档。
两块：取 P² 的底部特征函数，按取值排序做阈值扫描，对每个阈值切精确算 F，取最小。这个扫描恰好解一维加权 two-means rounding。若特征函数只取两个值，扫描达到谱下界，划分是最优的。
k 块：用底部 k-1 个特征函数把状态嵌进 R^{k-1}，做 π 加权 k-means 生成候选，再用 F 重打分。rounding 误差 δ 等于嵌入点到块质心的加权平方和，也等于两个子空间主夹角的正弦平方和。谱夹逼把 δ 转回 F 的次优界：特征间隙越大、谱宽越窄，rounding 越稳。
加法混合 AO=(P+GO)/2：目标换成 H(O)=||AO-Π||²{F,π}。松弛改用 P 的代数最小特征函数，能保留负特征值的符号。P² 会把大正、大负特征值压成同一档，加法混合不会。
还有有限时域和折扣无限时域版本。折扣 γ=0.9 时几何视野均值是 10 步。多时域不换嵌入，只换最后用哪条目标给候选打分。F(P^t, O) 量的是「先在块内平均、再让原链走 t 步」，一般不等于反复用 GO P 走 t 步。
前提很硬：块内条件分布要能采样。划分选得好但 GO 抽不动，这个核就落不了地。
三个精确可算的小实验。代码仓库是 mchchoi/spectral-partitioning。多路实验默认 80 次加权 k-means++ 启动，在生成的候选池里取原目标最小者，不是全局离散最优。
受控谱哑铃图：两个 20 环共 40 个状态，桥权 ε 控制慢正模态，lazy 参数 α 控制负谱。α=0.08、ε=0.03 时 λ1=-0.84、λ{n-1}=0.998748。重复核 t=10 的最坏全变差：
| 核 | d^{wc}{TV}(K,10) |
| 原核 P | 0.652 |
| 两块 GO P | 1.01×10^{-11} |
| 四块 F 选出的 GO P | 6.55×10^{-7} |
| 加法混合 AO | 0.129 |
| 多时域 GO P | 6.55×10^{-7} |
48 个 (α,ε) 格点上，F 与 H 选出的划分最大加权不一致 0.725，F 与 Fγ^∞ 最大 0.550。最敏感的点是 α=0.16、ε=0.006：多时域把 Fγ^∞ 从 3.4202 打到 1.5517，lag-10 的 F 从 0.3002 打到 0.05818，t=10 的 TV 从 1.10×10^{-6} 到 3.61×10^{-8}。后一项改进是经验观察，目标本身不保证。
精确 Curie-Weiss Ising，d=8、256 态、k=4，热浴核。(β,h)=(1.5,0) 时相对磁化分箱和坐标块：
| 目标 | 谱扫描 | 磁化分箱 | 坐标块 |
| F | 0.7454 | 2.4185 | 2.3616 |
| H | 19.4566 | 20.1889 | 20.1833 |
| Fγ^∞ | 1.7356 | 12.9934 | 11.4684 |
F 相对磁化基线降 69.2%，Fγ^∞ 降 86.6%。H 的百分比只有 3.63%，因为 H 里有一项与划分无关的大常数。t=10 最坏 TV：P 为 0.5277，四块 GO P 约 2.46×10^{-4}，加法混合 0.0820。选出的块极不平衡：最大块平稳质量约 0.96，最小约 0.012。平均核要压的是持续模态，不是社区。
贝叶斯变量选择：12 个二值变量、4096 个模型，6 对高度相关代理 (ρ=0.995)，单翻转 Metropolis 在 10 与 01 之间几乎过不去。无约束 rounding 块质量塌成约 (1.00, 7.3×10^{-29}, 1.1×10^{-33}, 2.4×10^{-39})，Gibbs 更新几乎是直接抽后验。加上 0.15≤π(Oi)≤0.35 的块质量约束后，T=5000 时平衡多时域核相对 P：ePIP、epair、esize、eBMA 分别降 10.4、8.4、2.5、9.5 倍。质量匹配的随机划分再用 F 重打分，已经接近谱方法。这里大部分收益来自「有受控块质量的条件平均」，谱候选生成的额外收益不大。
给有限状态 MCMC 提供一条可算的划分启发式：特征函数不只用来诊断混合快慢，还用来构造一个新的、可仿真的核。对已经能做块内 Gibbs 更新的模型（精确枚举的变量选择、小格点 Ising、有轨道结构的群平均链），这是现成的调参器。
对做谱聚类的人，方向反转本身就是判断：你要的是慢社区还是快遗忘的平均块，用的特征函数差一档。加法混合保留负谱，P² 目标会把振荡模态和慢模态混在一起，这个区别在带负特征值的链上是真的。
它不是通用加速器。GO 要可采样，实验全是精确小链，无约束会塌成近乎抽后验。变量选择里随机平衡划分已经很强。更接近「有谱保证的划分搜索」，距离即插即用的采样算法还很远。
作者自己写得很清楚。前两个实验分别只有 40 和 256 个状态，无约束目标会产出不平衡块。更大系统需要稀疏特征求解、近似目标或对称性约化。全变差图画的是核迭代次数，不是等计算量。Frobenius 目标不提供普适的 TV 混合保证；(GO P)^t 一般也不等于 GO P^t，所以 Fγ^∞ 更小不必然 TV 曲线更好。
变量选择里 GO 能精确采样，是因为 4096 个模型全部枚举了。可扩展应用必须保证块的条件后验能在不枚举全空间的前提下采样。平衡约束管的是后验质量，不是仿真成本。质量匹配的随机基线已经接近谱输出，谱 rounding 的增量在这个设定里并不大。
Ising 在 k=4 时截止落在七重特征值内部。三个目标共用同一组三维子空间才可比较；换一组正交基底，候选池会变。