阿里电商场景下的大规模异构网络表示学习
根据图结构(同构/异构)以及是否包含节点特征，我们将图分为如下六类：HON, AHON, HEN, AHEN, MHEN, 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拼起来记为矩阵Ui：
其中m表示edge type的数量。由于我们不知道每个节点在每种edge type下的表示之间的关系，所以我们通过self-attention[4]的机制来建模这种相互关系，并得到每种edge type下的表示对于各个edge type的权重：
其中wr, Wr是模型需要训练得到的参数，ai,r是计算得到的权重向量。最后我们就能得到每个节点i在某种edge type r下的向量表示：
由于实际问题中会遇到冷启动等问题，需要给没有在训练集中出现过的节点也求得embedding。而transductive model不具备这种能力。所以我们引入了节点的特征提出了相应的inductive model，记为GATNE-I。具体来说，原先在GATNE-T中bi和ui,r(0)都是随机初始化的。但是在GATNE-I，这两个embedding都是基于节点的特征，也就是通过节点的特征经过某种变换(比如线性变换或者神经网络等)得到的。那么节点i在某种edge type r下的向量表示就可以表达成：
其中xi表示节点i的特征。
接下来介绍模型的训练方式。GATNE-T/I模型的训练方式基于meta-path-based random walk和heterogeneous skip gram。具体来说，我们预先设定meta-path scheme (比如User-Item-User)，那么random walk的转移概率即为：
其中Er表示类型为r的边集。给定一个节点与其在某个random walk上的context C，我们的目标是最小化如下的负对数似然函数：
其中右侧的每一项的概率通过heterogeneous softmax function来计算：
其中c表示节点的context embedding。最后我们通过heterogeneous negative sampling来近似负对数似然：
整体的算法流程如下：
我们在3个公开数据集Amazon、YouTube、Twitter和阿里数据集上进行了实验，验证了我们所提出的模型的有效性，同时也说明了异构边的信息对如何学到更好的graph embedding能带来较大的帮助。用到的数据集的规模如下（数据集从原始数据集中进行了采样）：
如下表所示，在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.