CS224W：图机器学习3¶
本页统计信息
-
本页约 1628 个字, 预计阅读时间 5 分钟。
-
本页总阅读量次
消息传递和节点分类¶
- 这一节内容主要关注对于一个给定的网络结构，一些节点已经做好了标注，那么我们如何对图中的剩余节点进行标准，就比如一张图中已知部分节点是可疑的，另一部分节点是可信的，那么我们应该如何判定剩下那些没有标注的节点是否可信呢？
- 这类任务被称为半监督的节点分类问题
- 之前已经介绍了节点嵌入的方法可以识别相似的节点，而这一节主要介绍的方法是消息传递
- 一般我们认为网络中的关系是具有相关性的，也就是说相似的节点会互相连接，并且相近的节点可能属于相同的类型
- 同质性Homophily：指的就是相同或者类似的节点个体会和其他的节点相互连接
- 影响：网络中的连接关系可能会影响到单个节点，即节点可能会被与之相互连接的节点给带偏
- 这样的半监督学习经常被用在：
- 文本分类
- 语音标记
- 连接预测
- 光学字符识别
- 图像和3D分割
- 节点异常检测
- 这一节内容将主要介绍三种实现上述半监督图学习的技术：
- 关系分类Relational classification
- 可迭代分类Iterative classification
- 信任传播Belief propagation
关系分类¶
关系分类的基本想法：节点v的类概率\(Y_v\)是一个节点附近节点的类别的加权平均(这里我们只考虑二分类问题，正反类别的标签分别用1和0来表示)，而对于已经有标记的节点v，其\(Y_v\)可以直接设置成其真实类别，而对于没有标记的节点可以将其初始化为\(Y_v=0.5\)，然后对所有的节点进行类似于加权平均的更新知道收敛或者达到最大迭代次数上限。 $$ P(Y_v=c)=\frac{1}{\sum_{(v,u)\in E}A_{v,u}}\sum_{(v,u)\in E}A_{v,u}P(Y_v=c) $$
- 其中A表示每条边的权重
- 问题在于：收敛是没有保证的，并且模型没有用到节点的特征信息
迭代分类¶
相比于关系分类，迭代分类会使用节点v的一系列特征构成的特征向量\(f_v\)和邻近节点的标签\(z_v\)，而这种分类方式需要训练两个分类器：
-
\(\phi_1(f_v)\)通过节点的特征来预测节点的标签
-
\(\phi_2(f_v,z_v)\)通过特征向量和邻近节点的标记来共同预测节点的标签
训练两个分类器只是第一阶段，第二阶段需要进行迭代训练直到结果收敛或者训练结束，但是结果是否收敛依然没有保证。
举例：网页分类¶
- 首先训练一个基于二维特征向量的分类器，用邻近节点(区分出和入节点)的特征向量作为\(z_v\)
- 然后按照步骤训练出两个分类器，然后用测试集来测试分类器的效果，并对关系特征\(z_v\)和标签进行更新
- 进行迭代更新，直到收敛或者达到次数上限
协作分类：信任传播机制¶
信任传播机制是一种动态规划算法，通过一个节点和节点之间互相“通信”和传递消息的迭代过程，当节点直接达到共识的时候就可以计算出最后的结果
一个简单的消息传播的例子¶
举一个简单的例子来说明消息传递的作用，比如我们需要在一个图中计算节点总数，并且每个节点只能和与之相邻的节点之间进行通信，简单的消息传递算法的实现如下：
- 定义节点的顺序形成一条完整的路径
- 每次向下一个节点来传播当前统计到的节点个数，最后一个节点要发送出去的数据就是结果
- 这样的算法也可以在树状的结构中进行，区别就是要从叶节点将信息汇总到根节点
循环消息传递算法¶
加入一个节点i指向j，那么i将会给j传递消息，而传递什么消息需要根据i从指向i的节点中获得的信息来决定，循环消息传递算法中定义了这样几个关键的变量：
-
标签势能矩阵，\(\Phi(Y_i,Y_j)\)表示对于一个节点j，如果给定它的邻居节点i属于类别\(Y_i\)时，节点j属于类别\(Y_j\)的概率
-
先验信任 \(\phi(Y_i)\)表示节点i属于\(Y_i\)类别的概率
- i向j传递的消息可以记成\(m_{i\rightarrow j}(Y_j)\)，这表示i估计j的最终类型是\(Y_j\)在循环消息传递算法中，传递的消息可以表示为：
-
这种计算方式的意思是，如果i预测j的最终标签是\(Y_j\)，那么就需要考虑节点i所有可能的标签，并且对于每一个标签计算节点i收到的信息是节点i属于类别\(Y_i\)进行求和，我们可以记 $$ b_i(Y_i)=\phi(Y_i)\prod {k\in N_i\ k\not=j}m(Y_i) $$
-
是先验概率和所有从邻居节点收到消息的和的乘积
-
如果我们遇到的图是有环的，那么这样一来节点就不存在一个确定的顺序，但我们依然可以用上述算法来计算信任的传播。当有顺序的时候可以从任意一个节点开始，然后依次更新其邻居节点的信息，但是当图有环的时候，从不同的子图中获得的信息就不是独立的了，这个时候信任传递依然可以使用，但是会出现循环传递的情况，可能会导致不收敛的情况，但是在实际操作中，这个算法依然比较好用
