图卷积神经网络之 - 图拉普拉斯矩阵的解释

图拉普拉斯矩阵是图论和谱图理论中的一个核心概念，它在图卷积神经网络（GCN）的设计中起着重要的作用。下面我将详细解释图拉普拉斯矩阵和归一化图拉普拉斯矩阵。

图拉普拉斯矩阵 $L$

图拉普拉斯矩阵是由节点的度矩阵 $D$ 和邻接矩阵 $W$ 组成的。这里的度指的是每个节点的连接数（在无向图中是连接边的数量，在加权图中是连接边的权重和）。

• 度矩阵 $D$: 这是一个对角矩阵，其对角线上的元素 $D_{ii}$ 是节点 $i$ 的度。
• 权重邻接矩阵 $W$: 这个矩阵的元素 $W_{ij}$ 表示节点 $i$ 和 $j$ 之间边的权重。如果 $i$ 和 $j$ 之间没有边相连，则 $W_{ij}=0$。

图拉普拉斯矩阵 $L$ 定义为 $L=D?W$。在这个定义中，拉普拉斯矩阵的每个非对角线元素 $L_{ij}$（即 $i\ne j$）都是 $?W_{ij}$，表示节点 $i$ 和 $j$ 的连接性（如果它们直接相连）。对角线元素 $L_{ii}$ 是 $D_{ii}$，表示节点 $i$ 的度减去所有到 $i$ 的边的权重和。

归一化图拉普拉斯矩阵 $\tilde{L}$

归一化图拉普拉斯矩阵是对原始拉普拉斯矩阵的一种变换，旨在改善其数值性质，例如特征值的范围。这有助于在学习算法中使用拉普拉斯矩阵时保持数值稳定性。

• 归一化图拉普拉斯矩阵 $\tilde{L}$ 定义为 $\tilde{L}=I?D^{?\frac{1}{2}}W{D}^{?\frac{1}{2}}$。在这个表达式中：
  • $D^{?\frac{1}{2}}$ 是度矩阵 $D$ 的每个元素取平方根的倒数（只在对角线上有非零元素）。
  • $I$ 是单位矩阵，大小与 $D$ 和 $W$ 相同。

归一化操作的直觉是，我们希望在计算节点的特征表示时，每个节点的贡献是平衡的，不会因为节点的度过大或过小而有不公平的影响。通过左乘和右乘 $D^{?\frac{1}{2}}$，我们相当于对每个节点的贡献进行了规范化，确保了特征传播在图中更为平滑和均衡。

简而言之，图拉普拉斯矩阵捕捉了图的拓扑结构，并在谱图理论中用于定义图上的傅立叶变换，这对于在图数据上进行机器学习是至关重要的。通过归一化，拉普拉斯矩阵的谱（即其特征值）通常会被限制在[0,2]的范围内，这对于使用梯度下降等优化算法时是有好处的。

代码实现

import numpy as np

# 定义图的邻接矩阵
W = np.array([
    [0, 1, 0, 1],
    [1, 0, 1, 0],
    [0, 1, 0, 1],
    [1, 0, 1, 0]
])

# 定义度矩阵D
D = np.diag(W.sum(axis=1))

# 计算未归一化的图拉普拉斯矩阵L
L = D - W

# 计算归一化的图拉普拉斯矩阵L_norm
D_inv_sqrt = np.diag(1 / np.sqrt(W.sum(axis=1)))
L_norm = np.eye(4) - D_inv_sqrt @ W @ D_inv_sqrt

L, L_norm

output:

(array([[ 2, -1,  0, -1],
        [-1,  2, -1,  0],
        [ 0, -1,  2, -1],
        [-1,  0, -1,  2]]),
 array([[ 1. , -0.5,  0. , -0.5],
        [-0.5,  1. , -0.5,  0. ],
        [ 0. , -0.5,  1. , -0.5],
        [-0.5,  0. , -0.5,  1. ]]))