图拉普拉斯算子是一种矩阵或线性算子,用于衡量定义在图顶点上的函数在某个顶点处的值与其相邻顶点处的值之间的差异。对于边权非负的有限无向图,其标准形式为 ,其中 是邻接矩阵, 是由各顶点的加权度构成的对角矩阵。它是负拉普拉斯算子的离散对应形式,在能量最小化、扩散和势理论中有着密切相关的解释。
图拉普拉斯算子将图论与线性代数、概率论、几何学和计算联系起来。其特征值揭示图的连通分量和瓶颈;以它构成的方程描述电势和平均化过程;其行列式则可用于计数生成树。归一化形式是随机游走和谱聚类的基础,而大型稀疏拉普拉斯线性方程组在数值算法中占据核心地位。由于多种约定并存,权重、归一化方式、符号以及孤立顶点的处理方式,都是该算子定义的一部分。
定义与归一化约定
设 是一个有 个顶点的有限无向图。对于不同的顶点 和 ,令 ,两者之间没有边时取 。先假设图中没有自环。其邻接矩阵为 ,各顶点的加权度为
记 ,则组合拉普拉斯矩阵为
向量 可以理解为定义在顶点上的实值函数。于是
因此,该算子刻画的是加权差值,而非函数值本身。给 的所有分量加上同一个常数, 保持不变。
有两种归一化形式得到广泛应用。如果所有顶点的度都为正,则对称归一化拉普拉斯矩阵和随机游走拉普拉斯矩阵分别为
前者在通常的欧几里得内积下是对称的。后者的作用为
即比较某个顶点的函数值与其邻接顶点函数值的加权平均值。这两个矩阵之间存在矩阵相似关系:
因此它们具有相同的特征值,但特征向量的缩放方式不同。在 -正则图上,两者都化为 。
对于孤立顶点,必须明确约定处理方式,因为此时 不存在。一种常见做法是将对应的度的倒数设为零,并定义 。这样,孤立顶点对应的行和列均为零。在这一约定下,公式 必须针对孤立顶点作出调整:将其中的单位矩阵项替换为投影到正度顶点所张成子空间上的投影矩阵。其他约定则将孤立顶点对应的对角元设为一,这会改变零特征值的重数。
自环也需要谨慎处理,因为图论中对度的定义有不同约定。如果将度定义为邻接矩阵的行和,那么自环的贡献会在 中抵消,但仍可能通过 影响归一化算子。最后,有些作者将 称为拉普拉斯矩阵。在谱图论的大部分文献中,半正定的 是标准约定;取相反符号的约定则更直接地对应于分析学中微分拉普拉斯算子通常采用的符号。
关联矩阵分解、能量与边值问题
拉普拉斯算子可以由离散梯度构造。为 条无向边各自任意指定一个方向,并构造关联矩阵 。对于从 指向 的边,其对应行在 列的元素为 ,在 列的元素为 ,其余元素均为零。若 为边权构成的对角矩阵,则
改变一条边的方向,相当于将 中对应的行乘以 ,不会改变上述乘积。因此,指定方向只是为了便于代数运算,并不意味着给图添加了额外结构。
向量 包含各条边两端顶点的函数值之差。乘以 后,这些差值被赋予相应的权重,再由 汇总回各个顶点。这一分解是先求梯度、再求散度这一复合运算的离散对应。特别地,相应的二次型为
它通常称为图的狄利克雷能量。另一种常见约定是在此基础上再乘以 ;这不会影响使能量最小的函数。
这一恒等式证明了 是对称半正定矩阵,也精确刻画了它的零空间:当且仅当 在仅由正权边构成的图的每个连通分量上均为常数时,能量为零。若有 个连通分量,则零空间的维数为 ,而矩阵的秩为 。因此,这一能量衡量的是实际由边相连的顶点之间的函数值变化,而非任意顶点对之间的变化。
图上的边值问题是在一组边界顶点上固定 的值,并在其余顶点上求使能量最小的函数值。对于每个不受约束的顶点,驻值条件为
当 时,可改写为
这样的调和函数在每个顶点的值都等于其相邻顶点函数值的加权平均。若每个连通分量都包含边界顶点,则 中对应于内部顶点的主子矩阵为正定矩阵,因而延拓唯一。上述平均值恒等式还蕴含一个离散最大值原理:内部顶点的函数值不会高于边界上的最大值,也不会低于边界上的最小值。
在未指定边界值时,图上的泊松方程为 。当且仅当 在每个连通分量上对应的各分量之和分别为零时,该方程才有解。此时,解在每个连通分量上相差一个任意的加法常数。这些相容性条件既体现了 在代数上的奇异性,也反映了封闭连通分量内源与汇必须平衡的物理要求。
特征值、连通性与图割
由于 是实对称矩阵,谱定理保证存在一组由特征向量构成的标准正交基,且相应的特征值均非负。将特征值按升序排列,记为
对于连通图,零特征值是单重的,其对应的特征向量为常向量。第二小的特征值 称为代数连通度,它为正当且仅当图连通。米罗斯拉夫·菲德勒于 1973 年的研究确立了这一量作为图连通性核心度量的地位;与之对应的特征向量通常称为菲德勒向量。
瑞利商给出了如下变分刻画:
这一值较小,意味着存在某个非常值函数,相对于其整体大小,它沿边的变化很小。一种产生这种情况的结构是:两个内部连接紧密的区域,仅由少数几条弱边连接。此时,函数在各个区域内部可以近乎恒定,而在弱连接两侧取不同的值。因此,特征向量所编码的信息不只是可达性,还能揭示连通图中耦合较弱的部分。
归一化拉普拉斯算子的特征值与按度加权的割有着自然的联系。对于至少包含两个顶点的连通图,定义
其电导率定义为
若 是 的第二小特征值,则图的切格不等式表明
这些界将向量上的连续优化与顶点子集上的离散优化联系起来。对经过适当缩放的归一化拉普拉斯特征向量进行阈值划分,可以得到候选割,而这正是上述上界的基础。
一些简单的图可以展示不同的谱表现。具有 个顶点的无权完全图,其拉普拉斯谱为 。具有 个顶点的路径图,其特征值为
因此,其代数连通度渐近等价于 。所以,长路径图具有变化缓慢的低能量模态。
谱并不能决定图的所有特征:非同构的图也可能具有相同的拉普拉斯谱。不过,谱确实决定了若干结构不变量,包括连通分量的个数和加权度之和,因为
对于归一化拉普拉斯算子,所有特征值均位于 内;一个至少含有一条边的连通图具有特征值 ,当且仅当它是二分图。
扩散、随机游走与共识
图上的热方程为
其解为
其中的指数是矩阵函数。若 ,则沿 方向的分量会乘以 。常数分量保持不变,而能量较高的分量衰减得更快。在连通图上,
这一极限源于零空间是一维的,体现了顶点取值的无权总和守恒。
矩阵 也可作为连续时间马尔可夫链的生成元。从顶点 跳转到 的速率为 ,因此离开该顶点的总速率为 。由于这些速率具有对称性,均匀分布在连通图上是平稳的。这里, 既是转移矩阵,也是热传播算子。若概率用列向量表示,对称性保证同一个矩阵也能描述其前向演化。
采用不同的计时方式便得到归一化游走。矩阵
是离散时间随机游走的转移矩阵;该游走以正比于边权的概率选择下一个顶点。在连通图上,其平稳分布为
算子 生成一条连续时间链,其跳转尝试以单位速率发生。作用于顶点上的函数时,相应的演化收敛到按度加权的平均值:
因此,组合拉普拉斯扩散与归一化扩散所守恒的平均值通常不同。
归一化谱隙控制连续时间下的弛豫速度。离散时间下的收敛还取决于周期性:连通二分图上的随机游走会在两个部分之间交替移动。将 替换为惰性转移矩阵 ,便引入了停留在原处的概率,从而消除这种振荡。连续时间演化不存在同样的周期性障碍。
同样的方程也可用来描述由相互作用的智能体组成的网络中的共识过程。若智能体 按照
调整自身状态,则有 ,而连通无向网络最终会在初始状态的算术平均值处达成一致。衰减最慢的非常数模态按 衰减,因此代数连通度是刻画收敛速度的参数。时变权重、时延、有向相互作用及非线性更新规则都需要进一步分析;固定的无向图拉普拉斯算子则提供了基本的线性模型。
电网络与有效电阻
当 被解释为电导(即电阻的倒数)时,无向加权图就表示一个电阻网络。若以 表示电势,则根据欧姆定律,从 流向 的电流为 。基尔霍夫电流定律于是写为
其中, 是从外部注入顶点 的电流。对于连通网络,相容性条件 表明,注入的总电流必须等于流出的总电流。
由于电势只能确定到相差一个常数,摩尔—彭罗斯伪逆 在这里很有用。它将 的正特征值取倒数,并在其零空间上保持为零。对于满足电流平衡条件的 ,向量 是均值为零的唯一解。等价地,也可以将一个顶点接地,删除其对应的行和列,再求解所得的正定方程组,得到其余顶点的电势。
顶点 与 之间的有效电阻,是在 处注入单位电流、在 处引出同样大小的电流时产生的电势差:
与最短路径距离不同,这个量将所有可用路径都纳入考虑。一条由 条单位电阻边构成的路径,其两端之间的有效电阻为 。如果 条电阻均为 的路径连接同一对端点,路径之间除端点外互不相交,且没有其他连接,那么它们并联后的电阻为 。在具有 个顶点、各边电导均为单位电导的完全图中,每对顶点之间的有效电阻都是 。
能量原理可以用边电流给出对偶表述。给定有向关联矩阵 ,电流向量 对应的净注入电流为 。汤姆孙原理指出,在各边电导均为正的条件下,
在两端点之间的所有单位流中,实际电流唯一地使耗散能量达到最小。由这一刻画可得瑞利单调性:增大电导或添加一条新的导电边,都不会使有效电阻增大。
电阻还将电网络与概率联系起来。对于离散时间加权随机游走,设 为从 出发到达 所需步数的期望,则
这一往返时间恒等式适用于离散时间随机游走,而非所有可能的连续时间约定。因此,有效电阻既是电压响应,也是最小流能量,同时还是随机游走可达性的一种度量。
生成树与行列式恒等式
拉普拉斯算子通过行列式蕴含了全局的组合信息。生成树是包含所有顶点的连通无环子图。对于加权图,赋予树 权重
并令
矩阵树定理源于古斯塔夫·基尔霍夫于1847年对电网络的分析。该定理指出,从 中删去任意一行及其对应的列,所得矩阵的行列式等于 。对于无权图,这就是通常意义下的生成树数量。
关联矩阵分解解释了这一联系。从 中删去一列,得到约化关联矩阵 。相应的主子式为 。应用柯西–比内行列式恒等式,可以将其行列式展开为对所有含 条边的边集求和。所选边集只有构成生成树时才有非零贡献。对于生成树,约化关联矩阵的行列式为 或 ,因此将该行列式平方后乘以所选各边的权重,所得贡献恰好就是这些边的权重之积。由此,一个行列式便能对一个规模可能极其庞大的子图族进行精确求和。
对于连通图,用特征值表示的公式为
完全图的非零特征值都等于 ,由此得到凯莱公式 。含有 个顶点的环图有 棵生成树,每棵都可通过删去任意一条边得到。如果图不连通,则不存在生成树,此公式中的每个代数余子式都为零。
生成树的概率又将行列式与电阻联系起来。假设以概率 随机选取一棵树。对于边 ,有
右侧的量有时称为该边的杠杆得分。对于桥,这个值为1,因为每棵生成树都必须包含这条边;当存在其他路径,使这条边可以被替代时,该值就较小。对所有边求和,得到
这与每棵生成树的边数一致。
相关的行列式恒等式还可以用于森林计数。例如,
是生成有根森林的生成函数:森林的每个连通分量都选定一个根,而 的幂次记录森林的边数。因此,拉普拉斯算子的一个多项式就包含了从孤立的有根顶点到生成树等各种结构的加权计数。这些恒等式使拉普拉斯算子不仅适用于连续优化和随机过程,也适用于精确计数。
稀疏计算与谱近似
对于一个有 个顶点和 条边的图, 中可能非零的元素至多有 个。因此,很自然地可以将其表示为稀疏矩阵,与向量相乘的计算成本为 。利用关联矩阵表示,可以直接根据边列表计算矩阵与向量的乘积,而无须构造稠密矩阵。这些性质使拉普拉斯算子成为数值线性代数中的重要研究与测试对象。
求解 时,需要处理其零空间。对于连通图,可以施加约束 ,将一个顶点接地,或直接在与常数向量正交的子空间内求解。将一个顶点接地后,得到的主子矩阵是对称正定的,因而可以使用Cholesky分解和共轭梯度法。不过,稀疏直接分解仍可能产生填充:原本为零的位置在分解因子中变为非零。消元顺序和图结构会显著影响内存需求与运行时间。
迭代法的收敛性取决于谱条件。在与常数向量正交的子空间上,组合拉普拉斯算子的条件数为 。因此,即使边数很少,具有狭窄瓶颈的图也可能产生难以在未经预条件处理的情况下求解的方程组。预条件处理用一种新的几何结构替代原有几何结构,使相关特征值更加集中。多层次方法、近似分解和低伸展生成树都利用图结构来构造这类预条件子。
谱稀疏化图是一个边数更少、经过重新赋权的图 ,其拉普拉斯算子对任意向量 都满足
这一条件比保留选定的一组特征值或仅仅维持连通性更强。它近似保留了图的所有能量,因而也近似保留了所有割。对于连通图,在与常数向量正交的子空间上求逆,还能得到对有效电阻相应的乘法误差控制。
根据与 有关的量对边进行采样,再重新赋权,便可得到一种有理论依据的稀疏化方法。在电学意义上越难被替代的边,采样优先级就越高。丹尼尔·斯皮尔曼和滕尚华于2004年公布的工作,确立了求解拉普拉斯方程组及相关对称对角占优方程组的近线性时间方法。这里的“近线性”允许包含多对数因子以及对精度的依赖,并不意味着每一种实际实现都严格以 时间运行。
大规模谱计算同样会避免完整对角化。Lanczos类方法可以近似求得少量特征值与特征向量对,而多项式或有理函数近似则可以在不显式计算特征向量的情况下,施加扩散及其他谱滤波算子。直接法、迭代法和多层次方法之间的选择,取决于图结构、所需精度,以及是否需要求解多个具有相同拉普拉斯算子的方程组。
谱聚类、图信号与学习
图可以表示数据点之间的相似性,边权越大,表示关联越强。拉普拉斯算子的特征向量据此提供一组适应这些关系的坐标,而非沿用原始的测量坐标轴。在谱聚类中,先用少量低频特征向量将顶点嵌入欧几里得空间,再用常规的聚类分析方法对嵌入后的点进行划分。当各个簇在原始特征空间中连通但非凸时,这种构造尤其有用。
它与图划分的联系可以通过指示向量来说明。对于子集 ,
割的目标函数由此化为离散取值向量的二次表达式。放宽向量必须为指示向量的要求,就会得到特征值问题。考虑顶点度平衡的目标函数会导出广义特征值方程
当所有顶点的度均为正时,它等价于一个归一化拉普拉斯算子的特征值问题。史建波和吉滕德拉·马利克于 2000 年提出的归一化割方法将这一思路应用于图像分割。不同的平衡项会产生不同的松弛问题,因此未归一化聚类与归一化聚类不能互相替代。
图信号就是一个函数 ,例如相互连接的传感器所记录的温度,或交通网络上的测量值。若 构成 的一组标准正交特征基,则其图傅里叶系数为
这种与傅里叶变换的类比基于能量:特征值较小的特征向量在大权重边的两端变化缓慢,而特征值较大的模态变化更快。谱滤波器的形式为
例如, 对应热扩散平滑。
多项式滤波器具有一个实用的局部性性质。由于乘以 只会将一个顶点的值与其邻居的值混合, 次多项式的作用结果仅依赖于图上距离不超过 步的顶点。这将谱滤波与基于图的机器学习中使用的局部消息传递过程联系起来。不过,反复平滑会削弱顶点之间的差异;在连通图上不加限制地持续扩散,最终只会留下常量信号。
拉普拉斯算子也可用于构造正则化惩罚项。给定子集 上的标签 ,可以通过最小化
来估计函数。第二项体现了这样一种假设:连接越强的顶点,其预测值应越相近。当标签固定,且内部顶点上没有拟合项时,解便成为调和延拓。真正关键的假设体现在图的构建中:邻居的选择、权重带宽、度归一化以及不连通的分量,都可能显著改变结果。拉普拉斯算子忠实表达的是所选定的图,而不是某种能够独立保证具有实际意义的相似性概念。
连续极限、有向图与高阶算子
只有明确了尺度缩放和几何结构,图拉普拉斯算子与微分拉普拉斯算子之间的类比才具有精确含义。在间距为 的一维网格上,无权路径图的拉普拉斯矩阵中,对应内部顶点的一行给出
若这些数值采样自一个足够光滑的函数,则有
因此,逼近负二阶导数的是 ,而不是未经缩放的矩阵。边界顶点需要单独处理,因为它们的度数不同,并且体现了特定的边界行为。
对于从流形上采样得到的点,局部邻域图可以逼近拉普拉斯–贝尔特拉米算子等微分算子。权重可以基于尺度逐渐缩小的距离核来构造,而一致性取决于样本量、邻域尺度、归一化方式及正则性假设。除非进行适当校正,否则非均匀采样通常会引入依赖于采样密度的效应。因此,仅凭“图拉普拉斯算子”这一名称并不能确定其连续极限。米哈伊尔·贝尔金和帕尔塔·尼约吉在 2003 年发表的研究中提出了拉普拉斯特征映射方法,利用较小特征值对应的特征向量作为坐标,实现非线性降维。
几何离散化带来了另一项重要区别。在有限元法中,刚度矩阵表示梯度能量,而质量矩阵表示底层的测度或内积。由此得到的特征值问题通常具有如下形式:
三角网格上的余切权重拉普拉斯算子就属于这一类几何构造。即使组装后的刚度能量非负,某些余切权重仍可能为负。因此,如果不对网格施加额外条件,那些依赖于所有边权重均非负的性质,例如直接的平均解释或某些最大值原理,就未必成立。
对于有向图,出度拉普拉斯算子 通常不是对称的。它的特征值可能为复数,左零空间与右零空间不同,无向图的二次能量公式也不再直接适用。随机游走生成元仍然有意义,但在许多构造中,平稳分布取代了均匀测度。基于平稳测度的对称化方法和磁拉普拉斯算子提供了不同途径,既能保留部分方向信息,又能得到自伴算子;这些方法编码的信息各不相同,并不存在唯一的典范推广。
高维的类似算子出现在代数拓扑中。对于边界矩阵为 的单纯复形,作用于 -链的无权组合霍奇拉普拉斯算子为
在零维时,它还原为普通的图拉普拉斯算子。在更高维度中,它作用于边上的流、三角形上的数据以及其他高阶信号。它的零空间由调和链构成,其维数等于相应的贝蒂数,从而将拉普拉斯分析与同调及拓扑孔洞的检测联系起来。