CS224W-图神经网络笔记6.2：Message Passi

2021-03-12 本文已影响0人 Epiphron

CS224W-图神经网络笔记6.2：Message Passing and Node Classification - 三类主要的节点分类算法介绍

本文总结之日CS224W Winter 2021只更新到了第四节，所以下文会参考2021年课程的PPT并结合2019年秋季课程进行总结以求内容完整

课程主页：CS224W: Machine Learning with Graphs

视频链接：【斯坦福】CS224W：图机器学习( 中英字幕 | 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） $f(a_i)$ ：使用节点自身特征，去预测每个节点的标签 $Y_i$ .；分类器可以是 SVM, kNN或者其他
Iteration Phase：
- 通过计数、众数、占比、均值等方式聚合邻居特征。并更新每个节点的特征向量 $a_i$ 。
- 用分类器预测并更新新的标签 $Y_i$ 。
- 重复过程直到标签稳定（收敛）或者达到最大迭代次数。

模型存在问题：模型不一定收敛；

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 $\psi$ ：其中 $\psi(Y_i, Y_j)$ 表示节点 $i$ 是类别 $Y_i$ 的条件下，其邻接节点 $j$ 为类别 $Y_j$ 的概率;这反映的就是上面介绍的相邻节点间的相关性correlation。
prior belief $\phi$ ： $\phi_i(Y_i)$ 表示节点 $i$ 为类别 $Y_i$ 的先验概率；
message $m_{i->j}(Y_j)$ : 节点预测其邻接节点 $j$ 为状态 $Y_j$ 的概率
stats $\mathcal{L}$ : 表示所有的状态