论文阅读 Predicting Dynamic Embedding Trajectory in Temporal Interaction Networks

🚀 优质资源分享 🚀

学习路线指引（点击解锁）	知识定位	人群定位
🧡 Python实战微信订餐小程序 🧡	进阶级	本课程是python flask+微信小程序的完美结合，从项目搭建到腾讯云部署上线，打造一个全栈订餐系统。
💛Python量化交易实战💛	入门级	手把手带你打造一个易扩展、更安全、效率更高的量化交易系统

Probing the Forecasting of Dynamic Embedding Trajectory in Temporal Interaction Networks

link:https://arxiv.org/abs/1908.01207

Abstract

该文提出了一种在嵌入空间中展示建模用户及项目未来走向的JODIE模型。该模型基于RNN架构，在学习用户与项目嵌入演变路径方面具有应用价值。通过JODIE方案，可实现对未来走势的预测分析。本文还提出了t-Batch算法，在采用该方法的基础上创建时间同步批次可使训练效率提升9倍。

Conclusion

在本文中

未来的工作将涉及以下几个方面。训练单个用户的嵌入模型计算开销较大, 但可以通过训练用户行为轨迹来降低计算复杂度; 同时也可以考虑对项目组的行为进行建模; 另一个研究方向是分析并建模实体间的行为模式; 最后, 一个新兴的研究领域是根据许多潜在互动的对象精准预测新项目的构建需求

Figure and table

由于图片无法正常加载，请检查源站是否设置了防盗链相关限制，并尝试将图片保存后重新上传至指定存储路径：$oss-v2.aliyuncs.com/

如图1所示，在左侧展示了一个基于时序交互的时间序列模型（二部图），涉及三个用户节点和四个商品节点。连接线代表了在时间t点上基于特征向量f的互动关系。右侧展示了用户行为与商品行为的时间序列演变过程，并通过训练一个基于可学习参数矩阵的嵌入预测模块来推导用户的潜在行为轨迹（如虚线所示）。其中虚线标记的是系统对用户的潜在行为趋势的推断结果

由于外部链接中的图片无法正常转存至源站（原因可能是防采集技术限制），建议用户将图片保存后直接上传至该外链地址：https://luoyoucodeimg.oss-cn-hangzhou.aliyuncs.com/image-20220518171523083.png

表1 进行了对现有多种算法及JODIE用途领域的比较分析，并确保了自己的论文需求得到了充分满足。

该外链图片无法正常上传至平台中，请您参考以下方式进行操作：在访问源站时可考虑防获取或下载限制机制，并建议您将图片保存后直接上传以规避相关限制

请确保外链图片存储于本地设备后进行上传

如图2所示的JODIE模型中，在一轮交互(u,i,t,f)之后（其中(u,i,t,f)表示一次交互），该模型将通过RNNU和RNNI两个模块将用户的兴趣点uuu和物品iii的状态更新为它们各自的动态嵌入表示；随后进行预测以推断出用户的未来时间点t+Δt的嵌入信息

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fL8ocpQF-1653325856952)(https://luoyoucodeimg.oss-cn-hangzhou.aliyuncs.com/image-20220518203728664.png)]

表2 符号的含义

由于外链图片无法正常显示（img-xbtKTFMx-1653325856953），建议您在本地保存后再重新上传至（https://luoyoucodeimg.oss-cn-hangzhou.aliyuncs.com/image-20220518203757197.png）

由于外链图片无法正常显示（img-xbtKTFMx-1653325856953），建议您在本地保存后再重新上传至（https://luoyoucodeimg.oss-cn-hangzhou.aliyuncs.com/image-20220518203757197.png）

图3呈现了预测操作的结果。该系统对用户的三个不同时间点进行了嵌入位置预测，并标注了这些时间点之间的关系：Δ1小于Δ2小于Δ∆1小于∆2小于∆∆_1小于∆_2小于∆。随着观察时间的延长，预测值将逐渐偏离基准值；在用户进行下一次交互时，系统会重新计算当前嵌入向量。

外部链接中的图片无法正常上传，请检查您的网络环境并尝试重新上传；网站可能存在防盗链配置，请确保文件存储位置正确

交互预测实验结果表中展示了各类算法在多个数据集上的性能对比，并以MRR和Recall作为评估标准

由于该外链图片无法显示（可能因源站设置了防采集措施），请将图片保存后直接上传至指定链接：https://luoyoucodeimg.oss-cn-hangzhou.aliyuncs.com/image-20220519104929588.png。

表4 用户状态更改预测：用auc做指标

建议您将图片保存后重新上传至目标位置（img-prxl3fRM-1653325856957）。

图4 运行时间对比

外部链接中的图片无法正常上传，请参考源站可能存在的防盗链等技术限制访问并保存相关文件后重新上传（img-82RhRPuy-1653325856958）（https://luoyoucodeimg.oss-cn-hangzhou.aliyuncs.com/image-20220519105858297.png）

图5 鲁棒性对比

外部链接图片存取失败（图）

图6 动态嵌入尺寸的鲁棒性对比

Introduction

本文提出了一个工业场景中实际的四个问题

这类方法通常是在用户产生交互后进行嵌入更新，并且无法实时反映最新的行为模式。例如，在购买当天的一位新用户体验者将拥有最新的初始状态表示。然而，在两天后、一周之后或更长时间内访问平台时该用户的后续访问行为中将始终使用这一不变的初始状态从而导致系统对她的行为预测也将保持一致这也就意味着在她频繁访问的情况下（如每天登录）系统对她的行为预测也将保持一致然而在时间推移的过程中用户的意图会发生变化（即需求优先级可能会发生调整）因此平台必须定期重新计算用户的当前状态以适应新的查询时间点这意味着系统必须能够有效地跟踪并预测这些动态变化的过程

实体随着时间变化的属性以及固定不变的属性都是存在的。现有的方法通常仅关注其中一类

许多现有方法均采用对每个用户的各项任务进行评分的方式来进行互动关系估算。

目前主流的大多数模型都是将交互被串行化的形式进行线性排列，并被按顺序执行以保留时间顺序信息。此外计算开销较高。

该模型JODIE通过时间交互机制构建了所有用户与项目的时空行为轨迹。当进行用户行为预测时，默认并不会直接引用上一步骤的用户行为向量；而是在此过程中采用分步策略：首先根据目标时间点推断出用户的潜在行为特征；接着基于此推断出下一步的行为模式。从而有效解决了系统行为建模中的第一个关键难题。

本文提出了一个名为JODIE的学习模型。该模型能够从时间交互中提取所有用户的与项目之间的关系，并为每个用户和项目生成两个不同的属性：一个是静态属性（static embedding），另一个是动态属性（temporal embedding）。静态属性用于表示实体的长期稳定特征，而动态属性则用于捕捉随时间变化的特征，并通过JODIE算法实现了这些嵌入特性的学习，并成功解决了第二个关键问题。

该模型由两个核心组件构成：更新模块与预测模块。在该模型中进行更新的操作包含两个RNN网络分别用于生成用户的表示以及项目的表示，并且这两个网络被巧妙地连接在一起以便整合用户的偏好与项目的属性间的相互影响。当再次进行互动时，在新的信息下调整用户的表示；同样地利用最新的用户信息来优化项目的表达；这种机制促进了特征间的交叉作用

对于以往的工作而言，在预测用户的下一步交互项目时，通常需要为每个项目进行评分。这将导致线性时间复杂度的问题。本文提出的方法通过模型预测生成的嵌入向量，在这些向量之间寻找最接近的目标向量。通过位置敏感哈希（LSH）技术能够在固定时间内高效地解决问题。

作者进一步阐述了t-batch操作的具体实现。传统模型通常采用按时间序列处理单个交互的方式来构建用户嵌入。本文提出的方法通过构建独立于其他批次的交互集来进行JODIE模型训练，在此过程中各批次间的互动得以有效管理。每次迭代包含从整个互动图中选择一组不重叠边的操作，并确保所有用户的互动按照时间顺序排列递增。

Method

3 JODIE: JOINT DYNAMIC USER-ITEM EMBEDDING MODEL

在本节中，我们将阐述JODIE的具体架构。该模型旨在学习用户的嵌入序列\boldsymbol{u}(t) \in \mathbb{R}^{n}（对于所有u\in\mathcal{U}）以及项目的嵌入序列\boldsymbol{i}(t) \in \mathbb{R}^{n}（对于所有i\in\mathcal{I}），其中t属于时间段[0,T]。这些嵌入均基于时序用户的交互数据形成的有序序列S_r = (u_r,i_r,t_r,f_r)（r=1,…）。每个交互事件由用户u_r\in\mathcal{U}与项目i_r\in\mathcal{I}在时间点t_r\inℝ⁺上发生，并且满足顺序关系0 < t₁ ≤ t₂ ≤ … ≤ fₐ。

JODIE基于用户与物品间的互动进行更新机制的训练。通过之前记录的状态及所花费时间学习预测未来嵌入的操作。当检测到用户的项目互动时其嵌入将发生更新。

每个用户与项目都被赋予了两种嵌入形式：分别是静态嵌入与动态 embed. 通过这种双重 embed 策略, 我们能够有效地捕捉实体的长期 static 特性和 dynamic 变化特征.

static embeddings are defined as u_{\text{bar}} \in \mathbb{R}^{d} for all u in \mathcal{U}, and similarly i_{\text{bar}} is defined as \mathbb{R}^{d} for all i in \mathcal{I}. These static embeddings remain constant over time. They are designed to encode fixed attributes, such as the long-term interests of users. In this paper, we employ one-hot encoding to establish the static embeddings for both users and projects.

动态嵌入概念：我们通过将每个用户uuu与项目iii分别映射到时间t的不同维度空间中来构建动态嵌入模型。其中u(t)\in\mathbb{R}^{n和i(t)\in\mathbb{R}}n分别代表了在时间t上的用户的低维向量表示与项目的低维向量表示。随着t的变化而发生更新，从而能够反映其在不同时间段的行为模式及属性特征。用户的动态轨迹则反映了其行为演变过程中的路径特征。

接下来介绍更新和预测操作

*3.1 Embedding update operation

在更新阶段中，在时间点t上进行的互动由用户uu以及项目iii共同参与，并通过关系S=(u,i,t,f)进行记录。这些互动被用来生成其动态表示u(t)和i(t)。图2清晰展示了这一过程

我们的模型基于两层递归神经网络完成参数更新，在线学习过程中每个用户都与同一个RNU参数矩阵结合使用以生成用户的兴趣向量，在线学习过程中每个项目也都与同一个RI参数矩阵结合使用以生成项目的流行度向量。这些用户的隐藏状态分别对应于用户的兴趣空间维度和项目的流行度空间维度

这两个RNN结构之间存在相互递归关系（recurrently mutual）。在与项目iii进行交互时，在时间ttt阶段，它们的时间序列编码嵌入被作为输入传递给RNNU。该模型通过更新其时间序列编码嵌入来处理用户的互动行为。

作者提到了原来普遍用的使用项目独热码来训练的缺点

a） 独热码只包含关于项的id的信息，而不包含项的当前状态

b）当实际数据集有数百万项时，独热码的维度变得非常大，不利于训练

本文采用项目动态嵌入技术, 其反映了项目当前的状态, 从而带来了更为有意义的动态用户 嵌入以及更加容易的学习过程。同样地, RNNI通过利用 u(t) 更新项目 iii 的 动态 嵌 i(t^-) (此 处为 时间 t 之前的 u 嵌) , 这将 形成各向 异性间的 相互依 赖关 系, 见 下 式

等于 σ 函数作用于 u 在时间 t 的值等于 σ 函数作用于 i 在时间 t 的值，
其中 u 和 i 分别表示细胞激活状态，
各个权重参数 Wu、Wi、Wf 和 Δ 分别代表更新门、输入门、遗忘门以及变化量，
数学表达式如下：
\begin{array}{c} \boldsymbol{u}(\boldsymbol{t})=\sigma\left(W_{1}^{U} \boldsymbol{U}\left(\boldsymbol{t}-\right) + W_{2}^{U} \boldsymbol{I}\left(\boldsymbol{t}-\right) + W_{3}^{U} f + W_{4}^{U} \Delta U\right), \\ \boldsymbol{i}(\boldsymbol{t})=\sigma\left(W_{1}^{I} \boldsymbol{I}\left(\boldsymbol{t}-\right) + W_{2}^{I} \boldsymbol{U}\left(\boldsymbol{t}-\right) + W_{3}^{I} f + W_{4}^{I} \Delta I\right) \end{array}
其中，

Δ_u表示自用户上一次交互（与任何项目）以来的时间间隔, Δ_i表示自机器人上一次交互（与任何用户）以来的时间间隔. （引入了时间间隔的相关信息）。

ff f是交互特征向量

Wu1,…Wu4W1u,…W4uW^u_1 , . . .Wu_4和Wi1,…Wi4W1i,…W4iWi_1 , . . .W^i_4是可训练矩阵

σσ σ 是激活函数sigmoid

RNN的不同版本及其衍生模型如LSTM、GRU和T-LSTM，在实际应用中展现出类似的效能水平。值得注意的是这些替代型在某些场景下可能会略逊一筹因此在模型设计中合理选择替代型有助于减少可训练参数的数量。（这表明并非所有新技术都能带来优势）

*3.2 Embedding projection operation

在本节中, 作者阐述了自己模型的第二个主要部分, 即预测操作。通过这一方法, 模型能够推断出用户的未来嵌入行为轨迹。该方法可用于后续应用场景, 例如链接预测、社交网络分析等。

图3呈现了预测过程的核心概念。在时间点t时，u(t)代表用户的行为主特征向量。假设存在三个不同时间段Δ₁ < Δ₂ < Δ₃，在每个时间段内观察用户的行为变化轨迹u(t + Δ₁), u(t + Δ₂), u(t + Δ₃)。从图中可以看出作者主张这些时间段与用户的嵌入平移距离呈正相关

接着基于真实位置{ u }( t + Δ )和预测位置 \hat{ u }( t + Δ )为基础进行训练的可调节矩阵。

该操作涉及两个输入变量u(t)、即u(t)以及\Delta\Delta\Delta。然而，并非仅仅是将嵌入与时间间隔进行连接，而是通过哈达玛积的运算实现时间和嵌入的融合。这表明先前研究表明神经网络在处理拼接特征方面效果不佳。

本文随后通过线性层W_p进行计算来生成时间相关向量\boldsymbol{w}, 其中w = W_p\Delta. 这种初始化方式采用零均值高斯分布以确保初始状态具有良好的性质. 接下来, 将预测嵌入与上一个时间步的相关嵌入进行点积操作以获取当前时刻的时间依赖信息

\widehat{\boldsymbol{u}}(t+\Delta)=(1+\omega)*\boldsymbol{u}(t)
通过时间注意力机制将权重（1+\omega）放大至过去的时间步用户嵌入。当\Delta = 0时，在线性系数中设置零权重；预测用户的嵌入表示与输入之间的差异随着\Delta数值增大而增大。

该作者认为，在嵌入空间中的神经网络层能够最佳适用于嵌入预测任务。等价于一种简单的、可解释的、可微分的、并行计算机制。如果在变换中加入非线性元素，则会导致投影操作呈现明显的非线性的特征。通过实验结果表明，在实际应用中这种策略的效果令人失望。基于以上分析与论证的结果。

3.3 Training to predict next item embedding

本节作者将会介绍如何去预测下一个项目嵌入

此前提到过，在本文中所提出的模型与以往大多数模型的主要区别在于其并未通过计算两个嵌入之间的连接概率来实现相似度评估（类似于CTR模型），而是直接输出了一个完整的嵌入向量。这种设计上的改动带来显著的优势在于大幅降低了计算复杂度——从与项目数量呈线性的规模缩减至几乎恒定的时间复杂度。具体而言，在JODIE模型中仅需对预测层执行一次前向传播过程即可生成并返回与之对应的预测项嵌入向量。为了实现这一高效检索功能，则采用了位置敏感哈希（LSH）技术，在几乎相同的时间复杂度内即可检索出最接近的项。此外，在每次项目的嵌入更新过程中也需要同步维护LSH数据结构以保证其有效性和稳定性。

因此经过JODIE模型训练后能够实现预测嵌入\tilde{j}(t+\Delta)与真实嵌入\left[\bar{j}, j\left(t+\Delta^{-}\right)\right]之间的最小化L2范数计算具体公式为\left|\tilde{j}(t+\Delta)-\left[\bar{j}, j\left(t+\Delta^{-}\right)\right]\right|_{2}其中符号[x,y]表示两个向量的拼接操作而上标"-"则表示时间域内的相关操作该符号定义见表2

在基于时间增量\Delta的情况下，在t + \Delta前侧采用用户的预测嵌入\widehat{\boldsymbol{u}}(t + \Delta)以及项目的潜在因子i(t + \Delta - )进行预测。

使用项目嵌入i(t+Δ−)i(t+Δ−)i(t+\Delta^{-})有两点原因

项目i可能在时间段[t, t+∆]内与其他用户进行交互操作，并由此使得嵌入模型能够捕获最新的动态信息

（b）用户经常连续地与同一项目交互，包含项目嵌入有助于简化预测。

我们使用静态和动态嵌入来预测预测项j的静态和动态嵌入。

使用完全连接的线性层进行预测，如下所示

计算得到j在时间点t加Δ时的值为：j(\boldsymbol{t}+\Delta)等于权重矩阵\mathbf{W}_{1}与平滑后的输入特征\widehat{\mathbf{u}}在时间点t+\Delta时的乘积加上权重矩阵\mathbf{W}_{2}与平均化的输入特征\overline{\mathbf{u}}的乘积再加上权重矩阵\mathbf{W}_{3}与t+\Delta^{-}时刻的空间插值结果i的乘积以及权重矩阵\mathbf{W}_{4}与平均化的插值结果\overline{\mathbf{i}}的乘积之和再加上偏置向量\mathbf{B}。\n其中权重矩阵和偏置向量共同构成一个线性层结构。\n

综上 损失如下

第一个损失项旨在最小化预测嵌入误差。此外添加了两项是为了规范化总损失，并防止用户和项目在连续时间点上的动态嵌入出现剧烈变化。其中λ_U和λ_I是调节参数。

如何将损失扩展到分类预测

可以训练另一个预测函数Φ:ℝ^{m+q}→Y，在交互过程中形成的静态嵌入通常具有较低的维度数（d维），而动态嵌入则由交互行为决定（n维）。通过交互过程生成的用户嵌入用于标签预测任务中。同时，在优化过程中会引入缩放因子以防止模型过拟合问题。

*3.4 t-Batch: Training data batching

该方法旨在实现模型的并行化训练，并将所有操作安排在相应的计算节点上以减少通信开销。例如，在处理交互项S_r时，应位于序列S_k之前，并满足条件∀r<k

现有的并行方法主要采用将用户划分为多个批次来进行并行处理。然而JODIE基于其两个RNN模型具有相互递归特性，在同时处理同一项目的两个用户之间建立了直接关联这会导致在同时处理同一项目的两个用户之间建立直接关联这会导致在同时处理同一项目的两方之间形成直接关联从而避免将一个用户的活动分解为独立的小批次以实现异步处理

所以提出了在构建批次时应该满足的两个条件

1：可并行训练

2：若按照索引的递增顺序处理，应保持交互的时间顺序

t-Batch采用了基于独立边缘集的选择机制来构建每个批次，并确保同一时间段内的任意两个交互均不共享公共用户或项目。

具体说一下这个算法的流程，分两步

1 选择：该算法将从给定的边集中挑选出一组互不共享顶点的边，并通过最小化每条选中边（u, i）的时间戳来优化整体性能。

2 减少：在单个批次的训练完成后，并将其上一步选出来的边从图中删除。然后继续下一步操作。

Experiment

4 EXPERIMENTS

静态向量和动态嵌入维度为128，eopch选择50

选择三个种类的算法baseline：

(1) Deep recurrent recommender models

Recurrent Recommender Networks (RRN): C.-Y. Wu, A. Ahmed, A. Beutel, A. J. Smola, and H.-Jing Jing.Recurrent recommender networks in WSDM (2017).

LatentCross ：A. Beutel, P. Covington, S. Jain, C. Xu, J. Li, V. Gatto, and E.H.Chi.Latent cross: Exploiting context within recurrent recommender systems.In WSDM 2018

Next step: modeling user behavior with Time-LSTM. presented at the IJCAI conference in 2017.

(2) Dynamic co-evolution models

Deep Coevolve Network: 研究者们提出了通过嵌入用户和物品特征来进行推荐的方法，在arXiv上发表于2016年。

(3) Temporal network embedding models

CTDNE为G.H.Nguyen,J.B.Lee,R.A.Rossi,N.K.Ahmed,E.Koh,andS.Kim提供了Continuous-timeDynamicNetworkEmbeddings。ProceedingfromtheWWWBigNetsymposium2018。

数据集：

Reddit public dataset : 我们收集了来自Reddit平台下一个个别子版块一个月内的帖子内容。为了构建该项目的数据集, 我们从1000个活跃度最高的子版块中进行了选择, 并筛选出1万位活跃度最高的用户群体. 这样的选择带来了672,447次互动行为. 我们将每篇文章的内容转换为反映其语言风格特性的特征向量

Wikipedia edits : His public dataset comprises one month of editing data from Wikipedia pages. We selected the top 1,000 most edited Wikipedia pages as our study subjects. These editors have contributed at least five edits under the user identity, involving a total of 8,227 unique users. This resulted in a total of 157,474 interactions between editors and Wikipedia pages. Similar to the Reddit dataset, we converted the edit texts into LIWC feature vectors.

该公共数据集包含一个月的Who Listen行为数据。我们从全部1,000名注册用户和播放频率最高的1,000首歌曲中抽取样本，并记录下了共计1,293,103次交互记录。在本数据集中，默认情况下交互功能被设置为关闭状态。

4.1 Experiment 1: Future interaction prediction

sota见表三

4.2 Experiment 2: User state change prediction

sota见表4

4.3 Experiment 3: Runtime experiment

运行时间见图4

4.4 Experiment 4: Robustness to the proportion of training data

sota见图5

4.5 Experiment 5: Embedding size

sota见图6

Summary

本文的核心内容在于探讨用户与项目的互动预测机制。而非直接采用用户的嵌入向量作为基础，在经过预测操作后，在时间维度上推演用户的动态嵌入变化趋势。将这一趋势用于项目相关分析。整篇论文既简洁又实用，并简要阐述了其采用的关键原因。例如为何选择使用RNN模型？以及线性变换参数Δ的作用是什么？整体阅读体验良好。