Message Passing and Node Classification
lecture 5主要介绍的是一种用于结点分类的Framework: Message Passing。在结点分类中，我们的任务其实是semi-supervised：已知部分结点的label，预测未知结点的label。而Message Passing是一种利用了图的同质性的模型，简言之，就是通过neighbor来预测未知结点，遵循的思想就类似于“近朱者赤近墨者黑”
Homophily
Message Passing框架的前提假设就是Homophily: Individuals have tendency to associate with similar others，比如有相同爱好的人相互之间联系更紧密、在同一个领域做研究的人相互之间认识的可能性更大等等。
上面这张图就是一个例子。那么反过来，个体之间的联系也会对个体产生影响。基于以上两点，我们就可以设计Message Passing的模型了。
Collective Classification
lecture中介绍的方法叫做collective classification。collective classification是一种利用结点之间correlation的概率模型，它通常分为三个部分：
- Local Classifier：用于给每个结点赋一个initial label
- Relational Classifier：用于捕获结点之间的correlation
- Collective Inference：用于在网络中传递Relational Classifier所获取到的correlation
具体来说，有三种不同的模型：
- Relational Classification
- Iterative Classification
- Belief Propagation
Relational Classification
Relational Classification是最简单的一种，它的核心思想就是对结点的neighbor取一个平均。对于每个结点
u
u
u和label c（二分类，
c
∈
{
0
,
1
}
c \in \{0,1\}
c∈{0,1}），
u
u
u的label
Y
u
Y_u
Yu等于
c
c
c的概率为：
p
(
Y
u
=
c
)
=
1
∑
(
u
,
v
)
∈
E
A
u
v
∑
(
u
,
v
)
∈
E
A
u
v
p
(
Y
v
=
c
)
p(Y_u=c)\ =\ \frac{1}{\sum_{(u,v) \in E}{A_{uv}}}\sum_{(u,v) \in E}A_{uv}p(Y_v=c)
p(Yu=c) = ∑(u,v)∈EAuv1(u,v)∈E∑Auvp(Yv=c)
但是这个方法是不能保证一定converge，并且很明显这里没有用到任何结点的feature。
Iterative Classification
Iterative Classification做了一些改进，它将node feature考虑进来，因此我们现在是基于结点特征 f u f_u fu和结点类别 z u z_u zu（这里的 z u z_u zu也是一个vector，计算的方式有很多，可以自行设置，比如 N u N_u Nu中每种label的数量等）进行分类。我们训练两个分类器 ϕ 1 , ϕ 2 \phi_1,\phi_2 ϕ1,ϕ2， ϕ 1 \phi_1 ϕ1的输入是node feature f u f_u fu，输出是label，因此 ϕ 1 \phi_1 ϕ1的作用是根据node feature预测label； ϕ 2 \phi_2 ϕ2的输入是node feature f u f_u fu和邻居label summary z u z_u zu，输出也是label，因此 ϕ 2 \phi_2 ϕ2的作用是根据 f u f_u fu和 z u z_u zu来预测label。算法分为两个阶段：
- Phase 1：在训练集上，我们训练这两个分类器 ϕ 1 \phi_1 ϕ1和 ϕ 2 \phi_2 ϕ2
- Phase 2：在测试集上，我们把 ϕ 1 \phi_1 ϕ1当作Local Classifier，用于给待预测结点赋初始标签；把 ϕ 2 \phi_2 ϕ2当作Relational Classifier，结合每个结点的邻居的label summary z u z_u zu 对 u u u的label进行更新。每次更新过后，不要忘记更新收到影响的 z z z。不断重复迭代直至收敛。
这种方法解决了Relational Classification中没有利用node feature的问题，但依然无法保证收敛。
Belief Propagation
Belief Propagation is a dynamic programming approach to answering probability queries in a graph (e.g. probability of node 𝑣 belonging to class 1)
Belief Propagation 更多是在考虑结点之间的“交流”。首先明确几个概念：
- label-to-label potential matrix ψ \psi ψ: ψ ( Y i , Y j ) \psi(Y_i,Y_j) ψ(Yi,Yj)正比于已知 i i i的邻居结点 j j j的label为 Y j Y_j Yj， i i i 的label为 Y i Y_i Yi的概率
- Prior belief ϕ \phi ϕ： ϕ ( Y i ) \phi(Y_i) ϕ(Yi)正比于结点 i i i的label为 Y i Y_i Yi的概率（类似于先验）
- m i → j ( Y j ) m_{i \rightarrow j}(Y_j) mi→j(Yj)：表示 i i i对于 j j j的label为 Y j Y_j Yj的信息/估计
以上图的结构为例，此时我们要预测的结点为
j
j
j，我们的转移方程为：
m
i
→
j
(
Y
j
)
=
∑
Y
i
ψ
(
Y
j
,
Y
i
)
ϕ
(
Y
i
)
∏
k
∈
N
(
i
)
−
{
j
}
m
k
→
i
(
Y
i
)
m_{i \rightarrow j}(Y_j)\ =\ \sum_{Y_i} \psi(Y_j, Y_i)\phi(Y_i)\prod_{k \in N(i)-\{j\}}m_{k \rightarrow i}(Y_i)
mi→j(Yj) = Yi∑ψ(Yj,Yi)ϕ(Yi)k∈N(i)−{j}∏mk→i(Yi)
式子中
ϕ
(
Y
i
)
∏
k
∈
N
(
i
)
−
{
j
}
m
k
→
i
(
Y
i
)
\phi(Y_i)\prod_{k \in N(i)-\{j\}}m_{k \rightarrow i}(Y_i)
ϕ(Yi)∏k∈N(i)−{j}mk→i(Yi)这一项其实就是结点
i
i
i label为
Y
i
Y_i
Yi的一个总信息（概率），因此这里的
ψ
(
Y
j
,
Y
i
)
\psi(Y_j,Y_i)
ψ(Yj,Yi)可以看作是一个transition probability
收敛后，我们就可以计算每个结点不同label的belief：
b
u
(
Y
u
)
=
ϕ
(
Y
u
)
∏
v
∈
N
(
u
)
m
v
→
u
(
Y
u
)
Y
u
∈
{
Y
1
,
Y
2
,
…
,
Y
m
}
b_u(Y_u) \ =\ \phi(Y_u)\prod_{v \in N(u)}m_{v \rightarrow {u}}(Y_u) \ \ \ \ \ \ \ \ \ Y_u \ \in \{Y_1, Y_2, \dots,Y_m\}
bu(Yu) = ϕ(Yu)v∈N(u)∏mv→u(Yu) Yu ∈{Y1,Y2,…,Ym}
从转移方程我们可以看出，我们做了条件独立性假设，也就是neighbor对于当前节点的信息传递是互相独立的。因此，BP在遇到环的时候会失效
