一个无向图的邻接矩阵也是个实对称矩阵，它能否运用实对称矩阵的某些特有性质实现某些运用呢？ 第1页

要说无向图对应的对称Laplace矩阵特有的性质的话，其实还真一时想不起来，毕竟基础领域里的人都特别热爱推广，无向图上的东西会推广到更一般的有向图上。而无向图也可以看作是特殊的双向连接的有向图。

限定在比较基础的知识上吧，比如最小生成树、谱聚类（无向图上的谱分解）之类的。当然不得不说的是这些都是存在有向图版本的，但在无向图上的应用多很多。

好，来到最小生成树，下面会介绍最小生成树的计数跟一个快速逼近的算法。再次声明最小生成树的计数有有向图版本，但快速逼近算法应该还没有人提。

对于一个无向图而言，其所谓的最小生成树就是一个连通了所有顶点的子图，而且是棵树。要得到一课最小生成树，那么可以考虑

• Kruskal Algorithm
• Prim Algorithm

最小生成树计数

但今天的问题不是这个，而是计算最小生成树总数。比如这个图：

一共有4种最小生成树，

这种简单还好枚举，更复杂的就需要点代数方法了。

还是以上面的图为例，构造邻接矩阵：

再构造度矩阵：

然后就得到了Laplace矩阵

观察得L是个半正定对称矩阵。然后就比较魔术了，选取任意的第行第列，比如，删除它们，得到子矩阵：

本来半正定的式子变成正定了，然后计算其行列式值

刚好是其最小生成树的总数。 这个就是 Kirchhoff’s Matrix Tree Theorem，对任意大的无向图，都有子矩阵行列式值跟最小生成树总数相等，更准确的表述请参考链接1。总之，一个组合计数问题转换成了一个线性代数问题。一个看起来比较麻烦的问题变成了一个可以简单硬算的问题。

快速算法

对于某些超大型的图，也被称作复杂网络，其最小生成树的总数可以作为连通性的一种指标，那么如果使用Kirchhoff’s Matrix Tree Theorem进行计算的话，就需要算矩阵的行列式。

如果是稠密矩阵，其计算量相当于一次LU分解，N个节点的图对应计算的时间复杂度就是

后来有人（参考链接3）意识到了下面这个算法（参考链接2）刚好可以干这个事情

Han, Insu, Dmitry Malioutov, and Jinwoo Shin. "Large-scale log-determinant computation through stochastic Chebyshev expansions." International Conference on Machine Learning. PMLR, 2015.

用了一种有趣的随机算法对进行逼近。对于任何一个正定矩阵，假设其最大特征值的一个任意上界为吗，先做变换，平移下特征值到 区间上，

那么有

其中 是N阶的正交多项式投影，也就是正交多项式展开逼近。另一方面，把矩阵放在多项式里计算也是挺费事的，幸运的是最后也只需要计算trace

更准确地讲，是

其中u是归一化的高斯随机向量或者Rademacher随机向量，这里的B得是个对称矩阵。

然后只要采几个样进行逼近，矩阵跟矩阵的乘法也不用算了。剩下再用三项递推公式来继续减少计算量，总计算量就是几个矩阵向量乘法跟向量求和平均了，时间复杂度大概在:

不知道上面这个算不算利用了Laplace矩阵的对称性质，逼近算法本身倒是跟混沌多项式的思想挺像的：

参考链接：

[1] Kirchhoff’s Matrix Tree Theorem https://en.wikipedia.org/wiki/Kirchhoff%27s_theorem

[2] 原算法 http://proceedings.mlr.press/v37/hana15.html

[3] 在图上的应用 https://www.sciencedirect.com/science/article/abs/pii/S0898122117307010