KDD 2019：Representation Learning for Attributed Multiplex Heterogeneous Network

原文链接：Representation Learning for Attributed Multiplex Heterogeneous Network (arxiv.org)

摘要

Network embedding(or graph embedding) has been widely used in many real-world applications. However, existing methods mainly focus on networks with single-typed nodes/edges and cannot scale well to handle large networks. Many real-world networks consist of billions of nodes and edges of multiple types, and each node is associated with different attributes. In this paper, we formalize the problem of embedding learning for the Attributed Multiplex Heterogeneous Network and propose a unified framework to ad-dress this problem. The framework supports both transductive and inductive learning. We also give the theoretical analysis of the pro-posed framework, showing its connection with previous works and proving its better expressiveness. We conduct systematical eval-uations for the proposed framework on four different genres of challenging datasets: Amazon, YouTube, Twitter, and Alibaba1. Ex-perimental results demonstrate that with the learned embeddings from the proposed framework, we can achieve statistically signif-icant improvements(e.g., 5.99-28.23% lift by F1 scores; p < 0.01, t−test) over previous state-of-the-art methods for link prediction. The framework has also been successfully deployed on the recom-mendation system of a worldwide leading e-commerce company, Alibaba Group. Results of the offline A/B tests on product recom-mendation further confirm the effectiveness and efficiency of the framework in practice.

预备知识

在阅读这篇文章之前，我们先来看一下什么是图嵌入表示学习

参考资料：随机游走的艺术-图嵌入表示学习【斯坦福CS224W图机器学习】_哔哩哔哩_bilibili

嵌入（embedding）

首先我们给出机器学习中嵌入的定义

定义

把离散的、分类型的数据投影到连续向量表达的过程

在处理复杂图形数据时，计算机通常难以直接理解其中的结构和关系。为了使计算机能够有效处理这些信息，我们需要将图中的节点和边转化为可计算的向量形式，这一过程就是我们常说的“嵌入”(Embedding)。通过嵌入技术，每个节点可以被表示为一个向量，这个向量能够捕捉到节点自身的属性以及它与其他节点之间的关系。同样地，边也可以被嵌入到向量空间中，用来表示不同节点之间的连接强度或类型。

图表示学习

自然语言处理的许多概念和图表示学习有许多相似性，在学习中，我们可以类比学习

图节点嵌入

节点u通过一个映射函数f从图空间到d维向量空间。这个过程将节点映射为d维向量，使得向量维度远小于节点数，如下图所示。 向量化后的特征具有以下几个特点：

• 低维：维度远小于节点数。
• 连续：每个元素都是实数（有大有小，有零有整）
• 稠密：每个元素都不为零。

还记得之前在图节点级任务中老Hi教练和Jone管理员得例子吗，我们将派系扩充至四种，通过聚类方法（无监督学习）得到不同得节点颜色，节点的颜色代表了不同的派系，节点上的数字标识了各个成员。

我们使用一种随机游走的算法，它可以将图中的每个节点编码为一个D维向量（embedding），在二维嵌入中，节点的位置隐式包含了图中的社群结构、连通性等信息。经过图节点嵌入后的节点向量可以用作机器学习模型的输入，以便于执行诸如节点分类、预测等任务，如下图所示。

通过比较两张图，我们可以看到原图中相邻的节点在二维嵌入后仍然相对靠近。这表明该算法成功地将图中的结构信息保留在了低维空间中。也就是说，尽管节点被投影到了二维平面上，但它们之间的相互联系并没有被破坏。

编码器（Encoder）

编码器是一个函数映射，它将网络中的每个节点映射到一个D维度的向量空间。这个过程是通过随机游走生成节点序列，然后使用skip-gram模型训练得到的。

• 随机游走：在图上进行的随机移动。在每次移动时，随机游走者会从当前所在的节点随机选择一个相邻的节点作为下一个访问的目标。这个过程可以重复多次，会形成一条由访问过的节点组成的路径。这条路径被称为随机游走序列，如下图所示

• Skip-gram模型：最大化一个节点（中心点）和它周围的节点（与中心点相邻的节点）同时出现的概率。

在定义好编码器后，我们引入一个节点相似度函数（Node Similarity Function）用于量化网络中两个节点之间的相似程度，在向量空间中计算两个节点的相似度应该尽可能地接近它们在网络中的实际相似度。

$$\mathrm{similarity}(u,v)\approx {\mathbf{z}}_v^{\mathrm{T}}{\mathbf{z}}_u$$

解码器（Decoder）

解码器的作用是将嵌入空间中的节点向量转换回原始网络中的相似度得分。最常见的做法是计算两个节点向量之间的余弦相似度。余弦相似度衡量的是两个向量之间的角度，值范围从-1到1，其中1表示完全相同，-1表示完全相反，0表示正交（不相关）。

机器学习方法

• 归纳式学习（Inductive Learning）：我们通常所指的监督学习。它的核心思想是从特定的训练数据中学习出一般性的规则或模型，然后将这个模型应用到新的、未见过的数据上。这种方法强调模型的泛化能力，即模型能够对新数据做出准确的预测。

• 直推式学习（Transductive Learning）：首先观察全部数据，包括了训练和测试数据，在训练过程中，直推式学习不仅使用已标记的训练数据，还会直接利用未标记的测试数据来改进模型的预测性能。值得注意的是：直推式学习不会建立一个预测模型，如果一个新数据节点加入测试数据集，需要重新训练模型，然后再预测标签。

引言

动机与挑战

图表示学习近年来在许多下游任务（节点分类、链接预测和社区检测）方面取得了显著进展，目前的许多方法如DeepWalk、node2vec仅针对具有单一类型节点和边的同质网络设计。然而，现实世界的应用程序，例如电子商务，远比这复杂得多，不仅包含多类型的节点和边，而且还包含丰富的属性集。由此作者提出了一种名为带属性的多层异构网络（Attribute Multi-layer Heterogeneous Network, AMHEN）的网络模型，这种模型的不同类型的节点可能与多种不同类型的边连接，并且每个节点都与一组不同的属性相关联。 虽然这种模型较为复杂，但这种情况在许多在线应用程序中很常见。

如上图所示：

• 在电子商务系统中，用户可以与商品有多种交互方式，如点击、转化、加入购物车、加入收藏夹等。显然，“用户”和“物品”有着固有的不同属性，不应被同等对待。
• 不同的用户 - 商品交互意味着不同的偏好，应得到不同的对待。否则，系统无法准确地捕捉到用户的行为模式和偏好。

由于AMHEN的复杂性，在处理时带来了一些挑战

• 每个节点对可能有多种不同的关系类型，如何从不同关系中进行有效聚合，并学习统一的嵌入表示
• 在网络数据集中，某些节点或边可能只有一小部分被观测到，由于数据的稀疏导致无法处理长尾或冷启动问题。

tips

长尾：一般指客户可能只与少数产品有过交互记录，导致这些客户的购买行为数据不足以全面反映其偏好或行为模式。

冷启动问题：当新用户首次使用某个平台时，由于缺乏历史行为数据，推荐系统难以为其提供个性化的推荐。

贡献

为解决上述挑战，作者提出了一种新颖的方法来捕获丰富的属性信息，并利用来自不同节点类型的多层拓扑结构，即通用归属多层异构网络嵌入（General Attributed Multiplex HeTerogeneous Network Embedding，GATNE）。该模型已应用于阿里的推荐引擎。

主要方法

问题定义

下表是对本文中一些符号的定义

• 异质网络（Heterogeneous Network）

一个异质网络是一个由节点集合 $V$ 和边集合 $E$ 组成的网络 $G=(V,E)$，并且它还关联着一个节点类型映射函数 $\varphi :V\to O$ 和一个边类型映射函数 $\psi :E\to R$。其中，$O$ 表示所有节点类型的集合，而 $R$ 则表示所有边类型的集合。

每个节点 $v\in V$ 都属于特定的一个节点类型。同样地，每条边 $e\in E$ 被归类到一种特定的边类型中。

如果 $|O|+|R|>2$，那么这个网络被称为异质网络；否则，它就是同质网络。简单来说，拥有的节点和边的类型大于2即为异质网络。而同质网络只有一种类型的节点和边。

值得注意的是：在异质网络中，由于可能存在多个类型的不同边连接同一对节点，所以不能再用简单的 $e_{ij}$ 来表示一条边。在这种情况下，需要使用 $e_{ij}^{(r)}$ 来表示一条边，其中 $r$ 对应于这条边的具体类型（比如外卖平台中的取货边和送货边）。

• 属性网络（Attributed Network）

属性网络是一个赋予了特征表示的网络，即 $G=(V,E,A)$。每个节点 $v_i\in V$ 都与某种类型的特征向量相关联。$A=\{x_i|v_i\in V\}$ 是所有节点的特征集，其中 $x_i$ 是节点 $v_i$ 相关的节点特征。这些特征可以用来描述节点的各种属性，如年龄、性别、职业等。

• 带有属性的多层异质网络（AMHEN）

将AMHEN定义为一张图 $G=(V,E,A)$，其中 $E=\bigcup _{r\in R}{E}_r$，$E_r$ 包含所有具有边缘类型 r 的边，且 $|R|>1$。把针对每种边缘类型的网络分离出来，记作 $G_r=(V,E_r,A)$。

• AMHEN Embedding

给定一张图$G=(V,E,A)$，目标是为每种边缘类型$r$提供一个统一的低维空间表示形式。具体来说，目标是为每种边缘类型$r$找到一个函数 $f_r:V\to {\mathbb{R}}^d$，其中$d\ll |V|$。

GATNE模型

Transductive Model：GANTE-T

GATNE-T将特定节点$v_i$在每种边类型$r$上的整体嵌入分解为两部分：基础嵌入（Base Embedding）和边嵌入（Edge Embedding），如上图所示。

Base Embedding

将每个节点都用一个基础的向量表示，用于描述其特征。

Edge Embedding

在边嵌入过程中，每个节点$v_i$在每种边缘类型$r$上都有一个对应的边缘嵌入 $u_{i,r}$，并且这些嵌入会在多个层级上进行迭代更新。点$v_i$在边缘类型$r$上的第$K$级边嵌入为$u_{i,r}^{(k)}\in {\mathbb{R}}^s$，其中$s$是嵌入维度，$K$是网络中的层数。这里的“层数”$K$表示了从节点$v_i$到其邻居节点的跳数。例如：

边嵌入的名字是Edge Embedding，但并不是对边的Embedding，而是对节点$u_{i,r}^{(k)}$使用$aggregator$进行聚合操作，该函数接收所有邻居$N_{i,r}$的前一层的边嵌入作为输入，然后计算出当前层的边嵌入。

• $N_{i,r}$ 表示节点$v_i$在边缘类型$r$上的邻居集合。换句话说，它是所有与节点$v_i$直接连接的其他节点的集合。

公式如下：

$${\mathbf{u}}_{i,\tau }^{(k)}=aggregator\left(\{{\mathbf{u}}_{j,\tau }^{(k-1)},\mathrm{\forall }{v}_j\in {\mathcal{N}}_{i,\tau }\}\right)$$

嵌入过程在一个或多层中重复执行，每次更新都会考虑更多的邻居节点及其嵌入。这样做的目的是让节点的边缘嵌入能够逐渐捕获到更广泛的上下文信息，经过多次迭代后，每个节点$v_i$ 在每种边缘类型$r$上的最终边缘嵌入$u_{i,r}^{(k)}$将作为模型的输出

对于每个节点$v_i$和每种边缘类型$r$，初始边缘嵌入$u_{i,r}^{(0)}$是随机初始化的。模型开始时对每个节点和边缘类型的嵌入都是未知的，它们的值是从随机分布中采样的。

作者还提到了两种可能的聚合函数：

• 均值聚合器：将邻居节点的前一层嵌入取平均值，然后通过线性变换和激活函数$\sigma$来得到新的边缘嵌入。公式如下所示：

  $$u_{i,r}^{(k)}=\sigma ({\hat{W}}^{(k)}\cdot mean(u_{j,r}^{(k-1)},\mathrm{\forall }{v}_j\in N_{i,r}))$$

  其中，${\hat{W}}^{(k)}$是权重矩阵，$mean$函数计算邻居节点的前一层嵌入的均值$\sigma$是激活函数。

• 最大池化聚合器：作者还提供了另一种替代方案，即最大池化聚合器。在这种情况下，边缘嵌入是通过将邻居节点的前一层嵌入与权重矩阵 ${\hat{W}}_{pool}^{(k)}$相乘，再加上偏置项 $b_{pool}^{(k)}$，然后求出结果的最大值来获得的。具体公式如下：

  $$u_{i,r}^{(k)}=max(\{\sigma ({\hat{W}}_{pool}^{(k)}{u}_{j,r}^{(k-1)}+b_{pool}^{(k)}),\mathrm{\forall }{v}_j\in N_{i,r}\})$$

自注意力机制（self-attention mechanism）

不同边类型对节点的影响不同，重要程度实际上也是不同的，由此作者引入了自注意力机制来计算不同边类型的权重

作者首先使用自注意力机制来计算了线性组合系数$a_{i,r}$，具体公式如下：

$${\mathbf{a}}_{i,r}=\mathrm{softmax}{({\mathbf{w}}_r^T\tanh \left({\mathbf{W}}_r{\mathbf{U}}_i\right))}^T$$

该公式将可训练的参数 $w_r$ 和 $W_r$ ，以及节点 $v_i$ 在边缘类型 $r$ 上的所有邻居节点 $v_j$ 的嵌入向量组成的矩阵 $U_i$作为输入 。

接下来结合节点$v_i$的基础嵌入$b_i$和边类型$r$的邻居节点嵌入，形成节点 $v_i$的最终嵌入$v_{i,r}$,具体公式如下：

$${\mathbf{v}}_{i,r}={\mathbf{b}}_i+{\alpha }_r{\mathbf{M}}_r^T{\mathbf{U}}_i{\mathbf{a}}_{i,r}$$

最终得到的 $v_{i,r}$ 是节点 $v_i$ 在边缘类型 $r$ 上的综合嵌入，它既考虑了节点自身的特征（基础嵌入），又考虑了邻居节点的特征 (边缘嵌入)。

Inductive Model: GATNE-I

GATNE-T 是一个 transductive model。它只是聚合了节点的邻居信息，没有应用到节点的属性信息。由上面的公式可知， ${\mathrm{u}}_{\mathrm{i},\mathrm{r}}$ 都是通过聚合邻居得到的，训练的参数是一个整体的矩阵。所以，GATNE-T不能单独为新加入的节点生成嵌入表示，也就是不能使用训练集训练好的参数用于生成(训练时不可见的)测试集的节点嵌入表示，必须重新训练。

这一点对于在线网络是十分致命的，例如一个外卖平台作为节点的商家，骑手和顾客是不断更新的。如果不能加入新的节点，那这个模型基本是含无意义的。

为了应对这一挑战，作者扩展了 GATNE-T，将其应用到Inductive Model中，创建了一个新的模型名为 GATNE-I。这个新模型能够处理部分观测到的网络数据，也就是所谓的 semi-supervised learning 或 inductive learning。主要改变在以下两个方面

• 节点和边的初始嵌入：在 GATNE-I 中，作者将节点 $v_i$ 的基础嵌入 $b_i$ 和边 $e_{ij}$ 的初始嵌入 $u_{ij}$ 设置为可参数化的函数。

$$\begin{gathered} b_i=h_z(x_i) \\ {\mathbf{u}}_{i,r}^{(0)}={\mathrm{g}}_{z,r}\left({\mathbf{x}}_i\right) \end{gathered}$$

节点 $v_i$ 的基础嵌入 $b_i$ 是通过一个变换函数 $h_z$ 来计算的，其中 $z$ 是节点 $v_i$ 的类型。同样，边 $e_{ij}$ 的初始嵌入 $u_{ij}$ 也是通过一个变换函数 $g_{z,r}$ 来计算的，其中 $z$ 是节点 $v_i$ 的类型， $r$ 是边的类型。

• 额外的属性项：除了上述的基础嵌入和边的初始嵌入外，GATNE-I 还添加了一个额外的属性项到节点 $v_i$ 的最终嵌入中。

$${\mathbf{v}}_{i,r}={\mathbf{h}}_z\left({\mathbf{x}}_i\right)+{\alpha }_r{\mathbf{M}}_r^T{\mathbf{U}}_i{\mathbf{a}}_{i,r}+{\beta }_r{\mathbf{D}}_z^T{\mathbf{x}}_i$$

这个额外的属性项是由节点 $v_i$ 的属性 $x_i$ 经过一个变换函数 $D_z$ 和一个系数 ${\beta }_r$ 得到的。这一项的设计使得模型能够利用节点的原始属性信息来增强其表示能力。

比较

直推式模型和归纳式模型的区别在于：基类向量 $b_i$ 和初始边嵌入 $u_{i,r}^{(0)}$ 的生成方式。

• 在Transductive Model中，$b_i$和 $u_{i,r}^{(0)}$是基于网络结构，为每个节点直接训练的。所以，无法处理训练中未出现过的节点。
• 在归纳式模型中，训练的是转换函数 $h_2$ 和 $g_{z,r}$ ，将原始特征 ${\mathrm{x}}_1$ 转换为 $b_1$ 和 $u_{i,r}^{(0)}$ 。并非为每个节点直接训练 $b_1$ 和 $u_{i,r}^{(0)}$ 。这就可以处理训练中未出现的节点，只要这个节点有特征$x$ 。

tips

归纳式模型之所以可以处理训练中未出现过的节点，是因为它并不是为每个节点直接训练 $b_1$ 和 $u_{i,r}^{(0)}$，而是训练节点特征 ${\mathrm{x}}_1$ 的转换函数： $h_2$ 和 $g_{z,r}$ 。也就是说，为新加入的节点生成嵌入表示时，用到了节点的属性特征信息 $x_i$ ，生成的初始边嵌入，聚合的也是邻居节点的属性特征信息。

模型优化

之前讨论了GATNE两种类型的模型结构，作者接下来介绍了如何学习这两种模型

这两种模型都是基于元路径(meta-path-based)的随机游走生成节点序列，然后输入skip-gram模型，生成嵌入表示。

• 元路径随机游走：元路径是一个节点类型的序列，例如外卖任务 (商家1-->商家2-->商家3），通过遵循元路径，随机游走可以捕捉到不同节点类型之间的关系。

• 转移概率：给定一个元路径 $\mathcal{T}:V_1\to V_2\to \cdots V_l$，在步长 t 处的转移概率定义如下：

$$p(v_j\mid v_i,\mathcal{T})=\{\begin{array}{cl}\frac{1}{|{\mathcal{N}}_{i,r}\cap {\mathcal{V}}_{t+1}|}& (v_i,v_j)\in {\mathcal{E}}_r,v_j\in {\mathcal{V}}_{t+1}\\ 0& (v_i,v_j)\in {\mathcal{E}}_r,v_j\notin {\mathcal{V}}_{t+1}\\ 0& (v_i,v_j)\notin {\mathcal{E}}_r\end{array}$$

在这个公式中:

• $N_{i,r}$ 表示当前节点 $v_i$ 在元路径 $T$ 中的邻居集合。

• $V_{t+1}$ 表示在时间步 $t+1$ 可能到达的所有节点集合。

• $(v_i,v_j)\in E_r$ 表示存在一条沿着元路径 $T$ 的边连接节点 $v_i$ 到 $v_j$ 。

• $p(v_j\mid v_i,T)$ 是条件概率，表示在给定当前节点 $v_i$ 和元路径 $T$ 的条件下，下一个节点 $v_j$ 出现的概率。

如果节点 $v_j$ 是当前节点 $v_i$ 在元路径 $T$ 下的邻居，并且 $v_j$ 属于下一时间步可能到达的所有节点集合 $V_{t+1}$ ，则概率为 $\frac{1}{\mid N_{i,r}}$ ，这意味着所有符合条件的邻居都有相等的机会成为下一个节点。

Loss function

作者首先给出了一个负对数似然性的形式的目标函数，它表示了模型在给定节点 $v_i$ 的上下文 $C$ 下，预测正确节点 $v_j$ 的概率。这个目标函数的目的是最大化模型预测正确的概率，即 $P(v_j\mid v_i)$ 。

$$-\log P_{\theta }(\{v_j\mid v_j\in C\}\mid v_i)=\sum _{v_j\in C}-\log P_{\theta }(v_j\mid v_i)$$

接着，我们使用概率分布来计算 $P_{\theta }(v_j\mid v_i)$ :

$$P_{\theta }(v_j\mid 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})}$$

为了加快训练速度，我们使用了负采样技术来近似目标函数。负采样损失函数是通过对正样本和负样本的期望值求和来近似的。

$$E=-\log \sigma ({\mathbf{c}}_j^T\cdot {\mathbf{v}}_{i,r})-\sum _{l=1}^L{\mathbb{E}}_{v_k\sim P_t(v)}[\log \sigma (-{\mathbf{c}}_k^T\cdot {\mathbf{v}}_{i,r})]$$

最后，再来回顾一下GATNE的整体算法流程

实验