Dual Graph Convolutional Networks for Graph-Based Semi-Supervised Classification

Dual Graph Convolutional Networks for Graph-Based Semi-Supervised Classification

• Introduction
• • Local Consistency Convolution:ConvA
  • Global Consistency Convolution:ConvP
  • 整合局部和全局一致性

Introduction

这篇文章的主要思想，是基于半监督学习的两个基本假设 ：

• （1）局部一致性 ：距离比较近的数据，通常有相同的标签；
• （2）全局一致性 ：处在相似的上下文中的数据，通常有相同的标签。如下图所示，该图卷积网络包括两个通路，ConvA嵌入了半监督分类局部一致性的信息，是一个传统的图卷积过程；ConvP 嵌入了半监督分类全局一致性的信息，是作者的一个创新点。在两个通路后，作者设计了一个新的Loss 函数，可以将局部一致性和全局一致性完美结合，取得一个好的实验效果。
• 

Local Consistency Convolution:ConvA

convA 的计算公式如下：

• \tilde{A} = A + I_N 是无向图G的自环邻接矩阵。
• I_N是单位矩阵。
• \tilde{D}_{ii} = \sum_j \tilde{A}_{ij} 是\tilde{A} 的度矩阵。
• W^{(i)}是可训练的权重矩阵，即网络的参数。
• \tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}是对邻接矩阵A的归一化
• \sigma(\cdot)是激活函数，比如ReLU。
• Z^{(i)} \in \mathbb{R}^{N \times D}是第i层的激活矩阵，即网络的输出。
• Z^{(0)}=X第一层为输入。

对邻接矩阵进行归一化处理，可以很好的在每一层中进行1-hop\ diffusion\ process。但是，只使用局部一致性会使得一部分并不属于一类的点距离很近，以至于被错误的分为一类。

举例
按局部信息进行计算，8与30距离很近，但实际标签一个为红一个为绿，标签不同。因此为解决这个问题，引入全局一致性信息，引入了ConvP

Global Consistency Convolution:ConvP

作者使用随机游走的策略 ，生成频率矩阵，进而生成PPMI矩阵。PPMI矩阵可以很好的嵌入语义信息，利用数据的全局一致性。

获得频率矩阵 F:

• （1）确定节点的随机游走长度\gamma，采样次数w，初始化频率矩阵F值为0。

• （2）以节点x_i为起点，开始以0为步长随机游走，得到所有可能的情况，表示为点对集合S=\{{(x_n,x_m)}\}，接着以等式（8）作为概率采样w次，得到w对点对。

• （3）对于点对(x_n,x_m)，在频率矩阵中对应位置F_{n,m},F_{m,n}​ 对应加1。

• （4）将游走步长1逐渐变化到\gamma，循环(2)(3)步骤。

• （5）对于所有的节点，执行(2)(3)(4)步骤得到频率矩阵F。
  伪代码如下：
  
  马尔可夫链描述了随机游走所访问的节点的顺序，通常被称为随机游走。每个节点的转移概率可以由等式（8）计算得到：
  
  构建PPMI矩阵P：
  
  

• ConvP的热度图想对于ConvA有所不同

• 通过t-stochastic\ neighbor\ embeddings(SNEs)对结果进行比较，8与30距离有所增大
  PPMI介绍
  
  
  

• 除了这个以外，我们还可以在加入拉普拉斯平滑
  
  

整合局部和全局一致性

DualGCN伪代码如下：

DGCN ：Dual Graph Convolutional Networks for Graph-Based Semi-Supervised Classification
https://github.com/ZhuangCY/DGCN