CS224w图机器学习（五）：Message Passing and Node Classification

内容简介

本文主要介绍CS224W的第六课，图的信息传播和节点分类。上一章讲述的谱聚类，就可以对节点进行分类，本节则从信息传递的角度来考虑节点的分类。

CS224W Lecture 6: Message Passing and Node Classification

上图为CS224W第六讲谱聚类的内容框架，如下链接为第六讲的课程讲义

1 Collective Classification

什么是图的信息传输呢？举个例子，如下图所示，如果我们给图的一小部分节点打上标签，那么其他这个标签的信息能否传递给其他节点并帮助他们都打上标签（也成为半监督节点分类，semi-supervised node classification）。这种把标签传递给所有节点的想法，也就是集体分类（Collective Classification）。

首先，网络的节点之间是有相关性（correlation）的。

以社交网络为例，它有着如下图所示的三种类型的关系（个体视为节点，社会关系视为边）： 1）个体的特质会影响他们的社会关系（同质性 Homophily） 2）社会关系也会进一步影响他们的特质（影响性 Influence） 3）同时外部环境会同时影响我们的性格和社交关系（混合型 confounding）。 上述例子相对不太清晰，我们从另一个清晰的角度来看社交网络，个体为节点，个体间的社交关系是边，如果我们想按国籍给个体分类，那么我们需要寻找与个体国籍相关的特征来进行节点分类，这个特征便可以描述节点间的相关性，上述三种类别关系便是节点间存在相关性的原因。

节点分类的一个重要想法是：相似的节点通常紧密相连或直接连接（图的分割、社区、角色基本都离不开这点，但切入点不同，最终也就形成了图的不同性质）。

通常一个节点的类别取决于三个因素： 1）当前节点的特征 2）当前节点的邻居节点的类别（Labels） 3）当前节点的邻居节点的特征（Features）

图的信息传播和节点分类的引入大体如此，下面将开始问题抽象和数学描述。

定义拥有

[公式]

个节点的图

[公式]

，其邻接矩阵为

[公式]

。 再定义向量

[公式]

，用于表示

[公式]

个节点的标签（当前仅考虑二分类问题），其中

[公式]

表示节点标签为positive ，

[公式]

表示节点标签为negative，

[公式]

表示节点还没有标签。 我们需要解决的问题是所有没标签的节点，有多少节点标签为positive，有多少为negative。 集体分类（Collective Classification）在解决这个问题时，引入马尔科夫假设，节点

[公式]

标签的概率分布，取决于其邻居节点标签的概率分布：

[公式]

。 引入该思想后，我们待解决的问题变成，计算所有节点的标签概率分布。 我们再过一下集体分类的三个步骤： 1）Local Classifier: 给节点分配初始标签，该部分是个标准的分类任务，通过节点的特征预测其初始标签（没有使用网络信息）； 2）Relational Classifier: 基于网络结构捕捉节点间的关系，该部分会使用网络信息，基于节点自身以及邻居节点的属性对节点进行分类； 3）Collective Inference: 通过网络传播相关性，将Relational Classifier应用于所有节点，直至相邻节点的非一致化最小。 完全按照上述流程进行集体分类，实操时是一个NP难度的问题，实际的节点分类算法都是基于近似推断的迭代算法。用来进行集体分类的算法如下： 1）Probabilistic Relational Classifier 2）Iterative Classification 3）Loopy belief propagation

2 Probabilistic Relational Classifier

概率关系分类器（Probabilistic Relational Classifier）的基本思想如下：

节点

[公式]

归属于类别

[公式]

的概率

[公式]

，是其邻居节点归属于类别

[公式]

的概率的加权平均。 对于有类别标签的节点，其概率标签已确定（训练过程中也不会变）； 对于没有标签的节点，对其不同类别的概率值进行统一初始化（比如二分类问题，正负类别的概率都为0.5）。 对于每一个节点

[公式]

，其归属于类别

[公式]

的概率如下，重复进行如下迭代计算，直至收敛（或达到最大迭代次数）。

[公式]

，其中

[公式]

是节点

[公式]

到节点

[公式]

的权重。

下面我们简单感受下概率关系分类器的训练过程，其中绿色为正标签节点，蓝色为负标签节点，其余为未标注节点：

1）初始化

初始化未标注节点所属类别的概率

2）第一轮迭代

第一轮迭代，计算节点3的概率

第一轮迭代，计算节点4的概率

第一轮迭代结束后，最终各节点类别的概率情况

3）第二轮迭代

第二轮迭代结束后，最终各节点类别的概率情况

4）第三轮迭代

第三轮迭代结束后，最终各节点类别的概率情况

5）第四轮迭代，趋于收敛

第四轮迭代结束后，最终各节点类别的概率情况

6）最终各节点的类别

概率关系分类器有两点不足：

1）并不能保证算法最终能达到收敛； 2）算法并没有使用节点自身的信息，仅使用节点间的边权重用作概率推理。

3 Iterative Classification

概率关系分类器虽然没用上节点自身的信息，但迭代分类（Iterative Classification）用上了，它的基本思想如下：

通过节点自身的属性及其邻居节点的标签来进行分类。主要步骤如下： 1）Bootstrap阶段：对每个节点

[公式]

，定义一个向量

[公式]

，并训练一个基于向量

[公式]

的分类器

[公式]

来计算节点所述最佳的类别

[公式]

（如SVM、KNN）； 2）Iteration阶段：基于节点的邻居类别，更新节点的向量

[公式]

，并基于分类器更新节点所属的类别

[公式]

。重复Iteration阶段，直至收敛或最大迭代次数。

下面我们通过对网页分类来更清晰的了解迭代分类的过程。

• 网页特征向量 准备阶段

1）提取网页的原始特征，比如代表网页上文本的词频等，我们假设提取出了三个特征， 并用

[公式]

进行表征。基于这三个特征，使用KNN作为网页分类器。

2）如上图，当拥有两个相同文本特征的网页隶属于不同类别时，再利用文本特征预测时肯定有一个会出错。此时我们给网页的向量再加几个维度（该节点的邻居类别），如下图所示，其中

[公式]

表示指向该网页（可以跳转到当前网页）的网页，至少有一个属于类别A。最终网页的向量由自身的属性

[公式]

和邻居节点的类别标签

[公式]

组成。

• 分类模型训练阶段

初始化状态并非所有节点都有邻居节点的类别标签，所以我们要训练两个分类器，一个基于网页提取的特征（下图绿框框），一个基于网页提取的特征+邻居网页标签（下图红框框）。

当模型训练好后，使用基于网页特征（绿框框）训练出来的模型，预测所有网页的类别。如下图所示，我们要在"?"这里填上A或B。

• 迭代阶段

使用当前网页的邻居网页标签更新所有节点的特征向量（上上图的红框框）。如下图，我们再使用基于网页提取的特征+邻居网页标签训练的模型来进行重新预测所有节点的类别。

再基于新的结果继续更新网页的特征向量，并重复迭代过程，直至最终收敛或达到最大迭代次数。最终我们会得到所以网页的分类结果。

与概率关系分类器类似，迭代分类也难以保证模型最终能够收敛，所以一般使用最大迭代次数作为迭代的终止条件。

4 Loopy belief propagation

LBP算法是基于BP算法演进而来，信念传播（Belief Propagation, BP）算法源于贝叶斯网络，，UC Berkeley CS188课程有花大篇幅详细介绍贝叶斯网络，如感兴趣可以深入了解。贝叶斯网络通过变量间的概率推演，将多变量的联合分布，变成若干局部分量的条件概率分布，此时变量间的关系是树结构的，即BP算法是针对树结构的。而当我们想解决的变成了无向图以后，也就出现了Loopy Belief Propagation（LBP）。

在介绍无向图的LBP算法前，我们先看一条有节点组成的链上的信息传输。

每个节点只能和他的邻居进行信息交互。 一条链上的节点在信息传输时，接受来自上游的信息，更新当前的状态，并把信息传给下游，如此便可实现一条链上的信息传输。 如下图所示，信息从左往后传输时，每个节点都知道有多少个人在自己前面，从右往左传输时，它们则知道有多少个节点在后面。

数据结构在复杂一点，从一条链变成一棵树时，信息如何传输。

每个节点从树的所有分支接收信息。 如下图所示，每个节点可以往所有邻居节点传递信息，下列三张图分别是ME所在的节点往三个方向传出的信息。

节点ME往右下方向传递信息，包含ME在内一共有11个节点

节点ME往左上方向传递信息，包含ME在内一共有7个节点

节点ME往右上方向传递信息，包含ME在内一共有11个节点

上面无论是链式结构还是树状结构，如果节点成环则都无法合理的进行信息传输。此时便需要引入LBP算法。

重新定义信息传输： 节点

[公式]

传递给节点

[公式]

传递的信息取决于节点

[公式]

的所有邻居节点

[公式]

传递给节点

[公式]

的信息，以及邻居节点

[公式]

对节点

[公式]

当前置信度的影响。 在上述信息传输的定义之上，我们再引入几个概念： 1）Label-label potential Matrix

[公式]

: 用来表示节点与其邻居节点之间的关系，

[公式]

表示节点

[公式]

的类别为

[公式]

时，节点

[公式]

类别为

[公式]

的概率，即

[公式]

。 2）Prior belief

[公式]

:

[公式]

表示节点

[公式]

类别为

[公式]

的概率。 3）

[公式]

: 节点

[公式]

对节点

[公式]

类别的估计。 4）

[公式]

: 所有状态的集合 引入上述定义后，我们详细的看下LBP是怎么进行信息传输的。 1）首先将全部节点的信息初始化为1。 2）计算

[公式]

，公式详情如下图所示（这个公式类似于马尔科夫过程的状态转移计算，推荐把这些概念放在一起理解，详情可参考UC Berkeley CS188，这课程中引入的例子相对简单，用下雨、带伞和踢足球来构建状态转移的场景，我们的决策过程是下雨带伞，不下雨踢足球，然后状态就是下雨或不下雨，通过计算昨天（下雨|不下雨）的条件下，今天（下雨|不下雨）的条件概率， 今天下雨的概率等于昨天不下雨的情况下今天下雨 加上 昨天下雨的情况下今天下雨的概率，这一步计算和下个公式看上去是不是很相似，LBP在信息传输时也是类似的，在上游节点所有的可能性的基础之上，计算当前节点处于类别

[公式]

的概率，并传递给下游）。

3）重复2的过程，直至最终收敛。再使用如下公式计算节点

[公式]

处于状态

[公式]

的置信度。

与上述两种手段一样，不保证最终一定能收敛。