调和矩阵

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

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

定义

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

$L=D-A$

$L_{i,j}:=\{\begin{array}{cc}\mathrm{deg}(v_i)& \text{if}i=j\\ -1& \text{if}i\ne j\text{and}{v}_i\text{ is adjacent to }{v}_j\\ 0& \text{otherwise}\end{array}$

动机

这跟拉普拉斯算子有什么关系？若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}=\{\begin{array}{cc}1,& \text{if }v=i\\ -1,& \text{if }v=j\\ 0,& \text{otherwise}.\end{array}$

$L=K^{t}K$

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

$\begin{array}{cc}{\lambda }_i& ={𝐯}_i^{\mathsf{\text{T}}}L{𝐯}_i\\ & ={𝐯}_i^{\mathsf{\text{T}}}{M}^{\mathsf{\text{T}}}M{𝐯}_i\\ & ={\left(M{𝐯}_i\right)}^{\mathsf{\text{T}}}\left(M{𝐯}_i\right)\\ \end{array}$

举例

图	度矩阵	邻接矩阵	调和矩阵
	$\left(\begin{array}{cccccc}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}{cccccc}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}{cccccc}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_{i,j}^{\text{sym}}:=\{\begin{array}{cc}1& \text{if }i=j\text{ and }\mathrm{deg}(v_i)\ne 0\\ -\frac{1}{\sqrt{\mathrm{deg}(v_i)\mathrm{deg}(v_j)}}& \text{if }i\ne j\text{ and }{v}_i\text{ is adjacent to }{v}_j\\ 0& \text{otherwise}.\end{array}$

注意

$\lambda =\frac{⟨g,L^{\text{sym}}g⟩}{⟨g,g⟩}=\frac{⟨g,D^{-\frac{1}{2}}L{D}^{-\frac{1}{2}}g⟩}{⟨g,g⟩}=\frac{⟨f,Lf⟩}{⟨D^{\frac{1}{2}}f,D^{\frac{1}{2}}f⟩}=\frac{\sum _{u\sim v}(f(u)-f(v){)}^2}{\sum _{v}f(v{)}^2{d}_v}\ge 0,$

随机漫步

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

$L_{i,j}^{\text{rw}}:=\{\begin{array}{cc}1& \text{if }i=j\text{ and }\mathrm{deg}(v_i)\ne 0\\ -\frac{1}{\mathrm{deg}(v_i)}& \text{if }i\ne j\text{ and }{v}_i\text{ is adjacent to }{v}_j\\ 0& \text{otherwise}.\end{array}$

动力学和微分方程

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

$\begin{array}{cc}\frac{d{\varphi }_i}{dt}& =-k\sum _j{A}_{ij}({\varphi }_i-{\varphi }_j)\\ & =-k({\varphi }_i\sum _j{A}_{ij}-\sum _j{A}_{ij}{\varphi }_j)\\ & =-k({\varphi }_i\mathrm{deg}(v_i)-\sum _j{A}_{ij}{\varphi }_j)\\ & =-k\sum _j({\delta }_{ij}\mathrm{deg}(v_i)-A_{ij}){\varphi }_j\\ & =-k\sum _j\left({\ell }_{ij}\right){\varphi }_j.\end{array}$

使用矩阵矢量

$\begin{array}{cc}\frac{d\varphi }{dt}& =-k(D-A)\varphi \\ & =-kL\varphi \end{array}$

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

解是

$\begin{array}{cc}\frac{d\left(\sum _i{c}_i{𝐯}_i\right)}{dt}+kL\left(\sum _i{c}_i{𝐯}_i\right)& =0\\ \sum _i[\frac{d{c}_i}{dt}{𝐯}_i+k{c}_{i}L{𝐯}_i]& =\\ \sum _i[\frac{d{c}_i}{dt}{𝐯}_i+k{c}_i{\lambda }_i{𝐯}_i]& =\\ \frac{d{c}_i}{dt}+k{\lambda }_i{c}_i& =0\\ \end{array}$

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

$c_i(0)=⟨\varphi (0),{𝐯}_i⟩$

平衡举动

当$\underset{t\to \mathrm{\infty }}{\lim }\varphi (t)$的时候，

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

$\underset{t\to \mathrm{\infty }}{\lim }\varphi (t)=⟨c(0),{𝐯}^{\mathrm{𝟏}}⟩{𝐯}^{\mathrm{𝟏}}$

${𝐯}^{\mathrm{𝟏}}=\frac{1}{\sqrt{N}}[1,1,...,1]$

$\underset{t\to \mathrm{\infty }}{\lim }{\varphi }_j(t)=\frac{1}{N}\sum _{i=1}^N{c}_i(0)$

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

GIF：离散拉普拉斯过程，使用拉普拉斯矩阵

应用

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

阅读

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