图卷积网络

图卷积网络 (Graph convolutional net, GCN) 能够聚合图中的单跳或多跳邻域信息，更好学习到图结构。或者说调节图上的平滑度。

前置知识：

核心要素：标准化图拉普拉斯矩阵：Lnorm =I− D−1/2AD−1/2 其中A是邻接矩阵，D是对角度或者强度矩阵。Lnorm有n（A的节点数）个正交的特征向量，并且特征值全非负。L = U ΛU T，其中U是特征向量矩阵，Λ是对角特征值矩阵。假设有一个反映图上每个节点的特征的向量x，可以通过下面的公式反映图上的平滑度：

其中a和b代表不同节点。Aa,b就是连接a和b之间的连接强度，而da或db就是a或者b节点的强度。可以发现当存在连接的两个节点特征值越接近，图上越平滑，这个值xTLx越小。

如果L不是标准化，而是原始的图拉普拉斯矩阵L = D-A， 括号内的根号d就直接舍弃，不再归一化节点度的影响。归一化的话，高度节点的变化对于xTLx的影响就减小。

而特征值和特征向量的关系又可以写成下面的关系：

也就是说，特征值越小的特征向量代表了图上的低频成分，也就是最平滑的成分。因此图拉普拉斯矩阵的特征向量就适合作为图傅里叶变换的正交基。

图傅里叶变换：

x尖的每个元素就是图上不同的频率成分的幅值

然后图逆傅里叶变换如下：

可以通过一个滤波器来控制高频和低频成分

其中是哈达玛积。

UTf是卷积核，通过控制图在频域上的表示，来实现滤波。滤波之后再图傅里叶逆变换回去。

图卷积网络的发展：

1.Spectral CNN

把UTf换成gθ，就是以θn为对角元素的对角矩阵。

uiuiT就是一个过滤器，只提取出x的ui对应的频率成分，然后θ就是抑制还是增强这个频率成分。

优点：非常直观

缺点：要学习的参数比较多（有多少个节点就要学习多少个θ参数）

2.ChebyNet

把gθ换成下面的多项式展开：

然后卷积过程：

L的指数越大，整合的跳数越多，越能整合图上的信息。（似乎是让图更平滑了）

最简单的GCN就是这ChebyNet的一阶近似。K = 2，且 α = α0 = -α1。α就是对这个图卷积后的特征进行增强或者抑制。

为了整合节点对自己的影响，Li 等人 (2019)在设计单层GCN时，会给A加上I，然后再构建标准化图拉普拉斯矩阵。

问题：λ越大对应的频率成分越高，而如果跳数越多，K越大，则实际上会方法高频成分（K对于大λ的增大作用强于小λ）

3.热核扩散

用于抑制高频成分而放大低频成分。

热核：

卷积核改为如下：

其中

将卷积公式展开：

好处：可以抑制高频成分，因为λ越大，代入到e^(-sλ)之后得到越小的值。

取K = 2，热核卷积简化为如下公式：

s越大，节点信息在图上扩散的时间越久，越能整合更多节点的信息。落到下面的图就是圆圈越大。

参考文献：Graph Convolutional Networks using Heat Kernel for Semi-supervised Learning