图/超图拉普拉斯分解 Graph/Hypergraph Laplacian eigendecomposition

这篇具有很好参考价值的文章主要介绍了图/超图拉普拉斯分解 Graph/Hypergraph Laplacian eigendecomposition。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

大家好,还是之前的风格,简单粗暴,直接开干!

一、图拉普拉斯特征分解

1. 数学公式

直接上公式,下边公式是图的归一化 拉普拉斯特征分解公式:
Δ = I − D − 1 2 A D − 1 2 = U T Λ U \Delta = I-D^{-\frac{1}{2}}AD^{-\frac{1}{2}} = U^{T}\Lambda U Δ=ID21AD21=UTΛU

各参数的含义是,给定一个图G,假如它有n个节点和m个边:

  • Δ \Delta Δ :拉普拉斯特征矩阵,我们要先计算出这个矩阵,才方便进行特征分解, 矩阵shape是 n × n n\times n n×n

  • I I I:单位矩阵, 矩阵shape是 n × n n\times n n×n

  • D D D:节点度矩阵,矩阵shape是 n × n n\times n n×n

  • A A A :邻接矩阵,矩阵shape是 n × n n\times n n×n

  • U U U:特征向量, 矩阵shape是 n × n n\times n n×n,用代码获取的一般是按照对应特征值从小到大的顺序排列的,每一行对应每个节点的特征值,每一列对应一个特征值。对应特征值小的特征向量包含了更多图整体的结构信息,对应特征值大的特征向量包含了更多这个节点附近的局部信息。

  • Λ \Lambda Λ:特征值, 矩阵shape是 1 × n 1\times n 1×n,一般从函数获得后都是自动排好序的,从小到大

2. 参考代码

参考代码 Github

下边的代码是我加了一些个人注释的,便于理解:

import torch
import torch.utils.data
import numpy as np


def eig(sym_mat):
	# 特征分解函数
    # (sorted) eigenvectors with numpy
    EigVal, EigVec = np.linalg.eigh(sym_mat) # 特征分解函数,输入图邻接矩阵A,返回特征值和特征向量

    # for eigval, take abs because numpy sometimes computes the first eigenvalue approaching 0 from the negative
    eigvec = torch.from_numpy(EigVec).float()  # [N, N (channels)] # 转一下type,无伤大雅
    eigval = torch.from_numpy(np.sort(np.abs(np.real(EigVal)))).float()  # [N (channels),] #其实分解函数返回的时候就已经是排过序的了
    return eigvec, eigval  # [N, N (channels)]  [N (channels),]


def lap_eig(dense_adj, number_of_nodes, in_degree):
    """
    拉普拉斯特征矩阵函数
    Graph positional encoding v/ Laplacian eigenvectors
    https://github.com/DevinKreuzer/SAN/blob/main/data/molecules.py
    """
    dense_adj = dense_adj.detach().float().numpy() # 邻接矩阵
    
    # 节点入度,这里in_degree输入的是每个节点的入度,现在还是一个一维的向量
    # 大概长这样:[2, 1, 4, 2, ..., 3, 3],长度就是number_of_nodes,对于无向图来说也是出度矩阵
    in_degree = in_degree.detach().float().numpy() 

    # Laplacian
    A = dense_adj # 邻接矩阵
    N = np.diag(in_degree.clip(1) ** -0.5) # diag就是把 1xn 的向量转为 nxn 的矩阵
    L = np.eye(number_of_nodes) - N @ A @ N #这就是上文说的计算拉普拉斯特征矩阵的公式

    eigvec, eigval = eig(L) # 上边那个特征分解函数
    return eigvec, eigval  # [N, N (channels)]  [N (channels),]

二、超图拉普拉斯特征分解

1. 数学公式

下边公式是超图的归一化 拉普拉斯特征分解公式:

L = I − D v − 1 2 H W D e − 1 H T D v − 1 2 = U T Λ U L=I-D_{v}^{-\frac{1}{2}}HWD_{e}^{-1}H^{T}D_{v}^{-\frac{1}{2}}= U^{T}\Lambda U L=IDv21HWDe1HTDv21=UTΛU

各参数的含义是,给定一个超图G,假如它有n个节点和m个边:

  • L L L :拉超图普拉斯特征矩阵,我们要先计算出这个矩阵,才方便进行特征分解,矩阵shape是 n × n n \times n n×n

  • I I I:单位矩阵, 矩阵shape是 n × n n \times n n×n

  • D v D_{v} Dv:节点度矩阵,矩阵shape是 n × n n \times n n×n

  • D e D_{e} De:超边度矩阵,矩阵shape是 m × m m \times m m×m

  • H H H :关联矩阵,矩阵shape是 n × m n \times m n×m

  • W W W:包含超边权重的对角矩阵,如果没有明确给出超边权重矩阵,一般超边的权重矩阵就按超边的度矩阵算,矩阵shape是 m × m m \times m m×m

  • U U U:特征向量, 矩阵shape是 n × n n \times n n×n

  • Λ \Lambda Λ:特征值, 矩阵shape是 1 × n 1\times n 1×n

2. 参考代码

参考代码 Github

这是我自己写的参考代码,由于接收的数据不太理想,所以代码中可能含有除公式外一些额外的东西:文章来源地址https://www.toymoban.com/news/detail-686433.html

import numpy as np

def getEigvec(HT):
    H, Dv, De, W = getHypergraph(HT)
    eigval, eigvec = eig(H, Dv, De, W)

    return eigval, eigvec

def getHypergraph(HT):
    """
    This function aims to convert a graph to a hypergraph.
    
    graph: 
        HT: a hypergraph incidence matrix, shape is [num_hyperedges, num_hypernodes], contains 0 and 1.
    
    return Hypergraph:
        H: a hypergraph incidence matrix, shape is [num_hypernodes, num_hyperedges], contains 0 and 1.
        Dv: node degree matrix --> [num_nodes, num_nodes]
        De: hyperedge degree matrix --> [hyperedge_num, hyperedge_num]
        W: hyperedge weight matrix --> [hyperedge_num, hyperedge_num]
        
    """
    H = HT.T

    De = np.diag(np.sum(H, axis = 0)) # hyperedge degree matrix --> [num_hyperedges, num_hyperedge]
    Dv = np.diag(np.sum(H, axis = 1)) # nodes degree matrix  --> [num_nodes, num_nodes]
    W = De    # hyperedge weight matrix --> [hyperedge_num, hyperedge_num]
    
    return H, Dv, De, W

def eig(H, Dv, De, W):
    """
    This function aims to get hypergraph eigendecomposition.
    Reference: 
        https://github.com/DevinKreuzer/SAN/blob/main/data/molecules.py
        https://github.com/jw9730/tokengt/blob/main/large-scale-regression/tokengt/data/algos.py
    
    H: a hypergraph incidence matrix, shape is [num_hypernodes, num_hyperedges], contains 0 and 1.
    Dv: node degree matrix --> [num_nodes, num_nodes]
    De: hyperedge degree matrix --> [hyperedge_num, hyperedge_num]
    W: hyperedge weight matrix --> [hyperedge_num, hyperedge_num]
    
    return:
        EigVal: eigenvalue --> [num_nodes, 1]
        EigVec: eigenvector --> [num_nodes, num_nodes]
    """
    
    Dv_half = np.diag(Dv.sum(axis = 0).clip(1) ** -0.5)
    De_1 = np.diag(De.sum(axis = 1).clip(1) ** -1)
    num_nodes = len(Dv)
    
    delta = np.eye(num_nodes) - Dv_half @ H @  De_1 @ H.T @ Dv_half
    
    EigVal, EigVec = np.linalg.eigh(delta)
    # EigVal = np.sort(np.abs(np.real(EigVal)))
    idx = EigVal.argsort()
    EigVal, EigVec = EigVal[idx], np.real(EigVec[:, idx])


    return EigVal, EigVec

到了这里,关于图/超图拉普拉斯分解 Graph/Hypergraph Laplacian eigendecomposition的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【信号与系统】(二十一)拉普拉斯变换与复频域分析——拉普拉斯变换及其性质

    傅里叶变换: j w jw j w 拉普拉斯变换: s = σ + j w s=sigma+jw s = σ + j w 有些函数不满足绝对可积条件 ,求解傅里叶变换困难。为此,可用一衰减因子 e − σ t e^{-sigma t} e − σ t ( σ sigma σ 为实常数)乘信号 f ( t ) f(t) f ( t ) ,适当选取 σ sigma σ 的值,使乘积信号 f ( t ) e −

    2024年02月09日
    浏览(61)
  • 拉普拉斯算子

    在介绍拉普拉斯算子概念之前我们先介绍,哈密尔顿算子( ∇ nabla ∇ ),梯度,散度等概念 所谓哈密尔顿算子即为某一物理量在笛卡尔坐标系下的偏导数的矢量和,其运算符号为: ∇ nabla ∇ ,定义如下: ∇ = δ δ x i + δ δ y j + δ δ z k nabla={frac{delta}{delta x}}pmb{i}+{f

    2024年02月09日
    浏览(50)
  • 拉普拉斯变换

    1.公式:设f(t)在t≥0时有定义, 其中s=β+jw。 注:L(1)=   L(sgnt)=   L()= 2.性质         性质1:          性质2:          性质3:         性质4:L()= 推导性质2:使用欧拉公式进行推导 同理,cosat= ,使用分部积分法,经过两次分部积分后会出现原来的积分,通过合并

    2024年02月05日
    浏览(46)
  • 【电路分析】拉普拉斯变换及其应用

    零状态响应 是指电路的外加激励源为零的情况下,由动态元件的初始储能引起的响应。 零输入响应 是指电路的初始状态为零(即换路前电容电压为零,电感电流为零),由外加激励源产生的响应。 该函数在 t0时幅值为1,在 t0 时幅值为-0,在 t=0时函数没有定义但为有限值

    2024年02月03日
    浏览(46)
  • visual Studio MFC 平台实现拉普拉斯和拉普拉斯与直方图均衡化与中值滤波相结合实现比较

    本文使用visual Studio MFC 平台实现图像增强中的拉普拉斯变换,同时拉普拉斯一般不会单独使用,与其他平滑操作相结合,本文使用了拉普拉斯与直方图均衡化以及与中值滤波相结合,也对三种方式进行了对比 关于基础工程的创建可以参考 01-Visual Studio 使用MFC 单文档工程绘制

    2024年02月04日
    浏览(51)
  • 【线性代数】P3 拉普拉斯定理

    拉普拉斯定理是通过对余子式和代数余子式的变形展开得到,有关余子式和代数余子式的概念见:https://blog.csdn.net/weixin_43098506/article/details/126765390 假设有四阶行列式: k阶子式 行列式D的一个二阶子式为: 余子式 那么二阶子式A的余子式为: 代数余子式 那么二阶子式的代数余

    2024年02月12日
    浏览(46)
  • 图谱论学习—拉普拉斯矩阵背后的含义

    一、为什么学习拉普拉斯矩阵     早期,很多图神经网络的概念是基于图信号分析或图扩散的,而这些都需要与图谱论相关的知识。并且在图网络深度学习中(graph deep learning)中,拉普拉斯矩阵是很常用的概念,深入理解其物理含义非常有助于加深对GNN模型的理解。博主最

    2023年04月09日
    浏览(46)
  • 基于拉普拉斯金字塔的图像融合

    仅为笔记,供自己使用。 读入两幅大小相同的图像 img1 img2; 构建 img1 img2的 高斯金字塔,层数根据需要设定(本实验为7层); 根据高斯金字塔和拉普拉斯金字塔的关系,推出拉普拉斯金字塔的Li(也为7层,第一层大小和原图相同); 在 两组拉普拉斯图层 的每一层进行图像

    2024年02月11日
    浏览(47)
  • 学习笔记:Opencv实现拉普拉斯图像锐化算法

    2023.8.19 为了在暑假内实现深度学习的进阶学习,Copy大神的代码,记录学习日常 图像锐化的百科: 图像锐化算法-sharpen_lemonHe_的博客-CSDN博客 在环境配置中要配置opencv: pip install opencv-contrib-python Code and lena.png:注意你是否在data下由lena.png   附上lena.png  效果所示(解读):

    2024年02月12日
    浏览(49)
  • 图像处理之LoG算子(高斯拉普拉斯)

    LoG算子是由拉普拉斯算子改进而来。拉普拉斯算子是二阶导数算子,是一个标量,具有线性、位移不变性,其传函在频域空间的原点为0。所有经过拉普拉斯算子滤波的图像具有零平均灰度。但是该算子的缺点是对噪声具有敏感性,因此在实际应用中,一般先要对图像进行平滑

    2024年02月16日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包