Laplacian算子的谱性质在谱图论中有什么效应？

1 Laplacian 算子 给定无向图\(G=(V, E)\)，我们在上一篇博客《谱图论：Laplacian二次型和Markov转移算子》中介绍了其对应的Laplacian二次型： \[\mathcal{E}[f]=\frac{1}{2} \cdot \mathbb{E}_{u \sim v}\left[(f(u)-f(v))^2\right] \] 这里\(f: V\rightarrow \mathbb{R}\)为图的顶点标签，\(u\sim v\)表示服从均匀分布的随机无向边\((u, v)\in E\)。直观地理解，Laplacian二次型刻画了图的“能量”（energy）。\(\mathcal{E}[f]\)的值越小，也就意味着\(f\)更加“光滑”（smooth），即其值不会沿着边变化得太剧烈。 事实上，我们可以做进一步地等价变换： \[\begin{aligned} \mathcal{E}[f] &=\frac{1}{2} \cdot \mathbb{E}_{u \sim v}\left[(f(u)-f(v))^2\right]\\ &= \langle f, f \rangle - \mathbb{E}_{u\sim v}\left[f(u)f(v)\right]\\ &= \langle f, f \rangle - \langle f, Kf \rangle\\ &= \langle f, If - Kf \rangle \\ &= \langle f, (I - K) f \rangle \end{aligned} \] 这\(K\)为我们在上一篇博客中提到的MarKov转移算子，它满足：\((K f)(u)=\mathbb{E}_{v \sim u}[f(v)]\)。 对于最后一个等式而言，我们称算子 \[L = I - K \] 为图\(G\)的 （归一化）Laplacian算子。 注 对于\(d\)-正则图\(G\)而言，我们有 \[L = I - \frac{1}{d} A = \frac{1}{d}(dI - A) \] 这里\(A\)为\(G\)的邻接矩阵，\(dI - A\)被称为非归一化Laplacian算子，或直接被简称为Laplacian算子。 和\(K\)一样，\(L\)也是定义在函数空间\(\mathcal{F}=\{f: V \rightarrow \mathbb{R}\}\)上的线性算子，按照以下规则将\(f\in \mathcal{F}\)映射到\(Lf\in \mathcal{F}\)，满足 \[Lf(u) = f(u) - \mathbb{E}_{v\sim u}[f(v)]， \] 通过研究\(L\)，我们就能把握Laplacian二次型\(\mathcal{E}[f] = \langle f, Lf \rangle\)的特性，从而把握图\(G\)的特性，这是谱图理论中至关重要的一点。 接下来再来看我们熟悉的那个示性函数例子。 例 设图顶点的子集\(S\subseteq V\), 0-1示性函数\(f=\mathbb{I}_S\)用于指示顶点是否在集合\(S\)中，即： \[f(u)=\left\{\begin{array}{lll} 1 & \text { if } & u \in S \\ 0 & \text { if } & u \notin S \end{array}\right. \] 则我们有： \[\begin{aligned} & \langle f, Lf \rangle = \mathbb{E}[f] = \text{Pr}_{u\sim v}[u\in S, v\notin S]\\ & \langle f, f\rangle = \mathbb{E}_{u\sim \pi}[f(u)^2] = \text{Pr}_{u\sim \pi}[u\in S] = \text{vol}(S) \end{aligned} \] 直观地理解，这里\(\text{Pr}_{u\sim v}[u\in S, v\notin S]\)表示“伸出”\(S\)的边占总边数的比例；\(\text{vol}(S)\)表示\(S\)的“体积”。