在本章《图神经网络理论动机》中，我们将探讨图神经网络（GNN）的一些基本理论基础。GNN最引人入胜的地方在于，它们是由不同的理论观点独立发展起来的。一方面，GNN是基于图信号处理理论构建的，旨在将欧氏空间中的卷积扩展到非欧氏图领域[Bruna等人，2014]。另一方面，大多数现代GNN的核心——神经消息传递方法，是通过与图形模型中的概率推理消息传递算法的类比提出的[Dai等人，2016]。此外，还有一些工作是基于GNN与Weisfeiler-Lehman图同构测试的联系来驱动的[Hamilton等人，2017b]。这三种不同领域的理论融合成一个单一的算法框架是十分引人注目的。
每一种理论动机都带有其独特的直觉和历史，所采取的视角对模型发展有着深远的影响。之所以在介绍GNN模型之后才提及这些理论动机，是因为我们希望读者在理解了关键概念之后，能自由地探索并结合这些直觉和动机。
7.1 GNNs与图卷积
从研究兴趣和关注度来看，基于图卷积关联来推导GNN是最主要的理论范式。在这个视角下，GNN的诞生源于一个问题：如何将卷积的概念扩展到一般图结构数据上？
7.1.1 卷积与傅里叶变换
为了在图上定义卷积，我们首先需要明确我们要推广什么，并提供一些背景知识。假设我们有两个函数f和h，它们在欧氏空间中定义，卷积可以表示为两个函数的线性组合，其中每个组合项是f在h的平移版本。在连续空间中，卷积可以写作：
\[ (f \ast h)(x) = \int_{-\infty}^{\infty} f(y) h(x - y) dy \]
卷积在频域中有着深刻的解释，通过傅里叶变换，卷积在频域中转化为乘法：
\[ \mathcal{F}(f \ast h) = \mathcal{F}(f) \cdot \mathcal{F}(h) \]
傅里叶变换是一个将信号从时域转换到频域的工具，它揭示了信号的频率成分。
在图上，我们没有欧几里得空间的平移操作，因此不能直接应用上述卷积定义。然而，图谱理论提供了在图上进行类似傅里叶分析的方法。图谱理论涉及到将图上的信号表示为图谱（或特征向量）的线性组合，这与傅里叶变换中的基函数（如正弦和余弦波）类似。图的拉普拉斯矩阵（Laplacian matrix）在图谱理论中扮演着核心角色，它定义了节点间的相互作用。
图卷积操作可以被看作是在图谱域中进行的滤波过程，通过将滤波器（即权重矩阵）应用到图谱表示上，然后通过逆傅里叶变换回到图节点域。这种操作允许我们捕捉到图结构中的局部和全局信息，从而在图数据的处理中实现类似于欧氏空间中的卷积操作。
7.1.2 图神经网络的卷积
在图神经网络中，卷积操作通常涉及邻居节点的信息聚合。每个节点的特征向量会与其相邻节点的特征向量进行加权和，形成新的特征表示。这种消息传递机制反映了图信号处理中的思想，即通过在图上“传播”信息来捕获邻接关系。
例如，经典的图卷积网络（GCN）层的更新规则可以表示为：
\[ h_v^{(l+1)} = \sigma\left(\sum_{u \in \mathcal{N}(v)} \frac{1}{\sqrt{d_v d_u}} W^{(l)} h_u^{(l)}\right) \]
其中，\( h_v^{(l)} \) 是节点v在第l层的特征向量，\( \mathcal{N}(v) \) 是节点v的邻居集，\( d_v \) 和 \( d_u \) 分别是节点v和u的度，\( W^{(l)} \) 是权重矩阵，\( \sigma \) 是激活函数。
这种消息传递与图谱理论相结合，使得GNN能够学习图结构的复杂特性，并且在节点分类、链接预测等任务中表现出强大的性能。
7.2 消息传递与概率推理
神经消息传递方法，如GraphSAGE[Hamilton等人，2017a]，受到图形模型中消息传递算法的启发。在图形模型中，消息传递算法用于执行变量的联合概率分布的近似推理。在GNN中，节点间的消息传递可以视为一种迭代过程，其中节点不断更新其状态，基于邻居节点的状态信息。这种方法强调了图结构数据中的局部交互，同时保持了全局结构的考虑。
7.3 Weisfeiler-Lehman图同构测试
Weisfeiler-Lehman（WL）测试是一种确定两个图是否同构的算法。在GNN的上下文中，其关联在于，某些GNN架构可以达到与WL测试相同的区分能力。这意味着，如果两个图在WL测试下是不可区分的，那么这些GNN也无法区分它们。通过连接到图同构测试，GNN可以从图的局部结构中学习并提取全局信息，以实现图的分类和识别任务。
总结来说，GNN的理论动机涵盖了图信号处理、概率推理和图同构测试等多个领域。这些理论视角提供了理解和设计GNN的不同途径，使得GNN能够适应各种图数据的挑战，广泛应用于社会网络分析、化学分子结构识别、推荐系统等多个领域。了解这些理论基础对于深入掌握GNN的工作原理和优化模型至关重要。
