2、图神经网络基础回顾：图的基本概念、邻接矩阵、度矩阵与拉普拉斯矩阵

在深入 GraphSAGE 的阈值分层试验之前，必须牢固掌握图神经网络的核心数学基础。图（Graph）是描述实体间复杂关系的通用数据结构，而邻接矩阵、度矩阵与拉普拉斯矩阵则是将图结构转化为可计算代数形式的三大基石。本节将系统梳理这些概念，为后续的采样、聚合与分层操作建立严格的数学语境。

2.1 图的基本概念

一个图 G 由顶点集合 V 和边集合 E 组成，记为 G = (V, E)。根据边的方向性与权重，图可分为以下常见类型：

在 GraphSAGE 的阈值分层试验中，我们默认处理的是无向无权图，但阈值机制可以扩展至加权场景。节点 v 的邻居集合定义为 N(v) = {u ∈ V | (v, u) ∈ E}，这是后续采样与聚合的直接操作对象。

2.2 邻接矩阵

邻接矩阵 A 是图最直接的代数表示。对于包含 n 个节点的图，A ∈ ℝ^n×n，其中：

• 无向无权图： A_ij = 1 当且仅当节点 i 与节点 j 之间存在边；否则为 0。矩阵对称。
• 有向图： A_ij = 1 表示存在从节点 i 指向节点 j 的边；矩阵不一定对称。
• 加权图： A_ij = w_ij，其中 w_ij 为边权重。

邻接矩阵的稀疏性是图数据的关键特征。真实世界图（如社交网络、引文网络）的邻接矩阵通常极度稀疏，这直接影响了 GraphSAGE 的采样策略——我们不需要遍历所有节点，只需对邻居进行随机采样。

2.3 度矩阵

度矩阵 D 是一个对角矩阵，其对角线元素 D_ii 表示节点 i 的度（即与该节点相连的边数）。对于无向图：

D_ii = ∑_j A_ij

度矩阵在 GNN 中承担归一化的重要角色。在 GraphSAGE 的均值聚合器中，邻居特征的求和结果需要除以节点度（或采样邻居数）来实现平均。度矩阵的逆平方根 D^-1/2 更是拉普拉斯矩阵对称归一化的关键组件。

2.4 拉普拉斯矩阵

拉普拉斯矩阵 L 是图信号处理与谱图理论的核心算子，定义为：

L = D - A

拉普拉斯矩阵具有以下重要性质：

• 半正定性： 所有特征值非负，最小特征值为 0。
• 对称性： 对于无向图，L 是对称矩阵。
• 零特征值对应全 1 向量： 表示图的连通分量个数。

在实际 GNN 应用中，更常用的是对称归一化拉普拉斯矩阵：

L_sym = D^-1/2 L D^-1/2 = I - D^-1/2 A D^-1/2

这种归一化形式避免了节点度差异导致的数值不稳定问题，是 GCN（图卷积网络）消息传递公式的直接基础。GraphSAGE 虽然不直接使用拉普拉斯矩阵进行谱卷积，但理解其归一化逻辑有助于把握聚合权重的设计原理。

2.5 从矩阵到消息传递

理解上述矩阵后，GNN 的消息传递范式可以简洁地表达为矩阵运算。以 GraphSAGE 的均值聚合为例，第 k 层的节点特征更新可写为：

# 伪代码：均值聚合的矩阵形式
h_v^(k) = σ( W · MEAN( { h_v^(k-1) } ∪ { h_u^(k-1), ∀u ∈ N(v) } ) )

# 等价矩阵运算（忽略自环）：
H^(k) = σ( D^(-1) · A · H^(k-1) · W^(k) )

其中 D^-1A 就是行归一化的邻接矩阵，每一行之和为 1。阈值分层试验的本质，就是在 A 上施加一个可学习的或预设的阈值 τ，生成掩码矩阵 M_τ，使得：

A_τ = A ⊙ M_τ

从而控制每一层聚合时邻居信息的“准入强度”。