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

缺乏、安全感 2023-01-01 11:47 379阅读 0赞

### GNN（图神经网络） ###

*  图卷积的谱方法
 *   *  图（Graph）
     *  图拉普拉斯矩阵（Graph Laplacian）
     *  正则化的图拉普拉斯矩阵（Normalized graph Laplacian）
     *  图傅里叶基（Fourier basis of graph  G G G）
     *  图傅里叶变换（Graph Fourier transform）
     *  谱域的卷积定理（Convolution theorem）
     *  谱域的图卷（Spectral Graph CNN）
     *  切比雪夫多项式近似图卷积核（ChebyNet）
     *  图小波神经网络（Graph wavelet neural network-GWNN）
 *  图卷积的空间方法
 *   *  初步的图重构的方法
     *  GraphSAGE
     *  Graph Convolution Network-GCN
     *  Graph Attention Network-GAT
     *  普通的空间方法框架-MoNet
 *  图卷积谱方法和空间方法的关系
 *   *  谱方法是空间方法的特例
     *  图的卷积核
     *  改进切比雪夫方法
     *  方法对比
 *  图池化（Graph Pooling）
 *   *  图粗化（Graph coarsening）
     *  节点选择（Node selection）

> [拉普拉斯矩阵示例][Link 1]  
> [视频地址][Link 2]

# 图卷积的谱方法 #

## 图（Graph） ##

G = ( V , E , W ) \\boldsymbol\{G = (V,E,W)\} G=(V,E,W)

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

## 图拉普拉斯矩阵（Graph Laplacian） ##

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

*   D − 度 矩 阵 ， D i i = ∑ j W i j \\boldsymbol\{D-度矩阵，\\boldsymbol\{D\}\_\{i i\}=\\sum\_\{j\} \\boldsymbol\{W\}\_\{i j\}\} D−度矩阵，Dii=∑jWij
 *   W − 权 值 矩 阵 \\boldsymbol\{W-权值矩阵\} W−权值矩阵

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

L = I − D − 1 2 W D − 1 2 \\boldsymbol\{L\}=\\boldsymbol\{I\}-\\boldsymbol\{D\}^\{-\\frac\{1\}\{2\}\} \\boldsymbol\{W\} \\boldsymbol\{D\}^\{-\\frac\{1\}\{2\}\} L=I−D−21WD−21  
 I \\boldsymbol\{I\} I为单位矩阵， L \\boldsymbol\{L\} 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)10 if i=j and deg(vi)=0 if i=j and vi is adjacent to vj otherwise.

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

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

*   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可对角化： L = U Λ U T  where  U = \[ u 1 , ⋯   , u n \] ,  and  Λ = diag ⁡ ( \[ λ 1 , ⋯   , λ n \] ) \\boldsymbol\{ \\begin\{array\}\{c\} L=U \\Lambda U^\{T\} \\\\ \\text \{ where \} U=\\left\[\\boldsymbol\{u\}\_\{1\}, \\cdots, \\boldsymbol\{u\}\_\{n\}\\right\], \\text \{ and \} \\Lambda=\\operatorname\{diag\}\\left(\\left\[\\lambda\_\{1\}, \\cdots, \\lambda\_\{n\}\\right\]\\right) \\end\{array\}\} L=UΛUT where U=\[u1,⋯,un\], and Λ=diag(\[λ1,⋯,λn\])

## 图傅里叶变换（Graph Fourier transform） ##

图傅里叶变换：  
 x ^ = U T x \\widehat\{\\boldsymbol\{x\}\}=\\boldsymbol\{U\}^\{T\} \\boldsymbol\{x\} x=UTx  
图傅里叶逆变换：  
 x = U x ^ \\boldsymbol\{x\}=\\boldsymbol\{U\} \\widehat\{\\boldsymbol\{x\}\} x=Ux

## 谱域的卷积定理（Convolution theorem） ##

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

x ∗ G y = U ( ( U T x ) ⊙ ( U T y ) ) \\boldsymbol\{x \*\_\{G\} y=U\\left(\\left(\\boldsymbol\{U\}^\{T\} \\boldsymbol\{x\}\\right) \\odot\\left(\\boldsymbol\{U\}^\{T\} y\\right)\\right)\} x∗Gy=U((UTx)⊙(UTy))

*   U T y − 在 谱 域 上 的 卷 积 核 \\boldsymbol\{U^\{T\} y-在谱域上的卷积核\} UTy−在谱域上的卷积核

所以可进一步表示为：  
 x ∗ G y = U g θ U T x \\boldsymbol\{x\} \*\_\{\\boldsymbol\{G\}\} \\boldsymbol\{y\}=\\boldsymbol\{U\} \\boldsymbol\{g\}\_\{\\theta\} \\boldsymbol\{U\}^\{\\boldsymbol\{T\}\} \\boldsymbol\{x\} x∗Gy=UgθUTx  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70]

## 谱域的图卷（Spectral Graph CNN） ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 1]  
h-非线性变换。

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 3]

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 7]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 8]

# 图卷积的空间方法 #

## 初步的图重构的方法 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 9]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 10]

## GraphSAGE ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 11]

## Graph Convolution Network-GCN ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 12]

## Graph Attention Network-GAT ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 13]

## 普通的空间方法框架-MoNet ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 14]

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

## 谱方法是空间方法的特例 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 15]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 16]

## 图的卷积核 ##

信号变换的过程  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 17]

## 改进切比雪夫方法 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 18]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 19]

## 方法对比 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 20]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 21]

# 图池化（Graph Pooling） #

## 图粗化（Graph coarsening） ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 22]

## 节点选择（Node selection） ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 23]

[Link 1]: https://blog.csdn.net/qq_30159015/article/details/83271065
[Link 2]: https://www.bilibili.com/video/BV1ta4y1t7EK
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70]: /images/20221120/6a34e987650847ec93b4cac0efe14622.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 1]: /images/20221120/c4b9ea48b52845c3bb566df853f851d4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 2]: /images/20221120/bed6bae0ba8c4050aba7ebd63207f19d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 3]: /images/20221120/a1c8cb1197554171a6cc1108dddd82fb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 4]: /images/20221120/19e71b8628c946a7a43c81907d0954ca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 5]: /images/20221120/d0555a68dfc3475bbeab5ec108da8cf3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 6]: /images/20221120/ce6b6d8ab4a94aa58f2fa337970c1321.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 7]: /images/20221120/6985e45a8d4e42ae9f93ac94819fbe75.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 8]: /images/20221120/09dea7ade8314456a4a868f01a97fb9f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 9]: /images/20221120/0c5166919e684682a6b4d8069f3d808d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 10]: /images/20221120/eb2ca926b129444bb4b5d06f0953e017.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 11]: /images/20221120/1f4c12e0f8dd4f8eb1a83057386e9b95.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 12]: /images/20221120/6ed028b995494cb298a40e14969d8fb1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 13]: /images/20221120/cc9243eb5c554c61bdbb4eae984d425d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 14]: /images/20221120/6214e868913b48f4ba45830d537978b7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 15]: /images/20221120/8d4bde695d6540dbb3b54cd2f127ca7b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 16]: /images/20221120/f67cbbbdeab74047a8df9ad06c9ad7e5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 17]: /images/20221120/5f5502d603e246a0a6d33ed68b6be5c6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 18]: /images/20221120/30e18da06632477d8672b5699476d003.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 19]: /images/20221120/28760817facc4117b377f65ec37b4cd3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 20]: /images/20221120/9c7158313a364806939cc5fee288da26.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 21]: /images/20221120/b5b4c8e5bc1f4c20960b55b55ffd74d9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 22]: /images/20221120/4eb403df363940b89a8ceef2de7ab53e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI1NjAxMzQ1_size_16_color_FFFFFF_t_70 23]: /images/20221120/a1535f74e51848f494c5187d5daeecfb.png