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

因此预测节点 $v$ 的标签，只需要知道 $v$ 的邻居（邻域） 的标签即可。（假设这些节点有趋向性）

问题

如图，这些节点绿色和红色已知，分别为 $1,0$ 请你预测灰色的节点

这和以下问题类似：

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

首先我们把有标签的节点赋与初始值 $0/1$ 把无标签的初始值赋为 $0.5$

并且按照以下方法迭代：

$P(Y_v=c)=\frac{1}{\sum _{(u,v)\in E}{A}_{u,v}}\sum _{(u,v)\in E}{A}_{(}u,v)P(Y_u=c)$

缺点（1.不一定收敛2.不一定有趋向性）

注意到每个点 $u$ 更新后对未更新的邻居产生的贡献是新的概率 $P_u$

迭代过程如图所示

Iterative classification

刚才的算法缺点很显然，并没有利用到节点的特征，仅仅利用了边的关系。

主要的方法是训练了两个分类器，一个基于特征向量 $f_v$ 预测节点标签，另一个通过特征向量和邻居节点标签 $z_v$ 预测。

这是关于 $z_v$ 的解释

流程如下，需要注意的是，和 RC 一样，不一定收敛。

训练 ${\varphi }_1$

以特征向量的第一个值进行判断，可见出错了。但是我们再加上两个维度

首先我们通过已知节点训练分类器，之后利用分类器预测无标签节点，图中的 ? 节点还是 $0$

之后更新标签 $z$ ，问号节点变为1

Correct & Smooth (C&S)

假设一张图中，部分节点有标签，我们要预测节点的标签，C&S 分为以下三步

1.训练预测器

2.用预测器预测 soft labels （大概是和节点是某种颜色的概率）

3.利用图的结构进行调整，得到最后的信息。

最后一步就是 C&S

误差矫正 (Correct step)：利用训练数据中的残差来纠正测试数据中的误差；

平滑标签 (Smooth step)：平滑测试数据中的预测结果。

source

Correct 主要对于最后两方概率都接近 $0.5$ ,也就是误差较大的节点，能准确一些，这运用到了之前提到的 Homophily 性质，确切的说是假设有这个性质。首先我们知道了残差training errors ( Ground-truth label minus soft label. Defined as 0 for unlabeled nodes.) 真实值减去预测值。

$E^{(t+1)}\leftarrow (1-\alpha )\cdot E^{(t)}+\alpha \cdot \tilde{A}{E}^{(t)}$

$\tilde{A}$ 是 $A$ 矩阵的正则化表达，注意我们要考虑自环，因为这也是一种影响。

并且类似拉普拉斯正则化一样，我们写出表达式 $\tilde{A}=\frac{1}{\sqrt{d_i}\sqrt{d_j}}$ 如果 $\{v_i,v_j\}\in E$ 此时度比较大的节点对邻居的影响就变小。

我们利用这个表达式，迭代后得到以下结果

此时基本不存在很难预测的节点了，但是有些soft label还是还是不太理想，不要急，我们还有 Smooth step

我们利用刚才的公式，但是我们用真实的标签部分替换估计的

$E^{(t+1)}\leftarrow (1-\alpha )\cdot E^{(t)}+\alpha \cdot \tilde{A}{E}^{(t)}$

迭代出来的结果如图所示