前言

深度学习中大家熟知的几种框架DNN、CNN、RNN(LSTM和GRU)等等是为了处理欧式空间中的数据，如图片、语音、文本。而图神经网络可以应用于更为丰富的拓扑结构数据，如社交网络、推荐系统、交通网络等，这些数据的特点是具有无序的连接关系。
图神经网络是受CNN的启发，并假设距离越近的两个节点，它们的关系也更为亲密，试图通过将节点的特征信息和节点之间的拓扑信息相结合的方式来进行节点预测、图预测等任务。

信号处理和傅里叶变换（基础）

以波的形式传递的信号常常会通过傅里叶变换将其从时域空间转到频域空间进行处理，下面以一个简单的例子进行说明：对声音进行变声处理，可以分为以下几步,

1.用傅里叶变换将声波从时域转换到频域,
$F(w)=\int_{- \infty}^{+\infty} f(t)e^{-itw}dt$

左图为声波的时域图，右图为频域图

2.对频域图进行滤波处理：即用某个函数 $h(w)$ 与 $F(w)$ 相乘,

滤波后的频域图.png

3.将频域进行逆傅里叶变换，重新变为声波,

F(t) = \int_{-\infty}^{+\infty}f(w)e^{itw}dw

变换后的时域图

图片转自python基于傅里叶变换的频率滤波－音频降噪

注：傅里叶变换就是以 $e^{-iwt}$ 为基底， $f(t)$ 为系数的线性组合。

图基本定义

设G(V,E)，V代表节点集合，共有N个节点；E代表边集合，共有M条边。可以用连接矩阵A来表示一个图的拓扑结构信息,
$A = \left\{ \begin{aligned} &1 \ \ A_{ij} \in E\\ &0 \ \ A_{i,j} \notin E \end{aligned} \right.$
用D表示度矩阵，它是一个对角阵，对角线上的元素是节点的度数,
$D_{ii} = \sum_j A_{ij}\$
拉普拉斯矩阵L的定义如下：
$L = D - A$

拉普拉斯矩阵

为了使大家能对GCN有更加直观的理解，这里对拉普拉斯矩阵做几点说明。

$(L x)_{i}=\sum_{j \in N(v_i)} (x_i - x_j)$ ，其中 $x \in R^N$ ， $N(v_i)$ 代表节点 $v_i$ 的一阶邻居节点集合。可以看到 $L$ 矩阵是对图中一阶节点信息的简单聚合操作。
$x^T L x = \sum_{e_{ij}\in E} (x_i - x_j)^2$ ，可以衡量一个图中节点信息的差异性，该值越大，则信息差异也越大。且可以看出 $L$ 是对称的半正定矩阵。
常用的拉普拉斯矩阵是其规范化的形式： $L_{s} = D^{(- \frac{1}{2})} L D^{(- \frac{1}{2})}$ ，该矩阵通过特征分解得到的特征值，其范围是[0,2)。证明如下,
$Lemma$
$\lambda_{min} = min \frac{x^T B x}{x^T x},\\ \lambda_{max}=max \frac{x^T B x}{x^T x}$
其中 $\lambda_{min}$ 是矩阵 $B$ 的最小特征值， $\lambda_{max}$ 是矩阵 $B$ 的最大特征值。
$Proof$
最小特征值为0可以从 $L_{s}$ 为半正定矩阵推出，且其特征向量较易得出 $D^{\frac{1}{2}} I$ ，下证其最大特征值<2,
$\begin{aligned} & \frac{x^TL_{s} x}{x^T x} \\ =& \frac{x^TD^{(- \frac{1}{2})} L D^{(- \frac{1}{2})}x}{x^T x} \\ =& \frac{y^TL y}{y^T D y} (令y=D^{- \frac{1}{2}}x) \\ =& \frac{\sum_{e_{ij} \in E} (y_i - y_j)^2}{\sum_{e_{ij} \in E}(y_i ^2 + y_j ^2)} \\ \leq & \frac{\sum_{e_{ij} \in E} 2(y_i ^2 + y_j ^2)}{\sum_{e_{ij} \in E}(y_i ^2 + y_j ^2)} = 2，得证 \end{aligned}$
特征分解：因为 $L$ 是一个对称阵，一定有一个正交阵 $V$ ，使得其对角化，对应的对角矩阵为 $\Lambda$ ,
$VLV^T = \Lambda$
设 $x \in R^N$ ，对其进行傅里叶变换,
$\tilde{x} = V^T x$
对其进行逆傅里叶变换：
$\begin{aligned} x =& V \tilde{x} \\ =& [v_1,...,v_N] \tilde{x} \\ =& \sum_{i=1}^{N} v_i \tilde{x}_i \end{aligned}$
其中特征向量 $v_i$ 为基底，傅里叶系数为其线性组合的系数。

GCN

理论

GCN的计算过程与信号处理过程相同，先将卷积核和图数据通过傅里叶变换转换到频域空间，再对频域空间的系数进行数值运算，最后进行逆傅里叶变换得到卷积后的结果。设 $x \in R^N$ 是图中节点的特征向量， $\theta$ 是待学习的参数，则一次图卷积可以定义为,
$\begin{aligned} y=&F^{-1}(g(\theta) \circ F(x)) \\ =&F^{-1}(g(\theta)\circ V^Tx)\\ =&F^{-1}(diag(\theta)V^Tx) \\ =&Vdiag(\theta)V^Tx \end{aligned}$
其中 $F$ 代表傅里叶变换， $F^{-1}$ 代表逆傅里叶变换， $g(\theta)=diag(\theta)$ ， $\circ$ 代表元素之间的点乘。
从式子中可以看出待学习的参数是 $diag(\theta)，$ 共 $N$ 个，即和图中节点的数目相关，该方法难以适应节点数量较多的图（而这种情况在现实世界中更为常见）。那么可以使用多项式进行逼近，下面简单介绍下切比雪夫多项式。
$切比雪夫多项式递推形式\left\{\begin{aligned} &T_0(x) = 1\\ &T_1(x) = x\\ &T_n(x) = 2x*T_{n-1}(x) - T_{n-2}(x) \end{aligned} \right. x\in[-1,1]$
则对应的 $g(\theta)=\sum_{k=0}^{K}\theta_{k}'T_k(\tilde\Lambda)$ ，其递推形式为,
$切比雪夫多项式递推形式 \left\{\begin{aligned} &T_0(\tilde\Lambda) = 1\\ &T_1(\tilde\Lambda) = \tilde\Lambda\\ &T_n(\tilde\Lambda) = 2\tilde\Lambda*T_{n-1}(\tilde\Lambda) - T_{n-2}(\tilde\Lambda) \end{aligned} \right. \tilde\Lambda=\frac{2}{\lambda_{max}}\Lambda_s-I \in [-1, 1]$
对应的 $y=\sum_{k=0}^{K}\theta_{k}'T_k(\tilde L)x$ ，其递推形式为，
$切比雪夫多项式递推形式 \left\{\begin{aligned} &T_0(\tilde L) = 1\\ &T_1(\tilde L) = \tilde L\\ &T_n(\tilde L) = 2 \tilde L*T_{n-1}(\tilde L) - T_{n-2}(\tilde L) \end{aligned} \right. \tilde L=\frac{2}{\lambda_{max}}L_s-I \in [-1, 1]$
用一阶切比雪夫多项式进行逼近， $\lambda_{max} \approx2$ ，令 $\theta=\theta_0'=-\theta_1'$ ，
$\begin{aligned} y=&(\theta_0I+\theta_1\tilde L)x \\ =&(\theta_0I+\theta_1(L_s-I))x\\ =&(\theta_0I-\theta_1D^{-\frac{1}{2}}AD^{-\frac{1}{2}})x\\ =&\theta(I+D^{-\frac{1}{2}}AD^{-\frac{1}{2}})x\\ \approx & \theta\tilde D^{-\frac{1}{2}}\tilde A \tilde D^{-\frac{1}{2}} x \end{aligned}$
其中 $\tilde D=D+I,\tilde A=A+I$ 。
进一步推广，得到图卷积的形式，设 $X \in R^{n*m}$ ， $m$ 是特征向量的维度， $W\in R^{m*d}$ ， $d$ 是输出向量的维度，
$Z=\tilde D^{-\frac{1}{2}}\tilde A \tilde D^{-\frac{1}{2}}XW$
paper：semi-supervised classification with graph convolutional networks