2. 图论基础：图的定义与表示、有向图与无向图、度、邻接矩阵与邻接表
在构建反欺诈图谱之前，必须理解图（Graph）这一核心数据结构。图由节点（Vertex/Node）和边（Edge）组成，用于描述实体之间的复杂关系。在反欺诈场景中，节点可以是用户、设备、IP地址、订单等，边则代表它们之间的交互行为（如登录、转账、共享设备）。
2.1 图的定义与基本要素
图 G 可以形式化定义为 G = (V, E)，其中：
- V：非空节点集合，V = {v₁, v₂, ..., vₙ}。
- E：边集合，E ⊆ V × V，每条边连接两个节点。
反欺诈视角： 在反欺诈图谱中，节点通常代表实体（如用户账号、手机号、设备指纹），边代表关联行为（如同一设备登录多个账号、同一手机号注册多个用户）。这种结构天然适合检测团伙欺诈。
2.2 有向图与无向图
根据边是否具有方向性，图分为两种基本类型：
| 类型 | 定义 | 边表示 | 反欺诈应用示例 |
|---|---|---|---|
| 无向图 | 边没有方向，表示对称关系 | (u, v) 与 (v, u) 等价 | 共享同一设备、共用同一IP |
| 有向图 | 边有方向，表示非对称关系 | u → v 与 v → u 不同 | 转账行为（A→B）、关注关系 |
关键区别： 无向图适用于“共同持有”类关系（如共用设备），有向图适用于“单向行为”类关系（如资金流向）。在GraphSAGE建模时，有向图通常需要转化为无向图或保留双向边特征。
2.3 度（Degree）
度是衡量节点连接数量的重要指标，在不同图类型中有不同定义：
- 无向图：节点 v 的度 deg(v) = 与该节点相连的边的数量。
- 有向图：
- 出度（Out-degree）：从该节点出发的边数。
- 入度（In-degree）：指向该节点的边数。
反欺诈应用： 在欺诈检测中，异常节点的度往往呈现极端分布。例如，一个设备关联了数百个用户账号（高入度），或一个账号向大量陌生账户转账（高出度），这些都是典型的欺诈信号。
2.4 图的表示方法：邻接矩阵与邻接表
在计算机中存储图结构，最常用的两种方式是邻接矩阵和邻接表。选择哪种方式直接影响图神经网络的训练效率和内存占用。
| 表示方法 | 存储结构 | 空间复杂度 | 查询边 (u,v) 时间复杂度 | 适用场景 |
|---|---|---|---|---|
| 邻接矩阵 | |V| × |V| 二维数组 | O(|V|²) | O(1) | 稠密图、小规模图 |
| 邻接表 | 每个节点维护一个邻居列表 | O(|V| + |E|) | O(deg(v)) | 稀疏图、大规模图（反欺诈图谱常用） |
2.4.1 邻接矩阵示例
对于包含 4 个节点的无向图，邻接矩阵是一个 4×4 的对称矩阵：
# 节点: [A, B, C, D]
# 边: A-B, A-C, B-C, C-D
邻接矩阵:
A B C D
A [0, 1, 1, 0]
B [1, 0, 1, 0]
C [1, 1, 0, 1]
D [0, 0, 1, 0]2.4.2 邻接表示例
同样的图，使用邻接表存储：
邻接表:
A -> [B, C]
B -> [A, C]
C -> [A, B, D]
D -> [C]
GraphSAGE 选择： 反欺诈图谱通常包含数百万节点和数亿条边，属于典型的稀疏图。GraphSAGE 的邻居采样机制天然适配邻接表结构——只需根据节点 ID 快速获取其邻居列表，无需遍历整个矩阵。因此，在课程后续的模型实现中，我们将统一使用邻接表作为图的存储格式。
2.5 反欺诈图谱构建实战要点
在开始 GraphSAGE 模型训练前，需要将原始数据转换为图结构。以下是关键步骤：
- 节点定义：确定哪些实体作为节点（用户、设备、IP、手机号等）。
- 边定义：根据业务规则建立关联（如“同一设备登录”建立设备-用户边）。
- 图存储：使用邻接表存储，便于后续邻居采样。
- 特征工程：为每个节点准备初始特征向量（如用户行为统计、设备属性）。
实践建议： 在反欺诈场景中，建议将有向边（如转账）转化为双向无向边，同时保留方向作为边特征。这样既能利用无向图的对称性简化模型，又能保留行为方向信息用于欺诈判定。