超图嵌入论文阅读2:超图神经网络

2023-11-21 15:50

本文主要是介绍超图嵌入论文阅读2:超图神经网络,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

超图嵌入论文阅读2:超图神经网络

原文:Hypergraph Neural Networks ——AAAI2019(CCF-A)

源码:https://github.com/iMoonLab/HGNN 500+star

概述

贡献:用于数据表示学习的超图神经网络 (HGNN) 框架,对超图结构中的高阶数据相关性进行编码

  • 定义超边卷积来处理表示学习过程中的数据相关性

  • 够学习考虑高阶数据结构的隐藏层表示,是一个通用框架

    ——GCN可以看作是 HGNN 的一个特例,其中简单图中的边可以被视为仅连接两个顶点的 2 阶超边

  • 引文图、图像识别数据集上实验,优于图卷积网络(GCN)

  • others:在处理多模态数据时具有优势

背景

图卷积能够使用神经网络模型对不同输入数据的图结构进行编码,用于无监督、半监督、监督学习,在表示学习方面显示出优越性。传统图卷积网络,使用成对连接,难以表征多模态数据:

  1. 数据相关性可能比成对关系更复杂,很难用图结构建模
  2. 数据表示往往是多模态

——传统的图结构具有规定数据相关性的局限性,这限制了图卷积网络的应用。

超图

超图优势

  • 超图可以使用其可变度数超边高阶数据相关性(超出成对连接)进行编码

  • 使用超图的灵活性超边很容易扩展到多模态和异构数据表示:

    如:可以通过组合邻接矩阵来联合使用多模态数据来生成超图

——图已被用于许多计算机视觉任务,例如分类和检索任务

超图问题:传统的超图学习方法计算复杂度和存储成本较高,难以广泛应用

相关研究

  1. 超图学习

    前期发展

    • 2007首次引入,转导推理旨在最小化超图上连接更强的顶点之间的标签差异
    • 2009进一步用于视频对象分割
    • 2010对图像关系进行建模,并进行转导推理过程进行图像排序

    注意力机制引入:

    • 2013对权重进行正则化
    • 2008提出假设:高度相关的超边应该具有相似的权重

    多模态

    • 2012引入多超图结构为不同的子超图分配权重
  2. 图神经网络

    前期发展

    • 2005 2009应用循环神经网络来处理图

    谱方法

    • 2014第一个图 CNN:图拉普拉斯特征基
    • 2015谱滤波器可以使用平滑系数参数化
    • 2016图拉普拉斯算子的切比雪夫扩展进一步用于近似谱滤波器
    • 2017chebyshev 多项式被简化为 1 阶多项式,形成一个有效的逐层传播模型

    空间方法

    • 2016使用转移矩阵的幂来定义节点的邻域
    • 2017使用高斯混合模型形式的局部路径算子来概括空间域中的卷积
    • 2018注意力机制被引入图以构建基于注意力的架构,以在图上执行节点分类任务

HGNN

超图学习

基础知识(略):

与简单图不同,超图中的超边连接两个或多个顶点。超图定义为 G = (V, E, W)

超图 G 可以用 |V| × |E|关联矩阵 H 表示
h ( v , e ) = { 1 , if  v ∈ e 0 , if  v ∉ e , h(v,e)=\left\{\begin{array}{l} 1, \text{if} \space v \in e \\ 0, \text{if} \space v \notin e, \\\end{array}\right. h(v,e)={1,if ve0,if v/e,
d ( v ) = ∑ e ∈ E ω ( e ) h ( v , e ) d(v) =∑_{e∈E} ω(e)h(v, e) d(v)=eEω(e)h(v,e) δ ( e ) = ∑ v ∈ V h ( v , e ) δ(e) = ∑_{v∈V} h(v, e) δ(e)=vVh(v,e) D e \mathbf{D}_e De D v \mathbf{D}_v Dv 分别表示边度和顶点度的对角矩阵

超图节点分类问题:节点标签应该在超图结构上平滑

——用以下正则化框架描述:
arg ⁡ min ⁡ f { R e m p ( f ) + Ω ( f ) } \arg \min_f \{\mathcal{R}_{emp}(f)+\Omega(f)\} argfmin{Remp(f)+Ω(f)}
其中 Ω ( f ) \Omega(f) Ω(f) 是超图上的正则化, R e m p ( f ) \mathcal{R}_{emp}(f) Remp(f) 表示监督经验损失, f ( ⋅ ) f (·) f() 是分类函数。正则化 Ω ( f ) \Omega(f) Ω(f)定义为:
Ω ( f ) = 1 2 ∑ e ∈ ε ∑ { u , v } ∈ V w ( e ) h ( u , e ) h ( v , e ) δ ( e ) ( f ( u ) d ( u ) − f ( v ) d ( v ) ) 2 \Omega(f)=\frac{1}{2} \sum_{e \in \varepsilon} \sum_{\{u,v\}\in \mathcal{V}} \frac{w(e)h(u,e)h(v,e)}{\delta(e)} \left(\frac{f(u)}{\sqrt{d(u)}}-\frac{f(v)}{\sqrt{d(v)}}\right)^2 Ω(f)=21eε{u,v}Vδ(e)w(e)h(u,e)h(v,e)(d(u) f(u)d(v) f(v))2
我们令 Θ = D v − 1 / 2 H W D e − 1 H T D v − 1 / 2 \mathbf \Theta=\mathbf D_v^{-1/2}\mathbf H \mathbf W \mathbf D_e^{-1}\mathbf H^{\mathsf T}\mathbf D_v^{-1/2} Θ=Dv1/2HWDe1HTDv1/2 Δ = I − Θ \mathbf \Delta = \mathbf I -\mathbf \Theta Δ=IΘ 归一化 Ω ( f ) \Omega(f) Ω(f) 可以写成:
Ω ( f ) = f T Δ \Omega(f)=f^{\text T} \mathbf \Delta Ω(f)=fTΔ
其中 Δ \mathbf \Delta Δ 是半正定的,通常称为超图拉普拉斯算子。

超图谱卷积

给定一个具有 n 个顶点的超图,拉普拉斯算子 Δ \mathbf \Delta Δ 是半正定的。对其进行特征分解 Δ = Φ Λ Φ T \mathbf \Delta =\mathbf \Phi \mathbf \Lambda \mathbf \Phi^{\mathsf T} Δ=ΦΛΦT 可得到正交特征向量 Φ = diag ( ϕ 1 , . . . , ϕ n ) \mathbf \Phi = \text{diag}(\phi_1,..., \phi_n) Φ=diag(ϕ1,...,ϕn) 和对角矩阵 Λ = diag ( λ 1 , . . . , λ n ) \mathbf \Lambda =\text{diag}(\lambda_1,..., \lambda_n) Λ=diag(λ1,...,λn) 对应非负特征值。

信号 x = ( x 1 , . . . , x n ) \text x = (x_1,..., x_n) x=(x1,...,xn) 在超图中定义为 x ^ = Φ T x \hat {\text x}=\mathbf \Phi^{\mathsf T}\text x x^=ΦTx ,其中特征向量被视为傅里叶基,特征值被解释为频率。信号x滤波器g的谱卷积可以表示为:
g ⋆ x = Φ ( ( Φ T g ) ⊙ ( Φ T x ) ) = Φ g ( Λ ) Φ T x , \text g\star \text x=\mathbf \Phi((\mathbf \Phi^{\mathsf T}\text g)\odot (\mathbf \Phi^{\mathsf T} \text x))=\mathbf \Phi g(\mathbf \Lambda) \mathbf \Phi^{\mathsf T}\text x, gx=Φ((ΦTg)(ΦTx))=Φg(Λ)ΦTx,

  • ⊙ \odot 表示逐元素的Hadamard乘积
  • g ( Λ ) = diag ( g ( λ 1 ) , . . . , g ( λ n ) ) g(\mathbf \Lambda)=\text{diag}(\text g(\lambda_1),...,\text g(\lambda_n)) g(Λ)=diag(g(λ1),...,g(λn)) 是傅立叶系数的函数

然而正向和反向傅里叶变换的计算成本为 O ( n 2 ) O(n^2) O(n2)。可以用某论文中的方法使用K 阶多项式参数化 g ( Λ ) g(\mathbf \Lambda) g(Λ),我们使用截断切比雪夫展开作为这样的多项式。Chebyshv多项式 T k ( x ) T_k(x) Tk(x) T k ( x ) = 2 x T k − 1 ( x ) − T k − 2 ( x ) T_k(x) = 2xT_{k−1}(x)−T_{k−2}(x) Tk(x)=2xTk1(x)Tk2(x)递归计算,其中 T 0 ( x ) = 1 T_0(x) = 1 T0(x)=1 T 1 ( x ) = x T_1(x) = x T1(x)=x。因此, g ( Λ ) g(\mathbf \Lambda) g(Λ)可以参数化为:
g ⋆ x ≈ ∑ k = 0 K θ k T k ( Δ ^ ) x , \text g\star \text x \approx \sum_{k=0}^K \theta_k T_k(\hat {\mathbf \Delta})\text{x}, gxk=0KθkTk(Δ^)x,
其中 T k ( Δ ^ ) T_k(\hat {\mathbf \Delta}) Tk(Δ^) 是k阶切比雪夫多项式,里面的缩放拉普拉斯算子为 Δ ^ = 2 λ m a x Δ − I \hat{\mathbf \Delta}=\frac{2}{\lambda_{max}}\mathbf \Delta-\mathbf I Δ^=λmax2ΔI。排除了拉普拉斯特征向量的扩展计算,只包括矩阵幂、加法和乘法,提升运算速度。我们可以进一步让 K = 1 来限制卷积操作的顺序,因为超图中的拉普拉斯算子已经可以很好地表示节点之间的高阶相关性。另一篇论文检建议,由于神经网络的规模适应性,令 λ m a x ≈ 2 \lambda_{max} \approx 2 λmax2,卷积运算可以进一步简化为:
g ⋆ x ≈ θ 0 x − θ 1 D v − 1 / 2 H W D e − 1 H T D v − 1 / 2 x , \text g\star \text x \approx \theta_0 \text x-\theta_1 \mathbf D_v^{-1/2}\mathbf H \mathbf W \mathbf D_e^{-1} \mathbf H^{\mathsf T} \mathbf D_v^{-1/2} \text x, gxθ0xθ1Dv1/2HWDe1HTDv1/2x,
其中 θ 0 θ_0 θ0 θ 1 θ_1 θ1 是所有节点的过滤器参数。我们进一步使用单个参数 θ 来避免过拟合问题,定义为:
{ θ 1 = − 1 2 θ θ 0 = 1 2 θ D v − 1 / 2 H W D e − 1 H T D v − 1 / 2 , \left\{\begin{array}{l} \theta_1 = -\frac{1}{2}\theta \\ \theta_0 = \frac{1}{2}\theta \mathbf D_v^{-1/2}\mathbf H \mathbf W \mathbf D_e^{-1} \mathbf H^{\mathsf T} \mathbf D_v^{-1/2}, \\\end{array}\right. {θ1=21θθ0=21θDv1/2HWDe1HTDv1/2,
卷积运算可以简化为下式:
g ⋆ x ≈ 1 2 θ D v − 1 / 2 H ( W + I ) D e − 1 H T D v − 1 / 2 x ≈ θ D v − 1 / 2 H W D e − 1 H T D v − 1 / 2 x \text g\star \text x \approx \frac{1}{2}\theta \mathbf D_v^{-1/2}\mathbf H \mathbf {(W+I)} \mathbf D_e^{-1} \mathbf H^{\mathsf T} \mathbf D_v^{-1/2} \text x\\\approx \theta \mathbf D_v^{-1/2}\mathbf H \mathbf W \mathbf D_e^{-1} \mathbf H^{\mathsf T} \mathbf D_v^{-1/2} \text x gx21θDv1/2H(W+I)De1HTDv1/2xθDv1/2HWDe1HTDv1/2x
其中 ( W + I ) \mathbf{(W + I)} (W+I) 可以看作是超边的权重。 W \mathbf W W 被初始化为单位矩阵,这意味着所有超边的相等权重。

当我们有一个具有n个节点和C1维特征的超图信号 X ∈ R n × C 1 \mathbf X \in \mathbb R^{n \times C_1} XRn×C1 时,我们的超边卷积可以表示为:
Y = D v − 1 / 2 H W D e − 1 H T D v − 1 / 2 X Θ , \mathbf{Y=D_v^{-1/2}HWD_e^{-1}H^{\mathsf T}D_v^{-1/2}X\Theta}, Y=Dv1/2HWDe1HTDv1/2,
其中 W = diag ( w 1 , . . . , w n ) \mathbf W =\text{diag}(\text{w}_1,...,\text{w}_n) W=diag(w1,...,wn) Θ ∈ R C 1 × C 2 \Theta \in \mathbb R^{C_1 \times C_2} ΘRC1×C2 是训练过程中要学习的参数。过滤器 Θ \mathbf \Theta Θ 应用于超图中的节点以提取特征。卷积后,我们可以得到 Y ∈ R n × C 2 \mathbf Y \in \mathbb R^{n \times C_2} YRn×C2 ,可用于分类。

超图神经网络分析

网络结构

多模态数据集分为训练数据和测试数据,每个数据包含多个具有特征的节点。然后从多模态数据集的复杂相关性构建多个超边结构组。我们组合超边组以生成超图邻接矩阵 H \mathbf H H。将超图邻接矩阵 H \mathbf H H和节点特征输入到HGNN中,得到节点输出标签。

我们可以在以下公式中构建一个超边卷积层 f ( X , W , Θ ) f \mathbf{(X, W, \Theta)} f(X,W,Θ)
X ( l + 1 ) = σ ( D v − 1 / 2 H W D e − 1 H T D v − 1 / 2 X ( l ) Θ ( l ) ) , \mathbf X^{(l+1)}=\sigma (\mathbf D_v^{-1/2}\mathbf H \mathbf W \mathbf D_e^{-1} \mathbf H^{\mathsf T} \mathbf D_v^{-1/2} \mathbf X^{(l)} \mathbf \Theta^{(l)}), X(l+1)=σ(Dv1/2HWDe1HTDv1/2X(l)Θ(l)),
其中 X ( l ) ∈ R N × C \mathbf X^{(l)} \in \mathbb R^{N \times C} X(l)RN×C l l l 层的超图信号, X ( 0 ) = X \mathbf X^{(0)} = \mathbf X X(0)=X σ \sigma σ 表示非线性激活函数。

卷积层结构

HGNN模型基于超图上的谱卷积。HGNN 层可以执行 节点-边-节点 的变换,这可以有效地提取超图上的高阶相关性。

卷积层结构

  1. 初始节点特征 X ( 1 ) \mathbf X^{(1)} X(1) 由可学习的滤波器矩阵 Θ ( 1 ) \mathbf \Theta^{(1)} Θ(1) 处理以提取 C 2 C_2 C2- 维特征
  2. 据超边收集节点特征以形成超边特征 R E × C 2 \mathbb R^{E \times C_2} RE×C2 ,这是通过乘以矩阵 H T ∈ R E × N \mathbf {H^{\mathsf T}} \in \mathbb R^{\mathbf {E \times N}} HTRE×N 来实现的
  3. 通过聚合其相关的超边特征来获得输出节点特征,该特征是通过乘以矩阵 H \mathbf H H 来实现的

—— D v \mathbf D_v Dv D e \mathbf D_e De在公式11中起到了归一化的作用

与现有方法的关系

超边只连接两个顶点时,超图被简化为一个简单的图,拉普拉斯算子 Δ \mathbf \Delta Δ 也与简单图的拉普拉斯算子一致(1/2倍相乘)

  • HGNN可以自然地对数据之间的高阶关系进行建模,有效地利用和编码形成特征提取
  • 与传统的超图方法相比,我们的模型在计算上非常高效,没有拉普拉斯算子 Δ \mathbf \Delta Δ 的逆运算
  • 在超边生成的灵活性下对多模态特征具有很大的可扩展性

实施

  1. 超图构造:图片分类任务中,提取每个对象的特征,根据欧氏距离构建超图。每个顶点代表一个视觉对象,每个超边通过连接一个顶点及其 K 个最近邻居来形成,这带来了 N 个链接 K + 1 个顶点的超边。引文图也类似地构造。
  2. 节点分类模型:数据集分为训练数据和测试数据,构建超图。按上图搭建网络,构建了一个两层HGNN模型,使用softmax 函数生成预测标签。使用交叉熵损失函数,将各种超边融合在一起,对数据的复杂关系进行建模。

实验

两个任务:引文网络分类和视觉对象识别,与图卷积网络和其他最先进的方法进行比较。

引文网络分类

Cora 和 Pubmed两个数据集

  • 每个数据的特征是文档的词袋表示
  • 每次选择图中的每个顶点作为质心,其连通顶点用于生成一条超边,包括质心本身
  • 获得与原始图规模相同的关联矩阵
  • Cora2708 个5%标记,Pubmed19717 个0.3%标记

参数设置:两层 HGNN

  • 隐藏层的特征维度设置为 16
  • dropout 丢弃率 p = 0.5
  • ReLU 作为非线性激活函数
  • Adam 优化器最小化交叉熵损失函数
  • 学习率为 0.001

结果讨论:Core和Pumbed上100次运行的平均分类精度

  • 与最先进的方法相比,HGNN模型可以达到最佳或相当的性能

    ——与 GCN 相比,HGNN 方法在 Cora 数据集上略有改进,在 Pubmed 数据集上提高了 1.1%

  • HGNN 获得的增益并不是很显著——因为构建的超图和传统图差不多

视觉对象分类

数据集

  • 普林斯顿ModelNet40
  • 国立台湾大学(NTU) 3D模型数据集

超图构建

  • 特征使用多视图卷积神经网络 (MVCNN) 和组视图卷积神经网络 (GVCNN)提取

  • 根据节点的距离构造一个概率图,生成亲和矩阵A来表示不同顶点之间的关系

    A i j = exp ⁡ ( − 2 D i j 2 Δ ) A_{ij}=\exp(-\frac{2D_{ij}^2}{\Delta}) Aij=exp(Δ2Dij2)

    其中Dij表示节点i和节点j之间的欧氏距离。Δ 是节点之间的平均成对距离

  • 两种超图构建方法:

    1. 基于单模态特征:每次选择一个数据集中的一个对象作为质心,选取特征空间中的10个最近邻生成一个超边,包括质心本身
    2. 基于多模态特征:使用多个特征来生成建模复杂多模态相关性的超图 G,只需要将超图关联矩阵拼接即可

结果讨论

  • HGNN方法在ModelNet40数据集中优于最先进的目标识别方法:分别获得 4.8% 和 3.2% 的增益
  • 与 GCN 相比,所提出的方法在所有实验中都取得了更好的性能:一个特征取得轻微改进,多个特征改进明显

优势分析

  1. 超图结构能够传达数据之间的复杂关系和高阶相关性,与图结构或没有图结构的方法相比,可以更好地表示底层的数据关系。
  2. 多模态数据/特征可用时,HGNN 的优势在于通过其灵活的超边将这种多模态信息组合在同一结构中。
  3. 与传统的超图学习方法可能存在计算复杂度高、存储成本高的问题相比,所提出的HGNN框架通过超边卷积运算效率更高

结论

超图神经网络 (HGNN) 的框架

  • 卷积运算推广到超图学习过程:谱域的卷积用超图拉普拉斯算子进行,进一步用截断的切比雪夫多项式逼近
  • 是一个更通用的框架:与传统图相比,能够通过超图结构处理复杂和高阶相关性以进行表示学习
  • 对引文网络分类和视觉对象识别任务进行了实验:HGNN 模型有更好的性能

——HGNN能够将复杂的数据相关性纳入表示学习,从而在视觉识别、检索和数据分类等许多任务中带来潜在的广泛应用。

这篇关于超图嵌入论文阅读2:超图神经网络的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/403356

相关文章

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来,一站式有声阅读平台听书系统 🌟 开篇:遇见未来,从“智听”开始 在这个快节奏的时代,你是否渴望在忙碌的间隙,找到一片属于自己的宁静角落?是否梦想着能随时随地,沉浸在知识的海洋,或是故事的奇幻世界里?今天,就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统,它正悄悄改变着我们的阅读方式,让未来触手可及! 📚 第一站:海量资源,应有尽有 走进“智听

图神经网络模型介绍(1)

我们将图神经网络分为基于谱域的模型和基于空域的模型,并按照发展顺序详解每个类别中的重要模型。 1.1基于谱域的图神经网络         谱域上的图卷积在图学习迈向深度学习的发展历程中起到了关键的作用。本节主要介绍三个具有代表性的谱域图神经网络:谱图卷积网络、切比雪夫网络和图卷积网络。 (1)谱图卷积网络 卷积定理:函数卷积的傅里叶变换是函数傅里叶变换的乘积,即F{f*g}

AI hospital 论文Idea

一、Benchmarking Large Language Models on Communicative Medical Coaching: A Dataset and a Novel System论文地址含代码 大多数现有模型和工具主要迎合以患者为中心的服务。这项工作深入探讨了LLMs在提高医疗专业人员的沟通能力。目标是构建一个模拟实践环境,人类医生(即医学学习者)可以在其中与患者代理进行医学

【生成模型系列(初级)】嵌入(Embedding)方程——自然语言处理的数学灵魂【通俗理解】

【通俗理解】嵌入(Embedding)方程——自然语言处理的数学灵魂 关键词提炼 #嵌入方程 #自然语言处理 #词向量 #机器学习 #神经网络 #向量空间模型 #Siri #Google翻译 #AlexNet 第一节:嵌入方程的类比与核心概念【尽可能通俗】 嵌入方程可以被看作是自然语言处理中的“翻译机”,它将文本中的单词或短语转换成计算机能够理解的数学形式,即向量。 正如翻译机将一种语言

论文翻译:arxiv-2024 Benchmark Data Contamination of Large Language Models: A Survey

Benchmark Data Contamination of Large Language Models: A Survey https://arxiv.org/abs/2406.04244 大规模语言模型的基准数据污染:一项综述 文章目录 大规模语言模型的基准数据污染:一项综述摘要1 引言 摘要 大规模语言模型(LLMs),如GPT-4、Claude-3和Gemini的快

论文阅读笔记: Segment Anything

文章目录 Segment Anything摘要引言任务模型数据引擎数据集负责任的人工智能 Segment Anything Model图像编码器提示编码器mask解码器解决歧义损失和训练 Segment Anything 论文地址: https://arxiv.org/abs/2304.02643 代码地址:https://github.com/facebookresear

论文翻译:ICLR-2024 PROVING TEST SET CONTAMINATION IN BLACK BOX LANGUAGE MODELS

PROVING TEST SET CONTAMINATION IN BLACK BOX LANGUAGE MODELS https://openreview.net/forum?id=KS8mIvetg2 验证测试集污染在黑盒语言模型中 文章目录 验证测试集污染在黑盒语言模型中摘要1 引言 摘要 大型语言模型是在大量互联网数据上训练的,这引发了人们的担忧和猜测,即它们可能已

OmniGlue论文详解(特征匹配)

OmniGlue论文详解(特征匹配) 摘要1. 引言2. 相关工作2.1. 广义局部特征匹配2.2. 稀疏可学习匹配2.3. 半稠密可学习匹配2.4. 与其他图像表示匹配 3. OmniGlue3.1. 模型概述3.2. OmniGlue 细节3.2.1. 特征提取3.2.2. 利用DINOv2构建图形。3.2.3. 信息传播与新的指导3.2.4. 匹配层和损失函数3.2.5. 与Super

软件架构模式:5 分钟阅读

原文: https://orkhanscience.medium.com/software-architecture-patterns-5-mins-read-e9e3c8eb47d2 软件架构模式:5 分钟阅读 当有人潜入软件工程世界时,有一天他需要学习软件架构模式的基础知识。当我刚接触编码时,我不知道从哪里获得简要介绍现有架构模式的资源,这样它就不会太详细和混乱,而是非常抽象和易

BERT 论文逐段精读【论文精读】

BERT: 近 3 年 NLP 最火 CV: 大数据集上的训练好的 NN 模型,提升 CV 任务的性能 —— ImageNet 的 CNN 模型 NLP: BERT 简化了 NLP 任务的训练,提升了 NLP 任务的性能 BERT 如何站在巨人的肩膀上的?使用了哪些 NLP 已有的技术和思想?哪些是 BERT 的创新? 1标题 + 作者 BERT: Pre-trainin