[WSDM 2022]HTGN-BTW: Heterogeneous Temporal Graph Network with Bi-Time-Window Training Strategy for Temporal Link Prediction
介绍
这篇文章是基于 WDSM 2022 CUP 比赛的文章。根据作者的介绍，这篇的作者是在比赛中拿了第二名。
比赛内容
给定一个时间间隔（a given time span），预测间隔内两点间是否会出现某种类型的边
数据集
两组数据集A和B
- A：时序事件图，正常图，无向，每条边包含源点，目标点，边类型，时间戳，且拥有点特征和边特征
- B：用户-商品图，二部图，无向，相比A数据集，没有点特征
数据统计：
其中，A的时间戳可以被3600整除，所以文中把A的时间戳由秒转为了时。文中统一将两组数据集视作异构图。
相关工作
文中称以前的工作特征丰富（without feature missing problems），并且没有不固定的时间间隔限制
- [arxiv 2022]Inferring network structure with unobservable nodes from time series data
- [KDD 2021]Heterogeneous Temporal Graph Transformer: An Intelligent System for Evolving Android Malware Detection
- [PKDD 2021] Dynamic Heterogeneous Graph Embedding via Heterogeneous Hawkes Process.
- [TKDE 2020] Dynamic Heterogeneous Information Network Embedding with Meta-path based Proximity
- [New Gener. Comput. 2020]Temporal Link Prediction: A Survey
- [PKDD 2020]Temporal Heterogeneous Interaction Graph Embedding for Next-Item Recommendation
- [KDD 2020] Dynamic Heterogeneous Graph Neural Network for Real-time Event Prediction
难点
- 异构信息
- 点/边缺失特征
- 不固定的时间间隔预测
对于第一点，靠建立交换邻居信息的模型解决；
对于第二点，用其他信息补足特征
对于第三点，把间隔裁剪成更小的片段，再将他们视作时间点。模型事先时间戳的预测后，再聚合成最终结果。
问题定义
已知T前的信息，预测T+1到T+x之间的边类型。
模型
Memory
这部分和TGN相同。
对于每个点，都有一个随时间更新的向量\(m_i(t_i)\)，其中\(t_i\)表示最后更新的时间。这些向量用0向量来初始化，每次这个点涉及的边出现就进行更新。
注意这部分不会进行反向传播。
静态点嵌入
这部分，每个点需要另一组特征\(sne_i\)，这组特征随机生成。
关系嵌入
对于不同类型的关系\(r\)，也就是边类型，都有一个特征\(re_r\)。有这个特征就可以同时兼容带边特征和不带边特征的图了。
时间编码
用于把时间差\(t_2-t_1\)嵌入成\(te_{t_2-t_1}\)
不同于TGN，这里有更具体的嵌入。将每个时间的年月日时的不同视作特征，通过两层MLP得到嵌入。而时间差也有三种，连接时间减记忆更新时间，查询时间减连接时间，以及查询时间减记忆更新时间。
Message Function
TGN中的message function被称作raw message function。对于每个连接，记录两组信息用于更新源点和目标点的记忆：
文中将这两组再通过两层全连接层，得到\(rmsg_i(t_l) \to msg_i(t_l)\)
一个点在一组边中会有很多信息。在TGN里，会对这些特征进行聚合。文中用自己提出的HTGN进行聚合。
Memory更新
利用GRU进行更新。点的memory作为初始隐藏状态，messages作为输入特征，更新后的隐藏状态作为更新后的Memory。这些信息中的最大时间戳被视为最新Memory更新时间。
Temporal Graph Attention
和TGN类似，提出的模型也会得到每个点任何时间的嵌入\(z_i(t)\)。相比于原本的temporal graph attention，会有一些微调。
具体模型：
对于其中的符号：
| 名称 | 含义 |
|---|---|
| \(t\) | 预测时间 |
| \(t_i\) | i点的记忆更新时间 |
| \(z_i(t)\) | i点t时时序嵌入 |
| \(\widetilde{z}_i(t_i)\) | 初始化时序嵌入。来自记忆\(m_i(t_i)\)和静态点嵌入\(sne_i\)的加权求和 |
| \(\phi_{src}\) | 预测时间和记忆更新时间之差的时间嵌入 |
| \(\phi_{ngh}\) | 预测时间和连接时间之差的时间嵌入 |
此外，还要选取一组i相关的，时间是最接近\(t_i\)的连接\(\{e_{ij}(t’_j), \dots, e_{ik}(t’_k)\}\)，得到它们的关系嵌入\(\{re_{ij}, re_{ik}\}\)，时间戳\(\{t’_j,\dots, t’_k\}\)和初始化时序点嵌入\(\{\widetilde{z}_j(t_j), \dots, \widetilde{z}_k(t_k)\}\)。
对于每种关系，都会有个MLP作为解码器，输入为两个点的特征，输出为是该类别的概率。
Bi-Time-Window 训练策略
在训练时，需要设置两个可调节的时间窗口来获取batch，分别为Memory Window \(L_m\)和Prediciton Window \(L_p\)，单位都是小时。
对于第\(\tau\)次的训练，都会选择这两时间窗口内的边 \(B^m_{\tau}\) 和 \(B^p_{\tau}\) 做训练。
更具体地说，在生成 \(B^m_{\tau}\) 时，会优先固定sample的数量而非窗口大小，在生成 \(B^p_{\tau}\) 时会生成负样本。负样本的生成有两种方式，一种是一比一随机生成边，一种是随机改变正样本中的部分信息（点，关系）
实验
原文地址：http://www.cnblogs.com/yujianke100/p/16825769.html
