第一代图卷积网络：图的频域网络与深度局部连接网络

作者: 酷酷的群 | 来源:发表于2021-05-15 15:51 被阅读0次

论文标题：Spectral Networks and Locally Connected Networks on Graphs
论文链接：https://arxiv.org/abs/1312.6203
论文来源：NeurIPS 2014

本文需要的前置知识：傅里叶变换与谱图理论基础
链接：
①傅里叶级数与傅里叶变换
②图神经网络中的谱图理论基础

一、概述

CNN在机器学习领域内的一些问题上取得了比较成功的效果，这主要得益于它处理的底层数据通常有一个坐标网格结构（在1，2，3维度上），因此这些数据就存在平移不变性（ translational equivariance/invariance）。图像、语音、视频就属于这一类数据。由于网络不具备平移不变性（网络中的每个节点的邻居数量是不固定的），因此在网络上直接应用CNN是比较困难的。

对于常规的网格数据，CNN能够利用以下几个很好地结合在一起的结构来大大减少系统中的参数数量：
①平移结构（translation structure），使用滤波器在数据的网格结构上平移处理数据，从而实现参数共享，并没有使用线性映射；
②网格上的度量，使用紧凑支持滤波器（compactly supported filters），紧凑支持滤波器是指与输入数据大小无关的滤波器，它的大小可能远小于输入数据的大小；
③网格的多尺度二元聚类（multiscale dyadic clustering），是指CNN应用了跨步卷积（stride convolution）和池化（pooling）来进行下采样（subsampling）。

如果网格数据有 $n$ 个坐标，数据的维度为 $d$ （举例来说，图片的坐标数就是像素点数，维度就是图片的通道数，彩色图为 $3$ ，灰度图为 $1$ ），如果使用有 $m$ 的输出节点的全连接网络就需要 $n\times m$ 个参数，相当于 $O(n^2)$ 的参数复杂度。使用任意的滤波器（也就是①）而非全连接网路能将参数复杂度降低到 $O(n)$ ，使用网格上的度量结构（也就是②）来构建局部连接网络也可以。而如果两种一起使用能够将复杂度降低到 $O(k\cdot S)$ ，这里的 $k$ 代表数据feature map的数量， $S$ 代表卷积核的数量，此时复杂度与 $n$ 无关。最后使用网格的多尺度二元聚类（也就是③）可以进一步降低复杂度。

然而某些数据并不具备上述几何结构，比如表面张力或温度、从一个气象台网络中观测到的数据、来自社交网络或协同过滤的数据，这些数据都不能直接应用CNN。虽然CNN可以应用于多层，但是在特征维度上没有假设任何几何属性，导致一个4-D tensor只能沿其空间坐标进行卷积，即对于一个4-D的tensor而言，其有 $X,Y,Z,feature$ 四个维度，典型的CNN只能对 $X,Y,Z$ 三个维度（即空间维度）进行卷积操作（通过3D convolution 操作），而不能对 $feature$ 维度（特征维度）进行操作。

网络提供了低维网格数据的一种泛化的框架，也就是GCN是CNN在domain上的推广，推广的方式是通过推广卷积的概念。在本文中将会讨论将深度卷积应用于网络数据的方法。本文一共提供两种架构。第一种为空域架构（spatial construction），这种架构能够对网络数据应用上述②和③，应用它们可以构建网络数据的局部连接网络，参数复杂度为 $O(n)$ 而非 $O(n^2)$ 。另一种架构称为频域架构（spectral construction），能够在傅里叶域内应用卷积。频域架构对于每一个feature map最多需要 $O(n)$ 的参数复杂度，也可以构建参数数量与 $n$ 无关的架构。这两种架构都可以应用高效的前向传播并且能够应用在有多个坐标的数据的数据集上。

二、空域架构

网络数据将由一个加权图 $G=(\Omega ,W)$ 来表示， $\Omega$ 是一个离散的节点集合，大小为 $m$ ， $W$ 是一个对称半正定矩阵，也就是加权邻接矩阵。将CNN泛化到网络数据的最直接想法是应用多尺度的、层级的局部感受野。

通过 $W$ 定义局部性

在网络上可以轻松的定义局部性（locality）的概念。边的权重决定了节点的局部性，举例来说，可以设置一个阈值 $\delta$ 来决定一个节点的邻居节点集合：

$N_{\delta }(j)=\left \{i\in \Omega :W_{ij}>\delta \right \}$

我们可以将注意力限制在稀疏的滤波器上，这些滤波器通过节点的邻居节点集合来定义感受野，以此来构建局部连接网络，这样可以将参数量降低为 $O(S\cdot n)$ ，这里的 $S$ 代表平均邻居节点数量。

图的多尺度聚类

CNN通过池化和下采样来降低网格的大小，这一操作也就是网格的多尺度聚类（ multiscale clustering）：为每个cluster输入多个特征，输出一个特征。在图上被证明更为有效的聚类方法仍然有待研究，在本文中选择了一种比较朴素的聚类方法。如下图所示，下图中有两层聚类，灰色的点为数据中的无向图节点，然后进行聚类得到下一层带颜色的节点，然后再对这些带颜色的节点进行聚类，第一层为12个节点，第二层6个节点，第三层3个节点：

图上的聚类

深度局部连接网络

本文提出的空域架构也叫做深度局部连接网络（Deep Locally Connected Networks）。在这个架构中使用了网络的多尺度聚类，事实上这里的尺度可以认为是下采样的层数，在这里我们考虑 $K$ 个尺度，实际上也就是说这个架构由 $K$ 个卷积层，每个卷积层后面都有一个池化层（也就是进行一次聚类），因此这个架构中总共有 $K$ 层，每层包括一个个卷积层和一个池化层。

我们设置 $\Omega _{0}=\Omega$ ，也就是输入层的节点集合，可以认为是第0层，每一层的节点集合记作 $\Omega _{k}$ ，这里 $k=1,2,\cdots ,K$ ， $\Omega _{k}$ 可以认为是将 $\Omega _{k-1}$ 聚成 $d_k$ 个簇的一个划分，因此 $d_k$ 就表示第 $k$ 层的节点个数，有 $d_{k}=|\Omega _{k}|$ 。另外定义 $\Omega _{k-1}$ 的节点的邻居节点集合的表示：

$N_{k}=\left \{N_{k,i};i=1,2,\cdots d_{k-1}\right \}$

注意这里 $N_{k}$ 的下标虽然为 $k$ ，但它代表的是第 $k-1$ 的节点集合 $\Omega _{k-1}$ 的每个节点的邻域的表示，里面的每个 $N_{k,i}$ 都是一个集合。

有了上述定义现在我们可以定义网络的第 $k$ 层。假设输入信号是 $\Omega _{0}$ 上的实值信号，以 $f_k$ 来代表第 $k$ 层的卷积核的数量，也代表了第 $k$ 层feature map的数量和信号的维度（类比CNN，卷积核的数量等于feature map的数量，也就是卷积后的信号特征的维度）。每一层都会将 $\Omega _{k-1}$ 上的 $f_{k-1}$ 维的信号转换成 $\Omega _{k}$ 上的 $f_{k}$ 维的信号，这一过程会权衡空间分辨率和新创建的特征坐标，也就是说，虽然经过每一层的节点数量降低了，但是卷积核的数量会逐层增加以保证特征的维度会增加，也就是说每层有两个结果：
①空间分辨率降低（loses spatial resolution），即空间点数减少；
②滤波器数目增加（increases the number of filters），即每个点特征数 $d_k$ 增加。

第 $k$ 层的输入用 $x_{k}=(x_{k,i};i=1,2,\cdots ,f_{k-1})$ 来表示，这里的 $x_{k}$ 是一个 $d_{k-1}\times f_{k-1}$ 的矩阵， $x_{k,i}$ 可以认为是一个列向量， $x_{k,i}$ 也就相当于第 $i$ 个feature map的信号。那么第 $k$ 层的输出 $x_{k+1}$ 就被定义为：

$x_{k+1,j}=L_{k}h\left (\sum_{i=1}^{f_{k-1}}F_{k,i,j}x_{k,i}\right )\; \; \; (j=1,2,\cdots ,f_{k})$

这里的 $F_{k,i,j}$ 代表第 $k$ 层的第 $j$ 个卷积核对第 $k-1$ 层的第 $i$ 个feature map进行卷积的部分，注意由于图的节点的邻居分布情况不同，所以卷积核不像CNN那样是共享的。这里的 $F_{k,i,j}$ 是一个 $d_{k-1}\times d_{k-1}$ 的稀疏矩阵，矩阵的第 $m$ 行的非零值都只会存在于 $N_{k,m}$ 所指定的第 $m$ 个节点的邻居节点位置。 $h$ 代表非线性激活函数。 $L_k$ 代表对卷积的结果进行之前所述的池化操作来降低节点的数量， $L_k$ 相当于聚类的结果，是一个 $d_{k}\times d_{k-1}$ 的稀疏矩阵，每一行指示一个簇的分布，如果采用平均池化，那么 $L_k$ 的一个例子（ $d_{k}=3,d_{k-1}=6$ ）可以是：

$L_{k}=\begin{vmatrix} 1 & 0 & 0 & 0 & 0 & 0\\ 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 & 0\\ 0 & 0 & \frac{1}{3} & 0 & \frac{1}{3} & \frac{1}{3} \end{vmatrix}$

整个过程可以用下图来表示：

空域架构

另外通过以下过程构建第 $k$ 层的 $W_k$ 和 $N_k$ ：

$W_{0}=W\\ A_{k}(i,j)=\sum _{s\in \Omega _{k}(i)}\sum _{t\in \Omega _{k}(j)}W_{k-1}(s,t),\; (k\leq K)\\ W_{k}=rownormalize(A_{k}),\; (k\leq K)\\ N_{k}=supp(W_{k}),\; (k\leq K)$

这里 $A_{k}(i,j)$ 的计算过程是指：由于 $\Omega _{k}$ 中的节点来自 $\Omega _{k-1}$ 中的节点的聚类，所以 $i,j$ 之间的权重是 $i$ 和 $j$ 对应的聚类之前的 $\Omega _{k-1}$ 中节点之间所有权重的累加。 $\Omega _{k}$ 是对 $\Omega _{k-1}$ 的聚类，图聚类的方法是多种多样的，可以自行选取，这里的方法是采用 $W_{k}$ 的 $\epsilon$ - covering，使用核函数 $K$ 的 $\Omega$ 的 $\epsilon$ - covering是一个划分 $P=\left \{P_{1},P_{2},\cdots ,P_{n}\right \}$ ，满足：

$sup_{n}sup_{x,x^{'}\in P_{n}}K(x,x^{'})\geq \epsilon$

以 $S_k$ 代表平均节点数量，那么第 $k$ 层用来学习的参数量为：

$O(S_{k}\cdot |\Omega _{k}|\cdot f_{k}\cdot f_{k-1})=O(n)$

实践中通常有 $S_{k}\cdot |\Omega _{k}|\approx \alpha \cdot |\Omega _{k-1}|$ ， $\alpha$ 是下采样因子，满足 $\alpha \in(1,4)$ 。

评价

这种架构的优点在于不需要很强的前提假设，只需要图具备邻域结构即可，甚至不需要很好的embedding向量。但是缺点在于没办法进行参数共享，对于每一层的每一个节点都要有单独的参数进行卷积而不能像CNN那样使用同一个卷积核在数据网格上进行平移。

三、频域架构

图的拉普拉斯矩阵

在这里，以 $D$ 代表图的度矩阵， $W$ 代表图的加权邻接矩阵，常用的图的拉普拉斯矩阵有三种：
①Combinatorial Laplacian，也就是普通形式的拉普拉斯矩阵：

$L=D-W$

其中的元素为：

$L_{i,j}=\left\{\begin{matrix} d_{i},i=j \\ -w_{ij},i\neq j\; and\; v_{i}\; is\; adjacent\; to\; v_{j}\\ 0,otherwise \end{matrix}\right.$

②Symmetric normalized Laplacian，也就是对称归一化的拉普拉斯矩阵：

$L^{sys}=D^{-1/2}LD^{-1/2}=I-D^{-1/2}WD^{-1/2}$

其中的元素为：

$L_{i,j}^{sys}=\left\{\begin{matrix} 1,i=j\; and\; d_{i}\neq 0\\ -\frac{w_{ij}}{\sqrt{d_{i}d_{j}}},i\neq j\; and\; v_{i}\; is\; adjacent\; to\; v_{j}\\ 0,otherwise \end{matrix}\right.$

③Random walk normalized Laplacian，也就是随机游走归一化拉普拉斯矩阵：

$L^{rw}=D^{-1}L=I-D^{-1}W$

其中的元素为：

$L_{i,j}^{rw}=\left\{\begin{matrix} 1,i=j\; and\; d_{i}\neq 0 \\ -\frac{w_{ij}}{d_{i}},i\neq j\; and\; v_{i}\; is\; adjacent\; to\; v_{j}\\ 0,otherwise \end{matrix}\right.$

加权图的调和分析

为简便起见，本文应用的是第①种。对于一个固定的加权邻接矩阵 $W$ ，不同的节点信号列向量 $x\in \mathbb{R}^{m}$ （也就是说网络有 $m$ 个节点）有不同的平滑性（smoothness）度量 $||\nabla x||_{W}^{2}$ ，在节点 $i$ 处的平滑性度量为：

$||\nabla x||_{W}^{2}(i)=\sum _{j}w_{ij}[x(i)-x(j)]^{2}$

所有信号的平滑性度量为：

$||\nabla x||_{W}^{2}=\sum _{i}\sum _{j}w_{ij}[x(i)-x(j)]^{2}$

其实 $||\nabla x||_{W}^{2}$ 也就是 $x^{T}Lx$ ，关于拉普拉斯矩阵与信号平滑性的关系已经在本文开头给出的文章链接里介绍过了，这里不再赘述。

有了上面的公式我们可以得出最平滑的信号 $x$ 其实是一个归一化的全 $1$ 向量：

$v_{0}=\underset{x\in \mathbb{R}^{m}\; ||x||=1}{argmin}||\nabla x||_{W}^{2}=(1/\sqrt{m})1_{m}$

事实上 $\mathbb{R}^{m}$ 空间中最平滑的 $m$ 个相互正交的单位向量其实就是 $L$ 的特征向量：

$v_{i}=\underset{x\in \mathbb{R}^{m}\; ||x||=1\; x\perp \left \{v_{0},\cdots ,v_{i-1}\right \}}{argmin}||\nabla x||_{W}^{2}$

每个特征向量 $v_{i}$ 的平滑性度量的值其实也就是特征值 $\lambda _{i}$ ，这一点只需要代入计算一下就可以得出，拉普拉斯矩阵的谱分解为 $L=V\Lambda V^{-1}=V\Lambda V^{T}$ ，这里的 $\Lambda$ 为特征值构成的对角矩阵， $V$ 为特征向量构成的正交矩阵， $V$ 的每一列都是一个特征向量，那么 $v_{i}^{T}Lv_{i}$ 计算一下就可以得到等于特征值 $\lambda _{i}$ ，因此最平滑的信号向量就是特征值最小的特征向量，拉普拉斯矩阵的特征值就代表了特征向量的平滑度。

上面提到的一组特征向量其实就是 $\mathbb{R}^{m}$ 空间的一组基，前面的文章里说过图傅里叶变换其实就是将信号向量投影到拉普拉斯矩阵的各个特征向量上：

$F(\lambda _{k})=\sum_{i=1}^{m}x(i)v_{k}(i)$

特征值的大小表示平滑程度，它对应传统傅里叶变换中的频率，频率高表示短时间内变动多，和这里的相邻节点变动大（变动越大越不平滑）能对应起来。因此图傅里叶变换就是在将一个图信号分解到不同平滑程度的图信号上，就像传统傅里叶变换将函数分解到不同频率的函数上一样。

一个任意信号向量 $x$ 分解到所有的特征向量上对应的每个系数用 $a_{i}$ （ $a_{i}=F(\lambda _{i})$ ，这些系数也就是图傅里叶变换后的系数）表示， $x$ 可以表示为 $\sum_{i=1}^{m}a_{i}v_{i}$ ，也就是 $Va$ ，那么 $x$ 的平滑性度量的值可以用这些系数和特征值表示：

$x^{T}Lx=(Va)^{T}LVa\\ =a^{T}V^{T}LVa\\ =a^{T}V^{T}V\Lambda V^{T}Va\\ =a^{T}I\Lambda Ia\\ =a^{T}\Lambda a\\ =\sum_{i=1}^{m}a_{i}^{2}\lambda _{i}$

图卷积

两个函数 $f$ 和 $g$ 进行卷积可以应用卷积定理，用公式表达卷积定理就是：

$F(f*g)=F(f)\cdot F(g)$

应用卷积定理可以在频域上进行图的卷积操作，具体的方法是将滤波器 $h$ 和图信号 $x$ 都通过图傅里叶变换转换到频域然后计算转换后的结果的乘积（哈达玛积，也就是向量对应元素相乘），然后将相乘的结果再通过图傅里叶逆变换转换回空域，整个过程如下：

$h*x=F^{-1}\left \{F\left \{h\right \}\cdot F\left \{x\right \}\right \}\\ =F^{-1}\left \{\hat{h}\cdot \hat{x}\right \}\\ =F^{-1}\left \{\hat{h}\cdot V^{T}x\right \}\\ =F^{-1}\left \{diag[\hat{h}_{1},\cdots ,\hat{h}_{m}]V^{T}x\right \}\\ =Vdiag[\hat{h}_{1},\cdots ,\hat{h}_{m}]V^{T}x$

这里将 $\hat{h}$ 组织成对角矩阵 $diag[\hat{h}_{1},\cdots ,\hat{h}_{m}]$ ， $\hat{h}_{1},\cdots ,\hat{h}_{m}$ 也就是神经网络要学习的参数。

频域架构

在这里我们仍然使用 $k$ 来代表网络的第 $k$ 层， $k=1,2,\cdots ,K$ ， $f_k$ 仍然代表卷积核的数量。这种架构的卷积的过程主要依照卷积定理，首先来描述卷积的过程，之后再描述如何进行下采样，因此现在假设第 $k$ 层和第 $k+1$ 层的节点数都是 $|\Omega |$ ，那么第 $k$ 层的输入 $x_{k}$ 就是一个 $|\Omega |\times f_{k-1}$ 的矩阵，输出 $x_{k+1}$ 就是一个 $|\Omega |\times f_{k}$ 的矩阵。第 $k$ 层的计算过程可以表示为：

$x_{k+1,j}=h\left (V\sum_{i=1}^{f_{k-1}}F_{k,i,j}V^{T}x_{k,i}\right )\; \; \; (j=1,2,\cdots ,f_{k})$

这里的 $x_{k,i}$ 仍然相当于第 $i$ 个feature map的信号。 $F_{k,i,j}$ 也就是第 $j$ 个卷积核中对第 $i$ 个feature map进行卷积的部分，每一个 $F_{k,i,j}$ 都是一个对角矩阵，其实就是前面的 $diag[\hat{h}_{1},\cdots ,\hat{h}_{m}]$ ，这里之所以有一个连加号是因为要将多个feature map的结果累加起来， $h$ 仍然表示非线性激活，另外这里的 $V$ 的每一列的特征向量是按照特征值的大小依次排列的（降序）。

通常只有拉普拉斯矩阵的前 $d$ 个特征向量是有意义的，因为后面的特征向量对应的特征值比较小，特征向量非常的平滑，因此在实际中可以取拉普拉斯矩阵的前 $d$ 列构成的矩阵 $V_d$ 代替 $V$ ，这个过程就相当于频域架构的下采样的过程，这里的 $d$ 就相当于空域架构中的 $d_k$ ，每一层可以取不同的值。按照目前这种架构所需的参数复杂度为 $f_{k-1}\cdot f_{k}\cdot d=O(|\Omega |)$ 。