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

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）切比雪夫近似

2、Can Abnormality be Detected by Graph Neural Networks?

文中认为GNN会平滑节点之间的特征，正常节点的特征平缓（低频），而异常节点特征陡峭（高频），GNN平滑节点之间信息之后，会降低异常节点的信息表达。

因此提出使用不同频次的滤波器，抽取特征，再通过attention机制做信息融合，更好地表达异常节点的特征，效果提升明显，达到新的 sota 效果。

疑问：

1）GNN只能提取低频特征：暂时来看，是低频特征的传播比较有效，从而反证GNN只提取了低频特征。

2）高低频特征怎么理解：

图上的一组信号，可以被表示为图拉普拉斯矩阵特征向量的一组线性组合。

特征向量对应的特征值越大，该特征向量越“振荡”，反之越平滑。

而对于对图特征x，其在高频特征向量上的分量越大，可以说该特征具有更多高频的特征，反之亦然。

3、Revisiting Graph Neural Networks: All We Have is Low-Pass Filters

对结果有效(能提升节点分类效果)的都是低频滤波器。 验证：不断添加频率分量，重新构建特征，添加到一定比例时，效果开始下降。

参考

博客

欧拉公式

离散傅立叶变化：进行傅立叶变换和逆变换，时间复杂度 $O(N^2)$

快速傅立叶变换：降低复杂度到 $O(Nlog(N))$