图与图信号：结构、算子和建模单位

图是关系结构，不是节点编号表

图写作 $G=(V,E)$，$V=\{v_1,\ldots,v_n\}$ 是节点集合，$E$ 是边集合。无向边 $\{v_i,v_j\}$ 表示对称关系，有向边 $(v_i,v_j)$ 表示从 $i$ 指向 $j$ 的关系。简单图不含重边和自环；实际数据可能有多种关系、重复事件、自环和时间戳，不能在读入时无声删除。

节点编号只是把集合元素排成矩阵行列的临时索引。编号 $7$ 不表示节点位于编号 $6$ 与 $8$ 之间，也不提供长度、角度或方向。若节点确有空间坐标，应把坐标或相对位移作为带单位的特征，并说明坐标系及其变换规则；不能从索引差推断几何。

图建模的第一步不是选神经网络，而是写出实体和关系。分子图可以把原子作为节点、化学键作为边；交通图可按道路连接站点；推荐图可能包含用户—物品两类节点。把“相关性超过阈值”当边、把最近邻当边或把物理接触当边，会形成不同问题。缺少记录可能表示真正无边，也可能表示尚未观测，二者不应共用同一零值。

邻接矩阵保存边，不保存天然几何

本章先采用非负加权无向图。邻接矩阵 $A\in\mathbb R^{n\times n}$ 定义为

当节点 $i,j$ 相连，否则为零。无权图取 $w_{ij}=1$。节点度为 $d_i=\sum_jA_{ij}$，度矩阵为

无向图中 $A$ 对称，行和等于列和；有向图必须区分入度和出度，并明确 $A_{ij}$ 表示 $i\to j$ 还是 $j\to i$。许多库的聚合约定不同，矩阵方向若未声明，代码看似运行却会沿反方向传信。

邻接权重需要语义和单位。道路边权可能是米、秒或通行能力；相似图边权可能是无量纲核值。把距离直接作为“连接强度”会使更远邻居权重更大，常与预期相反；若用 $e^{-d^2/\sigma^2}$，还要说明距离与尺度 $\sigma$ 使用同一单位。负权边不能直接套用后文非负 Laplacian 的半正定结论。

节点、边和全局特征各有粒度

节点特征矩阵 $X\in\mathbb R^{n\times d_v}$ 的第 $i$ 行 $x_i$ 描述节点 $v_i$。单通道图信号是向量 $x\in\mathbb R^n$，例如每个站点的温度；多通道可以同时包含温度、压力、类别和状态。不同物理量不能因都在同一行就直接相加，数值标准化也只能用训练数据统计量，并保留还原到原单位的办法。

边特征 $e_{ij}\in\mathbb R^{d_e}$ 描述关系本身，如键类型、距离、流量或相对位移。相对位移有方向，交换端点时通常变号；标量距离不变。全局特征 $u$ 描述整张图共享的条件，如环境温度、时间段或外场强度。把全局变量复制到每个节点可供局部计算使用，但它仍是同一个图级量，批处理时不能跨图串接。

任务粒度必须匹配输出。节点分类为每个节点输出一个标签，节点重编号后输出应同步重排；边预测为每条候选边输出关系；图分类或图回归把整图读出为固定维结果，节点重编号不应改变答案。链路预测还要定义“负边”如何采样，因为未记录边未必是真负例。

Laplacian 测量邻居差异

非归一化图 Laplacian 定义为

对单通道信号，

它汇总节点与邻居的加权差异。对非负无向图，

因此 $L$ 对称半正定。每个连通分量上的常量信号落在零空间；零特征值的重数等于连通分量数。这个结论依赖无向、非负权与所用 Laplacian 定义，有向图和带符号图需要其他构造。

归一化处理度数尺度但改变算子

常见归一化 Laplacian 为

随机游走形式为

它们减弱高连接度节点的绝对总量影响，却与 $D-A$ 不是同一个算子。孤立节点的 $d_i=0$ 使逆度无定义，必须明确把逆度置零、保留恒等项还是单独处理。加入自环会改变度和归一化，也不是只在图上画一条装饰边。

度归一化是否合理取决于任务。若边权代表并联导热能力，总量可能具有真实物理意义，任意除以度会改变方程；若目标是平均邻域信息，归一化可以防止高度节点数值尺度过大。应从单位和生成机制决定，而不是因为某个默认层这样实现。

平滑是局部算子，不是证明标签相同

一个显式平滑步可写为

小正步长会把每个节点向邻居值移动，并常降低非负无向图上的二次能量。$\eta$ 的单位必须抵消 $L$ 的边权单位；步长过大可导致振荡或放大。更重要的是，边相连只说明建模者声明了关系，不自动证明两端标签或物理状态应接近。异配图中相邻节点可能有意属于不同类别。

重编号必须同步变换结构和特征

节点重编号由置换矩阵 $P$ 表示。若新第 $i$ 行对应旧图的某个节点，则

并且 $D'=PDP^\top,L'=PLP^\top$。因此

图算子输出随节点顺序同步重排，称为置换等变；图级标量如 $x^\top Lx$ 在重编号下保持不变。若只重排 $X$ 而不重排 $A$，特征就被分配给错误节点，这不是数据增强而是破坏样本。

局部邻域与全局结构不能互相替代

节点的一跳邻域是直接相邻节点，$k$ 跳邻域包含最短路径不超过 $k$ 的节点。矩阵 $A^k$ 的元素与长度为 $k$ 的游走有关，但不等于欧氏距离，也不保证路径简单。局部统计包括度、邻居特征和小子图；全局结构包括连通分量、直径、长环、割点和跨图规模。

只看固定半径局部邻域的模型可能无法区分局部完全相同但全局连接不同的节点。反过来，只做全局均值会丢失谁与谁相连。任务设计应说明预测需要的范围：分子局部键环境可能重要，图连通性则需要跨越很长路径。增加层数扩大感受野，却还会引入过平滑和信息拥挤，不能视作免费的全局访问。

图构造和批处理属于模型合同

真实数据常先从坐标、日志或相似度构图。$k$ 近邻保证每个节点发出若干连接，却可能跨越物理障碍；半径图保留距离阈值，却在稀疏区域产生孤立节点；相关图容易把同一时间窗口噪声变成边。构图超参数只能用训练与验证数据选择，若用测试标签决定边，就发生结构泄漏。

多张图批处理时可组成不相连并图，邻接矩阵呈块对角结构，并用 graph id 标出节点所属样本。任何跨块边都会把不同样本信息混合。sum 读出随节点数增长，mean 更接近尺度无关平均，max 只保留极端值；三者回答不同问题。若图大小本身有预测意义，应显式保留节点数，而不是期望归一化读出偶然编码。

批内统计也要注明按节点还是按图加权。直接汇总全部节点会让大图主导均值和方差；若任务要求每张图等权，应先在图内归约，再跨图汇总。

时间图还需固定快照边界。用预测时刻之后出现的边或全局统计构造当前图会泄漏未来。删除节点、合并实体和 ID 重用必须有版本规则，否则同一编号在不同时刻可能代表不同对象。

三个常见误区

第一，“节点编号接近就表示几何接近”。编号只是索引；距离和方向必须来自显式坐标、边或其他有语义特征。

第二，“Laplacian 越平滑越好”。平滑只符合相连节点信号应接近的假设，异配关系、边方向或物理守恒可能需要其他算子。

第三，“没有记录边就是真负例”。缺边可能源于未观测、采样或权限限制；链路任务必须建模观测机制并声明负样本规则。

练习

关系与资源

• 图、连通性与路径 提供图结构和局部全局关系基础。
• 矩阵乘法 支持邻接和 Laplacian 对信号的作用。
• 特征值与特征向量 连接 Laplacian 零空间和谱结构。
• 消息传递神经网络 将局部图算子推广为可学习更新。
• 谱图方法与几何学习 从 Laplacian 特征基继续分析。