接续矩阵

在圖論中，**調和矩陣**（**harmonic matrix**），也稱**拉普拉斯矩陣**或**拉氏矩陣**（**Laplacian matrix**）、**離散拉普拉斯**（**discrete Laplacian**），是圖的矩陣表示。

調和矩陣也是拉普拉斯算子的離散化。換句話說，調和矩陣的縮放極限是拉普拉斯算子。它在機器學習和物理學中有很多應用。

## 定義

若 G 是簡單圖，G 有 n 個頂點，A 是鄰接矩陣，D 是度數矩陣，則**調和矩陣**是

$$
L=D-A
$$

$$
L_{i,j}:={\begin{cases}\deg(v_{i})&{\mbox{if}}\ i=j\\-1&{\mbox{if}}\ i\neq j\ {\mbox{and}}\ v_{i}{\mbox{ is adjacent to }}v_{j}\\0&{\mbox{otherwise}}\end{cases}}
$$

### 動機

這跟拉普拉斯算子有什麼關係？若 f 是加權圖 G 的頂點函數，則

$$
E(f)=\sum w(uv)(f(u)-f(v))^{2}/2=f^{t}Lf
$$

w 是邊的權重函數。u、v 是頂點。f = (f (1), ..., f (n)) 是 n 維的矢量。上面泛函也稱為 Dirichlet 泛函。

### 接續矩陣

而且若 K 是接續矩陣（incidence matrix），則

$$
K_{ev}=\left\{{\begin{array}{rl}1,&{\text{if }}v=i\\-1,&{\text{if }}v=j\\0,&{\text{otherwise}}.\end{array}}\right.
$$

$$
L=K^{t}K
$$

Kf 是 f 的圖梯度。另外，特徵值滿足

$$
{\begin{aligned}\lambda _{i}&=\mathbf {v} _{i}^{\textsf {T}}L\mathbf {v} _{i}\\&=\mathbf {v} _{i}^{\textsf {T}}M^{\textsf {T}}M\mathbf {v} _{i}\\&=\left(M\mathbf {v} _{i}\right)^{\textsf {T}}\left(M\mathbf {v} _{i}\right)\\\end{aligned}}
$$

## 舉例

## 其他形式

### 對稱正規化調和矩陣

$$
L^{\text{sym}}:=D^{-{\frac {1}{2}}}LD^{-{\frac {1}{2}}}=I-D^{-{\frac {1}{2}}}AD^{-{\frac {1}{2}}}
$$

$$
L_{i,j}^{\text{sym}}:={\begin{cases}1&{\mbox{if }}i=j{\mbox{ and }}\deg(v_{i})\neq 0\\-{\frac {1}{\sqrt {\deg(v_{i})\deg(v_{j})}}}&{\mbox{if }}i\neq j{\mbox{ and }}v_{i}{\mbox{ is adjacent to }}v_{j}\\0&{\mbox{otherwise}}.\end{cases}}
$$

注意

$$
\lambda \ =\ {\frac {\langle g,L^{\text{sym}}g\rangle }{\langle g,g\rangle }}\ =\ {\frac {\left\langle g,D^{-{\frac {1}{2}}}LD^{-{\frac {1}{2}}}g\right\rangle }{\langle g,g\rangle }}\ =\ {\frac {\langle f,Lf\rangle }{\left\langle D^{\frac {1}{2}}f,D^{\frac {1}{2}}f\right\rangle }}\ =\ {\frac {\sum _{u\sim v}(f(u)-f(v))^{2}}{\sum _{v}f(v)^{2}d_{v}}}\ \geq \ 0,
$$

### 隨機漫步

$$
L^{\text{rw}}:=D^{-1}L=I-D^{-1}A
$$

$$
L_{i,j}^{\text{rw}}:={\begin{cases}1&{\mbox{if }}i=j{\mbox{ and }}\deg(v_{i})\neq 0\\-{\frac {1}{\deg(v_{i})}}&{\mbox{if }}i\neq j{\mbox{ and }}v_{i}{\mbox{ is adjacent to }}v_{j}\\0&{\mbox{otherwise}}.\end{cases}}
$$

## 動力學和微分方程

例如，離散的冷卻定律使用調和矩陣

$$
{\begin{aligned}{\frac {d\phi _{i}}{dt}}&=-k\sum _{j}A_{ij}\left(\phi _{i}-\phi _{j}\right)\\&=-k\left(\phi _{i}\sum _{j}A_{ij}-\sum _{j}A_{ij}\phi _{j}\right)\\&=-k\left(\phi _{i}\ \deg(v_{i})-\sum _{j}A_{ij}\phi _{j}\right)\\&=-k\sum _{j}\left(\delta _{ij}\ \deg(v_{i})-A_{ij}\right)\phi _{j}\\&=-k\sum _{j}\left(\ell _{ij}\right)\phi _{j}.\end{aligned}}
$$

使用矩陣矢量

$$
{\begin{aligned}{\frac {d\phi }{dt}}&=-k(D-A)\phi \\&=-kL\phi \end{aligned}}
$$

$$
{\frac {d\phi }{dt}}+kL\phi =0
$$

解是

$$
{\begin{aligned}{\frac {d\left(\sum _{i}c_{i}\mathbf {v} _{i}\right)}{dt}}+kL\left(\sum _{i}c_{i}\mathbf {v} _{i}\right)&=0\\\sum _{i}\left[{\frac {dc_{i}}{dt}}\mathbf {v} _{i}+kc_{i}L\mathbf {v} _{i}\right]&=\\\sum _{i}\left[{\frac {dc_{i}}{dt}}\mathbf {v} _{i}+kc_{i}\lambda _{i}\mathbf {v} _{i}\right]&=\\{\frac {dc_{i}}{dt}}+k\lambda _{i}c_{i}&=0\\\end{aligned}}
$$

$$
c_{i}(t)=c_{i}(0)e^{-k\lambda _{i}t}
$$

$$
c_{i}(0)=\left\langle \phi (0),\mathbf {v} _{i}\right\rangle
$$

### 平衡舉動

當 $\lim _{t\to \infty }\phi (t)$ 的時候，

$$
\lim _{t\to \infty }e^{-k\lambda _{i}t}=\left\{{\begin{array}{rlr}0&{\text{if}}&\lambda _{i}>0\\1&{\text{if}}&\lambda _{i}=0\end{array}}\right\}
$$

$$
\lim _{t\to \infty }\phi (t)=\left\langle c(0),\mathbf {v^{1}} \right\rangle \mathbf {v^{1}}
$$

$$
\mathbf {v^{1}} ={\frac {1}{\sqrt {N}}}[1,1,...,1]
$$

$$
\lim _{t\to \infty }\phi _{j}(t)={\frac {1}{N}}\sum _{i=1}^{N}c_{i}(0)
$$

### MATLAB 代碼

## 應用

* Kirchoff 定理：調和矩陣的行列式
* 人工智慧
* 非線性降維
* 譜聚類
* Cheeger 不等式：調和矩陣的第二大的特徵值跟最大割問題有關
* 圖 Signal processing

## 參考文獻

## 閱讀

* T. Sunada. Chapter 1. Analysis on combinatorial graphs. Discrete geometric analysis. P. Exner, J. P. Keating, P. Kuchment, T. Sunada, A. Teplyaev (編). 'Proceedings of Symposia in Pure Mathematics **77**. 2008: 51–86. ISBN 978-0-8218-4471-7.
* B. Bollobás, _Modern Graph Theory_, Springer-Verlag (1998, corrected ed. 2013), ISBN 0-387-98488-7, Chapters II.3 (Vector Spaces and Matrices Associated with Graphs), VIII.2 (The Adjacency Matrix and the Laplacian), IX.2 (Electrical Networks and Random Walks).