图卷积神经网络

2024-05-14

现在给定一个图 $G=(V, E)$ 其中 $n = |V|$ 为顶点数， $E$ 为边集。给定其中每个点的特征，每个特征都是一个 $C$ 维的向量，以及它们其中某些点对应的标签 $y$ ，现在我们需要预测剩下的点的标签。

例如 Cora 数据集，每个点表示一篇论文，两个点间如果有一条无向边，那么表示这两篇论文之间存在引用关系。对于每个点给定一个向量，这个向量的每一维表示某个单词有没有出现过，某些点的类别，需要去预测剩下的点的类别。

谱域图卷积神经网络

在 CNN 里面，我们通过定义了一个卷积核，然后借助互相关运算，来在保留位置关系的同时提取图像的特征。我们希望在图上做类似的操作，但是图数据不像图像那么规整，我们希望通过一些方式对它进行卷积，同时能综合图的结构的信息。考虑我们对单点上的卷积操作很好做，那有没有什么方法能让我们在单点上做卷积，但是它能综合图上的信息？

考虑我们在做离散傅里叶变换（DFT）将两个多项式相乘 $O(n^2)$ 优化成 $O(n\log n)$ 的乘法的时候我们做了什么？

首先对两个多项式进行 DFT 变换，得到 $\tilde f$ 和 $\tilde g$ ，从时域变换到频域。
然后将其对位相乘 $\tilde h = \tilde f \odot \tilde g$
接着对 $\tilde h$ 做离散傅里叶逆变换，从频域变换回时域得到 $h$ 。

那么其实可以理解为在频域上和另一个频域中的向量对位相乘（Hadamard积），相当于在原来的时域做了一次卷积。我们希望在图上寻找类似的 “频域”。幸运的是恰好有这样的东西。

Laplace 矩阵和谱域

设 $A$ 和 $D = \text{diag}(d_1, \cdots, d_n)$ 分别为 $G$ 的邻接矩阵和度数矩阵，定义 Laplace 矩阵为 $L = D - A$ 。Laplace 矩阵有一些美妙的性质：

实对称半正定矩阵，特征向量为实向量
$L$ 可以正交对角化： $L = U\Lambda U^T$ ，其中 $U$ 为正交矩阵， $U$ 的列向量为 $L$ 的特征向量， $\Lambda = \text{diag}(\lambda_1, \cdots, \lambda_n)$ 。

假设点 $i$ 上有一个值 $x_i$ ，那么整个图的信息是一个向量 $x$ 。我们发现 $x^T L x = \frac{1}{2} \sum_i \sum_j A_{ij} (x_i - x_j)^2$ 能够一定程度上反应 $x$ 在整个图上的平滑程度。

将多项式从时域变为频域，实际上是将多项式从以 $\{1, t, \cdots, t^{n - 1}\}$ 为基变为以 $\{1, e^{2\pi t i/n}, \cdots, e^{2(n-1)\pi t i/n}\}$ 为基。整个图上的信号 $x$ 它相当于是以 $\{e_1, \cdots, e_n\}$ 为基的坐标。我们现在求它在 $U$ 为基下的坐标 $\hat x$ ，那么有 $U \hat x = Ix$ ，那么 $\hat x = U^T x$ 。我们考虑在以 $U$ 为基下 $x^TLx = x^TU\Lambda U^Tx = \hat x^T \Lambda \hat x = \sum_{i} \hat x_i^2 \lambda_i$ 。

特别地，当 $x$ 取为特征向量 $u_i$ 的时候，那么有 $\hat x_i = e_i$ ，此时 $x^TL x$ 的值即为 $\lambda_i$ 。也就是说当 $x$ 为 $L$ 的特征向量的时候，其对应的特征值越高，那么说明它在图上表示的信息就越不平滑，频率就越高。我们可以将图上的一条信息 $x$ 用 $U$ 的线性组合（即特征向量的线性组合 $U\hat x$ ）进行表示，此时的坐标 $\hat x$ 就相当于将它转化为“频域”。

（这里只是感性理解，其严格数学上的原因是因为傅里叶变换的基函数是 Laplace 算子的本征函数，Laplace 矩阵作为的线性变换是图上的 Laplace 算子，图上的傅里叶变换的基函数对应 Laplace 矩阵的特征向量）

傅里叶变换

在实际使用的时候，我们需要保证在后续的计算过程中的数值稳定性，所以我们需要对 Laplace 矩阵进行归一化，常用的有两种归一化的方法：

对称归一化： $L^{sym} = D^{-1/2}LD^{-1/2} = I - D^{-1/2}AD^{-1/2}$
随机游走归一化： $L^{rw} = D^{-1}L = I - D^{-1}A$

对于 $L^{sym}$ ，可以证明其特征值介于 $[0, 2]$ 之间。

SCNN

我们希望对整个图进行卷积， $x \ast \theta$ ，其中 $\theta$ 是某个卷积核，那么相当于在谱域做了一次 Hadamard积，我们将其变换到谱域（相当于信号处理中的频域），然后进行点积，然后再转换回空域（相当于信号处理中的时域）。

x\ast \theta = U((U^T x)\odot (U^T \theta))

我们在谱域做乘积，因此不关心 $\theta$ 在空域的结果，所以我们直接用 $\theta$ 来替换 $U^T\theta$ 来作为我们一个图卷积层 $F$ 的参数。那么有

F(x) = U(\theta \odot (U^T x))

这里有一个问题，我们真实的信息表示每个点是一个 $C$ 维的向量，即输入是 $X \in \R^{n\times C}$ 。这里稍微做一些变形，我们仍然将其转换到谱域 $U^TX$ ，此时我们希望能对每个频率此时的信息做一些信息的抽取，得到一些维度为 $H$ 的深一层的信息，因此我们在进行完 $U^T x$ 对第 $i$ 个频率维度乘上一个矩阵 $\Theta_i \in R^{C\times H}$ 。接着我们将其变换回时域，得到提取过一次信息的特征表示 $Y\in \R^{n\times H}$ 。

这里乘 $\Theta_i $ 的实现的话相当于是一个 (n, 1, C) 形状的张量和 (n, C, H) 形状的张量做批量矩阵乘操作，可以利用 torch.bmm 来实现。

这个方法它存在一些比较严重的问题：

它的所有卷积操作都是在全局上更新的，我们很难显示在局部上去汇集信息。
需要对 $L$ 进行特征值分解，这样至少需要 $O(n^3)$ 的时间复杂度，在一些特别大的图上非常难以接受。
它的参数个数为 $n$ ，在不同大小的图上也没有可扩展性

ChebyNet

我们来解决 SCNN 中两个问题。我们考虑将 $L^k$ 进行线性组合：

\begin{aligned} \sum_{i} \alpha_iL^i = \alpha_i\sum_i U\Lambda^i U^T = U(\sum_i \alpha_i \Lambda^i)U^T \end{aligned}

其实我们将 $L^k$ 线性组合，其实就相当于是对 $\Lambda^i$ 进行线性组合。我们考虑用这样一个近似的结果 $\hat \theta$ 来代替上面的 $\theta$ ，这样我们可以用 $f(L) x = U \text{diag} (\hat\theta) U^T x$ 来表示这个图卷积的过程。通过计算 $f(L)$ 我们就可以避免去对 $L$ 进行特征值分解。

这里注意如果要使得 $\Lambda^i$ 数值稳定，那么我们需要对 $L$ 进行归一化 $L \leftarrow \frac{2L}{\lambda_{max}}-I$ ，使得 $L$ 的特征值在 $[-1, 1]$ 内。同时当 $i$ 增大的时候 $\lambda^i$ 也会保留住大的那些特征值，而且这高频的信息容易带来过拟合。因此我们设置一个超参数 $K$ ，我们计算 $\sum_{i=0}^K \alpha_i L^i$ ，其中 $\{\alpha_i\}$ 是我们的参数

但是这里同样存在一些问题，比如 $L^k$ 会导致一些较小的特征值在 $k$ 增大的时候会变得非常地小，甚至变为 0，这这可能会带来一些数值上的问题。因此我们考虑利用在多项式一致逼近上性质更好的 Chebyshev 多项式，其定义如下：

\begin{aligned} & T_0(x) = 1, T_1(x) = x \\ & T_n(x) = 2xT_{n-1}(x) - T_{n-2}(x) & (n\geqslant 2) \end{aligned}

Chebyshev 多项式在 $[-1, 1]$ 有一些不错的性质：

值域为 $[-1, 1]$
$T_n$ 在 $[-1, 1]$ 上有 $n + 1$ 个极值点
$T_n$ 的零点分割 $T_{n + 1}$ 的零点（即 $T_{n + 1}$ 的两个零点之间，必然有 $T_n$ 的零点）

因此可以感性理解一下 Chebyshev 多项式相比 $x^i$ 用来拟合会有更好的效果。

显然以 $\{I, L, L^2, \cdots, L^K\}$ 的线性组合到 $\{T_0, T_1, \cdots, T_K\}$ 的线性组合是存在一一映射的。我们计算

\sum_{i=0}^K \alpha_i T_i(L)x

来替代原先的式子。这里由于 $T$ 是递归定义的，于是我们有：

T_i(L)x = 2L\left(T_{i-1}(L)x\right) - (T_{i-2}(L) x)

所以对于 $T_i (L) x$ 我们也可以通过递推的方式来计算，这里只用通过稀疏矩阵乘向量的方式来计算即可。

ChebyNet 相比 SCNN 有一些明显的好处：

参数数量降低了，同时对不同大小的图也有了扩展性
省去了其中时间开销最大的矩阵特征值分解的过程
能够显示地获取局部的信息：乘 $L$ 相当于每个点做了一次邻域的微分，因此乘上 $L^K$ 相当于指定感受域的大小为 $K$ 。

当输入维度为 $C$ 的时候，我们考虑计算输出第 $i$ 个维度上的答案，那么每次我们希望做的事是在进行 $U^TX$ 去计算 $U^TX$ 的第 $j$ 个特征维度对第 $i$ 个特征维度贡献了多少。由于线性性，我们可以把这个过程放在外面来枚举。即我们枚举 $j, i$ ，它享有参数 $\alpha = \Alpha_{i, j}$ ，然后像上面那样来计算即可。

为了提高计算效率，这里我们先去计算 $T_i(L)X$ ，这样会得到一个张量 $Y \in \R^{K\times n\times C}$ ，我们去把它和 $\Alpha \in \R^{K\times C\times H}$ 做批量矩阵乘操作。

GCN

假设我们在 ChebyNet 中只取一阶 Chebyshev 多项式，那么有

f(x) = (\alpha_0 I +\alpha_1 L)x

我们再作进一步简化，要求 $\alpha_0 = -\alpha_1 = \theta$ ，这样我们只有一个可学习的参数 $\theta$ 。注意这里的 $L$ 是上面通过 $\frac{2L}{\lambda_{max}} - I$ 进行归一化后的矩阵 $\tilde L$ （取 $\lambda_{max}=2$ ），此时