前言

已知一部分节点的标签,利用节点之间的关系预测节点的属性(半监督学习)

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
节点之间的关系(边)能影响一个节点性质

预测节点标签

pSp8wZQ.png

原理

Similar nodes are typically close together or directly connected in the network

因此预测节点 vv 的标签,只需要知道 vv 的邻居(邻域) 的标签即可。(假设这些节点有趋向性)

问题

pSp80aj.png

如图,这些节点绿色和红色已知,分别为 1,01,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/10/1 把无标签的初始值赋为 0.50.5

并且按照以下方法迭代:

P(Yv=c)=1(u,v)EAu,v(u,v)EA(u,v)P(Yu=c)\large P(Y_v=c)=\frac{1}{\sum_{(u,v)\in E}\limits A_{u,v}}\sum_{(u,v)\in E}\limits A_(u,v)P(Y_u=c)

缺点(1.不一定收敛2.不一定有趋向性)

注意到每个点 uu 更新后对未更新的邻居产生的贡献是新的概率 PuP_u
pSp8TRx.png

迭代过程如图所示

pSp8bQK.png

pSp87z6.png

pSp8qsO.png

pSp8LLD.png

pSp8Xee.png

Iterative classification

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

pSpGSJI.md.png

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

pSpGpWt.md.png

这是关于 zvz_v 的解释

pSpGdl6.png

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

pSpG5nS.png

训练 ϕ1\phi_1

pSpGo7Q.png

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

pSpGHts.png

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

pSpGLpq.png

之后更新标签 zz ,问号节点变为1

pSiylYn.png
pSiyQFs.png
pSiyKoj.png

Correct & Smooth (C&S)

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

1.训练预测器

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

pSkX06P.png

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

最后一步就是 C&S

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

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

source

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

pSkvsiQ.png

pSkxzn0.png

E(t+1)(1α)E(t)+αA~E(t)E^{(t+1)}\leftarrow(1-\alpha)\cdot E^{(t)}+ \alpha \cdot \widetilde{A}E^{(t)}

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

pSkzz2d.png

pSkzih4.png

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

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

pSASuMn.png

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

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

E(t+1)(1α)E(t)+αA~E(t)E^{(t+1)}\leftarrow(1-\alpha)\cdot E^{(t)}+ \alpha \cdot \widetilde{A}E^{(t)}

迭代出来的结果如图所示

pSACjeI.png