Ch.05 图半监督学习：翻译 + 学习笔记

第 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|$。在下文中，我们将始终假设预言机是有信息的。

给定预言机 $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.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}$ 的方法。

作为预言机标签传播的解释（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。

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)}$ 的一个迭代表达式。

事实上，引理 5.3 还提供了一种计算该解的迭代数值过程。该过程在算法 10 中正式描述。

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}$。

基于引理 5.4，并遵循 Wang and Davidson, 2010 与 Wang et al., 2014，我们提出如下过程：

1. 求广义特征值问题 $\mathcal{L} v_k = \lambda_k \left( \bar{Q} - \beta I_n \right) v_k$ 中与 $\lambda_k > 0$ 相应的解向量 $v_1, \cdots, v_p$；
2. 给定所有可行特征向量 $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 中。

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 中。

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，书内无证明入口）的说明

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）

项 $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）与使社区大小平衡）与一个半监督项（最小化预言机与预测之间不一致的数目）之间的权衡。

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 节进一步讨论。

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}$。注意，与无监督聚类不同，我们不对预测标签的置换取最小值，因为我们应该能够从有信息的预言机学到正确的社区标签。

在下文中，平均场图（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}$。

量 $(\eta_1 - \eta_0) n$ 是被预言机正确标注的节点数与被错误标注的节点数之差的期望。特别地，由于 $\eta_0$ 与 $\eta_1$ 可以趋于零，推论 5.6 允许标注节点数是次线性的。

量 $\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) 给出了若干这类方法的例子。