Deep Insight GCN

---

摘要

GCN的原理没有解释明白。本文提出GCN相当于一个拉普拉斯平滑操作，这也是导致过平滑的原因。接着提出了自训练和协同训练的方法。

介绍

1、现实场景对无标签、少标签数据的需求很高。
2、拉普拉斯平滑：混合相邻节点的特征。

相关知识

$A、D、L=D-A、L_{sym}=D^{-\frac{1}{2}}LD^{-\frac{1}{2}}、L_{rw}=D^{-1}L$分别表示邻接矩阵、度矩阵、拉普拉斯矩阵、对称归一化的拉普拉斯将矩阵、随机游走的拉普拉斯矩阵。X特征矩阵。

K阶切比雪夫多项式近似：

$$g_\theta\star\mathrm{s}\approx\sum_{k=0}^K\theta_k^{\prime}T_k(L_{\mathrm{sym}})\mathrm{s},$$

GCN使用一阶（K=1）的切比雪夫多项式，卷积式子：

$$g_\theta\star\mathbf{s}=\theta\left(I+D^{-\frac12}AD^{-\frac12}\right)\mathbf{s},$$

归一化技巧：

$$I+D^{-\frac12}AD^{-\frac12}\to\tilde{D}^{-\frac12}\tilde{A}\tilde{D}^{-\frac12},$$

分析

why GCN Work

拉普拉斯平滑：现在只考虑一层的GCN，包含两步：（1）通过卷积从原始特征中产生新的特征。$Y=\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}X.$

(2)将新的特征矩阵 用于全连接层的输入。

每一个节点的输入的拉普拉斯平滑定义（已经加入自环）：

$$\mathbf{\hat{y}}_i=(1-\gamma)\mathbf{x}_i+\gamma\sum_j\frac{\tilde{a}_{ij}}{d_i}\mathbf{x}_j\quad\text{(for }1\leq i\leq n),$$

我们可以将拉普拉斯平滑写成矩阵形式：

$$\hat{Y}=X-\gamma\tilde{D}^{-1}\tilde{L}X=(I-\gamma\tilde{D}^{-1}\tilde{L})X,$$

令$\gamma=1$，仅使用邻居节点的信息，可以得到：$\hat{Y}=\tilde{D}^{-1}\tilde{A}X$.(拉普拉斯平滑的标准形式)

接下来，使用对称归一化的拉普拉斯$\tilde{D}^{-\frac{1}{2}}\tilde{L}\tilde{D}^{-\frac{1}{2}}$代替上述正则化的拉普拉斯$\tilde{D}^{-1}\tilde{L}$,并且令$\gamma=1$，可以得到，$\hat{Y}=\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}X$,

因为同质图中，往往同类节点是相连的，使用拉普拉斯平滑，使得相邻节点更加相似，便于分类。

when GCN Fail

当层数过多时，使用拉普拉斯平滑会混合不同类的节点，变得难以区分。

假设一个图G有k个联通分量，${\{C_i}\}_{i=1}^{k}$,第i个分量的指示向量定义为$1^{i}\in R^n$,因此可以定义为：

$$\left.\mathbf{1}_j^{(i)}=\left\{\begin{array}{c}1,v_j\in C_i\\0,v_j\not\in C_i\end{array}\right.\right.$$

理论一：

非二分图，

$\begin{aligned}\lim_{m\to+\infty}\left(I-\alpha L_{rw}\right)^m\mathbf{w}=[\mathbf{1}^{(1)},\mathbf{1}^{(2)},\ldots,\mathbf{1}^{(k)}]\theta_1,\end{aligned}$.

$\lim_{m\to+\infty}\left(I-\alpha L_{sym}\right)^m\mathbf{w}=D^{-\frac{1}{2}}[\mathbf{1}^{(1)},\mathbf{1}^{(2)},\ldots,\mathbf{1}^{(k)}]\theta_2,$

证明：可以已知$L_{rw}和L_{sym}$有相同的特征值，但特征向量不同，如果图是连通的，特征值属于[0,2),因此，$(I-\alpha L_{rw})和(I-\alpha L_{sym})$的特征值属于(-1,1].(接下来不证了)

协同训练

标签比较少的情况下，通过一个随机游走矩阵$P=(L+\alpha\Lambda)^{-1}$，预测相邻节点的标签，并加入到训练集中。

自训练

经过一次GCN后，预测其他的节点，并添加到训练集中。