【论文知识点笔记】GNN概述（图神经网络概述）_graph wavelet neural network

拉普拉斯矩阵示例
视频地址

图卷积的谱方法

图（Graph）

$$\mathbf{G}=(\mathbf{V},\mathbf{E},\mathbf{W})$$

• $\mathbf{V}-节点的集合$
• $\mathbf{E}-边的集合$
• $\mathbf{W}-权重的集合,\mathbf{W}\in {\mathbf{R}}^{\mathbf{n}\times \mathbf{n}}$
• $\mathbf{X}-节点的特征矩阵,\mathbf{X}\in {\mathbf{R}}^{\mathbf{n}\times \mathbf{d}}$
  每个节点都有d维的特征，X为节点的特征矩阵，X的每一列可以看作定义在n个节点的图上的信号。（信号处理）

图拉普拉斯矩阵（Graph Laplacian）

定义了图上的导数，刻画了信号在图上的平滑程度。
$$\mathbf{L}=\mathbf{D}-\mathbf{W}$$

• $\mathbf{D}-度矩阵，{\mathbf{D}}_{\mathbf{i}\mathbf{i}}={\sum }_{\mathbf{j}}{\mathbf{W}}_{\mathbf{i}\mathbf{j}}$
• $\mathbf{W}-权值矩阵$

正则化的图拉普拉斯矩阵（Normalized graph Laplacian）

$$\mathbf{L}=\mathbf{I}-{\mathbf{D}}^{-\frac{1}{2}}\mathbf{W}{\mathbf{D}}^{-\frac{1}{2}}$$
$\mathbf{I}$为单位矩阵，$\mathbf{L}$的每个元素如下：
L i , j : = { 1  if  i = j  and  deg ⁡ ( v i ) ≠ 0 − 1 deg ⁡ ( v i ) deg ⁡ ( v j )  if  i ≠ j  and  v i  is adjacent to  v j 0  otherwise.  \boldsymbol{L_{i, j}:=\left\{

$$\begin{array}{ll} 1 & \text { if } i=j \text { and } \operatorname{deg}\left(v_{i}\right) \neq 0 \\ -\frac{1}{\sqrt{\operatorname{deg}\left(v_{i}\right) \operatorname{deg}\left(v_{j}\right)}} & \text { if } i \neq j \text { and } v_{i} \text { is adjacent to } v_{j} \\ 0 & \text { otherwise. } \end{array}$$ \right.} Li,j​:=⎩⎪⎨⎪⎧​1−deg(vi​)deg(vj​) ​1​0​ if i=j and deg(vi​)​=0 if i​=j and vi​ is adjacent to vj​ otherwise. ​

图傅里叶基（Fourier basis of graph $G$）

假如图上有n个节点，每个节点有一个取值，图上的一个信号就是一个n维度的向量，我们需要把这个n维度的向量变换到新的域里边去，那就需要一组基，这组基呢就是拉普拉斯矩阵的n个特征向量。它的n个特征向量就构成了一个n维空间，且n个特征向量正交的，这是由拉普拉斯矩阵性质决定的。我们所需要做的就是把这信号x投影在这n个基上，就相当于$x在u_1的投影=x\cdot u_1$，x在新的这组基下的投影$\hat{\mathbf{x}}={\mathbf{U}}^T\mathbf{x}$，$\hat{\mathbf{x}}$就是这个原始信号在谱域的表达。如何转换回，需要对其进行逆变换$x=U\hat{x}$。

• U = { u l } l = 1 n − L 的 正 交 特 征 向 量 的 集 合 U=\boldsymbol{\left\{\boldsymbol{u}_{l}\right\}_{l=1}^{n}-L的正交特征向量的集合} U={ul​}l=1n​−L的正交特征向量的集合
• { λ l } l = 1 n − L 的 非 负 特 征 值 的 集 合 \boldsymbol{\left\{\boldsymbol{\lambda}_{l}\right\}_{l=1}^{n}-L的非负特征值的集合} {λl​}l=1n​−L的非负特征值的集合
• 图拉普拉斯L可对角化：$$\begin{array}{c}L=U\Lambda U^T\\ \text{ where }U=\left[{\mathbf{u}}_1,\cdots ,{\mathbf{u}}_n\right],\text{ and }\Lambda =\mathrm{diag}\left(\left[{\lambda }_1,\cdots ,{\lambda }_n\right]\right)\end{array}$$

图傅里叶变换（Graph Fourier transform）

图傅里叶变换：
$$\hat{\mathbf{x}}={\mathbf{U}}^T\mathbf{x}$$
图傅里叶逆变换：
$$\mathbf{x}=\mathbf{U}\hat{\mathbf{x}}$$

谱域的卷积定理（Convolution theorem）

两个信号的卷积，可以看成他们傅里叶变换后的点积。
根据卷积定理，给定一个x作为输入，y作为卷积核，图卷积${\ast }_G$可表示为
【对整体进行傅里叶逆变换（（对x进行傅里叶变换）点乘（对y进行傅里叶变换））】

$$\mathbf{x}{\ast }_{\mathbf{G}}\mathbf{y}=\mathbf{U}\left(\left({\mathbf{U}}^{\mathbf{T}}\mathbf{x}\right)\odot \left({\mathbf{U}}^{\mathbf{T}}\mathbf{y}\right)\right)$$

• ${\mathbf{U}}^{\mathbf{T}}\mathbf{y}-在谱域上的卷积核$

所以可进一步表示为：
$$\mathbf{x}{\ast }_{\mathbf{G}}\mathbf{y}=\mathbf{U}{\mathbf{g}}_{\theta }{\mathbf{U}}^{\mathbf{T}}\mathbf{x}$$

谱域的图卷（Spectral Graph CNN）

h-非线性变换。

切比雪夫多项式近似图卷积核（ChebyNet）

图小波神经网络（Graph wavelet neural network-GWNN）

图卷积的空间方法

初步的图重构的方法

GraphSAGE

Graph Convolution Network-GCN

Graph Attention Network-GAT

普通的空间方法框架-MoNet

图卷积谱方法和空间方法的关系

谱方法是空间方法的特例

图的卷积核

信号变换的过程

改进切比雪夫方法

方法对比

图池化（Graph Pooling）

图粗化（Graph coarsening）

节点选择（Node selection）