前两篇介绍完图卷积网络的背景知识,现在正式引入 GCN!

卷积定义

在泛函分析中,卷积是通过两个函数ffgg 生成第三个函数的一种数学算子,表示函数ff 与经过翻转和平移的gg 的乘积函数所围成的曲边梯形的面积,公式如下所示:

(fg)(t)= def Rnf(τ)g(tτ)dτ(1)(f * g)(t) \stackrel{\text { def }}{=} \int_{\mathbb{R}^{n}} f(\tau) g(t-\tau) d \tau \quad\quad\quad (1)

下面给出两幅图来直观理解上述公式,参考 卷积解释


以上是连续函数的卷积运算,对于离散卷积公式定义如下:

(fg)[n]=m=f[m]g[nm]=m=f[nm]g[m](2)(f * g)[n]=\sum_{m=-\infty}^{\infty} f[m] g[n-m]=\sum_{m=-\infty}^{\infty} f[n-m] g[m] \quad\quad\quad (2)

卷积除了直接计算这种方法,还可以根据卷积定理来计算。

卷积定理:在适当条件下,两个信号的卷积的傅立叶变换等于它们傅立叶变换的点积。例如,一个域(如时域)的卷积等于另一个域(如频域)的点乘:

F{fg}=F{f}F{g}(3)\mathcal{F}\{f * g\}=\mathcal{F}\{f\} \cdot \mathcal{F}\{g\} \quad\quad\quad (3)

如果以F1\mathcal{F}^{-1} 表示傅里叶逆变换,那么卷积计算可以重新表示为:

fg=F1{F{f}F{g}}(4)f * g=\mathcal{F}^{-1}\{\mathcal{F}\{f\} \cdot \mathcal{F}\{g\}\} \quad\quad\quad (4)

PS:利用卷积定理可以简化卷积的运算量。对于一个长度为nn 的序列,按照卷积的定义来计算则需要做2n12n-1 组对位乘法,即时间复杂度为O(n2)O(n^2) ;而利用傅立叶变换后,只需要计算一组对位乘法,而且离散傅立叶变换有快速的算法(快速傅立叶变换),所以总的计算复杂度为O(nlogn)O(n\log n)

图卷积

谱图卷积的思想是:既然无法直接在空域对图进行卷积,那么将图信号映射到频域后再做卷积操作。

根据公式 (4)与文章 图卷积网络 GCN(Graph Convolution Network)(二)图上的傅里叶变换和逆变换 中图上的傅里叶变换公式,可得

(fh)G=F1[F{f}F{h}]=F1[UTfh^](5)\begin{aligned} (f * h)_{G} &=\mathcal{F}^{-1}[\mathcal{F}\{f\} \cdot \mathcal{F}\{h\}] \\ &=\mathcal{F}^{-1}\left[\mathbf{U}^{T} f \cdot \hat{h}\right] \end{aligned} \quad\quad\quad (5)

上式表示时域信号ffhh 的卷积等价于将信号转换到傅立叶域做点乘后再逆变换回来。其中,向量ff 与向量h^\hat{h} 的元素点积,等价于将h^\hat{h} 组织成对角矩阵的形式进行矩阵乘法,可得:

(fh)G=F1[UTfh^]=F1[diag[h^1,,h^n]UTf](6)\begin{aligned} (f * h)_{G} &=\mathcal{F}^{-1}\left[\mathbf{U}^{T} f \cdot \hat{h}\right] \\ &=\mathcal{F}^{-1}\left[\operatorname{diag}\left[\hat{h}_{1}, \ldots, \hat{h}_{n}\right] \mathbf{U}^{T} f\right] \end{aligned}\quad\quad\quad (6)

根据图上的逆变换计算公式,上式做成U\mathbf{U}可得:

(fh)G=Udiag[h^1,,h^n]UTf(7)(f * h)_{G}=\mathbf{U} \operatorname{diag}\left[\hat{h}_{1}, \ldots, \hat{h}_{n}\right] \mathbf{U}^{T} f\quad\quad\quad (7)

也可以写成写成矩阵形式为:

(fh)G=U((UTf)(UTh))(8)(f*h)_G=\mathbf{U} ((\mathbf{U} ^Tf)(\mathbf{U} ^Th)) \quad\quad\quad (8)

目前先不写成式 (8) 的形式,是因为在 GCN 中我们的卷积核是可训练并且参数共享的,所以在此我们可以直接令

diag[h^1,,h^n]=diag[θ1,,θn]=gθ(9)\operatorname{diag}\left[\hat{h}_{1}, \ldots, \hat{h}_{n}\right] =\operatorname{diag}\left[\theta_{1}, \ldots, \theta_{n}\right] = g_{\theta} \quad\quad\quad (9)

这就是深度学习中的可学习参数。

第一代图卷积

论文来源:《Spectral Networks and Deep Locally Connected Networks on Graphs》

第一代图卷积的计算方法就直接根据式(7)(9)推出

y=σ(UgθUTx)=σ(U[θ1θ2θN]UTx)(10)y=\sigma\left(\mathbf{U} g_{\theta} \mathbf{U}^{T} x\right)=\sigma\left(\mathbf{U}\left[\begin{array}{ccc} \theta_{1} & & \\ & \theta_{2} & \\ & & \\ & & \theta_{N} \end{array}\right] \mathbf{U}^{T} x\right) \quad\quad\quad (10)

虽然利用上式已经可以构造深度网络进行图卷积运算了,但该版本有不少缺点:

  1. 没有 local 信息。每次卷积都是所有顶点都参与运算,没有实现局部卷积和参数共享。
  2. 运算量大。每次卷积都要进行拉普拉斯矩阵分解和矩阵相乘,计算复杂度为O(N3)O(N^3)
  3. 参数量大。每个卷积核参数量为O(N)O(N)

第二代图卷积

文章来源:
《Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering》

针对第一代图卷积中存在的问题,学者基于切比雪夫多项式提出第二代 GCN:ChbeyNet

首先回顾下图傅里叶计算公式:

FT(λk)=g^k=i=1Ng(i)uk(i)(11)\mathcal{F}_{T}\left(\lambda_{k}\right)=\hat{g}_{k}=\sum_{i=1}^{N} g(i) u_{k}(i) \quad\quad\quad (11)

可知函数和特征值密切相关,令gθg_{\theta} 为拉普拉斯矩阵LL 的特征值函数gθ(Λ)g_{\theta}(\Lambda)

y=σ(UgθUTx)=σ(Ugθ(Λ)UTx)(12)y=\sigma\left(\mathbf{U} g_{\theta} \mathbf{U}^{T} x\right)=\sigma\left(\mathbf{U} g_{\theta}(\Lambda) \mathbf{U}^{T} x\right) \quad\quad\quad (12)

以拉普拉斯矩阵的特征值作为卷积核同样存在缺陷:

  • 不具备局部连接性;
  • 时间复杂度为O(n)O(n);

为了克服上述缺陷引入KK 阶多项式:

gθ(Λ)k=0K1θkΛk(13)g_{\theta}(\Lambda) \approx \sum_{k=0}^{K-1} \theta_{k} \Lambda^{k}\quad\quad\quad (13)

其中,参数θkRK\theta_k\in R^K 是多项式系数,因此滤波器具有了KK 阶局部性,复杂度也降低到O(K)O(K)

将式代入第一代图卷积式(10)中可得:

y=σ(Ugθ(Λ)UTx)=σ(Uk=0K1θkΛkUx)=σ(k=0K1θkLkx)(14)y=\sigma\left(\mathbf{U} g_{\theta}(\Lambda) \mathbf{U}^{T} x\right)=\sigma\left(\mathbf{U} \sum_{k=0}^{K-1} \theta_{k} \Lambda^{k} \mathbf{U} x\right)=\sigma\left(\sum_{k=0}^{K-1} \theta_{k} L^{k} x\right)\quad\quad\quad (14)

其中σ\sigma 是激活函数,公式(14)的计算时间复杂度为O(K×N2)O(K×N^2) ,因为对于静态图而言LL 是固定的,LkL^k 可以提前计算得到。如果使用稀疏矩阵乘法(pytorch 里有封装),时间复杂度是O(K×E)O(K×|E|) 其中E|E| 是稀疏矩阵中非零元的个数表示图中边的数量。 此时计算图卷积就不需要再乘上特征向量矩阵U\mathbf{U},而是直接使用拉普拉斯矩阵LLkk 次方,就避免了进行特征分解。

因为LkL^kKK 很大的时候并不稀疏(E|E| 接近N2N^2 ),所以文中提出了利用切比雪夫多项式展开(任何kk次多项式都可以通过切比雪夫多项式展开)来近似LkL^k ,切比雪夫多项式递归式为:

T0(x)=1T1(x)=xTk(x)=2xTk1(x)Tk2(x)(15)T_0(x)=1\\T_1(x)=x\\T_k(x)=2xT_{k-1}(x)-T_{k-2}(x) \quad\quad\quad (15)

因此根据上式可知:

gθ(Λ)k=0K1θkTk(Λ~)(16)g_{\theta}(\Lambda) \approx \sum_{k=0}^{K-1} \theta_{k} T_{k}(\widetilde{\Lambda})\quad\quad\quad (16)

其中,Λ~=2λmaxΛIN\tilde{\Lambda}=\frac{2}{\lambda_{\max }} \Lambda-I_{N};λmax\lambda_{\max }是指拉普拉斯矩阵LL的最大特征值。

PS:因为切比雪夫多项式的输入要在[1,1][-1, 1] 之间,由于拉普拉斯矩阵的半正定性,所以所有的特征值都是大于等于 0 的,将其除以最大特征值可以将特征压缩到[0,1][0,1] 区间内,现在需要将其压缩到[1,1][-1, 1],所以我们有:Λ~=2λmaxΛIN\tilde{\Lambda}=\frac{2}{\lambda_{\max }} \Lambda-I_{N}

我们将切比雪夫多项式引入到我们的卷积变换中:

gθxk=0K1θkTk(L~)x(17)g_{\theta} * x \approx \sum_{k=0}^{K-1} \theta_{k} T_{k}(\widetilde{L}) x \quad\quad\quad (17)

其中,L~=2λmaxLIN\tilde{L}=\frac{2}{\lambda_{\max }} L-I_{N} 。这个表达式为拉普拉斯多项式中的一个kk 阶近似函数,依赖于节点的kk 阶邻域(kk 步可达),时间复杂度与边呈线形相关。

总结第二代图卷积优点如下:

  • 运算量相比第一代的O(N3)O(N^3) 可以降到O(KE)O(K|E|)
  • 引入 K-hop 感受野,可以捕捉局部特征。

第三代图卷积

文章来源:《Semi-supervised Classification with Graph Convolutional Networks》

第二代图卷积解决了拉普拉斯矩阵特征分解的问题,但是在计算图卷积操作时矩阵乘法时间复杂度为O(N2)O(N^2),在此基础上优化 Kipf 等人提出了目前流行的 GCN。

GCN 通过式(17)进行多层卷积层进行叠加,而每层都会逐点进行非线性叠加。考虑到时间复杂度问题,令K=2K=2,也就是说得到了一个拉普拉斯算子的二阶近似函数。既可以对网络进行卷积操作计算量增加不大。通过叠加层数可以提升模型的非线性。

归一化的拉普拉斯矩阵的特征值区间为[0,2][0, 2],令λmax2,K=2{\lambda}_{max} \approx 2, K=2 可得:

gθxθ0x+θ1(LIN)x=θ0xθ1D12AD12x(18)g_{\theta} * x \approx \theta_{0} x+\theta_{1}\left(L-I_{N}\right) x=\theta_{0} x-\theta_{1} D^{-\frac{1}{2}} A D^{-\frac{1}{2}} x\quad\quad\quad (18)

其中,θ0,θ1\theta_0,\theta_1是切比雪夫系数且仅存的两个参数!

在 GCN 的训练过程中需要规范化参数避免过拟合,令θ=θ0=θ1\theta=\theta_{0}^{\prime}=-\theta_{1}^{\prime},由式可得:

gθxθ(IN+D12AD12)x(19)g_{\theta} * x \approx \theta\left(I_{N}+D^{-\frac{1}{2}} A D^{-\frac{1}{2}}\right) x\quad\quad\quad (19)

注意IN+D12AD12I_{N}+D^{-\frac{1}{2}} A D^{-\frac{1}{2}}的特征值范围在 [0, 2] 之间,所以如果在很深的网络中会引起梯度爆炸的问题,需要再次进行一次归一化(Renormalization trick):

IN+D12AD12D~12A~D~12,D~ii=jA~ijA~=A+IN(20)I_{N}+D^{-\frac{1}{2}} A D^{-\frac{1}{2}} \rightarrow \widetilde{D}^{-\frac{1}{2}} \widetilde{A} \widetilde{D}^{-\frac{1}{2}} , \widetilde{D}_{i i}=\sum_{j} \widetilde{A}_{i j} \widetilde{A}=A+I_{N}\quad\quad\quad (20)

把上式从标量推广到矩阵,对于输入顶点的向量XRN×CX \in R^{N \times C} ,其中NN 为节点数,CC 为顶点的特征向量维度,可得:

Z=D~12A~D~12XΘ(21)Z=\widetilde{D}^{-\frac{1}{2}} \widetilde{A} \widetilde{D}^{-\frac{1}{2}} X \Theta\quad\quad\quad (21)

其中,ΘRC×F\Theta \in R^{C \times F}是参数矩阵,ZRN×FZ \in R^{N \times F}是卷积后的顶点特征,时间复杂度为O(EFC)O(|E|FC)

根据上式一层卷积,多层图卷积计算公式公式为:

H(l+1)=σ(D~12A~D~12H(l)W(l))(22)H^{(l+1)}=\sigma\left(\widetilde{D}^{-\frac{1}{2}} \widetilde{A} \widetilde{D}^{-\frac{1}{2}} H^{(l)} W^{(l)}\right)\quad\quad\quad (22)

其中,A~=A+IN\widetilde{A}=A+I_{N}AA 为邻接矩阵,INI_N 为单位矩阵,所以A~\widetilde{A}为添加自连接的邻接矩阵;D~ii=jA~ij\widetilde{D}_{i i}=\sum_{j} \widetilde{A}_{i j}D~\widetilde{D}为顶点的度数矩阵;W(l)W^{(l)} 为神经网络第ll 层的权重矩阵;σ()\sigma(\cdot) 是激活函数;H(l)RN×DH^{(l)} \in R^{N \times D} 是第ll 层的激活矩阵,并且H(0)=XH^{(0)}=XXX 是由顶点的特征向量组成矩阵。

总结第三代图卷积:

  • 令 K=1,相当于只考虑 1-hop 邻点。通过堆叠层数来增加感受野。
  • 每层计算复杂度降低为O(E)O(|E|)

总结

CNN 中的卷积无法直接应用于网络图中,所以引出了谱图理论和图中的傅里叶变换,进而定义图卷积的计算方法,最后结合深度学习发展出来 GCN。至此图卷积 GCN 的理论推导三部曲完成,接下来就开启应用篇吧!

联系作者