一、回答四个必要问题

1、What did authors try to accomplish?

• 提出一个可扩展的半监督图卷积神经网络
• 第一：作者介绍了一个简单且行为规范的分层传播规则，该规则可以直接在图上运行。同时我们推导出如何从频谱卷积的一阶近似中使之激活。（快速卷积规则）
• 第二：作者介绍了这个规则如何用于可扩展的图半监督分类学习

2、What were the key elements of the approach?

•  快速卷积规则的数学推导
• 半监督学习的传播过程

3、What can you use yourself?

 使用其快速卷积的理论基础，利用该架构实现图上的半监督学习。

4、What reference do you want to follow?

None。

二、文章结构

1.Introduction

• 提出新的Loss公式
• 介绍文章主要工作，一是引入新的分层传播规则，二是该种规则如何运用于半监督分类学习的图网络中

2.Fast Approximate Convolutions on Graphs(图上的快速逼近卷积方法）

• 图上的传播规则

\begin{equation}
H^{(l+1)}=\sigma(\widetilde{D}^{-\frac{1}{2}}\widetilde{A}\widetilde{D}^{-\frac{1}{2}}H^{l}W^{l}).
\end{equation}

其中$\sigma$代表激活函数，例如RELU；$\widetilde{A}$是邻接矩阵加上自连接(self connection)；$\widetilde{D}^{-\frac{1}{2}}\widetilde{A}\widetilde{D}^{-\frac{1}{2}}$代表归一化的拉普拉斯变换 ,$\H^{l}$为特征矩阵，$W^{l}$为某层可训练的参数

2.1 Spectral Graph Convolutions（频域图卷积）

• 定义卷积操作

\begin{equation}
g_{\theta} \star x=U g_{\theta}U^{T}x
\end{equation}

　其中$U$是归一化后拉普拉斯矩阵的特征向量；

\begin{equation}
L=I_{N}-\widetilde{D}^{-\frac{1}{2}}\widetilde{A}\widetilde{D}^{-\frac{1}{2}}=U\Lambda U^{T}
\end{equation}

可以将$g_{\theta}$理解为$L$的特征值函数。由于对特征值矩阵的计算代价较高（$O(N^{2})$），而且在图比较大的时候计算$L$也比较expensive.为了解决这个问题$g_{\theta}(\Lambda)$可以被Chebyshev（切比雪夫）多项式的K阶展开取代。

\begin{equation}
g_{\theta^{'}}(\Lambda)\approx\sum_{k=0}^K\theta_{k}^{'}T_{k}(\widetilde{\Lambda})x
\end{equation}

上述$\widetilde{\Lambda}=\frac{2}{\lambda_{max}}\Lambda-I_{N}$，$\lambda_{max}$代表$L$的最大特征值。$\theta_{k}^{'}$是切比雪夫系数的向量，切比雪夫不等式的递归定义如下：

\begin{equation}
T_{k}(x)=2x T_{k-1}(x)-T_{k-2}(x),with\quad T_0(x)=1\quad and \quad T_1(x)=x
\end{equation}

由第一个定义卷积的公式可以得出：

\begin{equation}
g_{\theta^{'}}\star x\approx\sum_{k=0}^{K}\theta_{k}^{'}T_{k}(\widetilde{L})x \quad with\quad \widetilde{L}=\frac{2}{\lambda_{max}}L-I_{N}
\end{equation}

此为1606.09375-Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering文章中定义的卷积。

证明过程：

\begin{aligned}g_\theta * x & = Ug_\theta U^Tx \\& = U g_{\theta}(Λ) U^Tx \\& =U (\sum^{K}_{k=0} \theta_kT_K(\tilde Λ)) U^Tx \\& = (\sum^{K}_{k=0} \theta_kT_K(U\tilde Λ U^T)) x \\& = \sum^{K}_{k=0} \theta_k T_K(\tilde L) x \qquad \end{aligned}

2.2layer-wise Linear Model（分层线性模型）

• 引入一阶近似ChebNet。假设K=1，$\lambda_{max}=2$，则卷积公式简化近似为：

\begin{equation}
x\ast g_\theta=\Theta_0 x-\Theta_1D^{-\frac{1}{2}}AD^{-\frac{1}{2}}x
\end{equation}

假设$\Theta=\Theta_0=-\Theta_1$:

\begin{equation}
x\ast g_\theta=\Theta(I_N+D^{-\frac{1}{2}}AD^{-\frac{1}{2}})x
\end{equation}

又因为$I_N+D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$是范围$[0,2]$的特征值，在训练过程中会出现梯度爆炸和消失的情况，所以引入一个$renormalization \quad trick$:

\begin{equation*}
I_N+D^{-\frac{1}{2}}AD^{-\frac{1}{2}}\stackrel{\widetilde{A}=A+I_N}{\longrightarrow}{\widetilde{D}^{-\frac{1}{2}}\widetilde{A}\widetilde{D}^{-\frac{1}{2}}}
\end{equation*}

其中$\widetilde{A}=A+I_N,\widetilde{D_{ii}}=\sum_j\widetilde{A}_{ij}$,即图中加上自连接。

再加上激活函数即推导出公式（1）的传播规则:

$H^{(l+1)}=\sigma(\widetilde{D}^{-\frac{1}{2}}\widetilde{A}\widetilde{D}^{-\frac{1}{2}}H^{l}W^{l}).$

可以推广这个特征映射公式到具有C个输入通道（即每个结点的C维特征向量）的信号$X\in\mathbb{R}^{N \times C}$和F个滤波器：

\begin{equation*}
Z={\widetilde{D}^{-\frac{1}{2}}\widetilde{A}\widetilde{D}^{-\frac{1}{2}}}X\Theta
\end{equation*}

　　其中$\Theta\in\mathbb{R}^{C \times F}$是滤波器的参数矩阵，$Z\in\mathbb{R}^{N \times F}$是一次卷积输出的矩阵