第 06 章学习笔记：时序网络社区检测

证明目标：设 $\rho_a^{\theta_i\theta_j}=\log\dfrac{\mu_a^{\theta_i\theta_j}}{\nu_a^{\theta_i\theta_j}}$、$R_{ab}^{\theta_i\theta_j}=\log\dfrac{P_{ab}^{\theta_i\theta_j}}{Q_{ab}^{\theta_i\theta_j}}$、$\ell_{ab}^{\theta_i\theta_j}=R_{ab}^{\theta_i\theta_j}-R_{00}^{\theta_i\theta_j}$（$a,b\in\{0,1\}$）。则模型 (6.14)–(6.15) 的 MLE 是使下式最大的社区指派 $\hat z$： $$\sum_{\substack{i,j\\z_i=z_j}}\Big\{A^1_{ij}\big(\rho_1^{\theta_i\theta_j}-\rho_0^{\theta_i\theta_j}\big)+\rho_0^{\theta_i\theta_j}+\big(A^1_{ij}-A^T_{ij}\big)\ell_{10}^{\theta_i\theta_j}\Big\}+\sum_{\substack{i,j\\z_i=z_j}}\sum_{t=2}^T\Big\{\big(\ell_{01}^{\theta_i\theta_j}+\ell_{10}^{\theta_i\theta_j}\big)\big(A^t_{ij}-A^{t-1}_{ij}A^t_{ij}\big)+\ell_{11}^{\theta_i\theta_j}A^{t-1}_{ij}A^t_{ij}-\log\frac{Q_{00}^{\theta_i\theta_j}}{P_{00}^{\theta_i\theta_j}}\Big\}.$$

依赖工具：时间马尔可夫性（似然 = 初值 × 逐转移，式 (6.5)/(6.15) 的结构）；示性函数恒等式 $\delta(z_i,z_j)$ 拆项（与 Ch4 Prop 4.4 同款代数）；两个初等展开（§11 补证卡）。

证明思路：对数似然按时间马尔可夫性拆成"初值项 + 逐转移项"；每项再把 $z_i=z_j$（核为 $\mu/P$）与 $z_i\ne z_j$（核为 $\nu/Q$）分开——后者不含 $z$，吸收进常数 $c(A)$；最后用两个示性展开把"$\sum_a\delta(A^1,a)\rho_a$"与"$\sum_{a,b}\delta\delta R_{ab}$"写成 $A^1,A^{t-1},A^t,A^{t-1}A^t$ 的线性式，按 $A^{t-1}A^t$（持久）、$A^t-A^{t-1}A^t$（新生）归并即得。

完整证明： 1. 时间分解：由 (6.14)–(6.15) 的马尔可夫结构， $$\log\mathbb P(A|z,\theta)=\log\mathbb P(A^1|z,\theta)+\sum_{t=2}^T\log\mathbb P(A^t|A^{t-1},z,\theta).$$ 2. 初值项按社区关系拆项：$z_i=z_j$ 时交互分布为 $\mu^{\theta_i\theta_j}$，否则为 $\nu^{\theta_i\theta_j}$，故 $$\log\mathbb P(A^1|z,\theta)=\frac12\sum_{i,j}\sum_a\delta(A^1_{ij},a)\Big(\delta(z_i,z_j)\rho_a^{\theta_i\theta_j}+\log\nu_a^{\theta_i\theta_j}\Big)=\frac12\sum_{i,j}\delta(z_i,z_j)\sum_a\delta(A^1_{ij},a)\rho_a^{\theta_i\theta_j}+c_1(A),$$ 其中 $c_1(A)=\frac12\sum_{i,j}\log\nu_{A^1_{ij}}^{\theta_i\theta_j}$ 与 $z$ 无关。 3. 转移项同理：以 $R_{ab}$ 记对数似然比， $$\log\mathbb P(A^t|A^{t-1},z,\theta)=\frac12\sum_{i,j}\delta(z_i,z_j)\sum_{a,b}\delta(A^{t-1}_{ij},a)\delta(A^t_{ij},b)R_{ab}^{\theta_i\theta_j}+c_t(A),$$ $c_t(A)$ 与 $z$ 无关；记 $c(A)=\sum_tc_t(A)$。 4. 初等展开（原书 "Simple calculations"，完整验证见 §11 补证卡）： $$\sum_a\delta(A^1_{ij},a)\rho_a=A^1_{ij}(\rho_1-\rho_0)+\rho_0;$$ $$\sum_{a,b}\delta(A^{t-1}_{ij},a)\delta(A^t_{ij},b)R_{ab}=R_{00}+A^{t-1}_{ij}\ell_{10}+A^t_{ij}\ell_{01}+A^{t-1}_{ij}A^t_{ij}(\ell_{11}-\ell_{01}-\ell_{10}),$$ 其中用到 $\ell_{ab}=R_{ab}-R_{00}$（故 $R_{10}-R_{00}=\ell_{10}$，$R_{11}-R_{01}-R_{10}+R_{00}=\ell_{11}-\ell_{01}-\ell_{10}$；系数上标 $\theta_i\theta_j$ 省略未写）。 5. 归并成持久/新生边形式：把第 4 步第二式对 $t=2,\dots,T$ 求和。注意 $A^{t-1}_{ij}\ell_{10}$ 与 $A^t_{ij}\ell_{10}$ 的指标平移关系： $$\sum_{t=2}^T A^{t-1}_{ij}\ell_{10}=\sum_{t=2}^T A^t_{ij}\ell_{10}+A^1_{ij}\ell_{10}-A^T_{ij}\ell_{10}.$$ 于是对每个同社区对 $(i,j)$，转移部分贡献 $$\sum_{t=2}^T\Big\{\ell_{10}A^t_{ij}+\ell_{01}A^t_{ij}+(\ell_{11}-\ell_{01}-\ell_{10})A^{t-1}_{ij}A^t_{ij}+R_{00}\Big\}+\big(A^1_{ij}-A^T_{ij}\big)\ell_{10},$$ 而 $\ell_{10}A^t+\ell_{01}A^t+(\ell_{11}-\ell_{01}-\ell_{10})A^{t-1}A^t=(\ell_{01}+\ell_{10})(A^t-A^{t-1}A^t)+\ell_{11}A^{t-1}A^t$（拆出新生边 $A^t-A^{t-1}A^t$ 与持久边 $A^{t-1}A^t$），且 $R_{00}=-\log\frac{Q_{00}}{P_{00}}$。 6. 合并初值项：把第 4 步第一式（初值）与第 5 步的边界修正 $(A^1-A^T)\ell_{10}$ 合写，再对同社区对求和、补上与 $z$ 无关的 $c(A)$，即得目标式（原书陈述中把 $\frac12$ 吸收为对有序对 $i,j$ 求和）。$\square$

闭合检查：最大化目标只含 $z_i=z_j$ 的示性项与数据量（$A^1,A^{t-1}A^t,A^t-A^{t-1}A^t$），其余全部吸收进 $c(A)$——$z$ 只通过"哪些对算同社区"进入目标，这正是模块度型目标的形状，也是 Lemma 6.1 近似的起点。常见误用：忘记 $\ell_{ab}=R_{ab}-R_{00}$ 的相对定义（第 5 步归并时 $R_{00}$ 项不能丢，它给出 $-\log\frac{Q_{00}}{P_{00}}$）。

证明目标：在 $P^{\theta_i\theta_j},Q^{\theta_i\theta_j}$ 非退化、$\mu^{\theta_i\theta_j},\nu^{\theta_i\theta_j}$ 为各自平稳分布、且 $P_{01},Q_{01}=o(1)$ 的条件下，Prop 6.2 的 MLE（忽略边界项后）近似等价于最大化正则化模块度 $\mathcal M(W,z,\gamma)=\sum_{i,j}\delta(z_i,z_j)\big(W_{ij}-\gamma\frac{d_id_j}{2m}\big)$，其中 $$W=\sum_{t=2}^T\big(\alpha A_{\mathrm{new}}^t+\beta A_{\mathrm{pers}}^t\big),\qquad \alpha=\log\frac{P_{01}}{Q_{01}}+\log\frac{1-P_{11}}{1-Q_{11}},\qquad \beta=\log\frac{P_{11}}{Q_{11}}.$$

依赖工具：一阶 Taylor $\log(1-x)=-x+o(x)$（$x=o(1)$）；平稳分布定义（$\mu_1$ 同时是"边出现"的平稳概率）；标签均匀 + $\theta$ 归一化（每社区 $\sum\theta_i=$ 社区大小）下的期望计数；Ch4 式 (4.21) 的正则化模块度定义。

证明思路：稀疏性使所有 $\theta_i\theta_j$ 上标的对数似然比塌缩为不带 $\theta$ 的常数（$\ell_{01}\approx\log\frac{P_{01}}{Q_{01}}$ 等），$-\log\frac{Q_{00}^{\theta_i\theta_j}}{P_{00}^{\theta_i\theta_j}}$ 一阶展开成 $\theta_i\theta_j(P_{01}-Q_{01})$；目标于是变成 (6.18)。关键是先对 $t=2,\ldots,T$ 求和，使零模型惩罚也累积 $(T-1)$ 次，再用 $W$ 的期望度与总权匹配模块度项。

完整证明： 1. 稀疏 Taylor 近似：$P_{01},Q_{01}=o(1)$ 时 $$\log\frac{1-\theta_i\theta_jQ_{01}}{1-\theta_i\theta_jP_{01}}=\theta_i\theta_j(P_{01}-Q_{01})+o(P_{01}^2+Q_{01}^2),$$ 且 $\ell_{01}^{\theta_i\theta_j}=\log\frac{\theta_i\theta_jP_{01}}{\theta_i\theta_jQ_{01}}-\log\frac{1-\theta_i\theta_jP_{01}}{1-\theta_i\theta_jQ_{01}}\approx\log\frac{P_{01}}{Q_{01}}$（第二项为 $O(\theta_i\theta_j(P_{01}-Q_{01}))$，被主导项 $\log\frac{P_{01}}{Q_{01}}$ 吸收）；同理 $\ell_{10}^{\theta_i\theta_j}\approx\log\frac{1-P_{11}}{1-Q_{11}}$（注意 $P_{10}=1-P_{11}$ 且 $P_{11}$ 不带度校正），$\ell_{11}^{\theta_i\theta_j}\approx\log\frac{P_{11}}{Q_{11}}$。 2. 目标化简为 (6.18) 并完成时间求和：把第 1 步代入 Prop 6.2 的目标（$T$ 大忽略边界项）：$(\ell_{01}+\ell_{10})\approx\alpha$、$\ell_{11}\approx\beta$，常数项 $-\log\frac{Q_{00}^{\theta_i\theta_j}}{P_{00}^{\theta_i\theta_j}}\approx-\theta_i\theta_j(P_{01}-Q_{01})$。先写成原书的逐时刻形式，再用 $W=\sum_{t=2}^T\tilde A^t$ 合并： $$\sum_{t=2}^T\sum_{i,j}\delta(z_i,z_j)\Big(\tilde a^t_{ij}-\theta_i\theta_j(P_{01}-Q_{01})\Big)=\sum_{i,j}\delta(z_i,z_j)\Big(W_{ij}-(T-1)\theta_i\theta_j(P_{01}-Q_{01})\Big),$$ 其中 $\tilde a^t_{ij}=\alpha(A_{\mathrm{new}}^t)_{ij}+\beta(A_{\mathrm{pers}}^t)_{ij}$。右侧的 $(T-1)$ 是后面匹配模块度时不能丢掉的关键。 3. 期望权重（平稳性，取稀疏主项）：度校正链的精确平稳边概率为 $$\mu^{\theta_i\theta_j}_1=\frac{\theta_i\theta_jP_{01}}{\theta_i\theta_jP_{01}+1-P_{11}}=\theta_i\theta_j\mu_1\,[1+o(1)],$$ 其中最后一步还需要逐对稀疏条件 $\theta_i\theta_jP_{01}=o(1)$（正是前一 Taylor 展开的适用尺度）；异社区同理。因而新生边与持久边的概率在主阶上分别为 $\theta_i\theta_j\mu_1(1-P_{11})$ 与 $\theta_i\theta_j\mu_1P_{11}$。故 $$\mathbb E W_{ij}=\begin{cases}(T-1)\,\theta_i\theta_j\mu_1\big(\alpha(1-P_{11})+\beta P_{11}\big),&z_i=z_j,\\ (T-1)\,\theta_i\theta_j\nu_1\big(\alpha(1-Q_{11})+\beta Q_{11}\big),&z_i\ne z_j,\end{cases}$$ 这里及下文等号均表示本引理保留的稀疏主阶。 4. 期望度与总权：标签均匀（每社区约 $n/K$ 个节点）+ $\theta$ 归一化（$\sum_{z_j=k}\theta_j=n/K$）⇒ $$\bar d_i=\sum_j\mathbb E W_{ij}=(T-1)\,\theta_i\,n\,\frac{S}{K},\qquad S:=\mu_1\big(\alpha(1-P_{11})+\beta P_{11}\big)+(K-1)\nu_1\big(\alpha(1-Q_{11})+\beta Q_{11}\big),$$ $$\bar m=\frac12\sum_i\bar d_i=\frac{(T-1)n^2}{2}\cdot\frac{S}{K}\quad(\text{用到 }\textstyle\sum_i\theta_i=n).$$ 5. 匹配聚合后的零模型项：把第 2 步的 $(T-1)\theta_i\theta_j(P_{01}-Q_{01})$ 写成 $\gamma\dfrac{\bar d_i\bar d_j}{2\bar m}$。由上式 $$\frac{\bar d_i\bar d_j}{2\bar m}=\frac{(T-1)^2\theta_i\theta_jn^2S^2/K^2}{(T-1)n^2S/K}=(T-1)\,\theta_i\theta_j\,\frac{S}{K},$$ 故使恒等式闭合的取值是 $$\gamma=\frac{K(P_{01}-Q_{01})}{S}.$$ 代回第 2 步的时间聚合式即得 $\sum_{i,j}\delta(z_i,z_j)\big(W_{ij}-\gamma\frac{\bar d_i\bar d_j}{2\bar m}\big)$（期望意义下）；用经验度 $d_i,m$ 替代期望度即得结论。$\square$

闭合检查：代数匹配还要求 $S\ne0$。$z$ 只经 $\delta(z_i,z_j)$ 进入，$W$ 把马尔可夫结构压缩成两个权重；但 Algorithm 17 的归一化拉普拉斯还需正文随后明确要求的 $\alpha,\beta\ge0$ 及正度条件，不能仅由本引理自动保证。$\beta=\log(P_{11}/Q_{11})$ 的符号跟随 $P_{11}-Q_{11}$，与 Figure 6.4 的实验方向一致。

校勘提示（对照原书文件页 164–165 / 印刷页 155–156）：原书对 $\gamma$ 给了两个彼此不一致的版本，且 $\bar m$ 漏 $(T-1)$。本项目早期修订虽然补回 $\bar m$，却把单个时刻的惩罚直接匹配到聚合矩阵 $W$，因而误留了 $1/(T-1)$。完整目标先对 $t=2,\ldots,T$ 求和，惩罚同样累积 $(T-1)$ 次；它与 $\bar d_i\bar d_j/(2\bar m)$ 中的 $(T-1)$ 抵消，最终校勘值是 $\gamma=K(P_{01}-Q_{01})/S$。$W,\alpha,\beta$ 的形式不受影响。

原书目标：同质 Markov SBM，$n$ 固定、$T\to\infty$，$P,Q$ 已知，演化非静态且 $P\ne Q$；Algorithm 18 以趋于 1 的概率完全恢复。

必须补足的条件与规则：原书证明实际需要一个满足 $P_{a_*b_*}\ne Q_{a_*b_*}$ 且在两类链下起始状态 $a_*$ 都被正频率访问的判别坐标；两条链不可约、非周期即可保证这一点。“演化非静态”按字面并不足以推出 $n_{a_*}\to\infty$。此外，Algorithm 18 印作“存在任意 $a,b$ 使 $|\widehat P_{ab}-P_{ab}|\le|P_{ab}-Q_{ab}|/2$ 就加边”；当 $P_{ab}=Q_{ab}$ 时右端为 0，这些无区分力坐标不应参与存在量词。项目可认证的最小修订是只在 $$\mathcal D:=\{(a,b):P_{ab}\ne Q_{ab}\}$$ 中检查该条件。

依赖工具：平稳遍历马尔可夫链的转移率一致性/渐近正态性（Billingsley, 1961）；并集界；相似图的连通分量结构。

条件补全后的证明： 1. 单对的一致性：固定 $(a,b)\in\mathcal D$，记 $n_{ab}(i,j)$ 为节点对 $(i,j)$ 的 $a\to b$ 转移数，$n_a(i,j)=\sum_bn_{ab}(i,j)$。在补充的遍历性/正访问频率条件下，$n_a(i,j)\to\infty$，且由马尔可夫链 CLT， $$\xi_{ab}(i,j):=\sqrt{n_a(i,j)}\,\big(\widehat P_{ab}(i,j)-P_{ab}(i,j)\big)\ \Rightarrow\ \mathcal N(0,\lambda_{ab}),\qquad \lambda_{(ab),(cd)}=\delta_{ac}\big(\delta_{bd}P_{ab}(i,j)-P_{ab}(i,j)P_{ad}(i,j)\big)$$ （多项式协方差结构）。于是对任意 $\alpha>0$， $$\mathbb P\Big(\big|\widehat P_{ab}(i,j)-P_{ab}(i,j)\big|\ge\alpha\Big)=\mathbb P\Big(\big|\xi_{ab}(i,j)\big|\ge\alpha\sqrt{n_a(i,j)}\Big)\ \xrightarrow[T\to\infty]{}\ 0.\tag{6.19}$$ （原书此处 $\xi$ 的分子在 OCR 中误植为 $n_{ab}-n_a\widehat P_{ab}$，按 Billingsley 的标准形式应为 $n_{ab}-n_aP_{ab}$；上式即其等价写法。） 2. 修订规则逐对一致：固定任一 $(a_*,b_*)\in\mathcal D$，记 $\Delta=|P_{a_*b_*}-Q_{a_*b_*}|>0$。若 $z_i=z_j$，真值为 $P$，不加边只能在 $|\widehat P_{a_*b_*}-P_{a_*b_*}|>\Delta/2$ 时发生；若 $z_i\ne z_j$，真值为 $Q$，错误加边 $|\widehat P_{a_*b_*}-P_{a_*b_*}|\le\Delta/2$ 由反三角不等式蕴含 $|\widehat P_{a_*b_*}-Q_{a_*b_*}|\ge\Delta/2$。两种误差概率都由第 1 步趋于 0。若修订算法遍历整个有限集 $\mathcal D$ 并用“存在”判据，再对 $|\mathcal D|\le4$ 个坐标取一次并集界即可。 3. 节点对并集界：至少一个节点对被误判的概率至多为 $\binom n2$ 乘以最大逐对误差概率；$n$ 固定，故该上界趋于 0。原书这里误写成“所有节点正确分类的概率被一个趋零量上界”，正确被上界的是至少一个节点对出错的概率。 4. 从配对判定到社区：全部配对判定正确时，相似图恰为 $K$ 个不相交团，连通分量给出真实社区，因此修订后的 Algorithm 18 输出 $\widehat K=K$、$\hat z=z$（标签置换意义下）。$\square$

闭合检查：在“判别坐标被正频率访问 + 忽略 $P_{ab}=Q_{ab}$ 的坐标”两项补充下，证明闭合；印刷版的“非静态”与未过滤存在量词本身不足以推出该结论。该渐近仍只适用于 $n$ 固定；若 $n\to\infty$，还需能压过 $\binom n2$ 的误差速率。

原书要证明的结论：在变分族 $\mathbb Q_\tau$ 下，$\widehat\tau=\arg\max_\tau J(\theta,\tau)$ 满足耦合固定点方程 $$\widehat\tau(t,i,k,\ell)\ \propto\ \pi_{k\ell}\prod_{j\ne i}\prod_{k'=1}^K\Big(\mathrm{Ber}(p_{\ell k'})(A^t_{ij})\Big)^{\widehat\tau_{\mathrm{marg}}(t,j,k')},$$ 比例常数由归一化 $\sum_\ell\widehat\tau(t,i,k,\ell)=1$ 确定；边际递推 $\tau_{\mathrm{marg}}(1,i,k)=\tau(i,k)$、$\tau_{\mathrm{marg}}(t,i,k)=\sum_\ell\tau_{\mathrm{marg}}(t-1,i,\ell)\tau(t,i,\ell,k)$。

审计结论：这不是一个可由原书所示一行偏导闭合的“显式解”，而是相互依赖的固定点条件。Matias 与 Miele（2017）的 Proposition 2 给出同类转移固定点，并明确省略证明；其初始 $\tau(i,k)$ 更新则是忽略依赖后的近似。原书展示的偏导还存在三处可直接看出的缺项：发射项没有写 $\sum_{j\ne i}\sum_{k'}$，$-\tau\log\tau$ 的导数符号不对，且没有处理当前转移参数经 $\tau_{\mathrm{marg}}(s,i,\cdot)$ 对 $s\ge t$ 产生的链式依赖。

可核验的局部代数：若在一次坐标更新中暂时冻结所有进入发射项的边际量，只保留当前转移坐标的直接贡献，则相应局部目标含 $$\tau_{\mathrm{marg}}(t-1,i,k)\,\tau(t,i,k,\ell)\left[\log\pi_{k\ell}-\log\tau(t,i,k,\ell)+\sum_{j\ne i}\sum_{k'}\tau_{\mathrm{marg}}(t,j,k')\log\mathrm{Ber}(p_{\ell k'})(A^t_{ij})\right].$$ 在对 $\ell$ 的归一化约束下对此局部代理目标求导，才会得到上面的“先验转移 $\pi_{k\ell}$ × 发射似然”比例形状。这能解释公式的结构，但不能替代对完整 $J$ 的固定点证明。

使用边界：本项目保留该式作为外引 VEM 固定点，不再声称已给完整证明，也不声称“把右端旧值代入”必然是完整 ELBO 的单调坐标上升。给定 $\tau$ 时的 M 步 $\widehat\pi,\widehat p$ 可以直接严格求出；初始 $\tau(i,k)$ 只能按原论文标为近似，见 §11 补证卡。

原书结论：令 $s\in[K]^n$ 的总错误率为 $\rho=\mathbb P(s_i\ne z_{it})$，并取 $\lambda=\log\frac{1-\rho}{\rho}$，则 MAP 目标等于下列图项加匹配奖励： $$\sum_{\substack{i,j\\z_i=z_j}}\Big\{\ell_{01}^{\theta_i\theta_j}\big(A^t_{ij}-A^{t-1}_{ij}A^t_{ij}\big)+\ell_{10}^{\theta_i\theta_j}\big(A^{t-1}_{ij}-A^{t-1}_{ij}A^t_{ij}\big)+\ell_{11}^{\theta_i\theta_j}A^{t-1}_{ij}A^t_{ij}-\log\frac{Q_{00}^{\theta_i\theta_j}}{P_{00}^{\theta_i\theta_j}}\Big\}+2\lambda\sum_{i=1}^n1(z_i=s_i).$$

成立所需的额外工作模型：

1. 用 $s$ 完全概括过去信息，即 $\mathbb P(z_t\mid A^{t-1},s,\theta)=\mathbb P(z_t\mid s)$；
2. 节点的预言机输出在给定 $z_t$ 后条件独立；
3. 若 $K=2$，采用二元对称错标：匹配概率 $1-\rho$、唯一错误标签概率 $\rho$。若 $K>2$，还必须指定混淆机制。

条件性推导：Bayes 分解先给出 $$\mathbb P(z|A^t,A^{t-1},s,\theta)\propto\mathbb P(A^t|A^{t-1},z,s,\theta)\,\mathbb P(z|A^{t-1},s,\theta),$$ 第一项由预言机独立性化为 $\mathbb P(A^t|A^{t-1},z,\theta)$；第二项只有在额外条件 1 下才能化为 $\mathbb P(z|s)$。对第一项应用 Prop 6.2 的单步拆项： $$\log\mathbb P(A^t|A^{t-1},z,\theta)=\frac12\sum_{\substack{i,j\\z_i=z_j}}\Big\{\ell_{01}^{\theta_i\theta_j}\big(A^t_{ij}-A^{t-1}_{ij}A^t_{ij}\big)+\ell_{10}^{\theta_i\theta_j}\big(A^{t-1}_{ij}-A^{t-1}_{ij}A^t_{ij}\big)+\ell_{11}^{\theta_i\theta_j}A^{t-1}_{ij}A^t_{ij}-\log\frac{Q_{00}^{\theta_i\theta_j}}{P_{00}^{\theta_i\theta_j}}\Big\}+c(A),$$ 其三类边分别是新生、消失和持久边。

在 $K=2$ 的二元对称错标模型下， $$\mathbb P(z|s)=\prod_i\frac{\mathbb P(s_i|z_i)\mathbb P(z_i)}{\mathbb P(s_i)}=\Big(\frac{\rho}{1-\rho}\Big)^{\#\{i:z_i\ne s_i\}}(1-\rho)^n\Big(\frac1K\Big)^n\Big/\prod_i\mathbb P(s_i),$$ 后三个因子与 $z$ 无关。取对数并用 $\#\{z_i\ne s_i\}=n-\sum_i1(z_i=s_i)$： $$\log\mathbb P(z|s)=\lambda\sum_i1(z_i=s_i)+\text{const},\qquad \lambda=\log\frac{1-\rho}{\rho}.$$ 合并两部分并把整个目标乘以 2，即得印刷式。$\square$

多类修订：若 $K>2$ 且错误时在其余 $K-1$ 类间均匀分配，则 $\mathbb P(s_i=a\ne z_i\mid z_i)=\rho/(K-1)$，匹配奖励应为 $$\lambda_K=\log\frac{(K-1)(1-\rho)}{\rho}.$$ 一般混淆矩阵 $C_{ka}=\mathbb P(s_i=a\mid z_i=k)$ 则贡献 $\sum_i\log C_{z_i,s_i}$，不能压成单一匹配计数。故原书 $\lambda$ 对 $K=2$ 精确，对一般 $K$ 并不由“总错误率 $\rho$”唯一确定；式 (6.21) 随后主动限制到 $K=2$，在额外条件 1 下可安全复用 Ch5 的二元松弛。

条目：Proposition 6.1 陈述后原书仅言 "whose proof can be found in (Avrachenkov et al., 2022)"（文件页 153 / 印刷页 144），书内无证明。

处理方式：不补证（该证明是信息论阈值论文的技术主体，篇幅远超本章定位），但把命题使用时的关键点固定下来：

1. 命题条件的完整转写（使用 Prop 6.1 时逐条核对）：稀疏参数化 (6.7)（$\mu_1=u\rho$ 等四个常数因子）且 $\rho T\ll1$；$P_{11},Q_{11}$ 为不随 $n,T$ 变的常数；非退化条件 $(P_{11},Q_{11})\ne(1,1)$（排除"边一旦出现永不消失"）与可辨识条件 $(p_{01},P_{11})\ne(q_{01},Q_{11})$（$f_{\mathrm{in}}\ne f_{\mathrm{out}}$）；$K\asymp1$。结论三层：(i) 一致恢复阈值 $\rho T\asymp1/n$；(ii) 强一致阈值 $\rho T\asymp\log n/n$；(iii) 临界常数 $\tau\tilde I=K$（$\tilde I$ 含几何分布 Hellinger 项 $H_{11}^2$，见 §9 卡片 T1）。
2. 技术出处与角色：Avrachenkov, Dreveton & Leskelä (2022) 证明 $\rho T\tilde I$ 是两个马尔可夫链分布 $f_{\mathrm{in}},f_{\mathrm{out}}$ 间 Rényi 散度（Ch4 Definition 4.3）Taylor 展开的主项，然后套用 Ch4 §4.4.3 的"散度 → 恢复分级"框架——证明骨架与静态 SBM 相同，新内容全在散度的计算（马尔可夫链的非独立序列使散度不再是简单乘积，$H_{11}^2$ 项正是"边保持时长分布"的贡献）。
3. 与本书证据链的衔接：本书侧的支撑是数值的——Figure 6.1 的 $T^*_{\mathrm{theo}}$ 由 (iii) 解出，实验精度曲线在其附近起飞；Figure 6.3 展示 $\rho=O(1/n)$ 极稀疏情形（Remark 6.1 的断言区间）Algorithm 16 仍可恢复。

证明目标（文件页 162 / 印刷页 153，原书一句带过）：对 $A^1,A^{t-1},A^t\in\{0,1\}$（省去上标 $\theta_i\theta_j$ 与下标 $ij$）， $$\text{(E1)}\quad\sum_{a\in\{0,1\}}\delta(A^1,a)\rho_a=A^1(\rho_1-\rho_0)+\rho_0;$$ $$\text{(E2)}\quad\sum_{a,b}\delta(A^{t-1},a)\delta(A^t,b)R_{ab}=R_{00}+A^{t-1}\ell_{10}+A^t\ell_{01}+A^{t-1}A^t(\ell_{11}-\ell_{01}-\ell_{10}),\quad\ell_{ab}:=R_{ab}-R_{00}.$$

依赖工具：二值变量的示性函数穷举；$\ell_{ab}$ 的定义。

完整证明：(E1)：$A^1=0$ 时左 = $\rho_0$，右 = $\rho_0$ ✓；$A^1=1$ 时左 = $\rho_1$，右 = $(\rho_1-\rho_0)+\rho_0=\rho_1$ ✓。

(E2)：左边是 $(A^{t-1},A^t)$ 的分段函数，穷举四种取值；右边记为 $\mathrm{RHS}$。 - $(0,0)$：左 = $R_{00}$；$\mathrm{RHS}=R_{00}$ ✓。 - $(1,0)$：左 = $R_{10}$；$\mathrm{RHS}=R_{00}+\ell_{10}=R_{00}+(R_{10}-R_{00})=R_{10}$ ✓。 - $(0,1)$：左 = $R_{01}$；$\mathrm{RHS}=R_{00}+\ell_{01}=R_{01}$ ✓。 - $(1,1)$：左 = $R_{11}$；$\mathrm{RHS}=R_{00}+\ell_{10}+\ell_{01}+(\ell_{11}-\ell_{01}-\ell_{10})=R_{00}+\ell_{11}=R_{11}$ ✓。$\square$

闭合检查：(E2) 的代数实质是"二值二元的离散泰勒展开"——$R_{ab}$ 写成基线 $R_{00}$ + 各变量的主效应 + 交互效应；交互项系数 $\ell_{11}-\ell_{01}-\ell_{10}=R_{11}-R_{01}-R_{10}+R_{00}$ 正是"持久边的超额对数似然比"，这是持久边在 Lemma 6.1 获得独立权重 $\beta$ 的代数根源。

审查目标：给定 $\tau$ 时，M 步 $\widehat\pi,\widehat p$ 可精确求出；初始坐标 $\tau(i,k)$ 因会影响后续全部边际，只能把原论文的乘积式标为忽略这些依赖后的近似更新。

依赖工具：$J$ 的初始、转移与发射三项；带归一化约束的 Lagrange 乘子法；$\partial(x\log x)=\log x+1$；VE 固定点的证明边界。

精确部分： (i) $\widehat\pi$：$J$ 中含 $\pi$ 的项为 $\sum_{t\ge2}\sum_{i,k,\ell}\tau_{\mathrm{marg}}(t-1,i,k)\tau(t,i,k,\ell)\log\pi_{k\ell}$，约束 $\sum_\ell\pi_{k\ell}=1$（逐 $k$）。拉氏量对 $\pi_{k\ell}$ 求导：$\frac{1}{\pi_{k\ell}}\sum_{t,i}\tau_{\mathrm{marg}}(t-1,i,k)\tau(t,i,k,\ell)+\mu_k=0$ ⇒ $\pi_{k\ell}$ 正比于该和式，归一化即得。$\square$

(ii) $\widehat p$：采用有序节点对 $i\ne j$ 可把对称参数的两种标签方向统一计入。记 $w_{ij}^{k\ell}(t)=\tau_{\mathrm{marg}}(t,i,k)\tau_{\mathrm{marg}}(t,j,\ell)$；由于 $A_{ij}=A_{ji}$，对 $k\ne\ell$，$(i,j)$ 与 $(j,i)$ 两项正好对应无序节点对上的 $(k,\ell)$ 与 $(\ell,k)$ 两种分配。$J$ 中相关项（整体重复因子不影响极值）为 $$\sum_t\sum_{i\ne j}w_{ij}^{k\ell}(t)\big[A^t_{ij}\log p_{k\ell}+(1-A^t_{ij})\log(1-p_{k\ell})\big].$$ 对 $p_{k\ell}$ 求导： $$\frac{\partial J}{\partial p_{k\ell}}=\sum_t\sum_{i\ne j}w_{ij}^{k\ell}(t)\Big(\frac{A^t_{ij}}{p_{k\ell}}-\frac{1-A^t_{ij}}{1-p_{k\ell}}\Big)=0\ \Longrightarrow\ (1-p_{k\ell})\sum wA=p_{k\ell}\sum w(1-A),$$ 其中求和现统一取 $t$ 与 $i\ne j$。整理得 $$\widehat p_{k\ell}=\frac{\sum_t\sum_{i\ne j}w_{ij}^{k\ell}(t)A^t_{ij}}{\sum_t\sum_{i\ne j}w_{ij}^{k\ell}(t)}.$$ $\square$（原书印刷中第二个边际的节点下标应为 $j$，且自环对 $i=j$ 应排除；二值邻接下 $1(A^t_{ij}\ne0)=A^t_{ij}$。）

(iii) 初始 $\tau(i,k)$ 的近似边界：若只保留初始项与 $t=1$ 发射项，并冻结由它诱导的 $t\ge2$ 边际依赖，则代理目标的偏导为 $$\log\alpha_k-\log\tau(i,k)-1+\sum_{j\ne i}\sum_{k'}\tau_{\mathrm{marg}}(1,j,k')\log\mathrm{Ber}(p_{kk'})(A^1_{ij})+\mu(i)=0,$$ 从而得到近似比例式 $\tau(i,k)\propto\alpha_k\prod_{j\ne i}\prod_{k'}\mathrm{Ber}(p_{kk'})(A^1_{ij})^{\tau_{\mathrm{marg}}(1,j,k')}$。完整 $J$ 中，$\tau(i,k)$ 还经递推影响所有后续 $\tau_{\mathrm{marg}}(t,i,\cdot)$；这些链式项没有在该式中出现，所以不能把它称为精确 maximizer。

闭合检查：$\widehat\pi$ 是软转移计数归一化，$\widehat p$ 是软连边率；这两项是给定变分分布时的标准、精确 M 步。VE 固定点与初始坐标近似则依赖外部算法推导，本项目明确分层，不再把三者合称“完整 VEM 证明”。