第 26 届 ACM SIGKDD 知识发现和数据挖掘会议（KDD2020）正在以线上形式召开。今年今年KDD应用数据科学方向(Applied Data Science Track)有756篇论文投递，收录121篇，接收率约为16.0%，其中Oral论文44篇、Poster论文77篇；KDD研究方向(Research Track)有1279篇论文投稿，收录216篇，接收率约为16.9%。
本文是对滴滴Poster论文《实时事件嵌入学习的动态异质图神经网络》的详细解读。在这篇论文中，滴滴提出了一种基于多层注意力的图神经网络算法，用于对历史行为和环境周边的事件进行嵌入学习，从而提升对于响应模型的预测准确率。目前，这个框架已经在滴滴进行了实际应用，每天服务于千万级别的实时事件预测。
研究背景
在线上广告和推荐领域中，实时客户响应预测在许多工业应用中至关重要。特别是对于滴滴和Uber等打车平台而言，挑战更大。这是因为响应预测模型需要考虑历史和物理环境中的实时信息，诸如周边的交通和供需状况。如图一所示，对于一个打车平台，用户的打车行为包括以下几种类型：1）PreView(预览事件)；2）Request(发单事件)；3）Cancel_Order(取消事件)；4）Finish_Order完单事件。
图一：用户打车行为中的不同事件具体地，一个乘客在预览(Preview)之后，会不会发出订单(Request)受到用户的历史行为习惯的影响和当前环境中的供需情况影响，如图二所示：
图二：典型的用户打车事件流图二中，我们把乘客的一次历史交易行为定义成一个异质的session(h-session)，一个异质session可能包括预览、发单、取消、完单事件（异质顶点）。同时我们按照业务逻辑连接不同的顶点，并定义了异质边。除此之外，我们考虑和用户预览行为相同起点的其他异质session，并根据同时出发和同时到达定义了另外两种异质边。这两种异质边是为了把和用户预览相同起点格子的异质session连接起来，这样可以间接的对需求信息进行建模；另外我们把以当前起点格子为终点的异质session和当前用户预览连接起来，这样可以间接的对供给信息进行建模。此外，对于同一个乘客在时间轴上的其他历史交易行为，我们把这些交易行为的历史供需快照信息也按照同时出发或同时到达连接了它们对应的异质session。故而，对于每一个用户的预览事件，它能看到的历史异质session各不相同，每一个实时预览会有一个新的动态异质图。在本论文中，我们提出一种基于动态异质图的事件嵌入学习算法，用于对周边的信息进行建模。
问题挑战
然而，动态实时事件嵌入学习面临着以下挑战：
1、对于每一个新的实时事件，系统需要为该事件进行动态的图构造。
2、动态图里面的实体和边都是异质的，异质图里包含了多种不同类型的顶点和边。
3、不同种类的实体以及不同类型的边会对当前的实时事件产生不同的影响。
4、如何进行大规模的实时事件建模。
为了解决上述问题，我们提出一种实时事件嵌入学习的图神经网络算法（Real-time Event Graph Neural Network，REGNN），REGNN以归纳学习的方式编码了用户行为习惯和周围环境的动态异质事件，可以为实时事件产出嵌入表示。具体地，我们的REGNN有以下4个创新点：
1、从不同维度为实时事件构造了动态异质图。
2、基于事件动态异质图，提出一种多层注意力机制的图神经网络(GAT)算法进行事件嵌入表示学习。
3、对于有时序关系的实时事件，采用RNN进行时序建模。
4、我们把动态异质图神经网络用到滴滴的两个实际应用场景中，均取得了较大的离线和在线提升。
解决方案
REGNN首先基于实时事件不同维度的属性进行动态异质图构造，进而进行嵌入学习，最后用于事件预测。具体地，我们算法框架如图三所示：
图三：REGNN算法框架首先，对于一个事件，REGNN会抽取该事件的基本信息进行动态异质图构造。例如一个预览事件包括以下基本信息：乘客ID，起点POI格子，终点POI格子等。根据乘客ID，REGNN抽取了乘客的历史异质session，图三中不同的形状代表不同类型的事件。类似地，对于起点POI格子和终点POI格子，同时出发或同时到达的异质session也可以和当前事件连接。进而，根据不同属性构造的事件子图之间可以进行跨属性的聚合。最后，对于下游任务任务预测，REGNN采用RNN对不同时序上的事件又做了一次时序上的聚合。
在对异质图信息进行聚合时，我们采用了一个多层次的GAT(Graph Attention network)算法进行信息聚合，如图四所示。在算法第0层，我们对各种异质顶点进行初始化，具体的我们对预览事件、发单事件、取消事件和完单事件按照事件属性进行初始化，对于虚拟的异质session，我们用预览事件的特征对它进行初始化。在算法第一层，我们把各种不同类型的事件利用GAT聚合到h-session，这也叫h-session内部的GAT（cross h-session embedding）。在算法第二层，我们对于同一个子图内部的所有h-session进行聚合（cross h-session embedding）。在算法第三层，我们把不同子图的h-session做跨属性的聚合(cross subgraph embedding)。最后，我们对于时序上的事件embedding，采用了RNN进行了聚合。
图四：多层注意力机制的图神经网络在三层GAT之后，每一个预览事件的嵌入表示都编码了该预览之前的历史交易信息，每一个历史交易对应的POI快照信息。但是不同时刻的历史交易信息对当前预览的影响权重并不相同，所以REGNN引入了RNN对这种时序模式进行建模。具体地，REGNN采用多头注意力机制计算不同层次的权重，within h-session的GAT, cross h-session的GAT和cross subgraph的GAT计算分别如公式一、二、三所示：
公式一：h-session内部的多头注意力机制
公式二：h-session之间的多头注意力机制
公式三：跨属性的多头注意力机制由于我们的GAT是针对异质事件计算的，故而在多头注意力时需要对不同类型的事件进行transformation之后再进行聚合，transformation的逻辑如图五所示。H-session会针对其内部的不同类型的事件计算不同的注意力权重，再进行向量更新。
图五：h-session内部的GAT生成预览事件的embedding表示之后，对于不同时序上的h-session,我们采用了RNN做时序建模，对于预测用户是否发单，我们的目标函数是一个分类问题，采用了交叉熵损失。
实验与结果
我们对比了一系列用户点击率预估算法和基于图神经网络的推荐算法，包括：
1）DNN(Deep Neural Network)是经典的多层神经网络算法。
2）DIN(Deep Interest Network)是经典的采用注意力机制进行点击率预估的算法。
3）DIEN(Deep Interest Evolution Network)在DIN的基础上集成了GRU和注意力机制进行点击率预估。
4）MIMN(Multi-channel user Interest Memory Network)采用了NTM(Neural Turing Machine)和基于记忆力的算法框架进行点击率预估。
5）SRGNN(Session-based Recommendation Graph Neural Networks)采用了GNN对 session中的item进行embedding并用于推荐。
通过实验，我们验证了REGNN相对于以上经典算法均取得了较大的离线效果提升。此外，对于时序聚合算法RNN，我们对比了不同版本的GRU和LSTM以及图聚合算子GAT, GCN, Pooling等。此外，我们把REGNN部署到线上系统，通过ABTEST之后，线上AUC也取得了较大的提升。此外，我们把相同的建模框架应用到智能客服机器人对话系统，也取得了较大的离线和线上提升。
