Titlel：《Semi-Supervised Classification with Graph Convolutional Networks》
Authors：Thomas Kipf, M. Welling
Source：2016, ICLR
Paper：Download
Code：Download
本文主要是：基础+二代GCN+三代GCN
0 Knowledge review 0.1 卷积卷积的定义：$(f∗g)(t)$ 为 $f ∗ g $ 的卷积
连续形式：
$(f * g)(t)=\int_{R} f(x) g(t-x) d x$
离散形式：
$(f * g)(t)=\sum\limits _{R} f(x) g(t-x)$
0.2 傅里叶变换核心：将函数用一组正交基函数的线性组合表述出来。
Fourier 变换：
$F\{f\}(v)=\int_{R} f(x) e^{-2 \pi i x \cdot v} d x$
Where
$e^{-2 \pi i x \cdot v}$ 为傅里叶变换基函数，且为拉普拉斯算子的特征函数 。
Fourier 逆变换：
$F^{-1}\{f\}(x)=\int_{R} f(x) e^{2 \pi i x \cdot v} d v$
0.3 傅里叶变换和卷积的关系定义 $h$ 是 $f$ 和 $g$ 的卷积，则有
$\begin{aligned}\mathcal{F}\{f * g\}(v)&=\mathcal{F}\{h\}(v)\\&=\int_{R} h(x) e^{-i 2 \pi v x} d x \\&=\int_{R} \int_{R} f(\tau) g(x-\tau) e^{-i 2 \pi v x} d \tau d x \\&=\int_{R} \int_{R}\left[f(\tau) e^{-i 2 \pi v \tau} d \tau\right] \left[g(x-\tau) e^{-i 2 \pi v(x-\tau)} d x\right] \\&=\int_{R}\left[f(\tau) e^{-i 2 \pi v \tau} d \tau\right] \int_{R}\left[g\left(x^{\prime}\right) e^{-i 2 \pi v x^{\prime}} d x^{\prime}\right]\\&=\mathcal{F}\{f \}(v)\mathcal{F}\{g \}(v)\end{aligned}$
对上式左右两边做逆变换 $F^{-1}$ ，得到
$f * g=\mathcal{F}^{-1}\{\mathcal{F}\{f\} \cdot \mathcal{F}\{g\}\}$
0.4 拉普拉斯算子定义：欧几里德空间中的一个二阶微分算子，定义为梯度的散度。可以写作 $\Delta$, $\nabla^{2}$, $\nabla \cdot \nabla$ 这几种形式。
例子：一维空间形式
$\begin{aligned}\Delta f(x) &=\frac{\partial^{2} f}{\partial x^{2}} \\&=f^{\prime \prime}(x) \\& \approx f^{\prime}(x)-f^{\prime}(x-1) \\& \approx[f(x+1)-f(x)]-[f(x)-f(x-1)] \\&=f(x+1)+f(x-1)-2 f(x)\end{aligned}$
即：拉普拉斯算子是所有自由度上进行微小变化后所获得的增益。
0.5 拉普拉斯矩阵所有节点经过微小扰动产生的信息增益：
$\begin{array}{l}\bigtriangleup f &= (D-W) f \\&=L f\end{array}$
类比到图上，拉普拉斯算子可由拉普拉斯矩阵 $L$ 代替。
Where
$L $ is Graph Laplacian.
0.6 拉普拉斯矩阵谱分解$L \mu_{k}=\lambda_{k} \mu_{k}$
由于 $L $ 拉普拉斯矩阵是 实对称矩阵，所以
$L=U \Lambda U^{-1}=U \Lambda U^{T}$
Where
$\Lambda$ 为特征值构成的对角矩阵;
$U$ 为特征向量构成的正交矩阵。
0.7 图傅里叶变换让拉普拉斯算子 $\bigtriangleup$ 作用到傅里叶变换的基函数上，则有:
$\begin{array}{c}\Delta e^{-2 \pi i x \cdot v}=\frac{\partial^{2}}{\partial^{2} v} e^{-2 \pi i x \cdot v}=-{(2 \pi x)}^2 e^{-2 \pi i x \cdot v} \\\Updownarrow \\L \mu_{k}=\lambda_{k} \mu_{k}\end{array}$
Where
拉普拉斯算子 $\bigtriangleup $ 与 拉普拉斯矩阵 $L$ “等价” 。（两者均是信息增益度）
正交基函数 $e^{-2 \pi i x \cdot v}$ 与 拉普拉斯矩阵的 正交特征向量 $\mu_{k}$ 等价。
根据亥姆霍兹方程 $\bigtriangleup f= \nabla^{2} f=-k^{2} f$ ，$-(2 \pi x)^{2}$ 与 $\lambda_{k}$ 等价。
对比傅里叶变换：
$F\{f\}(v)=\int_{R} f(x) e^{-2 \pi i x \cdot v} d x$
可以近似得图傅里叶变换：
$F\{f\}\left(\lambda_{l}\right)=F\left(\lambda_{l}\right)=\sum \limits _{i=1}^{n} u_{l}^{*}(i) f(i)$
Where
$\lambda_{l}$ 表示第 $l$ 个特征；
$n$ 表示 graph 上顶点个数；
$f(i)$ 顶点 $i$ 上的函数。
Another thing：对于所有节点
值向量
$f=\left[\begin{array}{c}f(0) \\f(1) \\\cdots \\f(n-1)\end{array}\right]$
$n$ 个特征向量组成的矩阵