思想
GCN 是谱图卷积（spectral graph convolution） 的局部一阶近似（localized first-order approximation）。GCN的另一个特点在于其模型规模会随图中边的数量的增长而线性增长。总的来说，GCN 可以用于对局部图结构与节点特征进行编码。
特点
图卷积神经网络具有几个特点：
- 局部特性：图卷积神经网络关注的是图中以某节点为中心，K阶邻居之内的信息，这一点与GNN有本质的区别；
- 一阶特性：经过多种近似之后，GCN变成了一个一阶模型。也就是说，单层的GCN可以被用于处理图中一阶邻居上的信息；若要处理K阶邻居，可以采用多层GCN来实现；
- 参数共享：对于每个节点，其上的滤波器参数 W 是共享的，这也是其被称作图卷积网络的原因之一。
Symbols
- $\mathcal{G}=(\mathcal{V},\mathcal{E}) $表示一个图， $\mathcal{V},\mathcal{E} $分别表示相应的节点集与边集，$u,v\in\mathcal{V} $表示图中的节点，$ (u,v)\in\mathcal{E} $表示图中的边。
- A 表示图的邻接矩阵（adjacency matrix）。节点的连接情况的矩阵。该矩阵可以是二值的，也可以是带权的
- D 表示图的度矩阵（degree matrix）。度矩阵是一个对角矩阵，对于无向图来说，一般只使用入度矩阵或出度矩阵。
-
L 表示图的拉普拉斯矩阵（Laplacian matrix），$\mathcal{L}$ 表示图的归一化拉普拉斯矩阵。
$d_{v}$ 表示节点 v 的度，则该矩阵称之为图 $\mathcal{G}$ 的拉普拉斯矩阵（ L=D-A ）。相应的归一化拉普拉斯矩阵为
可以通过下式计算：
motivation
普图卷积
GCN是谱图卷积的一阶局部近似，图上的谱卷积可以定义为信号 $x\in\mathbb{R}^{N} $与滤波器 $g_{\theta}=diag(\theta) （ \theta\in\mathbb{R}^{N} ）$在傅里叶域的乘积:
U 为归一化拉普拉斯 $L=I_{N}-D^{-\frac{1}{2}}AD^{-\frac{1}{2}}=U\Lambda U^{T} $的特征向量矩阵（即谱矩阵），其中， $\Lambda$ 为相应的特征值矩阵（对角矩阵）， $U^{T}x$ 为 x 的图傅氏变换。在这里，可以将 $g_{\theta} $看作是 L 特征向量的函数，也就是 $g_{\theta}(\Lambda)$
问题
谱图卷积的计算代价很大；因此使用切比雪夫多项式（Chebyshev polynomial） $T_{k}(x) $的 K 阶截断来获得对 $g_{\theta}(\Lambda) $的近似 :
其中， $\tilde{\Lambda}=\frac{2}{\lambda_{max}}\Lambda-I_{N} $为 L 的最大特征值（即谱半径）缩放后的特征向量矩阵。 $\theta’\in \mathbb{R}^{K} $表示一个切比雪夫向量。切比雪夫多项式使用递归的方式进行定义：$T_{k}(x)=2xT_{k-1}(x)-T_{k-2}(x) $，其中， $T_{0}(x)=1 $且 $T_{1}(x)=x $。
推导
使用近似的 g_{\theta’} 替代原来的 g_{\theta}
而 $T_{k}(\tilde{\Lambda}) $是$ \Lambda $的 k 阶多项式，且有 $ U\tilde{\Lambda}^{k}U^{T}=(U\tilde{\Lambda}U^{T})^{k}=\tilde{L}^{k} $，其中， $\tilde{L}=\frac{2}{\lambda_{max}}L-I_{N}$ 。这样
可以发现，谱图卷积不再依赖于整个图，而只是依赖于距离中心节点 K 步之内的节点（即 K 阶邻居,使用了这一概念定义了图上的卷积神经网络。
Layer-wise线性模型
一阶邻居依赖
在$ \tilde{L} $上进行 K 阶运算。在实际过程中，这一运算的代价也是非常大的,为了进一步简化该运算，限定 K=1 。此时，谱图卷积可以近似为 $\tilde{L} $（或$ L $）的线性函数；图谱卷积的一阶线性近似：
叠加layer实现K-阶邻居依赖
通过堆积多层图卷积网络建立 K 阶邻居的依赖，而且，这样做的另一个优势是，在建立 K>1 阶邻居的依赖时，不需要受到切比雪夫多项式的限制。仅有两个参数 $\theta_{0}’ $与 $\theta_{1}’ $。若需建立 k 阶邻居上的依赖，可以通过设置 k 层这样的滤波器来实现.
通过对参数进行约束来避免过拟合，并进一步简化运算复杂度。例如，可以令 \theta=\theta_{0}’=-\theta_{1}’ ，从而得到
需要注意的是，$ I_{N}+D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$ 的特征值范围为[0,2]，这意味着，当不停地重复该操作时（网络非常深时），可能会引起梯度爆炸或梯度消失。
renormalization trick（解决深网络的梯度消失、梯度爆炸问题）
其中， $\tilde{A}=A+I_{N} ， \tilde{D}{ii}=\Sigma{j}\tilde{A}_{ij} $。
当图中每个节点的表示不是单独的标量而是一个大小为 C 的向量时，可以使用其变体进行处理：
其中， $\Theta\in\mathbb{R}^{C\times F} $表示参数矩阵， $Z\in\mathbb{R}^{N\times F} $为相应的卷积结果。此时，每个节点的节点表示被更新成了一个新的 $F$ 维向量， 该 F 维向量包含了相应的一阶邻居上的信息 。
图卷积神经网络
图卷积神经网络的（单层）最终形式：
其中， 第 l 层网络的输入为 $H^{(l)}\in\mathbb{R}^{N\times D} $（初始输入为 $H^{(0)}=X$ ）， N 为图中的节点数量，每个节点使用 D 维的特征向量进行表示。$ \tilde{A}=A+I_{N}$ 为添加了自连接的邻接矩阵，$ \tilde{D} $为度矩阵，$\tilde{D}{ii}=\Sigma{j}\tilde{A}_{ij} $。 $W^{(l)}\in \mathbb{R}^{D\times D} $为待训练的参数。 $\sigma $为相应的激活函数，例如 $ReLU(·)=max(0,·)$.
model
半监督节点分类问题
依靠已标注的节点来对那些没有标注过的节点进行分类，在这类问题中，由于大部分节点都没有已标注的标签，因此往往需要使用某种形式的图正则项对标签信息进行平滑（例如在损失函数中引入图拉普拉斯正则（graph Laplacian regularization）
其中，$ \mathcal{L}_{0} $表示有监督的损失， $f(·) $可以是一个类似于神经网络的可微函数。 $\lambda$ 表示一个权值因子， X 则是相应的节点向量表示。$ \Delta=D-A $表示未归一化的图拉普拉斯矩阵。这种处理方式的一个基本假设是：相连的节点可能有相同的标签。然而，这种假设却往往会限制模型的表示能力，因为图中的边不仅仅可以用于编码节点相似度，而且还包含有额外的信息。
GCN处理方法
GCN通过一个简单的映射函数$ f(X,A)$ ，可以将节点的局部信息汇聚到该节点中，然后仅使用那些有标注的节点计算 $\mathcal{L}_{0}$即可，从而无需使用图拉普拉斯正则。 使用了一个两层的GCN进行节点分类。模型结构图如下图所示：
具体流程
其具体流程为：
- 首先获取节点的特征表示 X 并计算邻接矩阵 $\hat{A}=\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}$ 。
-
将其输入到一个两层的GCN网络中，得到每个标签的预测结果：
其中， $W^{(0)}\in\mathbb{R}^{C\times H}$ 为第一层的权值矩阵，用于将节点的特征表示映射为相应的隐层状态。 $W^{(1)}\in\mathbb{R}^{H\times F}$ 为第二层的权值矩阵，用于将节点的隐层表示映射为相应的输出（ F 对应节点标签的数量）。 最后将每个节点的表示通过一个softmax函数，即可得到每个标签的预测结果。 - 对于半监督分类问题，使用所有有标签节点上的期望交叉熵作为损失函数：
其中，$ \mathcal{Y}_{L} $表示有标签的节点集。
referrence
https://zhuanlan.zhihu.com/p/31067515