KDD20 | 异质图在滴滴的行业应用专题

论文解读者：北邮 GAMMA Lab 硕士生  庄远鑫

1 引言

异质信息网络的概念自 2009 年首次提出以来，迅速成为数据挖掘领域的研究热点，并在这类网络上开发了许多创新性的数据挖掘任务。 此外，还开发了一些独特的分析技术来展示异质信息网络的好处。 特别是，随着大数据时代的到来，异质信息网络为大数据中复杂对象及其关系的建模和分析提供了一种有效的途径。

本文将介绍两篇滴滴在KDD 2020上发表的利用异质信息网络解决实际问题的工作。

第一个工作是《HetETA: Heterogeneous Information Network Embedding for Estimating Time of Arrival》，提出异质时空图卷积网络用于预估到达时间。

第二个工作是《Gemini: A Novel and Universal Heterogeneous Graph Information Fusing Framework for Online Recommendations》，提出一种通用的在线推荐异质信息融合框架。

2 HetETA: Heterogeneous Information Network Embedding for Estimating Time of Arrival

2.1 动机与贡献

预估到达时间（ETA）是智能交通系统的核心功能，它测量车辆预计从起点到达某个目的地时的旅行时间。 通过挖掘复杂的时空信息来准确的估计行程时间可以节省用户时间和优化车辆调度。

这篇文章首次将异质信息网络应用于 ETA 任务。 从时间和空间两个角度提取异质信息，并提出了 HetETA 框架来融合它们并学习对 ETA 任务的表示。

在一个大规模城市道路网中的四个真实世界车辆出行数据集上进行的实验验证了提出的模型明显优于其他方法。

2.2 模型

HetETA 由三个组件组成，分别用于学习最近时段、每日时段和每周时段的 时空异质信息。 三个组件由一个全连接层连接，并输出预测值。

鉴于 GNNs 已被证明是一种成功的学习矢量化节点表示的基于图结构的模型，使用图神经网络来学习空间相关性，并在异质信息的道路网络和基于车辆轨迹的网络上提取有意义的表示。

最近的研究表明，与 RNNs 相比，CNNs 具有并行化、可训练性和推理速度快等优点。 因此，使用 CNNs 来分析时间序列轴上的时间相关性。

GNNs 和 CNNs 在 3 个双拼三明治结构（Double-stuffed sandwich layer）下协同工作，分别学习近期周期、每日周期和每周周期的时空异质信息的相关性。 在双层夹层内进行了层归一化处理，以解决过拟合问题。

2.3 实验

数据集

实验部分是在中国辽宁省省会沈阳进行了实验。 根据滴滴出行提供的商业地图构建了沈阳市的公路网。 它是一个有74,685个顶点和94,127条边的多关系图，其中关系类型表示路段之间的转弯方向。 节点特征分为静态特征和动态特征。 静态特征（包括道路类型、路段宽度、路段长度、限速、车道数等）不会随时间变化。 相反，动态特征以 5 分钟为周期变化，计算每个路段中过往车辆的平均速度，并将其作为动态特征。

实验结果

可以看出 HetETA 在四个数据集上比最具竞争力的基线分别降低了1.99%、1.59%、2.13%和1.79%的 MAPE。

ETA 任务的性能很难提高，MAPE 略有降低通常意味着 ETA 任务具有很高的商业应用价值。

3 Gemini: A Novel and Universal Heterogeneous Graph Information Fusing Framework for Online Recommendat ions

3.1 动机 与贡献

滴滴出行服务于亿万活跃乘客和数百万活跃司机。 针对日常运营的不同需求，滴滴出行构建了乘客增长的优惠券推荐、司机激励的产品推荐、订单增长的广告推荐等十几种不同类型的推荐场景。 在不同的推荐场景中，推荐的项目完全不同，可获得的信息也大相径庭。 因此，如何构建一个统一的推荐系统来解决所有这些场景的推荐需求是一个巨大的挑战，特别是在面对用户与项目交互的稀疏性问题时。

这篇文章提出了一种新的异质图融合框架 Gemini，该框架不依赖任何辅助信 息，通过新颖有效的网络变换更有效地处理异质图。 因此，Gemini 可以应用于各种推荐方案，并取得满意的效果。 这是第一个将异质图转换为两个不遗漏任何关键拓扑信息的半同质图的工作。

3.2 模型

为了在滴滴出行的各种推荐场景中得到应用，Gemini 只使用了最常见的用户-项目点击日志。

Gemini不是直接在用户-项目异质网络上工作，而是分别从用户和项目的角度将其转换为两个半同质图（即图1中的Gemini-U和Gemini-I）。

Gemini-U和Gemini-I具有相似的结构，由网络节点和属性节点组成，就像双胞胎一样，这就是它的名字的由来。

从用户的角度来看，如果两个用户都点击了相同的一些项目，那么他们就有了一些共同的兴趣，从而增加了Gemini-U的优势。 这些项目是边的属性节点，称为Att-U。 除了提供项嵌入来表示用户对的共同兴趣之外，ATT-U还可以通过两种方式表征边的重要性。 一种方式是项目的数量，项目越多，边就越重要。 另一种方式是单个项目的重要性，项目越重要，边就越重要。

前人的一些工作将异质的 User-Item 图转化为 User-User 的同质图，但是丢失了 User 和 Item 之间原有的拓扑关系。 相比之下，从 User-Item 图到Gemini-U的转换不会丢失任何原始拓扑信息，因为所有的用户节点、项目节点以及它们之间的关系仍然可以在 Gemini-U 中找到，只是从不同的角度。 这种变换的优点是基于 GCN 的算法可以应用于 Gemini-U，只需额外考虑 Att-U 中的项嵌入。

从项目的角度出发，可以得到 Gemini-I 和 Att-I（即边的用户节点），并应用相同的 GCN 算法。

在训练过程中，共享 Gemini-U 和 Gemini-I 之间的用户和项目嵌入，通过边属性 Att-U 和 Att-I 将两个网络信息融合过程紧密地关联起来。 这带来了两个好处：

1. 两类节点的表示是不同的，但仍然在同一个低维空间中；

2. 随着网络信息融合的进行，项目嵌入结合了其多阶邻居的信息，从而可以将项目之间的邻居关系信息引入到基于 Gemini-U 的用户信息融合中。类似地，这样的用户信息也被引入到 Gemini-I 中。

3.3 实验

数据集

为了验证Gemini的普适性和有效性，选取了五种不同类型的推荐数据集。 前四个数据集提取自滴滴出行的以下推荐场景，如图3所示： 积分商城中的产品推荐(DiDi-Product)、滴滴出行APP中的内容推荐(DiDi-Content)、滴滴出行FM中的音乐推荐(DiDi-音乐)和滴滴出行APP中的优惠券推荐(DiDi-优惠券)。 最后一个数据集是一个常见的公共数据 MovieLens。 MovieLens与上述四种推荐不同，因此选择MovieLens作为额外的数据集来评估在不同推荐类型下的性能。

实验结果

表1给出了所有方法的评估结果。 与每个场景中的最佳基线相比，Gemini 将 AUC 分别提高了3.7%、10.8%、1.1%、3%和1%. 这些结果证明了该方法的有效性和普适性。

4 总结

本文介绍的两篇工作利用异质信息网络处理预估到达时间以及推荐问题，模型都非常新颖和巧妙。

本期责任编辑：杨成

本期编辑：刘佳玮

---

北邮 GAMMA Lab 公众号

主编：石川

责任编辑：王啸、杨成

编辑：刘佳玮

副编辑：郝燕如，纪厚业

长按下图并点击“识别图中二维码”

即可关注北邮 GAMMA Lab 公众号