一种基于GCN的半监督学习模型

一种基于GCN的半监督学习模型

这是GCN的经典论文 SEMI -SUPERVISED CLASSIFICATION WITH
GRAPH CONVOLUTIONAL NETWORKS 的阅读笔记.

文章目录

• 一种基于GCN的半监督学习模型

• • 1. 概述

  • 2. 背景知识

  • • 2.1 普通的图上半监督学习
    • 2.2 GCN

  • 3. 文章的主要工作

  • • 3.1 构建神经网络传播规则
    • 3.2 构建神经网络
    • 3.3 实现, 测试和比较
    • 3.4 讨论

  • 4. 代码分析

1. 概述

对于传统的图上的半监督学习, 我们可以在损失函数中加入正则化项\sum_{i, j} (\mathbf{A})_{ij}(f(x_i) - f(x_j))^2, 借助相邻的顶点倾向于拥有相同的标签 这一假设来完成半监督学习过程.

但有时图的边未必能够很好地表示顶点的相似性, 相连的顶点未必倾向于有相同的标签. 在这种情况下, 在损失函数中显式地加入表示图结构的正则化项来迫使图上相连的顶点倾向于拥有相同的标记, 就可能对模型的预测能力造成限制.

为了解决这个问题, 类似于在图像处理中使用卷积来提取一个像素及其周边像素特征, 我们可以在图上定义卷积, 通过卷积来提取一个顶点及其相邻顶点的特征, 从而直接把图的结构用GCN来表示, 避免了图结构在损失函数中显式出现, 从而解决上述问题.

文章提出了一种GCN框架, 即在神经网络中的每一层用一个一阶切比雪夫不等式来对图上卷积进行近似, 通过多层网络的传播达到多阶相邻顶点间特征传播的效果, 并最终实现分类目的. 实验证实这个简单的框架是准确和高效的.

2. 背景知识

2.1 普通的图上半监督学习

对于一个数据集, 当我们知道数据集中的样本之前存在某种关系时, 就可以以这些样本为顶点定义一张图, 如文献的引用关系, 知识点的依赖关系等. 如果数据集中只有部分样本的标签已知, 那么我们可以借助这张图的结构和已知样本的标签来预测其余样本的标签或者数据集之外样本的标签. 我们假设图的邻接矩阵为\mathbf{A}.

(实际上, 即使样本之间没有已知的显式的关系, 我们也可以将样本定义成一张图. 当两个样本的相似度足够高时, 将其连一条边; 或者将所有顶点之间连接一条边, 用边权表示样本间的相似程度. 若用两个样本之差的范数表示其相似程度, 则该图的邻接矩阵可定义为
(\mathbf{A})_{ij}=\left\{ \begin{aligned} e^{\frac{||x_i-x_j||^2}{2\sigma^2}} &,& i \neq j \\ 0&,& i = j \end{aligned} \right.

其中x_i为表示样本i的特征的向量, ||x_i-x_j||为两个样本特征之间的某种闵氏距离.)

对于一个定义在图的顶点空间\mathbf{V}上的实函数f:V \rightarrow R, 定义函数
E(f)=\sum_{i, j} (\mathbf{A})_{ij}(f(x_i) - f(x_j))^2

这个函数表彰了相似的样本是否具有相近的标记. 我们借助在特征上相近的样本点应具有相同的标签 这一假设来完成半监督学习过程. 这样我们可以将损失函数设定为
L = \ \ \ \lambda(\sum_{i, j}\mathbf{A}_{ij}\|\frac{f(x_i)}{\sqrt{d_i}} - \frac{f(x_j)}{\sqrt{d_j}}\|^2) + \sum_i \|f(x_i) - y_i \|^2

即
L = \lambda L_{reg} + L_0
其中 L_0=\sum_i \|f(x_i) - y_i \|^2 使得有标记样本上的预测尽量和真实标记相同, 而正则化项 L_{reg} = \lambda(\sum_{i, j}\mathbf{A}_{ij}\|\frac{f(x_i)}{\sqrt{d_i}} - \frac{f(x_j)}{\sqrt{d_j}}\|^2) 使得在图上相近的样本具有相似的标记.

定义了损失函数后, 我们可以使用EM算法, 多层感知机等方法构造学习器.

但其弊端在于, 有时图的边未必能够很好地表示顶点的相似性. 比如说, 在一个将不同种类的论文分类的任务中, 我们将论文作为图的顶点, 论文的引用关系作为图的边. 一篇物理类论文当然最有可能引用另一篇物理类论文. 然而, 一篇物理类论文或计算机类论文很可能引用一篇数学论文, 一篇化学论文也很可能引用一篇物理类论文, 如果使用上述损失函数训练学习器, 则学习器很可能会把一篇物理类论文预测成一篇数学类论文, 所以相邻的顶点倾向与拥有相同的标签这一假设太过严格, 会限制学习器的预测能力.

2.2 GCN

为了解决上述问题, 我们用图像处理中的卷积神经网络做类比. 在图像处理中, 通过卷积运算可以提取一个像素点及其周围像素点的特征和信息. 我们可以把图片看成一张排列很规则的, 由像素点构成的图. 那么对于不规则的, 一般的图, 应该怎么用卷积提取其特征呢?

首先定义一个和图上顶点的相邻关系和特征传播方式息息相关的矩阵: 拉普拉斯矩阵.
Normalized: L = D - A \\ Unnormalized: L = I - D^{-1/2}AD^{-1/2}
其中, A是邻接矩阵, D_{ii}=\sum_{j}A_{ij}, I是单位矩阵. 显然拉普拉斯矩阵是实对称举证, 故有特征分解
L=U\Lambda U^{-1}=U \Lambda U^{T}
其中U=(\mu_1, ..., \mu_n)为L的特征向量构成的矩阵, \Lambda=diag(\lambda_1, .., \lambda_n)为L的特征向量构成的对角矩阵.

为了定义图上的卷积, 我们先定义图上的傅里叶变换. 普通函数的傅里叶变换是从时域到频域, 图上的傅里叶变换是从图的顶点域到图的拉普拉斯矩阵的特征值域. 定义图上傅里叶变换
\hat{f}(\lambda_l) = \sum_i u_l(i)f(x_i)
式中x_i为顶点i对应的feature向量.

把所有顶点的傅里叶变换写成统一的形式, 有
\hat{f} = Fourier(f) = U^Tf
由于U是正交矩阵, 故傅里叶逆变换为
f = If = UU^{-1}f= UU^Tf= U \hat{f}
即
f = Fourier^{-1}(\hat{f}) = U\hat{f}
设卷积核g是定义在图的顶点域上的函数, 根据傅里叶变换的卷积性质, 有
g*f= Fourier^{-1}(Fourier(g) Fourier(f)) \\ = U diag(\hat{g}(\lambda_1), ..., \hat{g}(\lambda_n))U^Tf \\ = U g_{\theta} U^T f
令f(x) = x, 则经过这样的卷积运算 h(i) = (U g_{\theta}U^Tx )(i), 我们以顶点i为中心提取了图上各个顶点的特征或信息.

这样一来, 我们就可以根据这个卷积运算来定义神经网络的传播规则了:
H^{(l + 1)} = \sigma(UWU^TH^{(l)})
其中, W就是我们要训练的卷积核. 但是, W中将会有n个参数, 计算开销是非常大的. 应该想办法将其简化.

注意到g_{\theta} = diag(\hat{g}(\lambda_1), ..., \hat{g}(\lambda_n))是L的特征值\lambda_1, ..., \lambda_n的函数, 所以可以使用关于\lambda_1, ..., \lambda_n的多项式来对g_{\theta}进行近似. 即
g_{\theta} = \sum \alpha_i \Lambda^i

3. 文章的主要工作

3.1 构建神经网络传播规则

文章使用了一阶切比雪夫多项式来近似图上卷积, 构建了神经网络传播规则:
H^{(l + 1)} = \sigma(\hat{D}^{-1/2}\hat{A}\hat{D}^{-1/2}H^{(l)}W^{(l)}) \\ where \ \hat{A} = A + I_N, \ \hat{D}_{ii} = \sum_j A_{ij}
其中H^{(l)}是上一层的输出, W^{(l)}是这一层的权重或者trainable variable, \sigma是激励函数, A是图的邻接矩阵, \hat{A}和\hat{D}如上定义.

下面是推导和证明.

第2部分最后提到, 可以用多项式来近似卷积核:
g_{\theta} = \sum \alpha_i \Lambda^i
进一步地, 为了避免\Lambda^i中的幂运算有人证明, 可以用切比雪夫多项式
g_{\theta'}(\Lambda) \approx \sum_{k=0} ^K \theta'T_k(\hat{\Lambda})
来近似卷积核.

其中T(x)为切比雪夫多项式, 满足
T_0(x) = 1, T_1(x) = x \\ T_k(x) = 2xT_{k-1}(x) - T_{k-2}(x)
同时对\Lambda​ 进行了放缩\hat{\Lambda} = 2\frac{\Lambda}{\lambda_{max}} - I_N, 这是因为切比雪夫多项式的定义域在[-1, 1]之内.

用切比雪夫多项式可以避免幂运算, 进一步降低了计算开销.

将近似后的卷积核带入卷积计算公式, 有
g * f = U g_{\theta} U^T f = U \sum_{k=0} ^K \theta'T_k(\hat{\Lambda}) U^T f \\ = \sum_{k=0} ^K \theta' U T_k(\hat{\Lambda}) U^T f = \sum_{k=0} ^K \theta'T_k(\hat{L})f
此处用到U\hat{\Lambda}U^T = \hat{L}及 I = UU^T, 其中\hat{L} = 2\frac{L}{\lambda_{max}} - I_N.

若f(x) = x, 则有
g * x = \sum_{k=0} ^K \theta'T_k(\hat{L}) \ x
**文章对这个式子进行了进一步近似: 只取切比雪夫多项式的前两项: **
g * x = \sum_{k=0} ^1 \theta'T_k(\hat{L}) \ x = \theta_0 + \theta_1 \hat{L} x
(我一开始觉得, 既然只取前两项, 那就没有必要强调是从切比雪夫多项式里取出来的了, 直接说从普通的多项式近似 g_{\theta} = \sum \alpha_i \Lambda^i里取前两项就行. 后来发现 , 从普通的多项式中取前两项这一算法就对应着Table 3中的First-order term only, 其效果并不很好. 差别在于使用切比雪夫多项式时经过了种种放缩和替换, 如L放缩为\hat{L}, 以及下面提到的I + D^{-1/2}AD^{-1/2} \rightarrow \hat{D}^{-1/2}\hat{A}\hat{D}^{-1/2}这个trick. 我觉得这是很重要的一点.)

这里的一阶近似, 相当于提取取了图中每个顶点的一阶相邻顶点的特征.

(我们实际上可以证明, 若用来近似卷积的多项式取到第k阶的近似, 则相当于对图上每个顶点的k阶相邻的顶点进行了特征提取.)

由于可以保障\lambda_{max} \approx 2, 所以可以再次做近似
\hat{L} \approx L - I_N
这里取拉普拉斯矩阵L = I_N - D^{-1/2}AD^{-1/2}, D, A的定义同第2部分中的定义相同. 故
g * x \approx \theta_0x - \theta_1 (D^{-1/2}AD^{-1/2})x
再进行简化\theta_0 = -\theta_1 = \theta, 有
g * x \approx \theta(I + D^{-1/2}AD^{-1/2})x
以及一个我觉得很重要的trick: I + D^{-1/2}AD^{-1/2}的一些特征值的绝对值可能大于1, 这样很可能会导致无法稳定收敛!

进行替换:
I + D^{-1/2}AD^{-1/2} \rightarrow \hat{D}^{-1/2}\hat{A}\hat{D}^{-1/2}
最终得到结果:
g * x \approx \hat{D}^{-1/2}\hat{A}\hat{D}^{-1/2}x\Theta
也就是神经网络的传播规则
H^{(l + 1)} = \sigma(\hat{D}^{-1/2}\hat{A}\hat{D}^{-1/2}H^{(l)}W^{(l)})

3.2 构建神经网络

文章利用上述传播规则, 构建了一个两层的神经网络, 该神经网络可基于半监督学习给图的顶点分类.
Z=softmax(\widetilde{A}ReLu(\widetilde{A}XW^0)W^1) \\ where\ \widetilde{A} = \hat{D}^{-1/2}\hat{A}\hat{D}^{-1/2}
该神经网络有两层, 第一层的激励函数是线性整流函数, 第二层的激励函数是softmax函数.X是输入, 其中的每个样本有C个信道或特征, 最后的输出中每个样本对应一个F维的向量, 该向量的第f个分量表示样本被分为第f类的概率.

同时定义了损失函数, 它是所有带有标签的顶点的表示真实类别的one-hot向量Y和其预测输出值F的交叉熵
Error=-\sum_{l\ in\ y_L} \sum_f Y_{lf}\log(Z_{lf})
**该损失函数保障了对于带有标签的顶点, 其预测类别和真实类别尽量相同. 而神经网络中蕴藏的图结构保障了在图上相近的顶点具有相同或相近的预测值, 但又不会向第1部分描述的方法一样因过于严格的假设而降低模型的预测能力. **

文章中使用梯度下降法和full batch来训练网络权重, 并将A保存为稀疏矩阵. 利用sparse-dense矩阵乘法技术, 使得Z的计算复杂度为O(\Epsilon CHF). 这是实现上的一个优化.

3.3 实现, 测试和比较

文章中实现了上述模型, 并在若干个数据集中与若干个其他模型进行了测试和比较.

[外链图片转存失败(img-qq9jD55p-1563460235700)(/home/chen/.config/Typora/typora-user-images/1562510097383.png)]

可以看到, 对于任一数据集, 文章中的模型相对于其他所有模型都有更高的准确率.

同时, 文章还测试了不同的传播规则:

[外链图片转存失败(img-4eIOBChK-1563460235701)(/home/chen/.config/Typora/typora-user-images/1562510229447.png)]

可以看到, 使用切比雪夫多项式近似的传播规则普遍好于未使用的, 而高阶的切比雪夫近似效果未必好于低阶(可能是由于过拟合). 其中, 3.1中提出的传播规则效果最好.

3.4 讨论

本模型相对于其他方法的优势:

基于图的拉普拉斯矩阵正则化的方法(如第1部分的讨论)假设图的边仅仅包含顶点相似性的信息, 限制了学习器的预测能力.

而基于skip-gram的方法需要多步流水线, 难以优化.

本模型可以克服以上问题.

本模型的限制:

• 内存要求: 使用full batch时, 内存要求和数据集大小成线性相关.
• 该模型目前无法直接用于有向图, 需要先将有向图转变为无向图.
• 我们现在假设只需提取一个顶点的k阶相邻顶点的特征, 并且假设顶点的自我连接和与其他顶点连接的边同等重要. 这可能有限制.

4. 代码分析

文章作者使用TensorFlow实现了文章中的模型, 并与其他模型进行了测试和比较. 这里分析实现中的一些比较重要的代码.

layers.py

其中定义了Layer, Dense, GraphConvolution三个类. Layer主要负责接收作用域的名字并输出日志. 后两者继承了Layer.

其中Dense建立一层播规则为Z = \sigma(xW + b)的网络, 它将用于多层感知机的构建;

GraphConvolution创建一层传播规则为Z=\sigma(\sum_i^n xs(i))的网络, s为代码中的supports, 这一传播规则将用于基于一阶或高阶的切比雪夫多项式估算图上卷积的GCN模型的构建, 通过调节supports可以调整使用何种阶数和类型的切比雪夫多项式来估算图上卷积.

        supports = list()
        for i in range(len(self.support)):
            if not self.featureless:
                pre_sup = dot(x, self.vars['weights_' + str(i)],
                              sparse=self.sparse_inputs)
            else:
                pre_sup = self.vars['weights_' + str(i)]
            support = dot(self.support[i], pre_sup, sparse=True)
            supports.append(support)
        output = tf.add_n(supports)

值得注意的是, 这两个类都为其输入建立了用于dropout的计算结点, 输入先流入dropout结点, 再流入计算输出的结点, 这样减少了过拟合的风险.

        if self.sparse_inputs:
            x = sparse_dropout(x, 1-self.dropout, self.num_features_nonzero)
        else:
            x = tf.nn.dropout(x, 1-self.dropout)

此外, 这里还定义了处理稀疏矩阵和普通矩阵乘法的函数. 正如文章中提到的, 代码中有大量稀疏矩阵乘法的应用.

    def dot(x, y, sparse=False):
    """Wrapper for tf.matmul (sparse vs dense)."""
    if sparse:
        res = tf.sparse_tensor_dense_matmul(x, y)
    else:
        res = tf.matmul(x, y)
    return res

metrics.py

定义了计算损失函数的函数和计算正确率的函数. 通过掩码mask掩盖部分数据以保障模型进行半监督学习.

Models.py

基类Model主要负责把网络层连接起来; 收集模型中变量的句柄; 并创建计算损失函数, 准确率和进行优化操作的计算结点:

    # Build sequential layer model
        self.activations.append(self.inputs)
        for layer in self.layers:
            hidden = layer(self.activations[-1])
            self.activations.append(hidden)
        self.outputs = self.activations[-1]
    
        # Store model variables for easy access
        variables = tf.get_collection(tf.GraphKeys.GLOBAL_VARIABLES, scope=self.name)
        self.vars = {var.name: var for var in variables}
    
        # Build metrics
        self._loss()
        self._accuracy()
    
        self.opt_op = self.optimizer.minimize(self.loss)

Model还负责进行模型的存储和加载.

然后是创建多层感知机的类MLP以及创建GCN模型的类GCN. 以GCN类为例, 它的主要任务是调用GraphConvolution类创建网络层(父类Model里的build函数会把这些网络层连接起来), 以及定义 创建各种计算结点(计算损失, 计算准确率等)的函数, 这些函数将被父类Model在build中被调用.

utils.py

定义了计算邻接矩阵的函数, 计算supports以明确切比雪夫多项式近似方案的函数, 处理输入的函数, 处理邻接矩阵的函数等辅助函数.

inits.py

其中定义了创建变量的函数, 四个函数按照不同的初始化方式初始化张量. 神经网络中的权重W都使用glorot初始化, 偏置值b都被初始化为0.