「工业落地」阿里异构图表示学习：19KDD GATNE

19KDD Representation Learning for Attributed Multiplex Heterogeneous Network

背景介绍

• 文章核心思想？

本文针对Attributed Multiplex Heterogeneous网络，即边和节点有有多种类型，且节点有多种特征的网络，提出GATNE模型，学习每个节点在不同类型边下的embedding表示，模型同时支持直推式学习和归纳式学习，利用四个数据集进行实验，表现良好。

• Attributed Multiplex Heterogeneous Network挑战

1. 多种类型的边：每个节点对有多种关系，比如在电子商务领域中，用户和item之间，可以点击、购买、添加到购物车等，需要借助多种关系来学习embedding

2. 部分观察：真实网络中往往不能看到全局信息，长尾用户只和部分产品有交互作用，现有大部分模型中都只关注直推式学习，不能解决长尾或者冷启动问题

3. 大规模：真实网络往往有亿级节点和边，需要设计模型处理大规模数据

• 文章贡献

1. 定义了多重异构特征网络embedding

2. 同时支持直推式和归纳式学习embedding，并提供了理论证明

3. 模型高效，适合处理大规模数据

算法原理

根据不同节点类型（单一节点、多种节点）、不同边类型（单一边、多种边）、节点性质（有性质、无性质），可以分成如下6种网络类型，不同网络有不同的建模方法：

本文关注Attributed Multiplex Heterogeneous 网络：

• Attributed：考虑节点性质，如用户性别、年龄、购买力等

• Multiplex：多重边，节点之间可能有多种关系，比如说两个用户之间可能为好友、同学、交易关系等；用户和item之间可以浏览、点击、添加到购物车、购买等

• Heterogeneous：异构，节点和边有多种类型，节点类型+边类型>2

下图为Attributed Multiplex heterogeneous network，左边一部分是具有节点性质的用户，用户特征包括性别、年龄、位置等，item特征包括价格、品牌等，边特调整包括点击、添加到喜欢等。中间部分表示三种方法建模：AMHEN（Attributed Multiplex Heterogeneous Network)，MHEM(Multiplex Heterogeneous Network)，HON(Homogeneous Network)，右图是建模结果，可以看出，AMHEN（考虑多种类型，节点性质的异构图网络），优于MHEN（不考虑节点性质的异构网络），优于HON同构网络。

本文提出General Attributed Multiplex Heterogeneous Network Embedding(GATNE)，希望每个节点在不同类型边中有不同的表示，比如说用户A在点击商品的场景下学习一种向量表示，在购买商品的场景下学习另一种向量表示，而不同场景之间并不完全独立，希望用base embedding来当作不同类型关系传递信息的桥梁，我们综合base embedding与每一类型边的edge embedding来进行建模，在直推式学习(Transductive)背景下，提出GATNE-T模型，在归纳式学习(Inductive)背景下，考虑节点特征，提出GATNE-I模型。

模型结构如下图所示，网络结构利用两部分向量Base Embedding和Edge embedding表示，其中Base Embedding为共享向量，出现在每一种边类型中；Edge embedding在每一种边类型中不同；GATNE-T仅仅利用了网络结构信息，GATNE-I同时考虑了网络结构信息和节点性质。

Transductive Model: GATNE-T

GATNE-T的核心思想就是聚合不同边类型的邻居到当前节点，然后对每一种边类型的节点都生成不同的向量表示，模型可分为如下四步：

• Step1：类似于Graphsage对邻居聚合的思想，节点  对边类型为r的第k阶邻居进行聚合，得到edge embedding  ：

其中  是节点  边类型为r的邻居。节点  类型为r的边 对应的向量 随机初始化。聚合函数可以为均值聚合：  ；最大池化聚合： 

• Step2：把第k阶邻居，不同类型的边节点，对应的edge embedding进行concat聚合： 

• Step3：考虑到不同类型边的影响不同，利用注意力机制计算权重：  ，其中  为要学习的参数

• Step4：综合base embedding和edge embedding得到最终节点  边类型r的节点向量表示：  ，其中  为节点i的base embedding，  为超参数控制edge embedding的重要程度，  是要学习的参数

Inductive Model：GATNE-I

上文的GATNE-T模型不能处理未见过的数据，为了解决这个问题，提出GATNE-I模型，考虑节点初始的特征。对比GATNE-T模型  ，GATNE-I模型主要从以下三个角度进行调整：

• base embedding：GATNE-T中base embedding  直接训练，而此处考虑利用节点初始特征生成base embedding，即  ，其中  为节点类型为z的转化函数，比如说多层感知机。

• 初始edge embedding：GATNE-T中edge embedding随机初始化，而此处初始edge embedding同样为节点特征的函数，即  ，其中  为节点类型为z，边类型为r的转化函数

• 最终节点  边类型为r的embedding   ：添加节点特征，  ，其中  是系数，  是类型为z的节点  的特征转化矩阵，均为要学习的参数

Model Optimization

我们利用基于元路径meta-path-based的随机游走方法和skip-gram来学习模型参数。给定第r种边关系而的网络  ,和长度为l的元路径  ，则在第t步转移概率为：

即只有当边属于类型r，且节点类型符合元路径中的节点类型，才有可能被采样到。

假设长度为l边类型为r的随机游走路径  ，节点  的背景向量为  ，其中c为采样窗口大小，即背景向量为随机游走路径中当前节点左右长度c范围内的节点。

因此，给定节点  和随机游走路径背景C，目标函数为：

最终，利用异构负采样来构建目标函数：

其中L为负采样个数。算法原理如图所示：

• 时间复杂度：  ，其中n为节点个数，m为边个数，d为向量维度，L为负采样个数

• 空间复杂度：  ，其中s为edge embedding维度

参考文献：

Cen Y , Zou X , Zhang J , et al. Representation Learning for Attributed Multiplex Heterogeneous Network[J]. 2019.