标准化拉普拉斯矩阵特征值范围为什么小于等于2?（证明）

0. 前言

谱图使用标准化拉普拉斯矩阵 $L^{norm}$ 的一个重要原因就是，$L^{norm}$ 比拉普拉斯矩阵$L$ 稳定。很多资料只是简单地介绍了$L^{norm}$ ，在kipfGCN中也只是简单地提到 $L^{norm}$ 的特征值不大于2。本文搜集了相关lecture，并推导部分内容，来证明这个结论。

1. 正文

设标准化邻接矩阵 $A^{norm}$ 的特征值为 ${\alpha }_1\le {\alpha }_2\le \cdots \le {\alpha }_n$；标准化拉普拉斯矩阵 $L^{norm}$ 的特征值为${\lambda }_1\le {\lambda }_2\le \cdots \le {\lambda }_n$。有：

$$-1\le {\alpha }_1\le {\alpha }_2\le \cdots \le {\alpha }_n\le 1$$ $$0\le {\lambda }_1\le {\lambda }_2\le \cdots \le {\lambda }_n\le 2$$

1.1 标准化拉普拉斯是非满秩矩阵

1.1.1 拉普拉斯是非满秩矩阵

首先，证明拉普拉斯矩阵 $L$ 是非满秩矩阵：

令 D = [ d 1 d 2 ⋱ d n ] D = \begin{bmatrix} d_1 & & & \\ & d_2 & & \\ & & \ddots & \\ & & & dn \\ \end{bmatrix} D= ​d1​​d2​​⋱​dn​ ​， A = [ a 11 a 12 ⋯ a 1 n a 21 a 22 ⋯ a 2 n ⋮ ⋮ ⋮ a n 1 a n 2 ⋯ a n n ] A = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \\ \end{bmatrix} A= ​a11​a21​⋮an1​​a12​a22​⋮an2​​⋯⋯⋯​a1n​a2n​⋮ann​​ ​，则：

∣ L ∣ = ∣ D − A ∣ = ∣ d 1 − a 11 − a 12 ⋯ − a 1 n − a 21 d 2 − a 22 ⋯ − a 2 n ⋮ ⋮ ⋮ − a n 1 − a n 2 ⋯ d − a n n ∣ (1) \begin{aligned}\tag{1} |L|=|D-A|=\begin{vmatrix} d_1-a_{11} & -a_{12} & \cdots & -a_{1n} \\ -a_{21} & d_2-a_{22} & \cdots & -a_{2n} \\ \vdots & \vdots & & \vdots \\ -a_{n1} & -a_{n2} & \cdots & d-a_{nn} \\ \end{vmatrix} \end{aligned} ∣L∣=∣D−A∣= ​d1​−a11​−a21​⋮−an1​​−a12​d2​−a22​⋮−an2​​⋯⋯⋯​−a1n​−a2n​⋮d−ann​​ ​​(1)，将第2~n行分别加到第一行，可得第一行的元素为：
$$[d_1+\sum _{i=1}^n(-a_{i1}),d_2+\sum _{i=1}^n(-a_{i2}),...,d_n+\sum _{i=1}^n(-a_{in})]\text{\hspace{1em}(2)}$$，因为度矩阵对角线元素是邻接矩阵对应行（列）的和，因此有：
$$d_1=\sum _{i=1}^n(a_{i1}),d_2=\sum _{i=1}^n(a_{i2}),...,d_n=\sum _{i=1}^n(a_{in})$$，所以 $(2)$ 的元素全为0，即$|L|=0$。

1.1.2 标准化拉普拉斯是非满秩矩阵

其次，证明标准化拉普拉斯矩阵 $L^{norm}$ 是非满秩矩阵：

$\because |L^{norm}|=|D^{-\frac{1}{2}}L{D}^{-\frac{1}{2}}|=|D^{-\frac{1}{2}}||L||D^{-\frac{1}{2}}|$,      $|L|=0$
$\therefore |L^{norm}|=0$

1.1.3 拉普拉斯矩阵及标准化拉普拉斯矩阵特征值与特征向量之间的关系

上一节我们知道，拉普拉斯矩阵 $L$ 和标准化拉普拉斯矩阵 $L^{norm}$ 都是非满秩矩阵，都有至少一个特征值为 0。设 $e$ 是 $L$ 的一个对应于特征值 0 的特征向量，有 $Le=0$。因为：

$L^{norm}{D}^{\frac{1}{2}}e=D^{-\frac{1}{2}}L{D}^{-\frac{1}{2}}{D}^{\frac{1}{2}}e=D^{-\frac{1}{2}}(Le)=0$

所以$D^{\frac{1}{2}}e$ 是 $L^{norm}$ 的一个对应于特征值 0 的特征向量。

1.2 标准化拉普拉斯矩阵是半正定矩阵

1.2.1 标准化邻接矩阵的二次型化简

设 A = [ a 11 a 12 ⋯ a 1 n a 21 a 22 ⋯ a 2 n ⋮ ⋮ ⋮ a n 1 a n 2 ⋯ a n n ] ,   D = [ d 1 d 2 ⋱ d n ] A = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \\ \end{bmatrix},\,D =\begin{bmatrix} d_1 & & & \\ & d_2 & & \\ & & \ddots & \\ & & & d_n \\ \end{bmatrix} A= ​a11​a21​⋮an1​​a12​a22​⋮an2​​⋯⋯⋯​a1n​a2n​⋮ann​​ ​,D= ​d1​​d2​​⋱​dn​​ ​，则 D − 1 2 = [ 1 d 1 1 d 2 ⋱ 1 d n ] D^{-\frac 1 2} =\begin{bmatrix} {\frac 1 {\sqrt{d_1}}} & & & \\ & {\frac 1 {\sqrt{d_2}}} & & \\ & & \ddots & \\ & & & {\frac 1 {\sqrt{d_n}}} \\ \end{bmatrix} D−21​= ​d1​ ​1​​d2​ ​1​​⋱​dn​ ​1​​ ​

标准化邻接矩阵    A n o r m = D − 1 2 A D − 1 2 = [ a 11 d 1 d 1 a 12 d 2 d 1 ⋯ a 1 n d 2 d n a 21 d 2 d 1 a 22 d 2 d 2 ⋯ a 2 n d 2 d n ⋮ ⋮ ⋮ a n 1 d n d 1 a n 1 d n d 1 ⋯ a n n d n d n ] \text{标准化邻接矩阵} \,\,A^{norm} = D^{-\frac 1 2}AD^{-\frac 1 2}= \begin{bmatrix} {\frac {a_{11}} {\sqrt{d_1d_1}}} & {\frac {a_{12}} {\sqrt{d_2d_1}}} & \cdots & {\frac {a_{1n}} {\sqrt{d_2d_n}}} \\ {\frac {a_{21}} {\sqrt{d_2d_1}}} & {\frac {a_{22}} {\sqrt{d_2d_2}}} & \cdots & {\frac {a_{2n}} {\sqrt{d_2d_n}}} \\ \vdots & \vdots & & \vdots \\ {\frac {a_{n1}} {\sqrt{d_nd_1}}} & {\frac {a_{n1}} {\sqrt{d_nd_1}}} & \cdots & {\frac {a_{nn}} {\sqrt{d_nd_n}}} \\ \end{bmatrix} 标准化邻接矩阵Anorm=D−21​AD−21​= ​d1​d1​ ​a11​​d2​d1​ ​a21​​⋮dn​d1​ ​an1​​​d2​d1​ ​a12​​d2​d2​ ​a22​​⋮dn​d1​ ​an1​​​⋯⋯⋯​d2​dn​ ​a1n​​d2​dn​ ​a2n​​⋮dn​dn​ ​ann​​​ ​，令$\mathbf{x}=[x_1,x_2,\cdots ,x_n{]}^T$，则：
x T A n o r m x = [ x 1 , x 2 , ⋯   , x n ] [ a 11 d 1 d 1 a 12 d 2 d 1 ⋯ a 1 n d 2 d n a 21 d 2 d 1 a 22 d 2 d 2 ⋯ a 2 n d 2 d n ⋮ ⋮ ⋮ a n 1 d n d 1 a n 1 d n d 1 ⋯ a n n d n d n ] [ x 1 x 2 ⋮ x n ] = [ ∑ i n x i a i 1 d i d 1 ,   ∑ i n x i a i 2 d i d 2 ,   ⋯   ,   ∑ i n x i a i n d i d n ] [ x 1 x 2 ⋮ x n ] = ∑ i n x i x 1 a i 1 d i d 1 + ∑ i n x i x 2 a i 2 d i d 2 + ⋯ + ∑ i n x i x n a i n d i d n = ∑ i , j n x i x j a i j d i d j = ∑ ( i , j ) ∈ E 2 x i x j a i j d i d j      ( 因为 a i j = a j i , 所以有个 2 ; a i j ∈ { 0 , 1 } , 所以可以消去 . ) \begin{aligned} \bold{x}^TA^{norm}\bold{x}&=[x_1, x_2,\cdots, x_n] \begin{bmatrix} {\frac {a_{11}} {\sqrt{d_1d_1}}} & {\frac {a_{12}} {\sqrt{d_2d_1}}} & \cdots & {\frac {a_{1n}} {\sqrt{d_2d_n}}} \\ {\frac {a_{21}} {\sqrt{d_2d_1}}} & {\frac {a_{22}} {\sqrt{d_2d_2}}} & \cdots & {\frac {a_{2n}} {\sqrt{d_2d_n}}} \\ \vdots & \vdots & & \vdots \\ {\frac {a_{n1}} {\sqrt{d_nd_1}}} & {\frac {a_{n1}} {\sqrt{d_nd_1}}} & \cdots & {\frac {a_{nn}} {\sqrt{d_nd_n}}} \\ \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \\ \end{bmatrix} \\ &=\begin{bmatrix} \sum_i^n{\frac {x_ia_{i1}} {\sqrt{d_id_1}}},\, \sum_i^n{\frac {x_ia_{i2}} {\sqrt{d_id_2}}},\, \cdots,\, \sum_i^n{\frac {x_ia_{in}} {\sqrt{d_id_n}}} \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \\ \end{bmatrix} \\ &= \sum_i^n{\frac {x_ix_1a_{i1}} {\sqrt{d_id_1}}}+ \sum_i^n{\frac {x_ix_2a_{i2}} {\sqrt{d_id_2}}}+ \cdots+ \sum_i^n{\frac {x_ix_na_{in}} {\sqrt{d_id_n}}} \\ &=\sum_{i,j}^n{\frac {x_ix_ja_{ij}} {\sqrt{d_id_j}}} \\ &=\sum_{(i,j)\in E}{\frac {2x_ix_ja_{ij}} {\sqrt{d_id_j}}} \,\,\,\,(因为a_{ij}=a_{ji},所以有个2;a_{ij}\in\{0,1\},所以可以消去.) \end{aligned} xTAnormx​=[x1​,x2​,⋯,xn​] ​d1​d1​ ​a11​​d2​d1​ ​a21​​⋮dn​d1​ ​an1​​​d2​d1​ ​a12​​d2​d2​ ​a22​​⋮dn​d1​ ​an1​​​⋯⋯⋯​d2​dn​ ​a1n​​d2​dn​ ​a2n​​⋮dn​dn​ ​ann​​​ ​ ​x1​x2​⋮xn​​ ​=[∑in​di​d1​ ​xi​ai1​​,∑in​di​d2​ ​xi​ai2​​,⋯,∑in​di​dn​ ​xi​ain​​​] ​x1​x2​⋮xn​​ ​=i∑n​di​d1​ ​xi​x1​ai1​​+i∑n​di​d2​ ​xi​x2​ai2​​+⋯+i∑n​di​dn​ ​xi​xn​ain​​=i,j∑n​di​dj​ ​xi​xj​aij​​=(i,j)∈E∑​di​dj​ ​2xi​xj​aij​​(因为aij​=aji​,所以有个2;aij​∈{0,1},所以可以消去.)​，其中 $E$ 为边的集合。

1.2.2 标准化拉普拉斯矩阵是半正定矩阵的证明

对 $\forall \mathbf{x}\in {\mathbb{R}}^n$，$L^{norm}$的二次型为：
$$\begin{array}{rl}{\mathbf{x}}^T{L}^{norm}\mathbf{x}& ={\mathbf{x}}^T(I-A^{norm})\mathbf{x}\\ & =\sum _{i\in V}{x}_i^2-\sum _{(i,j)\in E}\frac{2x_i{x}_j}{\sqrt{d_i{d}_j}}\\ & =\sum _{(i,j)\in E}(\frac{x_i^2}{d_i}+\frac{x_j^2}{d_j})-\sum _{(i,j)\in E}\frac{2x_i{x}_j}{\sqrt{d_i{d}_j}}\\ & =\sum _{(i,j)\in E}(\frac{x_i}{\sqrt{d_i}}-\frac{x_j}{\sqrt{d_j}}{)}^2\\ & \ge 0\end{array}$$，根据半正定矩阵的定义可知，$L^{norm}$ 为半正定矩阵。

1.3 标准化邻接矩阵的特征值范围

1.3.1 瑞利商（Rayleigh quotient）

在求标准化邻接矩阵 $A^{norm}$ 的特征值范围前，需要了解瑞利商。瑞利商的定义如下：
$$R(A,x)=\frac{x^{T}Ax}{x^{T}x}$$，其中 $A$ 为 $n\times n$ 对称矩阵，$x$ 为 $n$ 维度向量。如果A的特征值为${\lambda }_1\le {\lambda }_2\le \cdots \le {\lambda }_n$，则其瑞利商的下界为${\lambda }_1$，上界为 ${\lambda }_n$。

关于瑞利商，参见我的博客：瑞利商性质及证明。

1.3.2 标准化邻接矩阵的特征值范围计算

$$x^T{L}^{norm}x\ge 0\Rightarrow x^T(I-A^{norm})x\ge 0\Rightarrow x^{T}x-x^T{A}^{norm}x\ge 0\Rightarrow 1\ge \frac{x^T{A}^{norm}x}{x^{T}x}$$，由瑞利商的性质可知，$A^{norm}$ 最大特征值小于等于1，即 ${\alpha }_n\le 1$；当 $x=D^{\frac{1}{2}}e$ 时，${\alpha }_n=1$。

类似于证明 $L^{norm}$ 是半正定矩阵，$I+A^{norm}$ 也是半正定矩阵：

$$x^T(I+A^{norm})x=\sum _{i\in V}{x}_i^2+\sum _{(i,j)\in E}(\frac{x_i}{\sqrt{d_i}}+\frac{x_j}{\sqrt{d_j}}{)}^2\ge 0$$，所以有：
$$x^T(I+A^{norm})x\ge 0\Rightarrow x^{T}x+x^T{A}^{norm}x\ge 0\Rightarrow \frac{x^T{A}^{norm}x}{x^{T}x}\ge -1$$，由瑞利商的性质可知，$A^{norm}$ 最小特征值大于等于-1，即 ${\alpha }_1\ge -1$。

所以标准化邻接矩阵 $A^{norm}$ 的特征值满足$-1\le {\alpha }_1\le {\alpha }_2\le \cdots \le {\alpha }_n=1$

1.3.3 标准化拉普拉斯矩阵的特征值范围计算

$\because$
$$\begin{array}{rl}& \frac{x^T{L}^{norm}x}{x^{T}x}=\frac{x^T(I-A^{norm})x}{x^{T}x}=1-\frac{x^T{A}^{norm}x}{x^{T}x}=1-R(A^{norm},x)\\ & -1\le R(A^{norm},x)\le 1\end{array}$$$\therefore$
$$\begin{array}{rl}& 0\le \frac{x^T{L}^{norm}x}{x^{T}x}\le 2\end{array}$$，其下确界为0，当 $x=D^{\frac{1}{2}}e$ 时，${\lambda }_1=0$。

证毕。

参考网址

拉普拉斯性质
ORIE 6334 Spectral Graph Theory Lecture 7（主要参考了本文）
瑞利商性质及证明
Bounding matrix quadratic form using eigenvalues
Why Laplacian Matrix need normalization and how come the sqrt of Degree Matrix?

$■$文章来源地址https://www.toymoban.com/news/detail-669082.html

到了这里，关于标准化拉普拉斯矩阵特征值范围为什么小于等于2?（证明）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！