1 简介
谱图理论是图论和线代的交叉学科。这篇论文（或者说讲义？）介绍了谱理论的基础知识。前面介绍一些图论的基本概念，然后介绍邻接矩阵、拉普拉斯矩阵，然后介绍几种简单的图的谱，最后，探究谱、团和染色数的关系。（我感觉）这些都是机器学习里面谱方法的预备知识，也是理解 GCN 等必要的知识。
2 预备知识
2.1 图论基础
下面是一些基础定义，简单列举：
- 图（graph）：$G = (V,E)$
- 相邻顶点（adjacent）：$v_{ij}\in E$
- 简单图（simple graph）：没有平行边（两个顶点之间最多一条边）和自环（顶点到自己的边）的图。本文仅讨论简单图
- 图的阶（order）：$|G| = |V|$ 等于顶点数
- 顶点的度（degree）：$deg(v)$ 等于从顶点发出的边数。称 0 度的顶点为孤立点（isolated vertex），称 1 度点为悬垂点（pendant vertex）
- 路径（walk）：无需解释
- 闭环路径（closed walk）：起点终点为相同顶点
- 环（cycle）：每个边最多只走一次的闭环路径
- 连通（connected）：任意两个顶点之间都有路径
- 图的直径（diameter）：两个顶点的最远距离
- 邻接矩阵（adjacent matrix）：$A = \{0,1\} \in R^{v\times v}$
- 简单图的邻接矩阵：对称、对角线全零
定理 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 几种简单的图
我就不画图了，只写一下它们邻接矩阵的格式。
- 线形（path）：$|i-j|=1$ 时，$a_{ij} = 1$，其余为零。
- 环形（cycle）：$|i-j|=1$ 或者 $n-1$ 时，$a_{ij} = 1$，其余为零。
- 完全图（complete graph）：$|i-j|\ne 0$ 或者 $n-1$ 时，$a_{ij} = 1$，其余为零。
- 二分图（bipartite graph）：$A=\left[\begin{array}{cc}O&B\\B^T&O\end{array}\right]$，其中 $B\in R^{x\times y}, x+y=n$。
- 完全二分图（complete bipartite graph）：$A=\left[\begin{array}{cc}O&C\\C^T&O\end{array}\right]$，其中 $C\in R^{x\times y}$，每项均为 1。
- 星形（star）：这个形状是，只有一个中心，其他的都只连着它。$i$ 或 $j=1$ 时，$a_{ij} = 1$，$i=j$ 时为零，其余为零。
2.3 拉普拉斯矩阵
- 度矩阵：对角矩阵，$a_{ii} = deg(v_i)$
- 拉普拉斯矩阵：$L=D-A$，对角线上数字 $\ge$ 0，其它地方 $\le$ 0
2.4 谱
- 特征值：图邻接矩阵的特征值叫做图的邻接谱（adjacency spectrum），图拉普拉斯矩阵的特征值叫做图的拉普拉斯谱（laplacian spectrum）（由于都是对称矩阵，故特征值都是实数）。
- 迹：$trace(A) = \sum \lambda_i = 0,trace(L)=\sum v_i=\frac{1}{2}e(G)$（边数的一半）
3 几种简单图的谱
这一部分的目的是，推导各种图的邻接矩阵的特征多项式，对应的特征值就是 Adjacency Spectrum。有推倒的都是很简单的线代，我就不放上了，直接写结论了。
以下 $F_n$ 是特征多项式（或者有的只有递推式），$S_n$ 是邻接谱。
- 星形：$F_n = \lambda^{n-2}(\lambda^2 – (n-1)),\;S_n = \{\sqrt{n-1},0^{n-2},-\sqrt{n-1}\}$
- 线形：$f_k = \lambda f_{k-1} – f_{k-2},\; P_n = 2\cos (\frac{\pi j}{n+1}),\;j=1,2,…,n$
- 完全图：$f_{K_n}(x) = (x-n+1)(x+1)^{n-1},\; Kn = \{n-1, (-1)^{n-1}\}$
- 环形：$C_n = 2\cos(\frac{2\pi j}{n}), j=0,1,…,n-1$
- 完全二分图：$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]