调和矩阵

在图论中，调和矩阵（harmonic matrix），也称拉普拉斯矩阵或拉氏矩阵（Laplacian matrix）、离散拉普拉斯（discrete Laplacian），是图的矩阵表示。

调和矩阵也是拉普拉斯算子的离散化。换句话说，调和矩阵的缩放极限是拉普拉斯算子。它在机器学习和物理学中有很多应用。

## 定义

若G是简单图，G有n个顶点，A是邻接矩阵，D是度数矩阵，则调和矩阵是

$$L = D - A$$

$$L_{i,j} := \begin{cases} <pre> \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} </pre> \end{cases}$$

### 动机

这跟拉普拉斯算子有什么关系？若f 是加权图G的顶点函数，则

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

w是边的权重函数。u、v是顶点。f = (f(1), ..., f(n)) 是n维的矢量。上面泛函也称为Dirichlet泛函。

### 接续矩阵

而且若K是接续矩阵（incidence matrix），则

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

$$L = K^tK$$

Kf 是f 的图梯度。另外，特征值满足

$$\begin{align} <pre> \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) \\ </pre> \end{align}$$

## 举例

图｜度矩阵｜邻接矩阵｜调和矩阵

<image>

｜$\left(\begin{array}{rrrrrr} 2 & 0 & 0 & 0 & 0 & 0\\ 0 & 3 & 0 & 0 & 0 & 0\\ 0 & 0 & 2 & 0 & 0 & 0\\ 0 & 0 & 0 & 3 & 0 & 0\\ 0 & 0 & 0 & 0 & 3 & 0\\ 0 & 0 & 0 & 0 & 0 & 1\\ \end{array}\right)$｜$\left(\begin{array}{rrrrrr} 0 & 1 & 0 & 0 & 1 & 0\\ 1 & 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0\\ \end{array}\right)$｜$\left(\begin{array}{rrrrrr} 2 & -1 & 0 & 0 & -1 & 0\\ -1 & 3 & -1 & 0 & -1 & 0\\ 0 & -1 & 2 & -1 & 0 & 0\\ 0 & 0 & -1 & 3 & -1 & -1\\ -1 & -1 & 0 & -1 & 3 & 0\\ 0 & 0 & 0 & -1 & 0 & 1\\ \end{array}\right)$

## 其他形式

### 对称正规化调和矩阵

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

$$L^\text{sym}_{i,j} := \begin{cases} <pre> 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}. </pre> \end{cases}$$

注意

$$<pre> \lambda \ = \ \frac{\langle g, L^\text{sym}g\rangle}{\langle g, g\rangle} \ = \ \frac{\left\langle g, D^{-\frac{1}{2}} L D^{-\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, </pre>$$

### 随机漫步

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

$$L^\text{rw}_{i,j} := \begin{cases} <pre> 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}. </pre> \end{cases}$$

## 动力学和微分方程

例如，离散的冷却定律使用调和矩阵

$$\begin{align} <pre> \frac{d \phi_i}{d t} &= -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. </pre> \end{align}$$

使用矩阵矢量

$$\begin{align} <pre> \frac{d\phi}{dt} &= -k(D - A)\phi \\ &= -kL \phi </pre> \end{align}$$

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

解是

$$\begin{align} <pre> \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 + k c_i L \mathbf{v}_i\right] &= \\ \sum_i \left[\frac{dc_i}{dt} \mathbf{v}_i + k c_i \lambda_i \mathbf{v}_i\right] &= \\ \frac{dc_i}{dt} + k \lambda_i c_i &= 0\\ </pre> \end{align}$$

$$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} <pre> 0 & \text{if} & \lambda_i > 0 \\ 1 & \text{if} & \lambda_i = 0 </pre> \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代码

```matlab
N = 20;%The number of pixels along a dimension of the image
A = zeros(N, N);%The image
Adj = zeros(N*N, N*N);%The adjacency matrix

%Use 8 neighbors, and fill in the adjacency matrix
dx = [-1, 0, 1, -1, 1, -1, 0, 1];
dy = [-1, -1, -1, 0, 0, 1, 1, 1];
for x = 1:N
   for y = 1:N
       index = (x-1)*N + y;
       for ne = 1:length(dx)
           newx = x + dx(ne);
           newy = y + dy(ne);
           if newx > 0 && newx <= N && newy > 0 && newy <= N
               index2 = (newx-1)*N + newy;
               Adj(index, index2) = 1;
           end
       end
   end
end

%%%BELOW IS THE KEY CODE THAT COMPUTES THE SOLUTION TO THE DIFFERENTIAL
%%%EQUATION
Deg = diag(sum(Adj, 2));%Compute the degree matrix
L = Deg - Adj;%Compute the laplacian matrix in terms of the degree and adjacency matrices
[V, D] = eig(L);%Compute the eigenvalues/vectors of the laplacian matrix
D = diag(D);

%Initial condition (place a few large positive values around and
%make everything else zero)
C0 = zeros(N, N);
C0(2:5, 2:5) = 5;
C0(10:15, 10:15) = 10;
C0(2:5, 8:13) = 7;
C0 = C0(:);

C0V = V'*C0;%Transform the initial condition into the coordinate system 
%of the eigenvectors
for t = 0:0.05:5
   %Loop through times and decay each initial component
   Phi = C0V.*exp(-D*t);%Exponential decay for each component
   Phi = V*Phi;%Transform from eigenvector coordinate system to original coordinate system
   Phi = reshape(Phi, N, N);
   %Display the results and write to GIF file
   imagesc(Phi);
   caxis([0, 10]);
   title(sprintf('Diffusion t = %3f', t));
   frame = getframe(1);
   im = frame2im(frame);
   [imind, cm] = rgb2ind(im, 256);
   if t == 0
      imwrite(imind, cm, 'out.gif', 'gif', 'Loopcount', inf, 'DelayTime', 0.1); 
   else
      imwrite(imind, cm, 'out.gif', 'gif', 'WriteMode', 'append', 'DelayTime', 0.1);
   end
end
```

<image>

## 应用

- Kirchoff定理：调和矩阵的行列式
- 人工智能
- 非线性降维
- 谱聚类
- Cheeger不等式：调和矩阵的第二大的特征值跟最大割问题有关
- 图Signal processing

## 阅读

- B. Bollobás, Modern Graph Theory, Springer-Verlag (1998, corrected ed. 2013), , 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).