图结构数据与深度学习的交汇 · Convergence of Graph-Structured Data and Deep Learning

图结构数据与深度学习的交汇

Convergence of Graph-Structured Data and Deep Learning

如果你把 2012 年 AlexNet 在 ImageNet 上的胜利视作深度学习的"创世纪"，那么此后十年的绝大多数进展都可以被一句话概括：找到一种把数据塞进规则张量的方法。图像被切成像素网格、文本被切成 token 序列、语音被切成帧窗口——一旦数据被规整为 $n$ 维欧几里得空间中的稠密张量，CNN、RNN、Transformer 就能以几乎"开箱即用"的方式发挥作用。然而，2017 年前后学界与工业界逐渐意识到一类广泛存在的数据形态根本无法被这种范式优雅地吸纳：实体之间的关系本身就是信息，而关系所构成的结构既不规则、也不均匀、且维度不固定。这就是图（graph）——社交网络中的人与人、分子中的原子与化学键、城市路网中的路口与道路、推荐系统中的用户与商品、代码仓库中的函数与调用——它们构成了现实世界极其庞大的一类数据。当我们要让深度学习真正理解这些数据时，传统范式会在三个维度上同时失效。

这就是本章要回答的核心问题：为什么图结构数据需要一类全新的深度学习范式？为什么传统神经网络不能被简单迁移？ 我们将从欧氏数据与非欧氏数据的形式化对比出发，剖析图域所面临的三大根本性挑战，回顾早期图嵌入范式的成功与局限，并通过与 CNN、Transformer 的结构性类比，论证图神经网络（Graph Neural Network, GNN）作为独立范式的必要性。在此基础上，我们以欺诈检测与分子性质预测两个工业案例，具象化 GNN 创造的业务价值。最后，我们会在 PyTorch Geometric 中搭建一个可运行的 GNN 雏形，让读者从"概念理解"过渡到"工程感知"，为后续章节铺垫工程基础。

1.1 欧氏数据与非欧氏数据：被忽略的形式化分野

传统深度学习的成功建立在一个隐含但至关重要的假设之上——数据存在于规则的网格结构上。在数学上，这种结构被称为欧几里得空间（Euclidean space） $\mathbb{R}^n$，它具备平移不变性、缩放对称性，以及可由标准基向量线性生成的内积结构。在该空间中，张量的形状（shape）是一个具有强约束意义的元信息：对于一张 RGB 图像，其张量形状为 $(C, H, W)$，三个维度上的相邻元素存在明确的几何邻接关系——上下左右四个像素、加上对角线共八个像素，构成了 2D 卷积核的天然作用域；对于一段文本，其 token 序列可被视作 1D 网格，时间步的前后关系定义了 1D 卷积或自注意力的滑动窗口；对于一段语音，频谱图是 2D 网格，时间-频率双轴上的局部性定义了时频卷积的作用域。

我们可以用更形式化的语言刻画这一假设。设数据样本为 $x \in \mathcal{X}$，欧氏数据假设意味着存在一个维度固定的流形结构（grid、lattice 或其近似），使得样本可以被索引为 $x_{i_1, i_2, \ldots, i_k}$，且索引集合 $\mathcal{I} = \{1,\ldots,N_1\} \times \{1,\ldots,N_2\} \times \cdots \times \{1,\ldots,N_k\}$ 与输入的拓扑无关——也就是说，形状是先验固定的，无论具体样本的内容如何变化，张量的阶数和每一阶的长度都是确定的。这一不变性让随机梯度下降、批归一化、Dropout、卷积核共享等所有标准工具都能成立。

非欧氏数据 则彻底打破这一假设。最典型的代表就是图（graph）。一个图记作 $G = (V, E)$，其中 $V$ 是节点集合，$E \subseteq V \times V$ 是边集合。与图像像素网格不同，图的节点没有"第几个"这样的自然顺序——你可以对节点的编号做任意置换，图的本质结构不变；与文本序列不同，图的邻居数因节点而异——度数为 1 的节点和度数为 10000 的节点可以共存于同一个图中。我们把这种不具备规则网格结构的数据统称为非欧氏数据（non-Euclidean data） 或几何深度学习（geometric deep learning） 所关心的对象。流形（manifold）与流形上的图，是其更一般的数学抽象。

为了精确刻画这种差异，研究者引入了排列不变性（permutation invariance） 与排列等变性（permutation equivariance） 两个概念。给定一个图 $G = (A, X)$，其中 $A \in \{0,1\}^{N \times N}$ 是邻接矩阵，$X \in \mathbb{R}^{N \times d}$ 是节点特征矩阵，$P$ 为任意置换矩阵（permutation matrix），我们要求任何良定义的图函数 $f$ 满足：

$$ f(P A P^\top, P X) = f(A, X) \quad \text{(排列不变性)} $$

或者

$$ f(P A P^\top, P X) = P f(A, X) \quad \text{(排列等变性)} $$

这个看似抽象的要求实际上排除了绝大多数传统深度学习操作：标准全连接层不具备排列不变性（节点顺序变了，权重作用的对象就变了）；二维卷积不具排列不变性（卷积核假设了固定的左上-右下顺序）；甚至 RNN 也假设了固定的时序。**这就是图数据无法被传统神经网络"直接迁移"的第一个数学根源——我们需要一种在置换群作用下保持良定义性的新

的计算范式——这种范式必须把"图的拓扑"作为一等公民来对待，而不是事后修补。这就是我们在第 8 章将详细展开的消息传递（message passing） 框架的几何直觉来源：每条消息都沿着真实的边传递，而非沿着虚假的网格索引传播。

为了让读者直观感受"形状"假设失效的后果，我们做一个小实验。取一张 $28 \times 28$ 的 MNIST 手写数字图像，将像素的行号和列号彻底打乱，得到的新图像在视觉上毫无意义——但对一个未经训练的 MLP 而言，二者的输入向量在数学上等价，张量形状同样是 $(1, 784)$。这一矛盾恰好暴露了规则的网格结构隐含提供了三件欧氏深度学习的"基础设施"：邻居的确定性（像素 5 的左边一定是像素 4）、位置的标准化（图像中心 vs 角落的几何意义不同）、操作的局部性（$3\times3$ 卷积核扫过整图时的感受野几何恒定）。在图域，这三件基础设施全部需要重新构建。

1.2 图域的三大根本性挑战

理解了欧氏与非欧氏数据的形式化分野之后，我们可以更精确地刻画深度学习在图域面临的根本性挑战。这些挑战彼此并不独立，但出于概念清晰性的考虑，我们逐一剖析。

挑战一：不规则拓扑（Irregular Topology）。 图像的像素网格是一个高度对称的二维格点（lattice），任何 $3\times 3$ 邻域都具有相同的几何结构；而图中节点的邻居集合是一个由 $E$ 决定的、因节点而异的集合。我们既无法对所有节点定义"上、下、左、右"四个方向，也无法用同一个固定大小的核同时处理度数 2 和度数 200 的节点。从拓扑角度看，规则格点是一个具有平移不变性的 Cayley 图（与 $\mathbb{Z}^2$ 的标准生成元对应），而任意图通常不具备任何非平凡对称群。这种"无规则"在工程上的体现是：图像的卷积实现可以借助 im2col + GEMM 的高度优化路径（图卷积可借由 FFT），而图的卷积长期缺乏等效的统一实现，必须借助 scatter-gather 等稀疏算子。

挑战二：邻居数目的动态性（Variable Neighborhood Size）。 在同一个图中，节点的度分布往往呈现长尾（long-tail） 特征。以 Twitter 关注关系图为例，超过 60% 的用户粉丝数不到 100，但少数"超级节点"（明星、媒体账号）的粉丝数可达千万级。这种异质性意味着任何试图用固定大小邻域的算子都会遭遇两难困境：若按小度数节点设计算子（如固定采样 5 个邻居），则在超级节点上信息损失严重；若按大度数节点设计算子，则小度数节点会被大量无意义的填充（padding）信号淹没。GraphSAGE 在 2017 年提出的邻居采样（neighbor sampling）、PinSage 在 2018 年提出的基于随机游走的重要性采样，都是为了缓解这一挑战的工程创新——但它们本身也引入了"采样方差"这一新的设计维度。我们将在第 6 章详细讨论这一权衡。

挑战三：缺乏平移不变性（Lack of Translation Invariance）。 在图像中，一个 $3\times 3$ 卷积核扫描全图时，权重是共享的——左上角和右下角的卷积运算使用完全相同的参数集合。这种权重共享（weight sharing） 正是 CNN 能够用极少参数就处理任意分辨率图像的关键，也使得"平移不变性"成为 CV 任务的天然归纳偏置（inductive bias）。在图域，由于节点的邻居数不固定、邻居的几何位置不规整，我们无法直接定义"权重共享"。一个可行的替代方案是消息函数共享：所有节点都使用同一个消息函数 $f_\theta$ 处理各自邻居发来的消息，由消息传递机制隐式实现"在结构上共享参数"。这一思想是 GNN 设计的核心范式之一，但需要解决一个棘手的对称性问题：消息聚合必须是置换不变的（sum、mean、max 等对称函数），否则消息的顺序会反过来破坏等变性。这一约束将在第 4 章 GCN 的推导和第 8 章消息传递的统一框架中被反复使用。

当我们把这三个挑战放在一起观察，会发现它们共同指向一个事实：图域不存在一个类似卷积核那样的"局部性+平移不变性+权重共享"三位一体的天然算子。这意味着我们不能简单地把图像或文本领域的成功经验平移过来，而必须从零构建一种新的范式——这正是图神经网络存在的意义。

1.3 早期图嵌入范式：概念前奏与历史局限

在 GNN 真正成熟（以 2016 年 Kipf & Welling 的 GCN 论文为里程碑）之前，学界已经尝试用一种更朴素的方式把图数据"喂给"深度学习模型：先把图中的节点、边、子图映射到一个低维稠密向量空间（即嵌入，embedding），然后再对得到的向量做下游任务。这个范式被称为图嵌入（Graph Embedding） 或表示学习（Representation Learning），它是现代 GNN 的概念前奏。

基于矩阵分解的方法是最早的尝试。其核心思想是把邻接矩阵 $A \in \mathbb{R}^{N \times N}$ 视为一种"相似度矩阵"，并通过分解 $A \approx Z Z^\top$（其中 $Z \in \mathbb{R}^{N \times d}$, $d \ll N$）来得到每个节点的 $d$ 维嵌入。经典代表包括 LLE（Locally Linear Embedding）、Laplacian Eigenmaps 和 GraphFactorization。这类方法的优点是数学上清晰、可解释性强，但缺点也同样明显：它们本质上是转导学习（transductive learning） 的——必须在见到整个图之后才能产出嵌入，且无法处理训练时未出现的新节点。在真实的工业场景中，节点会以分钟级速度不断加入（如新用户注册、新商品上架），转导学习的这一缺陷是不可接受的。

基于随机游走的方法把自然语言处理中的 word2vec 思想迁移到了图上。2014 年提出的 DeepWalk 是这一范式的开创性工作：它从一个节点出发进行固定长度的随机游走，把游走序列视作"句子"，把序列中的节点视作"词"，然后用 Skip-Gram 模型学习节点嵌入。2016 年提出的 node2vec 进一步引入了两个超参数 $p$ 和 $q$ 来控制游走的"广度优先"与"深度优先"倾向，使得嵌入可以捕获更丰富的同质性（homophily）和结构等价性（structural equivalence）。LINE（2015）则从另一个角度切入，定义了节点间的一阶邻近度（直接相连）和二阶邻近度（共享邻居），分别优化对应的似然函数。

这些方法在节点分类、链接预测等任务上取得了令人瞩目的成绩，但也暴露了若干根本性局限。

第一，节点特征未被利用。DeepWalk 和 node2vec 仅仅使用了图的拓扑结构（随机游走产生的共现关系），完全忽略了节点的属性信息（如用户的年龄、购买历史；分子的原子类型、官能团）。在多数实际场景中，节点特征是任务信号的重要载体，纯拓扑嵌入会把这些强信号浪费掉。

第二，参数与节点数耦合。上述方法为每个节点学习一个独立的嵌入向量 $z_v \in \mathbb{R}^d$，因此参数总量为 $N \times d$。当 $N$ 达到亿级时，存储和推理开销都难以承受。更关键的是，新节点加入时必须重新训练全部嵌入，这在动态图中是不可接受的。

第三，难以捕获高阶结构。随机游走主要编码了局部共现信息，对于跨越多个跳数（multi-hop）的全局结构、长程依赖（long-range dependency）、高阶子图（如三角形、四边形）等模式，捕捉能力有限。

这些局限性共同推动了研究者从"独立嵌入每个节点"转向"用神经网络参数化一个函数 $f_\theta: G \mapsto \mathbb{R}^{N \times d}$，由 $\theta$ 而非节点本身承载嵌入信息"。这一范式转移，就是图神经网络诞生的本质。

1.4 与 CNN、Transformer 的结构性类比：为什么 GNN 需要新范式

读者可能会问：既然 Transformer 通过自注意力已经在 NLP、CV 甚至蛋白质结构预测领域取得如此广泛的成就，能不能直接用 Transformer 来处理图？GNN 究竟带来了什么 Transformer 做不到的"增量价值"？这一节我们通过结构性类比来回答这个问题。

让我们先回顾 CNN 和 Transformer 各自抓住了什么本质特征。

CNN 的核心归纳偏置：局部性（locality）和平移不变性（translation invariance）。它假设图像中的相邻像素高度相关、远处的信息可以通过层次化的局部聚合得到。这种偏置使得 CNN 在参数效率上远超 MLP——一个 $3\times 3$ 卷积核无论作用于图像的哪个位置都共享同一组参数，从而把参数复杂度从 $O(H \times W \times d^2)$ 降到 $O(k^2 \times d^2)$。CNN 的成功本质上是"正确的归纳偏置 + 足够的数据"。

Transformer 的核心归纳偏置：任意位置之间的全局交互。它通过 Query-Key-Value 三元组的点积注意力机制，允许序列中任意两个位置直接通信，绕过了 RNN 的顺序依赖和 CNN 的局部限制。但代价是必须显式注入位置编码（positional encoding）来弥补"自注意力本身是置换不变的"这一性质——Transformer 把"局部性"作为一个可学习的偏置（通过位置编码和数据驱动的方式隐式学得），而非像 CNN 那样作为先验硬编码。

现在让我们审视图域。图数据具有什么独特的归纳偏置？答案是稀疏连接（sparsity） 与显式结构（explicit structure）。在大多数真实图中，每个节点的度数远小于节点总数，即节点之间的连接是稀疏的；同时，连接本身就是有意义的信号——它显式编码了"哪些实体之间存在关系"。Transformer 的全局注意力机制则把所有位置视为全连接，对图数据而言，这相当于把稀疏结构强行"稠密化"，会带来两个问题：其一，计算复杂度从稀疏的 $O(|E| \cdot d)$ 膨胀到 $O(N^2 \cdot d)$；其二，真正有意义的边被淹没在大量无意义的非边注意力中——Transformer 的归纳偏置没有利用"显式结构"这一极强信号。

GNN 的核心归纳偏置：以边为骨架的消息传递（message passing on edges）。它显式地把边作为信息流动的载体，并在此基础上叠加置换不变性、等变性、可选的层次聚合。这套偏置与图数据本身的结构高度匹配，是 CNN 的"局部性 + 平移不变性"思想在非欧域的自然推广。我们将在第 8 章看到，消息传递框架可以被理解为"图上的卷积"——它把卷积核从规则的网格邻域推广到不规则的边集合，权重共享从"位置级"提升为"结构级"。

值得注意的是，GNN 与 Transformer 并非互斥关系。Graph Transformer（如 Graphormer、GraphGPS 等）近年来成为研究热点，它在消息传递层之上叠加全局注意力，试图同时享受两者的优势。但这种混合范式也带来了新的设计选择：局部消息与全局注意力如何分配权重？位置编码如何在非欧域表达？这些问题直到 2024 年仍未完全解决，也是第 14 章要讨论的核心议题之一。

1.5 贯穿性工业案例：欺诈检测与分子性质预测

抽象的概念需要落地到具体问题才显出价值。本书选择社交网络欺诈检测和分子性质预测作为贯穿全书的两个工业案例，是因为它们恰好覆盖了 GNN 价值最显著的两类场景：大规模稀疏图上的节点分类，以及中小规模富特征图上的图级回归。在第 1 章我们先做问题陈述，第 13 章会回到这两个案例做完整的工程化方案。

案例一：社交网络欺诈检测。 在蚂蚁集团、PayPal、Venmo 等大型支付平台中，欺诈账户通常不会孤立存在——它们倾向于组成欺诈团伙（fraud ring）：批量注册账户之间互相转账、共享设备指纹、共用 IP 段，甚至彼此关注形成小型社群以提升"正常度"。这类团伙在用户-用户关系图中表现为稠密子图（dense subgraph） 或准团（quasi-clique），其拓扑特征与正常用户的稀疏、长尾分布形成鲜明对比。

为什么传统机器学习难以单独解决这一问题？因为欺诈团伙的核心特征不在于单个用户的属性（年龄、性别、历史行为），而在于用户之间的关系——这正是图结构所编码的信息。一个用户看起来"完全正常"，但若其 10 个邻居全部是高风险账户，那么该用户是欺诈的概率会显著上升。这种"邻居信号"的传递，正是 GNN 擅长的运算形式。具体地，我们可以把每个账户视为一个节点，把账户间的转账、关注、设备共享等关系视为边，把账户的画像特征（注册时间、历史交易、设备指纹）作为节点初始特征 $X$，然后用 GNN 学习节点的最终嵌入 $Z \in \ma