Spectral Graph Theory 谱图论简谈 图的特征值和拉普拉斯型

最近科研时经常遇到一个名词， spectral graph theory， 很多论文由于缺少这方面知识看不下去，因此找了些材料补充了一下，记录备忘。

“Just as astronomers use stellar spectra to determine the make-up of distant stars… [we aim] to deduce the properties and structure of [networks] from its spectrum.”
-Chapter 1, Spectral Graph Theory by F.R.K. Chung

我们知道，在天体观测中，由于许多天体离我们实在是太过遥远，因此不便直接观察，因此我们往往通过观察光谱来进行天体观测，其中最著名的例子就是由观察到谱线红移而推测出宇宙正在不断扩张。
同样的，一个图的谱也是用于描述图的重要工具。谱图理论就是研究如何通过几个容易计算的定量来描述图的性质。通常的方法是将图编码为一个矩阵然后计算矩阵的特征值（也就是谱 spectrum） 。

Laplacian and eigenvalues

首先对于图$G$, 我们定义$d_v$为节点的度。首先考虑简单图，也就是没有重边和环的图，我们定义矩阵$L$如下：

$$L(u,v)=\left\{ \begin{aligned} d_v &\quad \text{if}\ u=v, \\ -1 &\quad \text{if}\ u\ \text{and}\ v\ \text{are adjacent},\\ 0 &\quad \text{otherwise} \end{aligned} \right.$$

我们令$T$主对角线为图上各顶点度值的对角矩阵，接着可以定义图的Laplacian为：

$$\mathcal{L}(u,v)=\left\{ \begin{aligned} 1 &\quad \text{if}\ u=v\ \text{and}\ d_v\ne0\\ -\frac{1}{\sqrt{d_ud_v}} &\quad \text{if}\ u\ \text{and}\ v\ \text{are adjacent},\\ 0 &\quad \text{otherwise} \end{aligned} \right.$$

所以我们可以得到$\mathcal{L}=T^{-1/2}LT^{-1/2}$ .

如果我们对其取消正则化，那么Unnormalized Laplacian可以写作：

$$\mathcal{L}g(u)=\sum g(u)-g(v)$$

如果图是k正则的，也就是每个点的度均为k，那么$\mathcal{L}=I-1/kA$ .$I$为单位矩阵，$A$为邻接矩阵。
对于一般的没有孤点（度为0的点）的图， 我们有：

$$\begin{array}{c} \mathcal{L} &=&T^{-1/2}LT^{-1/2}\\ &=&I - T^{-1/2}AT^{-1/2} \end{array}$$

接下来我们考虑一般的有权图，此时我们有非正则的Laplacian$\mathcal{L}=D-W$ , 这里$D$就是$T$ 也就是度数对角矩阵，$W$为权重矩阵。
由此可以推得图的Laplacian的一些性质：

• $x^T\mathcal{L}x=\frac{1}{2}\sum w_{ij}(x_i-x_j)^2$
• $\mathcal{L}\times \mathbf{1} = \mathbf{0}$ 即0肯定为Laplacian的一个特征值
• $0=\lambda_1 \lt \lambda_2 \le …\lambda_n $

这时的特征值的集合就被称作$\mathcal{L}$的谱(spectrum)。

Laplacian可以被看作是一种函数空间上函数的一种操作，该空间中的函数$g:V(G)\rightarrow\mathbb{R}$将每个节点都映射到一个数上去。这种操作满足：

$$\mathcal{L}g(u)=\frac{1}{\sqrt{d_u}}\sum_{\tiny\begin{array}{c}v\\u\sim~v \end{array}}{\frac{g(u)}{\sqrt{d_u}} - \frac{g(v)}{\sqrt{d_v}}}$$

我们令$g$为任意一个给每个定点赋予一个值$g(v)$的函数，那么可以将其看作一个向量。那么：

$$\begin{array}{c} \frac{\langle g,\mathcal{L}g\rangle}{\langle g,g\rangle} & = & \frac{\langle g,T^{-1/2}LT^{-1/2}g \rangle}{\langle g, g \rangle} \\ &=&\frac{\langle f, Lf \rangle}{\langle T^{1/2}f, T^{1/2}f \rangle}\\ &=&\frac{\sum_{u\sim v}(f(u) - f(v))^2}{\sum_vf(v)^2d_v} \end{array}$$

这里$g=T1^{1/2}$ 而$\langle f,g \rangle$表示内积操作, $\sum(f(u)-f(v))^2$即为Dirichlet sum。