问题描述

卷积神经网络（CNN）的输入图片是具有欧几里得结构的图结构，具有规则的空间结构，比如图片是规则的正方形栅格，比如语音是规则的一维序列。而这些数据结构能够用一维、二维的矩阵表示，卷积神经网络处理起来很高效。

而广义上的图（graph）是非欧几里得结构，不规则的空间结构。图卷积神经网络就是以某种方式将卷积算子推广到任意图数据上。融合节点特征和图的拓扑结构，利用深度学习生成新的表示的方法。

图卷积神经网络具有卷积神经网络的以下性质

• 局部参数共享：算子适用于每个节点，处处共享
• 感受域正比于层数：最开始，每个节点包含直接邻居的信息，然后把邻居的邻居的信息包含近来。层数越多，感受域越广。

GCN

模型
$H^{(l+1)}=\sigma(\tilde D^{-1/2} \tilde A \tilde D^{-1/2} H^{(l)}W^{(l)})$H(l+1)=σ(D~−1/2A~D~−1/2H(l)W(l))
$\tilde A = A + I_N$A~=A+IN​ 是邻接矩阵加上自环，$I_N$IN​ 是单位矩阵，

ChebNet

谱图卷积

图的谱卷积（spectral convoluton）定义为信号$x\in \mathbb R^{N \times N}$x∈RN×N 与滤波器 $g_\theta ={\rm diag}(\theta) $ 相乘，其中 $\theta \in \mathbb R^{N \times N}$θ∈RN×N 为傅里叶系数向量。
$g \star x = U g_\theta U^{T}x$g⋆x=Ugθ​UTx
其中$U$U是归一化图拉普拉斯矩阵的特征向量构成的矩阵，归一化图拉普拉斯矩阵 $L = I_N - D^{-1/2}AD^{-1/2} = U \Lambda U^{T}$L=IN​−D−1/2AD−1/2=UΛUT，因为 $L$L 是实对称矩阵，所以$L= U \Lambda U^{-1}= U \Lambda U^{T}$L=UΛU−1=UΛUT

$\Lambda$Λ 是$L$L的特征值构成的对角矩阵，$U^{T}x$UTx是$x$x的图傅里叶变换。我们可以将$g_\theta$gθ​理解为$L$L的特征值的函数，即 $ g_{\theta} (\Lambda) = \sum_{k=0}^{K-1}\theta_{k} \Lambda^{k} $ ，其中 $\theta \in \mathbb R^{N \times N}$θ∈RN×N 为多项式系数向量。

在大图中计算$L$L 的特征分解复杂度很高，为了解决问题，使用切比雪夫多项式$T_k(x)$Tk​(x)直到第$k$k阶的截断展开来近似$g_\theta (\Lambda)$gθ​(Λ)
$g_{\theta } (\Lambda) \approx \sum_{k=0}^{K-1} \theta_{k}T_{k}(\tilde{\Lambda})$gθ​(Λ)≈k=0∑K−1​θk​Tk​(Λ~)
其中 $ \tilde{\Lambda} = \frac{2}{\lambda_{\rm max}} \Lambda - I_N$， $\lambda_{max}$λmax​是$L$L中最大的特征值，$\theta\in \mathbb R^{K}$θ∈RK 是切比雪夫系数向量。切比雪夫多项式定义为$ T_{k}(x) = 2xT_{k-1}(x) - T_{k-2}(x)$ 其中 $ T_0 = 1 $ ，$ T_1 = x$。因此信号与滤波器相乘可近似为：
$g_{\theta } (\Lambda) \star x \approx \sum_{k=0}^{K-1} \theta_{k} T_{k}(\tilde{L}) x$gθ​(Λ)⋆x≈k=0∑K−1​θk​Tk​(L~)x
其中$ \tilde{L} = \frac{2}{\lambda_{\rm max}} L - I_N$。上式是K-localized，因为式子是$。上式是K−localized，因为式子是L$ 的K阶展开，即依赖于从中心节点出发最多K步内能到达的节点（K阶邻居）。该式计算复杂度为 $O(|\mathcal{E} |)$O(∣E∣) ，与边数呈线性关系。

模型
$H^{(l+1)}= \sum_{k=0}^{K} T_k{ (\tilde{L} )}H^{(l)}W^{(k)}$H(l+1)=k=0∑K​Tk​(L~)H(l)W(k)
其中$T_k(\tilde L) = 2{\tilde L}T_{k-1}(\tilde L) - T_{k-2}(\tilde L) $，$，T_1(\tilde L) = \tilde L, T_0(\tilde L) =I_N$；这些系数在预处理步骤先计算。$；这些系数在预处理步骤先计算。H^{(0)}=X$

FastGCN

总结

传播模型

模型	传播模型 $H^{(l+1)}=\sigma(\cdot)$H(l+1)=σ(⋅)	介绍	计算复杂度
GCN	$\hat AH^{(l)}W^{(l)}$A^H(l)W(l)	一阶近邻近似，多层叠加	$O(
ChebNet	$\sum_{k=0}^{K} T_k{ (\tilde{L} )}H^{(l)}W^{(k)}$∑k=0K​Tk​(L~)H(l)W(k)	利用截断的切比雪夫多项式近似，K阶近似
MLP	$H^{(l)}W$H(l)W

Reference

[1] T. N. Kipf and M. Welling, ``Semi-supervised classification with graph convolutional networks,’’ Int. Conf. Learn. Representations, pp. 1-14, 2017.

[2] M. Defferrard and P. Bresson, X.and Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In NIPS, 2016.