图神经网络入门（GNN）

顾名思义，就是把神经网络应用到图结构上

1、Semi-supervised Classification with Graph Convolutional Networks

图卷积的广义理解：

1）卷积：两个函数的一种运算，输入两个函数，加入时间变量做累计，输出一个新函数。

2）考虑CNN（卷积神经网络）怎么做的：函数看做矩阵，输入原始图像和卷积核（两个函数），拿卷积核遍历原始图像，做计算（点乘、求和），生成新矩阵（输出新函数）。

3）图卷积：图卷积最基本的问题是，输入”原始图像”形状并不固定，不同节点的邻居节点数量不同，怎么办？利用邻接矩阵，每个节点信息都输入，把不连接的节点信息置为0就好了。加大复杂度来让这个问题可解。

图卷积过程：

1）通过图的邻接矩阵获得拉普拉斯矩阵

2）拉普拉斯矩阵分解，特征向量作为正交基，作为傅立叶变换的基

3）利用正交基进行傅立叶变换，乘积之后求逆变换，得到两个函数的卷积

卷积的一个输入为原始图结构，另一个是卷积核，作为参数训练。

基础概念：

1）傅立叶变换

每个函数由多个周期性函数组合而成，每个周期函数可以看做正交基为 $1,sin(x),cos(x),sin(2x),cos(2x)…sin(nx),cos(ns)$的组合，这些函数互相垂直（相互的乘积积分为0），根据欧拉公式，正交基变成 $e^{wnx}$，其中w标识周期函数的频率。傅立叶变换是指将一个函数拆解为多个三角函数的和，每个三角函数用频率和振幅描述，即将函数从时域（时间为横轴，信号大小为纵轴）变到频域（频率为横轴，振幅为纵轴）。

2）卷积定义和傅立叶变换

两函数傅立叶变换之后的乘积，等于卷积之后的傅立叶变化，那么两函数的卷积，就等于，各自傅立叶变换后乘积的逆傅立叶变换。

3）拉普拉斯算子

目的：在图上找到一组正交基，结合傅立叶变换做卷积。

传统拉普拉斯算子，是欧式空间中的二阶微分：$\triangledown f=f(x-1,y)+f(x+1,y)+f(x,y-1)+f(x,y+1)-4*f(x,y)$

图结构利用邻接矩阵就能求出对应的拉普拉斯矩阵，进行矩阵分解，得到的特征向量可以看作傅立叶变换的基，从而完成图上的傅立叶变换。

图上的拉普拉斯矩阵：$L=D-A$，$D$ 表示顶点度矩阵，$A$ 表示邻接矩阵。

拉普拉斯矩阵是实对称矩阵 -> 能对角化 -> 找到正交基

图卷积优化

1）矩阵分解复杂度太多，用特征值的多项式代替卷积核，就不需要做矩阵分解了。

2）切比雪夫近似