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

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

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

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

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

实际上如果扩展到有向图(比如把无向图的每条边转化为两条方向相反的有向边),定义Incidence Matrix( ):

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

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

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

假设L的n个特征值和对应的特征向量分别为 ,满足 ,并且对于第二小的特征向量 ,定义:

则有:

(1)

(2)如果G是连通图,那么 都是连通的,如果 那么 可能不连通。

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