图数据基础与表示 / Fundamentals of Graph Data and Representations

图数据（Graph Data）作为一种表示实体间复杂关系的基本结构，其核心由节点（Node/Vertex） 和边（Edge/Link） 构成。节点代表研究对象（如用户、分子、论文），边描述节点间的关系（如关注、化学键、引用）。这种“关系驱动”的表示范式，使其成为建模社交网络、分子结构、知识体系等非欧几里得（Non-Euclidean）数据的天然工具。与具有规则网格结构的图像（Image）或具有固定时序顺序的序列（Sequence）不同，图数据具有不规则拓扑（Irregular Topology） 和可变大小（Variable Size） 的核心特性，这对传统的深度学习模型提出了根本性挑战。本章将系统性地建立图数据的理论基石，从数学定义出发，深入探讨其表示方法、存储机制及预处理流程，并通过跨领域实例揭示其普适性与特殊性，为后续学习图神经网络（Graph Neural Networks, GNNs）奠定坚实基础。

1.1 核心概念与数学定义

1.1.1 图的基本类型与属性

一个图（Graph） $G$ 在数学上被严格定义为有序对 $G = (V, E)$，其中 $V$ 是节点集（Vertex Set），$E \subseteq V \times V$ 是边集（Edge Set）。这种形式化定义是理解一切图相关算法的基础。

根据边的方向性，图可分为：

• **无向图（Undirected Graph）**：边 $(u, v)$ 与 $(v, u)$ 等价，关系是对称的。例如，Facebook 的好友关系是相互的。
• **有向图（Directed Graph/Digraph）**：边 $(u, v)$ 表示从节点 $u$（尾节点，Tail）指向节点 $v$（头节点，Head）的有向关系，$(u, v) \neq (v, u)$。例如，Twitter 的关注关系、论文引用网络。

根据边是否具有权重，可分为：

• **无权图（Unweighted Graph）**：所有边权重默认为 1，仅表示连接存在与否。
• **加权图（Weighted Graph）**：边 $e_{uv}$ 附带一个实数权重 $w_{uv} \in \mathbb{R}$，表示关系的强度、距离或成本。例如，合作网络中两人合作的论文数量、交通网络中道路的通行时间。

根据节点和边的类型，可分为：

• **同构图（Homogeneous Graph）**：所有节点属于同一类型，所有边属于同一类型。这是最简形式，如社交网络中的用户节点和好友边。
• **异构图（Heterogeneous Graph）**：节点和/或边属于多种预定义类型。通常用一个**节点类型映射函数** $\phi_v: V \rightarrow \mathcal{A}$ 和一个**边类型映射函数** $\phi_e: E \rightarrow \mathcal{R}$ 来定义，其中 $\mathcal{A}$ 和 $\mathcal{R}$ 分别是节点类型集合和关系类型集合。例如，学术知识图谱中，节点可以是论文（Paper）、作者（Author）、会议（Venue），边可以是“撰写”（Writes）、“发表于”（Publishes）。

此外，自环（Self-loop） 指节点到自身的边 $(v, v)$，在某些图卷积操作中被特意添加以包含节点自身信息。多重图（Multigraph） 允许同一对节点间存在多条边。

1.1.2 节点与边属性

图数据的丰富性不仅在于拓扑结构，更在于其附带的特征（Features） 或属性（Attributes）。

• **节点特征矩阵 $\mathbf{X} \in \mathbb{R}^{n \times d}$**：其中 $n = |V|$ 是节点数，$d$ 是每个节点的特征维度。例如，在分子图中，$d$ 可能是原子类型（one-hot 编码）、电负性、度等化学性质的拼接；在用户图中，$d$ 可能是用户画像（年龄、兴趣标签、注册时长）的嵌入向量。
• **边特征矩阵 $\mathbf{E} \in \mathbb{R}^{m \times p}$**（可选）：其中 $m = |E|$ 是边数，$p$ 是边特征维度。例如，在交通图中，边的权重可以是距离、限速、车道数；在知识图谱中，不同关系类型（如“出生于”、“就职于”）可被编码为不同的关系向量。

在异构图语境下，不同节点类型 $\tau \in \mathcal{A}$ 的特征维度 $d_\tau$ 可能不同，需分别处理。边特征同理。

1.1.3 核心数学表示：邻接矩阵与拉普拉斯矩阵

将图结构转化为计算机可处理的矩阵形式是图计算的核心。

邻接矩阵（Adjacency Matrix） $\mathbf{A} \in \{0, 1\}^{n \times n}$（无权图）或 $\mathbf{A} \in \mathbb{R}^{n \times n}$（加权图）是图结构最直接的编码： $$ \mathbf{A}_{ij} = \begin{cases} w_{ij} & \text{if } (v_i, v_j) \in E \\ 0 & \text{otherwise} \end{cases} $$ 对于无向图，$\mathbf{A}$ 是对称矩阵。邻接矩阵的行 $\mathbf{A}_{i:}$ 或列 $\mathbf{A}_{:j}$ 分别对应节点 $v_i$ 或 $v_j$ 的邻居集合，其非零元素个数即节点度（Degree） $k_i = \sum_j \mathbf{A}_{ij}$。邻接矩阵是定义图卷积滤波器的基础。

然而，邻接矩阵的谱性质（特征值分布）直接影响图信号（节点特征）在图上传播的稳定性。图拉普拉斯矩阵（Graph Laplacian Matrix） $\mathbf{L}$ 提供了更优的数学框架，其标准定义为： $$ \mathbf{L} = \mathbf{D} - \mathbf{A} $$ 其中 $\mathbf{D} \in \mathbb{R}^{n \times n}$ 是度矩阵（Degree Matrix），一个对角矩阵，对角线元素 $\mathbf{D}_{ii} = k_i$。

$\mathbf{L}$ 是对称半正定矩阵，其最小特征值为 0，对应的特征向量为全 1 向量。这反映了图的连通性：特征值 0 的重数等于图的连通分量数。$\mathbf{L}$ 的二次型形式 $\mathbf{x}^\top \mathbf{L} \mathbf{x} = \frac{1}{2}\sum_{i,j} \mathbf{A}_{ij}(x_i - x_j)^2$ 衡量了节点特征值 $\mathbf{x}$ 在图上的“平滑度”，即相邻节点特征差异的总和。这一性质使其成为定义图正则化项和图卷积的核心。

为改善数值稳定性并赋予物理意义（如随机游走），常使用对称归一化拉普拉斯矩阵（Symmetric Normalized Laplacian） $\mathbf{L}_{\text{sym}}$： $$ \mathbf{L}_{\text{sym}} = \mathbf{D}^{-1/2} \mathbf{L} \mathbf{D}^{-1/2} = \mathbf{I} - \mathbf{D}^{-1/2} \mathbf{A} \mathbf{D}^{-1/2} $$ 其中 $\mathbf{D}^{-1/2}$ 是对角线上为 $1/\sqrt{k_i}$ 的矩阵（对孤立节点 $k_i=0$ 通常设 $1/\sqrt{k_i}=0$）。$\mathbf{L}_{\text{sym}}$ 也是对称半正定的，特征值范围在 $[0, 2]$。

另一种常见形式是随机游走归一化拉普拉斯矩阵（Random Walk Normalized Laplacian） $\mathbf{L}_{\text{rw}}$： $$ \mathbf{L}_{\text{rw}} = \mathbf{D}^{-1} \mathbf{L} = \mathbf{I} - \mathbf{D}^{-1} \mathbf{A} $$ $\mathbf{L}_{\text{rw}}$ 不对称，但 $\mathbf{D}^{-1}\mathbf{A}$ 正是随机游走转移矩阵。$\mathbf{L}_{\text{rw}}$ 的特征向量与 $\mathbf{L}_{\text{sym}}$ 通过 $\mathbf{D}^{1/2}$ 关联。

```mermaid graph TD A[图 G(V,E)] --> B[邻接矩阵 A] A --> C[度矩阵 D] B --> D[标准拉普拉斯 L = D - A] C --> D D --> E[对称归一化 L_sym = I - D^{-1/2} A D^{-1/2}] D --> F[随机游走归一化 L_rw = I - D^{-1} A] E --> G[谱域图卷积理论基础] F --> G ```

这些矩阵的谱分解（$\mathbf{L} = \mathbf{U} \Lambda \mathbf{U}^\top$，其中 $\mathbf{U}$ 是特征向量矩阵，$\Lambda$ 是特征值对角阵）将图结构信号处理与卷积神经网络中的频域滤波联系起来，是早期图卷积网络（如 ChebNet, GCN）的理论起点。

1.2 图数据 vs. 序列与图像：范式差异剖析

理解图数据的独特性，必须将其与另外两种主流结构化数据——序列（Sequence） 和图像（Image）——进行系统对比。这种对比不仅揭示技术路线的根本差异，也解释了为何需要专门为图设计的神经网络架构。

| 特性维度 | 图像 (Image) | 序列 (Sequence) | 图 (Graph) | | :--- | :--- | :--- | :--- | | 数据结构 | 规则二维网格（欧几里得） | 一维链式序列（欧几里得） | 不规则拓扑（非欧几里得） | | 基础关系 | 空间局部性（相邻像素） | 时序依赖性（相邻时间步） | 拓扑连接性（邻接节点） | | 节点/元素顺序 | 固定（行列索引） | 固定（时间顺序） | 无固有顺序（排列等变） | | 输入尺寸 | 固定（如 224×224） | 可变但通常填充/截断 | 高度可变（节点数、边数） | | 典型表示 | 稠密张量 $\mathbb{R}^{H \times W \times C}$ | 序列张量 $\mathbb{R}^{T \times d}$ | 稀疏矩阵 $\mathbf{A}$， 列表 $\{V, E\}$ | | 核心操作 | 卷积（局部、平移不变） | 循环/注意力（时序依赖） | 消息传递/聚合（基于拓扑） | | 主要挑战 | 空间不变性、计算效率 | 长程依赖、序列长度 | 拓扑多样性、过平滑 |

关键差异的深入解读：

1. 排列等变性（Permutation Equivariance）：这是图神经网络最核心的设计约束。对于图像，卷积核在空间上滑动，其参数在位置 $(i,j)$ 和 $(i',j')$ 是共享的，体现了平移不变性（Translation Invariance）。对于序列，RNN 或 Transformer 在时间步上共享参数，体现时间平移不变性。然而，图节点没有天然的顺序。一个 GNN 层的输出 $\mathbf{h}_i'$ 必须仅依赖于节点 $i$ 及其邻居的特征和结构，而与邻居的枚举顺序无关。即，若 $\pi$ 是节点 $i$ 的邻居集合的任意排列，则聚合函数 $f$ 必须满足 $f(\{\mathbf{h}_j, \mathbf{e}_{ij} \mid j \in \mathcal{N}(i)\}) = f(\{\mathbf{h}_{\pi(j)}, \mathbf{e}_{i\pi(j)} \mid j \in \mathcal{N}(i)\})$。这直接导致了消息传递（Message Passing） 范式的诞生：聚合（如 sum, mean, max）天然满足排列不变性。

2. 可变尺寸与结构：图像分类网络（如 ResNet）通常要求固定输入尺寸。虽然可以通过全局池化处理可变尺寸，但图的结构（连通性、节点度分布）本身千差万别。一个 GNN 必须能够处理训练时未见过的、具有不同节点数和拓扑结构的图。这要求模型参数不依赖于具体图的规模，而只依赖于局部邻域模式。图池化（Graph Pooling）操作（如 DiffPool, SAGPool）的设计难度远高于图像池化（如 MaxPool2d），因为它需要在保留重要结构信息的同时，处理节点的对齐问题。

3. 过平滑问题（Over-smoothing）：随着 GNN 层数增加，通过反复的邻域聚合，所有节点的表征会逐渐收敛到同一个向量（或低维子空间），失去区分性。这在图像或序列中较少见（深层 CNN 可能产生语义类似的特征，但通常仍可区分）。过平滑的根本原因是图拉普拉斯算子的幂次：$k$ 层 GCN 相当于对初始特征应用 $\mathbf{L}_{\text{sym}}^k$ 的滤波。当 $k$ 很大时，高频分量被滤除，所有节点趋于平滑。这直接限制了有效感受野的深度，促使研究者设计残差连接、跳连（Jumping Knowledge）或基于子图的方法。

4. 结构信息的不确定性：图像中，像素位置是精确已知的。序列中，顺序是明确的。但在许多现实图（如社交网络推断图、分子构象）中，边本身可能存在噪声、缺失或不确定性。GNN 通常假设输入图是给定的、确定的，如何鲁棒地处理不完美图结构是前沿挑战。

1.3 图的存储格式与计算效率

在计算机内存中高效存储大规模稀疏图是实践的第一步。图的规模 $n$ 可能达百万甚至十亿级，但边密度通常很低（稀疏图），因此必须使用稀疏矩阵表示。以下介绍三种主流格式。

1.3.1 边列表（Edge List, COO 格式）

最直观、最易读的格式。存储两个（无向）或三个（有向）数组：

• `src`: 源节点索引数组，长度 $m$
• `dst`: 目标节点索引数组，长度 $m$
• `weight` (可选): 权重数组，长度 $m$

例如，边 $(0, 1, 0.5), (0, 2, 1.0), (1, 2, 0.8)$ 的 COO 表示为： ``` src = [0, 0, 1] dst = [1, 2, 2] weight = [0.5, 1.0, 0.8] ``` 优点：构建简单，易于从文件读取（如 `u v w` 格式）。缺点：不支持高效的行/列切片操作，不适合需要频繁访问某节点所有邻居的场景。

1.3.2 压缩稀疏行（Compressed Sparse Row, CSR）

最适合基于邻接的图遍历操作（如 BFS、消息传递中按源节点聚合）。它使用三个数组：

• `indptr`: 指针数组，长度 $n+1$。`indptr[i]` 指向 `indices` 和 `data` 中节点 $i$ 邻居的起始位置，`indptr[i+1] - indptr[i]` 即为节点 $i$ 的度 $k_i$。
• `indices`: 列索引数组，存储所有邻居节点的全局 ID，长度 $m$。
• `data` (可选): 权重数组，长度 $m$，与 `indices` 一一对应。

接上例，节点 0 度=2，节点 1 度=1，节点 2 度=2（假设无向图，边对称存储），则 CSR 为： ``` indptr = [0, 2, 3, 5] # 节点0邻居从0开始(2个)，节点1从2开始(1个)，节点2从3开始(2个) indices = [1, 2, 2, 0, 1] # 按节点顺序排列的邻居 data = [0.5, 1.0, 0.8, 0.5, 1.0] # 对应权重（无向边存储两次） ``` 要获取节点 0 的所有邻居和权重，只需 `indices[indptr[0]:indptr[1]]` 和 `data[indptr[0]:indptr[1]]`，时间复杂度 $O(1)$。

优点：行遍历高效，内存开销小（相比稠密矩阵）。缺点：列遍历（如按目标节点聚合）效率低，需要额外转换或扫描。

1.3.3 压缩稀疏列（Compressed Sparse Column, CSC）

与 CSR 类似，但按列压缩。`indptr` 指向每列的起始位置。适合需要频繁列操作的场景，如图拉普拉斯矩阵的某些计算。在 PyTorch Geometric 等库中，通常内部使用 CSR 或更高效的稀疏张量（Sparse Tensor） 表示（基于 `torch.sparse`），它支持高效的稀疏-稀疏矩阵乘法和稀疏-稠密矩阵乘法。

```python

使用 SciPy 构建 CSR 邻接矩阵示例

import numpy as np import scipy.sparse as sp

src = np.array([0, 0, 1, 2, 2]) dst = np.array([1, 2, 2, 0, 1]) data = np.array([0.5, 1.0, 0.8, 0.5, 1.0]) n = 3 # 节点数

构建 COO

A_coo = sp.coo_matrix((data, (src, dst)), shape=(n, n)) print("COO:\n", A_coo)

转换为 CSR

A_csr = A_coo.tocsr() print("\nCSR indptr:", A_csr.indptr) print("CSR indices:", A_csr.indices) print("CSR data:", A_csr.data)

访问节点 0 的邻居

node_0_neighbors = A_csr[0].indices # 或 A_csr.indices[A_csr.indptr[0]:A_csr.indptr[1]] print("\nNode 0 neighbors:", node_0_neighbors) ```

选择策略：

• **数据加载/序列化**：COO 最方便。
• **GNN 训练（消息传递）**：CSR 或框架内置稀疏张量，因为聚合操作通常是“按源节点收集邻居”