图的梯度与散度
我将从基本概念出发，循序渐进地讲解图上的梯度和散度算子，并最终联系到图上的拉普拉斯算子。
第一步：从连续空间到离散图的直观类比
-
背景：在微积分和物理学中，梯度和散度是分析标量场（如温度分布）和向量场（如流体速度场）的基本工具。
- 梯度：作用于一个标量函数，衡量该函数在空间各点处的变化率和变化最快的方向。其结果是一个向量场。例如，山丘的高度是一个标量场，其梯度指向最陡峭的上升方向。
- 散度：作用于一个向量场，衡量在场中某点附近，场是“发散”还是“汇聚”的程度。其结果是一个标量函数。正散度表示该点是“源”，有净流出；负散度（收敛）表示该点是“汇”，有净流入。
-
图的设定：现在我们将场景转移到一个无向图 \(G = (V, E)\) 上，其中 \(V\) 是顶点集合，\(E\) 是边集合。我们假设图是连通的、简单的（无自环和重边）。
第二步：定义图上的函数空间
为了定义梯度等算子，我们需要先明确它们作用的对象——函数。
- 顶点上的函数：定义在图的每个顶点上的实值函数。所有这样的函数构成一个函数空间，记作 \(\mathcal{H}(V)\)。一个函数 \(f: V \to \mathbb{R}\) 可以看作一个定义在顶点上的标量场。例如，每个顶点的温度、人口数等。
- 边上的函数：定义在图的每条边上的实值函数。所有这样的函数构成另一个函数空间，记作 \(\mathcal{H}(E)\)。一个函数 \(s: E \to \mathbb{R}\) 可以看作一个定义在边上的向量场，但它有一个重要特性：我们通常要求它是反对称的，即对于一条边 \(e = (u, v)\)，有 \(s(u, v) = -s(v, u)\)。这类似于向量场有方向。我们通常约定一个边的方向（如从编号小的顶点指向编号大的顶点）。
第三步：定义图上的梯度算子
- 定义：图的梯度算子（gradient operator）是一个将顶点函数映射为边函数的线性算子。
记作 \(\nabla: \mathcal{H}(V) \to \mathcal{H}(E)\)。 - 操作：梯度算子作用于一个顶点函数 \(f\) 后，得到一个新的边函数 \(\nabla f\)。对于任意一条有向边 \(e = (u, v)\)（根据我们约定的方向），梯度在该边上的值定义为：
\[ (\nabla f)(u, v) = f(v) - f(u) \]
- 解释：
- 这个定义直观地反映了“变化”的概念。它衡量了函数 \(f\) 的值从顶点 \(u\) 到顶点 \(v\) 的差值。
- 如果 \(f(v) > f(u)\)，则梯度值为正，表示从 \(u\) 到 \(v\) 是“上坡”。
- 这个差值（梯度）天然地满足反对称性：\((\nabla f)(u, v) = -(\nabla f)(v, u)\)。
- 例子：考虑一个简单的路径图 \(u-w-v\)。
- 设顶点函数 \(f\) 的值为：\(f(u)=2, f(w)=5, f(v)=1\)。
- 则梯度 \(\nabla f\) 在边 \((u, w)\) 上的值为 \(5-2=3\)。
- 在边 \((w, v)\) 上的值为 \(1-5=-4\)。
- 在边 \((u, v)\) 上不存在（因为不是边）。
第四步：定义图上的散度算子
- 定义：图的散度算子（divergence operator）是梯度算子的（负）伴随算子。它是一个将边函数映射为顶点函数的线性算子。
记作 \(\text{div}: \mathcal{H}(E) \to \mathcal{H}(V)\)。
（“伴随”是一个严格的数学概念，这里我们可以先接受其具体形式定义） - 操作：散度算子作用于一个边函数 \(s\)（需满足反对称性）后，得到一个新的顶点函数 \(\text{div} s\)。在任意一个顶点 \(u\) 上，散度的值定义为：
\[ (\text{div} s)(u) = \sum_{v \sim u} s(u, v) \]
其中 \(v \sim u\) 表示对所有与顶点 \(u\) 相邻的顶点 \(v\) 求和。求和时边的方向遵循我们之前的约定（从 \(u\) 指向 \(v\)）。
3. 解释：
- 这个定义直观地反映了“净流出”的概念。它将进入顶点 \(u\) 的所有边上的函数值（考虑方向）加起来。
- 如果 \(s\) 被解释为某种“流”（如电流、车流），那么 \((\text{div} s)(u)\) 就表示从顶点 \(u\) 净流出的流量。
- 如果 \((\text{div} s)(u) > 0\)，说明顶点 \(u\) 是一个“源”，有净流出。
- 如果 \((\text{div} s)(u) < 0\)，说明顶点 \(u\) 是一个“汇”，有净流入。
- 如果 \((\text{div} s)(u) = 0\)，则满足基尔霍夫电流定律，流在顶点 \(u\) 处是守恒的。
- 例子：接上例，路径图 \(u-w-v\)。
- 假设我们有一个边函数 \(s\)，其值为：\(s(u, w)=3, s(w, v)=-2\)（根据约定，\(s(w, u) = -3, s(v, w)=2\)）。
- 则在顶点 \(u\) 的散度：只有一条出边 \((u, w)\)，所以 \((\text{div} s)(u) = s(u, w) = 3\)。
- 在顶点 \(w\) 的散度：有两条边相连，一条是流入 \((u, w)\)，但方向是从 \(u\) 到 \(w\)，所以对 \(w\) 而言，\(s(u, w)\) 是流入（负方向？）。我们需要严格按照定义：从 \(w\) 指向 \(u\) 的边是 \((w, u)\)，其值为 \(s(w, u) = -3\)。从 \(w\) 指向 \(v\) 的边是 \((w, v) = -2\)。所以 \((\text{div} s)(w) = s(w, u) + s(w, v) = (-3) + (-2) = -5\)。
- 在顶点 \(v\) 的散度：只有一条流入边 \((w, v)\)，但方向是 \(w\) 到 \(v\)，所以对 \(v\) 而言，从 \(v\) 指向 \(w\) 的边是 \((v, w) = 2\)。所以 \((\text{div} s)(v) = s(v, w) = 2\)。
第五步：图的拉普拉斯算子作为“梯度的散度”
- 组合定义：图的最常见的拉普拉斯算子（组合拉普拉斯）\(L\) 是一个作用于顶点函数的算子。它可以被定义为负的散度算子作用于梯度算子：
\[ L = -\text{div} \circ \nabla \]
也就是说，拉普拉斯算子是“梯度的散度”再取负号。\(L: \mathcal{H}(V) \to \mathcal{H}(V)\)。
2. 计算：对于顶点函数 \(f\) 和顶点 \(u\)：
\[ (L f)(u) = (-\text{div} (\nabla f))(u) = -\sum_{v \sim u} (\nabla f)(u, v) = -\sum_{v \sim u} (f(v) - f(u)) \]
化简后得到我们熟悉的形式：
\[ (L f)(u) = \deg(u) f(u) - \sum_{v \sim u} f(v) \]
其中 \(\deg(u)\) 是顶点 \(u\) 的度（邻居个数）。这正好是拉普拉斯矩阵 \(L = D - A\)（度矩阵减邻接矩阵）作用于向量 \(f\) 的结果。
总结
您已经学习了图上的梯度、散度和拉普拉斯算子的核心思想：
- 梯度 \(\nabla\)：衡量顶点函数沿着边的局部变化（差值）。
- 散度 \(\text{div}\)：衡量边函数在顶点处的净流出。
- 拉普拉斯 \(L = -\text{div} \circ \nabla\)：综合了局部变化和净流出的概念，是梯度算子的散度，是图上的一个核心微分算子。
这套理论为在图上进行类似于微积分的分析（离散微积分或微积分在图上的类比）奠定了基础，广泛应用于图上的偏微分方程、谱图理论、图神经网络和网络分析等领域。