SGC

Simplifying Graph Convolutional Networks

摘要

本文提出：1、去除层之间的非线性变换不影响分类的准确度。

​ 2、分析得出每层是一个低通滤波器。

1、介绍

图 1. GCN 和SGC。 顶行：GCN 在 K 层中重复变换特征向量，然后对最终表示应用线性分类器。 底行：SGC 将整个过程简化为一个简单的特征传播步骤，然后是标准逻辑回归。

1. Simple Graph Convolution

定义：,由，是对称的邻接矩阵，D是度矩阵。每个v~i~都有特征向量x~i~.

2.1 GCN

,表示GCN输入的第一层数据。

特征传播 是GCN与MLP的不同。在每一层的开始，每个节点 v~i~的特征 h~i~与其局部邻域中的特征向量进行平均：

$$\bar{\mathbf{h}}_i^{(k)}\leftarrow\frac1{d_i+1}\mathbf{h}_i^{(k-1)}+\sum_{j=1}^n\frac{a_{ij}}{\sqrt{(d_i+1)(d_j+1)}}\mathbf{h}_j^{(k-1)}.$$

S代表归一化、自环的邻接矩阵。

$$\mathbf{S}=\tilde{\mathbf{D}}^{-\frac12}\tilde{\mathbf{AD}}^{-\frac12},$$

其中是的度矩阵。表示为：

$$\bar{\mathbf{H}}^{(k)}\leftarrow\mathbf{SH}^{(k-1)}.$$

此步骤沿着图的边缘局部平滑隐藏的表示，并最终鼓励本地连接的节点之间的类似预测。

特征变换和非线性过渡。GCN平滑的隐藏特征表示 被线性变换。K-th表示为：

$$\mathbf{H}^{(k)}\leftarrow\mathrm{ReLU}\left(\bar{\mathbf{H}}^{(k)}\boldsymbol{\Theta}^{(k)}\right).$$

分类器。GCN总的公式为：

$$\hat{\mathbf{Y}}_{\mathrm{GCN}}=\text{softmax}\left(\mathbf{SH}^{(K-1)}\boldsymbol{\Theta}^{(K)}\right),\quad\quad(6)$$

2.2. SGC

GCN在每一层中，隐藏表示在一跳之外的邻居之间进行平均。这意味着在 k 层之后，节点从图中距离 k−hops 的所有节点获取特征信息

线性化。

$$\hat{\mathbf{Y}}=\text{softmax}\left(\mathbf{S}\ldots\mathbf{SSX\Theta}^{(1)}\boldsymbol{\Theta}^{(2)}\ldots\boldsymbol{\Theta}^{(K)}\right).$$

简化后（SGC）：

$$\hat{\mathbf{Y}}_{\mathrm{SGC}}=\mathrm{softmax}\left(\mathbf{S}^K\mathbf{X}\boldsymbol{\Theta}\right),$$

逻辑回归。SGC包含一个固定的特征提取/平滑成分：,还有一个softmax回归。

优化细节。略。

3、谱域分析

SGC 对应于图谱域上的固定滤波器。，SGC 充当低通滤波器，在图形上产生平滑特征，附近的节点倾向于共享相似的表示和预测。

3.1. 1.图卷积的预备知识

图拉普拉斯,是一个对称半正定矩阵，特征分解.U由特征向量组成，是一个对角矩阵。其中特征向量表示傅里叶的基，特征值表示图的频率。我们将 x 的图傅立叶变换定义为 ，逆运算由 给出。因此，信号x和滤波器g之间的图卷积运算为：

$$\mathbf{g}*\mathbf{x}=\mathbf{U}\left((\mathbf{U}^{\top}\mathbf{g})\odot(\mathbf{U}^{\top}\mathbf{x})\right)=\mathbf{U}\hat{\mathbf{G}}\mathbf{U}^{\top}\mathbf{x},$$

其中 对角矩阵，其中对角线对应于频谱滤波器系数。

图卷积可以通过拉普拉斯算子的 k 阶多项式来近似:

$$\hat{\mathbf{UGU}}^\top\mathbf{x}\approx\sum_{i=0}^k\theta_i\boldsymbol{\Delta}^i\mathbf{x}=\mathbf{U}\left(\sum_{i=0}^k\theta_i\boldsymbol{\Lambda}^i\right)\mathbf{U}^\top\mathbf{x},\quad\text{(10)}$$

θ~i~代表系数。在这种情况下，滤波器系数对应于拉普拉斯特征值的多项式。也就是说

GCN采用k = 1，θ~0~ = 2θ and θ~1~ = −θ。GCN表示为：$\mathbf{g}\mathbf{x}=\theta(\mathbf{I}+\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2})\mathbf{x}.$使用**“重整化技巧”*使得代替.

3.2. SGC和低通滤波

GCN 中导出的初始一阶切比雪夫滤波器对应于传播矩阵 。

因为归一化的拉普拉斯是,那么.

阶的特征传播意味着滤波器系数下图 说明了与 相关的滤波操作，其中传播步数不同 K ∈ {1,…,6}。

Cora 数据集上不同传播矩阵的特征（红色）和滤波器（蓝色）频谱系数

正如人们所观察到的，的高功率会导致滤波器系数爆炸，并在频率 λ~i~ < 1 处过度放大信号。

为了解决与一阶切比雪夫滤波器相关的潜在数值问题，采用归一化技巧。增强归一化邻接矩阵,相应地，我们定义增强归一化拉普拉斯.因此，我们可以将与相关的谱滤波器描述为基础拉普拉斯算子的特征值的多项式。也就是说；.

我们现在分析 的频谱，并表明向图中添加自循环会缩小相应归一化拉普拉斯算子的频谱（特征值）。

定理1。让,分别表示最小最大的特征值（.）。让分别表示最小最大的特征值(),可以得到：

$$0=\lambda_1=\tilde{\lambda}_1<\tilde{\lambda}_n<\lambda_n.$$

定理1表明，加入自环γ > 0后，归一化图拉普拉斯算子的最大特征值变小（证明见补充材料）。

上图描述了与标准化邻接相关的过滤操作。S~adj~的谱域范围[0,2],因此 Sadj 的奇次幂在频率 λ~i~> 1 处产生负滤波器系数.最大特征值从2缩小到约1.5，然后消除负系数的影响。该缩放频谱允许通过采用 的 K > 1 来定义的滤波器充当低通型滤波器。

4.相关工作