论文笔记 – Spectra of Simple Graphs

1 简介

谱图理论是图论和线代的交叉学科。这篇论文(或者说讲义?)介绍了谱理论的基础知识。前面介绍一些图论的基本概念,然后介绍邻接矩阵、拉普拉斯矩阵,然后介绍几种简单的图的谱,最后,探究谱、团和染色数的关系。(我感觉)这些都是机器学习里面谱方法的预备知识,也是理解 GCN 等必要的知识。

2 预备知识

2.1 图论基础

下面是一些基础定义,简单列举:

  1. 图(graph):$G = (V,E)$
  2. 相邻顶点(adjacent):$v_{ij}\in E$
  3. 简单图(simple graph):没有平行边(两个顶点之间最多一条边)和自环(顶点到自己的边)的图。本文仅讨论简单图
  4. 图的阶(order):$|G| = |V|$ 等于顶点数
  5. 顶点的度(degree):$deg(v)$ 等于从顶点发出的边数。称 0 度的顶点为孤立点(isolated vertex),称 1 度点为悬垂点(pendant vertex)
  6. 路径(walk):无需解释
  7. 闭环路径(closed walk):起点终点为相同顶点
  8. 环(cycle):每个边最多只走一次的闭环路径
  9. 连通(connected):任意两个顶点之间都有路径
  10. 图的直径(diameter):两个顶点的最远距离
  11. 邻接矩阵(adjacent matrix):$A = \{0,1\} \in R^{v\times v}$
  12. 简单图的邻接矩阵:对称、对角线全零

定理 2.1:$A^k$ 中的项 $a_{ij}$ 表示顶点 $i$ 到 $j$ 的长度为 $k$ 的路径个数。

证明:$A^k$ 的第 $i$ 行表示从顶点 $i$ 到其它各点的长度为 $k$ 的路径数,$A$ 的第 $j$ 列表示和顶点 $j$ 相邻的顶点,那么这样行列相乘,得到的 $A^{(k+1)}$ 中的 $a_{ij}$,就是从顶点 $i$ 到 $j$ 的长度为 $k+1$ 的路径数。

根据定理 2.1 可推,对于阶为 $n$ 的图来说,$A + A^2 + A^3 + … + A^{n-1}$ 中的一项 $a_{ij}$ 表示从顶点 $i$ 到 $j$ 的所有路径条数(因为 $n$ 阶图的直径最大是 $n-1$)。

如果一个图是连通图,那么任意两点之间都有路径,且距离都小于图的直径,即 $\sum_{k=1}^{n-1} A^k$ 的每一项都为正数。那么反过来,我们可以用这个结论计算图的直径:满足 $\sum_{k=1}^{r} A^k$ 每项都为正数的最小的 $r$ 即为图的直径。

但是,有时候图比较复杂,算这样求幂相加比较困难。我们可以令 $B = A+I$(就是把对角线补成 1),满足 $B^r$ 每项都为正数的最小的 $r$ 即为图的直径。或者表述为:

引理 2.1:如果 $B^{n-1}$ 每项都是正数,那么这是一个连通图。

证明:

$$\begin{aligned} (A+I)^r &= \sum_{k=0}^r \left(\begin{array}{c}r\\k\end{array}\right) A^{r-k}I^k \\ &= A^r + \left(\begin{array}{c}r\\1\end{array}\right) A^{r-1} + \left(\begin{array}{c}r\\2\end{array}\right) A^{r-2} + … + I^k \end{aligned} $$

这和 $\sum_{k=1}^{r} A^k$ 只差一些系数。

2.2 几种简单的图

我就不画图了,只写一下它们邻接矩阵的格式。

  1. 线形(path):$|i-j|=1$ 时,$a_{ij} = 1$,其余为零。
  2. 环形(cycle):$|i-j|=1$ 或者 $n-1$ 时,$a_{ij} = 1$,其余为零。
  3. 完全图(complete graph):$|i-j|\ne 0$ 或者 $n-1$ 时,$a_{ij} = 1$,其余为零。
  4. 二分图(bipartite graph):$A=\left[\begin{array}{cc}O&B\\B^T&O\end{array}\right]$,其中 $B\in R^{x\times y}, x+y=n$。
  5. 完全二分图(complete bipartite graph):$A=\left[\begin{array}{cc}O&C\\C^T&O\end{array}\right]$,其中 $C\in R^{x\times y}$,每项均为 1。
  6. 星形(star):这个形状是,只有一个中心,其他的都只连着它。$i$ 或 $j=1$ 时,$a_{ij} = 1$,$i=j$ 时为零,其余为零。

2.3 拉普拉斯矩阵

  1. 度矩阵:对角矩阵,$a_{ii} = deg(v_i)$
  2. 拉普拉斯矩阵:$L=D-A$,对角线上数字 $\ge$ 0,其它地方 $\le$ 0

2.4 谱

  1. 特征值:图邻接矩阵的特征值叫做图的邻接谱(adjacency spectrum),图拉普拉斯矩阵的特征值叫做图的拉普拉斯谱(laplacian spectrum)(由于都是对称矩阵,故特征值都是实数)。
  2. 迹:$trace(A) = \sum \lambda_i = 0,trace(L)=\sum v_i=\frac{1}{2}e(G)$(边数的一半)

3 几种简单图的谱

这一部分的目的是,推导各种图的邻接矩阵的特征多项式,对应的特征值就是 Adjacency Spectrum。有推倒的都是很简单的线代,我就不放上了,直接写结论了。

以下 $F_n$ 是特征多项式(或者有的只有递推式),$S_n$ 是邻接谱。

  1. 星形:$F_n = \lambda^{n-2}(\lambda^2 – (n-1)),\;S_n = \{\sqrt{n-1},0^{n-2},-\sqrt{n-1}\}$
  2. 线形:$f_k = \lambda f_{k-1} – f_{k-2},\; P_n = 2\cos (\frac{\pi j}{n+1}),\;j=1,2,…,n$
  3. 完全图:$f_{K_n}(x) = (x-n+1)(x+1)^{n-1},\; Kn = \{n-1, (-1)^{n-1}\}$
  4. 环形:$C_n = 2\cos(\frac{2\pi j}{n}), j=0,1,…,n-1$
  5. 完全二分图:$K_{n,m} = \{-\sqrt{mn},0^{n+m-2},\sqrt{mn}\}$

4 团(Clique)和染色数(Chromatic Number)

4.1 团数

定义:团是(clique)顶点的集合,满足团内的每个顶点两两互相邻接。团是完全子图。定义 i-clique 是有 $i$ 个顶点的团。

1-clique 的数量是顶点的数量,2-clique 的数量是边的数量。

定义:团数(clique number)$cl(G)$ 等于图中最大的完全子图个数。

定义:如果图不包含顶点数为 $p+1$ 的完全子图,那么这个图被称作 $K_{p+1}-free$

定理:如果图 $G\;K_{p+1}-free$,那么邻接矩阵的最大特征值 $\lambda_1$ 满足:

$$\lambda_1 \le \sqrt{2\frac{p-1}{p}e(g)}\le \sqrt{2\frac{cl(G)-1}{cl(G)}e(g)}$$

通过这个式子可以反推,得到:

$$cl(G) \ge \dfrac{1}{1-\frac{\lambda_1^2}{2e(g)}}$$

就可以从最大特征值得到团数的下界。

4.2 图的最大团

Turans Theorem:如果图是 $K_{p+1}-free$,那么有:

$$e(g)\le\frac{p-1}{2p}n^2$$

联合 4.1 式子,可以得:

$$cl(G)\ge\frac{n}{n-\lambda_1}$$

这是团数的另一个下界,上面那个是和边数相关,这个只跟顶点数数相关。

4.3 染色数

染色数 $\chi(G)$ 是使每个边的两个端点颜色都不同的染色的最小颜色数目。染色数一定大于团数。

定理:$\lambda_n$ 是最小特征值,那么有:

$$1+\frac{\lambda_1}{\lambda_n}\le \chi(G)\le 1+\lambda_1$$

于是可以得到 $\lambda_1$ 的上下界:

$$\chi(G)-1\le\lambda_1\le\frac{\chi(G)-1}{\chi(G)}n$$

(这个第四部分的所有结论都没有证明,很烦,需要看一下 [2],那里有)

5 连通性

We show not only how spectra help determine the shape of a graph, but also how the eigenvalues associated with a graph give information that vertex and edge connectives do not provide.

5.1 点联通(Vertex Connectivity)和边联通(Edge Connectivity)

  • 点连通度:为了使图不连通,去掉最少的顶点的数量;
  • 边联通度:为了使图不连通,去掉最少的边的数量;

点联通度和边连通度都能描述“使图不连通的难易程度”,勉强算是一种描述连通性的指标。但是,下面的两个图,点联通度和边连通度都相等,但明显图 b 要比 a 更“联通”。

从另外一个角度来讲,如果图中两点距离更小(经历的边更少),那么这个图的连通性更强。为了衡量它,我们引入代数联通度 $a(G)$。

5.2 代数联通度(Algebraic Connectivity)

代数联通度:图拉普拉斯矩阵的第二小的特征值 $v_{n-1}$(不过我看网上也有人写是“最小非零特征值”🤔)

对于 k 正规图(每个顶点的度都是 k),$a(G) = k-\lambda_2(G)$

如果 $G$ 是连通图,那么 $v_{n-1}>0$。因为拉普拉斯矩阵的零特征值个数等于图的连通区域个数。(这个可以用谱聚类中间的推导来理解,特征值为零,那这割的一刀代价就是 0,也就是这一刀本来就是不连通的,详见谱聚类和 [3])

因此我们得到推论:如果 $G$ 是 k 正规图,那么 $G$ 是连通图 $\Leftrightarrow$ $\lambda_2\le k$

6 总结

看过整篇文章,发现介绍的东西跟谱图理论没啥关系。。。浪费一天时间。。。

7 引用和拓展阅读

[1] Owen Jones, "Spectra of Simple Graphs", https://www.whitman.edu/Documents/Academics/Mathematics/Jones.pdf

[2] Hoffman, A.J. On eigenvalues and colorings of graphs, Graph Theory and its Applications, Academic Press, New York (1970)

[3] 谱图理论(spectral graph theory) 深度好文!必看!

[mathjax]

Leave a Comment

电子邮件地址不会被公开。