论文笔记-Semi -Supervosed Classifica

2021-07-27 本文已影响0人升不上三段的大鱼

这篇文章提出了图网络一个比较经典的模型Graph Convolution Network，用神经网络来编码图结构，从而避免了损失函数中基于图的显式正则化。

数学符号

$A$ ：图的邻接矩阵
$\tilde{A} = A + I_N$ ：无向图的邻接矩阵加上自连接
$\tilde{D}$ ：对角矩阵， $\tilde{D}_{ii}=\sum_j \tilde{A}_{ij}$
$W^{(l)}$ ：第 $l$ 层的可训练权矩阵
$H^{(l)}$ ：第 $l$ 层的激活矩阵， $H^{(0)}=X$
$\sigma$ ：激活函数
$x$ ：一个N维的信号
$\theta$ ：滤波器的参数
$g_{\theta}$ ：参数为 $\theta$ 的滤波器 $g_{\theta}=diag(\theta)$
$L$ ：归一化图拉普拉斯算子 $L=I_N-D^{- \frac{1}{2}}AD^{- \frac{1}{2}}$
$U$ ：归一化图拉普拉斯算子的特征向量， $L=U\Lambda U^T$
$\Lambda$ ：具有其特征值的对角矩阵
$T_k(x)$ ：最高K阶切比雪夫多项式
$\tilde{\Lambda} = \frac{2}{\lambda_{max}} \Lambda-I_N$
$\lambda_{max}$ ：L的最大特征值
$\theta'$ ：是一个切比雪夫系数的向量
$\tilde{L}$ ： $\tilde{L}=\frac{2}{ \lambda _{max}}L-I_N$

1. 介绍

对于图的节点的分类任务，只有一小部分的节点是有标记的，这个问题可以被称为基于图的半监督学习，根据传统方法，其中的标签信息要通过某种形式的基于图的显式正则化在图上做平滑。

在这篇文章中，作者直接使用了神经网络模型 $f(X,A)$ 对图结构进行编码，并对所有带标签的节点在监督目标 $L_0$ 上进行训练，从而避免了损失函数中基于图的显式规则化。在图的邻接矩阵上施加条件 $f(·)$ ，将让模型从有监督的损失中分配梯度信息，并使其能够学习有标签和无标签节点的表示。

这篇文章的贡献包括：首先，作者介绍了一个简单且性能良好的分层映射规则，能直接作用于图的神经网络模型，并展示了如何从谱图卷积的一阶近似中得到启示，作者展示了如何使用这种形式的基于图的神经网络模型，对图中的节点进行快速并且可扩展的半监督分类。在多个数据集上的实验表明，这个模型在分类精度和效率方面都优于当时最先进的半监督学习方法。

2. 快速近似卷积算法

作者提供了一个特定的基于图的神经网络模型 $f(X,A)$ 的理论动机，将在本文的其余部分使用。作者提出多层图层卷积网络（GCN），具有如下逐层传播规则：

$H^{(l+1)} = \sigma(\tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}}H^{(l)} W^{(l)})$

对于这个公式，作者在自己的博客里给出了解释。

对于一个图卷积网络的模型，目标是学习一个可以表现图上的特征的函数，其中输入是描述每个节点特征的特征矩阵 $H$ ，以及描述图结构的邻接矩阵 $A$ ，输出是每一个节点的输出特征。神经网络的每一层都可以被写作一个非线性的函数 $H^{(l+1)} = f(H^{(l)}, A)$

首先考虑一个简单的逐层传播的规则，
$f(H^{(l)},A) = \sigma(AH^{(l)}W^{(l)})$

相当于图的邻接矩阵 $A$ 和节点的特征 $H$ ，和一个可以训练的参数矩阵 $W$ 做内积，再通过一个非线性的激活函数，比如ReLU。

这个简单的模型有两个局限性：

与邻接矩阵 $A$ 的乘法意味着将所有相邻节点的所有特征向量相加（想一下矩阵乘法），但是少了这个节点本身的特征。这个问题可以通过在 $A$ 上加上一个单位矩阵来解决。
邻接矩阵 $A$ 通常没有经过归一化，与 $A$ 的乘法会完全改变特征向量的尺度，所以需要将 $A$ 进行归一化。比较常用的对称归一化，即 $D^{- \frac{1}{2}} AD^{-\frac{1}{2}}$ 。

结合以上两点，上面的传播规则就成了： $f(H^{(l)},A) = \sigma(\tilde{D}^{-\frac{1}{2}}\tilde{A} \tilde{D}^{-\frac{1}{2}}H^{(l)}W^{(l)})$

在下文中，作者展示了这种传播规则的形式可以通过图上局域谱滤波器的一阶近似来激励得到。

2.1 谱图卷积

考虑图上的谱卷积，定义为信号 $x∈R^N$ 与由傅立叶域中的 $θ∈R^N$ 参数化的滤波器 $g_θ=diag(θ)$ 相乘，即： $g_θ \star x=Ug_θU^Tx$

因为 $U$ 是归一化图拉普拉斯矩阵 $L$ （图的另一种矩阵表示形式）的特征向量， $\Lambda$ 是 $L$ 的特征值的对角矩阵，可以将滤波器 $g_θ$ 理解为特征值的函数，也就 $g_θ(\Lambda)$ 。
为了避免过于复杂的计算，可以用切比雪夫多项式 $T_k(x)$ 的最高至K阶的截断展开来逼近：
$g_θ'(\Lambda) \approx \sum_{k=0} ^{K} \theta'_k T_k(\tilde{\Lambda})$

代回到对于一个信号与一个卷积核的卷积公式，可以得到
$g_θ \star x \approx \sum_{k=0} ^{K} \theta'_k T_k(\tilde{L})x$

需要注意的是，这个表达式现在是局部的，因为它是拉普拉斯算子中的K阶多项式，也就是说，它仅取决于距离中心节点（第k阶邻域）最大步数为K的节点。计算上面公式的复杂性是在边数上是线性的。Defferrard 在2016年使用这个K局部的卷积定义了图上的卷积神经网络。

（个人笔记）
上面这部分大概就是用切比雪夫多项式来计算了图上的谱卷积（spetral graph convolution），这里就涉及到了图的傅里叶变换。

先回忆一下一般时序信号上的傅里叶变换是怎样的。

对于一个连续周期时间信号 $f(t)$ ，假设它的周期是 $T$ ，可以将它展开为傅里叶级数：
$f(t) = \sum_{n= -\infty}^{\infty} F(n) e^{j 2 \pi n t/T} =\sum_{n= -\infty}^{\infty} F(k\omega) e^{jk \omega t}$
$F(k \omega) = \frac{1}{T} \int_{- \frac{T}{2}}^{\frac{T}{2}} f(t) e^{-jk \omega t} dt$

利用欧拉公式： $e^{jt} = cos(t) + jsin(t)$ ，可以将 $f(t)$ 写作正弦函数与余弦函数的和，对于实值函数：
$f(t) = \frac{a_0}{2} + \sum_{n=1}^{\infty} [ a_ncos(\omega t) + b_n sin(\omega t)]$

可以直观的理解为，这个周期函数可以看作是无限个谐波分量的线性叠加。上面的 $\omega = \frac{ 2 \pi n}{T}$ ，是角速度，如果以 $\omega$ 为坐标绘制函数，得到的就是频域上的波形。

连续形式的傅里叶变换是傅里叶级数的推广，当信号 $f(t)$ 满足一定条件时，频域上的函数 $F(\omega)$ 为：
$F(\omega) = \int_{-\infty}^{\infty} f(t) e^{-j \omega t} dt$

在图信号 $x$ 上，图的傅里叶变换被定义为：
$\hat{x} = U^T x$
其中 $U$ 是图的拉普拉斯矩阵的特征向量组成的矩阵， $\tilde{x}$ 是信号 $x$ 进行了图傅里叶变换之后得到的系数，这些系数是每个图傅里叶分量对图信号做出的贡献。

对于第 i 个 $x_i$ 对应的图傅里叶分量 $u_i$ ，它的频率是 $\lambda_i$ ，是与 $u_i$ 对应的特征值。现在对于每一个 $x_i$ 进行滤波操作，滤波器可以被理解为特征值的函数（时域上的卷积等于频域上相乘）：
$\hat{x}'_i = \hat{x}_i \cdot g_{\theta}(\lambda_i)$
写成矩阵形式就是：
$\hat{x}' = g_{\theta}(\Lambda) \cdot \hat{x} = g_{\theta}(\Lambda) \cdot U^T x$
这样就得到了傅里叶域上的经过滤波的图信号 $\hat{x}'$ ，通过图傅里叶逆变换将信号重建到图域得到：
$x' = U \hat{x}' = U g_{\theta}(\Lambda) U^T x$
也就是说一个图信号 $x$ 与一个滤波器 $g_{\theta}$ 卷积之后，得到的信号为：
$g_θ \star x=Ug_θ(\Lambda)U^Tx$
这也就是论文中 2.1节一开始就提出来的那个图卷积的公式。

计算 $U g_{\theta}(\Lambda) U^T$ 的成本很高，为此可以采用切比雪夫多项式对滤波器进行建模。切比雪夫多项式的定义域是 $[-1,1]$ ，因此需要对特征值进行平移缩放，也就是：
$\tilde{\Lambda} = \frac{2}{\lambda_{max}} \Lambda-I_N$

2.2 分层线性模型

可以通过叠加多个卷积层来建立基于图卷积的神经网络模型，每一层后跟一个点式非线性函数。现在，假设我们限制了逐层卷积运算限制在K=1，即一个线性的函数，因此在图拉普拉斯谱它上是一个线性函数。

通过这种方式，仍然可以通过堆叠多个这样的层来表示的卷积滤波器函数类，但不限于由例如切比雪夫多项式给出的显式参数化。直觉上，这样的模型可以缓解具有非常宽的节点度分布的图的局部邻域结构的过度拟合问题，例如社交网络、引文网络、知识图和许多其他现实世界的图数据集。此外，对于固定的计算预算，这种逐层线性公式允许构建更深的模型，这种做法可以提高许多领域的建模能力。

在GCN的线性公式中，我们进一步近似 $\lambda_{max} \approx 2$ ，可以预期，神经网络参数将在训练期间适应这种规模的变化。在这些近似条件下，之前的式子简化为：

$\begin{align} g_{\theta} \star x & \approx \sum_{k=0} ^{K=1} \theta'_k T_k(\tilde{L})x \\ &\approx \theta_0' x + \theta_1' (L-I_N)\\ &= \theta_0' x - \theta_1' D^{-\frac{1}{2}} A D^{\frac{1}{2}}x \\ \end{align}$

滤波器参数 $\theta_0' ，\theta_1'$ 可在整个图上共享，这种形式的滤波器的连续应用可有效地卷积节点的第k阶邻域，即神经网络模型中连续滤波操作或卷积层数。

在实践中，可以进一步限制参数的数量以解决过拟合问题并最小化每层的操作（例如矩阵乘法）的数量，取 $\theta = \theta_0' = -\theta_1'$ ：
$g_{\theta} \star x \approx \theta (I_N + D^{-\frac{1}{2}} AD^{\frac{1}{2}})x$

$(I_N + D^{-\frac{1}{2}} AD^{\frac{1}{2}})$ 的特征值范围在[0,2]。在深层神经网络模型中重复使用该算子会导致数值不稳定性和爆炸/消失梯度。为了缓解这个问题，我们引入以下重整化技巧： $\tilde{A} = A + I_N$ ， $\tilde{D}_{ii}=\sum_j \tilde{A}_{ij}$ ,
$I_N + D ^ {-\frac{1}{2}} AD^{\frac{1}{2}} = \tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{\frac{1}{2}}$

我们可以把这个定义推广到一个N×C维的信号和F个滤波器或特征映射，输出维度是N×F：
$Z_{,:j} = \sum_{c=1}^C \theta_{j,c} \tilde{D} ^{-\frac{1}{2}} \tilde{A} \tilde{D}^{\frac{1}{2}} X_{:,c},j=1, \cdots,F$
写成矩阵形式如下，其中 $\Theta_{c,j} = \theta_{j,c}$ ，表示应用于第j个输出通道和第c个输入的参数：
$Z =\tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{\frac{1}{2}}X \Theta$

3. 半监督节点分类

在引入了一个简单而灵活的模型 $f(X，A)$ 之后，我们可以回到半监督节点分类问题。如简介中所述，我们可以通过在数据X和底层图结构的邻接矩阵X上调节我们的模型 $f(X，A)$ ，来放宽基于图的半监督学习中通常作出的某些假设。我们期望这种设置在邻接矩阵包含数据 X 中不存在的信息的场景中特别强大，例如引文网络中文档之间的引文链接或知识图中的关系。整体模型，半监督学习的多层GCN，如图所示：

图卷积网络

3.1 一个简单的例子

考虑一个两层 GCN，能在具有对称邻接矩阵 A的图上进行半监督节点分类的。前向模型采用简单的形式：
$Z= f(X, A) = softmax(\hat{A} ReLU(\hat{A}XW ^{(0)}) W^{(1)})$
对于半监督多类分类，评估所有标记样本的交叉熵误差.

3.2 代码实现

PyTorch Geometric 是一个基于PyTorch的用于处理不规则数据（比如图）的库，集成了GCN等等方法和常用数据集。

import torch
import torch.nn.functional as F
from torch_geometric.nn import GCNConv

class GCN(torch.nn.Module):
    def __init__(self, num_node_features, num_classes):
        super(GCN, self).__init__()
        self.conv1 = GCNConv(num_node_features, 16)
        self.conv2 = GCNConv(16, num_classes)

    def forward(self, data):
        x, edge_index = data.x, data.edge_index

        x = self.conv1(x, edge_index)
        x = F.relu(x)
        x = F.dropout(x, training=self.training)
        x = self.conv2(x, edge_index)
        return x

模型调用方法和pytorch一样，很方便上手。

参考：
Semi -Supervosed Classification With Graph Convolutional Networks
GRAPH CONVOLUTIONAL NETWORKS
跳出公式，看清全局，图神经网络（GCN）原理详解
图深度学习-马耀，汤继良
Pytorch geometric