谱图方法与几何学习

图Laplacian把邻接差异写成二次型

设无向加权图的邻接矩阵 $W=W^\mathsf T$，权重非负，节点度 $d_i=\sum_jw_{ij}$，$D=\operatorname{diag}(d_1,\ldots,d_n)$。组合Laplacian为

它对节点信号 $x\in\mathbb R^n$ 的作用是 $(Lx)_i=\sum_jw_{ij}(x_i-x_j)$。二次型满足

所以 $L$ 对称半正定。能量小表示相连节点取值接近，而不是信号在某个外部坐标中变化慢。$L\mathbf1=0$；零特征值重数等于连通分量数，每个分量上的常数信号都在零空间中。

对度差异大的图，常用对称归一化形式

孤立节点的 $D^{-1/2}$ 需要明确约定。组合和归一化Laplacian有不同特征向量、尺度与随机游走解释，不能训练时使用一种、推理时静默换成另一种。

随机游走Laplacian $L_{\mathrm{rw}}=I-D^{-1}W$ 一般不对称，但与 $L_{\mathrm{sym}}$ 在无孤立节点时相似，因而共享特征值。$D^{-1}W$ 的第 $i$ 行给出从节点 $i$ 按边权归一化转移到邻居的概率。组合形式按原始边权累积差异，归一化形式调整节点度影响；高度节点在两种算子中的尺度不同。选择哪一种应由信号和任务语义决定，而非只比较某次分数。

特征向量定义图上的傅里叶坐标

由谱定理，实对称Laplacian可分解为

其中 $U$ 的列是正交特征向量。图傅里叶系数定义为 $\widehat x=U^\mathsf Tx$，逆变换为 $x=U\widehat x$。特征向量 $u_k$ 的能量 $u_k^\mathsf TLu_k=\lambda_k$，较小特征值对应沿强边较平滑的模式，较大特征值对应更多相邻差异。

“低频”是相对于所选图Laplacian而言。改变边、权重或归一化会改变频率基。重复特征值内的特征向量基不唯一，单个坐标的符号也可翻转；依赖某一特征向量具体符号或顺序的模型跨图时不稳定，而只依赖对应不变子空间或Laplacian多项式更稳健。

谱嵌入坐标带有符号和子空间歧义

取若干非零低频特征向量作为节点坐标，可让强连接节点在嵌入中靠近，并用于聚类或位置特征。但每个简单特征向量乘负一仍是同一解；重复特征值对应的整个特征子空间还可任意正交旋转。两次数值分解即使表示同一几何，也可能给出坐标列翻转或混合。

因此直接把第 $k$ 列数值当作具有固定正方向的语义特征，需要符号对齐或对符号不敏感的处理；跨图使用时还要处理特征值穿越和维数变化。只比较由这些向量生成的距离、投影或子空间，往往比逐坐标比较更合适。图有多个连通分量时，零空间已经多维，跳过“第一个常数向量”也不足以唯一确定后续索引。

谱间隙 $\lambda_{k+1}-\lambda_k$ 可帮助判断一个低维子空间与其余频率是否分离，但小间隙会让采样或边权微扰显著旋转特征向量。嵌入稳定性应通过扰动边、重复分解和下游性能共同检查。

谱滤波按特征值缩放模式

给定标量响应 $g(\lambda)$，谱滤波定义为

先把信号投影到图频率，逐频率乘 $g(\lambda_k)$，再变回节点域。低通响应压低大特征值模式，使相邻节点更接近；高通响应突出边差。滤波是否有利取决于标签与图结构，异配图上相邻节点可能本就应不同，盲目低通会抹掉信号。

多项式滤波把谱定义变成局部稀疏计算

若用 $K$ 次多项式近似

就不必显式计算 $U$。一次乘 $L$ 只沿一跳边传递信息，$L^k x$ 最远依赖 $k$ 跳邻域，因此多项式滤波具有可控局部感受野。稀疏图上每次矩阵向量乘法约需与边数同阶的运算，总成本约为 $O(K|E|)$，还要乘特征通道和批量规模。

直接用幂基在高阶时可能数值不良。Chebyshev方法先把谱区间缩放到 $[-1,1]$，令 $\widetilde L=2L/\lambda_{\max}-I$，再用

递推。需要给出 $\lambda_{\max}$ 的可靠上界或估计；缩放区间错误会影响近似和稳定性。

空间消息传递与谱滤波是相交而非相同的视角

一层线性扩散可写成

它既是一阶谱响应 $g(\lambda)=1-\alpha\lambda$，也可在节点域解释为保留自身并按边差与邻居交换信息。更一般的共享线性邻居聚合常能写成邻接或Laplacian多项式；加入特征矩阵、可学习通道映射和逐点非线性后，空间消息传递仍保持局部计算，却不再等于一次固定线性谱滤波。

空间参数共享更容易跨不同大小图应用，因为规则按邻域定义。若直接为训练图的每个特征值学习独立系数，换图后特征值数量、位置和简并结构都改变，迁移缺少自然对应。把响应参数化为特征值的共享函数或多项式，能减轻但不消除图分布差异。

网格和流形离散决定算子含义

光滑流形上的Laplace–Beltrami算子描述内在几何扩散。三角网格、点云或邻域图上的离散Laplacian试图近似它，但结果依赖采样密度、邻域半径、边权、面积质量矩阵和边界条件。仅把欧氏近邻连边再用无权图Laplacian，不自动得到与连续曲面一致的算子。

三角网格可使用基于角度和面积的离散形式；点云常由 $k$ 近邻或半径图配合核权重构造。$k$ 太小可能断开，太大则跨越薄结构或不同流形分支；固定半径在密度不均时会让度差异巨大。边界处邻域缺失对应特定边界效应，需要在模型和评价中说明。

离散谱收敛到连续谱需要采样细化、权重和正则性等条件，不能从一张粗网格的相似图形直接推出。形状有孔洞、尖角或非均匀采样时，低阶谱也可能显著变化。

规模限制来自基分解、边数与动态结构

完整稠密特征分解在大图上时间和内存昂贵，保存所有特征向量需 $O(n^2)$ 空间。只求少数极端特征对谱嵌入可行，但深度模型每步重算仍可能不可接受。多项式滤波避免完整基，在稀疏图上扩展更好；图若近乎稠密，$|E|$ 本身已接近 $n^2$。

动态图每次改变边就改变Laplacian和谱基，缓存旧特征向量可能失效。批量包含不同图时，空间稀疏操作容易分别执行；直接堆叠图特征基需要处理不同尺寸。重复多步低通还会让节点表示趋同，产生过平滑；长距离信息经过有限通道汇聚还可能过压缩。提高多项式阶数增加范围，也同时增加计算和数值敏感性。

多尺度方法可先聚合节点形成粗图，在粗层传播远距离信息，再映射回细层。它减少有效路径长度，却引入聚类或池化误差：被合并节点的差异可能无法恢复，粗图边权也要有清楚定义。网格细化任务还需确认粗化在不同分辨率下代表相近物理区域，而不是按节点序号机械分组。

子图采样能控制单批内存，但切断跨子图边后，Laplacian度、归一化和谱响应都会变化。用全图度数配合采样边、或在子图内重新计算度，定义的是不同算子。规模优化必须记录哪些边可见、边界节点如何处理，以及最终输出是否在完整图上复算。

核验从代数不变量到任务信号

先检查 $L=L^\mathsf T$、$L\mathbf1=0$、随机向量二次型非负和连通分量零特征值数。节点置换 $P$ 后应有 $L'=PLP^\mathsf T$，多项式滤波输出应相应变为 $Py$。小图可把多项式结果与完整特征分解结果数值对照。

任务侧同时比较低通、高通、无图基线和打乱边。若标签在异配边上变化，低通失败可能是归纳偏置错误而非优化失败。网格任务还要按分辨率、采样密度和边界区域分组，分开模型误差与离散误差。

练习

概念关系

• 图信号与图Laplacian 定义邻接、度和节点信号能量。
• 谱定理 提供对称矩阵的正交特征分解。
• 光滑流形 提供连续几何和切空间背景。
• 消息传递神经网络 给出局部空间计算视角。
• 不变性与等变性 解释节点重新编号下的协变关系。
• 几何深度学习综合复习 延伸过平滑、过压缩和评价。

资源