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