图论基础与图数据表示

图，作为描述对象之间二元关系的数学结构，是复杂系统建模的自然工具。从社交网络中的人际关系，到分子中的原子连接，再到知识库中的实体关联，图数据无处不在。理解图的基本概念和数学表示，是进入图神经网络世界的第一步。本章将系统介绍图论的基础知识，包括图的定义、类型、核心矩阵表示及其性质，并通过实际案例展示图数据在社交网络、分子结构、知识图谱等领域的应用，为后续章节的图神经网络学习奠定坚实的数学基础。

图的基本概念与数学表示

图（Graph）是一种非线性的数据结构，由顶点（Vertex）和边（Edge）组成，用于刻画实体之间的关系。在数学上，图定义为有序对 $G = (V, E)$，其中 $V$ 是顶点（或节点）的非空有限集合，$E$ 是边的集合，每条边是顶点的一个无序对（无向图）或有序对（有向图）。例如，在一个包含3个顶点的简单无向图中，若顶点集 $V = \{v_1, v_2, v_3\}$，边集 $E = \{\{v_1, v_2\}, \{v_2, v_3\}\}$，则图 $G$ 描述了顶点 $v_1$ 与 $v_2$ 相连、$v_2$ 与 $v_3$ 相连的关系，而 $v_1$ 与 $v_3$ 之间无直接连接。

顶点的数量 $|V|$ 称为图的阶（Order），边的数量 $|E|$ 称为图的大小（Size）。在社交网络中，顶点可以表示用户，边表示好友关系；在分子结构中，顶点表示原子，边表示化学键；在交通网络中，顶点表示城市，边表示道路。这种抽象使得图成为跨领域数据建模的通用语言。

除了集合表示，图还可以用多种方式可视化。可视化不仅帮助直观理解图结构，还能揭示聚类、中心性等隐含模式。例如，下图展示了一个包含4个顶点和3条边的简单无向图：

```mermaid graph TD A[顶点 v1] --> B[顶点 v2] B --> C[顶点 v3] A --> D[顶点 v4] ```

在这个图中，边用直线连接顶点，没有方向箭头，表示关系是相互的。需要注意的是，Mermaid 默认绘制有向图，要表示无向边，可以使用 `---` 而非 `-->`。例如，一个无向图可以写为 `A --- B`。但为了清晰，上图使用有向箭头仅作连接示意，实际无向图应去掉箭头。

在实际应用中，图数据通常以结构化的形式存储，如边列表（Edge List）、邻接表（Adjacency List）或邻接矩阵（Adjacency Matrix）。边列表是最简单的表示，每行记录一条边的两个端点；邻接表为每个顶点维护一个列表，列出与其直接相连的邻居；邻接矩阵则是 $|V| \times |V|$ 的矩阵，元素 $A_{ij}$ 表示顶点 $i$ 与 $j$ 之间是否存在边。这些表示各有优劣：边列表节省空间但查询邻居效率低；邻接表适合稀疏图，查询邻居快；邻接矩阵便于矩阵运算，但占用 $O(|V|^2)$ 空间，仅适用于小规模或稠密图。后续章节将详细讨论邻接矩阵及其衍生矩阵，因为它们是图神经网络运算的核心。

图的类型与分类

图可以根据边的方向、权重、重复性等属性进行分类，不同分类对应不同的应用场景和算法设计。

无向图与有向图

最基础的分类是根据边是否有方向。在无向图（Undirected Graph）中，边没有方向，关系是对称的。例如，在Facebook好友关系中，若用户A是用户B的好友，则用户B也是用户A的好友，这种关系用无向边表示。无向图的边集 $E$ 由无序对组成，即 $\{u, v\} = \{v, u\}$。数学上，无向图的邻接矩阵是对称的，即 $A_{ij} = A_{ji}$。

有向图（Directed Graph，或Diraph）的边具有方向，称为有向边或弧（Arc）。例如，在Twitter或微博中，用户A关注用户B，但用户B不一定关注用户A，这种单向关系用从A指向B的有向边表示。有向图的边集由有序对组成，$(u, v) \neq (v, u)$。邻接矩阵一般不对称：$A_{ij} = 1$ 表示存在从顶点 $i$ 到 $j$ 的边，而 $A_{ji}$ 可能为0。下图对比了无向图和有向图：

```mermaid graph TD subgraph 无向图 A[用户A] --- B[用户B] B --- C[用户C] end subgraph 有向图 D[用户A] --> E[用户B] E --> F[用户C] end ```

在有向图中，顶点的度分为入度（In-degree）和出度（Out-degree）。入度 $d^{in}(v)$ 是指向顶点 $v$ 的边数，出度 $d^{out}(v)$ 是从 $v$ 指出的边数。总度 $d(v) = d^{in}(v) + d^{out}(v)$。无向图中，度就是相连边的数量，因为每条边对两个顶点的度各贡献1。

加权图与未加权图

若边带有数值权重（Weight），则称为加权图（Weighted Graph）。权重可以表示关系的强度、距离、成本等。例如，在道路网络中，边权重可以是两城市间的距离或行驶时间；在社交网络中，权重可以表示用户间互动的频率。加权图的邻接矩阵元素 $A_{ij}$ 为实数，表示边 $(i,j)$ 的权重；若无边，则通常为0或无穷大。未加权图可视为所有权重为1的特例。

多重图与自环

在简单图（Simple Graph）中，任意两个顶点之间最多有一条边，且没有顶点连接到自身的边（自环，Loop）。然而，许多现实场景需要更丰富的结构。多重图（Multigraph）允许两个顶点之间存在多条边，例如，两个城市之间有多条公路或航线，每条边可以有不同的权重或类型。自环表示顶点与自身的连接，在某些应用中有意义，例如在状态转移图中，一个状态可能转移到自身。

其他重要分类

• **稀疏图与稠密图**：若边数 $|E|$ 远小于 $|V|^2$，图是稀疏的（Sparse）；否则是稠密的（Dense）。大多数现实图（如社交网络、互联网）是稀疏的，边数大致与顶点数成线性或多项式关系，而非平方关系。稀疏性对算法设计和存储有关键影响：邻接表更适合稀疏图，而邻接矩阵在稠密图上效率较高。
• **连通图**：在无向图中，若任意两个顶点之间都存在路径，则图是连通的（Connected）。否则，图由多个连通分量（Connected Component）组成。在有向图中，强连通（Strongly Connected）指任意顶点 $u$ 到 $v$ 和 $v$ 到 $u$ 都存在路径；弱连通（Weakly Connected）指忽略方向后图是连通的。连通性是图分析的基础，影响信息传播和网络鲁棒性。
• **树与森林**：树（Tree）是无环的连通图。树有重要性质：$|E| = |V| - 1$，且任意两点间有唯一路径。森林（Forest）是无环的图，可能不连通，由多棵树组成。树结构在层次组织和分类中常见。
• **平面图**：若图可以画在平面上使得边仅在顶点处相交，则称为平面图（Planar Graph）。许多网络（如电路设计、地图）是平面的，平面图有特定的数学性质（如欧拉公式）。

这些分类并非互斥，一个图可以同时属于多个类别。例如，一个社交网络图可能是无向、未加权、稀疏且连通的。理解图的类型有助于选择合适的数学模型和算法。

邻接矩阵：图的核心数学表示

邻接矩阵（Adjacency Matrix）是图最常用的矩阵表示之一，尤其在图神经网络中作为基础运算对象。对于具有 $n = |V|$ 个顶点的图，邻接矩阵 $A \in \mathbb{R}^{n \times n}$ 定义为：

$$ A_{ij} = \begin{cases} w_{ij} & \text{如果顶点 } i \text{ 与 } j \text{ 之间有边，且边权重为 } w_{ij} \\ 0 & \text{否则} \end{cases} $$

其中，$w_{ij}$ 是边 $(i,j)$ 的权重。对于未加权图，通常取 $w_{ij}=1$。顶点通常按固定顺序编号（如 $1,2,\dots,n$），矩阵的行和列对应顶点。

邻接矩阵的性质

1. 对称性：无向图的邻接矩阵是对称矩阵，因为若 $i$ 与 $j$ 相连，则 $j$ 与 $i$ 相连，故 $A_{ij} = A_{ji}$。有向图一般不对称。 2. 对角元素：在简单图中，没有自环，因此对角元素 $A_{ii}=0$。若允许自环，则 $A_{ii}$ 可能非零。 3. 稀疏性：现实图通常稀疏，即矩阵中大部分元素为0。例如，一个拥有100万用户的社交网络，平均好友数可能只有几百，因此邻接矩阵的非零元素占比极小。稀疏存储（如压缩稀疏行格式）可大幅节省内存。 4. 矩阵幂的意义：邻接矩阵的 $k$ 次幂 $A^k$ 的元素 $(A^k)_{ij}$ 表示从顶点 $i$ 到 $j$ 长度为 $k$ 的路径数量（在未加权图中）。例如，$A^2$ 的元素 $ (A^2)_{ij} = \sum_{k} A_{ik} A_{kj} $，统计了通过中间顶点 $k$ 的两步路径数。这一性质在计算图上的随机游走或传播模型时有用。

示例：构建邻接矩阵

考虑一个简单的社交网络子图，包含4个用户：Alice、Bob、Charlie、Diana。好友关系如下：Alice与Bob、Charlie是好友；Bob与Diana是好友；Charlie与Diana是好友。这是一个无向、未加权图。

首先，给顶点编号：Alice=1, Bob=2, Charlie=3, Diana=4。边集为 $E = \{\{1,2\}, \{1,3\}, \{2,4\}, \{3,4\}\}$。对应的邻接矩阵为：

$$ A = \begin{bmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{bmatrix} $$

矩阵对称，因为关系是相互的。第 $i$ 行非零元素个数即为顶点 $i$ 的度：Alice和Diana度为2，Bob和Charlie度为2。

代码示例：使用 NetworkX 创建图并获取邻接矩阵

Python 的 NetworkX 库是图分析的标准工具。以下代码构建上述社交网络图，并输出邻接矩阵：

```python import networkx as nx import numpy as np

创建无向图

G = nx.Graph()

添加顶点（可选，添加边时自动创建）

G.add_nodes_from([1, 2, 3, 4])

添加边

edges = [(1, 2), (1, 3), (2, 4), (3, 4)] G.add_edges_from(edges)

获取邻接矩阵（以密集矩阵形式）

A = nx.adjacency_matrix(G, nodelist=sorted(G.nodes())).todense() print("邻接矩阵 A:") print(A)

计算度矩阵

degree_sequence = [d for n, d in G.degree()] D = np.diag(degree_sequence) print("\n度矩阵 D:") print(D)

计算拉普拉斯矩阵 L = D - A

L = D - A print("\n拉普拉斯矩阵 L:") print(L) ```

输出为： ``` 邻接矩阵 A: [[0. 1. 1. 0.] [1. 0. 0. 1.] [1. 0. 0. 1.] [0. 1. 1. 0.]]

度矩阵 D: [[2. 0. 0. 0.] [0. 2. 0. 0.] [0. 0. 2. 0.] [0. 0. 0. 2.]]

拉普拉斯矩阵 L: [[ 2. -1. -1. 0.] [-1. 2. 0. -1.] [-1. 0. 2. -1.] [ 0. -1. -1. 2.]] ```

这段代码同时计算了度矩阵 $D$ 和拉普拉斯矩阵 $L$，为下一节铺垫。

邻接矩阵的局限性

尽管邻接矩阵简洁且便于矩阵运算，但它也有缺点。主要问题是空间复杂度 $O(n^2)$，对于大规模稀疏图（如互联网图有数十亿顶点）不切实际。此时，邻接表（Adjacency List）更高效：为每个顶点存储一个邻居列表，空间复杂度 $O(|E|)$。邻接表适合遍历邻居，但随机访问边是否存在需 $O(\deg(v))$ 时间。在图神经网络中，由于需要批量处理图数据，邻接矩阵（或其稀疏表示）仍是常用形式，因为GPU加速的稀疏矩阵乘法效率高。

度矩阵与拉普拉斯矩阵

邻接矩阵 alone 不足以捕捉图的全局结构特性。度矩阵（Degree Matrix）和拉普拉斯矩阵（Laplacian Matrix）是两个关键衍生矩阵，广泛应用于图信号处理、图卷积和谱聚类。

度矩阵

度矩阵 $D$ 是一个 $n \times n$ 的对角矩阵，对角元素为各顶点的度。对于无向图，$D_{ii} = d_i = \sum_j A_{ij}$（因为 $A$ 对称，行和等于列和）。对于有向图，可以定义入度矩阵、出度矩阵或总度矩阵。通常，无向图的度矩阵定义为：

$$ D = \mathrm{diag}(d_1, d_2, \dots, d_n) $$

其中 $d_i$ 是顶点 $i$ 的度。在上例中，度矩阵如代码输出所示，所有顶点度为2，故 $D = 2I$。

拉普拉斯矩阵

拉普拉斯矩阵（简称拉普拉斯）定义为度矩阵与邻接矩阵之差：

$$ L = D - A $$

拉普拉斯矩阵 $L$ 是对称半正定矩阵（对于无向图），具有以下重要性质：

• **行和为零**：每一行元素之和为 $d_i - \sum_j A_{ij} = 0$，因为 $d_i = \sum_j A_{ij}$。因此，$L$ 有一个特征值0，对应的特征向量为全1向量 $\mathbf{1}$。
• **对称性**：由于 $D$ 和 $A$ 都对称，$L$ 对称。
• **半正定性**：对于任意向量 $\mathbf{x} \in \mathbb{R}^n$，二次型 $\mathbf{x}^\top L \mathbf{x} = \frac{1}{2} \sum_{i,j} A_{ij} (x_i - x_j)^2 \geq 0$。这可通过展开证明：

$$ \mathbf{x}^\top L \mathbf{x} = \mathbf{x}^\top D \mathbf{x} - \mathbf{x}^\top A \mathbf{x} = \sum_i d_i x_i^2 - \sum_{i,j} A_{ij} x_i x_j. $$ 由于 $A_{ij}=A_{ji}$，可以重写为： $$ \mathbf{x}^\top L \mathbf{x} = \frac{1}{2} \sum_{i,j} A_{ij} (x_i - x_j)^2. $$ 该式表明拉普拉斯二次型衡量了向量 $\mathbf{x}$ 在图上的平滑度：若相邻顶点值差异大，则二次型大；若 $\mathbf{x}$ 在连通分量上为常数，则二次型为0。这一性质使拉普拉斯成为图分割和谱聚类的核心。

归一化拉普拉斯矩阵

原始拉普拉斯矩阵的尺度受顶点度影响。为消除度的影响，常使用归一化拉普拉斯矩阵。常见形式有两种：

1. 对称归一化拉普拉斯（Symmetric Normalized Laplacian）： $$

拉普拉斯矩阵的谱分解与图傅里叶变换

拉普拉斯矩阵 $L = D - A$ 的谱性质（特征值和特征向量）揭示了图的深层结构。由于 $L$ 是对称半正定矩阵，根据谱定理，它可正交对角化：存在正交矩阵 $U$ 和对角矩阵 $\Lambda$，使得 $L = U \Lambda U^\top$，其中 $\Lambda = \mathrm{diag}(\lambda_1, \lambda_2, \dots, \lambda_n)$，$0 = \lambda_1 \le \lambda_2 \le \dots \le \lambda_n$ 是 $L$ 的特征值，$U$ 的列是对应的正交特征向量。

特征值的图含义

特征值 $\lambda_k$ 反映了图的连通性和聚类结构：

• **最小特征值 $\lambda_1 = 0$**：对应的特征向量为全1向量 $\mathbf{1}$，因为 $L\mathbf{1} = (D-A)\mathbf{1} = D\mathbf{1} - A\mathbf{1} = \mathbf{d} - \mathbf{d} = \mathbf{0}$，其中 $\mathbf{d}$ 是度向量。特征值0的重数等于图的连通分量数。若图连通，则0是单重特征值；若图有 $c$ 个连通分量，则0的重数为 $c$，对应特征向量在每個连通分量上为常数，不同分量间正交。
• **代数连通度（Algebraic Connectivity）**：第二小特征值 $\lambda_2$（称为Fiedler值）衡量图的连通强度。$\lambda_2$ 越大，图越难被分割，连通性越好；$\lambda_2 = 0$ 表示图不连通。Fiedler向量（对应 $\lambda_2$ 的特征向量）可用于图分割：通过将顶点按特征向量值排序并切割，得到近似最小割集。
• **特征值间隙（Spectral Gap）**：$\lambda_2$ 与 $\lambda_1=0$ 的差距称为谱隙。大谱隙表示图有一个明显的簇结构；小谱隙表示图更均匀。

图傅里叶变换

在信号处理中，傅里叶变换将时域信号转换到频域。类似地，图傅里叶变换（Graph Fourier Transform, GFT）将定义在图顶点上的信号（即 $\mathbf{x} \in \mathbb{R}^n$，其中 $x_i$ 是顶点 $i$ 的值）转换到图谱域（由拉普拉斯特征向量张成的空间）。

定义图傅里叶变换为： $$ \hat{\mathbf{x}} = U^\top \mathbf{x} $$ 其中 $U = [\mathbf{u}_1, \mathbf{u}_2, \dots, \mathbf{u}_n]$ 是 $L$ 的特征向量矩阵（正交归一）。变换后 $\hat{x}_k = \mathbf{u}_k^\top \mathbf{x}$ 是信号 $\mathbf{x}$ 在第 $k$ 个谱基上的系数，表示信号在频率 $\lambda_k$ 上的分量。低频对应平滑变化（相邻顶点值相似），高频对应剧烈变化。

逆变换为：