【GCN】图卷积网络初探——基于图（Graph）的傅里叶变换和卷积

小鱼儿 2023-06-04 02:50 39阅读 0赞

# 【GCN】图卷积网络初探——基于图（Graph）的傅里叶变换和卷积 #

2018年11月29日 11:50:38 [夏至夏至520][520] 阅读数 5980更多

分类专栏： [\# MachineLearning][MachineLearning]

本文链接： [https://blog.csdn.net/qq\_41727666/article/details/84622965][https_blog.csdn.net_qq_41727666_article_details_84622965]

*  本文为[从CNN到GCN的联系与区别——GCN从入门到精（fang）通（qi）][CNN_GCN_GCN_fang_qi]的阅读笔记，文中绝大部分公式和图片摘自原文。  
    
    
    ### 文章目录 ###
    
     *  [一、CNN（卷积神经网络）中的离散卷积][CNN]
     *  [二、GCN基本概念介绍][GCN]
        
         *  [（一）图Graph][Graph]
         *  [（二）研究GCN的原因][GCN 1]
         *  [（三）提取【拓扑图】空间特征的两种方式][Link 1]
     *  [三、图的拉普拉斯矩阵][Link 2]
        
         *  [（一）定义：拉普拉斯矩阵L][L]
         *  [（二）拉普拉斯矩阵L的良好性质][L 1]
         *  [（三）拉普拉斯矩阵L的谱分解（特征分解）][L 2]
     *  [四、Graph上的傅里叶变换与卷积][Graph 1]
        
         *  [（一）核心工作][Link 3]
         *  [（二）Graph上的傅里叶变换][Graph 2]
         *  [（三）Graph上的卷积][Graph 3]
     *  [五、深度学习中的GCN][GCN 2]

--------------------

# 一、CNN（卷积神经网络）中的离散卷积 #

推荐阅读：[如何通俗易懂地解释卷积？][Link 4]

1、CNN中的离散卷积：共享参数的过滤器

2、CNN中的卷积操作：通过计算中心像素点以及相邻像素点的【加权和】构成【feature map】;  
加权系数=卷积核的权重系数

【实例】下式是一个隐藏神经元的输出计算公式，b为偏置，w为5×5的权重向量，a为上一层的激活值，σ()为激活函数。  
可以看出，将上一层的5×5=25的神经元（a）加权（w）求和  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzI3NjY2_size_16_color_FFFFFF_t_70]

3、CNN中的卷积目的：空间特征的提取

4、确定卷积核的系数：随机化初值，训练中根据误差函数loss，通过反向传播+梯度下降进行迭代优化。

# 二、GCN基本概念介绍 #

## （一）图Graph ##

定义：顶点和边建立的关系拓扑图

## （二）研究GCN的原因 ##

1、CNN的【平移不变性】在【非矩阵结构】数据上不适用

2、希望在【拓扑图】上提取空间特征来进行机器学习

3、GCN主要工作：引入可以优化的【卷积参数】

## （三）提取【拓扑图】空间特征的两种方式 ##

1、vertex domain(spatial domain)：顶点域（空间域）

操作：把每个顶点相邻的neighbors找出来

缺点：每个顶点的neighbors不同，计算处理必须针对每个节点

2、spectral domain：谱域

过程：

（1）定义graph上的Fourier Transformation傅里叶变换

（利用Spectral graph theory，借助图的拉普拉斯矩阵的特征值和特征向量研究图的性质）

（2）定义graph上的convolution卷积

# 三、图的拉普拉斯矩阵 #

## （一）定义：拉普拉斯矩阵L ##

L=D−AL=D-AL=D−A  
其中，L为Laplacian矩阵；  
      D是顶点的度矩阵（对角矩阵），对角线上的元素依次为各个顶点的度（与该顶点相连的边的条数）；  
      A是图的邻接矩阵。

计算方法实例：  
![在这里插入图片描述][20181129101903921.jpg]

## （二）拉普拉斯矩阵L的良好性质 ##

1、是对称矩阵，可以进行谱分解（[特征分解][Link 5]），与GCN的spectral domain对应

2、只在【中心节点】和【一阶相连的顶点】这两种位置上有非0元素，其余位置都是0  
注：一阶相连就是通过一条边直接相连，如上图中与顶点1一阶相连的顶点为5和2；  
二阶相连就是通过两条边相连，如上图中与顶点1二阶相连的顶点为4（1-5-4）、2（1-5-2）、5（1-2-5）、3（1-2-3）

3、可以通过拉普拉斯算子与拉普拉斯矩阵进行类比

## （三）拉普拉斯矩阵L的谱分解（特征分解） ##

1、矩阵L的特征分解定义：将矩阵L分解为由特征值λ和特征向量u表示的矩阵之积

（1）求特征值和特征向量：λ为特征值，u为特征向量，则满足下式：  
Lu=λuLu=\\lambda uLu=λu

（2）求特征分解：

令 L是一个 N×N 的方阵，且有 N 个线性无关的特征向量 。  
这样， L可以被分解为：  
L=UΛU−1=U⎛⎝⎜λ1...λ3⎞⎠⎟U−1L=U\\Lambda U^\{-1\} =U\\begin\{pmatrix\}\\lambda\_1& & \\\\ &...& \\\\ & & \\lambda\_3 \\end\{pmatrix\} U^\{-1\}L=UΛU−1=U⎝⎛λ1...λ3⎠⎞U−1  
其中，U是N×N方阵，且其第i列为L的特征向量ui，ui为列向量；  
U=(u1⃗ ,u2⃗ ,...,un⃗ )U=(\\vec\{u\_1\},\\vec\{u\_2\},...,\\vec\{u\_n\})U=(u1,u2

转载于:https://www.cnblogs.com/think90/p/11508851.html

[520]: https://me.csdn.net/qq_41727666
[MachineLearning]: https://blog.csdn.net/qq_41727666/article/category/8288771
[CC 4.0 BY-SA]: http://creativecommons.org/licenses/by-sa/4.0/
[https_blog.csdn.net_qq_41727666_article_details_84622965]: https://blog.csdn.net/qq_41727666/article/details/84622965
[CNN_GCN_GCN_fang_qi]: https://www.zhihu.com/question/54504471/answer/332657604
[CNN]: https://blog.csdn.net/qq_41727666/article/details/84622965#CNN_3
[GCN]: https://blog.csdn.net/qq_41727666/article/details/84622965#GCN_20
[Graph]: https://blog.csdn.net/qq_41727666/article/details/84622965#Graph_22
[GCN 1]: https://blog.csdn.net/qq_41727666/article/details/84622965#GCN_26
[Link 1]: https://blog.csdn.net/qq_41727666/article/details/84622965#_34
[Link 2]: https://blog.csdn.net/qq_41727666/article/details/84622965#_52
[L]: https://blog.csdn.net/qq_41727666/article/details/84622965#L_54
[L 1]: https://blog.csdn.net/qq_41727666/article/details/84622965#L_64
[L 2]: https://blog.csdn.net/qq_41727666/article/details/84622965#L_74
[Graph 1]: https://blog.csdn.net/qq_41727666/article/details/84622965#Graph_98
[Link 3]: https://blog.csdn.net/qq_41727666/article/details/84622965#_100
[Graph 2]: https://blog.csdn.net/qq_41727666/article/details/84622965#Graph_106
[Graph 3]: https://blog.csdn.net/qq_41727666/article/details/84622965#Graph_127
[GCN 2]: https://blog.csdn.net/qq_41727666/article/details/84622965#GCN_143
[Link 4]: https://www.zhihu.com/question/22298352
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzI3NjY2_size_16_color_FFFFFF_t_70]: /images/20230601/86a7c585735e4b57b8fca6e524042f0e.png
[20181129101903921.jpg]: /images/20230601/3f2de5e92bf64e79aca7fb1b752aaa45.png
[Link 5]: https://baike.baidu.com/item/%E7%89%B9%E5%BE%81%E5%88%86%E8%A7%A3/12522621?fr=aladdin