Graph Convolutional Networks Meet Markov Random Fields: Semi-Supervised Community Detection in Attri

Graph Convolutional Networks Meet Markov Random Fields: Semi-Supervised Community Detection in Attribute Networks(AAAI-19)

应用场景：community 分类

除了网络拓扑结构之外，还有两点信息可以利用：

1. prior community membership，比如学生和教职员工
2. 结点的语义信息，比如个人爱好等

利用少量的1就可以明显的提高分类可信度，也可以把问题转换为半监督学习

利用2可以把社区检测扩展到包含属性网络

目前的社区检测方法包括：层次聚类、统计建模、图嵌入

本文将GCN和MRF结合

GCN有两个缺点：

1. GCN旨在得到结点的嵌入表示，并不能包含社区信息，没有考虑社区的属性
2. GCN能得到粗粒度分类，因为GCN缺乏平滑约束来强制相似或者邻居结点得到相同的标签

MRF包含一元势函数

和成对势函数

在图片分割里，一元势函数表示每个像素的分类，成对势函数表示相邻像素之间的属性，比如颜色。

它在附近的节点之间提供了平滑的标记，并能够细化粗略标记的社区。

本文将MRF当成一个新的卷积层，放在最后一层，构建一个end-to-end的图网络。GCN-GCN-MRF

本文对成对势函数的定义：

1. reward the edges between nodes in the same community,

2. penalize the edges across different communities,

3. penalize missing edges (nonedges) between nodes in the same community,

4. reward nonedges across different communities.
   
   

Method

MRFasGCN

$X_{n*m}$Xn∗m​：feature matrix KaTeX parse error: Got function '\^' with no arguments as superscript at position 3: A^\̲^̲_{n*n}: 邻接矩阵 $K_{n*n}$Kn∗n​: 基于A,X计算得到的结点相似矩阵

三组参数W0,W1,W2

第一层原始GCN用ReLU来捕捉非线性关系

第二层原始GCN使用softmax得到分类概率输入到MRF

第三层MRF利用成对势函数来构建一个面向社区的模型来平滑GCN的输出。

怎么把MRF变成GCN？

首先使用上一层GCN的输出作为一元势函数

为了展现两个社区之间的差异，比如例如，“政治”社区比“体育”社区更类似于“经济”社区。引入参数矩阵$W^2_{u,v}$Wu,v2​来表示两个结点之间的社区相似性关系

其中

然后定义两个节点的归一化的余弦相似度
定义两个结点之间的最终相似度

最终成对势函数

最后的势函数function：

用上周论文里相同的方法，求一个用KL散度最小化来近似E的函数作为分布函数，结果如下：
利用四个步骤解释公式中$Q_i(C_i)$Qi​(Ci​)

1. 初始化

2. 信息传递，分为两部分：

   • 节点之间传递

• 社区之间传递
• 

3. 加上一元势函数并取负数

4. 归一化：使用softmax函数

利用卷积的方式呈现计算流程：

损失函数：交叉熵

实验

数据集

GCN vs GCN+MRF MRFasGCN

GCN+MRF就是GCN计算先验概率，然后用MRF微调，与MRFasGCN不同

MRFasGCN vs baselines

baseline:We compared MRFasGCN with three types of the state-of-the-art methods. The first includes DCSBM (Karrer and Newman 2011) and NetMRF (He et al. 2018), which both use network topology alone. The second type includes PCLDC (Yang et al. 2009), SCI (Wang et al. 2016) and NEMBP (He et al. 2017), which use both topology and attribute information. The third type includes WSCDSM (Wang et al. 2018) and DIGCN (Li et al. 2018), which are semi-supervised methods on attribute networks.

可解释性

a. 2395号结点被邻居带星号结点（有标签）影响。MRF通过平滑和对邻居节点计算相似度来纠正分类

b. 同上

综上，MRF可以改善半监督学习效果