【强基固本】图神经网络的理论基础

“强基固本，行稳致远”，科学研究离不开理论基础，人工智能学科更是需要数学、物理、神经科学等基础学科提供有力支撑，为了紧扣时代脉搏，我们推出“强基固本”专栏，讲解AI领域的基础知识，为你的科研学习提供助力，夯实理论基础，提升原始创新能力，敬请关注。

来源：知乎—小皇帝

地址：https://zhuanlan.zhihu.com/p/434055715

内容依据：青源Talk第七期-图神经网络的理论基础(中国人大，魏哲巍)

https://www.bilibili.com/video/BV1HY411x7GS

写作目的：记录一下看Talk的笔记，之前写过图神经网络谱方法和空间方法定义卷积的文章，这里换一个角度，听一下另外一个老师的讲解，再梳理一下图的相关概念，希望脑中的条理更加清晰并且有更多的收获。

01

图的基本定义

这里讨论的是无向图。

   为归一化邻接矩阵，可以看到它是一个是对称的，它里面各个地方的信息与节点的度有关系，具体的关系如图：

比如说节点1和节点2之间这条边，反映在    中对应两个点(无向图，对称)，那除以的值就是根号下边连接节点的度数开根号。

归一化拉普拉斯矩阵定义为    ：

节点特征矩阵定义为    ：

02

GNN的模型表述

注意这里：    ,    由    计算得到。这里举一个例子，想要计算下一层    这个节点的表示(节点度带自环的话都要加1)：

GCN和CNN的关系对比：

卷积神经网络是中间点及其周围点进行信息聚集工作，聚集的比例是卷积核决定的，卷积核里面的参数是可以学出来的；而GCN是节点与和它有连接关系的点进行消息聚集的，积聚的比例和节点的度有关，这个是写死的，不是可学习参数。

节点分类是给定图中一些labeled的节点，去判断其他unlabel的节点的label；链接预测是给定图中一些节点之间的连接关系，去判断其他地方是否有连接关系；社区发现是给定一个图，去发现内部连接比较紧密而外面链接比较稀疏的区域。

03

图神经网络的两个视角

1、滤波器(GNN的频域解释)

以各个地方测得的温度作为节点的信号，但是测到的信号可能含有噪声，我们希望通过图结构利用周围点的信息将噪声平滑。可以用归一化拉普拉斯矩阵对节点信息处理，使得一点的信号向与它有连接关系的节点扩散。如下图：不同的乘法扩散的方式不同。

有了图信号，我们定义图信号的傅里叶变换。因为归一化的拉普拉斯矩阵是一个实对称矩阵，一定可以进行对角化。

可以将    看作是变换下的一组正交基。

以上过程相当于图信号先做图上的傅里叶变换变到谱域，然后在谱域做滤波，然后再图逆傅里叶变换变换回原域，完成卷积操作。举一个例子：

可见，高频的噪声被滤除掉，恢复的信号和原始信号接近。

图卷积就像信号与系统中的卷积定理一样：信号在时域的卷积，等于他们各自的频域的变换，相乘后结果的逆变换。

上面介绍了图卷积的概念，接下来说说问题在哪里，谱域卷积难以实现的地方在哪里：

   是一个稠密矩阵，当n(节点数特别大的时候)，    是巨大的(    的维度是n*n)，存储不下。再者，对归一化拉普拉斯矩阵进行特征值分解复杂度过高，难以实现。那一般的解决方法是利用多项式近似滤波器。

这样的好处是，L是一个稀疏矩阵，计算是比较快的。但是切比雪夫实现起来困难，而且因为自身性质可能导致它学不到最好的一个滤波器。因此后来要简化，提出GCN。

2、随机游走(GNN的空域解释)

比如当前在0节点，那么接下来随机游走一步到其他节点的概率可由计算上面。随机游走性质很多，但我们只关注一个，就是稳态，对于大部分图，稳态就是到一定程度，再走一步概率分布不变，稳态与起始行走点无关。无向图中，随机游走稳态概率分布可以写出来(节点度除以两倍总边数)：

每多走一步，就越接近稳态。

说明k层的卷积神经网络，实际上就是k层的随机游走，k步的随机行走会收敛到稳态，那就意味着GCN叠到k后，会收敛到忘记初始状态，之和图结构有关的一个状态，做节点分类效果还会很差。

本文目的在于学术交流，并不代表本公众号赞同其观点或对其内容真实性负责，版权归原作者所有，如有侵权请告知删除。

“强基固本”历史文章

更多强基固本专栏文章，

请点击文章底部“阅读原文”查看

分享、点赞、在看，给个三连击呗！