论文链接：https://arxiv.org/pdf/1905.01669.pdf
代码链接：https://github.com/THUDM/GATNE
论文来源：KDD2019

摘要

网络嵌入（图嵌入）在真实世界中已经有了非常大规模的应用，然而现存的一些网络嵌入（图嵌入）相关的方法主要还是集中在同质网络的应用场景下，即节点和边的类型都是单一类型的情况下。但是真实世界网络中每个节点的类型都多种，每条边的类型也有多种，而且每一个节点都具有不同且繁多的属性。所以本论文提出了一种在Attributed Multiplex Heterogeneous Network中进行嵌入学习的统一框架，并提供了充分的数学理论分析，还在数据集Amazon, YouTube, Twitter, and Alibaba上进行了大量的实验。实验结果表明，利用此框架学习到的嵌入有惊人的性能提升，F1 scores可提高5.99-28.23%，而且该框架还成功地部署在全球领先的电子商务公司阿里巴巴集团的推荐系统上。对产品推荐进行离线A/B测试的结果进一步证实了该框架在实践中的有效性和效率。

1、引言

作者根据网络拓扑类型（同构和异构）和属性特征（边、节点）将图分为六类，并总结了当今的发展，如下表所示：

可以看到 AMHEN 的研究是最少的。

本篇论文致力于研究 AMHEN 的表示学习，这种网络的特点在于多种类型的节点可能通过多种类型的边进行关联，并且每个节点都具有不同的属性。

这种结构非常常见，比如作者使用的四种数据集中，超过 15% 的节点对会有超过一种类型的边。举个具体的例子，在电商中，用户可能会对商品具有点击、加购、加收藏等多种交互行为。下图展示了一个真实场景下的异构网络：

图的左边用户和商品都分别有多个属性，而且用户和商品之间的连边类型也是多样的，一个用户和一个商品可能有多个类型不同的连边。图的中间部分是将左边的图分别形式化为了：AMHEN(属性多重异质网)、MHEN(多重异质网)和HON(同质网)。右边是，三种方法的实验效果对比。

传统的 Graph Embedding 方法比如 DeepWalk 的做法都是直接忽略图中边的类型以及节点的特征，将真实网络建模为 HON。而如果将边类型考虑进去建模为 MHEN，则会取得非常明显的效果。最后，如果还能够将节点的属性也考虑进去建模为 AMHEN，那么就充分利用到了原图的所有信息，这样便可以得到最好的效果。

除了异构性和多样性外，处理 AMHEN 也面临着多重挑战：

• 多路复用的边（Multiplex Edges）：每个节点对可能含有多种不同的类型边；
• 归纳学习（Inductive）：如何解决冷启动问题；
• 可扩展性（Scalability），如何拓展到大规模网络中。

为了解决这些问题，作者提出了一种通用的多路复用异构网络嵌入学习框架（General Attributed Multiplex HeTerogeneous Network Embedding，GATNE）， 并用于捕获节点丰富的属性信息和来自不同节点类型的多路复用拓扑结构。

2、GATNE模型

本节介绍两种类型的 GATNE 框架，包括直推式学习范式的 GATNE-T 和归纳式学习范式的 GATNE-I。

2.1、GATNE-T模型

我们先从多路复用的异构网络图开始，并介绍 GATNE-T 模型。

GATNE-T 考虑 Base Embedding 和 Edge Embedding（这里的 Edge Embedding 并不是对边进行 Embedding，而是基于 edge type 进行聚合得到 Embedding），如下图紫色边所示。

节点的 Base Embedding 对所有类型的边共享。

第 $k$k 层 $v_i$vi​ 节点的 edge type $r$r 类型的 Edge Embedding 如下所示：$u_{i,r}^{(k)}=aggregator\left(\left\{u_{j,r}^{(k-1)},\forall v_j\in\mathcal{N}_{i,r}\right\}\right)$ui,r(k)​=aggregator({uj,r(k−1)​,∀vj​∈Ni,r​})其中， $\mathcal{N}_{i,r}$Ni,r​为节点 $v_i$vi​基于 edge type $r$r 的邻居； $u_{i,r}^{(0)}$ui,r(0)​是随机初始化的。

聚合函数可以为均值聚合、最大池化聚合等：$u_{i,r}^{(k)}=\sigma\left(\hat{W}^{(k)}\cdot mean\left(\left\{u_{j,r}^{(k-1)},\forall v_j\in \mathcal{N}_{i,r}\right\}\right)\right)$ui,r(k)​=σ(W^(k)⋅mean({uj,r(k−1)​,∀vj​∈Ni,r​}))$u_{i,r}^{(k)}=max\left(\left\{\sigma\left(\hat{W}_{pool}^{(k)}u_{j,r}^{(k-1)}+\hat{b}_{pool}^{(k)}\right),\forall v_j\in\mathcal{N}_{i,r}\right\}\right)$ui,r(k)​=max({σ(W^pool(k)​uj,r(k−1)​+b^pool(k)​),∀vj​∈Ni,r​})使用第 $K$K 层的表示 $u_{i,r}^{(K)}$ui,r(K)​ 作为边$u_{i,r}$ui,r​ 的 Embedding，然后拼接节点 $v_i$vi​ 的所有 Edge Embedding：$U_i=\left(u_{i,1},u_{i,2},\cdots,u_{i,m}\right)$Ui​=(ui,1​,ui,2​,⋯,ui,m​)

然后利用 Self-Attention 来计算各边的权重：$a_{i,r}=softmax\left(w_r^Ttanh(W_rU_i)\right)^T$ai,r​=softmax(wrT​tanh(Wr​Ui​))T

其中，$w_r$wr​ 和 $W_r$Wr​ 为可训练参数。

对于 edge type $r$r 来说，节点 $v_i$vi​ 的 Embedding 为：$v_{i,r}=b_i+\alpha_rM_r^TU_ia_{i,r}$vi,r​=bi​+αr​MrT​Ui​ai,r​

其中，$b_i$bi​ 为节点$v_i$vi​ 的 base embedding，$\alpha_r$αr​ 为超参用于控制 edge embedding 的重要程度，$M_r$Mr​ 为可训练的转移矩阵。

后面作者对比了 GATNE-T 和 MNE（Scalable Multiplex Network Embedding），并证明 GATNE-T 是 MNE 的一种泛化形式。

直推式模型 GATNE-T 在聚合的时候按照边的类型进行了分类，生成节点$v_i$vi​ 对于 edge type $r$r 的 Embedding。而在计算点 $v_{i,r}$vi,r​ 时，使用了注意力机制为不同类型的边分配了不同的注意力。

但 GATNE-T 只是聚合了节点的邻居信息，没有应用到节点的属性信息。且由上面的公式可知， 都是通过聚合邻居得到的，训练的参数都是一个整体的矩阵。所以，GATNE-T 不能单独为新加入的节点生成 Embedding，也就是不能使用训练集训练好的参数用于生成（训练时不可见的）测试集的节点嵌入表示，必须重新训练。即 GATNE-T 只能进行直推式学习（transductive learning），不能进行归纳式学习（inductive learning）。

2.2、GATNE-I

为了解决 GATNE-T 的局限，作者提出了 GATNE-I 模型。该模型如下图橘色边所示：

在 GATNE-T 中，Base Embedding 和 Edge Embedding 都是随机初始化的，但是在 GATNE-I 中，这两个 Embedding 都是基于节点的特征，如上图中间部分，有两条橘色虚线从 Node Attributes 指向上下两方的 Embedding。

首先，定义 Base Embedding：$b_i=h_z(x_i)$bi​=hz​(xi​)

其中， $x_i$xi​为节点 $v_i$vi​ 的属性， $h_z$hz​为转换函数，$z=\phi(i)$z=ϕ(i) 映射节点$v_i$vi​ 的边类型。

不同类型的节点其维度可能也不同，所以转换函数会有着不同的形式。

然后，定义 Edge Embedding：$u_{i,r}^{(0)}=g_{z,r}(x_i)$ui,r(0)​=gz,r​(xi​)

其中， $g_{z,r}$gz,r​也是一个转换函数，将属性特征转换为节点 $v_i$vi​ 关于 $r$r 类型的 Edge Embedding。

于是，节点 $v_i$vi​在 edge type $r$r 下的向量表示为：$v_{i,r}=h_z(x_i)+\alpha_rM_r^TU_ia_{i,r}+\beta_rD_z^Tx_i$vi,r​=hz​(xi​)+αr​MrT​Ui​ai,r​+βr​DzT​xi​

其中，$\alpha_r,\beta_r$αr​,βr​ 为系数，$D_z$Dz​ 是针对属性的特征变换矩阵。

所以 GATNE-T 和 GATNE-I 的主要区别在于 Embedding 的初始化过程。

这边可能会有一些疑问：「为什么初始化的方式不同会导致两种学习范式？」

• 在 GATNE-T 中， 是基于网络结构的，为每个节点直接训练，所以无法处理训练中未出现过的节点；
• 而在 GATNE-I 中，训练的是两个转换函数 $h_z,g_{z,r}$hz​,gz,r​，将原始特征 $x_i$xi​转换为 $b_i,u_{i,r}^{(0)}$bi​,ui,r(0)​，并非为每个节点直接训练，所以这便可以处理未出现的节点，只要这个节点有特征即可。

2.3、模型优化

我们再来看一下模型的训练方式。

GATNE 模型的训练方式是基于 meta-path 的随机游走和 heterogeneous skip-gram。

具体来说，我们先给一个预定的 meta-path scheme，如 user-item-user 等，然后给出随机游走的概率矩阵：$p(v_j|v_i,\Tau)=\left\{ \begin{array}{rcl} \frac{1}{|\mathcal{N}_{i,r}\cap\mathcal{V}_{t+1}|} & & {(v_i,v_j)\in \varepsilon_r,v_j\in\mathcal{V}_{t+1}}\\ 0 & & {(v_i,v_j)\in \varepsilon_r,v_j\notin\mathcal{V}_{t+1}}\\ 0 & & {(v_i,v_j)\notin\varepsilon_r} \end{array} \right.$p(vj​∣vi​,T)=⎩⎨⎧​∣Ni,r​∩Vt+1​∣1​00​​(vi​,vj​)∈εr​,vj​∈Vt+1​(vi​,vj​)∈εr​,vj​∈/​Vt+1​(vi​,vj​)∈/​εr​​

其中，$v_i\in\mathcal{V}_t$vi​∈Vt​，$\mathcal{N}_{i,r}$Ni,r​ 为节点 $v_i$vi​ 基于 edgee type $r$r 的邻居。

对于给定节点 $v_i$vi​ 和它的上下文 C，我么的目标是最小化负对数似然函数：$-\log P_{\theta}(\{v_j|v_j\in C\}|v_i)=\sum_{v_j\in C}-\log P_{\theta}(v_j|v_i)$−logPθ​({vj​∣vj​∈C}∣vi​)=vj​∈C∑​−logPθ​(vj​∣vi​)

在给定 $v_i$vi​ 时，$v_j$vj​ 的概率为：$P_{\theta}(v_j|v_i)=\frac{exp(c_j^T\cdot v_{i,r})}{\sum_{k\in\mathcal{V}_t} exp(c_k^T\cdot v_{i,r})}$Pθ​(vj​∣vi​)=∑k∈Vt​​exp(ckT​⋅vi,r​)exp(cjT​⋅vi,r​)​

其中，$c_k$ck​ 表示节点$v_k$vk​ 的上下文 Embedding。

最后得到我们的目标函数为：$E=-\log\sigma(c_j^T\cdot v_{i,r})-\sum_{l=1}^L\mathbb{E}_{v_k\sim P_t(v)}[\log\sigma(-c_k^T\cdot v_{i,r})]$E=−logσ(cjT​⋅vi,r​)−l=1∑L​Evk​∼Pt​(v)​[logσ(−ckT​⋅vi,r​)]

其中， $\sigma(x)$σ(x)为 sigmoid 函数，$L$L 为负采样的数量。

整体的算法流程为：

3、实验

实验主要采用链接预测的方式进行比较本论文提出的方法和之前一个state-of-the-art方法进行对比，以及参数的敏感性、收敛性、以及其规模，最后将介绍此方法运用到阿里巴巴推荐系统上的测试结果。

首先给出数据集

• Amazon：在这个数据集中，我们只使用电子产品类别的产品元数据，包括产品属性和产品之间的共同购买链接，产品属性包括价格、销售等级、品牌和类别

• YouTuBe：YouTube数据集是一个多路双向网络数据集，由15088个YouTube用户之间的五种类型的交互组成，边缘的类型包括用户之间的联系人、共享朋友、共享订阅、共享订阅者和共享最喜欢的视频

• Twitter：推特数据集是关于2012年7月1日至7日发现希格斯玻色子的推特，它由450,000多个Twitter用户之间的四个方向关系组成，这些关系是Twitter用户之间的关系、回复、提及和友谊/追随者关系。

• Alibaba：阿里巴巴数据集由四种类型的交互组成，包括单击、添加到首选项、添加到购物车，以及用户和项目两种类型节点之间的转换。抽样的阿里巴巴数据集被表示为阿里巴巴-s，还在阿里巴巴的分布式云平台上提供了整个数据集的评估，完整的数据集被表示为阿里巴巴。

不同数据集下各模型的表现如下图所示，Amazon 的数据集节点的特征太少了，所以 GATNE-I 的效果略微逊色。

阿里巴巴数据集的表现如下图所示，阿里巴巴的数据集特征丰富，所以 GATNE-I 的效果很好。

收敛速度和可扩展性：

参数敏感性：

4、结论

本文首先基于网络拓扑类型和属性特征将图分为六大类，并重点关注目前研究较少的 MHEN 和 AMHEN 两种网络架构，分别提出了 GATNE-T 和 GATNE-I 两种模型。GATNE-T 在 MHEN 网络中建模并考虑 Base Embedding 和 Edge Embedding，Edge Embedding 利用注意力机制聚合邻居信息，并综合 Base Embedding 得到最终的 Node Embedding，GATNE-I 在 GATNE-T 的基础上考虑 Attribute Embedding 并弥补了 GATNE-T 无法泛化到未知节点的缺点。GATNE 模型在诸多工业界数据集中都取得不错的成绩，并在阿里推荐系统中成功落地应用。