cs224w-5-MessagePassingAndNodeClassification
前言
已知一部分节点的标签,利用节点之间的关系预测节点的属性(半监督学习)
Intuition: Correlations (dependencies) exist in networks
三种方法:
Relational classification
Iterative classification
Correct & Smooth
定义
Homophily
The tendency of individuals to associate and bond with similar others
大概就是趋向性的意思,个体与周围的相关性趋势。
Influence
Social connections can influence the individual characteristics of a person
节点之间的关系(边)能影响一个节点性质
预测节点标签
原理
Similar nodes are typically close together or directly connected in the network
因此预测节点 的标签,只需要知道 的邻居(邻域) 的标签即可。(假设这些节点有趋向性)
问题
如图,这些节点绿色和红色已知,分别为 请你预测灰色的节点
这和以下问题类似:
Document classification
Part of speech tagging
Link prediction
Optical character recognition
Image/3D data segmentation
Entity resolution in sensor networks
Spam and fraud detection
算法
Relational classification
首先我们把有标签的节点赋与初始值 把无标签的初始值赋为
并且按照以下方法迭代:
缺点(1.不一定收敛2.不一定有趋向性)
迭代过程如图所示
Iterative classification
刚才的算法缺点很显然,并没有利用到节点的特征,仅仅利用了边的关系。
主要的方法是训练了两个分类器,一个基于特征向量 预测节点标签,另一个通过特征向量和邻居节点标签 预测。
这是关于 的解释
流程如下,需要注意的是,和 RC 一样,不一定收敛。
训练
以特征向量的第一个值进行判断,可见出错了。但是我们再加上两个维度
首先我们通过已知节点训练分类器,之后利用分类器预测无标签节点,图中的 ?
节点还是
之后更新标签 ,问号节点变为1
Correct & Smooth (C&S)
假设一张图中,部分节点有标签,我们要预测节点的标签,C&S 分为以下三步
1.训练预测器
2.用预测器预测 soft labels (大概是和节点是某种颜色的概率)
3.利用图的结构进行调整,得到最后的信息。
最后一步就是 C&S
误差矫正 (Correct step):利用训练数据中的残差来纠正测试数据中的误差;
平滑标签 (Smooth step):平滑测试数据中的预测结果。
Correct 主要对于最后两方概率都接近 ,也就是误差较大的节点,能准确一些,这运用到了之前提到的 Homophily 性质,确切的说是假设有这个性质。首先我们知道了残差training errors ( Ground-truth label minus soft label. Defined as 0 for unlabeled nodes.) 真实值减去预测值。
是 矩阵的正则化表达,注意我们要考虑自环,因为这也是一种影响。
并且类似拉普拉斯正则化一样,我们写出表达式 如果 此时度比较大的节点对邻居的影响就变小。
我们利用这个表达式,迭代后得到以下结果
此时基本不存在很难预测的节点了,但是有些soft label还是还是不太理想,不要急,我们还有 Smooth step
迭代出来的结果如图所示