【HGT】文献精讲:Heterogeneous Graph Transformer

【HGT】文献精讲:Heterogeneous Graph Transformer

标题: Heterogeneous Graph Transformer
(异构图Transformer)
作者团队: 加利福尼亚大学Yizhou Sun
摘要: 近年来,图神经网络(GNN)在结构化数据建模方面取得了成功。然而,大多GNN是为同质图设计的,其中所有节点和边都属于同一类型,这使得表示异构结构变得不可行。本文提出了异构图转换器(HGT)架构来建模web规模的异构图。为了建模异构性,本文设计了节点和边缘类型相关的参数来表征每个边缘上的异构注意力,使HGT能够为不同类型的节点和边缘维护专用表示。为了处理web规模的图数据,文章设计了异构小批图采样算法——HGSampling,以实现高效和可扩展的训练。在包含1.79亿个节点和20亿个边的开放学术图上进行的大量实验表明,所提出的HGT模型在各种下游任务上的性能始终优于所有最先进的GNN基线9%-21%。

文献链接: https://dl.acm.org/doi/abs/10.1145/3366423.3380027
代码链接: https://github.com/acbull/pyHGT

1. 背景

过去尝试采用GNN与异构网络进行学习的工作往往面临着以下几个问题:

  • 大多数涉及为每种类型的异构图设计元路径或者变体,需要特定的领域知识;
  • 要么简单地假设不同类型的节点和边共享相同的特征和表示空间,要么单独为节点类型或边类型保留不同的非共享权重,使得它们不足以捕获异构图的属性;
  • 它们固有的设计和实现使得它们无法对web规模的异构图进行建模。

鉴于以上这些限制,本文设计了研究异构图的神经网络HGT,目标是保持节点和边类型的依赖表示,同时避免自定义元路径,并且可以扩展到web规模的异构图。

为了处理图的异构性,文章引入了依赖于节点和边类型的注意力机制,HGT中的异构相互注意不是参数化每种类型的边,而是通过基于其元关系三元组分解每个边 e = < s , t > e=<s,t> e=<s,t>来定义,其中s、t表示节点类型,e表示s与t之间的边类型。具体来说,HGT使用这些元关系来参数化权重矩阵,以计算每条边的注意力分数。因此,这样允许不同类型的节点和边保持其特定的表示空间。与此同时,不同类型的连接节点人若干可以交互、传递和聚合消息,不受其分布间隙的限制。
由于其体系结构的性质,HGT可以通过跨层的消息传递来合并来自不同类型的高阶邻居的信息,这也被称为“软”元路径。也就是说HGT只把它的一跳边作为输入,而不用手动设计元路径,所提出的注意力机制也可以自动和隐式地学习和提取对不同下游任务很重要的元路径

2.方法

在这里插入图片描述

上图显示了HGT的整体架构。给定一个采样的异构子图,HGT提取所有连接的节点对,其中目标节点t通过边e被源节点s连接,HGT的目标是聚合来自s的信息,以获得节点目标t的上下文表示。该过程主要是三个组件:异构互注意力、异构消息传递和目标特定聚合

2.1 Heterogeneous Mutual Attention 异构互注意力

将第 l l l个HGT层的输出表示为 H ( l ) H^{(l)} H(l),同时也作为第 l + 1 l+1 l+1个HGT层的输入。通过堆叠L层,可以得到整个图 H ( L ) H^{(L)} H(L)的节点表示,可以用于端到端训练或馈送到下游任务。
第一步首先是计算源节点 s s s与目标节点 t t t之间的相互注意力分数。在基于注意力的GNN中,有
H l [ t ] ← A g g r e g a t e ∀ s ∈ N ( t ) , ∀ e ∈ E ( s , t ) ( A t t e n t i o n ( s , t ) ⋅ M e s s a g e ( s ) ) H^{l} [t]\gets \underset{\forall s\in N(t),\forall e\in E(s,t)}{\mathbf{Aggregate } }(\mathbf{Attention}(s,t)\cdot \mathbf{Message}(s) ) Hl[t]sN(t),eE(s,t)Aggregate(Attention(s,t)Message(s))
其中三个基本的运算符:

  • A t t e n t i o n \mathbf{Attention} Attention用于计算每个源节点的重要性
  • M e s s a g e \mathbf{Message} Message用于使用源节点来提取消息
  • A g g r e g a t e \mathbf{Aggregate } Aggregate通过关注权重对邻居信息进行聚合
    例如,图注意力网络(GAT)采用了一种加性机制作为 A t t e n t i o n \mathbf{Attention} Attention,使用相同的权重来计算 M e s s a g e \mathbf{Message} Message,并利用简单平均和非线性激活函数来进行 A g g r e g a t e \mathbf{Aggregate } Aggregate步骤。形式上来看,GAT有:
    A t t e n t i o n G A T ( s , t ) = ∀ s ∈ N ( t ) ( a ⃗ ( W H l − 1 [ t ] ∥ W H l − 1 [ s ] ) ) M e s s a g e G A T ( s ) = W H l − 1 [ s ] A g g r e g a t e G A T ( ⋅ ) = σ ( Mean ⁡ ( ⋅ ) ) \begin{aligned} \mathbf{ Attention }_{G A T}(s, t) & =\underset{\forall s \in N(t)}{ }\left(\vec{a}\left(W H^{l-1}[t] \| W H^{l-1}[s]\right)\right) \\ \mathbf { Message }_{G A T}(s) & =W H^{l-1}[s] \\ \mathbf { Aggregate }_{G A T}(\cdot) & =\sigma(\operatorname{Mean}(\cdot)) \end{aligned} AttentionGAT(s,t)MessageGAT(s)AggregateGAT()=sN(t)(a (WHl1[t]WHl1[s]))=WHl1[s]=σ(Mean())
    虽然GAT对重要节点给予高关注度是有效的,但是它通过使用一个权重矩阵 W W W来假设节点 s s s和节点 t t t具有相同的特征分布,这种假设对于异构图来说通常是不正确的,因为每种类型的节点都会有自己的特征分布。基于此,作者设计了异构互注意力机制。
    给定一个目标节点 t t t,以及它所有的邻居节点 s ∈ N ( t ) s \in N(t) sN(t) ,它们可能属于不同的分布,根据它们的元关系计算它们的相互注意力,即 < τ ( s ) , ϕ ( e ) , τ ( s ) > <\tau(s), \phi(e), \tau(s)> <τ(s),ϕ(e),τ(s)>三元组。
    作者将目标节点 t t t映射为一个Query向量,将源节点 s s s映射为一个Key向量,并计算它们的点积作为注意力。其与普通的Transformer的关键区别在于,普通Transformer对所有单词使用一组投影,而在HGT中,每个元关系都有一组不同的投影权重。为了最大限度地实现参数共享,同时保持不同关系地特定特征,作者提出将交互算子地权重矩阵参数化为源节点投影、边投影和目标节点投影。具体来说,通过以下公式为每条边 e = ( s , t ) e=(s,t) e=(s,t)计算 h h h个头注意力:
    A t t e n t i o n H G T ( s , e , t ) = Softmax ⁡ ∀ s ∈ N ( t ) ( ∏ i ∈ [ 1 , h ] A T T − head  i ( s , e , t ) ) A T T − head  i ( s , e , t ) = ( K i ( s ) W ϕ ( e ) A T T Q i ( t ) T ) ⋅ μ ⟨ τ ( s ) , ϕ ( e ) , τ ( t ) ⟩ d K i ( s ) = K-Linear  τ ( s ) i ( H ( l − 1 ) [ s ] ) Q i ( t ) = Q-Linear  τ ( t ) i ( H ( l − 1 ) [ t ] ) \begin{aligned} \mathbf{Attention}_{H G T}(s, e, t) & =\underset{\forall s \in N(t)}{\operatorname{Softmax}}\left(\prod_{i \in[1, h]} A T T-\text { head }^{i}(s, e, t)\right) \\ A T T-\text { head }^{i}(s, e, t) & =\left(K^{i}(s) W_{\phi(e)}^{A T T} Q^{i}(t)^{T}\right) \cdot \frac{\mu_{\langle\tau(s), \phi(e), \tau(t)\rangle}}{\sqrt{d}} \\ K^{i}(s) & =\text { K-Linear }_{\tau(s)}^{i}\left(H^{(l-1)}[s]\right) \\ Q^{i}(t) & =\text { Q-Linear }_{\tau(t)}^{i}\left(H^{(l-1)}[t]\right) \end{aligned} AttentionHGT(s,e,t)ATT head i(s,e,t)Ki(s)Qi(t)=sN(t)Softmax i[1,h]ATT head i(s,e,t) =(Ki(s)Wϕ(e)ATTQi(t)T)d μτ(s),ϕ(e),τ(t)⟩= K-Linear τ(s)i(H(l1)[s])= Q-Linear τ(t)i(H(l1)[t])
    首先,对于第 i i i个注意的头 A T T − h e a d i ( s , e , t ) ATT-head^i(s,e,t) ATTheadi(s,e,t),通过线性函数 $K-Linear_{\tau(s)}^{i}:\mathbb{R} ^{d} \to \mathbb{R} ^{\frac{d}{h} } $ 将源节点 τ ( s ) \tau (s) τ(s)投影到第 i i i个键向量 K i ( s ) K^i(s) Ki(s),其中 h h h是注意力头的数量, d h \frac{d}{h} hd是每个头的向量维度。注意, K − L i n e a r τ ( s ) i K-Linear_{\tau(s)}^{i} KLinearτ(s)i是由源节点 s s s的类型 τ ( s ) \tau (s) τ(s)索引的,这意味着每种类型的节点都有一个唯一的线性投影,以最大限度地模拟分布差异。类似地,通过线性函数 Q − L i n e a r τ ( t ) i Q-Linear _{\tau(t)}^{i} QLinearτ(t)i将目标节点 t t t投影到第 i i i个查询向量中。
    接下来,计算查询向量 Q i ( t ) Q^i(t) Qi(t)和键向量 K i ( s ) K^i(s) Ki(s)的相似性。异构图的一个独特之处就是有可能存在不同边类型之间的一堆节点类型,例如 τ ( s ) \tau(s) τ(s) τ ( t ) \tau(t) τ(t)。因此仍然为每种类型的边 ϕ ( e ) \phi(e) ϕ(e)使用独特的边缘权重矩阵 W ϕ ( e ) A T T ∈ R d h × d h W^{ATT}_{\phi (e)} \in \mathbb{R}^{\frac{d}{h} \times \frac{d}{h}} Wϕ(e)ATTRhd×hd。这样一来,即使在相同的节点类型对之间,模型也可以捕获不同的语义关系。另外,由于并非所有关系对目标节点的贡献相同,作者添加一个先验张量 μ ∈ R ∣ A ∣ × ∣ R ∣ × ∣ A ∣ \mu \in \mathbb{R}^{|\mathcal{A} |\times |\mathcal{R} | \times |\mathcal{A} |} μRA×R×A来表示每个元关系三元组的一般意义,作为对注意力的自适应缩放。
    最后,将 h h h个注意力头连接在一起,等到每个节点对的注意向量。随后对于每个目标节点 t t t,从它的邻居节点 N ( t ) N(t) N(t)收集所有的注意力向量,并使用softmax函数,使其满足 $ { \sum_{\forall s\in N(t)}}\mathbf{Attention} _{HGT} (s,e,t)=\mathbf{1} _{h\times 1} $.

2.2 Heterogeneous Message Passing 异构消息传递

与第一步计算异构互注意力并行,将信息从源节点传递到目标节点。对于一对节点 e = ( s , t ) e=(s,t) e=(s,t),通过以下公式计算其多头消息:
Message ⁡ H G T ( s , e , t ) = ∥ i ∈ [ 1 , h ] MSG-head  i ( s , e , t ) M S G − head  i ( s , e , t ) = M-Linear  τ ( s ) i ( H ( l − 1 ) [ s ] ) W ϕ ( e ) M S G \begin{array}{l} \operatorname{Message}_{H G T}(s, e, t)=\|_{i \in[1, h]} \text { MSG-head }^{i}(s, e, t) \\ M S G-\text { head }^{i}(s, e, t)=\text { M-Linear }{ }_{\tau(s)}^{i}\left(H^{(l-1)}[s]\right) W_{\phi(e)}^{M S G} \end{array} MessageHGT(s,e,t)=i[1,h] MSG-head i(s,e,t)MSG head i(s,e,t)= M-Linear τ(s)i(H(l1)[s])Wϕ(e)MSG
为了得到第 i i i个消息头 M S G − h e a d i ( s , e , t ) MSG-head^i(s,e,t) MSGheadi(s,e,t),首先使用线性函数$M-Linear_{\tau(s)}^{i}:\mathbb{R} ^{d} \to \mathbb{R} ^{\frac{d}{h} } 将 将 \tau(s) 型源节点 型源节点 型源节点s 投影到第 投影到第 投影到第i 个消息向量中。随后使用矩阵 个消息向量中。随后使用矩阵 个消息向量中。随后使用矩阵W^{MSG}{\phi (e)} \in \mathbb{R}^{\frac{d}{h} \times \frac{d}{h}} 合并边缘依赖性。最后连接所有 合并边缘依赖性。最后连接所有 合并边缘依赖性。最后连接所有h 个消息头以获取每个节点对的 个消息头以获取每个节点对的 个消息头以获取每个节点对的\mathbb{Message}{HGT}(s,e,t)$

2.3 Target-Specific Aggregation 目标特定聚合

最后将计算的异构多头注意力和消息从源节点聚合到目标节点。在计算异构互注意力过程中softmax已经使每个目标节点 t t t的注意力向量汇聚成了一个和。因此此时可以简单地使用注意力向量作为权重来平均来自源节点的对应消息,并得到更新的向量 H ~ ( l ) [ t ] \widetilde{H}^{(l)}[t] H (l)[t]为:
H ~ ( l ) [ t ] = ⊕ ∀ s ∈ N ( t ) ( A t t e n t i o n H G T ( s , e , t ) ⋅ M e s s a g e H G T ( s , e , t ) ) \widetilde{H}^{(l)}[t]=\underset{\forall s \in N(t)}{\oplus}\left(\mathbf { Attention }_{H G T}(s, e, t) \cdot \mathbf { Message }_{H G T}(s, e, t)\right) H (l)[t]=sN(t)(AttentionHGT(s,e,t)MessageHGT(s,e,t))
以此将不同特征分布的源节点所有的邻居节点的信息聚合到目标节点 t t t
最后再将目标节点 t t t的向量由其节点类型 τ ( t ) \tau(t) τ(t)的索引映射回其特定类型的分布。为此,使用线性函数 A − L i n e a r τ ( t ) A-Linear_{\tau(t)} ALinearτ(t)来更新向量 H ~ ( l ) [ t ] \widetilde{H}^{(l)}[t] H (l)[t],然后进行非线性激活和残差连接为:
H ~ ( l ) [ t ] = σ ( A − L i n e a r τ ( t ) H ~ ( l ) [ t ] ) + H ~ ( l − 1 ) [ t ] \widetilde{H}^{(l)}[t]=\sigma(A-Linear_{\tau(t)\widetilde{H}^{(l)}[t]})+\widetilde{H}^{(l-1)}[t] H (l)[t]=σ(ALinearτ(t)H (l)[t])+H (l1)[t]
这样得到目标节点 t t t的第 l l l个HGT层的输出 H ( l ) [ t ] H^{(l)}[t] H(l)[t],将 l l l层的HGT块堆叠,使每个节点在整个图中达到不同类型和关系的节点的很大比例,即HGT为每个节点生成一个高度情境化的表示 H ( L ) H^{(L)} H(L),该表示可以输送到任何模型中进行下游异构网络任务,如节点分类和链路预测。

2.4 HGSampling 小批图采样算法

作者还提出一种高效的异构小批图采样算法—HGSampling——使HGT和传统GNN都能处理web规模的异构图。HGSampling能够为每种类型保持相似数量的节点和边,同时还能采样子图的密度,以最小化信息损失和样本方差。
在这里插入图片描述

以上为HGSampling的伪代码。其基本思想是为每种节点类型 τ \tau τ保持一个单独的节点预算 B [ τ ] B[\tau] B[τ],并使用重要采样策略对每种类型的节点进行相同数量的采样以减小方差。

3. 结果

最终在OAG数据集中进行节点分类任务发现,HGT模型远优于当前其他模型。
在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/467503.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

AI 写作(三)文本生成算法:创新与突破(3/10)

一、生成式与判别式模型&#xff1a;AI 写作的基石 &#xff08;一&#xff09;区别与特点 生成式模型和判别式模型在多个方面存在明显差异。在优化准则上&#xff0c;生成式模型致力于学习联合概率分布&#xff0c;而判别式模型则专注于建立输入数据和输出之间的关系&#xf…

蓝桥杯 懒洋洋字符串--字符串读入

题目 代码 #include <iostream>using namespace std;int main(){int n;cin>>n;char s[210][4];int ans0;for(int i0;i<n;i){scanf("%s",s[i]);}for(int i0;i<n;i){char as[i][0];char bs[i][1];char cs[i][2];// cout<<a<< <<b…

小红书图文矩阵的运营策略与引流技巧解析

内容概要 小红书图文矩阵是一种高效的内容运营方式&#xff0c;能够帮助品牌在竞争激烈的环境中脱颖而出。通过构建矩阵账号&#xff0c;品牌可以实现多维度的内容覆盖&#xff0c;创造出丰富而立体的用户体验。为什么要做图文矩阵&#xff1f;首先&#xff0c;这种方式能够提…

2.Python解释器

python解释器程序&#xff0c;用来翻译python代码&#xff0c;并提交给计算机执行。 上一篇博客就是安装了python解释器程序 写一个python文件&#xff0c;在文件中写入多行代码并执行&#xff1a; 进入python后&#xff0c;输入exit()命令退出

书生实战营第四期-基础岛第四关-InternLM + LlamaIndex RAG 实践

一、任务要求1 基于 LlamaIndex 构建自己的 RAG 知识库&#xff0c;寻找一个问题 A 在使用 LlamaIndex 之前 浦语 API 不会回答&#xff0c;借助 LlamaIndex 后 浦语 API 具备回答 A 的能力&#xff0c;截图保存。 1、配置开发机系统 镜像&#xff1a;使用 Cuda12.0-conda 镜…

【路径规划】PID搜索算法PSA求解UAV路径规划

摘要 本文研究了基于PID搜索算法&#xff08;PID Search Algorithm, PSA&#xff09;求解无人机&#xff08;UAV&#xff09;路径规划问题。通过引入PID控制思想来控制路径生成过程&#xff0c;使得无人机可以避开障碍物并在复杂地形中寻找最优路径。实验结果表明&#xff0c;…

编写第一个 Appium 测试脚本:从安装到运行!

前言 最近接到一个测试项目&#xff0c;简单描述一下&#xff0c;需求就是&#xff1a;一端发送指令&#xff0c;另一端接受指令并处理指令。大概看了看有上百条指令&#xff0c;点点点岂不是废了&#xff0c;而且后期迭代&#xff0c;每次都需要点点点&#xff0c;想想就头大…

劫持微信聊天记录并分析还原 —— 访问数据库并查看聊天记录(五)

本工具设计的初衷是用来获取微信账号的相关信息并解析PC版微信的数据库。程序以 Python 语言开发&#xff0c;可读取、解密、还原微信数据库并帮助用户查看聊天记录&#xff0c;还可以将其聊天记录导出为csv、html等格式用于AI训练&#xff0c;自动回复或备份等等作用。下面我们…

微软日志丢失事件敲响安全警钟

NEWS | 事件回顾 最近&#xff0c;全球最大的软件公司之一——微软&#xff0c;遭遇了一场罕见的日志丢失危机。据报告&#xff0c;从9月2日至9月19日&#xff0c;持续长达两周的时间里&#xff0c;微软的多项核心云服务&#xff0c;包括身份验证平台Microsoft Entra、安全信息…

音视频入门基础:H.264专题(17)——FFmpeg源码中,获取H.264视频的profile的实现

音视频入门基础&#xff1a;H.264专题系列文章&#xff1a; 音视频入门基础&#xff1a;H.264专题&#xff08;1&#xff09;——H.264官方文档下载 音视频入门基础&#xff1a;H.264专题&#xff08;2&#xff09;——使用FFmpeg命令生成H.264裸流文件 音视频入门基础&…

硬件基础06 滤波器——无源、有源(含Filter Solutions、Filter Pro、MATLAB Fdatool)

目录 一、Filter Solutions 1、软件资源及安装教程如下 2、使用相关内容 二、Filter Pro使用 1、软件资源及安装教程如下 2、使用相关内容 三、MATLAB Fdatool 1、在matlab命令中输入fdatool 2、输入相关参数&#xff0c;例如低通、FIR、20阶、hamming窗 3、调用 &am…

《数据治理精选案例集2.0(2024版)》592页PDF(已授权分享)

《亿信华辰数据治理精选案例集2.0》是北京亿信华辰软件有限责任公司倾力打造的专业数据治理案例集&#xff0c;汇集了100个一线政企数据治理实践案例&#xff0c;覆盖13大行业和500业务场景&#xff0c;通过深入剖析数据治理难题&#xff0c;提供了新思路和实战经验&#xff0c…

LangChain大模型应用开发指南:打造个性化LLM

在之前的课程中&#xff0c;我带领小伙伴们使用开源项目实现了将星火模型的OpenAI-API接口适配转换封装&#xff0c; 但是这种做法的局限性也很强&#xff0c;只能使用开源项目适配过的大模型&#xff0c;并且由于多了一层适配代理&#xff0c;接口的性能也存在一定损耗。今天…

Spring WebFlux 核心原理(2-3)

1、Project Reactor 高级 1.1、响应式流的生命周期 要理解多线程的工作原理以及 Reactor 中实现的各种内部优化&#xff0c;首先必须了解 Reactor 中响应式类型的生命周期。 1.1.1、组装时 流生命周期的第一部分是组装时&#xff08;assembly-time&#xff09;。 Reactor 提供…

走进算法大门---双指针问题(一)

一.双指针算法介绍 概念&#xff1a;双指针是指在遍历数据结构&#xff08;如数组、链表等&#xff09;时使用两个指针&#xff0c;通过特定的移动规则来解决问题。这两个指针可以同向移动&#xff0c;也可以相向移动。 同向双指针&#xff1a;常用于解决需要两个位置信息的问…

智能问答系统流程详解:多轮对话与模型训练的技术要点及案例

随着智能客服系统的广泛应用&#xff0c;如何在提升用户体验的同时保障系统的准确性与效率&#xff0c;成为了智能问答系统设计中的重要问题。本文将介绍一种智能问答系统的流程设计&#xff0c;涵盖从识别用户意图、匹配知识库、多轮对话到模型训练的全流程&#xff0c;并通过…

03集合基础

目录 1.集合 Collection Map 常用集合 List 接口及其实现 Set 接口及其实现 Map 接口及其实现 Queue 接口及其实现 Deque 接口及其实现 Stack类 并发集合类 工具类 2.ArrayList 3.LinkedList 单向链表的实现 1. 节点类&#xff08;Node&#xff09; 2. 链表类&a…

pyspark基础准备

1.前言介绍 学习目标&#xff1a;了解什么是Speak、PySpark&#xff0c;了解为什么学习PySpark&#xff0c;了解课程是如何和大数据开发方向进行衔接 使用pyspark库所写出来的代码&#xff0c;既可以在电脑上简单运行&#xff0c;进行数据分析处理&#xff0c;又可以把代码无缝…

gitlab项目如何修改主分支main为master,以及可能遇到的问题

如果你希望将 Git 仓库的主分支名称从 main 修改为 master&#xff1a; 1. 本地修改分支名称 首先&#xff0c;切换到 main 分支&#xff1a; git checkout main将 main 分支重命名为 master&#xff1a; git branch -m main master2. 更新远程仓库 将本地更改推送到远程仓库…

albert模型实现微信公众号虚假新闻分类

项目源码获取方式见文章末尾&#xff01; 600多个深度学习项目资料&#xff0c;快来加入社群一起学习吧。 《------往期经典推荐------》 项目名称 1.【基于CNN-RNN的影像报告生成】 2.【卫星图像道路检测DeepLabV3Plus模型】 3.【GAN模型实现二次元头像生成】 4.【CNN模型实现…