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

发布时间:2023年12月29日

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

图拉普拉斯矩阵 L L L

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

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

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

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

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

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

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

简而言之,图拉普拉斯矩阵捕捉了图的拓扑结构,并在谱图理论中用于定义图上的傅立叶变换,这对于在图数据上进行机器学习是至关重要的。通过归一化,拉普拉斯矩阵的谱(即其特征值)通常会被限制在[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. ]]))
文章来源:https://blog.csdn.net/weixin_46160781/article/details/135285580
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。