SGC：简化图卷积网络 《Simplifying Graph Convolutional Networks》

论文地址：https://arxiv.org/abs/1902.07153

一、简介

​ 图卷积神经网络($\text{Graph Convolutional Networks,GCNs}$)是卷积神经网络在图数据上的变体，其通过在非线性函数前堆叠若干个一阶谱过滤器来学习图数据的表示。近期，$\text{GCNs}$及其变体在各种图应用领域都实现了state-of-the-art。但是，由于$\text{GCNs}$是在神经网络“复兴”后提出的，因此不可避免的继承了神经网络的复杂性和难以解释性。

​ 本文认为对于那些需求低的应用来说，$\text{GCNs}$继承自神经网络的复杂性是不必要的。因此，本文的目标是推断出在$\text{GCN}$之前基于"传统"路径能够获得的最简单模型。具体来说，本文通过移除$\text{GCNs}$层之间的非线性并简化结果函数为单一线性变换，从而减少了$\text{GCNs}$的额外复杂性。实验显示，最终得到的模型可以与$\text{GCNs}$像媲美，且计算效率更高、拟合参数更少。本文将这个模型称为$\text{SGC(Simple Graph Convolution)}$。

​ 直觉上，$\text{SGC}$是可解释的，且本文从图卷积的角度提供了理论分析。$\text{SGC}$中的特征抽取对应于单个固定的过滤器。$\text{Kipf\&Welling}$发现$\text{renormalization trick}$能够改善任务准确率，本文证明这个方法能够有效的缩小图的谱域，且应用在$\text{SGC}$上能够产生低通过滤器。

​ 通过在基准数据集上的评估，展示了$\text{SGC}$能够与$\text{GCNs}$及其他state-of-the-art图神经网络媲美。然而，$\text{SGC}$的速度会快很多，甚至在最大的评估数据集上比$\text{FastGCN}$快2个数量集。此外，本文还证明了$\text{SGC}$能够有效的扩展至下游任务中。

二、方法

​ $\text{GCNs}$将带有部分标签的节点作为输入，并为图中的所有节点生成预测标签。形式化地，定义一个图为$\mathcal{G}=(\mathcal{V},\text{A})$，其中$\mathcal{V}$表示由节点{v1,…,vn}\{v_1,\dots,v_n\}{v1​,…,vn​}组成的顶点集合；$\text{A}\in {\mathbb{R}}^{n\times n}$是对称邻接矩阵，其中$a_{ij}$表示节点$v_i$和$v_j$的权重，缺失的边通过$a_{ij}=0$来表示。定义度矩阵$\text{D}=\text{diag}(d_1,\dots ,d_n)$为一个对角矩阵，其对角线上的每个分量是等于邻接矩阵的行求和$d_i={\sum }_j{a}_{ij}$。

​ 图中的每个节点$v_i$对应一个$d$维特征向量${\text{x}}_i\in {\mathbb{R}}^d$。整个特征矩阵$\text{X}\in n\times d$则是堆叠了$n$个特征向量，即$\text{X}=[{\text{x}}_1,\dots ,{\text{x}}_n{]}^{\top }$。每个节点都属于$C$个类别中的一个，并使用$C$维one-hot编码向量yi∈{0,1}C\textbf{y}_i\in\{0,1\}^Cyi​∈{0,1}C表示。

​ 模型仅知道一部分节点的标签，并希望预测节点的未知标签。

1. 图卷积神经网络$\text{GCN}$

​ 类似于$\text{CNN}$或者$\text{MLP}$，$\text{GCN}$也是通过多个层来从每个节点的特征${\text{x}}_i$中学习新的特征表示，并用线性分类器进行分类。对于第$k$个图卷积层来说，所有节点的输入表示为矩阵${\text{H}}^{(k-1)}$，输出节点表示为${\text{H}}^{(k)}$。自然而然地，初始化节点表示就是原始输入的特征：
$${\text{H}}^{(0)}=\text{X}\text{\hspace{1em}(1)}$$
其作为第1个$\text{GCN}$的输入。

​ 一个$\text{K}$层的$\text{GCN}$等同于在图中的每个节点特征${\text{x}}_i$上应用$\text{K}$层的$\text{MLP}$，且每个节点的向量表示都是平均了其邻居节点的表示。在每个图卷积层中，节点的向量表示会在三个阶段被更新：(1) 特征传播；(2) 线性变换; (3) 非线性激活函数。

1.1 特征传播

​ $\text{GCN}$与$\text{MLP}$的主要区别就是特征传播。在每层的开始，每个节点$v_i$的特征${\text{h}}_i$是平均了它局部邻居的特征向量
$${\bar{\text{h}}}_i^{(k)}\leftarrow \frac{1}{d_i+1}{\text{h}}_i^{(k-1)}+\sum _{j=1}^n\frac{a_{ij}}{\sqrt{(d_i+1)(d_j+1)}}{\text{h}}_j^{(k-1)}\text{\hspace{1em}(2)}$$
为了更加紧凑，这里将整个图上的更新表示为简单的矩阵操作。具体来说，令$\text{S}$表示规范化邻接矩阵
$$\text{S}={\tilde{\text{D}}}^{-1/2}\tilde{\text{A}}{\tilde{\text{D}}}^{-1/2}\text{\hspace{1em}(3)}$$
其中，$\tilde{\text{A}}=\text{A+I}$且$\tilde{\text{D}}$是$\tilde{\text{A}}$的度矩阵。那么，等式$(2)$中所有节点的同步更新能够简化为一个稀疏矩阵乘法
$${\tilde{\text{H}}}^{(k)}\leftarrow {\text{SH}}^{(k-1)}\text{\hspace{1em}(4)}$$
直觉上，这步操作沿着图的边平滑了局部向量表示，并且鼓励局部的点具有相似的预测。

1.2 线性变换与非线性激活

​ 经过局部平滑后，$\text{GCN}$层与$\text{MLP}$层等价。每个层都被关联一个可学习权重${\Theta }^{(k)}$，用于对经过平滑的特征向量进行线性变换。最后，在特征向量${\text{H}}^{(k)}$输出前，使用$\text{ReLU}$这样的非线性激活函数对输出进行变换。整体来说，第$k$层的向量表示更新规则为
$${\text{H}}^{(k)}\leftarrow \text{ReLU}({\tilde{\text{H}}}^{(k)}{\Theta }^{(k)})\text{\hspace{1em}(5)}$$

1.3 分类器

​ 类似于$\text{MLP}$，对于节点分类任务，$\text{GCN}$会在最后一层使用$\text{softmax}$分类器预测标签概率。$n$个节点的类别预测表示为$\hat{\text{Y}}\in {\mathbb{R}}^{n\times C}$，其中${\hat{y}}_{ic}$表示节点$i$属于类别$c$的概率。$\text{GCN}$第$K$层的类别预测记为
$${\hat{\text{Y}}}_{\text{GCN}}=\text{softmax}({\text{SH}}^{(K-1)}{\Theta }^{(K)})\text{\hspace{1em}(6)}$$
其中，$\text{softmax}(\text{x})=\text{exp}(\text{x})/{\sum }_{c=1}^C\text{exp}(x_c)$。

2. $\text{SGC(Simple Graph Convolution)}$

​ 在传统的$\text{MLP}$层中，更深的层能够增加表达能力。因此，深层的$\text{MLP}$能够构建特征的层次结构，即第二层的特征是在第一层特征的基础上构建的。在$\text{GCNs}$中，这些层还有第二个重要作用：每层的隐藏表示会被其一跳邻居平均。这也意味着，一个经过$k$层的阶段特征来源于其在图中的所有$k$跳邻居。这种方式类似于卷积神经网络，模型深度增加的同时也增加了特征的感知域。虽然随着深度的增加，卷积网络的效果会变好，但是典型的$\text{MLP}$在3或4层之后就收益很小了。

2.1 线性化

​ 假设两个$\text{GCN}$层间的非线性变换并不是必须的，模型的收益主要来自于局部平均。那么，移除每层的非线性变换并保留最后的$\text{softmax}$。这样得到的模型仍然是线性的，且与$K$层的$\text{GCN}$具有相同的感知域
$$\hat{\text{Y}}=\text{softmax}(\text{S}\dots \text{SSX}{\Theta }^{(1)}{\Theta }^{(2)}\dots {\Theta }^{(k)})\text{\hspace{1em}(7)}$$
为了简化表示，将规范化邻接矩阵的重复乘法表示为$\text{S}$的$K$次方法${\text{S}}^K$。此外，将权重矩阵重新参数化为单一的矩阵$\Theta ={\Theta }^{(1)}{\Theta }^{(2)}\dots {\Theta }^{(K)}$。那么最终的分类器表示为
$${\hat{\text{Y}}}_{\text{SGC}}=\text{softmax}({\text{S}}^K\text{X}\Theta )\text{\hspace{1em}(8)}$$
本文将其称为$\text{SGC(Simple Graph Convolution)}$。

2.2 Logistic回归

​ 通过观察等式$(8)$能够获得$\text{SGC}$的直觉解释：分离特征抽取和分类器。即$\text{SGC}$可以看做是由一个固定的特征抽取/平滑组件$\bar{\text{X}}={\text{S}}^K\text{X}$，后面跟一个线性$\text{logistic}$回归分类器$\hat{\text{Y}}=\text{softmax}(\bar{\text{X}}\Theta )$组成。由于$\bar{\text{X}}$不需要权重，因此计算$\bar{\text{X}}$就等价于特征预处理步骤。整个模型的训练就变成了在预处理特征$\bar{\text{X}}$上的直接进行多类别$\text{logistic}$回归。

三、谱分析($\text{Spectral Analysis}$)

1. 图卷积

​ 图数据上的$\text{Fourier}$分析依赖于图$\text{Laplacian}$算子的谱分解。

​ 图$\text{Laplacian}$矩阵$\Delta =\text{D-A}$(规范化版本${\Delta }_{sym}={\text{D}}^{-1/2}\Delta {\text{D}}^{-1/2}$)为对称正定矩阵。该矩阵的特征分解为$\Delta =\text{U}\Lambda {\text{U}}^{\top }$，其中$\text{U}\in {\mathbb{R}}^{n\times n}$是由正交特征向量组成，且$\Lambda =\text{diag}({\lambda }_1,\dots ,{\lambda }_n)$为特征值对角矩阵。$\text{Laplacian}$矩阵的特征分解能够允许在图域上定义等价的傅里叶变换，特征向量对应$\text{Fouries}$的模，特征值对应图上的频率。基于此，令$\text{x}\in {\mathbb{R}}^n$表示定义在图上顶点的信号，那么$\text{x}$的图上$\text{Fouries}$变换为$\hat{\text{x}}={\text{U}}^{\top }\text{x}$且逆操作为$\text{x}=\text{U}\hat{\text{x}}$。因此，信号$\text{x}$和过滤器$\text{g}$的图卷积操作定义为
$$\text{g}\ast \text{x}=\text{U}(({\text{U}}^{\top }\text{g})\odot ({\text{U}}^{\top }\text{x}))=\text{U}\hat{\text{G}}{\text{U}}^{\top }\text{x}\text{\hspace{1em}(9)}$$
其中，$\hat{\text{G}}=\text{diag}({\hat{g}}_1,\dots ,{\hat{g}}_n)$表示对角矩阵，其对角线元素对应谱过滤器系数。

​ 图卷积能够通过$\text{Laplacian}$的k阶多项式完成近似，
$$\text{U}\hat{\text{G}}{\text{U}}^{\top }\text{x}\approx \sum _{i=0}^k{\theta }_i{\Delta }^i\text{x}=\text{U}\left(\sum _{i=0}^k{\theta }_i{\Lambda }^i\right){\text{U}}^{\top }\text{x}\text{\hspace{1em}(10)}$$
其中，${\theta }_i$表示系数。在这个例子中，过滤器系数对应于$\text{Laplacian}$特征值的多项式，即$\hat{\text{G}}={\sum }_i{\theta }_i{\Lambda }^i$或者相当于$\hat{g}({\lambda }_i)={\sum }_i{\theta }_i{\lambda }_j^i$。

​ 图卷积神经网络利用了等式$(10)$的线性近似，该线性近似具有系数${\theta }_0=2\theta$和${\theta }_1=-\theta$。得到基本的$\text{GCN}$卷积操作
$$\text{g}\ast \text{x}=\theta (\text{I}+{\text{D}}^{-1/2}{\text{AD}}^{-1/2})\text{x}\text{\hspace{1em}(11)}$$
在其最终的设计中，将矩阵$\text{I}+{\text{D}}^{-1/2}{\text{AD}}^{-1/2}$替换为规范化版本${\tilde{\text{D}}}^{-1/2}\tilde{\text{A}}{\tilde{\text{D}}}^{-1/2}$，其中$\tilde{\text{A}}=\text{A+I}$且$\tilde{\text{D}}=\text{D+I}$。

2. $\text{SGC}$和低通滤波

​ $\text{GCN}$中初始的过滤器对应于传播矩阵${\text{S}}_{\text{1-order}}=\text{I}+{\text{D}}^{-1/2}\text{A}{\text{D}}^{-1/2}$。规范化拉普拉斯算子为${\Delta }_{\text{sym}}=\text{I}-{\text{D}}^{-1/2}{\text{AD}}^{-1/2}$，那么${\text{S}}_{\text{1-order}}=2\text{I}-{\Delta }_{\text{sim}}$。因此，特征传播${\text{S}}_{\text{1-order}}^K$意味着过滤系数${\hat{g}}_i=\hat{g}({\lambda }_i)=(2-{\lambda }_i{)}^K$，其中${\lambda }_i$表示${\Delta }_{\text{sym}}$的特征值。上图展示了传播步骤K∈{1,…,6}K\in \{1,\dots,6\}K∈{1,…,6}的变化与${\text{S}}_{\text{1-order}}$过滤操作的关系。可以观察到，高阶${\text{S}}_{\text{1-order}}$将会导致过滤系数的爆炸并在频率${\lambda }_i<1$上过度放大。

​ 为了解决一阶过滤器的问题，$\text{Kipf\&Welling}$等人提出了$\text{renormalization trick}$。该方法通过为所有节点加入自循环后的归一化邻接矩阵来替换${\text{S}}_{\text{1-order}}$。本文称得到的传播矩阵为增强的归一化邻接矩阵${\tilde{\text{S}}}_{adj}={\tilde{\text{D}}}^{-1/2}\tilde{\text{A}}{\tilde{\text{D}}}^{-1/2}$，其中$\tilde{\text{A}}=\text{A+I}$且$\tilde{\text{D}}=\text{D+I}$。相应的，定义增强规范化$\text{Laplacian}$矩阵${\tilde{\Delta }}_{sym}=\text{I}-{\tilde{\text{D}}}^{-1/2}\tilde{\text{A}}{\tilde{\text{D}}}^{-1/2}$。这样，就可以将关于${\tilde{\text{S}}}_{adj}$的谱过滤器描述为$\text{Laplacian}$矩阵特征值的多项式，即$\hat{g}({\tilde{\lambda }}_i)=(1-{\tilde{\lambda }}_i{)}^K$，其中${\tilde{\lambda }}_i$是${\tilde{\Delta }}_{sym}$的特征值。

• 定理1

  令$\text{A}$是一个无向、有权且无孤立点的简单图的邻接矩阵，其对应的度矩阵为$\text{D}$。令$\tilde{\text{A}}=\text{A}+\gamma \text{I}$为增强邻接矩阵($\gamma >0$)，其对应的度矩阵为$\tilde{\text{D}}$。令${\lambda }_1$和${\lambda }_n$表示${\Delta }_{sym}=\text{I}-{\text{D}}^{-1/2}{\text{AD}}^{-1/2}$的最小特征这和最大特征值。类似地，${\tilde{\lambda }}_1$和${\tilde{\lambda }}_n$则是${\tilde{\Delta }}_{sym}=\text{I}-{\tilde{\text{D}}}^{-1/2}\tilde{\text{A}}{\tilde{\text{D}}}^{-1/2}$的最小特征性和最大特征值。则有
  $$0={\lambda }_1={\tilde{\lambda }}_1<{\tilde{\lambda }}_n<{\lambda }_n\text{\hspace{1em}(12)}$$

定理1表明，在加入自循环$\gamma >0$后，规划化$\text{Laplacian}$矩阵的最大值变小。