研一上学期听数学课时第一次听到Graph Laplacian这个词,当时很不明白,现在看Metric Learning时再一次遇见,一样的不太明白,唉,抄公式做个记录看以后能不能理解吧。

首先是两个非常简单易懂的概念,邻接矩阵(Adjacency Matrix)和Degree Matrix(怎么翻译?),以无向图为例,假设 \(d_i\) 代表顶点 \(i\) 的度(因为无向图,所以不分初度和入度):

\[A_{i,j} = \left\{ \begin{array}{ll} 1 & \textrm{(i,j)\in E}\\ 0 & \textrm{otherwise} \end{array} \right .\] \[D_{i,j} = \left\{ \begin{array}{ll} d_i & \textrm{i=j}\\ 0 & \textrm{otherwise} \end{array} \right .\]

对于邻接矩阵,如果仔细观察,可以发现它非常神奇的代表着某种针对顶点函数(即对每个顶点赋值的函数 \(f(v_i)\) )的运算符:

\[g=Af; \quad g(i) = \sum_{(i,j) \in E}f(j)\] \[f^TAf=\sum_{(i,j) \in E}f(j)^2\]

现在借助这两个矩阵,我们可以得到一个叫做Graph Laplacian的矩阵:

\[L=D-A=\left\{\begin{array}{ll} d_i & \textrm{i=j}\\ -1 & \textrm{(i,j) \in E}\\ 0 & \textrm{otherwise} \end{array} \right .\]

这个奇怪的Graph Laplacian矩阵乍一眼看上去并没有什么特殊的地方,但是如果仔细观察一下,可以发现它首先是一个对称的半正定矩阵,此外,它同样代表者某种顶点函数的运算符:

\[(Lf)_i=\sum_{(i,j) \in E}(f(i)-f(j))\] \[f^TLf = \sum_{(i,j) \in E}(f(i)-f(j))^2\]

实际上如果扩展到有向图(比如把无向图的每条边转化为两条方向相反的有向边),定义Incidence Matrix( \(\bigtriangledown \in {\mathbb R}^{\|E\|\times \|V\|}\) ):

\[\bigtriangledown := \left\{ \begin{array}{ll} -1 & \textrm{v is the initial vertex of edge e}\\ 1 & \textrm{v is the terminal vertex of edge e}\\ 0 & \textrm{v is not in e}\end{array} \right .\]

我们还可以得到Graph Laplacian的另外一种形式:

\[L=D-A=\bigtriangledown^T\bigtriangledown\]

如果把上面这种普通的0、1邻接图改为边带权重的图模型,则有:

\[(Lf)_i=\sum_{(i,j) \in E}W_{ij}(f(i)-f(j))\] \[f^TLf = \frac{1}{2}\sum_{(i,j) \in E}W_{ij}(f(i)-f(j))^2\]

对于这个Graph Laplacian,除了用作运算符,还可以用来分析图的一些性质,比如Fiedler theory

假设L的n个特征值和对应的特征向量分别为 \(Lv_i=\lambda v_i, \qquad v_i \neq 0, \qquad i=0,1,\cdots,n-1\) ,满足 \(0=\lambda_0 \le \lambda_1 \le \cdots \le \lambda_{n-1}\) ,并且对于第二小的特征向量 \(v_1\) ,定义:

\[\begin{array}{ll} N_- &= \{i\quad :\quad v_1(i)<0\}\\N_+ &= \{i\quad :\quad v_1(i)>0\}\\N_0 &= \{i\quad :\quad v_1(i)=0\}\end{array}\]

则有:

(1) \(\#\{i|\lambda_i=0\}=\#\{connected\quad components\quad of\quad G\}\) ;

(2)如果G是连通图,那么 \(N_-\) 和 \(N_+\) 都是连通的,如果 \(N_0\neq 0\) 那么 \(N_-\cup N_0\) 和 \(N_+ \cup N_0\) 可能不连通。

对于第一点,我们可以认为Graph Laplacian的0特征值重数等于原图连通分量的个数,例如,若 \(\lambda_1 = 0\) ,则原图至少存在两个连通分量,若 \(\lambda_1 \neq 0\) ,则原图是连通的;而对于第二点,可以认为在 \(N_0\) 为空时,Graph Laplacian为我们提供了一种把原图划分为两个连通分量的方法。