CS224W-图神经网络 笔记6.2：Message Passing and Node Classification - 三类主要的节点分类算法介绍
本文总结之日CS224W Winter 2021只更新到了第四节，所以下文会参考2021年课程的PPT并结合2019年秋季课程进行总结以求内容完整
[toc]
引言
前面，接着上文节点分类的协作分类算法思想介绍。这节具体看看细分的三类算法。
-
关系分类relational classification -
迭代分类iterative classification -
信念传播belief propagation
1. 概率关系分类(Probabilistic Relational Classifier)
1.1 算法过程
基本思想：每个节点类别的概率是其邻接节点的加权平均。过程如下：
给已知和未知标签的节点分概率
- 未知的可初始化为
0，或者其他先验的概率值
- 未知的可初始化为
随机选择节点更新其概率值为其邻居的类别概率的加权平均值。
- 直到达到收敛或最大迭代次数
模型存在问题：
- 模型不一定收敛；
- 该模型并没有使用到节点的特征信息；
为什么采用随机选择节点？
选择节点的顺序会影响最终结果，尤其是对于较小的图（较大的图对顺序不敏感）。从经验上看，随机选取在大多数情况下都达到较好的效果。
2. Iterative Classification
2.1 算法过程
因为上述方法没有利用节点的特征，Iterative Classification 对这一点进行完善。整个过程分为两步：
Bootstrap Phase：- 为每个节点分配一个向量.
- 创建一分类器(local classifier）
：使用节点自身特征，去预测每个节点的标签
.；分类器可以是 SVM, kNN或者其他
Iteration Phase：- 通过计数、众数、占比、均值等方式聚合邻居特征。并更新每个节点的特征向量
。
- 用分类器 预测并更新新的标签
- 重复过程直到标签稳定（收敛）或者达到最大迭代次数。
- 通过计数、众数、占比、均值等方式聚合邻居特征。并更新每个节点的特征向量
模型存在问题：模型不一定收敛；
3. Belief Propagation
信念传播（Belief Propagation）通过消息传递(passing message)的方式，解决概率图模型中的条件概率问题。这涉及了概率图的相关知识。算法将变量消去法中的求和操作看作一个消息传递过程，较好地解决了求解多个边际分布时的重复计算问题。
3.1 什么是消息传递？
看到 Propagation，部分朋友也会联想到 深度学习训练中的正向传播和反向传播（back Propagation）。对于 信念传播（Belief Propagation）涉及信息传递（message passing）。对于图上的每个节点仅与它的邻居进行信息的收集（collect）和传递（distribute）。也就是当前节点的状态（state）不光取决于自身还与其邻居相关。在消息传递时，每个节点只能从其邻接接受消息。
借用课上的例子理解。如何基于消息传递机制统计图的节点数？或者说如何让图上每个节点都直到图中的节点数。
- 对于
链图:通过向左向右分别进行消息传递，对于中间节点将左边传递的消息和和右边传递的消息的进行汇总，并加上自身的1，实现图上节点数的统计。 - 对于
树图；通过加选中节点作为 根节点（root node），其余节点分别向根节点传递消息，最终根节点，汇总不同邻居传递的消息，并加上自身的1，实现图上节点数的统计。
当图上有环（loop/circle）时，传统的BP算法不适用，这时可以采用Loopy Belief Propagation。
3.2 Loopy Belief Propagation
在阐述具体算法前需要，先做一些符号定义。（可将下面的状态替换为标签更好理解）。
-
Label-Label potential matrix：其中
表示节点
是类别
为类别
的概率;这反映的就是上面介绍的相邻节点间的
相关性correlation。 -
prior belief：
表示节点
-
message: 节点预测其邻接节点
- stats
: 表示所有的状态
有了上面的定义，可以得出节点向其邻接节点
发送的消息为：
对
整个过程如下：
模型优点：
实现简单，极易并行化；
普适性强，适用所有图模型；对于有环的图，也可以使用LBP算法，因为在实践中
- a：环的回路较长，
- b：环的某些边的相关性correlation较小
使得传播过程中其影响被削弱。
模型存在问题：模型不一定收敛；
3.3 举例
课上老师给了一个将LBP用于在线拍卖网络的欺诈识别（NetProbe）。论文如下
http://www.cs.cmu.edu/~christos/PUBLICATIONS/netprobe-www07.pdf
总结
说实话，对于BP算法的理解还很表面，希望后面通过数据和代码加深理解。
参考资料
- https://zhuanlan.zhihu.com/p/279561894
- [PRML]图模型推论(四)--循环信念传播
- https://www.cnblogs.com/Leo_wl/p/3506242.html
