第 05 章精校翻译：图半监督学习
第 5 章 图半监督学习（Graph-based Semi-supervised Learning）
半监督学习（semi-supervised learning，SSL）旨在通过结合未标注数据与标注数据来获得更优的学习性能。由于未标注数据的数量通常远大于标注数据，当无监督学习的性能低下时，或者当为有监督学习获取大量标注数据的成本过高时，SSL 方法就有用武之地。不幸的是，许多标准的半监督学习技术已被证明不能高效利用未标注数据，从而导致不能令人满意或不稳定的性能（Chapelle et al., 2006, Chapter 4；Ben-David et al., 2008；Cozman et al., 2002）。此外，标注数据中噪声的存在可能进一步降低这些方法的性能。在实践中，噪声往往来自执行标注任务的疲惫或不够尽职的专家。
在本章中，我们将综述若干标准的半监督图聚类方法。特别地，我们将研究这些方法在标注数据量很少的情形下的性能，并在存在噪声标签时提出稳健的解决方案。
总体思路（General idea）
我们假设图 $G = (V, E)$ 的节点集 $V = [n]$ 被划分为 $K$ 个互不重叠的社区，由潜在的社区标注向量 $z \in [K]^n$ 表示。方便的做法是引入 $z$ 的独热表示（one-hot representation），即定义一个 $n \times K$ 的真值成员矩阵（ground-truth membership matrix）$Z \in \{0, 1\}^{n \times K}$，使得
$$ Z_{ik} = \left\{ \begin{array}{ll} 1, \qquad & \mathrm{if}\ z_i = k, \\ 0, \qquad & \mathrm{otherwise.} \end{array} \right. $$
如第 4 章所见，无监督社区检测（community detection）是从对 $G$ 的观测（有时还已知 $K$）中恢复 $Z$ 的问题。我们这里研究的是带噪声的半监督设定。更确切地说，我们假设除了观测到图之外，一个标签信息源（原文 oracle，计算机科学中常译“预言机”）还会给我们关于某些节点簇归属的额外信息。为与相关文献和后续公式保持一致，下文简称“预言机”。我们称这些节点为标注节点（labelled nodes），并用 $\ell$ 表示标注节点的集合。在这些节点中，一些被预言机正确标注，另一些被预言机错误标注。我们用 $\ell_0$ 表示被错误标注的节点集，用 $\ell_1$ 表示被正确标注的节点集。特别地，$\ell = \ell_0 \sqcup \ell_1$。预言机可以用一个 $n \times K$ 的矩阵 $S$ 表示，其行 $S_{i\cdot}$ 由下式给出
$$ S_{i\cdot} = \left\{ \begin{array}{ll} Z_{i\cdot}, & \quad \mathrm{if} \quad i \in \ell_1, \\ \widetilde{Z}_{i\cdot}, & \quad \mathrm{if} \quad i \in \ell_0, \\ 0_{1 \times K}, & \quad \mathrm{if} \quad i \notin \ell, \end{array} \right. \tag{5.1} $$
其中 $\widetilde{Z}_{i\cdot}$ 取自 $\{ z \in \{0, 1\}^K : \| z \|_1 = 1 \ \text{且}\ z \neq Z_{i\cdot} \}$，$0_{1 \times K}$ 表示 $K$ 个零构成的行。
换言之，预言机 (5.1) 揭示 $|\ell_1|$ 个节点的正确簇归属，并对 $|\ell_0|$ 个节点揭示错误的簇归属；对 $n - |\ell|$ 个节点它什么也不揭示。量 $|\ell_0| / |\ell|$ 是预言机的错误率（即预言机在揭示了信息的前提下揭示错误信息的概率）。若该量小于 $1/2$，则称预言机是有信息的（informative），这等价于直观条件 $|\ell_1| > |\ell_0|$。在下文中，我们将始终假设预言机是有信息的。
预言机是有信息的，即 $|\ell_1| > |\ell_0|$。
给定预言机 $S$ 与图 $G$，我们的策略是找到一个矩阵 $\widehat{X} \in \mathbb{R}^{n \times K}$，由它可以预测节点的标签。我们把列 $X_{\cdot k}$ 称为分类函数（classification functions），若
$$ \hat{z}_i = \operatorname{argmax}_{k \in \{1, \ldots, K\}} X_{ik}, \tag{5.2} $$
则节点 $i$ 被分入簇 $\hat{z}_i$。
一个标准框架是把 $\widehat{X}$ 定义为如下类型优化问题的解
$$ \widehat{X} \ = \ \underset{X \in \mathcal{X}}{\arg\min}\ C(X, S), $$
其中 $C(X, S)$ 是代价函数，$\mathcal{X}$ 是 $\mathbb{R}^{n \times K}$ 的一个子集。
记号（Notations）
贯穿本章，$\ell$ 表示被预言机标注的节点集，$u = [n] \setminus \ell$ 表示未标注节点集。预言机由矩阵 $S \in \{0, 1\}^{n \times K}$ 表示（定义见公式 (5.1)），目标是在观测到图 $G$ 与预言机 $S$ 之后推断 $Z \in \{0, 1\}^{n \times K}$。
在对节点重新编号意义下，我们可以假设前 $|\ell|$ 个节点被预言机标注，其余 $|u|$ 个未被标注。相应地，任何矩阵 $M \in \mathbb{R}^{n \times n}$ 都可以写成块形式
$$ M = \left( \begin{array}{cc} M_{\ell\ell} & M_{\ell u} \\ M_{u\ell} & M_{uu} \end{array} \right). $$
此外，对任何矩阵 $X = (X_{ik}) \in \mathbb{R}^{n \times K}$，$X_{i\cdot}$ 表示 $X$ 的第 $i$ 行，$X_{\cdot k}$ 表示 $X$ 的第 $k$ 列，并记 $X = \binom{X_{\ell\cdot}}{X_{u\cdot}}$。
最后，$I_{\ell}$ 表示这样的对角矩阵：其 $(i, i)$ 元在 $i \in \ell$ 时等于 1，否则等于 0。
5.1 基于拉普拉斯矩阵的 SSL 方法（Laplacian-based SSL Methods）
5.1.1 标签传播（Label Propagation）
方法介绍（Presentation of the method）
无监督社区检测的谱方法（spectral methods）基于二次函数的最小化，例如 $\mathrm{Tr}(X^T L X)$ 或 $\mathrm{Tr}(X^T \mathcal{L} X)$（见 4.1 节）。标签传播（Label Propagation）把这一思路推广到半监督设定。特别地，奠基性论文（Zhu and Ghahramani; Zhu et al., 2003）考虑了如下优化问题
$$ \widehat{X}^{LP} = \underset{\substack{X \in \mathbb{R}^{n \times K} \\ X_{\ell\cdot} = S_{\ell\cdot}}}{\arg\min}\ \mathrm{Tr}(X^T L X). \tag{5.3} $$
约束 $X_{\ell\cdot} = S_{\ell\cdot}$ 迫使解 $\widehat{X}^{LP}$ 在标注节点上等于预言机的预测。我们首先注意到，如果预言机带噪声，这一硬约束可能并不合适，因为它把解在被错误标注的节点上推向错误的分类。此外，谱聚类中防止无监督谱方法得到平凡解的约束 $X^T X = I_K$ 或 $X^T D X = I_K$（同样见 4.1 节）在这里是缺失的。因此，优化问题 (5.3) 仅依靠硬约束 $X_{\ell\cdot} = S_{\ell\cdot}$ 来防止退化解。我们后面将看到，当标注数据量很小时这会成为一个问题。从好的方面看，下面的引理给出了 $\widehat{X}^{LP}$ 的闭式表达。
优化问题 (5.3) 的解 $\widehat{X}^{LP}$ 由下式给出
$$ \left\{ \begin{array}{ll} \widehat{X}_{\ell\cdot}^{LP} & = S_{\ell\cdot}, \\ \widehat{X}_{u\cdot}^{LP} & = \left( I_{|u|} - (D^{-1} A)_{uu} \right)^{-1} (D^{-1} A)_{u\ell}\, S_{\ell\cdot}, \end{array} \right. \tag{5.4} $$其中 $I_{|u|}$ 是 $|u| \times |u|$ 的单位矩阵。
约束 $X_{\ell\cdot} = S_{\ell\cdot}$ 可以改写如下：
$$ \begin{array}{l} X_{\ell\cdot} = S_{\ell\cdot} \iff \forall k \in [K]\ \forall i \in \ell : (X_{ik} - S_{ik})^2 = 0 \\ \iff \displaystyle\sum_{k=1}^{K} \sum_{i=1}^{n} \big( \mathbf{1}(i \in \ell) X_{ik} - S_{ik} \big)^2 = 0 \\ \iff \mathrm{Tr}\left( (I_{\ell} X - S)^T (I_{\ell} X - S) \right) = 0. \end{array} $$因此，与最小化问题 (5.3) 相关联的一个拉格朗日函数是
$$ \mathcal{H} = \mathrm{Tr}\left( X^T L X + \mu (I_{\ell} X - S)^T (I_{\ell} X - S) \right), $$其中 $\mu$ 是拉格朗日乘子。对每个 $k \in [K]$，关于 $X_{\cdot k}$ 求导得到
$$ \frac{\partial \mathcal{H}}{\partial X_{\cdot k}} = 2 \left( L X + \mu (I_{\ell} X - S) \right). $$令该导数为零，得到
$$ (L + \mu I_{\ell}) \widehat{X}^{LP} = \mu S, $$而关于 $\mu$ 求导则给出约束 $I_{\ell} \widehat{X}^{LP} = S$。使用块记号，我们可以写出
$$ LX = \binom{L_{\ell\ell} \quad L_{\ell u}}{L_{u\ell} \quad L_{uu}} \binom{X_{\ell\cdot}}{X_{u\cdot}} = \binom{L_{\ell\ell} X_{\ell\cdot} + L_{\ell u} X_{u\cdot}}{L_{u\ell} X_{\ell\cdot} + L_{uu} X_{u\cdot}}, $$因此
$$ \left\{ \begin{array}{ll} L_{\ell\ell} \widehat{X}_{\ell\cdot}^{LP} + L_{\ell u} \widehat{X}_{u\cdot}^{LP} + \mu \widehat{X}_{\ell\cdot}^{LP} & = \mu S_{\ell\cdot}, \\ L_{u\ell} \widehat{X}_{\ell\cdot}^{LP} + L_{uu} \widehat{X}_{u\cdot}^{LP} & = 0. \end{array} \right. $$约束 $\widehat{X}_{\ell\cdot}^{LP} = S_{\ell\cdot}$ 给出解
$$ \left\{ \begin{array}{ll} \widehat{X}_{\ell\cdot}^{LP} & = S_{\ell\cdot}, \\ \widehat{X}_{u\cdot}^{LP} & = (L_{uu})^{-1} L_{u\ell}\, \widehat{X}_{\ell\cdot}^{LP}. \end{array} \right. $$最后，注意到由于 $L = D - A$ 且 $D$ 是对角矩阵，我们有 $L_{u\ell} = -A_{u\ell}$ 以及 $(L_{uu})^{-1} = \left( (D(I_n - D^{-1}A))_{uu} \right)^{-1} = \left( I_{|u|} - (D^{-1}A)_{uu} \right)^{-1} (D_{uu})^{-1}$。最后，$(D_{uu})^{-1} A_{u\ell} = (D^{-1} A)_{u\ell}$（因为 $D$ 是对角矩阵），证明完毕。
查看学习笔记校勘后完整证明（自由变量分块法）我们从引理 5.2 的证明中注意到
$$ LX_{ik} = \left\{ \begin{array}{ll} S_{ik}, & \text{若 } i \in \ell, \\ 0, & \text{其他}. \end{array} \right. \tag{5.5} $$
最后，我们给出下面的算法 8。由公式 (5.4) 计算 $\widehat{X}$ 需要求解一个 $|u| \times |u|$ 的线性方程组，其时间复杂度一般为 $O(|u|^3)$（若网络稀疏则更低）。接下来的段落介绍一种以去中心化、迭代方式计算 $\widehat{X}$ 的方法。
输入：图 $G$，预言机 $S$。
输出：节点标注 $\hat{z} = (\hat{z}_1, \dots, \hat{z}_n) \in [K]^n$。
过程：
- 令 $\widehat{X}$ 如公式 (5.4) 所示；
- 对 $i = 1, \ldots, n$，令 $\hat{z}_i$ 由分类规则 (5.2) 定义。
返回：$\hat{z}$。
作为预言机标签传播的解释（Interpretation as a propagation of the oracle labels）
我们首先给每个节点 $i$ 赋予一个 $1 \times K$ 向量 $X_{i\cdot}^{(0)} \in \mathbb{R}^{1 \times K}$，它等于预言机对节点 $i$ 的预测 $S_{i\cdot}$。然后，在每个时间步 $t$，对 $X$ 的更新按如下方式进行：
- 若 $i \in \ell$，则 $X_{i\cdot}^{(t+1)} = X_{i\cdot}^{(t)}$（不做更新）；
- 若 $i \notin \ell$，则 $X_{i\cdot}^{(t+1)}$ 取为节点 $i$ 各邻居的 $X_{j\cdot}^{(t)}$ 的平均，即 $X_{i\cdot}^{(t+1)} = \frac{1}{d_i} \sum_{j=1}^{n} A_{ij} X_{j\cdot}^{(t)}$。
这可以解释为预言机信息沿图的传播，也可以解释为部分智能体状态固定的共识算法（consensus algorithm）。标注节点的值始终等于预言机信息，而未标注节点会对邻居的值采样并做局部平均。用矩阵形式，可以把这一过程写成：
$$ X_{i\cdot}^{(t+1)} = \left\{ \begin{array}{ll} X_{i\cdot}^{(t)}, & \text{若 } i \in \ell, \\ \left( D^{-1} A X^{(t)} \right)_{i\cdot}, & \text{其他}. \end{array} \right. $$
使用块记号可得
$$ \left\{ \begin{array}{rcl} X_{u\cdot}^{(t+1)} & = & (D^{-1} A)_{uu} X_{u\cdot}^{(t)} + (D^{-1} A)_{u\ell} X_{\ell\cdot}^{(t)}, \\ X_{\ell\cdot}^{(t+1)} & = & X_{\ell\cdot}^{(t)}, \end{array} \right. $$
初始条件为 $X^{(1)} = S$。由于矩阵 $(D^{-1} A)_{uu}$ 是次随机的（substochastic），$X^{(t)}$ 收敛到满足如下方程组的 $X^{\infty}$
$$ \left\{ \begin{array}{rl} X_{u\cdot}^{\infty} & = (D^{-1} A)_{uu} X_{u\cdot}^{\infty} + (D^{-1} A)_{u\ell} X_{\ell\cdot}^{\infty}, \\ X_{\ell\cdot}^{\infty} & = S_{\ell\cdot}, \end{array} \right. $$
其解为
$$ \left\{ \begin{array}{rl} X_{u\cdot}^{\infty} & = \left( I_{|u|} - (D^{-1} A)_{uu} \right)^{-1} (D^{-1} A)_{u\ell} S_{\ell\cdot}, \\ X_{\ell\cdot}^{\infty} & = S_{\ell\cdot}, \end{array} \right. $$
这与标签传播的解 (5.4) 是同一表达式。
随机游走解释（Random walk interpretation）
设 $y_1, y_2, \ldots$ 为图上的随机游走，游走者从节点 $i$ 跳到节点 $j$，其中 $j$ 是均匀随机选取的 $i$ 的邻居。转移概率由
$$ p_{ij} = \mathbb{P}(y_{t+1} = j \,|\, y_t = i) = \frac{A_{ij}}{d_i}, $$
给出，其中 $d_i$ 是节点 $i$ 的度。特别地，$p_{ij} = (D^{-1} A)_{ij}$，我们注意到 $P = D^{-1} A$ 就是转移概率矩阵。
假设游走从节点 $i$ 出发，一旦到达某个标注节点就结束游走。记最终节点为 $y_{\mathrm{end}}$。我们用 $\widehat{X}_{ik}$ 表示 $S_{y_{\mathrm{end}}, k} = 1$ 的概率，即预言机把 $y_{\mathrm{end}}$ 指派到社区 $k$ 的概率。于是有
$$ \widehat{X}_{ik} = \mathbb{P}\left( S_{y_{\mathrm{end}}, k} = 1 \,|\, y_1 = i \right). $$
特别地，若 $i \in \ell$，则 $y_{\mathrm{end}} = i$，且
$$ \widehat{X}_{ik} = \left\{ \begin{array}{ll} 1, \quad & \text{若 } S_{ik} = 1, \\ 0, \quad & \text{其他}, \end{array} \right. $$
这等价于 $\widehat{X}_{\ell\cdot} = S_{\ell\cdot}$。由马尔可夫性，对任何节点 $i$ 我们还有
$$ \mathbb{P}\left( S_{y_{\mathrm{end}}, k} = 1 \,|\, y_1 = i \right) = \sum_{j=1}^{n} \mathbb{P}\left( S_{y_{\mathrm{end}}, k} = 1 \,|\, y_1 = j \right) p_{ij}, $$
因此
$$ \widehat{X} = P \widehat{X}. $$
把这一方程写成块形式，并与先前得到的约束 $\widehat{X}_{\ell\cdot} = S_{\ell\cdot}$ 结合，得到
$$ \widehat{X}_{u\cdot} = \left( I_{|u|} - (D^{-1} A)_{uu} \right)^{-1} (D^{-1} A)_{u\ell} S_{\ell\cdot}. $$
于是，我们再次得到与标签传播解 (5.4) 相同的表达式。
作为热方程的解释（Interpretation as a heat equation）
现在让我们把标签传播解释为热方程的解。各向同性材料温度 $T$ 的演化由热方程
$$ \frac{\partial T}{\partial t} = \alpha \Delta T, $$
支配，其中 $\Delta$ 是拉普拉斯算子，$\alpha$ 是材料的热导率。在平衡态，我们简单地有 $\Delta T = 0$。
预言机 $S$ 扮演热源（heat bath）的角色。更确切地说，我们先固定一个 $k \in [K]$。标注节点 $i \in \ell$ 的行为如同热源，其温度 $T_{ik}$ 保持常数并等于 $S_{ik} \in \{0, 1\}$。未标注节点的温度则会变化，因为热交换沿图的边发生，且与边两端点的温度差成正比。因此，
$$ \forall i \in \ell : \ T_{ik} = S_{ik}, $$
$$ \forall i \in u : \ \frac{\partial T_{ik}}{\partial t} = \sum_{j=1}^{n} A_{ij} (T_{jk} - T_{ik}). $$
由于 $\sum_{j=1}^{n} A_{ij} (T_{jk} - T_{ik}) = (A T_{\cdot k})_i - d_i T_{ik} = -(L T_{\cdot k})_i$，温度 $T_{\cdot k}$ 在平衡态满足
$$ \forall i \in u : \ LT_{ik} = 0, $$
而对任何标注节点 $i$ 有 $T_{ik} = S_{ik}$。这可以改写为
$$ \left\{ \begin{array}{ll} (LT)_{u\cdot} & = 0, \\ T_{\ell\cdot} & = S_{\ell\cdot}. \end{array} \right. $$
上述方程组等价于公式 (5.5)，其解等于标签传播的解 (5.4)（见引理 5.2）。
5.1.2 标签扩散（Label Spreading）
标签扩散（Label Spreading）这一 SSL 方法（Zhou et al., 2004）基于优化问题
$$ \widehat{X}^{LS} = \underset{X \in \mathbb{R}^{n \times K}}{\arg\min}\ C^{LS}(X), $$
其中代价函数 $C^{LS}$ 定义为
$$ C^{LS}(X) = \mathrm{Tr}\left( X^T \mathcal{L} X + \lambda (X - S)^T (X - S) \right). $$
经过简单的线性代数变形，我们有
$$ C^{LS}(X) = \sum_{k=1}^{K} \left( \frac{1}{2} \sum_{i, j} a_{ij} \left( \frac{x_{ik}}{\sqrt{d_i}} - \frac{x_{jk}}{\sqrt{d_j}} \right)^2 + \lambda \sum_{i=1}^{n} (x_{ik} - s_{ik})^2 \right), $$
其中 $d_i$ 表示节点 $i$ 的度。
参数 $\lambda$ 在解 $\widehat{X}^{LS}$ 在图上的平滑性与解贴近预言机信息 $S$ 的程度之间施加权衡。与标签传播方法的不同之处在于，解的平滑性现在由包含节点度归一化的项 $\mathrm{Tr}(X^T \mathcal{L} X)$ 施加。
与标签传播的情形一样，$\widehat{X}^{LS}$ 也有闭式表达。即对每个 $k \in [K]$，我们有
$$ \frac{1}{2} \frac{\partial C^{LS}}{\partial X_{\cdot k}} = \mathcal{L} X_{\cdot k} + \lambda (X_{\cdot k} - S_{\cdot k}), $$
因此
$$ \begin{array}{l} \widehat{X}_{\cdot k}^{LS} = (\lambda I + \mathcal{L})\, \lambda S_{\cdot k} \\ \ = \left( (1 + \lambda) I - D^{-1/2} A D^{-1/2} \right)^{-1} \lambda S_{\cdot k} \\ \ = \dfrac{\lambda}{1 + \lambda} \left( I - \dfrac{1}{1 + \lambda} D^{-1/2} A D^{-1/2} \right)^{-1} S_{\cdot k}. \end{array} $$
于是，
$$ \widehat{X}^{LS} = (1 - \alpha) \left( I - \alpha D^{-1/2} A D^{-1/2} \right)^{-1} S, $$
其中 $\alpha = \frac{\lambda}{1 + \lambda} \in (0, 1)$。这就给出了算法 9。
输入：图 $G$，预言机 $S$，参数 $\alpha \in (0, 1)$。
输出：节点标注 $\hat{z} = (\hat{z}_1, \dots, \hat{z}_n) \in [K]^n$。
过程：
- 计算归一化邻接矩阵 $\mathcal{A} = D^{-1/2} A D^{-1/2}$；
- 令 $\widehat{X}^{LS}$ 为 $(I - \alpha \mathcal{A}) \widehat{X}^{LS} = (1 - \alpha) S$ 的解；
- 对 $i \in [n]$，令 $\hat{z}_i$ 由分类规则 (5.2) 定义。
返回：$\hat{z}$。
5.1.3 广义拉普拉斯（Generalized Laplacian）
作为标签传播与标签扩散方法的后续工作，Avrachenkov et al., 2012 提出了一类一般的代价函数
$$ C^{GL}(X) = \mathrm{Tr}\left( X^T D^{\sigma - 1} L D^{\sigma - 1} X + \lambda (X - S)^T D^{2\sigma - 1} (X - S) \right), $$
其中 $\lambda > 0$ 与 $0 \leq \sigma \leq 1$ 是两个超参数。最小化问题
$$ \widehat{X}^{GL} := \underset{X \in \mathbb{R}^{n \times K}}{\arg\min}\ C^{GL}(X) $$
的解由
$$ \widehat{X}^{GL} = (1 - \alpha) \left( I_n - \alpha D^{-\sigma} A D^{\sigma - 1} \right)^{-1} S, $$
给出，其中 $\alpha = \lambda / (1 + \lambda)$。由于这里的计算与前几节中的计算相似，我们将其省略，并请读者参考 (Avrachenkov et al., 2012, Proposition 2) 了解细节。选取不同的 $\sigma$ 可以得到不同的归一化方式。特别地，
- $\sigma = 1$ 对应标签传播；
- $\sigma = 1/2$ 对应标签扩散；
- $\sigma = 0$ 对应基于 PageRank 的方法。
查看学习笔记对被省略计算（由 $C^{GL}$ 的驻点方程推出闭式解）的补全
5.1.4 基于拉普拉斯矩阵方法的数值性能（Numerical Performance of the Laplacian-based Methods）
Label Spreading 超参数 α 的选择（Choice of hyper-parameter α for Label Spreading）
我们首先考察 $\alpha$ 对分类性能的影响。我们选取两个此前看到无监督谱聚类在其上失败的数据集：DBLP 与 Cora。我们让 2% 的节点被预言机标注，并在图 5.1 中画出精度随 $\alpha$ 变化的曲线（蓝色曲线）。我们看到，精度随 $\alpha$ 增大而上升，但当 $\alpha$ 过于接近 1 时会突然下降。我们还注意到，可以通过观察预测划分的模块度（modularity）（图 5.1 中红色曲线）来选择最优的 $\alpha$，因为模块度与精度紧密相随。
噪声预言机（Noisy oracle）
我们现在研究噪声对分类性能的影响。仍使用同样的两个数据集，但这次标注节点占 5%。我们把噪声定义为预言机所犯错误的比例。结果画在图 5.2 中。不出所料，噪声会降低分类性能。
小标注数据量（Small amount of labelled data）
我们结束本节时强调小标注数据量问题的重要性。图 5.3 显示，当每类的标注节点数过少时，分类精度会严重下降。
5.2 小标注数据量下的学习（Learning with Small Amount of Labelled Data）
5.2.1 小标注数据的问题（The Problem of Small Labelled Data）
数值实验表明，在标注率非常低时，SSL 方法的性能会变差。我们将用标签传播算法的随机游走解释来说明这一现象（关于标签传播的更多细节见 5.1.1 节）。
设 $y_1, \ldots, y_t, \ldots$ 为图上从节点 $i$ 出发的随机游走。令 $\tau = \inf_{t \geq 1} \{ y_t \in \ell \}$ 为游走首次到达标注节点的时刻，并回忆 $\widehat{X}_{ik}^{LP} = \mathbb{P}(S_{y_{\tau}, k} = 1 \,|\, y_1 = i)$。换言之，$\widehat{X}_{ik}$ 是游走（从节点 $i$ 出发）到达的第一个标注节点带有标签 $k$ 的概率。
如果标注节点很少而图很大，那么时间 $\tau$ 会很大。特别地，若 $\tau$ 大于游走的混合时间（mixing time），则 $y_{\tau}$ 的分布非常接近随机游走的平稳分布（亦称不变分布）$\pi$，即
$$ \pi_j = \frac{d_j}{\sum_{s=1}^{n} d_s}. $$
这意味着链已经"忘记"了它的出发点 $i$，于是 $\widehat{X}_{ik}^{LP}$ 是一个与 $i$ 无关的常数，这就使分类的目标落空。
让我们把这一直觉形式化，并尝试缓解这个问题。我们首先注意到，对 $k \leq \tau$，
$$ \mathbb{E}\left[ X_{y_k} - X_{y_{k-1}} \,|\, y_{k-1} \right] = \frac{1}{d(y_{k-1})} LX_{y_{k-1}} = 0, $$
因为在未标注节点上 $LX = 0$（见公式 (5.5)）。于是，$X_{y_1}, \cdots, X_{y_k}, \cdots$ 是一个鞅（martingale）。由于 $\tau$ 是几乎当然有界的停时，Doob 最优停止定理意味着
$$ \mathbb{E}\left[ X_{y_0} \right] = \mathbb{E}\left[ X_{y_{\tau}} \right]. $$
由于 $y_0 = i$ 且 $y_{\tau} \in \ell$，我们有 $\mathbb{E}[X_{y_0}] = X_i$ 且 $X_{y_{\tau}} = S_{y_{\tau}}$，因此
$$ X_{ik} \approx \sum_{j \in \ell} \pi_j S_{jk} = \frac{\sum_{j \in \ell} d_j S_{jk}}{\sum_{j=1}^{n} d_j}. \tag{5.6} $$
于是，$\widehat{X}_{ik}^{LP}$ 的一阶近似对所有未标注节点 $i$ 都相同，潜在的差异只能来自二阶项。因此对标签传播的第一项改进是把分类规则 (5.2) 替换为
$$ \hat{z}_i = \underset{k \in \{1, \ldots, k\}}{\arg\max} \left( \widehat{X}_{ik} - c_k \right), $$
其中 $c_k = \frac{\sum_{j \in \ell} d_j S_{jk}}{\sum_{j \in \ell} d_j}$。等价地，可以把公式 (5.5)"平移"并求解
$$ LX_{ik} = \left\{ \begin{array}{ll} S_{ik} - c_k, & \text{若 } i \in \ell, \\ 0, & \text{其他}. \end{array} \right. $$
把上面的方程改写为
$$ LX_{ik} = \sum_{j \in \ell} d_j \left( S_{jk} - c_k \right) \delta_{ij}, $$
我们就可以把它解释为一个热方程，其中热源与热汇（heat sinks）被放置在标注节点上。
5.2.2 Poisson 学习（Poisson Learning）
令 $\bar{s}_k = \frac{\sum_{i \in \ell} S_{ik}}{|\ell|}$。沿用上述讨论，Calder et al., 2020 提出考虑方程
$$ LX_{ik} = \sum_{j \in \ell} \left( S_{jk} - \bar{s}_k \right) \delta_{ij}, \tag{5.7} $$
并满足 $\sum_{i=1}^{n} d_i X_{ik} = 0$。等价地，这相当于求解如下优化问题（Calder et al., 2020, Theorem 2.3）
$$ \underset{\substack{X \in \mathbb{R}^{n \times K} \\ \sum_{i=1}^{n} d_i X_{ik} = 0}}{\arg\min}\ \mathrm{Tr}\left( X^T L X \right) - (S - \bar{S})^T X, $$
其中
$$ \bar{S}_{ik} = \left\{ \begin{array}{ll} \bar{s}_k & \text{若 } i \in \ell, \\ 0, & \text{其他}. \end{array} \right. $$
特别地，标签传播通过施加硬约束来处理标注数据，而 Poisson 学习（Poisson learning）则是在能量函数中加入一个损失项。
随机游走解释（Random walk interpretation）
由于标注节点现在是热方程的源与汇，随机游走解释也有所不同。我们用 $y_1^j, \ldots, y_t^j, \ldots$ 表示图上从节点 $j \in \ell$ 出发的随机游走。每当随机游走到达节点 $i$ 时，我们记录平移后的标签 $S_{j\cdot} - \bar{S}_{j\cdot}$。这定义了量
$$ X_{ik}^{(T)} = \mathbb{E}\left[ \sum_{t=0}^{T} \frac{1}{d_i} \sum_{j \in \ell} \left( S_{jk} - \bar{S}_{jk} \right) \mathbf{1}\left( y_t^j = i \right) \right]. $$
下面的引理给出 $X^{(T)}$ 的一个迭代表达式。
我们有
$$ X_{ik}^{(T+1)} = X_{ik}^{(T)} + \frac{1}{d_i} \left( \sum_{j \in \ell} \left( S_{jk} - \bar{S}_{jk} \right) \delta_{ij} - \left( L X^{(T)} \right)_{ik} \right). $$进一步，假设 $G$ 是连通的，且由随机游走诱导的马尔可夫链是非周期的。那么 $\lim_{T \to \infty} X^{(T)} = X$，其中 $X$ 是 Poisson 方程 (5.7) 的唯一解。
我们首先写出
$$ X_{ik}^{(T+1)} = \sum_{j \in \ell} \left( S_{jk} - \bar{S}_{jk} \right) G_T(i, j), \tag{5.8} $$其中 $G_T(i, j) = \frac{1}{d_i} \mathbb{E}\left[ \sum_{t=0}^{T} \mathbf{1}\left( y_t^j = i \right) \right] = \frac{1}{d_i} \sum_{t=0}^{T} \mathbb{P}\left( y_t^j = i \right)$ 是归一化 Green 函数。利用
$$ \mathbb{P}\left( y_t^j = i \right) = \sum_{u=1}^{n} \mathbb{P}\left( y_t^j = i \,|\, y_{t-1}^j = u \right) \mathbb{P}\left( y_{t-1}^j = u \right), $$我们有
$$ \begin{array}{l} d_i G_T(i, j) = \displaystyle \delta_{ij} + \sum_{t=1}^{T} \sum_{u=1}^{n} \frac{w_{ui}}{d_u} \mathbb{P}\left( y_{t-1}^j = u \right) \\ \ = \displaystyle \delta_{ij} + \sum_{u=1}^{n} \frac{w_{ui}}{d_u} \sum_{t=0}^{T-1} \mathbb{P}\left( y_t^j = u \right) \\ \ = \displaystyle \delta_{ij} + \sum_{u=1}^{n} w_{ui} G_{T-1}(u, j), \end{array} $$因此
$$ d_i \left( G_T(i, j) - G_{T-1}(i, j) \right) + LG_{T-1}(i, j) = \delta_{ij}. $$与公式 (5.8) 结合，这就建立了
$$ d_i \left( X_{ik}^{(T)} - X_{ik}^{(T-1)} \right) = \sum_{j \in \ell} \left( S_{jk} - \bar{S}_{jk} \right) \delta_{ij} - \left( L X^{(T)} \right)_{ik}. $$然后，把该方程两端对 $i = 1, \cdots, n$ 求和，得到
$$ \sum_{i=1}^{n} d_i X_{ik}^{(T)} = \sum_{i=1}^{n} d_i X_{ik}^{(T-1)}, $$因此对所有 $T$ 都有 $\sum_{i=1}^{n} d_i X_{ik}^{(T)} = \sum_{i=1}^{n} d_i X_{ik}^{(0)}$。由于
$$ d_i X_{ik}^{(0)} = \sum_{j \in \ell} \left( S_{jk} - \bar{S}_{jk} \right) \delta_{ij}, $$我们得到 $\sum_{i} d_i X_{ik}^{(T)} = 0$。最后，令 $V_{ik}^{(T)} = d_i (X_{ik}^{(T)} - X_{ik})$。我们有
$$ V_{ik}^{(T)} = \sum_{j=1}^{n} \frac{w_{ij}}{d_j} V_{jk}^{(T-1)}, $$且对所有 $T$ 都有 $\sum_{j=1}^{n} V_{jk}^{(T)} = 0$。由于随机游走是非周期的且图是连通的，
$$ \lim_{T \to \infty} V_{ik}^{(T)} = \pi_i \sum_{j=1}^{n} V_{jk}^{(0)} = 0, $$其中 $\pi_i = \frac{d_i}{\sum_{j=1}^{n} d_j}$ 是链的平稳分布。
查看学习笔记完整证明（含逐步展开与校勘讨论）事实上，引理 5.3 还提供了一种计算该解的迭代数值过程。该过程在算法 10 中正式描述。
输入：图 $G$，预言机 $S \in \{0, 1\}^{n \times K}$，迭代次数 $T$。
输出：节点标注 $\hat{z} \in [K]^n$。
过程：
- 令 $L$ 为图的标准拉普拉斯矩阵，$D$ 为图的度矩阵；
- 令 $\ell$ 为标注节点集，并令 $\bar{S} = S\, \mathrm{diag}(\bar{s})$，其中 $\bar{s} = (\bar{s}_1, \ldots, \bar{s}_K)$，$\bar{s}_k = \frac{1}{|\ell|} \sum_{i \in \ell} S_{i\ell}$；
- 对 $t = 1, \cdots, T$，执行：$X \longleftarrow X + D^{-1} \left( S - \bar{S} - LX \right)$；
- 对 $i = 1, \ldots, n$，令 $\hat{z}_i$ 由分类规则 (5.2) 定义。
返回：$\hat{z}$。
5.2.3 数值实验（Numerical Experiments）
为了评估 Poisson 学习在标注节点极少的情形下的性能，我们重现 Calder et al., 2020 的结果。他们考虑 MNIST（LeCun et al., 1998）与 Fashion-MNIST（Xiao et al., 2017）数据集，并在其上训练自编码器（auto-encoders）以从数据中提取重要特征。更确切地说，他们分别使用了具有 3 个全连接层、大小为 (784, 400, 20) 与 (784, 400, 30) 的变分自编码器（variational auto-encoders），后接对称定义的解码器（Kingma and Welling, 2014）。自编码器在每个数据集上训练 100 轮（epochs）。然后，以高斯权重 $w_{ij} = \exp\left( -4 \| x_i - x_j \|^2 / \sigma_i^2 \right)$ 构建一个 10 最近邻图，其中 $x_i$ 是图像 $i$ 的潜变量，$\sigma_i$ 是 $x_i$ 与其第 10 最近邻之间的距离。结果如图 5.4 所示。特别地，即使每类只有一个标注节点，Poisson 学习的性能仍然极高。
5.3 其他方法（Other Methods）
5.3.1 约束谱聚类（Constrained Spectral Clustering）
该方法的目标是把半监督信息直接融入谱方法。具体地，由预言机信息 $S$，我们可以构造如下的必须连接/不可连接（must-link/cannot-link）矩阵 $Q$：
$$ Q_{ij} = Q_{ji} = \left\{ \begin{array}{ll} 1, & \text{若 } i, j \in \ell \text{ 且 } S_{i\cdot} = S_{j\cdot}, \\ -1, & \text{若 } i, j \in \ell \text{ 且 } S_{i\cdot} \neq S_{j\cdot}, \\ 0, & \text{其他}. \end{array} \right. $$
我们注意到，必须连接/不可连接信息也可以直接提供给我们。事实上，对专家来说，断定两个物品是否相似往往比把物品归入各个类别更容易。
对于隶属矩阵 $Z \in \mathcal{Z}_{N,K}$，量
$$ \mathrm{Tr}\left( Z^T Q Z \right) = \sum_{k=1}^{K} \sum_{i, j} Q_{ij} Z_{ik} Z_{jk} $$
度量隶属矩阵 $Z$ 对预言机信息的遵从程度。事实上，若 $Q_{ij} = 1$ 且 $Z$ 把节点 $i, j$ 分入同一簇，该量增加 1；若 $Q_{ij} = -1$ 但 $i$ 和 $j$ 被分入同一簇，该量减少 1。因此，$\mathrm{Tr}(Z^T Q Z)$ 等于被满足的必须连接/不可连接约束的数目减去被违反的约束的数目。与其要求 $Q$ 中所有约束都被满足，我们可以施加下界
$$ \mathrm{Tr}\left( Z^T Q Z \right) \geq \alpha $$
其中 $\alpha \geq 0$ 为某个常数。这样的约束可以直接并入归一化谱聚类的最小化问题，并导出如下优化问题
$$ \begin{array}{l} \displaystyle \arg\min_{U \in \mathbb{R}^{n \times K}}\; \mathrm{Tr}\left( U^T L U \right), \\ \qquad U^T D U = I_K \\ \mathrm{Tr}\left( U^T Q U \right) \geq \alpha \end{array} $$
经过变量替换 $X = D^{1/2} U$ 后，它可以改写为
$$ \begin{array}{l} \displaystyle \arg\min_{X \in \mathbb{R}^{n \times K}}\; \mathrm{Tr}\left( X^T \mathcal{L} X \right), \\ \qquad X^T X = I_K \\ \mathrm{Tr}\left( X^T \bar{Q} X \right) \geq \alpha \end{array} \tag{5.9} $$
其中 $\bar{Q} = D^{-1/2} Q D^{-1/2}$。
设 $X$ 为 (5.9) 的解。则 $X$ 的各行是广义特征值问题 $\mathcal{L} X_{\cdot k} = \lambda \left( \bar{Q} - \beta \right) X_{\cdot k}$ 的解，其中 $\beta$ 为某个常数。
最小化问题 (5.9) 的拉格朗日函数为
$$ \mathrm{Tr}\left( X^T \mathcal{L} X \right) - \lambda \left( \mathrm{Tr}\left( X^T \bar{Q} X \right) - \alpha \right) - \mathrm{Tr}\left( \Gamma^T \left( X^T X - I_K \right) \right), $$其中 $\lambda \in \mathbb{R}$ 是与约束 $\mathrm{Tr}(X^T \bar{Q} X) \geq \alpha$ 相应的拉格朗日乘子，$\Gamma \in \mathbb{R}^{K \times K}$ 是一个对称矩阵，其元素是与约束 $X^T X = I_K$ 相应的乘子。注意，在相差一个基变换的意义下，我们可以选取 $\Gamma$ 为对角矩阵。于是，根据 KKT 定理（Kuhn, 1982），问题 (5.9) 的任何可行最优解都必须满足
$$ \begin{array}{rl} \text{平稳性（stationarity）：} & \mathcal{L} X - \lambda \bar{Q} X - X \Gamma = 0, \\ \text{原始可行性（primal feasibility）：} & \mathrm{Tr}\left( X^T \bar{Q} X \right) \geq \alpha \text{ 且 } X^T X = I_K, \\ \text{对偶可行性（dual feasibility）：} & \lambda \geq 0, \\ \text{互补松弛（complementary slackness）：} & \lambda \left( \mathrm{Tr}\left( X^T \bar{Q} X \right) - \alpha \right) = 0. \end{array} $$互补松弛要求意味着要么 $\lambda = 0$，要么 $\mathrm{Tr}(X^T \bar{Q} X) = \alpha$。若 $\lambda = 0$，则平稳性要求会把问题化为标准的（无约束）谱聚类。因此 $\lambda \neq 0$，从而 $\mathrm{Tr}(X^T \bar{Q} X) = \alpha$，而 KKT 条件变为
$$ \begin{array}{r} \mathcal{L} X - \lambda \bar{Q} X - X \Gamma = 0, \\ \mathrm{Tr}\left( X^T \bar{Q} X \right) = \alpha, \\ X^T X = I_K, \\ \lambda > 0. \end{array} $$由于 $\Gamma$ 是对角矩阵，第一个方程等价于
$$ (\mathcal{L} - \Gamma_{kk}) X_{\cdot k} = \lambda \bar{Q} X_{\cdot k}, $$对给定的 $\Gamma_{kk}$，这是一个广义特征值问题。令 $\beta = -\frac{\Gamma_{kk}}{\lambda}$ 即完成证明。
查看学习笔记的条件性 KKT 推导基于引理 5.4，并遵循 Wang and Davidson, 2010 与 Wang et al., 2014，我们提出如下过程：
- 求广义特征值问题 $\mathcal{L} v_k = \lambda_k \left( \bar{Q} - \beta I_n \right) v_k$ 中与 $\lambda_k > 0$ 相应的解向量 $v_1, \cdots, v_p$；
- 给定所有可行特征向量 $v_1, \cdots, v_p$，按最小化 $v^T \mathcal{L} v$ 选出前 $K - 1$ 个，并令这 $K - 1$ 个向量构成 $X$ 的各列。
由于 $\beta < \lambda_K$，该广义特征值问题至少有 $K - 1$ 个与正特征值相应的解。此外，由于 $\mathcal{L}$ 与 $\bar{Q} - \beta I_n$ 都是埃尔米特（Hermitian）矩阵，这些解都是实向量。最后，这个过程是合理的：若 $(K - 1)\beta < \alpha$，则 $X$ 满足引理 5.4 证明中导出的 KKT 条件。事实上，由于 $\mathcal{L}$ 半正定，我们有 $v^T \mathcal{L} v \geq 0$，且等号仅在 $v \propto 1_n$ 时成立。因此 $\mathrm{Tr}(X^T \mathcal{L} X) > 0$。此外，$\mathrm{Tr}(X^T \mathcal{L} X) = \sum_{k=0}^{K} X_{\cdot k}^T \mathcal{L} X_{\cdot k} = \sum_{k} \lambda_k X_{\cdot k} \left( \bar{Q} - \beta I_n \right) X_{\cdot k} \geq \mathrm{Tr}\left( X^T \bar{Q} X \right) - (K - 1)\beta$，且 $\mathrm{Tr}\, B < \alpha$。我们把这一过程总结在算法 11 中。
输入：图 $G$，必须连接/不可连接矩阵 $Q$，簇数 $K$，参数 $\beta$。
输出：节点标注 $\hat{z} \in [K]^n$。
过程：令 $\mathcal{L}$ 为 $G$ 的归一化拉普拉斯矩阵，并令 $\bar{Q} = D^{-1/2} Q D^{-1/2}$。
若 $\beta \geq \lambda_{K-1}(\bar{Q})$，则
返回：$\varnothing$。
否则
- 令 $v_1, \cdots, v_p$ 为广义特征值问题 $\mathcal{L} v = \lambda \left( \bar{Q} - \beta \right) v$ 与特征值 $\lambda > 0$ 相应的解；
- 令 $V^{*} = \arg\min_{V \in \mathbb{R}^{n \times K-1}} \mathrm{Tr}\left( V^T \mathcal{L} V \right)$，其中 $V$ 的各列取自前面算出的可行特征向量的一个子集。
返回：$\hat{z} = \mathrm{k\text{-}means}(D^{-1/2} V^{*}, K)$。
5.3.2 拉普拉斯正则化（Laplacian Regularization）
前面的方法都是最小化一个代价函数，其中包含一个平滑项 $\mathrm{Tr}(X^T M X)$（$M$ 通常是图的（标准或归一化）拉普拉斯矩阵）、一个惩罚 $X_{\ell\cdot}$ 与 $S_{\ell\cdot}$ 之间任何差异的惩罚项，以及可能还有一个正则化项。
相比之下，拉普拉斯正则化（Laplacian regularization）（Belkin and Niyogi, 2002）通过约束向量 $X$ 属于由图拉普拉斯 $L$ 的、与 $p$ 个最小特征值相应的特征向量所张成的特征子空间来施加平滑性。然后，它寻找这些特征向量的、使 $X$ 与 $S$ 在标注节点上的均方误差最小的线性组合。
设 $v_1, \ldots, v_p$ 为 $L$ 的与 $p$ 个最小特征值相应的特征向量，并归一化使 $\|v_i\|_2^2 = 1$。解 $X = (x_{ik})_{i \in [n], k \in [K]}$ 写成 $x_{ik} = \sum_{q=1}^{p} b_{qk} v_q(i)$，其中 $v_q(i)$ 表示特征向量 $v_q$ 的第 $i$ 个分量。写成矩阵形式即 $X = V B$，其中 $V = (v_1, \ldots, v_p)$、$B \in \mathbb{R}^{p \times K}$。标注节点与其相应预言机取值之间的均方误差则为
$$ \mathrm{MSE}\left( X_{\ell\cdot}, S_{\ell\cdot} \right) = \sum_{k=1}^{K} \sum_{i \in \ell} \left( x_{ik} - s_{ik} \right)^2 = \sum_{k=1}^{K} \sum_{i \in \ell} \left( \sum_{q=1}^{p} b_{qk} v_{qi} - s_{ik} \right)^2. $$
令 $\tilde{b} = b_{\cdot k}$ 与 $\tilde{s} = S_{\cdot k}$ 分别为 $B$ 与 $S$ 的第 $k$ 列。最小二乘问题
$$ \underset{\tilde{b} \in \mathbb{R}^{p}}{\arg\min} \sum_{i \in \ell} \left( \sum_{q=1}^{p} \tilde{b}_{q} v_{qi} - \tilde{s}_{i} \right)^2 $$
的解由 $\tilde{b} = \left( V_{\ell\cdot}^T V_{\ell\cdot} \right)^{-1} V_{\ell\cdot}\, \tilde{s}_{\ell}$ 给出。因此，使均方误差最小的解 $\widehat{X}^{LR}$ 为
$$ \widehat{X}^{LR} = \left( V_{\ell\cdot}^T V_{\ell\cdot} \right)^{-1} V_{\ell\cdot}\, \tilde{s}_{\ell}. $$
这些内容总结在算法 12 中。
输入：图 $G$，预言机 $S$，特征向量个数 $p$。
输出：节点标注 $\hat{z} \in [K]^n$。
过程：
- 计算图拉普拉斯 $L = D - A$ 的与 $p$ 个最小特征值相应的标准正交特征向量 $v_1, \ldots, v_p$；
- 令 $V = (v_1, \ldots, v_p) \in \mathbb{R}^{n \times p}$；
- 令 $\widehat{X}^{LR} = V \widehat{B}^{LR}$，其中 $\widehat{B}^{LR}$ 是 $(I_{\ell} V) \widehat{B}^{LR} = S$ 的解；
- 对 $i = 1, \ldots, n$，在 $\widehat{X}^{LR}$ 上用分类规则 (5.2) 定义 $\hat{z}_i$。
返回：$\hat{z}$。
5.3.3 基于 $\ell^1$ 的方法：稀疏标签传播（Sparse Label Propagation）
前面的方法都是最小化基于 $\ell^2$ 范数的代价函数。与此不同，Jung et al., 2019 提出用总变差（total variation）
$$ \| x \|_{\mathrm{TV}} = \sum_{i, j} a_{ij} \left| x_i - x_j \right| $$
来度量图上一个信号 $x \in \mathbb{R}^n$ 的平滑性。
若令 $z^0 \in [K]^n$ 为社区标签，$\ell$ 为标注节点集，则可以陈述如下优化问题
$$ \hat{x} = \underset{\substack{x \in \mathbb{R}^n \\ \forall i \in \ell : \ x_i = z_i^0}}{\arg\min} \sum_{i, j} a_{ij} \left| x_i - x_j \right|. \tag{5.10} $$
把 $\hat{x} \in \mathbb{R}^n$ 截断为 $\hat{z} \in [K]^n$，即可恢复预测的社区 $\hat{z}$。我们回忆，标准的标签传播 (5.3) 是在预言机约束下最小化 $x^T L x = \sum_{i,j} a_{ij} (x_i - x_j)^2$。因此，问题 (5.10) 与标签传播相似，只是它涉及信号沿图的边的差分的 $\ell^1$ 范数。因此，我们期望它能准确学习在少数几条边上发生突变的信号（社区标签正是这样的信号）。相比之下，像标签传播这样基于 $\ell^2$ 范数的方法可能会把这种突变平滑掉。
最后，由于优化问题 (5.10) 涉及不可微函数，这使理论分析更加困难，并排除了一些常用方法（如基于梯度的方法）。关于理论分析与算法实现细节，我们请读者参考 Jung et al., 2019，这里只陈述算法 13。
查看学习笔记对该外引依赖（理论分析与实现细节均见 Jung et al., 2019，书内无证明入口）的说明
输入：图 $G = (V, E)$，标注集 $\ell$，初始标签 $(z_i^0)_{i \in \ell}$，迭代次数 $n_{\mathrm{iterations}}$。
输出：预测的节点标注 $\hat{z} \in [K]^n$。
初始化：令 $k = 0$，$z^{(0)} = z_{\ell}$，$\hat{z}^{(0)} = 0_n$，$\hat{y}^{(0)} = 0_n$；对 $i \in [n]$ 令 $\gamma_i = \frac{1}{\sum_{j \in \mathcal{N}_i} A_{ij}}$，对 $(ij) \in E$ 令 $\lambda_{(ij)} = \frac{1}{2 A_{ij}}$。定义 $\Gamma = \mathrm{diag}(\gamma)$、$\Lambda = \mathrm{diag}\left( \lambda_{(ij)} \right)_{(ij) \in E}$，以及 $G$ 的关联矩阵（incidence matrix）$\mathcal{T} \in \{0, 1\}^{|E| \times n}$。
更新：当 $k < n_{\mathrm{iterations}}$ 时，执行：
- $z^{(k+1)} = z^{(k)} - \Gamma \mathcal{T} y$；
- 对所有 $i \in \ell$，$z_i^{(k+1)} = z_i^0$；
- $y = y + \Lambda \mathcal{T}^T \left( 2 z^{(k+1)} - z^{(k)} \right)$；
- 对每条边 $(ij) \in E$，$y(ij) = \dfrac{y(ij)}{\max\{1, y_{ij}\}}$；
- $\hat{z} = \left( 1 - \dfrac{1}{k+1} \right) \hat{z} + \dfrac{1}{k+1} z^{(k+1)}$；
- $k = k + 1$。
返回：$\hat{z}$。
5.4 SSL 的贝叶斯方法及其理论分析（Bayesian Approach to SSL and Its Theoretical Analysis）
本节研究 SSL 设定下 DC-SBM 图的贝叶斯估计量的理论性质。为叙述简单起见，我们大多考虑 $K = 2$ 个簇的情形。先验的潜在分块结构由随机向量 $z^0 = (z_1^0, \ldots, z_n^0)$ 给出，其中 $z_i^0 \sim \mathrm{Uni}(\{-1, 1\})$。预言机则表示为一个向量 $s \in \{0, -1, 1\}^n$，其各分量 $s_i$ 相互独立，分布如下：
$$ s_i = \left\{ \begin{array}{ll} z_i^0, \qquad & \text{以概率} \quad \eta_1, \\ -z_i^0, \qquad & \text{以概率} \quad \eta_0, \\ 0, \qquad & \text{其他}. \end{array} \right. \tag{5.11} $$
5.4.1 带噪声预言机的 DC-SBM 的 MAP 估计量（MAP Estimator for DC-SBM with a Noisy Oracle）
设 $A$ 为如式 (2.7) 的同质（对称）Poisson SBM 的邻接矩阵，其中 $\omega_{\mathrm{in}} > \omega_{\mathrm{out}}$，并设 $s$ 为由 (5.11) 定义的预言机信息。真实类别标注的最大后验（Maximum A Posteriori, MAP）估计量由
$$ \hat{z}_{\mathrm{MAP}} = \underset{z \in [K]^n}{\arg\max}\; \mathbb{P}\left( z \,|\, A, s \right), $$给出，它等于
$$ \underset{z \in [K]^n}{\arg\min}\; \mathrm{Cut}(A, z) - \tau\, n_1(z)\, n_2(z) + \lambda \left| \left\{ i \in \ell : z_i \neq s_i \right\} \right|, \tag{5.12} $$其中 $\tau = \dfrac{\omega_{\mathrm{in}} - \omega_{\mathrm{out}}}{\log \frac{\omega_{\mathrm{in}}}{\omega_{\mathrm{out}}}}$，$\lambda = \dfrac{\log \frac{\eta_1}{\eta_0}}{\log \frac{\omega_{\mathrm{in}}}{\omega_{\mathrm{out}}}}$，$n_k(z) = \sum_{i=1}^{n} \mathbf{1}(z_i = k)$ 是被标注 $z$ 指派到类别 $k$ 的节点数。
项 $n_1(z)\, n_2(z) = n_1(z) \left( n - n_1(z) \right)$ 在 $n_1(z) = \frac{n}{2}$ 时取得最大值，即当 $z$ 预测出两个同样大小的簇时。因此，SSL 语境下的 MAP 估计量体现了两个无监督项（最小化图的割（cut）与使社区大小平衡）与一个半监督项（最小化预言机与预测之间不一致的数目）之间的权衡。
首先，由贝叶斯公式我们有
$$ \mathbb{P}(z \,|\, A, s) \propto \mathbb{P}(A \,|\, s, z)\, \mathbb{P}(z \,|\, s), $$其中比例关系隐藏了一个与 $z$ 无关的项 $\mathbb{P}(A \,|\, s)$。我们在命题 4.4 证明的末尾建立了
$$ \log \mathbb{P}(A \,|\, z) = \frac{1}{2} \log \frac{\omega_{\mathrm{in}}}{\omega_{\mathrm{out}}} \sum_{i \neq j} \left( A_{ij} - \frac{\omega_{\mathrm{in}} - \omega_{\mathrm{out}}}{\log \frac{\omega_{\mathrm{in}}}{\omega_{\mathrm{out}}}} \theta_i \theta_j \right) \mathbf{1}\left( z_i = z_j \right) + C, $$其中 $C$ 是与 $z$ 无关的常数。最后，由项 $\mathbb{P}(z \,|\, s)$ 给出的预言机信息等于
$$ \begin{array}{l} \displaystyle \mathbb{P}(z \,|\, s) = \prod_{i=1}^{n} \frac{\mathbb{P}(s_i \,|\, z_i)}{\mathbb{P}(s_i)}\, \mathbb{P}(z_i) \\ \displaystyle \phantom{\mathbb{P}(z \,|\, s)} = \left( \frac{\eta_1}{\eta_1 + \eta_0} \right)^{\left| \left\{ i \in \ell : z_i = s_i \right\} \right|} \left( \frac{\eta_0}{\eta_1 + \eta_0} \right)^{\left| \left\{ i \in \ell : z_i \neq s_i \right\} \right|} \left( \frac{1}{2} \right)^n \\ \displaystyle \phantom{\mathbb{P}(z \,|\, s)} = \left( \frac{\eta_0}{\eta_1} \right)^{\left| \left\{ i \in \ell : z_i \neq s_i \right\} \right|} \left( \frac{\eta_1}{\eta_1 + \eta_0} \right)^{|\ell|} \left( \frac{1}{2} \right)^n, \end{array} \tag{5.13} $$其中最后一行用到了 $\left| \{ i \in \ell : z_i = s_i \} \right| + \left| \{ i \in \ell : z_i \neq s_i \} \right| = |\ell|$。
查看学习笔记完整证明（含从 (5.13) 到 (5.12) 的收尾组装）
5.4.2 连续松弛（Continuous Relaxation）
命题 5.1 中导出的 MAP 估计量可以改写为
$$ \hat{z}^{\mathrm{MAP}} = \underset{z \in \{-1, 1\}^n}{\arg\min}\; -z^T \left( A - \tau 1_n 1_n^T \right) z + \lambda \left( s - \mathcal{P} z \right)^T \left( s - \mathcal{P} z \right), $$
其中 $\mathcal{P}$ 是这样的对角矩阵：其 $(i, i)$ 元素在 $i \in \ell$ 时等于 1，否则等于 0。首先，我们直接注意到
$$ \left| \left\{ i \in \ell : z_i \neq s_i \right\} \right| = \frac{1}{4} \sum_{i \in \ell} (s_i - z_i)^2 = \frac{1}{4} \left( s - \mathcal{P} z \right)^T \left( s - \mathcal{P} z \right). $$
然后，我们模仿无监督谱方法的常见做法（Newman, 2013；亦见 4.4.2 节的讨论）做连续松弛，即考虑如下优化问题
$$ \widehat{X} = \underset{\substack{x \in \mathbb{R}^n \\ \sum_i \kappa_i x_i^2 = \sum_i \kappa_i}}{\arg\min} \left( -x^T A_{\tau} x + \lambda (s - \mathcal{P} x)^T (s - \mathcal{P} x) \right), \tag{5.14} $$
其中 $A_{\tau} = A - \tau 1_n 1_n^T$，$\kappa = (\kappa_1, \ldots, \kappa_n)$ 是一个分量全为正的向量。为使推导简单，我们取 $\kappa_i = 1$，即把 $x$ 约束在超球面 $\|x\|^2 = n$ 上，但其他选取也会导致类似的分析。特别地，在数值实验一节（5.4.4 节）中，我们将把这一选择与度归一化方法（$\kappa_i = d_i$）作比较。
我们进一步注意到，对完美预言机（perfect oracle），相应的松弛为
$$ \widehat{X} = \underset{\substack{x \in \mathbb{R}^n,\ x_{\ell} = s_{\ell} \\ \|x\|^2 = n}}{\arg\min} \left( -x^T A_{\tau} x \right). \tag{5.15} $$
给定分类向量 $\widehat{X} \in \mathbb{R}^n$，节点 $i$ 按如下规则被分入簇 $\hat{z}_i \in \{-1, 1\}$：
$$ \widehat{z}_i = \left\{ \begin{array}{ll} 1 \qquad & \text{若 } \widehat{X}_i > 0, \\ -1 \qquad & \text{其他}. \end{array} \right. \tag{5.16} $$
让我们来求解最小化问题 (5.14)。令 $\gamma \in \mathbb{R}$ 为与约束 $\|x\|^2 = n$ 相应的拉格朗日乘子，则优化问题 (5.14) 的拉格朗日函数为
$$ -x^T A_{\tau} x + \lambda (s - \mathcal{P} x)^T (s - \mathcal{P} x) - \gamma \left( x^T x - n \right). $$
这导出带约束的线性方程组
$$ \left\{ \begin{array}{r} \left( -A_{\tau} + \lambda \mathcal{P} - \gamma I_n \right) x = \lambda s, \\ x^T x = n, \end{array} \right. \tag{5.17} $$
其未知量为 $\gamma$ 与 $x$。
遵循 Gander et al., 1989，可以显式求出 $\gamma$ 的最优值。首先我们注意到，若 $(\gamma_1, x_1)$ 与 $(\gamma_2, x_2)$ 是方程组 (5.17) 的解，则
$$ \mathcal{C}(x_1) - \mathcal{C}(x_2) = \frac{\gamma_1 - \gamma_2}{2} \left\| x_1 - x_2 \right\|^2, $$
其中 $\mathcal{C}(x) = -x^T A_{\tau} x + \lambda (s - \mathcal{P} x)^T (s - \mathcal{P} x)$ 是 (5.14) 中被最小化的代价函数。因此，在方程组 (5.17) 的解对 $(\gamma, x)$ 中，最小化问题 (5.14) 的解是与最小的 $\gamma$ 相对应的那个向量 $x$。
其次，$-A_{\tau} + \lambda \mathcal{P}$ 的特征值分解为
$$ -A_{\tau} + \lambda \mathcal{P} = Q \Delta Q^T, $$
其中 $\Delta = \mathrm{diag}(\delta_1, \dots, \delta_n)$，$\delta_1 \leq \cdots \leq \delta_n$，且 $Q^T Q = I_n$。因此，经变量替换 $u = Q^T x$ 与 $b = \lambda Q^T s$ 后，方程组 (5.17) 化为
$$ \left\{ \begin{array}{l} \Delta u = \gamma u + b, \\ u^T u = n. \end{array} \right. $$
于是，优化问题 (5.14) 的解 $\widehat{X}$ 满足
$$ \left( -A_{\tau} + \lambda \mathcal{P} - \gamma_{*} I_n \right) \widehat{X} = \lambda s, \tag{5.18} $$
其中 $\gamma_{*}$ 是显式久期方程（secular equation，Gander et al., 1989）
$$ \sum_{i=1}^{n} \left( \frac{b_i}{\delta_i - \gamma} \right)^2 - n = 0 \tag{5.19} $$
的最小解。
我们把上述内容总结在算法 14 中。注意，为了一般性起见，我们把 $\lambda$ 与 $\tau$ 作为算法的超参数。若模型参数已知，我们可以使用命题 5.1 中导出的 $\lambda$ 与 $\tau$ 的表达式。$\lambda$ 与 $\tau$ 的选取将在 5.4.4 节进一步讨论。
输入：邻接矩阵 $A$，预言机信息 $s$，参数 $\tau$ 与 $\lambda$。
输出：节点标注 $\hat{z} \in [K]^n = (\hat{z}_1, \ldots, \hat{z}_n)$。
过程：
- 令 $\gamma^{*}$ 为方程 (5.19) 的最小解；
- 计算 $\widehat{X}$ 为方程 (5.18) 的解；
- 对 $i = 1, \dots, n$，在 $\widehat{X}$ 上用 (5.16) 定义 $\hat{z}_i$。
返回：$\hat{z}$。
5.4.3 误分类节点数的上界（Upper Bound on the Number of Misclassified Nodes）
在本节中，我们导出在 DC-SBM 上被算法 14 误分类的未标注节点数的一个上界。然后，我们把结果特化到一些特殊情形。我们将假设，给定 $(p_{\mathrm{in}}, p_{\mathrm{out}}, \theta, z)$，图的邻接矩阵 $A = (a_{ij})$ 按如下方式生成：
$$ a_{ij} = a_{ji} \sim \left\{ \begin{array}{ll} \mathrm{Ber}\left( \theta_i \theta_j p_{\mathrm{in}} \right), \qquad & \text{若 } z_i = z_j, \\ \mathrm{Ber}\left( \theta_i \theta_j p_{\mathrm{out}} \right), \qquad & \text{其他}, \end{array} \right. \tag{5.20} $$
其中 $i < j$，且 $A_{ii} = 0$。此外，我们假设 $z_i \sim \mathrm{Uni}(\{-1, 1\})$，$\theta$ 的各分量是独立随机变量，满足 $\theta_i \in [\theta_{\min}, \theta_{\max}]$，且 $\mathbb{E} \theta_i = 1$、$\theta_{\min} > 0$、$\theta_{\max}^2 \max(p_{\mathrm{in}}, p_{\mathrm{out}}) \leq 1$。
对 $z$ 的一个估计量 $\hat{z} \in \{-1, 1\}^n$，被误聚类的节点数就是两个序列 $\hat{z}$ 与 $z$ 之间的汉明距离（Hamming distance），定义为
$$ d_{\mathrm{Ham}}(\hat{z}, z) = \sum_{i=1}^{n} \mathbf{1}\left( \hat{z}_i \neq z_i \right), $$
而被误聚类节点的比例为 $\frac{d_{\mathrm{Ham}}(\hat{z}, z)}{n}$。注意，与无监督聚类不同，我们不对预测标签的置换取最小值，因为我们应该能够从有信息的预言机学到正确的社区标签。
考虑一个由 (5.20)、(5.11) 定义的带噪声预言机的 DC-SBM。令 $\bar{d} = \frac{n}{2} (p_{\mathrm{in}} + p_{\mathrm{out}})$，$\bar{\alpha} = \frac{n}{2} (p_{\mathrm{in}} - p_{\mathrm{out}})$。假设 $\tau > p_{\mathrm{out}}$，并令 $\hat{z}$ 为算法 14 的输出。那么，被误分类的未标注节点的比例满足
$$ \frac{d_{\mathrm{Ham}}(\hat{z}_u, z_u)}{n} \leq 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}{\left( \eta_1 + \eta_0 \right) \left( \eta_1 - \eta_0 \right)^2 \bar{d}}. $$在下文中，平均场图（mean-field graph）指由 DC-SBM 图的期望邻接矩阵构成的加权图。此外，不失一般性，我们假设前 $\frac{n}{2}$ 个节点属于第一个簇、后 $\frac{n}{2}$ 个节点属于第二个簇。因此 $\mathbb{E} A = Z B Z^T$，其中 $B = \begin{pmatrix} p_{\mathrm{in}} & p_{\mathrm{out}} \\ p_{\mathrm{out}} & p_{\mathrm{in}} \end{pmatrix}$，$Z = \begin{pmatrix} 1_{n/2} & 0_{n/2} \\ 0_{n/2} & 1_{n/2} \end{pmatrix}$。特别地，由于 $\mathbb{E} \theta_i = 1$，系数 $\theta_i$ 消失了。我们考虑 $\mathbb{E} A$ 的对角元不为零的设定。这相当于修改 DC-SBM 的定义，使我们可以有以概率 $p_{\mathrm{in}}$ 出现的自环。不过，我们也可以把 $\mathbb{E} A$ 的对角元设为零，我们的结果仍然成立，只是表达式会变得繁琐。注意，矩阵 $\mathbb{E} A$ 有两个非零特征值：$\bar{d} = n \frac{p_{\mathrm{in}} + p_{\mathrm{out}}}{2}$ 与 $\bar{\alpha} = n \frac{p_{\mathrm{in}} - p_{\mathrm{out}}}{2}$。
定理 5.5 的证明。我们分三步证明该命题。我们首先证明，带约束线性方程组 (5.17) 的解 $\widehat{X}$ 集中在平均场模型下同一方程组的解 $\bar{x}$ 附近。然后，我们计算 $\bar{x}$，并证明可以从中恢复正确的簇指派。最后我们导出该界以作结。
(i) 与 (Avrachenkov et al., 2018c) 和 (Avrachenkov and Dreveton, 2019) 类似，让我们把方程 (5.18) 改写为与平均场解相应的线性方程组的一个扰动。于是我们有
$$ \left( \mathbb{E} \widetilde{\mathcal{L}} + \Delta \widetilde{\mathcal{L}} \right) \left( \bar{x} + \Delta x \right) = \lambda s, $$其中 $\widetilde{\mathcal{L}} = -A_{\tau} + \lambda \mathcal{P} - \gamma_{*} I_n$，$\Delta x := \widehat{X} - \bar{x}$，$\Delta \widetilde{\mathcal{L}} := \widetilde{\mathcal{L}} - \mathbb{E} \widetilde{\mathcal{L}}$。
线性方程组 $(A + \Delta A)(x + \Delta x) = b$ 的扰动导出如下的敏感性不等式（sensitivity inequality，Horn and Johnson, 2012, Section 5.8）：
$$ \frac{\| \Delta x \|}{\| x \|} \leq \kappa(A)\, \frac{\| \Delta A \|}{\| A \|}, $$其中 $\| \cdot \|$ 是与某向量范数 $\| \cdot \|$ 相应的算子范数（为简单起见我们使用相同记号），$\kappa(A) := \| A^{-1} \| \cdot \| A \|$ 是条件数。在我们的情形，上述不等式可以改写为：
$$ \frac{\left\| \widehat{X} - \bar{x} \right\|}{\left\| \bar{x} \right\|} \leq \left\| \left( \mathbb{E} \widetilde{\mathcal{L}} \right)^{-1} \right\| \cdot \left\| \Delta \widetilde{\mathcal{L}} \right\|, \tag{5.21} $$其中采用欧氏向量范数与谱算子范数。对 $\mathbb{E} \widetilde{\mathcal{L}}$ 的谱研究（见附录 B.1.1 中的推论 B.2）给出：
$$ \left\| \left( \mathbb{E} \widetilde{\mathcal{L}} \right)^{-1} \right\| = \frac{1}{\min \left\{ |\lambda| : \lambda \in \mathrm{Sp}\left( \mathbb{E} \widetilde{\mathcal{L}} \right) \right\}} = \frac{1}{-t_2^{+} - \bar{\gamma}_{*}}, $$其中 $t_2^{+}$ 定义于附录 B.1.1 中的推论 B.2，$\bar{\gamma}_{*}$ 是平均场模型下方程 (5.19) 的解。由附录 B.1.2 中的引理 B.3 可得
$$ \left\| \left( \mathbb{E} \widetilde{\mathcal{L}} \right)^{-1} \right\| \leq \frac{1}{\lambda + \bar{\alpha}}. \tag{5.22} $$所需的最后一个要素是邻接矩阵在其期望附近的集中性。我们有
$$ \left\| \widetilde{\mathcal{L}} - \mathbb{E} \widetilde{\mathcal{L}} \right\| \leq \left\| (\gamma_{*} - \bar{\gamma}_{*}) I_n \right\| + \| A - \mathbb{E} A \| \leq | \gamma_{*} - \bar{\gamma}_{*} | + \| A - \mathbb{E} A \|. $$附录 B.1.3 中的命题 B.2 表明
$$ | \gamma_{*} - \bar{\gamma}_{*} | \leq \left( 1 + \frac{27 (\bar{\alpha} + \lambda)^3}{\sqrt{2}\, \sqrt{\eta_1 + \eta_0}\, (\eta_1 - \eta_0)\, \bar{\alpha}^2 \lambda} \right) \sqrt{\bar{d}}. $$此外，当 $d = \Omega(\log n)$ 时，我们有 $\| A - \mathbb{E} A \| = O(\sqrt{\bar{d}})$（Feige and Ofek, 2005）。若 $\bar{d} = o(\log n)$，同样的结果在对 $A$ 做适当预处理后仍然成立，我们请读者参考 (Le et al., 2017) 了解更多细节。为保持记号简洁，我们将在证明中略去这一额外步骤。利用这一集中不等式，对某个常数 $C'$ 我们有
$$ \begin{array}{rcl} \left\| \widetilde{\mathcal{L}} - \mathbb{E} \widetilde{\mathcal{L}} \right\| & \leq & \left( C' + \dfrac{27 (\bar{\alpha} + \lambda)^3}{\sqrt{2}\, \sqrt{\eta_1 + \eta_0}\, (\eta_1 - \eta_0)\, \bar{\alpha}^2 \lambda} \right) \sqrt{\bar{d}} \\ & \leq & \left( C' + \dfrac{27}{\sqrt{2}} \right) \dfrac{(\lambda + \bar{\alpha})^3}{\bar{\alpha}^2 \lambda}\, \dfrac{\sqrt{\bar{d}}}{\sqrt{\eta_1 + \eta_0}\, (\eta_1 - \eta_0)} \end{array} $$令 $C = C' + \frac{27}{\sqrt{2}}$。把上式与不等式 (5.22) 相结合，不等式 (5.21) 变为
$$ \frac{\left\| \widehat{X} - \bar{x} \right\|}{\left\| \bar{x} \right\|} \leq C\, \frac{(\lambda + \bar{\alpha})^2}{\bar{\alpha}^2 \lambda}\, \frac{\sqrt{\bar{d}}}{\sqrt{\eta_1 + \eta_0}\, (\eta_1 - \eta_0)}. \tag{5.23} $$ 查看学习笔记对"$\bar{d} = o(\log n)$ 预处理步骤被省略"这一留白的依赖说明（指向 Le et al., 2017）(ii) 在平均场模型中，若 $\bar{x}_i$ 的符号与 $z_i$ 的符号相同，则节点 $i$ 被判决规则 (5.16) 正确分类。附录 B.2 中的推论 B.5 表明，未标注节点确实如此。
(iii) 最后，要使未标注节点 $i$ 被正确分类，该节点的取值 $\widehat{X}_i$ 应足够接近其平均场取值 $\bar{x}_i$。特别地，第 (ii) 部分表明，若 $|\widehat{X}_i - \bar{x}_i|$ 小于某个不趋于零的常数 $\beta$，则未标注节点 $i$ 将被正确分类。若 $|\widehat{X}_i - \bar{x}_i| > \beta$，则称未标注节点 $i$ 为 $\beta$-坏（$\beta$-bad）节点。我们记 $\beta$-坏节点的集合为 $S_{\beta}$。不是 $\beta$-坏的节点几乎必然被正确分类，因此 $d_{\mathrm{Ham}}(\hat{z}_u, z_u) \leq |S_{\beta}|$。由 $\left\| \widehat{X} - \bar{x} \right\|^2 \geq \sum_{i \in S_{\beta}} \left| \widehat{X}_i - \bar{x}_i \right|^2$ 可得 $\left\| \widehat{X} - \bar{x} \right\|^2 \geq \beta^2 |S_{\beta}|$。于是，利用 (5.23) 与范数约束 $\| \bar{x} \|^2 = n$，对某个常数 $C$ 我们有
$$ \left| S_{\beta} \right| \leq \frac{1}{\beta^2} \left( \frac{C}{\eta_1 - \eta_0}\, \frac{\bar{\alpha} + \lambda}{\bar{\alpha} \lambda} \sqrt{\bar{d}} \right)^2 n, $$注意到 $\frac{\bar{d}}{\bar{\alpha}} = \frac{p_{\mathrm{in}} + p_{\mathrm{out}}}{p_{\mathrm{in}} - p_{\mathrm{out}}}$，证明结束。
查看学习笔记对本证明的逐步整合（含原书跳步补全与附录 B 依赖定位）考虑一个 DC-SBM，满足 $\bar{d} \gg 1$、$\frac{p_{\mathrm{in}} + p_{\mathrm{out}}}{p_{\mathrm{in}} - p_{\mathrm{out}}} = O(1)$，且 $\sqrt{\eta_0 + \eta_1}\, (\eta_1 - \eta_0) \gg \frac{1}{\sqrt{\bar{d}}}$。假设 $\tau > p_{\mathrm{out}}$ 且 $\lambda \gtrsim \bar{\alpha}$。那么，算法 14 能正确分类几乎所有的未标注节点。
在推论的假设下，$(\eta_1 - \eta_0)^2 \bar{d} \to +\infty$ 且 $\frac{\bar{\alpha} + \lambda}{\lambda} = O(1)$。因此，由定理 5.5，被误分类节点的比例是 $o(1)$。
查看学习笔记条件性推导审计（含参数条件的逐条代入）量 $(\eta_1 - \eta_0) n$ 是被预言机正确标注的节点数与被错误标注的节点数之差的期望。特别地，由于 $\eta_0$ 与 $\eta_1$ 可以趋于零，推论 5.6 允许标注节点数是次线性的。
考虑一个 DC-SBM，其中 $p_{\mathrm{in}} = \frac{c_{\mathrm{in}}}{n}$、$p_{\mathrm{out}} = \frac{c_{\mathrm{out}}}{n}$，$c_{\mathrm{in}}, c_{\mathrm{out}}$ 为常数。假设 $\sqrt{\eta_0 + \eta_1}\, (\eta_1 - \eta_0)$ 是一个非零常数，并令 $\tau > 2 p_{\mathrm{out}}$、$\lambda \gtrsim 1$。那么，当 $\frac{(c_{\mathrm{in}} - c_{\mathrm{out}})^2}{c_{\mathrm{in}} + c_{\mathrm{out}}}$ 大于某个常数时，算法 14 以高概率（w.h.p.）表现得优于随机猜测。
根据定理 5.5，当 $\frac{(c_{\mathrm{in}} - c_{\mathrm{out}})^2}{c_{\mathrm{in}} + c_{\mathrm{out}}}$ 大于 $\frac{2 C}{(\eta_1 - \eta_0)^2} \left( \frac{\bar{\alpha} + \lambda}{\lambda} \right)^2$ 时，被误聚类节点的比例小于 $\frac{1}{2}$，而后者以一个常数为下界。
查看学习笔记条件性推导审计（含常数的来源讨论）量 $\frac{(c_{\mathrm{in}} - c_{\mathrm{out}})^2}{c_{\mathrm{in}} + c_{\mathrm{out}}}$ 可以解释为信噪比（signal-to-noise ratio）。遗憾的是，推论 5.7 不能让我们控制该推论陈述中的常数。这个常数来自邻接矩阵的集中性。(Le et al., 2017) 在对常数度情形下 SBM 图的无监督谱聚类的分析中也给出过类似的评注。
5.4.4 数值结果（Numerical Results）
本节既在由 DC-SBM 生成的合成数据集上，也在真实网络上给出数值实验。特别地，我们讨论预言机错误（由比值 $\frac{\eta_0}{\eta_0 + \eta_1}$ 定义）对各算法性能的影响。
λ 与 τ 的选择（Choice of λ and τ）
记 $\sigma_1$ 与 $\sigma_2$ 为 $A$ 的最大与第二大特征值。我们选取 $\tau = \frac{4}{n} (\sigma_1 + \sigma_2)$；当 $\eta_0 \neq 0$ 时取 $\lambda = \frac{\log \frac{\eta_1}{\eta_0}}{\log \frac{\sigma_1 + \sigma_2}{\sigma_1 - \sigma_2}}$，否则取 $\lambda = \frac{\log (n \eta_1)}{\log \frac{\sigma_1 + \sigma_2}{\sigma_1 - \sigma_2}}$。这一选择的启发式理由如下。对一个 SBM 图，我们有 $\sigma_1 \approx \frac{n}{2} (p_{\mathrm{in}} + p_{\mathrm{out}})$、$\sigma_2 \approx \frac{n}{2} (p_{\mathrm{in}} - p_{\mathrm{out}})$，因此 $\frac{4}{n} (\sigma_1 + \sigma_2) = 2 p_{\mathrm{in}} > p_{\mathrm{out}}$，即 $\tau$ 满足定理 5.5 的条件。对 $\lambda$，我们有 $\frac{\log \frac{\eta_1}{\eta_0}}{\log \frac{\sigma_1 + \sigma_2}{\sigma_1 - \sigma_2}} \approx \frac{\log \frac{\eta_1}{\eta_0}}{\log \frac{p_{\mathrm{in}}}{p_{\mathrm{out}}}}$，当 $p_{\mathrm{in}}, p_{\mathrm{out}} = o(1)$ 时，这确实接近命题 5.1 中导出的 $\lambda$ 的表达式。
松弛方式的选择（Choice of relaxation）
我们首先比较连续松弛 (5.14) 中约束的不同选择。具体地，我们比较 $\sum_i x_i^2 = n$（称为标准松弛）与 $\sum_i d_i x_i^2 = 2|E|$（称为度归一松弛）两种选择。这给出算法 14 的两个版本，它们在带噪声预言机的 SBM 图上取得的代价展示在图 5.5 中。特别地，我们观察到归一化的选择给出更小的代价。因此，在下文中我们只考虑求解带约束 $\sum_i d_i x_i^2 = 2|E|$（而非 $\sum_i x_i^2 = n$）的松弛问题 (5.14) 的算法 14 版本，因为它的数值结果更好。
合成图上的实验（Experiments on synthetic graphs）
我们首先考虑在 DC-SBM 上的聚类。我们设定 $n = 2000$、$p_{\mathrm{in}} = 0.04$、$p_{\mathrm{out}} = 0.02$。我们考虑三种情形：
- 在图 5.6(a) 中，我们考虑标准 SBM（对所有 $i$，$\theta_i = 1$）。
- 在图 5.6(b) 中，我们按 $|\mathcal{N}(0, \sigma^2)| + 1 - \sigma \sqrt{2/\pi}$ 生成 $\theta_i$，其中 $|\mathcal{N}(0, \sigma^2)|$ 表示均值为 0、方差为 $\sigma^2$ 的正态随机变量的绝对值。我们取 $\sigma := 0.25$。注意，这一定义使 $\mathbb{E} \theta_i = 1$ 得以成立。
- 在图 5.6(c) 中，我们从密度函数为 $f(x) = \frac{a m^a}{x^{a+1}} \mathbf{1}(x \geq m)$ 的 Pareto 分布生成 $\theta_i$，其中 $a = 3$、$m = 2/3$（选取使 $\mathbb{E} \theta_i = 1$）。
我们比较算法 14（在图中称为 map-relaxed）与 Poisson 学习（算法 10）、约束谱聚类（算法 11，缩写为 csc）的性能。结果如图 5.6 所示。虽然 map-relaxed 与 csc 在噪声增大时抑制了精度的下降，但 csc 在这些合成数据集上的性能相当差。此外，我们注意到 Poisson 学习在合成数据集上给出的结果也很差，且其性能随噪声进一步恶化。
MNIST 数据集上的实验（Experiments on MNIST data set）
作为真实数据的例子，我们在标准 MNIST 数据集（LeCun et al., 1998）上进行仿真。作为预处理，我们选取对应两个数字的 1000 张图片，并计算带高斯权重 $w_{ij} = \exp\left( -\|x_i - x_j\|^2 / s_i^2 \right)$ 的 $k$ 最近邻图（我们取 $k = 8$），其中 $x_i$ 表示图像 $i$ 的数据，$s_i$ 是 $x_i$ 与其 $K$ 个最近邻之间的平均距离。[校勘]不同数字对的精度见图 5.7。我们注意到，三种算法的性能都非常出色。但是，在较大的预言机噪声下，Poisson 学习的精度下降得比算法 14 或约束谱聚类更多。
为了进一步凸显噪声的影响，我们在图 5.8 中画出三种算法在未标注节点、被正确标注的节点与被错误标注的节点上取得的精度。虽然 Poisson 学习在未标注节点上的精度极佳，但它无法正确分类被错误标注的节点。相反，算法 14 实现了更平滑的恢复：未标注、被正确标注与被错误标注的节点具有大致相同的分类精度。虽然一些被正确标注的节点被误分类，但许多被错误标注的节点变为被正确分类，且未标注节点被恢复得更好。
进一步阅读（Further Notes）
在许多网络中，例如社交网络、引文网络与知识图谱，节点是带有特征的。因此，把图结构与节点特征同时纳入考量是非常自然的想法。这一思想已在图神经网络（Graph Neural Networks, GNNs）中实现。Scarselli et al., 2008 可能是最早提出 GNN 设计框架的工作。随后，Defferrard et al., 2016 利用图傅里叶变换给出了 GNN 的高效实现，Kipf and Welling, 2017 则在半监督学习语境下发展了 GNN。若干工作在 Personalized PageRank 与 GNN 之间建立了漂亮的联系：Klicpera et al., 2019、Bojchevski et al., 2020、Chien et al., 2020。近年来，这一主题上发表了许多工作，感兴趣的读者可以在 (Wu et al., 2020; Zhou et al., 2020) 中找到全面的综述。
除了 5.4 节给出的分析之外，随机矩阵理论的方法也被应用于半监督学习（Mai and Couillet, 2018, 2021）。
随着高性能计算与云计算的发展，人们需要考虑基于图的半监督学习的并行计算方法。(Avrachenkov et al., 2016a; Ravi and Diao, 2016; Chen et al., 2020) 给出了若干这类方法的例子。