
论文题目:MAGNN: Metapath Aggregated Graph Neural Network for Heterogeneous Graph Embedding
论文来源:WWW 2020
论文链接:https://arxiv.org/pdf/2002.01680.pdf
代码链接:https://github.com/cynricfu/MAGNN
关键词:神经网络,表示学习,社交网络,异质图,attention
本文提出MAGNN模型,正如标题所言,围绕元路径聚合的问题展开,需要人为定义元路径。聚合是指元路径内部的聚合、元路径间的聚合。在建模过程中还融入了节点内容特征的信息(节点属性信息)。
文章目录
- 1 引言
- 2 相关定义和符号
- 3 方法
-
- 3.1 Node Content Transformation
- 3.2 Intra-metapath Aggregation
- 3.3 Inter-metapath Aggregation
- 3.4 Metapath Instance Encoders
- 3.5 训练
- 4 实验
- 5 总结
- 参考文献
1 引言
本文解决的是异质图的嵌入学习问题。
现有的基于元路径的嵌入学习方法有以下局限性:
(1)忽略节点的内容特征(属性信息),不能很好地处理节点属性特征丰富的异质图。例如 metapath2vec, ESim, HIN2vec, HERec。
(2)舍弃了元路径内部的节点信息,只考虑元路径的起始节点和末尾节点,造成信息损失。例如 HERec, HAN。
(3)只依赖于单个元路径,因此需要人工选择元路径,丢失了来自其他元路径的部分信息,导致性能不佳。例如 metapath2vec。
为了解决上述问题,本文提出MAGNN(Metapath Aggregated Graph Neural Network )。
MAGNN由三个部分组成:
(1)节点内容转换(node content transformation ),将异质的节点属性信息映射到同一个隐层的向量空间;
(2)元路径内部聚合(intra-metapath aggregation ),使用注意力机制将元路径内部的语义信息纳入考虑;
(3)元路径间的聚合(inter-metapath aggregation ),使用注意力机制从多个元路径聚合信息。
贡献:
(1)提出新的元路径聚合的GNN方法用于异质图的嵌入学习;
(2)设计了几个候选编码器函数,用于从集合实例中提取信息,其中一个基于复杂空间中的关系旋转思想。
(3)在IMDB和DBLP数据集上进行了节点分类和节点聚类任务,在Last.fm数据集上进行了链接预测任务。实验证明使用MAGNN学习得到的节点嵌入表示超越了state-of-the-art baselines的表现。
2 相关定义和符号
异质图、元路径、元路径实例的定义不再赘述。
相关定义的图示如下图所示:
Metapath-based Neighbor:
给定异质图中的一个元路径 P P P,节点 v v v的metapath-based邻居 N v P \mathcal{N}^P_v NvP为和 v v v相连的遵循元路径 P P P的模式的节点集合。由两个不同的元路径实例与 v v v相连的同一个邻居节点,被视为 N v P \mathcal{N}^P_v NvP中的两个节点。另外,如果元路径 P P P是对称的, N v P \mathcal{N}^P_v NvP中也包含节点 v v v自身。
Metapath-based Graph:
给定异质图 G \mathcal{G} G中的元路径 P P P,基于元路径的图 G P \mathcal{G}^P GP由原始图 G \mathcal{G} G中所有的基于元路径 P P P的邻居点对组成(去掉了元路径实例的中间节点,只保留了元路径实例两端的节点,并在两点间建立起连边)。如果元路径 P P P是对称的,则 G P \mathcal{G}^P GP是同质图。如上图(d)所示。
异质图嵌入:
给定 G = ( V , E ) \mathcal{G}=(\mathcal{V}, \mathcal{E}) G=(V,E)和节点属性矩阵 X A i ∈ R ∣ V A i ∣ × d A i \mathbf{X}_{A_i}\in \mathbb{R}^{|\mathcal{V}_{A_i}|\times d_{A_i}} XAi∈R∣VAi∣×dAi,其中 A i A_i Ai表示节点类型,异质图嵌入学习的目的是从图中捕获到丰富的结构信息和语义信息,从而为每个节点学习到 d d d维的表示 h v ∈ R d \mathbf{h}_v\in \mathbb{R}^d hv∈Rd。
3 方法
MAGNN由节点内容转换、元路径内部聚合、元路径间的聚合三部分组成,图2展示了一个节点的嵌入生成过程。
3.1 Node Content Transformation
异质图中的不同类型的节点有着不同的属性,因此不同类型的节点的特征向量可能有着不同的维度,即使碰巧维度相同,特征向量也应该属于不同的特征空间。
为了方便统一处理,需要将这些不同类型的节点的特征映射到同一个隐层的向量空间中。具体方法就是对每种类型的节点都使用一个特定的线性转换,来将节点的特征向量转换到同一个隐层的特征空间中。对于类别为 A ∈ A A\in \mathcal{A} A∈A节点 v ∈ V A v\in \mathcal{V}_A v∈VA,进行如下的转换:
其中 x v ∈ R d A x_v\in \mathbb{R}^{d_A} xv∈RdA是原始的特征向量, h v ′ ∈ R d ′ \mathbf{h}^{'}_v\in \mathbb{R}^{d^{'}} hv′∈Rd′是映射后的节点 v v v的特征向量。 W A ∈ R d ′ × d A W_A\in \mathbb{R}^{d^{'}\times d_A} WA∈Rd′×dA是对于类型为 A A A的节点的参数化权重矩阵。
3.2 Intra-metapath Aggregation
给定元路径 P P P,元路径内部聚合层通过对 P P P的元路径实例编码,可以学习到 目标节点、基于元路径的邻居节点、节点之间的上下文 中嵌入的结构信息和语义信息。
定义连接目标节点 v v v和它的metapath-based邻居节点 u ∈ N v P u\in \mathcal{N}^P_v u∈NvP为 P ( v , u ) P(v, u) P(v,u)。
定义 P ( v , u ) P(v, u) P(v,u)的内部节点为 { m P ( v , u ) } = P ( v , u ) ∖ { u , v } {\{m^{P(v, u)}\}}=P(v, u)\setminus{\{u, v\}} {mP(v,u)}=P(v,u)∖{u,v}。
(1)元路径内部聚合采用了特殊的元路径实例编码器(metapath instance encoder)将元路径实例中的所有节点的特征转换成向量 h P ( v , u ) ∈ R d ′ \mathbf{h}_{P(v,u)}\in \mathbb{R}^{d^{'}} hP(v,u)∈Rd′:
节点 v , u v, u v,u之间可能存在多个元路径实例,3.4节介绍了限定的metapath instance encoder的几种选择。
(2)接着使用图注意力层(graph attention layer)加权聚合针对目标节点 v v v的且元路径为 P P P的多个元路径实例:
其中 a P ∈ R 2 d ′ a_P\in \mathbb{R}^{2d^{'}} aP∈R2d′是元路径 P P P的参数化的注意力向量。 e v u P e^P_{vu} evuP表示元路径实例 P ( v , u ) P(v, u) P(v,u)对节点 v v v的重要性,然后使用softmax进行了归一化,然后使用归一化后的注意力系数对和节点 v v v相关的元路径实例的表示进行加权求和。最后再经过一个激活函数。
(3)上述的注意力机制可以扩展成多头的(multi-heads),这有助于学习过程的稳定,并且可以减小图的异质性带来的高方差:
总结:
给出映射后的特征向量 h u ′ ∈ R d ′ , ∀ u ∈ V h^{'}_u\in \mathbb{R}^{d^{'}}, \forall u\in \mathcal{V} hu′∈Rd′,∀u∈V,以及一组元路径 P A = { P 1 , P 2 , . . . , P M } \mathcal{P}_A={\{P_1, P_2, ..., P_M\}} PA={P1,P2,...,PM}。内部元路径聚合为目标节点 v v v生成 M M M个针对特定元路径的向量表示,记为 { h v P 1 , h v P 2 , . . . , h v P M } {\{h^{P_1}_v,h^{P_2}_v, ..., h^{P_M}_v \}} {hvP1,hvP2,...,hvPM},每个$ h^{P_i}_v\in \mathbb{R}{d{’}} ( 假 定 (假定 (假定K=1 ) 都 表 示 了 节 点 )都表示了节点 )都表示了节点v$中隐含的一种语义信息。
3.3 Inter-metapath Aggregation
使用元路径间的聚合层结合所有元路径的语义信息。
从上一步可知,对于类型为 A A A的节点,生成了 ∣ V A ∣ |\mathcal{V}_A| ∣VA∣组隐层向量: { h v P 1 , h v P 2 , . . . , h v P M } {\{h^{P_1}_v, h^{P_2}_v, ..., h^{P_M}_v\}} {hvP1,hvP2,...,hvPM}, v ∈ V A v\in \mathcal{V}_A v∈VA, M M M是 A A A类型节点的元路径数目。使用注意力机制为不同的元路径分配不同的权重。
(1)首先,针对每条元路径 P i ∈ P A P_i\in \mathcal{P}_A Pi∈PA,对所有类型为 A A A的节点在特定元路径下的节点向量进行转换,然后取平均:
其中 M A ∈ R d m × d ′ , b A ∈ R d m M_A\in \mathbb{R}^{d_m\times d^{'}}, b_A\in \mathbb{R}^{d_m} MA∈Rdm×d′,bA∈Rdm为可学习到的参数。
(2)然后使用注意力机制混合特定元路径下的节点 v v v的特征向量:
其中 q A ∈ R d m q_A\in \mathbb{R}^{d_m} qA∈Rdm为参数化的针对 A A A类型节点的注意力向量。 β P i \beta_{P_i} βPi可解释为元路径 P i P_i Pi对于 A A A类型节点的重要性。使用这个注意力系数对节点 v v v的所有针对特定元路径的向量进行加权求和。
(3)最后,MAGNN使用线性转换和一层非线性函数,将节点嵌入映射到输出所需维度的向量空间:
其中 W o ∈ R d o × d ′ W_o\in \mathbb{R}^{d_o\times d^{'}} Wo∈Rdo×d′是权重矩阵, σ ( ⋅ ) \sigma(\cdot) σ(⋅)是激活函数。
这个映射针对具体任务有所不同,可以看成是用于节点分类的线性分类器,也可看成是带有节点间相似度度量的空间投影,可用于链接预测。
3.4 Metapath Instance Encoders
本节对应3.2(2)式中的元路径实例编码函数 f θ f_{\theta} fθ,作者给出了三个候选的编码函数:
(1)Mean encoder:
(2)Linear encoder
是mean encoder的扩展,区别在于添加了一个线性转换。
(3)Relational rotation encoder
基于在复杂空间的关系旋转(relation rotation)的元路径实例编码器。这一操作是RotatE[1]提出的,原文做的是知识图谱的嵌入学习。
mean encoder 和 linear encoder将元路径实例看作了一个集合,忽视了元路径序列结构中嵌入的信息。关系旋转的方法提供了建模这一类知识的方法。
给定 P ( v , u ) = ( t 0 , t 1 , . . . , t n ) , t 0 = u , t n = v P(v, u)=(t_0, t_1, ..., t_n), t_0=u, t_n=v P(v,u)=(t0,t1,...,tn),t0=u,tn=v, R i R_i Ri为节点 t i − 1 , t i t_{i-1}, t_i ti−1,ti之间的关系。令 r i \mathbf{r}_i ri为 R i R_i Ri的向量表示。Relational rotation encoder可形式化为:
其中, h t i ′ , r i \mathbf{h}^{'}_{t_i}, \mathbf{r}_i hti′,ri是复杂的向量, ⊙ \odot ⊙表示元素间乘积。可将 d ′ d^{'} d′维的真实向量( h P ( v , u ) \mathbf{h}_{P(v,u)} hP(v,u))看成是一个复杂的向量,它的前 d ′ / 2 d^{'}/2 d′/2维是真实的部分,后 d ′ / 2 d^{'}/2 d′/2为虚构的部分。
MAGNN前向传播算法如下:
3.5 训练
经过上述的三个部分,得到了最终的节点表示,可用于下游任务。
由于不同任务的特点不同,而且不一定能得到节点标签。因此为MAGNN设计了两种学习范式:半监督学习、无监督学习。
(1)半监督学习
最小化交叉熵损失:
其中, V L \mathcal{V}_L VL是有标签的节点集合, C C C是类别数目, y v \mathbf{y}_v yv是节点 v v v的one-hot向量, h v \mathbf{h}_v hv是模型输出的节点 v v v的向量表示。
(2)无监督学习
使用负采样技术,最小化如下的损失函数:
其中, Ω \Omega Ω是正样本集合, Ω − \Omega^{-} Ω−是负样本集合。
4 实验
实验回答了以下几个问题:
- MAGNN在节点分类任务上表现如何?
- MAGNN在节点聚类任务上表现如何?
- MAGNN在链接预测任务上表现如何?
- MAGNN的三个主要组成部分对其有什么样的影响?
- 如何理解不同图嵌入方法的表示学习能力?
数据集:
IMDb、DBLP、Last.fm
**实验任务:**节点分类、节点聚类、链接预测
对比方法:
- LINE:同质图模型,使用了节点间的一阶和二阶相似度;
- node2vec:同质图模型;
- ESim:异质图模型,从采样到的元路径实例中学习节点嵌入;
- metapath2vec:异质图模型,元路径指导下得到的随机游走路径输入到skip-gram模型中,得到节点嵌入;
- HERec:异质图模型,使用元路径将异质图转化为同质图,再在其上面进行随机游走;
- GCN:同质图GNN;
- GAT:同质图GNN;
- GATNE:异质图GNN,使用基类嵌入和边嵌入学习到节点表示,聚焦于链接预测任务;
- HAN:异质图GNN,从基于元路径的同质图学习到特定元路径下的节点嵌入,使用注意力机制进行聚合。
实验结果:
(1)节点分类实验结果(RQ1)
(2)节点聚类实验结果(RQ2)
(3)链接预测实验结果(RQ3)
(4)消融实验(RQ4)
- M A G N N r o t MAGNN_{rot} MAGNNrot使用了relation rotation encoder,作为参考模型;
- M A G N N f e a t MAGNN_{feat} MAGNNfeat没有使用节点内容特征;
- M A G N N n b MAGNN_{nb} MAGNNnb只考虑了基于元路径的邻居;
- M A G N N s m MAGNN_{sm} MAGNNsm考虑了单个最好的元路径;
- M A G N N a v g MAGNN_{avg} MAGNNavg使用了mean对元路径实例进行编码;
- M A G N N l i n e a r MAGNN_{linear} MAGNNlinear使用了linear对元路径实例进行编码。
M A G N N n b MAGNN_{nb} MAGNNnb和 M A G N N a v g , M A G N N l i n e a r , M A G N N r o t MAGNN_{avg}, MAGNN_{linear}, MAGNN_{rot} MAGNNavg,MAGNNlinear,MAGNNrot相比,可以看出聚合元路径实例比metapath-based邻居带来的提升更多,验证了元路径内部聚合(intra-metapath aggregation)的有效性。
比较 M A G N N s m MAGNN_{sm} MAGNNsm和 M A G N N r o t MAGNN_{rot} MAGNNrot可以看出元路径间聚合(intre-metapath aggregation)的有效性。
比较 M A G N N a v g , M A G N N l i n e a r , M A G N N r o t MAGNN_{avg}, MAGNN_{linear}, MAGNN_{rot} MAGNNavg,MAGNNlinear,MAGNNrot可以看出,使用relational rotation encoder可带来提升。这三个变形都比目前最好的baseline HAN要表现好。
(5)可视化(RQ5)
5 总结
本文提出元路径聚合的GNN模型——MAGNN,解决现有异质图嵌入方法的三个缺点:
(1)忽略节点的内容特征;
(2)不考虑元路径内部的节点;
(3)只考虑单个元路径。
MAGNN由三个部分组成,分别解决了上述的三个问题:
(1)节点内容转换(node content transformation)
(2)元路径内部聚合(intra-metapath aggregation)
(3)元路径间的聚合(inter-metapath aggregation)
另外,本文还定义了元路径实例编码器,以抽取出元路径实例中的结构信息和语义信息。提出3个候选的编码函数,其中relation rotation encoder是受RotatE启发的。
在真实数据集上进行了节点分类、节点聚类、链接预测三个任务,达到state-of-the-art。
未来方向:将MAGNN应用到rating prediction任务中(例如 推荐任务)。
本文正如标题所示,一目了然,方法围绕元路径的聚合展开。聚合具体分为元路径内部的聚合、元路径间的聚合。
聚合当然少不了注意力机制,这两个聚合都使用到了注意力机制,还引入了多头注意力(multi-head attention)。
MAGNN在建模的过程中还使用了节点的属性信息,GATNE[2]模型也考虑到了这一点,实验中也和此方法进行了对比。
比较创新的地方是考虑到了元路径的内部结构,使用元路径实例编码器(metapath instance encoder)进行了元路径的内部聚合。
一共对比了3种元路径实例编码器:mean, linear, relation rotation
实验效果显示relation rotation的效果最好,因为它考虑了元路径中每两个相邻节点间的关系。但是实验结果显示relation rotation和mean差别不是很大。
需要注意的是,MAGNN还是需要人为定义元路径。GTNs[3]是自动生成元路径,并且在节点分类任务上也超越了HAN,本文的MAGNN没有和GTNs进行对比。
另外同样被WWW 2020接收的HGT[4],也是不需要预先定义元路径,且在节点分类、链接预测任务上也表现出了很好的效果,超越了HAN。不知道HGT和MAGNN相比的话会怎么样呢。
参考文献
[1] Zhiqing Sun, Zhi-Hong Deng, Jian-Yun Nie, and Jian Tang. 2019. RotatE: Knowledge Graph Embedding by Relational Rotation in Complex Space. In ICLR.
[2] Yukuo Cen, Xu Zou, Jianwei Zhang, Hongxia Yang, Jingren Zhou, and Jie Tang. 2019. Representation Learning for Attributed Multiplex Heterogeneous Network. In SIGKDD. 1358–1368.
[3] Seongjun Yun, Minbyul Jeong, Raehyun Kim, Jaewoo Kang, Hyunwoo J.Kim. 2019. Graph Transformer Networks. In NeurIPS.
[4] Ziniu Hu, Yuxiao Dong, Kuansan Wang, Yizhou Sun. 2020. Heterogeneous Graph Transformer. 2020. In WWW.