首页 计算机 机器学习 GNN

整理关于拉普拉斯矩阵的数学性质。

# 邻接矩阵、度矩阵

邻接矩阵 (adjacency matrix) 是图的一种存储方式，用来表示两顶点之间是否存在边。若有向图中存在 kk 条 AiA_i 到 AjA_j 的边，那么邻接矩阵 AA 中的元素 aij=ka_{ij} = k. 对无向图，若存在 kk 条 AiA_i 到 AjA_j 的边，则 aij=aji=ka_{ij} = a_{ji} = k. 因此，对于无向简单图，其邻接矩阵是由 0,10,1 组成的，对角线元素全为 00 的矩阵。

度矩阵 (degree matrix) 用来描述一个图中各顶点的度。若顶点 AiA_i 度为 did_i, 则度矩阵 D=diag{d1,d2,…,dn}D = \mathrm{diag}\{d_1, d_2, \dots, d_n\}. 对于有向图，出度矩阵和入度矩阵不相同。

# 拉普拉斯矩阵

拉普拉斯矩阵 (Laplacian matrix) 又叫图拉普拉斯矩阵。常见的拉普拉斯矩阵定义有如下三种：

  1. 组合上的拉普拉斯矩阵 (Combinatorial Laplacian): L≔D−AL \coloneqq D-A. 如果只说拉普拉斯矩阵，那一般默认为这种形式。
  2. 对称归一化的拉普拉斯矩阵 (Symmetric normalized Laplacian): Lsym≔D−1/2LD−1/2L_{\mathrm{sym}} \coloneqq D^{-1/2} L D^{-1/2}. 这种拉普拉斯矩阵在 GCN 等图神经网络中常常用来进行理论分析。
  3. 随机游走归一化的拉普拉斯矩阵 (Random walk normalized Laplacian): Lrw≔D−1LL_{\mathrm{rw}} \coloneqq D^{-1} L.

# 性质

下面就来说一说组合上的拉普拉斯矩阵 L=D−AL = D-A 的性质。

首先罗列一些显然的拉普拉斯矩阵 LL 的性质及推论：

  1. L∈Zn×nL \in \mathbb{Z}^{n \times n};
  2. LL 是实对称矩阵；
    1. LL 有 nn 个实特征值。
  3. LL 是弱对角占优矩阵，由于 ∣aii∣=∑j≠i∣aij∣,∀i=1,2,…,n|a_{ii}| = \sum_{j \neq i} |a_{ij}|, \forall i = 1,2,\dots, n.
    1. LL 是半正定的 (Levy-Desplanques Theorem).

除此之外，如何对拉普拉斯矩阵的性质进行普遍地研究？基于组合性质，仍然需要从所有图的特征入手。因此，研究拉普拉斯矩阵性质的一个重要想法是按边进行拆分。下面来看一些例子。

# 拉普拉斯矩阵的特征值

00 是拉普拉斯矩阵的最小特征值，其代数重数为图的连通块数目。

# 归一化拉普拉斯矩阵

# 性质

拉普拉斯矩阵是实对称矩阵，因此可以相似对角化。可以证明，归一化的拉普拉斯矩阵

Lsym≔D−1/2LD−1/2L_{\mathrm{sym}} \coloneqq D^{-1/2} L D^{-1/2}

的特征值属于区间 [0,2][0,2].

证明

首先证明，拉普拉斯矩阵的特征值非负：

首先定义

Gs,t−=(gi,j)n×n≔{1,i=j=sori=j=t−1,i=s,j=tori=t,j=s0,other casesG_{s,t}^- = (g_{i,j})_{n \times n }\coloneqq \left\{ \begin{aligned} & 1, && i=j=s \;\text{or} \; i=j=t \\ & -1, && i=s,\; j=t \; \text{or} \; i=t, j=s \\ & 0, && \text{other cases} \end{aligned} \right.

那么，∀X∈Rn\forall X \in \mathbb{R}^n, 有 X⊤Gs,t−X=(xi−xj)2≥0X^\top G_{s,t}^- X = (x_i-x_j)^2 \geq 0. 因此 Gs,t−G_{s,t}^- 正定。

而对于图 G(V,E)G(V,E). 其拉普拉斯矩阵可以表示为

L=∑eij∈EGi,j−L = \sum_{e_{ij} \in E}G_{i,j}^-

因此，∀X∈Rn\forall X \in \mathbb{R}^n,

X⊤LX=X⊤(∑eij∈EGi,j−)X=∑eij∈EX⊤Gi,j−X=∑eij∈E(xi−xj)2≥0X^\top L X = X^\top \left(\sum_{e_{ij} \in E}G_{i,j}^- \right) X = \sum_{e_{ij} \in E} X^\top G_{i,j}^- X = \sum_{e_{ij} \in E} (x_i-x_j)^2 \geq 0

# Cheeger's Inequality

# Graph Conductance

# Ref

  • Wikipedia - Laplacian matrix
  • Wikipedia - Spectral graph theory
  • COMP 766 - Graph Representation Learning
  • Cheeger's Inequaality & Graph Conductance
    • Eigenvalues of the Laplacian and Their Relationship to the Connectedness of a Graph
    • berserker60 - 谱图理论 ——Cheeger's inequality
  • Petrron-Frobenius Theorem
    • Wikipedia - Perron–Frobenius theorem
    • 纯粹 - 非负矩阵之 Perron-Frobenius 定理