图与图数据：为什么我们需要图神经网络 (Graphs and Graph Data: Why We Need GNNs)

第 1 章 图与图数据：为什么我们需要图神经网络

关系数据 (relational data) 才是世界本来的样子。当我们把用户、原子、商品、概念都看成相互独立的"行"或"点"时，其实已经丢失了最关键的信息——它们之间的连接。传统的表格数据建模 (Table-based Modeling) 与序列建模 (Sequence Modeling) 之所以在许多真实场景下捉襟见肘，根本原因在于它们默认数据存在于欧几里得空间 (Euclidean Space)：一个具有规则拓扑、平移不变、且存在全局坐标系的空间。而图 (Graph) 是一种典型的非欧几里得数据结构 (Non-Euclidean Data Structure)——它的拓扑是不规则的，节点的邻居数量是可变的，整体结构不存在"原点"也不存在"自然坐标系"。这种结构上的根本差异，决定了卷积神经网络 (Convolutional Neural Network, CNN)、循环神经网络 (Recurrent Neural Network, RNN) 与早期 Transformer 等架构不能直接迁移到图上。本章正是要回答一个看起来简单却极其关键的问题：图数据与传统的欧氏空间数据有何本质区别？为什么现有深度学习架构无法直接处理图？

在进入正式讨论之前，先建立一个直观的对比。下图 (Mermaid flowchart) 给出了欧氏数据与非欧氏数据在结构形态上的根本差异：

```mermaid flowchart LR A[Euclidean Data] --> B[Grid Image 2D grid] A --> C[Sequence 1D chain] A --> D[Audio 1D waveform] E[Non-Euclidean Data] --> F[Graph arbitrary topology] E --> G[Manifold curved surface] E --> H[Point Cloud irregular set] B -.->|fixed neighbors| I[CNN RNN] C -.->|fixed order| I F -.->|variable neighbors| J[GNN] G -.->|variable neighbors| J ```

可以看到，欧氏数据天然具有规则的邻域结构（图像中每个像素有 4 或 8 个固定邻居，序列中每个 token 有左右各 1 个固定邻居），因此可以使用固定大小的卷积核或固定长度的时间窗口进行处理。但图的节点邻居数量是任意的，邻居之间也没有"左"和"右"的天然顺序——这就是问题所在。

1.1 关系世界：从四个真实场景看图的不可或缺性

让我们从四个真实的应用场景出发，看一看"关系"是如何成为问题核心的。

场景一：社交网络 (Social Network)。 在 Twitter、微博、Facebook 等社交平台上，每个用户是一个实体 (entity)，用户之间的"关注""好友""转发"则构成关系 (relation)。如果只用表格建模，我们通常会构造一张"用户特征表"，列是年龄、性别、地区、注册时间等属性，行为预测 (如点击、点赞、转发) 会被建模成监督学习中的 $y = f(\mathbf{x})$ 形式。然而，一条推文是否会病毒式传播，几乎不取决于"作者本人的特征"，而取决于它是否进入了高连接度的 KOL 集群、是否被有影响力的人转发、传播路径上用户的"二度连接"是否密集。换句话说，预测目标严重依赖于图的拓扑结构 (topology)，而不是孤立的节点特征 (node feature)。表格模型把"邻居信息"压缩成了诸如"关注者数"这样的标量 (scalar)，信息损失巨大。

场景二：分子结构 (Molecular Structure)。 一个有机分子可以用原子 (atom) 集合加化学键 (chemical bond) 集合精确表示。原子本身的特征 (元素、电荷、杂化方式) 固然重要，但分子的化学性质——沸点、毒性、是否可成药——主要由"原子通过什么样的键连接成什么形状"决定。氰化氢 (HCN) 和苯 (C₆H₆) 同样含有碳和氢，但前者是剧毒气体，后者却是常见的有机溶剂。把分子表示为固定长度的向量 (例如 RDK fingerprints) 是一种"指纹"近似，必然丢掉了三维几何与连接性信息。如果要做"分子性质预测 (molecular property prediction)"或"药物发现 (drug discovery)"，必须把图作为一等公民来对待。

场景三：推荐系统 (Recommender System)。 在用户-商品 (user-item) 二部图 (bipartite graph) 中，购买、点击、收藏、加入购物车等行为构成边。传统协同过滤 (Collaborative Filtering, CF) 将"用户-商品交互矩阵"分解为两个低秩矩阵 (low-rank matrix factorization)，这本质上是把图压缩成了一张稠密矩阵。一旦交互数据极度稀疏（实际业务中 99% 以上的格子是 0），矩阵分解就会失效。更重要的是，矩阵分解无法显式地利用"高阶连接 (high-order connectivity)"——例如"用户 A 喜欢商品 1，商品 1 又和商品 2 经常被一起购买，那么用户 A 也可能喜欢商品 2"。这种二阶甚至多阶的传播信号，只有把数据显式建模为图才能自然表达。

场景四：知识图谱 (Knowledge Graph, KG)。 知识图谱是由实体 (entity) 与关系 (relation) 组成的有向异构图 (heterogeneous directed graph)，形式化地表示为三元组 (head, relation, tail)，例如 (北京，是...首都，中国)、(爱因斯坦，出生地，乌尔姆)。在 KG 上，典型的任务包括链接预测 (link prediction) 与实体分类 (entity classification)。例如，给定 (爱因斯坦，职业，？)，我们需要根据图谱中已有的结构信息推断出 "?" 应是"物理学家"。这种"基于已知事实推理未知事实"的能力，与图谱中实体间的多跳路径 (multi-hop path) 紧密耦合。

这四个场景的共同点是：实体之间的连接承载了不可忽略的语义。把数据当成孤立的行来建模，就像拿着一张只有文字没有上下文的小说节选，再聪明的读者也难以还原全貌。表格模型丢失了"邻居是谁"，序列模型丢失了"图结构是否有环、是否有偏倚、是否具有层次性"。这就是为什么我们必须为图数据专门设计一类新的学习范式。

1.2 图论基础：节点、边与邻接矩阵的严格定义

在进入"图神经网络"之前，必须先建立扎实的图论基础。这一节给出所有后续章节都会用到的核心定义。

定义 1.1 (图 Graph)。 一个图 $G = (V, E)$ 由两个集合组成：$V$ 是节点 (vertex 或 node) 的有限集合，$E \subseteq V \times V$ 是边 (edge) 的集合。节点的数目记为 $n = |V|$，边的数目记为 $m = |E|$。

定义 1.2 (邻接矩阵 Adjacency Matrix)。 图 $G$ 的邻接矩阵是一个 $n \times n$ 的矩阵 $\mathbf{A}$，其元素定义为：

$$A_{ij} = \begin{cases} 1 & \text{if } (v_i, v_j) \in E \\ 0 & \text{otherwise} \end{cases}$$

对于无向图 (undirected graph)，邻接矩阵是对称的 (symmetric)，即 $A_{ij} = A_{ji}$。对于有向图 (directed graph)，$A_{ij} = 1$ 表示一条从 $v_i$ 指向 $v_j$ 的有向边，矩阵不再对称。

定义 1.3 (加权图 Weighted Graph)。 在加权图中，每条边附带一个权重 (weight) $w_{ij} \in \mathbb{R}$，邻接矩阵扩展为 $\mathbf{A} \in \mathbb{R}^{n \times n}$，其中 $A_{ij} = w_{ij}$（或 0）。

定义 1.4 (度 Degree)。 节点 $v_i$ 的度定义为与其直接相连的边数。在无向图中：

$$d(v_i) = \sum_{j=1}^{n} A_{ij}$$

在有向图中，进一步区分入度 (in-degree) $d_{\text{in}}(v_i) = \sum_{j} A_{ji}$ 与出度 (out-degree) $d_{\text{out}}(v_i) = \sum_{j} A_{ij}$。节点的度是图论中最基础的局部统计量 (local statistic)。

定义 1.5 (路径 Path)。 路径是节点序列 $v_{i_0}, v_{i_1}, \dots, v_{i_k}$，其中相邻节点之间存在边，即 $(v_{i_{t-1}}, v_{i_t}) \in E$ 对所有 $1 \le t \le k$ 成立。$k$ 称为路径长度 (path length)。如果起点和终点重合 ( $v_{i_0} = v_{i_k}$ )，则称之为环 (cycle)。

定义 1.6 (连通分量 Connected Component)。 在无向图中，如果任意两个节点之间都存在一条路径，则称图是连通的 (connected)。一个图的最大连通子图称为一个连通分量。如果一个图只有一个连通分量，则该图是连通图。

定义 1.7 (邻居 Neighborhood)。 节点 $v_i$ 的邻居集合定义为 $N(v_i) = \{v_j \in V : (v_i, v_j) \in E\}$。$k$ 跳邻居 (k-hop neighborhood) 则是通过长度不超过 $k$ 的路径可达的所有节点的集合。

以上是后续所有讨论的"词汇表"。读者可能已经注意到：邻接矩阵 $\mathbf{A}$ 是唯一的吗？ 不一定。如果我们把节点的编号打乱 (permutation)，邻接矩阵会变成 $\mathbf{P}^\top \mathbf{A} \mathbf{P}$，其中 $\mathbf{P}$ 是置换矩阵 (permutation matrix)。这意味着，同一张图可以用无穷多种邻接矩阵表示，但所有这些矩阵描述的都是同一张图。这一性质是后文讨论"置换不变性"的核心伏笔。

1.3 图的统计特性：度分布、聚类系数与幂律

理解一张图，光看节点和边远远不够。我们需要描述图的整体统计行为 (global statistics)。本节介绍四个最常用的图统计量。

度分布 (Degree Distribution)。 随机选取一个节点，其度恰好为 $k$ 的概率记为 $P(k)$。度分布描述了图中节点连接度的整体分布形态。可以通过如下公式计算：

$$P(k) = \frac{|\{v_i \in V : d(v_i) = k\}|}{n}$$

聚类系数 (Clustering Coefficient)。 聚类系数衡量"你的朋友之间也是朋友"的程度。对于节点 $v_i$，其局部聚类系数定义为：

$$C_i = \frac{2 \cdot |\{(v_j, v_k) \in E : v_j, v_k \in N(v_i)\}|}{d(v_i)(d(v_i) - 1)}$$

分子是 $v_i$ 的邻居之间实际存在的边数，分母是邻居之间最多可能存在的边数。$C_i \in [0, 1]$。整个图的聚类系数是所有节点聚类系数的平均值。

小世界属性 (Small-world Property)。 一个图被称为具有"小世界"性质，如果它的平均最短路径长度 (average shortest path length) 随节点数 $n$ 呈对数增长 $\langle \ell \rangle \sim \log n$，但同时聚类系数显著高于对应的随机图。社交网络是典型的小世界：六度分隔 (six degrees of separation) 实验早已证明，任何两个人之间平均只需 5.6 跳即可连通。

幂律分布 (Power-law Distribution)。 许多真实网络的度分布服从幂律：

$$P(k) \sim k^{-\alpha}$$

其中 $\alpha$ 通常在 2 到 3 之间。这意味着"少数节点拥有大量连接，而大多数节点只有少量连接"。Twitter 的关注者分布、互联网的路由器连接、学术论文的引用网络都呈现明显的幂律特征。幂律分布的"重尾 (heavy tail)"使得平均度不再是一个有代表性的统计量——少量高度节点对图的结构有支配性影响。这也是为什么图算法常常需要专门处理"度不平衡 (degree imbalance)"问题。

下面用 NetworkX 演示如何计算这些统计量。NetworkX 是 Python 中最常用的图分析库：

```python import networkx as nx import numpy as np import matplotlib.pyplot as plt

1. 创建一个有名的"Zachary's Karate Club"图

G = nx.karate_club_graph() print(f"Number of nodes: {G.number_of_nodes()}") print(f"Number of edges: {G.number_of_edges()}")

2. 计算度序列与度分布

degrees = [d for _, d in G.degree()] print(f"Degree sequence: {sorted(degrees, reverse=True)[:10]}") print(f"Average degree: {np.mean(degrees):.2f}") print(f"Max degree: {max(degrees)}, Min degree: {min(degrees)}")

3. 聚类系数

print(f"Average clustering coefficient: {nx.average_clustering(G):.3f}")

4. 平均最短路径长度（仅对连通图有意义）

if nx.is_connected(G): print(f"Average shortest path length: {nx.average_shortest_path_length(G):.3f}")

5. 度分布直方图

plt.figure(figsize=(6, 4)) plt.hist(degrees, bins=range(0, max(degrees) + 2), align="left", edgecolor="black") plt.xlabel("Degree k") plt.ylabel("Count") plt.title("Degree Distribution of Karate Club Graph") plt.tight_layout() plt.savefig("degree_distribution.png", dpi=120) plt.show() ```

运行这段代码后，读者会看到 Karate Club 图有 34 个节点、78 条边，平均聚类系数约为 0.57，平均最短路径长度约为 2.4，度分布右偏——这正是"小世界 + 度不均"的典型特征。Karate Club 图在图算法史上地位特殊——它是 1977 年社会学家 Zachary 研究的一个空手道俱乐部分裂事件中成员之间的关系网络，被作为社区检测 (community detection) 的标准 benchmark 使用了几十年。

1.4 三大核心障碍：为什么 CNN/RNN/Transformer 难以直接处理图

有了上述基础，我们现在可以严格地回答"为什么现有深度学习架构不能直接处理图"。核心障碍有三条，每一条都是图结构在数学上区别于欧氏数据的根本体现。

障碍一：节点排列不唯一 (Node Permutation Invariance / Non-uniqueness of Node Ordering)。 对一张图 $G$，我们可以用任意顺序对节点编号，从而得到不同的邻接矩阵 $\mathbf{A}^{(1)} = \mathbf{P}^\top \mathbf{A} \mathbf{P}$，但所有这些矩阵都描述同一张图。CNN、RNN 等模型对输入的"顺序"或"位置"是敏感的——把图像的像素重排一下，CNN 的输出必然不同；把句子的词序调换，RNN 的隐藏状态序列也会改变。但图的学习器必须满足置换不变性 (permutation invariance)：对节点的重排不应改变模型对图的预测结果。形式化地，对一个图级函数 (graph-level function) $f$ 来说，我们要求：

$$f(\mathbf{P}^\top \mathbf{A} \mathbf{P}, \mathbf{P}^\top \mathbf{X}) = f(\mathbf{A}, \mathbf{X})$$

其中 $\mathbf{X}$ 是节点特征矩阵。这一约束直接排除了"把邻接矩阵当成图像、把节点特征当成像素"的朴素思路。后面章节将看到，GNN 通过"邻居聚合 (neighbor aggregation)"的机制天然地满足置换不变性。

障碍二：邻居数量可变 (Variable Neighborhood Size)。 欧氏数据中，图像像素的邻居是固定的（4 邻接或 8 邻接），序列 token 的上下文是固定的（左 1 + 右 1，或固定窗口大小）。这使得我们可以使用固定大小的卷积核 (fixed-size kernel)。但图中节点的度可能从 1 到几千不等——Twitter 上普通用户可能只有几十个关注者，而明星账号的粉丝数可以上亿。如果沿用固定大小的卷积，要么严重欠采样低度节点的信息，要么在高度节点上计算量爆炸。图神经网络 (GNN) 通过"消息传递 (message passing)"的方式解决这个问题：每个节点从其所有邻居处收集信息，邻居数量自然地、可变地被处理。

障碍三：拓扑结构动态性 (Dynamic Topology)。 真实世界的图很少是静态的。社交网络每天都有新用户注册和新关注产生；引用网络