二专毕设，让人头大。

# 消息传递和节点分类

# 任务 —— 半监督节点分类问题

半监督节点分类问题 (semi-supervised node classification problem) 是指，如果一个图上的某些节点被标记为绿色或红色，而其余大部分节点没有标记（即灰色）。那么我们如何对节点进行染色，将节点划分为绿色或红色？

# 背景 & 想法

解决这一问题的基本想法是：在网络中存在相关性，换句话说，相似的节点是相连的。

基于此想法，我们将介绍三种技术：

• 关系分类 (Relational classification)
• 迭代分类 (Iterative classification)
• 信念传播 (Belief propagation)

# 网络中的相关性

首先，我们从社会科学的角度说说前面想法的可靠性。这包括三点：

1. 同质性 (homophily): 社会学家将同质性定义为个体与其他具有相似特征的个体之间联系的趋势 (tendency of associate and bond). 此外，社会连接也会影响个体的性格特点。
2. 影响 (influence): 相连的个体可以通过互相影响，从而形成更加近似的特征。因此，假定相连的顶点具有更大的相似度，是一种合理的假设和想法。
3. 混杂 (confound): 环境对个体的混杂作用，也使得相连的个体更加相似。

这就是我们设计算法的归纳偏置 (inductive bias).

# 动机

因此，我们的设计原则是一种连坐法 (guilt by associaion), 即如果我与一个含有标签 $X$ 的节点相连，那么我自身也应该含有标签 $X$.

于是，对网络中的节点 $v$ 进行标签分类取决于：

• $v$ 的特征
• $v$ 的邻居节点标签
• $v$ 的邻居节点特征

# 协作分类

协作分类 (collective classification) 就是解决前述半监督问题的具体方法。它有许多应用，包括：

• 文档分类 (document classification)
• 链路预测 (link prediction)
• 字符识别 (Optical Character Recognition, OCR)
• 图像 / 三维数据分割 (image/3D data segmentation)

# 建模

我们可以将任务规范化如下：输入为 $n$ 个节点的图对应的邻接矩阵 $A \in \mathbb{R}^{n \times n}$, $Y = \{0,1\}^n$ 是标签向量，其中 $Y_v = 1$ 对应节点 $v$ 的标签为 $1$. 且图中有大量节点的标签未标记。我们的目标是确定所有未标记节点的标签。

# Markov 假设

在规范化的任务中，我们采用图上的 Markov 假设，即节点 $v$ 的标签 $Y_v$ 只与节点 $v$ 的邻居节点 $N_v$ 有关，即

$$P(Y_v) = P(Y_v|N_v),$$

而与二阶邻居等其它节点无关。

# 分类器

为实现上述过程，我们需要三种类型的分类器：

1. 本地分类器 (local classifier): 为节点赋予初始标签。这一步骤不需要使用网络信息。
2. 关系分类器 (relational classifier): 捕捉邻居节点的特征。
3. 协作推理器 (collective inference): 依照协作关系将特征沿网络传播，直到标签收敛于某种状态。这一过程将迭代使用关系分类器。

# 关系分类

# 想法

概率关系分类器 (probabilistic relational classifier) 的想法是，节点 $v$ 的标签 $Y_v$ 是邻居节点标签的加权平均。

# 架构 / 过程

# 初始化

首先将已标记节点标签 $Y_v$ 赋为真实数据 $Y_V^*$, 对于非标记节点，标签赋予 $Y_v = 0.5$. （需要注意这是一个 0-1 二分类问题。）

# 更新

随后，将采用一个随机序更新所有节点，直到达到最大迭代次数或者标签收敛。对于每个标签为 $c$ 的节点 $v$, 更新过程如下：

$$P(Y_v = c) = \frac{\sum_{(v,u) \in E} A_{v,u} P(Y_u = c)}{\sum_{(v,u) \in E} A_{v,u}}$$

其中，邻接矩阵 $A$ 的数值可以是含权的，这样可以衡量不同边的强度。

但这样做有两个缺点：

1. 不能保证收敛性；
2. 模型没有使用节点的特征信息，仅仅使用了网络结构信息。

# 迭代分类

# 建模

迭代分类相比于前者，考虑到了如何使用节点的特征信息。其输入包括：

• $\boldsymbol{f}_v$: 节点 $v$ 的特征向量；
• $Y_v$: 部分节点 $v$ 的标签。

# 想法

要实现这一目的，需要构建两个分类器：

1. $\phi_1(\boldsymbol{f}_v)$: 基于节点特征 $\boldsymbol{f}_v$ 进行标签分类；
2. $\phi_2(\boldsymbol{f}_v, z_z)$: 基于节点特征 $\boldsymbol{f}_v$ 和总结自节点 $v$ 邻居节点标签的信息 $\boldsymbol{z}_v$. 这里的 $\boldsymbol{z}_v$ 是一个向量，其中可以包括各种有关邻居的节点信息，例如邻居中数量最多的标签，标签的类别数，不同标签所占百分比等。

# 架构 / 过程

这样一个分类模型的运行包括两个阶段：

1. 仅基于节点特征进行分类
   • 在训练集上，训练前述两个分类器：
   • $\phi_1(\boldsymbol{f}_v)$: 基于节点特征 $\boldsymbol{f}_v$ 进行标签分类；
   • $\phi_2(\boldsymbol{f}_v, z_z)$: 基于节点特征 $\boldsymbol{f}_v$ 和总结自节点 $v$ 邻居节点标签的信息 $\boldsymbol{z}_v$.
2. 迭代至收敛
   • 在测试集上，先基于 $\phi_1$ 进行标签设置，然后计算 $\boldsymbol{z}_v$, 再基于 $\phi_2$ 进行标签预测，最后基于预测结果更新标签。
   • 迭代直到标签收敛，或者达到了最大迭代次数

需要注意的是，这一迭代是不能保证收敛的，因此需要设置一个最大迭代次数。

# 循环信念传播

# 信念传播

信念传播 (belief propagation) 是一种用于解决图上概率查询的动态规划算法。这一算法是迭代进行的。在迭代过程中，每个顶点与邻居节点进行 “对话”，即消息传递 (message passing).

# 记号

引入下面几个记号：

• 标签潜在矩阵 (label-label potential matrix) $\psi$: 是一种用于衡量不同节点之间标签依赖关系的矩阵。元素 $\psi(Y_i, Y_j)$ 与节点 $j$ 标签为 $Y_j$ 时，其存在邻居节点 $i$ 标签为 $Y_i$ 的概率成比例。
• 先验信念 (prior belief) $\phi$: $\phi(Y_i)$ 与节点 $i$ 标签为 $Y_i$ 的概率成比例。
• $m_{i \to j}(Y_j)$: 表示节点 $i$ 对节点 $j$ 标签为 $Y_j$ 的信息 / 估计。
• $\mathcal{L}$: 标签集。

# 算法

算法流程如下：

1. 将所有信息初始化为 $1$.
2. 对于每个节点，重复下述信息传递公式直至收敛或达到最大迭代次数

   $$m_{i \to j}(Y_j) = \sum_{Y_i \in \mathcal{L}} \psi(Y_i, Y_j) \phi(Y_i) \prod_{k \in N_i \setminus j} m_{k \to i}(Y_i), \quad \forall Y_j \in \mathcal{L}.$$

收敛之后，

$$b_i(Y_i) = \phi_i(Y_i) \prod_{j \in N_i} m_{j \to i}(Y_j), \forall Y_i \in \mathcal{L}$$

是节点 $i$ 标签为 $Y_i$ 的信念。

这一算法称为循环信念传播 (loopy belief propagation), 究其原因是该算法常常应用在具有循环路径的图上。

# 算法可靠性

就像 PageRank 算法可能会陷入蜘蛛陷阱，该算法在循环路径中也可能无法达到收敛。但通常情况下，循环会放大信息，因此，该算法仍然能够收敛。此外，现实情况的复杂图大多是近似树的形式，循环往往较少。因此，这仍然是一个很有效的启发式算法。

# 讨论

算法的一些思考如下：

• 优点
  • 简单易编程 & 易并行化。
  • 通用：可以适用于多种形式的图模型，潜在标签矩阵也可以有更高阶的表示形式 ($\psi(Y_i, Y_j, Y_k, \dots)$).
• 挑战
  • 算法的收敛性是不确定的（尤其是在图中有许多闭环的情况下），因此何时停止算法难以确定。
  • 潜在标签矩阵需要训练