2、图的基本概念与表示方法
2.1 到底什么是图？
说实话，第一次接触“图”这个概念的人，很容易想到柱状图、折线图那些。但咱们这儿说的图，完全不同。
图，说白了就是一组节点和连接它们的边。你想想看，社交网络里每个人是一个节点，好友关系就是边；化合物里每个原子是节点，化学键就是边。就这么简单。
我刚开始做QSAR项目时，拿到一个分子数据集，第一反应就是“这怎么用图表示？”后来发现，你只要把原子当节点，键当边，分子的3D结构自然就成了一幅图。这个视角转换，可以说是整个GNN应用的起点。
2.2 图的数学定义
咱们从数学上再捋一捋。一个图 G 可以用一个二元组表示：
G = (V, E)- V：节点集合，也叫顶点集。比如 {v₁, v₂, v₃, …, vₙ}
- E：边集合，连接两个节点的关系。比如 {(v₁, v₂), (v₂, v₃)}
举个例子，一个水分子 H₂O：
V = {O, H₁, H₂}
E = {(O, H₁), (O, H₂)}你看，两个氧氢键就是两条边。嗯，这里要注意：边有没有方向？权重大小？这直接决定了你用哪种图来处理。
2.3 图的表示方法
图在计算机里怎么存？我个人习惯用三种方法，每种各有利弊。
2.3.1 邻接矩阵
这是最直观的表示。假设有 n 个节点，就建一个 n×n 的矩阵 A。如果节点 i 和节点 j 之间有边，A[i][j] = 1，否则为 0。
# 三个节点的简单图
# 节点1-2相连，节点2-3相连
# 邻接矩阵：
# 1 2 3
# 1 0 1 0
# 2 1 0 1
# 3 0 1 0代码实现也很直接：
import numpy as np
n = 3
A = np.zeros((n, n))
A[0, 1] = 1 # 节点1到节点2
A[1, 0] = 1 # 节点2到节点1
A[1, 2] = 1 # 节点2到节点3
A[2, 1] = 1 # 节点3到节点2
print(A)2.3.2 邻接表
邻接表只存有连接的边。每个节点后面挂一个链表，记录它连到了哪些节点。
# 同样的图，邻接表表示：
# 节点1: [2]
# 节点2: [1, 3]
# 节点3: [2]Python里用字典实现很顺手：
graph = {
0: [1],
1: [0, 2],
2: [1]
}
# 加一条边
graph[0].append(2)
graph[2].append(0)2.3.3 边列表
最省脑子的一种：直接把所有边列出来。
edges = [(0, 1), (1, 2)]
# 或者带权重的边
edges_with_weight = [(0, 1, 0.5), (1, 2, 1.2)]在我早期的一个项目中，边列表格式最方便做数据清洗。你只要读入CSV，每一行就是一条边。简单粗暴，但图大了之后查询效率很低。
2.4 图的类型
不同类型的图，表示方法有细微差别，但都会落到上面三种基础方法上。
| 图类型 | 特点 | 常用表示 | QSAR场景 |
|---|---|---|---|
| 无向图 | 边没有方向 | 对称邻接矩阵 | 化学键（不分方向） |
| 有向图 | 边有方向 | 非对称邻接矩阵 | 蛋白-配体结合方向 |
| 加权图 | 边带有权重 | 权重矩阵/带权边列表 | 键能、距离、作用力强度 |
| 带属性图 | 节点/边有特征向量 | 特征矩阵 + 邻接矩阵 | 原子类型、电荷、键级 |
我做QSAR时，最常见的其实是带属性图。每个原子节点有特征（原子类型、杂化态、部分电荷），每条化学键边有特征（键级、键长）。这些属性进入GNN后，才是真正发挥价值的地方。
2.5 图的基本属性
聊几个你马上就会遇到的概念。
- 度（Degree）：一个节点相连的边数。在分子里，碳的度是4，氧的度是2。度越高的节点，在GNN中汇聚的信息越多。
- 路径（Path）：从一个节点到另一个节点走过的节点序列。路径长度就是边的数量。
- 连通分量：图中互相连通的最大子图。一个分子通常就是一个连通分量。
- 直径：图中任意两个节点之间最短路径的最大值。分子的直径反映了它的“长度”。
2.6 图的稀疏性与存储选择
我曾经在一次分子筛筛选中，用了邻接矩阵存3000个分子。每个分子大概50个原子，计算到一半内存爆了。后来换成邻接表，内存占用从300MB降到5MB。为什么？因为分子图极其稀疏。
一个分子图，每个原子连的键很少，平均度也就2-4。也就是邻接矩阵里97%以上都是零。这就是稀疏性。
# 稀疏矩阵存储 - scipy版
from scipy.sparse import csr_matrix
# 一个50个原子的分子，平均度3
n = 50
rows = [0, 0, 1, 1, 2, ...] # 来自邻接表的行索引
cols = [1, 2, 0, 2, 1, ...] # 列索引
data = [1, 1, 1, 1, 1, ...] # 边权重
A_sparse = csr_matrix((data, (rows, cols)), shape=(n, n))
# 占内存：只存非零元素
print(A_sparse.shape) # (50, 50)2.7 本章知识结构图
2.8 怎么选？我的建议
到这里你可能会问：这么多表示方法，项目里到底用哪种？我说说我的经验。
- 规模小（节点 < 1000）：邻接矩阵最省心。查边快，实现简单，不用考虑稀疏性。
- 规模中等（1000-10000）：邻接表或者稀疏矩阵。PyG、DGL这些框架底层就是稀疏格式，直接用。
- 超大图（百万节点以上）：必须用邻接表+采样策略。全图没法一次计算。
- QSAR场景：分子图通常几十到几百个原子，用邻接矩阵或稀疏矩阵都行。我个人习惯用稀疏矩阵，因为后面要做批处理。