第二代图卷积网络：应用快速局部谱卷积的图卷积网络

2023-12-10 19:03:26

论文标题：Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering
论文链接：https://arxiv.org/abs/1606.09375
论文来源：NeurIPS 2016

之前的文章：
①傅里叶级数与傅里叶变换
②图神经网络中的谱图理论基础
③第一代图卷积网络：图的频域网络与深度局部连接网络

一、概述

在将CNN泛化到图数据上的一个主要的瓶颈在于局部图卷积核的定义。本文在第一代图卷积神经网络上进行改进，定义了第二代图卷积神经网络，主要的贡献如下：
①谱图理论表达式：一种基于图信号处理（Graph Signal Processing，GSP）中已建立的工具的图上卷积神经网络的谱图理论公式。
②严格局部化的卷积核：本文提出的卷积核在中心节点的以 K K K为半径的最短路径内是严格局部化的。
③低计算复杂度：本文提出的卷积核的复杂度是和卷积核的尺寸 K K K以及边的数量 ∣ ε ∣ |\varepsilon | ∣ε∣成线性关系的，另外由于大多数图稀疏的，我们可以估计地认为 ∣ ε ∣ ≪ n 2 |\varepsilon |\ll n^{2} ∣ε∣≪n2并且 ∣ ε ∣ = k n |\varepsilon |=kn ∣ε∣=kn，也就是每个节点只和 k k k个近邻有边，这样复杂度就和节点数量 n n n成线性关系。另外本方法避免了使用傅里叶基底，因此不再需要进行昂贵的特征值分解以及存储傅里叶基底（使用一个 n 2 n^2 n2大小的矩阵）。除了数据，本方法只需要存储拉普拉斯矩阵这个包含 ∣ ε ∣ |\varepsilon | ∣ε∣个非零值的稀疏矩阵。
④高效池化：本文提出了一种图上的高效池化策略。
⑤实验结果：通过实验证明了方法的有效性，并与其他方法进行了对比。

二、方法

将CNN泛化到图上需要3个基本步骤：
①设计图上的局部卷积核；
②图的粗化（coarsening）；
③图的池化（pooling）。

学习快速局部谱卷积核

定义图卷积核的方法分空域（spatial）和频域（spectral）两种。空域的方法可以通过定义有限大小的卷积核来确保卷积核的局部性。卷积定理将卷积定义为在傅里叶基底（表示为拉普拉斯矩阵的特征向量）中对角化的线性算子，频域方法应用这一定理，然而频域卷积核存在两个限制：
①频域卷积核并非天然局部化；
②由于需要与图傅里叶基底相乘，会产生 O ( n 2 ) O(n^2) O(n2)的复杂度，转换成本很高。在本文中。

上述两个限制可以通过特殊的卷积核参数化选择来克服，这也是本文的主要内容之一。

图信号的谱卷积核

图信号的卷积操作无法在空域完成，不过通过卷积定理可以定义频域的卷积操作，假设有图记作 G G G，并且两个图信号 x x x和 y y y的卷积操作记作 ∗ G *_{G} ∗G，即：

x ∗ G y = U ( ( U T x ) ⊙ ( U T y ) ) x\, *_{G}\, y=U((U^{T}x)\odot (U^{T}y)) x∗Gy=U((UTx)⊙(UTy))

这里的 U U U指图的拉普拉斯矩阵的特征向量矩阵， U U U的每一列都是一个特征向量， ⊙ \odot ⊙代指哈达玛积。同样的，一个图信号 x x x被 g θ g_{\theta } gθ所卷积后得到的结果 y y y可以表示为：

y = g θ ( L ) x = g θ ( U Λ U T ) x = U g θ ( Λ ) U T x y=g_{\theta }(L)x=g_{\theta }(U\Lambda U^{T})x=Ug_{\theta }(\Lambda )U^{T}x y=gθ(L)x=gθ(UΛUT)x=Ugθ(Λ)UTx

这里的 Λ \Lambda Λ是特征值的对角矩阵。一个非参数化（non-parametric）的卷积核，也就是说它的参数全部都是*参数，被定义为：

g θ ( Λ ) = d i a g ( θ ) g_{\theta }(\Lambda )=diag(\theta ) gθ(Λ)=diag(θ)

这里 θ ∈ R n \theta \in \mathbb{R}^{n} θ∈Rn，是一个傅里叶系数向量，其实可以理解为卷积核与 U U U相乘后的结果，这个结果的每一维相当于这一维对应的特征向量的系数。

局部卷积核的多项式参数化

前述非参数化的卷积核有两个局限性：
①这样的卷积核在空间上不是局部化的；
②他们的学习复杂度是 O ( n ) O(n) O(n)。

这些局限性可以通过采用多项式卷积核来解决：

g θ ( Λ ) = ∑ k = 0 K − 1 θ k Λ k g_{\theta }(\Lambda )=\sum_{k=0}^{K-1}\theta _{k}\Lambda ^{k} gθ(Λ)=k=0∑K−1θkΛk

这里的 θ ∈ R K \theta \in \mathbb{R}^{K} θ∈RK，是多项式的系数向量，是要学习的参数。此时，图信号 x x x被 g θ g_{\theta } gθ所卷积后得到的结果 y y y为：

y = U ( ∑ k = 0 K − 1 θ k Λ k ) U T x = ( ∑ k = 0 K − 1 θ k U Λ k U T ) x = ∑ k = 0 K − 1 θ k L k x y=U\left (\sum_{k=0}^{K-1}\theta _{k}\Lambda ^{k}\right )U^{T}x\\ =\left (\sum_{k=0}^{K-1}\theta _{k}U\Lambda ^{k}U^{T}\right )x\\ =\sum_{k=0}^{K-1}\theta _{k}L^{k}x y=U(k=0∑K−1θkΛk)UTx=(k=0∑K−1θkUΛkUT)x=k=0∑K−1θkLkx

有文献可以证明，当 d G ( i , j ) > K d_{G}(i,j)>K dG(i,j)>K时有 ( L K ) i , j = 0 (L^{K})_{i,j}=0 (LK)i,j=0， d G d_{G} dG代表最短路径距离，也就是图中连接两个顶点的最小的边的数量。也就是说这样的卷积核是严格K-localized的。另外，需要学习的参数复杂度为 O ( K ) O(K) O(K)，与CNN相同。

总结来说，这样设计的卷积核有以下特点：
①卷积核只有 K K K个参数，一般 K ≪ n K\ll n K≪n，参数复杂度大大降低了；
②不需要进行拉普拉斯矩阵的特征分解了，直接用拉普拉斯矩阵 L L L进行变换，然而由于要计算 L k L^k Lk，计算复杂度还是 O ( n 3 ) O(n^3) O(n3)；
③卷积核具有很好的空间局部性，具体来说， K K K就是卷积核的感受野，也就是说每次卷积会将中心顶点K-hop neighbor上的feature进行加权求和，权系数就是 θ k \theta _{k} θk。

应用递归多项式的快速卷积

非参数化的卷积核的复杂度较高，并且上述多项式卷积核的计算复杂度仍然是比较高的，本小节介绍的卷积核应用切比雪夫多项式，能够实现 O ( K ∣ ε ∣ ) O(K|\varepsilon |) O(K∣ε∣)的复杂度。设计的思想是将 g θ ( L ) g_{\theta }(L) gθ(L)参数化为一个可由 L L L递归计算的多项式函数，这样的多项式可以采用切比雪夫多项式，如下：

T 0 ( x ) = 1 T 1 ( x ) = x T k ( x ) = 2 x T k − 1 ( x ) − T k − 2 ( x ) T_{0}(x)=1\\ T_{1}(x)=x\\ T_{k}(x)=2xT_{k-1}(x)-T_{k-2}(x) T0(x)=1T1(x)=xTk(x)=2xTk−1(x)−Tk−2(x)

这里需要 x x x在 [ − 1 , 1 ] [-1,1] [−1,1]之间，不熟悉切比雪夫多项式的读者可以自行百度。利用切比雪夫多项式，卷积核可以设计为：

g θ ( Λ ) = ∑ k = 0 K − 1 θ k T k ( Λ ~ ) g_{\theta }(\Lambda )=\sum_{k=0}^{K-1}\theta _{k}T_{k}(\widetilde{\Lambda }) gθ(Λ)=k=0∑K−1θkTk(Λ )

这里的 θ \theta θ是切比雪夫系数向量，也就是需要学习的参数。 T k ( Λ ~ ) ∈ R n × n T_{k}(\widetilde{\Lambda })\in \mathbb{R}^{n\times n} Tk(Λ )∈Rn×n是 k k k阶的切比雪夫多项式， Λ ~ = 2 Λ / λ m a x − I n \widetilde{\Lambda }=2\Lambda /\lambda _{max}-I_{n} Λ =2Λ/λmax−In，这样可以将特征值标准化到 [ − 1 , 1 ] [-1,1] [−1,1]之间。如此卷积操作就是下面这样的过程：

y = g θ ( L ) x = ∑ k = 0 K − 1 θ k T k ( L ~ ) x y=g_{\theta }(L)x=\sum_{k=0}^{K-1}\theta _{k}T_{k}(\widetilde{L})x y=gθ(L)x=k=0∑K−1θkTk(L )x

上式的推导过程很简单就不赘述了，这里的 L ~ ∈ R n × n \widetilde{L}\in \mathbb{R}^{n\times n} L ∈Rn×n也就是标准化以后的 L L L，即 L ~ = 2 L / λ m a x − I n \widetilde{L}=2L/\lambda _{max}-I_{n} L =2L/λmax−In。

将 x ‾ k \overline{x}_{k} xk记作 x ‾ k = T k ( L ~ ) x ∈ R k \overline{x}_{k}=T_{k}(\widetilde{L})x\in \mathbb{R}^{k} xk=Tk(L )x∈Rk，同样地也可以利用递归关系去计算 x ‾ k = 2 L ~ x ‾ k − 1 − x ‾ k − 2 \overline{x}_{k}=2\widetilde{L}\overline{x}_{k-1}-\overline{x}_{k-2} xk=2L xk−1−xk−2，此时 x ‾ 0 = x , x ‾ 1 = L ~ x \overline{x}_{0}=x,\overline{x}_{1}=\widetilde{L}x x0=x,x1=L x，此时卷积的过程又可以表示为：

y = g θ ( L ) x = [ x ‾ 0 , ⋯ , x ‾ K − 1 ] θ y=g_{\theta }(L)x=[\overline{x}_{0},\cdots ,\overline{x}_{K-1}]\theta y=gθ(L)x=[x0,⋯,xK−1]θ

这样设计的卷积过程的复杂度为 O ( K ∣ ε ∣ ) O(K|\varepsilon |) O(K∣ε∣)。对比上一小节的多项式卷积核，这里利用切比雪夫多项式设计的卷积核不再需要计算 L k L^k Lk，而只是利用仅包含加减操作的递归关系来计算 T k ( L ~ ) T_{k}(\widetilde{L}) Tk(L )，这样大大减少了计算的复杂度。

卷积核的学习

在一个卷积层中，一个样本 s s s的第 j j j个feature map的输出为：

y s , j = ∑ i = 1 F i n g θ i , j ( L ) x s , i ∈ R n y_{s,j}=\sum_{i=1}^{F_{in}}g_{\theta _{i,j}}(L)x_{s,i}\in \mathbb{R}^{n} ys,j=i=1∑Fingθi,j(L)xs,i∈Rn

x s , i x_{s,i} xs,i是输入的feature map，总计有 F i n × F o u t F_{in}\times F_{out} Fin×Fout个向量 θ i , j \theta _{i,j} θi,j，这些是需要学习的参数向量。

另外在训练时需要计算两个梯度：

∂ E ∂ θ i , j = ∑ s = 1 S [ x ‾ s , i , 0 , ⋯ , x ‾ s , i , K − 1 ] T ∂ E ∂ y s , j ∂ E ∂ x s , i = ∑ j = 1 F o u t g θ i , j ( L ) ∂ E ∂ y s , j \frac{\partial E}{\partial \theta _{i,j}}=\sum_{s=1}^{S}[\overline{x}_{s,i,0},\cdots, \overline{x}_{s,i,K-1}]^{T}\frac{\partial E}{\partial y_{s,j}}\\ \frac{\partial E}{\partial x_{s,i}}=\sum_{j=1}^{F_{out}}g_{\theta _{i,j}}(L)\frac{\partial E}{\partial y_{s,j}} ∂θi,j∂E=s=1∑S[xs,i,0,⋯,xs,i,K−1]T∂ys,j∂E∂xs,i∂E=j=1∑Foutgθi,j(L)∂ys,j∂E

E E E是损失函数，由于采用多项式卷积核，不同阶直接是累加关系，因此无论是计算 E E E对 θ \theta θ还是 x x x的梯度，都只需要先计算 E E E对 y y y的梯度，再利用累加关系很方便地就能得到最终结果，因此应用反向传播算法学习参数是可行的，在并行运算时也是高效的。还有一点就是KaTeX parse error: Undefined control sequence: \ at position 29: …_{s,i,0},\cdots\̲ ̲\overline{x}_{s…只需要计算一次。

图的粗化

池化操作需要将相似的节点聚类到一起，对于多层网络来说做到这一点相当于对需要保持局部几何结构的图进行多尺度聚类（multi-scale clustering）。图的聚类方法存在多种，比如常见的谱聚类方法（参考链接：谱聚类|机器学习推导系列（二十））。在本文的方法中没有采用谱聚类这种方法，而是选择了一种近似能够将图的规模除以2的聚类方法，这样的方法可以精确控制粗化和池化的size。本文采用的图粗化方法为Graclus多尺度聚类算法。

Graclus方法采用一种贪婪的方法来计算给定图的连续的粗化的版本，并且能够最小化多种谱聚类的目标，在这里选择的目标为normalized cut。具体的方法是在每层进行粗化时，选择一个未标记的节点 i i i，然后选择一个能够最小化 W i j ( 1 / d i + 1 / d j ) W_{ij}(1/d_{i}+1/d_{j}) Wij(1/di+1/dj)的未标记的邻居节点，然后将这两个节点标记，这两个匹配的节点在池化时被合并，合并节点的信号是这两个节点的信号加和。上述匹配的过程一直进行下去知道所有节点被遍历。这种方法是非常快速的，并且能够将图的规模近似除以2，之所以近似是因为可能有一些未匹配的节点（文中称为singleton节点）。

图信号的快速池化

池化操作被执行多次，所以必须是高效的。输入的图和粗化图的节点的排列方法是无意义的，因此，一个直接的池化操作的方法是需要一张表来保存匹配的节点，然而这种方法是内存低效的，并且缓慢，也不能并行处理。本文采用的方法可以使得池化操作像1D池化那样高效。

本文采用的方法分两个步骤：
①创建一个平衡二叉树；
②重排列所有节点。

在进行图的粗化以后，粗化图的每个节点要么有两个子节点（被匹配到的节点），要么只有一个节点（singleton节点）。从最粗到最细的图，将会添加fake节点（不与图连接在一起）到每一层来与singleton节点进行匹配。这样的结构是一个平衡二叉树，主要包含3种节点：
①regular节点（或者singleton节点），拥有两个regular子节点（如下图 level 1节点0）；
②regular节点（或者singleton节点），拥有一个regular节点和一个singleton节点座位子节点的节点（如下图 level 2节点0）；
③fake节点，总是拥有两个fake子节点（如下图 level 1节点1）。

fake节点的值初始化通常选择一个中性的值，比如当使用max pooling和ReLU激活函数时初始化为0。这些fake节点不与图的节点连接，因此卷积操作不会影响到它们。虽然这些节点会增加数据的维度，这样会增加计算的花费，但是在实践中证明Graclus方法所剩下的singleton节点是比较少的。在最粗化的图中任意排列节点，然后传播回最细的图中，这是由于粗化图中第 k k k的节点的子节点是上一层图中的 2 k 2k 2k和 2 k + 1 2k+1 2k+1节点，这样就可以在最细的图中有一个规范的排列顺序，这里规范是指相邻节点在较粗的层次上分层合并。这种pooling方法类似1D pooling。这种规范的排列能够让pooling操作非常的高效且可以并行化，并且内存访问是local的。下图是这种方法的一个例子：