GraphSAGE阈值分层从入门到精通 - 第1节
1.1 图的基本概念
图（Graph）是描述实体之间复杂关系的数学结构，也是图神经网络处理的核心数据对象。与传统的欧几里得数据（图像、文本）不同，图数据具有非欧几里得、不规则邻域和全局拓扑依赖三大特性。
1.1.1 节点与边
- 节点（Node / Vertex）：图中的基本实体单元，代表一个对象或数据点。在社交网络中，节点表示用户；在分子图中，节点表示原子。
- 边（Edge）：连接两个节点的关系线，表示实体之间的相互作用或连接。边可以是有向的（如关注关系）或无向的（如朋友关系）。
- 属性（Attribute）：节点和边通常携带特征向量。例如，节点特征可以是用户的年龄、性别；边特征可以是关系的权重或类型。
关键理解：图神经网络的本质是学习如何利用节点自身的特征以及邻居节点的特征，通过消息传递机制更新节点表示。节点和边的属性质量直接影响模型性能。
1.1.2 邻接矩阵
邻接矩阵（Adjacency Matrix）是图最标准的代数表示方式。对于一个包含 N 个节点的图，邻接矩阵 A 是一个 N × N 的方阵：
- 若节点 i 与节点 j 之间存在边，则 Aij = 1（无权图）或权重值（有权图）；
- 若不存在边，则 Aij = 0。
- 无向图的邻接矩阵是对称矩阵；有向图则不一定对称。
| 图类型 | 邻接矩阵特点 | 存储复杂度 | 典型应用 |
|---|---|---|---|
| 无向无权图 | 对称，元素为 0 或 1 | O(N²) | 社交网络、分子结构 |
| 有向无权图 | 非对称，元素为 0 或 1 | O(N²) | 网页链接、知识图谱 |
| 有权图 | 元素为实数权重 | O(N²) | 交通网络、推荐系统 |
| 稀疏图 | 大部分元素为 0 | O(E)（邻接表） | 大规模真实图数据 |
工程注意：真实图数据通常是高度稀疏的（E ≪ N²），直接使用邻接矩阵存储会浪费大量内存。GraphSAGE 等现代 GNN 框架通常采用邻接表或 COO 格式存储，配合采样策略降低计算复杂度。
1.2 图的表示方法
在实际工程中，图数据需要转换为计算机可处理的数值形式。除了邻接矩阵，还有多种表示方法适用于不同场景：
1.2.1 常用表示方法对比
| 表示方法 | 存储结构 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 邻接矩阵 | 二维数组 | O(N²) | 稠密图、小规模图 |
| 邻接表 | 链表数组 | O(N + E) | 稀疏图、大规模图 |
| 边列表 | 三元组 (u, v, w) | O(E) | 图流处理、分布式存储 |
| COO 格式 | 行索引 + 列索引 + 值 | O(2E + E) | GPU 加速、PyG/DGL 框架 |
| CSR 格式 | 行偏移 + 列索引 + 值 | O(N + E) | 高效矩阵运算、图神经网络 |
GraphSAGE 选型提示：GraphSAGE 采用邻接表 + 采样策略，每次只聚合固定数量的邻居节点，避免全图邻接矩阵带来的 O(N²) 爆炸。在实现时，推荐使用 CSR 格式存储图结构，配合 torch.sparse 或 dgl.graph 进行高效计算。
1.2.2 图的属性与类型
根据节点和边的属性丰富程度，图可以进一步分类：
- 同构图（Homogeneous Graph）：所有节点类型相同，边类型相同。例如，社交网络中的用户-用户好友关系。
- 异构图（Heterogeneous Graph）：包含多种节点类型或边类型。例如，学术网络中作者、论文、会议三种节点，以及撰写、引用、发表三种边。
- 属性图（Attributed Graph）：节点和边携带多维特征向量。GraphSAGE 的核心输入就是节点属性矩阵 X ∈ ℝN×d。
- 动态图（Dynamic Graph）：图结构随时间演化，边和节点会新增或删除。
1.3 图神经网络发展简史
图神经网络的发展经历了从理论奠基到工业落地的快速演进，以下为关键里程碑：
| 年份 | 模型/方法 | 核心贡献 | 对 GraphSAGE 的影响 |
|---|---|---|---|
| 2005 | GNN（Scarselli 等） | 首次提出图神经网络的递归框架 | 奠定消息传递范式基础 |
| 2013 | DeepWalk | 将图节点嵌入与 Word2Vec 结合 | 启发无监督节点表示学习 |
| 2016 | GCN（Kipf & Welling） | 提出一阶谱图卷积，层式聚合 | GraphSAGE 的聚合函数设计参考 |
| 2017 | GraphSAGE | 提出归纳式学习 + 邻居采样 | 本课程核心模型 |
| 2018 | GAT（Veličković 等） | 引入注意力机制聚合邻居 | 改进 GraphSAGE 的聚合权重 |
| 2019 | GIN（Xu 等） | 证明图同构表达能力上限 | 指导 GraphSAGE 聚合函数选择 |
| 2020+ | 大规模 GNN 系统 | 分布式训练、异构图、动态图 | GraphSAGE 成为工业基线 |
GraphSAGE 的历史定位：在 GCN 提出后，图神经网络面临两大瓶颈：① 全图训练无法扩展到百万级节点；② 直推式（Transductive）学习无法处理新节点。GraphSAGE 通过邻居采样和归纳式（Inductive）学习解决了这两个问题，成为第一个真正可工业部署的大规模 GNN 框架。
1.4 本章小结
- 图的基本构成：节点（实体）、边（关系）、邻接矩阵（代数表示）。
- 图的表示方法：邻接矩阵适合稠密小图，邻接表/CSR 适合大规模稀疏图，GraphSAGE 采用采样 + 邻接表策略。
- 发展简史：从 GNN 递归框架到 GCN 谱卷积，再到 GraphSAGE 的归纳式采样学习，GNN 逐步走向工业级大规模应用。
- GraphSAGE 定位：第一个可处理百万级节点、支持归纳学习的 GNN 框架，是后续 GAT、GIN 等模型的基础架构。