图神经网络（GNN）代表了一类弱小的深度神经网络架构。在一个日益互联的世界里，因为信息的联通性，大部分的信息能够被建模为图。例如，化合物中的原子是节点，它们之间的键是边。
图神经网络的美好之处在于它们可能在不就义重要细节的状况下间接对图构造数据进行操作。这一点在解决简单的数据集（如化合物）时尤为显著，GNN 使咱们可能充分利用底层图形示意的丰富性。通过这样做，GNN 可能更全面地了解原子和键之间的关系，从而为更精确和深刻的剖析开拓路径。
在化学畛域之外，图构造的影响延长到不同的畛域。以交通数据为例，其中城市是节点，它们之间的路线是边。GNN 在交通堵塞预测等工作中被证实是十分贵重的，证实了它们在捕获城市流动性的简单动静方面是无效的。当面临预测交通拥堵等挑战时，GNN 把握图数据中固有的空间依赖性和模式的能力成为一种强有力的工具。基于 GNN 的泛滥模型已成为预测交通拥堵的最先进解决方案，成为最前沿的模型。上面是 paperswithcode 上预测交通堵塞的模型，基本上全副是 GNN
本文将介绍图卷积的实践根底。通过深入研究图傅立叶变换的复杂性及其与图卷积的分割，咱们将为深刻了解 GNN 世界中的这一要害概念奠定根底。
如何定义图卷积
GNN 的外围概念在于图卷积，通过捕捉节点和边之间的关系，实现对图数据的无效解决。
在了解图卷积的各种办法中，本文侧重于利用图傅里叶变换的实践来进行解释。这个概念提供了一个深入研究图卷积的机制的独特视角。
图傅里叶变换容许咱们用图形频率来示意图形信号——与节点相干的数据。这种以光谱分析为根底的合成，提供了对图中潜在模式和构造的洞察。
一些 GNN 架构利用注意力机制和其余超过图卷积范畴的高级办法。然而咱们次要探讨图卷积的实质及其与图傅立叶变换的相互作用，所以注意力等局部不在本文的范畴内
什么是图傅里叶变换?
图傅里叶变换的概念与经典的傅里叶变换有着乏味的相似之处。就像传统的傅里叶变换将一个波信号分解成它的组成频率一样，图傅里叶变换在图构造数据进行操作，揭示嵌入其中的信号的频率。
设想一个没有环路或多个边缘构造的加权无向图。图傅里叶变换是一种数学运算，它强调了图上存在的信号的变换。在信号维数等于 1 的状况下，这个概念变得特地具备说明性。思考上面的形容，它描述了信号在图表上的样子[1]。
将信号合成为图的频率，或图傅里叶变换，提供了一种辨认图形数据中固有的各种关系、法则和复杂性的办法。
图拉普拉斯算子
为了了解图的傅里叶变换，咱们将开始一个根本的摸索，首先介绍图的拉普拉斯变换。这个要害概念是揭示图形固有频率个性的基石。
图拉普拉斯量记为 L，定义为:
在这个等式中，A 示意邻接矩阵，它编码了图中节点之间的连贯，D 示意度矩阵，捕捉每个节点的度。
因为 D 和 A 是实对称矩阵，因而图拉普拉斯矩阵也具备实对称矩阵的性质。这个性质使咱们可能对图拉普拉斯函数进行谱合成，示意为:
上式中，U 示意特征向量矩阵，Λ 是由特征值 (Λ 1，Λ 2，…，Λ n) 组成的对角矩阵。
二次形
本节解释了拉普拉斯图的二次形和二次形的含意，以及它如何与图信号的频率分割起来。
图拉普拉斯的二次型能够定义为:
这里的 f 示意图信号，w 示意一条边的权值，Nk 示意与节点 k 相连的节点集。
这个示意模式揭示了两个根本的要害方面:
函数的平滑性
二次型提供了对函数在图形上的平滑性的洞察。思考 f =[1,1,1，…，1]T 的场景。依据图拉普拉斯式的定义，二次型的计算结果为零。也就是说，函数在节点间越平滑，失去的二次型就越小。这种相互作用提供了一种机制来量化图形信号固有的平滑水平。
相邻节点之间的相似性
二次型也用作评估相邻节点上信号之间相似性的度量。当 f(i)与 f(j)相差较大时，对应的二次型值成比例增大。相同，如果相邻节点上的信号类似，则二次型趋近于零。这种察看后果与二次型值越大反映相邻节点之间变动越大的想法是统一的。
有了这些概念，二次型就能够被解释为图形上函数“频率”的替代物。通过利用它提供信息，咱们能够进行基于频率成分的图形信号合成。这一关键步骤是图傅里叶变换的先驱，解锁了一种弱小的办法来揭示嵌入在图构造数据中的频率特色。
图傅里叶变换
咱们曾经建设了拉普拉斯图的二次形作为信号频率的指示器，其中二次形值越大示意频率越高。还有一个要点是：要留神这些值可能受到 f 的范数的影响。为了确保一致性并打消不同范数的潜在影响，咱们还须要施加 f 的范数等于 1 的束缚。
为了失去范数条件下二次型的安稳值，咱们利用了拉格朗日乘子法这一弱小的优化技术。对该问题进行适当的变换，最终失去一个特征值问题:
这个特征值提供了一个关系:L 的每个特征值反映了图拉普拉斯的二次形的值。简略地说，这些特征值捕捉了图形信号振动的频率。
这样咱们对特征值作为函数频率的指标有了根本的了解。特征向量和图拉普拉斯之间的分割成为进行图傅立叶变换的路径——一个系统地揭示图信号外在频率元素的过程。
当初，咱们能够看看傅里叶变换的定义了
从图傅里叶变换到图卷积
下面介绍的图傅里叶变换，咱们取得了一个无效剖析和解决图信号的弱小工具。在咱们钻研图傅里叶变换和图卷积之间的分割。
这种分割的外围是卷积定理，这个原理建设了傅里叶域中卷积运算和元素积之间的分割。
卷积运算相似于傅里叶域中变换后的信号的逐元乘法。利用卷积定理能够推导图卷积的一个间接定义:
- 对图形信号进行傅里叶变换。
- 将变换后的信号与一个可学习的权重向量相乘。
- 对元素积进行傅里叶反变换，失去图卷积的输入。
图卷积的公式当初能够表述如下:
为了使这个定义更加精简，咱们引入了一个实用的参数化。因为与 U f 的元素积能够示意为与 diag(Uf)的积，s 所以设可学习权值 θ 为:
通过利用这种参数化，gθ 的图卷积公式采纳了一种简化和直观的模式:
看看，咱们曾经从图的傅里叶变换中定义了一个图卷积!
总结
在本文中，咱们从揭示图拉普拉斯的基本原理开始，而后深入研究了图卷积的基本概念，这是图傅里叶变换的推导。
本文中所做的推到应该可能加深了你对图卷积实质的了解。咱们后续还会对图的消息传递机制进行更具体介绍，因为它能够聚合邻接节点信息，这是图卷积胜利的要害。
援用：
[1] D. I. Shuman et al.,“The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains”, IEEE Signal Processing Magazine, 30(3):83–98, 2013
https://avoid.overfit.cn/post/dbcee95a7b8444e8b5f0e0925ec66332
作者：Lalf