现实世界中不乏有大量数据是以**图(Graph)**的形式存在的，如社交网络、知识图谱、分子结构等。这些非欧几里得空间的数据没有固定的排列顺序和邻居数量。

为了在图结构数据上应用深度学习，**图神经网络(GNN)应运而生。而图卷积神经网络(GCN)**作为GNN中最简单、最经典的模型(由Kipf & Welling于ICLR 2017提出)，是我们理解图深度学习的最佳切入点。

1. 核心机制：消息传递计算图(Message Passing Computational Graph)#

在普通的神经网络中，前向传播是一层层独立的矩阵乘法。但在GNN中，网络结构是由图的拓扑结构决定的。

GNN的核心思想是：一个节点的特征表示，由它自身的特征以及其周围邻居的特征共同决定。

计算图的展开#

为了更新某个特定节点(例如节点 A)的嵌入表示，我们以 A 为根节点，向外展开它的邻居，形成一棵计算图(Computational Graph)：

第 0 层(输入层)：最底层的叶子节点输入的是图中节点的初始属性特征(Node Features)。如果没有属性特征，可以使用全1向量或 One-hot编码代替。
第 1 层：聚合节点 A 的一阶邻居信息。
第 $K$ 层：一个 $K$ 层的 GNN，其计算图向外扩展 $K$ 阶，意味着每个节点的最终表示(Embedding)融合了它 $K$ 阶邻居的感受野(Receptive Field)。

需要注意的是，图中的每一个节点都有自己独特的计算图，但所有计算图都共享同一套神经网络的参数。训练的时候，每一个计算图就是一个样本。

2. 聚合函数与数学形式(Aggregation Function & Math Formulation)#

有了计算图，节点之间是如何把信息传递并聚合起来的呢？最直观的**聚合函数(Aggregation Function)**就是求平均(Average)。

基础 GNN 的数学公式#

对于节点 $v$ ，其在第 $l+1$ 层的隐藏状态 $h_v^{(l+1)}$ 计算方式如下：

h_v^{(l+1)} = \sigma \left( W_l \sum_{u \in N(v)} \frac{h_u^{(l)}}{|N(v)|} + B_l h_v^{(l)} \right)

这里面的包含两个关键部分：

邻居聚合： $\sum_{u \in N(v)} \frac{h_u^{(l)}}{|N(v)|}$ 是收集所有邻居 $u$ 的特征并求平均，再乘以权重矩阵 $W_l$ 。
自身更新：节点本身的特征 $h_v^{(l)}$ 乘以权重矩阵 $B_l$ 。
最后将两者相加，通过一个非线性激活函数 $\sigma$ (如 ReLU)。

3. 计算图改进与 Normalized Adjacency 矩阵推导#

在上述公式中，我们需要分别训练 $W_l$ (管邻居)和 $B_l$ (管自己)，计算有些繁琐。为了更高效地利用 GPU 的矩阵运算，我们将逐节点的公式转化为矩阵形式。

引入自环(Self-loops)的计算图改进#

既然自身信息和邻居信息都需要参与聚合，我们不如直接在原图的邻接矩阵 $A$ 上给每个节点加上一个自环(Self-loop)： $\tilde{A} = A + I$

这样，节点本身也变成了自己的邻居， $W_l$ 和 $B_l$ 就可以合并为一个共享的权重矩阵 $W^{(l)}$ 。此时，未经归一化的特征聚合就可以写为： $\tilde{A}H^{(l)}$ ，其中 $H$ 为节点的特征矩阵，每一行表示一个节点的特征信息值的向量。然后，整体乘以共享的权重矩阵 $W^{(l)}$ ，即 $\tilde{A}H^{(l)}W^{(l)}$ 。

归一化(Normalization)推导#

直接用矩阵 $\tilde{A}$ 乘特征矩阵会有个致命问题：度数(Degree)越大的节点，聚合到的特征值越大，这会导致梯度爆炸或特征失真。 为了消除节点度的影响，我们需要用到对角线度矩阵 $\tilde{D}$ (其中 $\tilde{D}_{ii} = \sum_j \tilde{A}_{ij}$ )来进行归一化(Normalized Adjacency)。

行归一化(Row-normalized)： $\tilde{D}^{-1}\tilde{A}$ (对应求均值)
对称归一化(Symmetric normalized)：GCN 论文中采用了效果更好的对称归一化形式： $\tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}}$

最终，经典 GCN 的层级传播规则(数学形式)就诞生了：

H^{(l+1)} = \sigma \left( \tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}} H^{(l)} W^{(l)} \right)

(其中 $H^{(0)} = X$ 为初始特征矩阵)

这行极其优雅的公式意味着：矩阵乘法实现了一次全图范围内的高效消息传递。

4. 损失函数、训练流程与实验结果#

GCN 是一个端到端(End-to-End)的模型，支持多种训练方式：

训练流程与损失函数 (Loss Function)#

有监督分类(Supervised)：在节点分类任务中，GCN 的最后一层输出每个节点属于各类别的概率。我们只选取“有标签”的节点计算交叉熵损失(Cross-Entropy Loss)，然后通过反向传播更新所有层的权重 $W^{(l)}$ 。
无监督/自监督(Unsupervised)：如果没有标签，可以通过“图重构”或“随机游走”的方式，假设存在连接的两个节点在最终向量空间里的余弦相似度应当很高，通过对比损失(Contrastive Loss)等自监督形式训练。

5. GNN 相比传统图表示学习的巨大优点#

在 GNN 出现前，基于随机游走和矩阵分解的传统图嵌入方法(如 DeepWalk, Node2Vec)曾经盛极一时。相比传统方法，GNN/GCN 具有压倒性的优势：

归纳泛化能力(Inductive vs Transductive)
- 传统方法(直推式)：每个节点绑定一个独立的 Embedding 向量(通过查表 Lookup)。一旦图中加入了新的节点，或者要在一个全新未见过的图上测试，模型就彻底失效了，必须重新训练（类似过拟合的感觉）。
- GNN(归纳式)：GNN 学习到的不是特定节点的死板向量，而是“如何聚合邻居特征”的权重矩阵 $W^{(l)}$ 。这个聚合规则对任意新加入的节点甚至是全新图都是相对普适的，具有较强的泛化能力。
极小的参数量
- 传统方法的参数量为 $O(|V| \times d)$ ，随节点数线性暴增。
- GNN 采用全图参数共享，参数量只与层数、每层特征维度有关 $O(d_{in} \times d_{out})$ ，不管图有一万个节点还是十亿个节点，参数量都不变。
完美利用属性特征(Features)与标签信息(Labels)
- 传统方法只能利用图的拓扑连接结构，而无法结合节点本身的丰富属性(例如用户画像、文章内容特征等)。
- GNN 通过第0层的 $X$ 输入，完美实现了图拓扑结构与节点属性特征的端到端融合。

6. GNN 的表达能力理论天花板：Weisfeiler-Lehman (WL) 图同构测试#

在机器学习中，表达能力(Expressive Power)指的是模型区分不同输入的能力。

GNN 的表达能力，就是区分计算图根节点Embedding的能力。

对于图神经网络而言，最基础的任务之一是图分类(例如判断一个分子结构图是否有毒)。如果两个在拓扑结构上完全不同的图，经过 GNN 的 $K$ 层消息传递后，最终输出的全局 Embedding 向量竟然一模一样，这就意味着模型完全无法区分这两个图，分类必然失败。

图同构测试(Graph Isomorphism Test)#

判断两个图是不是同一个图(哪怕节点画的位置变了，但连接关系不变)，是一个非常经典的数学问题。其中最著名的启发式算法就是 Weisfeiler-Lehman (WL) 测试。

WL 测试的核心逻辑是通过给节点打标签，并不断收集“邻居标签集合”进行哈希映射，从而迭代更新中心节点的标签。如果迭代几轮后，两张图的标签集合直方图不同，则这两个图一定不同构。

仔细一想，你会发现 GNN 的“消息传递”与 WL 测试的“标签哈希”在本质上是完全等价的！

WL 测试收集邻居标签并哈希；
GNN 收集邻居特征(Embedding)并应用神经网络聚合(Aggregation)。

结论极其重要：所有基于消息传递(Message-Passing)的图神经网络，其表达能力的严格上限就是 WL 测试。GNN 再强，也不可能超过 WL 测试的区分能力。

7. 重集(Multiset)与单射(Injective)函数#

既然 WL 测试是天花板，那么我们要问：GNN 达到这个天花板了吗？这取决于 GNN 每一层的聚合函数(Aggregation Function)。

在图网络中，一个节点所有邻居的特征汇总在一起，构成了一个重集(Multiset)。“重集”是一个允许元素重复的集合，例如 $\{1, 1, 2\}$ 和 $\{1, 2\}$ 是两个不同的重集。

为了让 GNN 达到最强的区分能力(即达到 WL 测试的标准)，聚合函数必须是一个“单射”(Injective)重集函数。

单射(Injective)通俗解释：不同的输入，必须严格映射到不同的输出( $f(x) = f(y) \iff x=y$ )。绝不能出现“多对一”的信息丢失现象。如果在聚合邻居特征时丢失了信息，最终的 Embedding 就会产生混淆。

有了“单射”和“重集”作为裁判，我们来审视三种最经典的聚合器，看看为什么 GCN 和 GraphSAGE 在表达能力上存在致命缺陷。

1. Mean Aggregator (求平均)#

GCN 使用的是加权平均。

特点：善于捕捉邻居节点特征的比例(Distribution/Proportion)。
致命缺陷：无法区分数量上的差异。
反例：重集 $S_1 = \{A, B\}$ 和重集 $S_2 = \{A, A, B, B\}$ 。求平均后，两者的结果完全相同。GCN 会认为这两个节点的环境是一模一样的，从而产生混淆。这说明求平均不是单射。

2. Max-pooling Aggregator (求最大值)#

GraphSAGE 经常使用 Max-pooling。

特点：善于提取出邻居中的骨干/代表性特征(是否存在某种特定特征)。
致命缺陷：完全丢失了特征的**频率(频次)**和比例信息。
反例：重集 $S_1 = \{A, B\}$ 和重集 $S_2 = \{A, A, B\}$ 。无论 $A$ 出现几次，Max 操作的输出都一样。模型无法察觉周围到底是有 1 个 A 还是有 100 个 A。因此，求最大值也不是单射。

3. Sum Aggregator (求和)#

特点：简单粗暴地将所有邻居特征相加。
优势：无论是元素的类别(有没有这个特征)，还是元素的数量(这个特征有几个)，只要相加，最终的结果都是独一无二的！
结论：在重集上，只有“求和 (Sum)”才具备成为单射函数的潜力，能够无损地保留整个多重集的信息！

8. GIN (Graph Isomorphism Network)：设计强大表达能力的 GNN#

Jure Leskovec 团队(也是 CS224W 的主讲教授)据此提出了 GIN(Graph Isomorphism Network)。

根据万能近似定理(Universal Approximation Theorem, UAT)，理论上，只要有足够的宽度，MLP就是函数的“万能逼近器”，可以拟合任意的连续函数（这也是深度学习的理论基础和“上限”）。我们需要非线性函数MLP去拟合极度复杂的“单射映射”。并同时使用 Sum 为聚合函数。

GIN 的数学公式：#

GIN 每一层的特征更新规则如下：

h_v^{(k)} = \text{MLP}^{(k)} \left( (1 + \epsilon^{(k)}) \cdot h_v^{(k-1)} + \sum_{u \in N(v)} h_u^{(k-1)} \right)

公式拆解与精妙之处：

$\sum_{u \in N(v)} h_u^{(k-1)}$ ：使用 Sum(求和) 聚合器，无损收集所有邻居特征。
$(1 + \epsilon^{(k)}) \cdot h_v^{(k-1)}$ ：把自己当前层的特征加进去。这里引入了一个极其关键的可学习参数 $\epsilon$ 。它赋予了中心节点自身(Root Node)与邻居节点不同的权重，确保“中心自身特征”和“邻居聚合特征”在合并时也是单射的。
$\text{MLP}^{(k)}$ ：用一个多层感知机(至少两层，带有 ReLU)来保证该步骤能够拟合任意复杂的单射函数。

通过这样一套架构，GIN 在理论上证明了其表达能力等价于 Weisfeiler-Lehman 图同构测试，达到了基于消息传递的 GNN 的绝对上限。在各类图分类的数据集评测中，GIN 的表现也确实超越了 GCN 和 GraphSAGE。

9. 小结一下#

GCN(图卷积网络)：通过归一化的“求均值”矩阵运算，解决了将深度学习引入图结构(非欧空间)的开创性问题，具备了强大的归纳(Inductive)泛化能力。
GraphSAGE：通过采样(Sampling)机制和多种聚合器(如 Max-pooling)，解决了超大规模图的计算效率问题。
GIN(图同构网络)：回归数学本质，通过对 WL 测试、重集(Multiset)和单射(Injective)的深刻探讨，揭露了前两者的表达能力缺陷。最终采用“Sum聚合 + MLP + $\epsilon$ ”的极简优雅设计，登上了消息传递 GNN 表达能力的理论巅峰。