第 05 章学习笔记：图半监督学习

第 05 章学习笔记：图半监督学习

配套译文：内部译文（已落盘，status: structure-complete；proof-link 锚点已按译文顶部注释对账，见本文件顶部注释）。 本章讲图上的半监督学习（SSL）：除图 $G$ 外，一个可能出错的 oracle 给出部分节点的社区标签，目标是推断其余节点。结构为"一条方法主线 + 一条理论主线"：§5.1–§5.3 是方法线（Laplacian 方法族 → 小标注数据的修补 → 三条替代路线），§5.4 是理论线（DC-SBM 上的贝叶斯 MAP → 连续松弛 → 误分类上界）。语义对象 7 个（Assumption/Lemma/Theorem/Corollary 共享计数器 5.1–5.7，Proposition 独立计数仅 5.1）、编号公式 (5.1)–(5.23)、算法块 7 个（Algorithm 8–14）、8 图 0 表；章末为"进一步阅读"（Further Notes，印刷页 139），本书无习题。

1. 一句话定位

本章回答"社区检测已知一部分答案时怎么办"——第 4 章是无监督恢复（只靠图），本章引入 oracle：它标注了节点集 $\ell$（其中 $\ell_1$ 标对、$\ell_0$ 标错，恒设有信息的 oracle $|\ell_1|>|\ell_0|$，Assumption 5.1），方法上从"硬约束下的 Laplacian 平滑"（Label Propagation，Lemma 5.2 给出闭式解）出发，经历两次失效诊断（噪声 oracle、极小标注量）与两条修补线（Poisson learning；约束谱/谱子空间/$\ell^1$ 方法），最终在 §5.4 用 DC-SBM 分析 Algorithm 14。原书 Theorem 5.5 给出闭式误分类上界，但其 E3 谱隙与平方常数链均不成立；本项目保留源文陈述，并另给可验证的谱隙显式修订版。

2. 本章导读

1. 章首（印刷页 108–110）：SSL 问题设定。membership 矩阵 $Z$、oracle 矩阵 $S$（式 (5.1)：标对行 = $Z_{i\cdot}$、标错行 = 另一个 one-hot、未标注行 = 零行）、错误率 $|\ell_0|/|\ell|<1/2$ 的"有信息"条件（Assumption 5.1）、分类函数矩阵 $X$ 与判决规则 $\hat z_i=\operatorname{argmax}_kX_{ik}$（式 (5.2)）、$\ell/u$ 分块记号。这套记号是全章的公共语言。
2. 5.1 Laplacian 方法（印刷页 110–118）：Label Propagation（5.1.1）= 硬约束 $X_{\ell\cdot}=S_{\ell\cdot}$ 下最小化 $\mathrm{Tr}(X^{\top}LX)$（式 (5.3)），Lemma 5.2 给闭式解（式 (5.4)），并有传播/随机游走 hitting-time/热方程三种等价解释——随机游走解释是 §5.2 失效分析的钥匙，也呼应 Ch3 §3.3.2 的 hitting time。Label Spreading（5.1.2）把硬约束换成贴合损失、把 $L$ 换成归一化 $\mathcal L$；Generalized Laplacian（5.1.3）用参数 $\sigma$ 把三者（$\sigma=1$ LP、$1/2$ LS、$0$ PageRank 型）统一。5.1.4 的三组图（5.1/5.2/5.3）给出两个失效事实：精度随 $\alpha$ 升到近 1 处骤降（图 5.1）；噪声与小标注量都显著拉低精度（图 5.2/5.3）。
3. 5.2 小标注数据（印刷页 118–123）：先用随机游走语言解释失效机理——标注点太少时首中时间超过混合时间，游走"忘记起点"，$\widehat X^{LP}$ 对所有未标注点趋于同一常数（鞅 + Doob 可选停止，式 (5.6)）；修补思路是把标注节点从"热源"改成"源+汇"（Poisson learning，式 (5.7) 配平衡约束 $\sum_id_iX_{ik}=0$，Lemma 5.3 给迭代格式与收敛性，Algorithm 10），图 5.4 显示每类仅 1 个标注点时仍有高精度。
4. 5.3 其他方法（印刷页 123–128）：三条替代路线。约束谱聚类（5.3.1）：oracle 编成 must-link/cannot-link 矩阵 $Q$，加约束 $\mathrm{Tr}(X^{\top}\bar QX)\ge\alpha$ 后 KKT 条件化为广义特征值问题（Lemma 5.4，Algorithm 11）；Laplacian 正则化（5.3.2）：限制在 $L$ 的前 $p$ 个特征向量张成的子空间里做最小二乘（Algorithm 12）；$\ell^1$ 稀疏标签传播（5.3.3）：把沿边差分的 $\ell^2$ 惩罚换成全变差 $\ell^1$（式 (5.10)），不再把社区边界这种突变信号抹平（Algorithm 13，理论整体外引 Jung et al., 2019）。
5. 5.4 贝叶斯 SSL 与理论分析（印刷页 128–139）：本章理论高地。$K=2$、DC-SBM（式 (5.20)）+ 噪声 oracle（式 (5.11)，$\eta_1$ 标对概率、$\eta_0$ 标错概率）；Prop 5.1 推出 MAP 估计量 = $\min\mathrm{Cut}-\tau n_1n_2+\lambda|\{i\in\ell:z_i\ne s_i\}|$（式 (5.12)）；连续松弛（5.4.2）化为约束线性系统（式 (5.17)），解由 secular equation（式 (5.19)）给出，即 Algorithm 14。Theorem 5.5 的原书证明按三步展开并依赖 Appendix B，但精确常数链未闭合；本项目把它拆成“源文证明审计”和“谱隙显式修订版”。Corollary 5.6/5.7 保留为原书的条件性 regime 分级。5.4.4 数值实验：map-relaxed 抗噪最好，且对"被标错的节点"也能平滑纠错（图 5.8，与 Poisson learning 对照）。
6. 进一步阅读（印刷页 139）：3 段文献指引（GNN、随机矩阵方法、并行图 SSL），解读见本页 §16。

3. 本页使用方式

按你在正文中最可能卡住的位置直接跳转：

• Label Spreading 的 $\alpha$ 到底等于 $\lambda/(1+\lambda)$ 还是 $1/(1+\lambda)$？ → 这是原书印刷笔误：书上印 $\alpha=\lambda/(1+\lambda)$，但按其自身三行前的推导与 Algorithm 9 的方程，自洽的读法是 $\alpha=1/(1+\lambda)$，辨析见 §14 易混点 第 1 条与 §11 GL 补证卡 的校勘提示。
• Label Propagation 的解 (5.4) 和它的三种解释（传播/随机游走/热方程）对不上号 → 三者都收敛到同一个不动点系统 (5.5)；闭式解推导见 proof-lemma-5-2，随机游走解释需要的次随机矩阵/首中概率背景见 §7 第 2 条。
• §5.2.1 的鞅论证为什么说明"算法忘记了起点" → 一句话版：首中时间 $\tau$ 超过混合时间后 $y_\tau$ 近似服从平稳分布 $\pi_j\propto d_j$，与起点 $i$ 无关，所以 $\widehat X^{LP}_{ik}$ 对所有未标注 $i$ 趋于同一个数（式 (5.6)）；形式化链条见 §9 卡片 T3 与 §14 第 4 条。
• Theorem 5.5 陈述里的符号在 OCR 里全是错的（$\rho$、$\varphi$、游离抑扬符） → 已按 PDF 页面订正：斜体 $p$ 不是 $\rho$、$p_{\mathrm{out}}$ 不是 $\varphi_{\mathrm{out}}$、"z + 抑扬符"是 $\hat z$，上界中 $p_{\mathrm{in}}\pm p_{\mathrm{out}}$ 无 hat；订正后的完整陈述见 §9 卡片 T6。
• Theorem 5.5 证明里冒出来的 Corollary B.2 / Lemma B.3 / Proposition B.2 / Corollary B.5 是什么、在哪 → 它们属于 Appendix B（单元 91-appendix-b 已落盘）；每个结论在本证明中扮演的角色见 App B 依赖定位卡。
• 把 (5.23) 平方之后和定理陈述的上界对不上 → 你读得没错：按字面平方会多出一个 $((\bar\alpha+\lambda)/\bar\alpha)^2$ 因子，并且出现 $1/(\eta_1+\eta_0)$；$\lambda\gtrsim\bar\alpha$ 并不能控制前一个比值，故原书的 $|S_\beta|$ 中间式不能在现有条件下直接由 (5.23) 推出。只有另加 $\lambda=O(\bar\alpha)$ 与 $\eta_1+\eta_0$ 的统一下界（或允许参数依赖的常数）才可恢复原书形式；完整辨析见 proof-theorem-5-5 的校勘提示 (b)。
• 找不到 Theorem 5.1–5.4 / Lemma 5.1 → 本章 Assumption/Lemma/Theorem/Corollary 共享计数器 5.1→5.7，是原书编号体系，不是缺漏（§14 第 7 条）。
• §5.4.2 的 secular equation 和 $\gamma_*$ 是哪来的 → 约束 $\|x\|^2=n$ 的 Lagrange 乘子；完整推导链（(5.14)→(5.17)→(5.18)(5.19)→Algorithm 14）见 deriv-ssl-map-relaxation。

4. 本章主线

5. 本章学习路线 / 概念地图

因果结构读法：oracle 设定催生 Laplacian 平滑方法族；方法族撞上两处失效（噪声、小标注）；失效逼出修补线；最后生成模型（DC-SBM）把"方法好不好"变成"上界是多少"。

6. 分层阅读路线

• 第一遍（主线，约 1.5 小时）：章首设定（$S$、$\ell_0/\ell_1$、Assumption 5.1）→ 5.1.1 全节（(5.3) → Lemma 5.2 → 三种解释各读首段）→ 5.1.2/5.1.3 只读代价函数与闭式解形状 → 5.1.4 三组图 + 5.2.1 失效解释 → 5.2.2 Poisson learning 的"源+汇"直觉 → 5.4.3 Thm 5.5 陈述与 Cor 5.6/5.7 陈述。目标：能画出 §5 的因果图，说清 LP 的两处失效。
• 第二遍（证明精读，约 3 小时）：按依赖序读六组：① Lemma 5.2（拉氏量 + 分块求逆，含原书符号笔误校勘）；② §11 GL 补证（$\alpha$ 校勘是本章最佳"自己验证"训练）；③ Lemma 5.3（Green 函数递推 + 平衡守恒 + 遍历收敛）；④ Lemma 5.4（KKT → 广义特征值问题）；⑤ Prop 5.1（Bayes + 复用 Ch4 Prop 4.4 的对数似然）+ §5.4.2 松弛推导（secular equation 的来历）；⑥ Thm 5.5 全链（三步 + App B 定位 + 因子校勘）。
• 第三遍（应用与实验逻辑）：按 Algorithm 8–14 的实现视角重读（LP 的 $O(|u|^3)$ 线性系统 vs 迭代传播；Alg 10 的 $T$ 步迭代；Alg 14 的 $\gamma_*$ 求解）；细读 5.4.4：$\tau=4(\sigma_1+\sigma_2)/n$ 与 $\lambda$ 的启发式选择为何满足 Thm 5.5 的条件；标准约束 vs 度归一约束（图 5.5）；图 5.8 的三类节点精度对比（这是"平滑纠错"最直观的证据）。
• 专题回看：学 Ch3 §3.3.2 时回看 LP 的 hitting-time 解释（§7 第 2 条）；学 Ch4 Prop 4.4 / Thm 4.9 / Lemma 4.11 时对照 Prop 5.1、§11 预处理定位卡、Thm 5.5 第 (iii) 步 的 $\beta$-bad 论证；Appendix B 单元落盘后回链 定位卡。

7. 初学者背景补充

本章默认的数学背景集中在六处，按首次出现顺序：

1. 图拉普拉斯二次型恒等式：$x^{\top}Lx=\frac12\sum_{i,j}a_{ij}(x_i-x_j)^2$（附录 Prop A.10，Ch4 已反复使用）。它是 LP/LS/GL 一切"平滑性"的来源：最小化它 = 让相邻节点的值接近。归一化版本 $\mathcal L=I-D^{-1/2}AD^{-1/2}$ 对应的二次型见 (5.1.2) 的展开 $\frac12\sum a_{ij}(x_{ik}/\sqrt{d_i}-x_{jk}/\sqrt{d_j})^2$。
2. 次随机矩阵与吸收随机游走（5.1.1 起）：$P=D^{-1}A$ 是随机游走转移矩阵；删去标注行/列后的 $(D^{-1}A)_{uu}$ 是次随机矩阵（行和 $\le1$，与 $\ell$ 相邻的行严格 $<1$）。只要每个未标注节点都能走到某个标注节点（如 $G$ 连通且 $\ell\ne\emptyset$），其谱半径 $<1$，故 $(I_{|u|}-(D^{-1}A)_{uu})^{-1}=\sum_{t\ge0}(D^{-1}A)_{uu}^t$ 存在——这正是 (5.4) 中逆矩阵合法的原因，也是"从 $i$ 出发的游走 a.s. 有限步内撞上 $\ell$"的代数表述。hitting time/首中概率的系统处理见 Ch3 §3.3.2。
3. 鞅与 Doob 可选停止定理（5.2.1）：只用到一句——有界停时 $\tau$ 下 $\mathbb E[X_{y_0}]=\mathbb E[X_{y_\tau}]$。正文从 "$LX=0$ 在未标注节点上成立（式 (5.5)）"推出 $X_{y_t}$ 是鞅，再代 $y_0=i$、$y_\tau\in\ell$ 得 (5.6) 的一阶近似。
4. KKT 条件与 Lagrange 乘子（Lemma 5.4、§5.4.2）：不等式约束 $\mathrm{Tr}(X^{\top}\bar QX)\ge\alpha$ 的 KKT 四条（稳定/原始可行/对偶可行/互补松弛）；互补松弛 $\lambda(\mathrm{Tr}(X^{\top}\bar QX)-\alpha)=0$ 分"约束不起作用（$\lambda=0$，退回普通谱聚类）"与"约束贴边（$=\alpha$）"两情形。等式约束 $\|x\|^2=n$ 的乘子 $\gamma$ 引出约束线性系统 (5.17) 与 secular equation (5.19)（Gander et al., 1989 的显式求根法只引用结论）。
5. 平均场与谱浓度语言（5.4.3）：平均场图 = 期望邻接矩阵 $\mathbb EA$ 构成的加权图；二元 DC-SBM 的 $\mathbb EA=ZBZ^{\top}$ 只有两个非零特征值 $\bar d$（平均度）与 $\bar\alpha$（信号）。浓度指 $\|A-\mathbb EA\|=O(\sqrt{\bar d})$（$\bar d=\Omega(\log n)$，Feige & Ofek 2005）；线性系统敏感性不等式 $\|\Delta x\|/\|x\|\le\kappa(A)\|\Delta A\|/\|A\|$（Horn & Johnson §5.8）把矩阵扰动翻译成解扰动。这套语言与 Ch4 Thm 4.8/4.9 同源。
6. DC-SBM 与 MAP（5.4 起）：模型定义见第 2 章笔记与术语表（式 (2.7)(2.8)）；MAP 与"对数似然按示性函数拆项"的代数直接复用 Ch4 Prop 4.4 的结尾（第 4 章笔记），本章不重新推导。

8. 核心对象与符号表

9. 关键定理卡片

编号提醒：本章 Assumption/Lemma/Theorem/Corollary 共享计数器（5.1→5.7），Proposition 独立计数（仅 5.1）；没有 Theorem 5.1–5.4。

卡片 T0：Assumption 5.1（oracle 有信息，全章恒设）

• 内容：$|\ell_1|>|\ell_0|$——oracle 标对的节点多于标错的节点，等价于错误率 $|\ell_0|/|\ell|<1/2$。
• 用途：它是"oracle 标签有语义"的根据——正因如此，§5.4 的误差 $d_{\mathrm{Ham}}$ 不需要像 Ch4 那样对标签置换取最小（§14 第 5 条）；Thm 5.5 上界中的 $(\eta_1-\eta_0)^2$ 正是这个条件的定量化身（$\eta_1>\eta_0$ ⇔ 有信息）。

卡片 T1：Lemma 5.2（Label Propagation 的闭式解）

• 条件：图 $G$（可加权），oracle $S$；优化问题 (5.3)：硬约束 $X_{\ell\cdot}=S_{\ell\cdot}$ 下最小化 $\mathrm{Tr}(X^{\top}LX)$。
• 结论：$\widehat X^{LP}_{\ell\cdot}=S_{\ell\cdot}$，$\widehat X^{LP}_{u\cdot}=\big(I_{|u|}-(D^{-1}A)_{uu}\big)^{-1}(D^{-1}A)_{u\ell}S_{\ell\cdot}$（式 (5.4)）；等价地 $L\widehat X$ 在标注点上等于 $S$、在未标注点上为 0（式 (5.5)）。
• 用途：Algorithm 8 的根据；同一不动点系统 (5.5) 有三种解释（迭代传播 / 随机游走 hitting-time / 热方程），随机游走解释是 §5.2 失效分析的入口；逆矩阵合法性来自次随机性（§7 第 2 条）。
• 证明入口：proof-lemma-5-2（含原书中间式符号笔误的校勘）。

卡片 T2：Label Spreading 与 Generalized Laplacian 的闭式解（非编号对象）

• 结论：LS（Zhou et al., 2004）最小化 $\mathrm{Tr}(X^{\top}\mathcal LX)+\lambda\|X-S\|_F^2$，解 $\widehat X^{LS}=(1-\alpha)(I-\alpha\mathcal A)^{-1}S$（$\mathcal A=D^{-1/2}AD^{-1/2}$）；GL（Avrachenkov et al., 2012）最小化 $\mathrm{Tr}(X^{\top}D^{\sigma-1}LD^{\sigma-1}X)+\lambda\mathrm{Tr}((X-S)^{\top}D^{2\sigma-1}(X-S))$，解 $\widehat X^{GL}=(1-\alpha)(I-\alpha D^{-\sigma}AD^{\sigma-1})^{-1}S$。$\sigma=1/2$ 退回 LS，$\sigma=1$ 为 LP 的软约束版，$\sigma=0$ 时 $D^{-\sigma}AD^{\sigma-1}=AD^{-1}=P^{\top}$，正是 Personalized PageRank 的闭式形。
• 校勘要点：两处的 $\alpha$ 原书均印作 $\lambda/(1+\lambda)$，但按 LS 的三行推导链与 Algorithm 9 的方程 $(I-\alpha\mathcal A)\widehat X=(1-\alpha)S$，自洽读法是 $\alpha=1/(1+\lambda)$；图 5.1 的"$\alpha\to1$ 精度骤降"也只在 $\alpha=1/(1+\lambda)$（$\lambda\to0$ 贴合消失）下成立。
• 证明入口：LS 推导原书已给全；GL 计算被原书省略外引——§11 补证。

卡片 T3：Lemma 5.3（Poisson learning 的迭代与收敛）

• 条件：$G$ 连通、随机游走非周期；$\bar s_k=\frac1{|\ell|}\sum_{i\in\ell}S_{ik}$。
• 结论：(i) 由 $X^{(T+1)}_{ik}=\sum_{j\in\ell}(S_{jk}-\bar S_{jk})G_T(i,j)$（$G_T$ 归一化 Green 函数，式 (5.8)）定义的序列满足递推 $X^{(T+1)}=X^{(T)}+D^{-1}\big(\text{源汇项}-LX^{(T)}\big)$；(ii) $\lim_{T\to\infty}X^{(T)}=X$，$X$ 是 Poisson 方程 (5.7) 在平衡约束 $\sum_id_iX_{ik}=0$ 下的唯一解。
• 用途：Algorithm 10 的根据；平衡约束是它与 LP 的本质区别——LP 在未标注点上要求 $LX=0$（热量守恒、温度趋同），Poisson 允许源汇净通量为零但逐点可调，因此不会在小标注下退化成常数。
• 证明入口：proof-lemma-5-3。

卡片 T4：Lemma 5.4（约束谱聚类化为广义特征值问题）

• 条件：优化问题 (5.9)：$\min\mathrm{Tr}(X^{\top}\mathcal LX)$，约束 $X^{\top}X=I_K$ 与 $\mathrm{Tr}(X^{\top}\bar QX)\ge\alpha$（$\bar Q=D^{-1/2}QD^{-1/2}$）。
• 结论：解的各列满足广义特征值问题 $\mathcal LX_{\cdot k}=\lambda(\bar Q-\beta I)X_{\cdot k}$（某 $\beta$）；互补松弛排除 $\lambda=0$（否则退回无约束谱聚类），故约束贴边 $\mathrm{Tr}(X^{\top}\bar QX)=\alpha$ 且 $\lambda>0$。
• 用途：Algorithm 11 的根据（取 $\lambda_k>0$ 的可行特征向量中使 $\nu^{\top}\mathcal L\nu$ 最小的前 $K-1$ 个 + $k$-means）。
• 证明入口：proof-lemma-5-4。

卡片 T5：Proposition 5.1（带噪声 oracle 的 DC-SBM MAP 估计量）

• 条件：$K=2$ 同质 Poisson SBM（式 (2.7)，$\omega_{\mathrm{in}}>\omega_{\mathrm{out}}$），oracle $s$ 按 (5.11) 生成（$\eta_1$ 标对、$\eta_0$ 标错）。
• 结论：$\hat z_{\mathrm{MAP}}=\operatorname{argmin}_z\ \mathrm{Cut}(A,z)-\tau n_1(z)n_2(z)+\lambda\,|\{i\in\ell:z_i\ne s_i\}|$（式 (5.12)），其中 $\tau=\frac{\omega_{\mathrm{in}}-\omega_{\mathrm{out}}}{\log(\omega_{\mathrm{in}}/\omega_{\mathrm{out}})}$、$\lambda=\frac{\log(\eta_1/\eta_0)}{\log(\omega_{\mathrm{in}}/\omega_{\mathrm{out}})}$。
• 用途：三项的读法 = 两个无监督项（最小割 + 规模平衡 $n_1n_2$ 在 $n/2$ 处最大）与一个半监督项（与 oracle 不一致数）；它是 §5.4.2 连续松弛（Algorithm 14）的出发点，也回答了"Ch4 的 MAP 框架如何吸收标签信息"。
• 证明入口：proof-proposition-5-1（复用 Ch4 Prop 4.4 结尾的对数似然展开）。

卡片 T6：Theorem 5.5（原书上界与项目修订版）

• 条件：DC-SBM（式 (5.20)）+ 噪声 oracle（式 (5.11)）；$\bar d=\frac n2(p_{\mathrm{in}}+p_{\mathrm{out}})$、$\bar\alpha=\frac n2(p_{\mathrm{in}}-p_{\mathrm{out}})$；$\tau>p_{\mathrm{out}}$；$\hat z$ 为 Algorithm 14 的输出。
• 原书陈述（已按 PDF 订正 OCR 误读；此精确形式不列为项目已证明结论）： $$\frac{d_{\mathrm{Ham}}(\hat z_u,z_u)}{n}\ \le\ C\left(\frac{p_{\mathrm{in}}+p_{\mathrm{out}}}{p_{\mathrm{in}}-p_{\mathrm{out}}}\right)^{\!2}\left(\frac{\bar\alpha+\lambda}{\lambda}\right)^{\!2}\frac{1}{(\eta_1+\eta_0)(\eta_1-\eta_0)^2\,\bar d}.$$
• 审计结论：E3 使 (5.22) 失效；(5.23) 平方到 $|S_\beta|$ 又漏掉 $((\lambda+\bar\alpha)/\bar\alpha)^2$ 与 $1/(\eta_1+\eta_0)$。两处都是确定性断点。
• 项目修订结论：若 $g=\bar\delta_1-\bar\gamma_*$、$H=|\gamma_*-\bar\gamma_*|+\|A-\mathbb EA\|$、$\beta=\min_{i\in u}|\bar x_i|$，则 $d_{\mathrm{Ham}}/n\le H^2/(\beta^2g^2)$，且 $g\ge\lambda\bar\alpha(\eta_1-\eta_0)/(2(\lambda+\bar\alpha))$。
• 入口：源文证明审计、谱隙显式修订版；App B 依赖见 定位卡。

卡片 T7：Corollary 5.6 / 5.7（两个 regime 的分级）

• Cor 5.6（度发散，almost exact recovery）：$\bar d\gg1$、信噪比 $=O(1)$、$\sqrt{\eta_0+\eta_1}(\eta_1-\eta_0)\gg1/\sqrt{\bar d}$、$\tau>p_{\mathrm{out}}$、$\lambda\gtrsim\bar\alpha$ ⇒ 误分类比例 $=o(1)$。允许 $\eta_0,\eta_1\to0$，即次线性数量的标注节点（$(\eta_1-\eta_0)n$ 是标对与标错节点数的期望差）。
• Cor 5.7（常数度，detection）：$p_{\mathrm{in}}=c_{\mathrm{in}}/n$、$p_{\mathrm{out}}=c_{\mathrm{out}}/n$，$\sqrt{\eta_0+\eta_1}(\eta_1-\eta_0)$ 为非零常数，$\tau>2p_{\mathrm{out}}$、$\lambda\gtrsim1$ ⇒ 当 $\frac{(c_{\mathrm{in}}-c_{\mathrm{out}})^2}{c_{\mathrm{in}}+c_{\mathrm{out}}}$ 大于某常数时，whp 优于随机猜测。该量即信噪比 $\approx\bar\alpha^2/\bar d$，与 Ch4 的 KS 型阈值语言同族；原书自注遗憾：常数无法控制（来自浓度常数），与 Le et al., 2017 对无监督常数度 regime 的注记相同。
• 证明入口：proof-corollary-5-6、proof-corollary-5-7。

算法卡片（Algorithm 8–14，共 7 个）

10. 关键定理完整证明

原书在本章给出 7 处证明（Lemma 5.2/5.3/5.4、Prop 5.1、Thm 5.5、Cor 5.6/5.7）加 1 条非编号推导（§5.4.2 松弛链）。可闭合者按"证明目标 + 依赖工具 + 证明思路 + 完整证明 + 闭合检查"呈现；Thm 5.5 与两条下游推论因确定性断点改标为源文审计，并增加谱隙显式修订定理。Thm 5.5 对 Appendix B 的依赖另做定位卡。

11. 正文隐藏验证补全

清单 §6 判为"真正留白/压缩证明/外引留白"的 3 条逐一处理如下（锚点与译文顶部注释对账一致）；其余命中均为修辞性用法，不设卡片。

12. 术语与跨章链接

本章首次引入、已入全书术语表的术语（点击跳转定义）：

• 设定与框架：半监督学习、预言机 oracle、MAP 估计量、图拉普拉斯
• §5.1 方法族：Label Propagation、Label Spreading、Generalized Laplacian
• §5.2/5.3 方法：Poisson learning、约束谱聚类、Laplacian 正则化、稀疏标签传播
• §5.4 理论件：度校正 SBM、割 Cut、谱聚类、精确恢复、相变、对数几率 log-odds

跨章链接：

• 承接 Ch4：Prop 4.4（对数似然展开，Prop 5.1 第 2 步直接复用）；Thm 4.8（"浓度 → 扰动 → 坏集"证明范式，Thm 5.5 同构）；Thm 4.9 定位卡（稀疏区浓度失效与正则化，$\bar d=o(\log n)$ 预处理卡 的姊妹篇）；Lemma 4.11（坏集计数，与 $\beta$-bad 论证同族）；Ch4 的 $d^*_{\mathrm{Ham}}$（对置换取最小）对照本章 $d_{\mathrm{Ham}}$（§14 第 5 条）。
• 承接 Ch2：DC-SBM 与同质 Poisson SBM 的定义（式 (2.7)(2.8)），见第 2 章笔记与术语表。
• 呼应 Ch3：Label Propagation 解的 hitting-time / 首中概率解释（§7 第 2 条）是 Ch3 §3.3.2 随机游走 hitting time 的直接应用；GL 的 $\sigma=0$ 端接通 Personalized PageRank（Ch3 中心性指标 + §16 第 1 段的 GNN 脉络）。Ch3 单元落盘后应回填双向链接。
• 前瞻：Appendix B（91-appendix-b，Thm 5.5 的四个依赖，见定位卡）；Further Notes 的 GNN/随机矩阵/并行计算三条线（§16）。

校勘备忘（译文与本笔记统一按此处理，详见清单 §7）：① Thm 5.5 陈述的 OCR 误读（斜体 $p$ 误作 $\rho$、$p_{\mathrm{out}}$ 误作 $\varphi_{\mathrm{out}}$、$\hat z$ 拆成 z+抑扬符）已按 PDF+文本层订正，上界中 $p_{\mathrm{in}}\pm p_{\mathrm{out}}$ 无 hat；② §5.1.2/5.1.3 的 $\alpha=\lambda/(1+\lambda)$ 为原书印刷笔误，自洽读法 $\alpha=1/(1+\lambda)$（补证卡）；③ Lemma 5.2 起句缺句点是原书排版风格（与 Lemma 5.3/5.4 体例不一），非 OCR 错误；④ Lemma 5.2 证明中间式漏负号（proof-lemma-5-2 校勘提示）；⑤ Thm 5.5 第 (iii) 步 $|S_\beta|$ 中间式与 (5.23) 差一个因子（proof-theorem-5-5 校勘提示 (b)）。

13. 章节阅读路径

14. 易混点

1. $\alpha=\lambda/(1+\lambda)$ vs $\alpha=1/(1+\lambda)$：原书印前者，但按其自身推导（LS 三行链、GL 代价函数、Algorithm 9 方程）自洽的是后者。记忆法：$\alpha$ 是"传播/平滑"的权重、$1-\alpha$ 是"贴合 oracle"的权重——贴合权重应正比于 $\lambda$，故 $1-\alpha=\lambda/(1+\lambda)$、$\alpha=1/(1+\lambda)$。完整推导与三条旁证见 §11 补证卡。
2. $\lambda$ 三处撞名：LS/GL 的贴合权重（§5.1）；MAP (5.12) 的 oracle 权重 $\log\frac{\eta_1}{\eta_0}/\log\frac{\omega_{\mathrm{in}}}{\omega_{\mathrm{out}}}$（§5.4.1）；Lemma 5.4 的 KKT 乘子（§5.3.1）。三者语境互不相交，但 §5.4 的 $\lambda$ 会一路进入 Thm 5.5 的上界因子 $((\bar\alpha+\lambda)/\lambda)^2$——读到上界时它特指 MAP/松弛的 oracle 权重。
3. LP vs LS vs GL：约束方式（LP 硬钉死 $X_{\ell\cdot}=S_{\ell\cdot}$；LS/GL 软贴合 $\lambda\|X-S\|^2$ 类项）× 平滑矩阵（$L$ / $\mathcal L$ / $D^{-\sigma}AD^{\sigma-1}$）两个维度。GL 是统一框架：$\sigma=1/2$ 复现 LS，$\sigma=1$ 是 LP 的软约束版，$\sigma=0$ 是 PageRank 型。别把"LP 的硬约束"与"LS 的软贴合"混为同一算法的两个名字。
4. "忘记起点"的确切含义：§5.2.1 的鞅论证不是说 LP 数值上不收敛，而是说标注点太少时，从任一未标注点出发的随机游走在撞上 $\ell$ 之前已混合，$X_{ik}\approx\sum_{j\in\ell}\pi_jS_{jk}$（式 (5.6)）与 $i$ 无关——所有未标注点得到同一个分类函数值，argmax 退化为掷硬币。平移判决规则（减去该公共值）是治标，Poisson learning 的源+汇是治本。
5. $d_{\mathrm{Ham}}$ vs Ch4 的 $d^*_{\mathrm{Ham}}$：无监督恢复的标签没有语义（社区换名不变划分），误差必须对置换取最小；本章有信息 oracle（Assumption 5.1）固定了标签语义——$s_i=+1$ 的节点告诉了你"哪个社区叫 $+1$"——故 Thm 5.5 的 $d_{\mathrm{Ham}}$ 不取置换最小。这不是疏忽，是半监督设定的实质差别。
6. 两个 $\tau$ 方向相反：本章 $A_\tau=A-\tau1_n1_n^{\top}$（减，MAP 里的削峰项，$\tau=\frac{\omega_{\mathrm{in}}-\omega_{\mathrm{out}}}{\log(\omega_{\mathrm{in}}/\omega_{\mathrm{out}})}$）；Ch4 的正则化是 $A+\frac\tau n1_n1_n^{\top}$（加，治稀疏区浓度）。同名不同物；Thm 5.5 的条件 $\tau>p_{\mathrm{out}}$ 属于前者。
7. 编号共享计数器：本章不存在 Theorem 5.1–5.4、Lemma 5.1/5.5–5.7——Assumption 5.1 → Lemma 5.2/5.3/5.4 → Theorem 5.5 → Corollary 5.6/5.7 共享 5.1→5.7，Proposition 独立计数仅 5.1。是原书编号体系，不是 OCR 或译文缺漏。
8. 三级恢复语言：exact（一个不错）> almost exact（错 $o(n)$ 个，Cor 5.6）> detection（优于随机，Cor 5.7）。Cor 5.7 的"优于随机猜测"是 detection 级，不要读成接近 KS 阈值的最优结论（常数无法控制，原书自注遗憾）。
9. 标准约束 vs 度归一约束：§5.4.2 推导用 $\|x\|^2=n$（标准），§5.4.4 实验改用 $\sum_id_ix_i^2=2|E|$（度归一）——后者 cost 更小（图 5.5）且为实验实际采用版本。Thm 5.5 的分析按标准约束书写；度异质性大时两者结论可有实质差别，引用实验结论时注意是哪个版本。
10. $S$（矩阵）vs $s$（向量）vs $\bar s_k$ vs $\bar S$：章首 oracle 是 $n\times K$ 矩阵 $S$；§5.4 换 $\pm1$ 记号后 oracle 是向量 $s\in\{0,\pm1\}^n$；$\bar s_k$ 是类 $k$ 的标注均值（标量，式 (5.7)），$\bar S$ 是其矩阵化（Lemma 5.3）。$K=2$ 时两套记号互通：$s_i=\pm1$ 对应 $S_{i\cdot}$ 的两个 one-hot。

15. 公式卡片

本章编号公式 (5.1)–(5.23) 共 23 个，按用途归并为 12 张卡片；校勘要点附在相关卡片。

F1 — 式 (5.1)(5.2)（设定）：oracle 矩阵 $S$（标对行 $Z_{i\cdot}$、标错行 $\widetilde Z_{i\cdot}$、未标注行零）与判决规则 $\hat z_i=\operatorname{argmax}_kX_{ik}$。全章输入/输出格式。

F2 — 式 (5.3)(5.4)(5.5)（Label Propagation）：硬约束优化 $\min_{X_{\ell\cdot}=S_{\ell\cdot}}\mathrm{Tr}(X^{\top}LX)$ → 闭式解 $\widehat X^{LP}_{u\cdot}=(I_{|u|}-(D^{-1}A)_{uu})^{-1}(D^{-1}A)_{u\ell}S_{\ell\cdot}$ → 不动点系统 $L\widehat X=S$（$\ell$ 上）$/0$（$u$ 上）。证明（含负号校勘）。

F3 — LS 代价与解（未编号 + Algorithm 9）：$\min\mathrm{Tr}(X^{\top}\mathcal LX)+\lambda\|X-S\|_F^2$ → $\widehat X^{LS}=(1-\alpha)(I-\alpha\mathcal A)^{-1}S$，$(I-\alpha\mathcal A)\widehat X=(1-\alpha)S$。校勘：$\alpha=1/(1+\lambda)$（非印刷的 $\lambda/(1+\lambda)$），见 §11。

F4 — GL 代价与解（未编号）：$C^{GL}=\mathrm{Tr}(X^{\top}D^{\sigma-1}LD^{\sigma-1}X+\lambda(X-S)^{\top}D^{2\sigma-1}(X-S))$ → $\widehat X^{GL}=(1-\alpha)(I-\alpha D^{-\sigma}AD^{\sigma-1})^{-1}S$；$\sigma$ 插值 LP/LS/PageRank。补证。

F5 — 式 (5.6)（"忘记起点"）：$X_{ik}\approx\sum_{j\in\ell}\pi_jS_{jk}=\frac{\sum_{j\in\ell}d_jS_{jk}}{\sum_jd_j}$——鞅 + Doob 可选停止给出，与 $i$ 无关；小标注失效的定量表达。

F6 — 式 (5.7)(5.8)（Poisson learning）：Poisson 方程 $LX_{ik}=\sum_{j\in\ell}(S_{jk}-\bar s_k)\delta_{ij}$（配平衡 $\sum_id_iX_{ik}=0$）与 Green 函数迭代 $X^{(T+1)}_{ik}=\sum_{j\in\ell}(S_{jk}-\bar S_{jk})G_T(i,j)$。证明。

F7 — 式 (5.9)（约束谱聚类）：$\min\mathrm{Tr}(X^{\top}\mathcal LX)$，s.t. $X^{\top}X=I_K$、$\mathrm{Tr}(X^{\top}\bar QX)\ge\alpha$ → 广义特征值问题 $\mathcal LX_{\cdot k}=\lambda(\bar Q-\beta I)X_{\cdot k}$。证明。

F8 — 式 (5.10)（稀疏标签传播）：$\min_{x_i=z_i^0\,(i\in\ell)}\sum a_{ij}|x_i-x_j|$——全变差替代 $\ell^2$ 平滑；不可微 ⇒ 理论外引（§11）。

F9 — 式 (5.11)（§5.4 噪声 oracle）：$s_i=z_i^0$（概率 $\eta_1$）/$-z_i^0$（$\eta_0$）/$0$（其余）。上界因子 $(\eta_1+\eta_0)(\eta_1-\eta_0)^2$ 的来源。

F10 — 式 (5.12)(5.13)（MAP）：$\hat z_{\mathrm{MAP}}=\operatorname{argmin}\mathrm{Cut}-\tau n_1n_2+\lambda|\{i\in\ell:z_i\ne s_i\}|$，$\tau=\frac{\omega_{\mathrm{in}}-\omega_{\mathrm{out}}}{\log(\omega_{\mathrm{in}}/\omega_{\mathrm{out}})}$、$\lambda=\frac{\log(\eta_1/\eta_0)}{\log(\omega_{\mathrm{in}}/\omega_{\mathrm{out}})}$；oracle 后验因子 $\mathbb P(z|s)\propto(\eta_0/\eta_1)^{|\{i\in\ell:z_i\ne s_i\}|}$。证明。

F11 — 式 (5.14)–(5.19)（松弛链）：(5.14) 球面松弛 $\min -x^{\top}A_\tau x+\lambda(s-\mathcal Px)^{\top}(s-\mathcal Px)$（约束 $\|x\|^2=n$；变体 (5.15) 完美 oracle 硬约束）→ (5.16) 符号判决 → (5.17) 约束线性系统 $(-A_\tau+\lambda\mathcal P-\gamma I)x=\lambda s,\ x^{\top}x=n$ → (5.18) 解式（$\gamma_*$ 代入）→ (5.19) secular equation $\sum_i(b_i/(\delta_i-\gamma))^2=n$。完整推导。

F12 — 式 (5.20)–(5.23)（理论链）：(5.20) DC-SBM 生成模型（$\theta_i\in[\theta_{\min},\theta_{\max}]$，$\mathbb E\theta_i=1$）；(5.21) 敏感性不等式 $\frac{\|\widehat X-\bar x\|}{\|\bar x\|}\le\|(\mathbb E\tilde{\mathcal L})^{-1}\|\|\Delta\tilde{\mathcal L}\|$（校勘提示 (a)，proof-theorem-5-5）；(5.22) 条件数界 $1/(\lambda+\bar\alpha)$（Lemma B.3）；(5.23) 集中界 $C\frac{(\lambda+\bar\alpha)^2}{\bar\alpha^2\lambda}\frac{\sqrt{\bar d}}{\sqrt{\eta_1+\eta_0}(\eta_1-\eta_0)}$（与 $|S_\beta|$ 中间式的因子不一致见校勘提示 (b)）。

16. Further Notes 导读

本书无习题；章尾"进一步阅读"（Further Notes，印刷页 139）共 3 段，按"读什么、为什么读、与后续章的关系"解读。

第 1 段：节点特征 + 图结构 → GNN 脉络——本章所有方法只用图（节点没有特征）；社交、引用、知识图谱网络的节点自带特征，"同时用图结构与特征"正是图神经网络（GNN）的出发点。读法：Scarselli et al. (2008) 是 GNN 的首个框架性文献（历史定位）；Defferrard et al. (2016) 用图傅里叶变换给出高效实现（ChebNet，技术上可看作"谱滤波的参数化"——与 §5.3.2 谱子空间方法血脉相通）；Kipf & Welling (2017) 是 SSL 语境下的 GCN，即本章问题的"带特征版"，必读。三篇 Personalized PageRank ↔ GNN 的联系文献（Klicpera et al., 2019；Bojchevski et al., 2020；Chien et al., 2020）对本章读者特别有性价比：GL 的 $\sigma=0$ 端就是 Personalized PageRank 闭式（卡片 T2），这批文献说明"传播矩阵 + 重启"的 LP/GL 结构正是 GNN 信息传递的极限形态——也把本章接回 Ch3 的 PageRank 中心性。综述 Wu et al. (2020)、Zhou et al. (2020) 作全景地图。与后续章关系：本书正文不再展开 GNN；这是离书进入当前文献的主出口。

第 2 段：随机矩阵方法分析 SSL——Mai & Couillet (2018, 2021)。§5.4 的分析走"平均场 + 浓度 + 敏感性"路线，部件散见 Appendix B；随机矩阵理论给出另一条分析路线（大维渐近下分类函数本身的分布刻画），适合在读完 Thm 5.5 源文审计、项目修订定理与 App B 后作为对照技术体系阅读。

第 3 段：并行/云计算下的图 SSL——Avrachenkov et al. (2016a)、Ravi & Diao (2016)、Chen et al. (2020)。回应的是 Algorithm 8–10 的实现层：LP 的闭式解要解 $|u|\times|u|$ 线性系统（一般 $O(|u|^3)$），但不动点迭代（传播形式）天然可分布式；大图场景下"传迭代不传矩阵"是这批文献的核心。读法建议：工程导向读者在 §5.1.1 的"迭代传播"解释处接入本段文献即可，不影响理论主线。

17. 学习检查表

学完本章后自查：

• [ ] 能复述：SSL 设定四要素（$Z$、$S$、$\ell_0/\ell_1$、Assumption 5.1）与判决规则 (5.2)；为什么有信息 oracle 使 $d_{\mathrm{Ham}}$ 不需要对置换取最小。
• [ ] 能推导：从 (5.3) 到 (5.4) 的完整链条（拉氏量 → 分块 → 随机游走形式），并解释逆矩阵为何存在（次随机性）；从 LS/GL 代价函数到闭式解，并指出 $\alpha$ 的正确值及三条旁证。
• [ ] 能解释：Label Propagation 的三种解释（迭代传播/随机游走 hitting-time/热方程）为何收敛到同一不动点系统 (5.5)；"忘记起点"的鞅论证一句话版（首中时间 > 混合时间 ⇒ $X_{ik}$ 与 $i$ 无关）。
• [ ] 能区分：LP 的硬约束 vs LS 的软贴合 vs GL 的 $\sigma$ 插值；热源（LP）vs 源+汇（Poisson learning，平衡约束 $\sum_id_iX_{ik}=0$ 的作用）；$\ell^2$ 平滑 vs $\ell^1$ 全变差（社区边界为何被前者抹平）。
• [ ] 能推导：Prop 5.1 的三项 MAP 目标（Cut、$-\tau n_1n_2$、$\lambda$ 不一致计数）各自从对数似然的哪部分来；§5.4.2 从 (5.14) 到 secular equation (5.19) 的链条，特别是"为什么取最小 $\gamma$"。
• [ ] 能复述：Thm 5.5 原书上界的四个因子、E3 与平方链两个断点；能写出项目修订版 $d_{\mathrm{Ham}}/n\le H^2/(\beta^2g^2)$ 及 $g$ 的有效下界。
• [ ] 能判别：Cor 5.6（almost exact）与 Cor 5.7（detection）的 regime 差异；为什么 Cor 5.6 允许次线性标注量而 Cor 5.7 的常数无法控制。
• [ ] 能定位：两处失效的实验证据（图 5.1–5.3）；Algorithm 14 是 Thm 5.5 的被估计对象；图 5.8 三类节点精度对比说明"平滑纠错"；$\bar d=o(\log n)$ 预处理与 Jung et al. 理论分别去哪篇文献追。

18. 后续衔接

• Appendix B（单元 91-appendix-b，已落盘）：Thm 5.5 的四个依赖（Corollary B.2、Lemma B.3、Proposition B.2、Corollary B.5）在此落盘；定位卡 的角色表已回填双向链接。先读 App B.1（$\mathbb E\tilde{\mathcal L}$ 的谱与 secular equation 根的集中）再读 B.2（平均场解的符号恢复）。
• 第 3 章 Centrality Indices（待制作）：LP 解的 hitting-time 解释（§7 第 2 条）与 GL 的 $\sigma=0$ Personalized PageRank 端在 Ch3 §3.3.2 获得系统处理；两章落盘后互填回链。
• 第 6 章 Temporal Networks：社区恢复向时序网络的扩展；本章的"部分标签 + 图"设定与失效诊断（噪声、小样本）方法论可平移。
• 第 7 章 Sampling：本章假设图全观测 + 部分标签；Ch7 处理图本身只能抽样观测的对偶场景。
• 离书方向：Further Notes 三条线（§16）——GNN（带特征的 SSL，Kipf & Welling 2017 为入口）、随机矩阵分析（Mai & Couillet，对照 §5.4 路线）、并行图 SSL（大图实现）。