一、前言

现在的主要问题是
给定一个网络其中一些节点上有标签我们如何将标签分配给网络中的所有其他节点?

实际问题
在网络中一些节点是欺诈者而另一些节点是完全可信的。如何发现其他欺诈者和可信赖节点?

这是一个半监督问题

• 给定一些节点的标签
• 让我们预测未标记节点的标签
• 这被称为semi-supervised node classification

我们可以使用Node Embedding来解决这个半监督分类问题。但本文讨论另一种框架:消息传递(Message passing)。

该方法的思想是
网络中存在相关性(依赖关系)即相似节点间存在链接。

• 节点的行为在网络的各个链路上是相互关联的
• 相关性:相邻节点颜色相同(属于同一类)
  

为什么网络中节点的行为是相关的有两种解释:

• 以社交圈为例子具有相似特征的人倾向于相互联系这是社会科学的同质性(Homophily)概念。
  
  可以理解成物以类聚人以群分。如专注于同一研究领域的研究人员更有可能建立联系(在会议上见面在学术讲座上互动等)。

• 社会关系会影响我们自己的特征或我们自己的行为
  如我把我喜欢的音乐推荐给我的朋友们直到他们中的一个越来越喜欢我最喜欢的音乐类型!
  

本文将讲三种实现技术

• Relational classification
• Iterative classification
• Correct & Smooth

---

二、How do we leverage node correlation in network

我们如何利用网络中观察到的这种相关性来帮助预测节点标签?

• Motivation(1)相似的节点通常紧密相连或在网络中直接连接:
  • Guilt-by-association
    如果我链接到一个标签为X的节点那么我可能也有标签X。
  • 例如:恶意/良性网页:
    恶意网页相互链接以增加可见性看起来可信并在搜索引擎中排名更高
• Motivation(2)网络中节点的分类标签可能依赖于
  • v节点的features
  • v节点邻居节点的标签
  • v节点邻居节点的features

---

半监督学习问题描述

• 给定
  • Graph
  • 一些带有标签的节点
• 任务
  对剩余节点进行分类
• 解决问题的主要假设
  网络中存在同质性(Homophily)

---

示例任务:

• 设A为$n\times n$邻接矩阵
• 设 Y = { 0 , 1 } n Y=\{0,1\}^n Y={0,1}n为标签集
  • $Y_v=1$则属于$Class1$
  • $Y_v=0$则属于$Class0$
  • 有未标记的节点需要分类
• 目标预测哪些未标记的节点可能是$Class1$哪些可能是$Class0$

如下图每个节点v都有一个特征向量$f_v$给出了一些节点的标签。
任务是考虑到所有的特征和网络找到$P(Y_v)$。

---

实际应用

• 文档分类
• 词性标注
• 链接预测
• 光学字符识别
• 图像/3D数据分割
• 传感器网络中的实体解析
• 垃圾邮件和欺诈检测

三、Relational Classification

$Idea$
在网络中传播节点标签如节点$v$的类概率$Y_v$是其邻居类概率的加权平均。

在初始化时

• 对于有标签的节点$v$初始化$Y_v$为ground-truth label $Y_v^{\ast }$
• 对于无标签的节点初始化$Y_v=0.5$

然后按随机顺序更新所有节点直到收敛或达到最大迭代次数为止。

节点$v$的类概率更新公式如下

• 如果边有强度/重量信息$A_{v,u}$是u和v之间的边的权重。
• 前面的$\frac{1}{\sum }$项是归一化确保$P(Y_v)$在0-1之间
• $P(Y_v=c)$表示节点标签为$c$的概率

这个方法存在两个问题

• 不能保证收敛
• 模型不能使用节点特征信息

---

实例

对下图灰色节点进行分类红色和绿色节点表示已知标签的节点。$P_Y$表示其标签为1(绿色)的概率。

• 初始化

  • 有标签的节点初始化为ground truth
  • 没标签的节点初始化为0.5

• 第一轮迭代按1-9的次序更新节点

  • 更新节点3
    

  • 节点3更新完后更新节点4
    

  • 以同样的方式顺序更新节点5、2、9
    

• 第二轮迭代按1-9的次序更新节点
  
  节点9的标签未变即节点9收敛了将节点9的值固定后续不做更新。

• 第三轮迭代
  
  节点8收敛了将节点8的值固定后续不做更新。

• 第四轮迭代
  
  节点5、3收敛了将节点5、3的值固定后续不做更新。

• 第五轮迭代【这轮迭代可省因为其余顶点都收敛了】
  
  所有节点都收敛了

• 我们可以预测

  • 节点4,5,8,9属于class 1($P_{Y_v}>0.5$)
  • 节点3属于class 0($P_{Y_v}<0.5$)

这个方法没有用到节点的feature下面介绍一个使用了feature的方法:$Iterativeclassification$

---

四、Iterative classification

Relational classifier没有用节点属性。

Iterative classification的主要思想是:
根据节点$v$的属性$f_v$以及邻居集$N_v$的标签$z_v$对节点$v$进行分类。

---

问题描述

• 输入图$G$
  • 每个节点$v$都有特征向量$f_v$
  • 部分节点$v$有标签$Y_v$
• 任务
  预测未标记节点的标记
• 方法:训练两个分类器
  • ${\varphi }_1(f_v)=$根据节点特征向量$f_v$预测节点标签。称为base classifier。
  • ${\varphi }_2(f_v,z_v)=$根据节点特征向量$f_v$和$v$的邻居标签的汇总$z_v$来预测标签。称为relational classifier。

---

如何计算$z_v$
我们通过节点$v$的邻居节点的标签来定义$z_v$即$z_v$=捕获节点$v$周围标签的向量$z_v$可以定义为

• $N_v$中每个标签的数量的直方图(或分数)
• $N_v$中最常见的标签
• $N_v$中不同标签的数量

---

Iterative classification整体框架

• 阶段一仅根据节点属性进行分类

  • 在标记的训练集中训练两个分类器:
    • Base classifier:${\varphi }_1(f_v)$根据$f_v$来预测$Y_v$
    • Relational classifier:${\varphi }_2(f_v,z_v)$根据$f_v$和$v$的邻居标签的汇总$z_v$来预测Y

• 阶段二迭代直到收敛

  • 在测试集上根据分类器${\varphi }_1(f_v)$设置标签$Y_v$计算$z_v$用${\varphi }_2(f_v,z_v)$预测标签
  • 对每个节点$v$重复此步骤
    • 基于$Y_{u,u\in N_v}$更新$z_v$
    • 基于$新的z_v$使用${\varphi }_2(f_v,z_v)$更新$Y_v$
  • 迭代直到类标签稳定或达到最大迭代次数
  • 注意:不保证收敛

---

实例网页分类

• 输入Graph of web pages

• 顶点网页

• 边超链接

• Node feature网页描述

  • 为了简单描述我们只考虑两个二进制特征

• 任务预测网页的主题

• 首先训练分类器${\varphi }_1(f_v)$(如线性分类器)根据节点属性对页面进行分类。
  
  当然仅基于$f_v$预测是不够准确的所有会出现错误的预测值如上图的灰色节点。

• 第二步每个节点维护邻域标签向量$z_v$:
  这里$z_v$:采用四维向量四个元素分别为指向该节点的节点中标签为0和1的数目、该节点指向的节点中标签为0和1的数目。
  4维向量分为两个二维的向量$I$和$O$

  • $I$指向该节点的节点中标签为0和1的数目
  • $O$该节点指向的节点中标签为0和1的数目
    

• 第三步在没有标记的数据集上使用分类器${\varphi }_1(f_v)$去设置$Y_v$

• 第四步迭代以下两个步骤直到收敛或者达到最大迭代次数

  • 更新所有节点的$z_v$
  • 使用${\varphi }_2(f_v,z_v)$更新$Y_v$
    

五、Loopy Belief Propagation

Belief Propagation是一个用于回答图中的概率问题的动态方法。如回答节点v属于class 1的概率
迭代的过程就是邻居节点之间相互“talk”、相互传递信息(passing messages)的过程。

例子1
以课堂为例子学生们视为节点位置相邻的学生可以互相传递消息告诉对方我认为拟可能是class 1的概率。某个学生获得邻居的信息后会汇总得出结论再把消息传递给他的邻居。就像传字条

例子2计算图中有几个节点
条件每个节点只能和它的邻居pass message

• path graph(路径图)
  
  • 算法流程
    • 定义节点的顺序1-6
    • 边的方向(消息传递的方向)取决于节点的顺序
    • for node i from 1 to 6
      • 计算要从i传递到i+1的message
      • 将消息从节点i传递到i+1节点

• Tree(树状图)
  将path graph泛化到树结构的图上
  • 算法流程
    • 节点顺序从叶子节点到根节点传递信息
    • 子节点向父节点传递信息父节点汇总子节点信息并更新信息向其父节点传递信息。
    • 如下图4节点汇总子节点7、6的信息并在本地计算更新信息将更新的信息继续向上传递给父节点3
      
      直到消息传到根节点消息传递结束
      

Message Passing可总结未4个步骤

• 收集
• 计算
• 更新
• 创建new message并传递

---

符号标识

• Label-label potential matrix $\psi$节点与它邻居之间的依赖性。
  如$\psi (Y_i,Y_j)$表示在给定$j$的邻居$i$是class $Y_i$的情况下节点$j$属于class $Y_j$的概率
• Prior belief $\varphi$$\varphi (Y_i)$表示节点i属于$Y_i$的概率
• $m_{i\to j}(Y_j)$表示节点$i$的关于评估节点$j$属于$Y_i$的消息
• $L$标签集和

---

$LoopyBPAlgorithm$

以下图为例

流程

• 初始化所有节点的message为1
• 对所有节点进行重复计算
  • 计算需要传递的信息
    
    k∈N_i\j除了j以外i的邻居节点

• 个人对公式的理解
  • 粉色部分
    汇总所有的类别信息即i在不太类别情况下传递的message是不一样的需要进行汇总。
    如i节点是class 0的情况下会告诉j你和我有点像i节点是class 1的情况下会告诉j你和我一点都不像汇总起来就是j是class 0的概率很大。
  • 绿色部分$\times$红色部分
    i节点是calss $Y_i$的情况下j节点是$Y_j$的概率。这里$Y_i$不同则结果也会不同就是粉色部分说的message不同的意思。
  • 蓝色部分
    i的邻居k告诉ii节点是类别$Y_i$这个问题我向你提供这个信息
• 公式可以从右向左看
  • 首先是i的邻居节点向i提供其类别是$Y_i$的证据(证据指邻居节点有多大概率认为是Y_i)【蓝色部分】
  • 拿到证据后再结合自身的情况判断自己可能是$Y_i$的概率【红色部分】
  • 现在i对自己是$Y_i$有了一定的判断通过依赖矩阵$\psi$来提供j节点你可能和我一样是$Y_i$的证据。【绿色部分】
  • 枚举$Y_i\in L$将证据汇总就是i要传递给j的message【粉色部分】

• 收敛后计算$b_i(Y_i)$即节点i输出Y_i的置信度
  

---

上面的例子都是无环图Loopy BP Algorithm也能运用于有环图中这也是loopy含义。

• 现在我们开始考虑有环图
• 在有环图中我们不规定节点顺序。而是从随机节点开始执行Loopy BP Algorithm沿着边更新邻居节点。

在有环图中

1. 从不同子图中传递的信息不再相互独立

   • 如下图u获得的传递信息可能来自于i或者k而i和k的信息都是从j处传递过来的。即信息再传递到u时j已经和“talk”两次了传递的信息并不似相互独立的。
     

2. 信息会在圈子里加强

   • 就类似PageRank的spider trapmessage不断地在圈子里循环不断地被加强。
     

   • 实例
     

上述现象会导致算法不能够收敛但是在实际应用中由于现实世界的真实复杂图会更像树就算有环也会有弱连接所以还是能用Loopy BP Algorithm。

---

Belief Propagation的优点

• 易于编程和并行运算
• 可泛化到任何形式的图模型上

挑战

• 不一定能够收敛特别是含有环的时候
• $\psi (Y_i,Y_j)$矩阵参数需要去训练和评估