《SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS》论文理解

在《SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS》 中，作者对《Convolutional Neural Networks on Graphs
with Fast Localized Spectral Filtering》作出了改进，提出了以下创新：
（1）提出了一个可以直接在图上操作的神经网络模型的逐层传播规则；
（2）证明了这种形式的图卷积网络怎样在图上实现半监督的节点分类；

1.神经网络模型的逐层传播规则
卷积公式的频域表示：
$g*x=Ug_{\theta}U^{T}x\tag{1}$g∗x=Ugθ​UTx(1)

定义$L$L为对称归一化图拉普拉斯矩阵，$L=I_{N}-D^{-\frac{1}{2}}AD^{-\frac{1}{2}}=U\Lambda U^{T}$L=IN​−D−21​AD−21​=UΛUT,$A$A是无向图的邻接矩阵(可以是二值，也可以是权值)，$D_{ii}=\sum_{j}{A_{ij}}$Dii​=∑j​Aij​是图的度矩阵。$U$U是$L$L特征向量矩阵。$L$L的特征值范围为[0,1]。
由论文《Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering》得到，式(1)可以推导为：
$g_{\theta^{'}}(\Lambda) \approx \sum_{k=0}^{K}{\theta_{k}^{'}}T_{k}(\tilde\Lambda)\tag{2}$gθ′​(Λ)≈k=0∑K​θk′​Tk​(Λ~)(2)

其中$\tilde\Lambda=\frac{2}{\lambda_{max}}\Lambda-I_{N}$Λ~=λmax​2​Λ−IN​,$\theta^{'}\in R^{K}$θ′∈RK是切比雪夫系数。得到：$g*x \approx \sum_{k=0}^{K}{\theta_{k}^{'}}T_{k}(\tilde L)x$g∗x≈∑k=0K​θk′​Tk​(L~)x,其中$\tilde L=\frac{2}{\lambda_{max}}L-I_{N}$L~=λmax​2​L−IN​。$\tilde L$L~的特征值范围为[-1,1]。
当使用$K=1$K=1时，式（2）在频域变为线性函数，即：
$g*x\approx \theta_{0}^{'}x+\theta_{1}^{'}(\frac{2}{\lambda_{max}}L-I_{N})x\tag{3}$g∗x≈θ0′​x+θ1′​(λmax​2​L−IN​)x(3)

将$\lambda_{max}\approx2$λmax​≈2，则
$g*x\approx \theta_{0}^{'}x+\theta_{1}^{'}(L-I_{N})x=\theta_{0}^{'}x-\theta_{1}^{'}(D^{-\frac{1}{2}}AD^{-\frac{1}{2}})x\tag{4}$g∗x≈θ0′​x+θ1′​(L−IN​)x=θ0′​x−θ1′​(D−21​AD−21​)x(4)

由于$\theta_{0}^{'},\theta_{1}^{'}$θ0′​,θ1′​是训练参数，是可调整的，使得$\theta_{0}^{'}=-\theta_{1}^{'}=\theta$θ0′​=−θ1′​=θ，那么
$g*x\approx \theta(I_{N}+D^{-\frac{1}{2}}AD^{-\frac{1}{2}})x\tag{5}$g∗x≈θ(IN​+D−21​AD−21​)x(5)

$I_{N}+D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$IN​+D−21​AD−21​的特征值范围为[0,2],可能会导致梯度消失和梯度爆炸的问题，将$I_{N}+D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$IN​+D−21​AD−21​再次归一化为$\tilde D^{-\frac{1}{2}}\tilde A\tilde D^{-\frac{1}{2}}$D~−21​A~D~−21​,其中，$A\tilde = A+I_{N}$A=~A+IN​,$\tilde D_{ii}=\sum_{j}\tilde A_{ij}$D~ii​=∑j​A~ij​，可以有效的避免这个问题，同时由于$\theta$θ为一个数，可以放到等式的最后，得到：
$g*x\approx(\tilde D^{-\frac{1}{2}}\tilde A\tilde D^{-\frac{1}{2}})x \theta\tag{6}$g∗x≈(D~−21​A~D~−21​)xθ(6)

当信号$x$x为多通道信号$X\in R^{N×C}$X∈RN×C时，并且使用$F$F个卷积核，使得每个输出节点的通道数为$F$F，则：
$Z=(\tilde D^{-\frac{1}{2}}\tilde A\tilde D^{-\frac{1}{2}})X\Theta\tag{7}$Z=(D~−21​A~D~−21​)XΘ(7)

$C$C为输入节点的通道数，$F$F为输出节点的通道数，同时也是卷积核数目；$\Theta \in R^{C×F}$Θ∈RC×F为这$F$F个卷积核的参数。

2.半监督的节点分类
令$\tilde D^{-\frac{1}{2}}\tilde A\tilde D^{-\frac{1}{2}}=\hat A，\Theta=W$D~−21​A~D~−21​=A^，Θ=W,则两层的图卷积分类网络可以表示为：
$Z=f(X,A)=softmax(\hat A\ ReLU(\hat AXW^{(0)})W^{(1)})\tag8$Z=f(X,A)=softmax(A^ ReLU(A^XW(0))W(1))(8)

需要说明的是，一个图就是一个样本，每个样本在逐层传播的过程中认为$\hat A$A^是一样的，也就是说每层中$\hat A$A^是共享的。$softmax(x_{ij})=\frac{exp(x_{ij})}{\sum_{j}exp(x_{ij})}$softmax(xij​)=∑j​exp(xij​)exp(xij​)​，$i \in [1,N],j \in [1,F],x_{i} \in R^{1×F}$i∈[1,N],j∈[1,F],xi​∈R1×F表示两层卷积后输出$(R^{N×F})$(RN×F)的第$i$i行。交叉熵为$L=-\sum_{l\in Y_{L}}\sum_{f=1}^{F}Y_{lf}lnZ_{lf}$L=−∑l∈YL​​∑f=1F​Ylf​lnZlf​,其中$Y_{L}$YL​是有标签节点的集合。