KDD 2019 | GATNE：一种针对 Multi-Edge 的大规模异构图嵌入模型

传统的图嵌入(graph embedding)方法一般只针对同构的图，但是实际的图往往都是异构的。只包含异构节点的图的嵌入学习已经被广泛研究，例如 metapath2vec[1] 提出了异构的 random walk 和 skip gram。而包含异构边的图的嵌入学习近来开始被大家所关注，比如 MNE[2] 通过引入对于每种 edge type 的 embedding 来处理异构边的情形。在阿里电商场景下，由用户和商品构成的图就是异构的，并且不仅包含异构的节点（用户和商品），而且包含异构的边（用户和商品的多种交互行为，比如点击、购买等）。不仅如此，图中的节点还包含着丰富的属性。本文处理的就是这种包含异构节点和异构边的图的嵌入学习。

根据图结构(同构/异构)以及是否包含节点特征，我们将图分为如下六类：_HO_mogeneous _N_etwork(HON), _A_ttributed _HO_mogeneous _N_etwork(AHON), _HE_terogeneous _N_etwork(HEN), _A_ttributed _HE_terogeneous _N_etwork(AHEN), _M_ultiplex _HE_terogeneous _N_etwork(MHEN), _A_ttributed _M_ultiplex _HE_terogeneous _N_etwork(AMHEN)。

同时我们也在下表中列出了处理各种类型的图的方法(其中GATNE-T/I是我们提出的方法)：

下图是一个带节点属性的异构图的例子。在左侧原始的图中，用户包含了性别、年龄等属性，商品包含了价格、类目等属性。用户与商品之间包含了4种类型的边，分别对应点击、收藏、加入购物车以及购买行为。传统的 graph embedding 算法比如 DeepWalk 的做法会忽略图中边的类型以及节点的特征，然后转换成一个 HON。如果将边的类型考虑进去，那么就得到一个 MHEN，能够取得非常明显的效果。此外，如果将节点的属性也同时考虑进去，那么就利用了原图的所有信息，可以得到最好的效果。

模型

由于有多种类型的边(比如点击、购买)，这里我们考虑给每个节点在每种边类型下都学一个表示。比如我们给用户和商品在点击场景下学一种表示，在购买场景下学一种表示。但是这两种表示之间并不是完全独立的，是通过某种机制互相影响的。我们主要考虑的就是如何来建模不同类型的表示之间相互影响的方式：

模型的大致结构如上图所示。对于GATNE-T(T for transductive)来说，每个节点在每种edge type 下的 embedding 由两个部分组成，分别是 base embedding 和 edge embedding。base embedding 是每个节点在每种 edge type下共享的，而 edge embedding 是通过相邻节点的 edge embedding 计算得到的。具体来说，类似于 GraphSAGE[3]，这里的 edge embedding 的计算方式如下：

其中 i, j 表示节点编号，r 表示某种 edge type，k 表示第 k 层的 edge embedding(1<=k<=K)，aggregator function 可以是 mean aggregator 或者 max-pooling aggregator。我们将第 K 层的 edge embedding 拼起来记为矩阵U：

其中，m 表示 edge type 的数量。由于我们不知道每个节点在每种 edge type 下的表示之间的关系，所以我们通过 self-attention[4] 的机制来建模这种相互关系，并得到每种 edge type 下的表示对于各个 edge type 的权重：

其中是模型需要训练得到的参数，是计算得到的权重向量。最后我们就能得到每个节点i在某种 edge type r 下的向量表示：

由于实际问题中会遇到冷启动等问题，需要给没有在训练集中出现过的节点也求得 embedding。而 transductive model 不具备这种能力。所以我们引入了节点的特征提出了相应的 inductive model，记为 GATNE-I。具体来说，原先在 GATNE-T 中和都是随机初始化的。但是在 GATNE-I，这两个 embedding 都是基于节点的特征，也就是通过节点的特征经过某种变换(比如线性变换或者神经网络等)得到的。那么节点i在某种 edge type r 下的向量表示就可以表达成：

其中表示节点 i 的特征。

接下来介绍模型的训练方式。GATNE-T/I 模型的训练方式基于 meta-path-based random walk 和 heterogeneous skip gram。具体来说，我们预先设定 meta-path schem，，(比如 User-Item-User)，那么 random walk 的转移概率即为：.

其中表示类型为 r 的边集。给定一个节点与其在某个 random walk 上的 context C，我们的目标是最小化如下的负对数似然函数：

其中右侧的每一项的概率通过 heterogeneous softmax function 来计算：

其中 c 表示节点的 context embedding。最后我们通过 heterogeneous negative sampling 来近似负对数似然：

整体的算法流程如下：

实验

我们在3个公开数据集 Amazon、YouTube、Twitter 和阿里数据集（user-item访问、购买、点击、加购关系）进行了实验，验证了我们所提出的模型的有效性，同时也说明了异构边的信息对如何学到更好的 graph embedding 能带来较大的帮助。用到的数据集的规模如下（3个公开数据集从原始数据集中进行了采样）：

如下表所示，在3个公开数据集和阿里小数据集上，我们提出的 GATNE-T/I 取得了最好的效果。Amazon 数据集上由于商品的特征比较弱，所以 GATNE-I 的效果会稍差于GATNE-T；而在阿里数据集上，因为节点的特征非常丰富，所以 GATNE-I 的效果会好于 GATNE-T。YouTube 和 Twitter 数据集不包含节点特征，所以我们把 DeepWalk 跑出来的200维向量作为初始的节点特征。由于 DeepWalk 生成的特征也只利用了图的结构，没有引入额外的信息，所以两种方法 GATNE-T/I 的结果差别不大。

我们实现了3个 baseline(DeepWalk, MVE, MNE)和 GATNE-T/I 的分布式版本，运行在PAI Tensorflow 上，并在阿里大数据集上进行了测试。如下表所示，相比于 baseline 来说，GATNE-I 取得了非常显著的提高。

我们对模型的 convergence 和 scalability 进行了测试。在阿里大数据集上，相比GATNE-T 来说，GATNE-I 能够更快地达到比较好的效果。并且，随着模型所使用的worker 数量的增加，GATNE-T/I 模型的训练时间都能显著降低。

参考文献

[1] Yuxiao Dong, Nitesh V Chawla, and Ananthram Swami. 2017. metapath2vec: Scalable representation learning for heterogeneous networks. In KDD’17. ACM, 135–144.
[2] Hongming Zhang, Liwei Qiu, Lingling Yi, and Yangqiu Song. 2018. Scalable Multiplex Network Embedding. In IJCAI’18. 3082–3088.
[3] Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. In NIPS’17. 1024–1034.
[4] Zhouhan Lin, Minwei Feng, Cicero Nogueira dos Santos, Mo Yu, Bing Xiang, Bowen Zhou, and Yoshua Bengio. 2017. A structured self-attentive sentence embedding. ICLR’17.