第3章：图数据结构与表示归纳总结
图，说白了就是由节点和边构成的集合。你在社交网络、分子结构、知识图谱里都能见到它。但我刚接触图神经网络那会儿，反而被“图怎么喂给模型”的问题卡了三天。嗯，这章咱们就把图的数据结构、表示方式和归纳偏好一次说清楚。
3.1 图的基本定义与元素
一个图可以用 G = (V, E) 来表示。其中 V 是节点集合，E 是边集合。每条边连接两个节点。举个例子，我有5个用户，他们之间有7个关注关系，那就是一个5节点7边有向图。
我个人习惯把图分成下面几类，好记又好用：
| 分类维度 | 类型 | 说明 |
|---|---|---|
| 边方向 | 有向图 / 无向图 | 关注关系用有向，好友关系用无向 |
| 边权重 | 有权图 / 无权图 | 权重可以表示相似度、距离、交互次数 |
| 节点属性 | 属性图 / 纯结构图 | 大部分实际场景都是属性图，节点和边都带特征 |
| 时间维度 | 静态图 / 动态图 | 用户行为随时间变化，就是动态图 |
3.2 图的存储结构对比
图要放进计算机，就得选一种存储方式。最常用三种：邻接矩阵、邻接表、边列表。你想想看，每种都各有坑，选错了后面寸步难行。
- 邻接矩阵：用
n × n的矩阵存，A[i][j]=1表示 i→j 有边。优点是查边 O(1)；缺点是稀疏时浪费内存，n=100万时矩阵存不下。 - 邻接表：每个节点存一个邻居列表。空间 O(|V|+|E|)，适合稀疏图。我在项目中处理亿级节点图时就用的邻接表。
- 边列表：直接存 (源节点, 目标节点) 对。适合简单分析，但查邻居慢。
下面这张图直观对比了三种存储方式，以及它们的数据访问特点：
3.3 图的基本统计特征
拿到图之后，我一般先用几个统计量摸摸底。这也是特征工程和模型选型的前置工作。
- 节点度数：每个节点连接的边数。有向图分入度和出度。度数分布能看出图中是否存在枢纽节点。
- 路径长度：两个节点之间的最短跳数。平均路径长度可以衡量图的“紧凑”程度。
- 聚类系数：衡量节点邻居之间互相连接的紧密程度。社交网络里这个值通常很高。
- 连通分量：图里有多少个互相不连通的子图。孤立点也算一个分量。
我在做风控反欺诈项目时，就发现社区聚类系数异常低的群组往往是羊毛党团伙——他们之间没真实关系，全是一个人注册一堆小号。聚类系数一下就给揪出来了。
3.4 图神经网络的输入表示
传统机器学习需要固定大小的特征向量，但图是变长、非欧的结构。咋办？图神经网络（GNN）的解法是：把每个节点用邻居信息来更新自己的嵌入。
具体来说，输入层需要三样东西：
- 节点特征矩阵：形状
N × F，N 是节点数，F 是每个节点的特征维度。 - 邻接矩阵或邻接表：告诉模型哪些节点连接在一起。
- （可选）边特征：比如边的权重、类型，形状
E × D。
3.5 归纳 vs 直推：GraphSAGE 的立场
图表示学习有两大流派：直推式（Transductive）和归纳式（Inductive）。总结成一句话：直推式只会在训练时见过的节点上做推理，一旦来了新节点就得重新训练；归纳式能泛化到没见过的节点。
| 特性 | 直推式（如 GCN） | 归纳式（如 GraphSAGE） |
|---|---|---|
| 训练时见过节点 | 所有节点都必须在训练集中 | 训练集和推理集的节点可以不同 |
| 新节点推理 | 需要重新训练或做矩阵分解 | 直接采样邻居、聚合特征，一次 forward 即可 |
| 适用场景 | 整个图固定不变 | 图不断增长，如社交网络新用户、电商新商品 |
| 参数量 | 每个节点有独立的嵌入向量 | 共享一套聚合函数参数，不依赖具体节点ID |
GraphSAGE 的“S”就是 Sample and AggreGatE，它天生是归纳式的。你可能会有疑问：归纳式就一定比直推式好那？不一定。如果图是静态的、节点不会增加，直推式的准确率通常还高一点。但现实世界图一直在变，你想想看，淘宝每天上架几百万新商品，用直推式得重新训练整个图，成本谁扛得住？
好了，图的数据结构和表示是后续一切操作的地基。下一站我们就动手搭建 GraphSAGE 的采样和聚合流程，到时候邻接表、特征矩阵全都会用上。