相关论文链接:

GNN综述:A Comprehensive Survey on Graph Neural Networks

ChebNet:Convolutional neural networks on graphs with fast localized spectral filtering

GCN:Semi-supervised classification with graph convolutional networks

Spectral-based ConvGNN一般形式为

其中$\mathbf{g}_{\theta}=diag(\mathbf{U}^T\mathbf{g})$为卷积核

ChebNet

Spectral-based ConvGNN原始形式中的卷积核$\mathbf{g}_{\theta}(\Lambda)=diag(\theta_1,…,\theta_n)$存在两个问题

  • 非局部化,即每次卷积都用到了图中所有节点
  • 参数量是$O(n)$的,即与输入图节点数成正比

为解决这些问题,ChebNet选择使用多项式来近似$\mathbf{g}_{\theta}(\Lambda)$,即

这样卷积核$\theta\in R^K$的参数量就变为常数$K$,且卷积具有K阶局部性,即对于任意节点,卷积只利用与其距离不超过$K$的节点的信息,下面是一个简单的证明

若$d{min}(i,j)>K$,则$(\mathbf{L}^k){i,j}=0$,因此节点$j$无法从节点$i$处获取信息

然而此时$g{\theta}$与$U$相乘的复杂度仍是$O(n^2)$的,ChebNet选择进一步使用$K$阶切比雪夫多项式来近似$g{\theta}$,即

其中$\tilde{\Lambda}=2\Lambda/\lambda_{max}-\mathbf{I}_n$,目的是将特征值对角阵的值域规范到$[-1,1]$中,参数$\theta_i\in R^K$

由数学归纳法易证$\mathbf{U}Ti(\tilde{\Lambda})\mathbf{U}^T=T_i(\tilde{\mathbf{L}})$,其中$\tilde{\mathbf{L}}=2\mathbf{L}/\lambda{max}-\mathbf{I}_n$,于是卷积公式可表示为

由于$T_i$可以递归计算,且稀疏图可以使用特殊的矩阵乘法进行加速,因此卷积的复杂度为$O(K|E|)$


这里补充一下切比雪夫多项式的说明,第一类切比雪夫多项式定义为

切比雪夫多项式定义的函数序列在$[-1,1]$上带权$\rho(x)=\frac{1}{\sqrt{1-x^2}}$正交,即

特别的,切比雪夫多项式可通过递归计算

切比雪夫多项式常用于函数逼近问题,即通过${Tn(x)}{0}^{\infty}$的线性组合$y=\sum_{i=0}^nc_iT_i(x)$近似给定函数$f$


GCN

GCN (Graph Convolutional Network) 是ChebNet的一阶近似

假设$K=1$且$\lambda=2$,ChebNet的卷积表达式简化为

为进一步限制参数数量以及避免过拟合,GCN假设$\theta=\theta_0=-\theta_1$,于是有

对于多通道的图信号,假设卷积层输入通道数为$C$,输出通道数为$F$,则有

其中$\mathbf{X}\in R^{N\times C}, \mathbf{\Theta}\in R^{C\times F}$,$\mathbf{\overline{A}}=\mathbf{I}_n+\mathbf{D}^{-\frac{1}{2}}\mathbf{A}\mathbf{D}^{\frac{1}{2}}$,$f$为激活函数

由于$\mathbf{\overline{A}}$的特征值取值范围为$[0,2]$,因此多个GCN层堆叠可能导致梯度爆炸/消失

为解决这个问题作者进行了重规范化,使用$\mathbf{\tilde{D}}^{-\frac{1}{2}}\mathbf{\tilde{A}}\mathbf{\tilde{D}}^{-\frac{1}{2}}$代替$\mathbf{\overline{A}}$,其中$\mathbf{\tilde{A}}=\mathbf{A}+\mathbf{I}n, \mathbf{\tilde{D}}{ii}=\sumj\mathbf{\tilde{A}}{ij}$

GCN的复杂度仅$O(|E|)$,且表现十分优秀,因此使用广泛