Neural Temporal Walks: Motif-Aware Representation Learning on Continuous-Time Dynamic Graphs
介绍
该文针对的是Continuous-Time Dynamic Graphs，也就是说边和点会随着时间增删
文章认为当前时序图神经网络（DGNNs）存在两大挑战：
- 动态图不能用常规静态GNN。
- 时序事件的不均匀分布。
这项工作是CAW（ICLR 21）的改良。具体区别：
- 在采样时除了时间信息，还会考虑其他更多信息
- 这个工作提出了一种motif的嵌入方法
- 使用pretext task作为训练目标
定义
本文使用的是时序交互流\(\mathcal{G}=\{(e_i, t_i)\}^N_{i=1}\)，每次交互都有两个点和一个时间戳\((e_i, t_i):=(\{u_i, v_i\}, t_i), t_i \in \mathbb{R}^+\)。
文章的目标就是得到某个\(t\)时刻的\(u\)和\(v\)的特征\(\overline{h}_u\)和\(\overline{h}_v\)，再通过一个\(\hat{y}_{u,v,t}=clf(\overline{h}_u, \overline{v}_v)\)预测他们之间是否会出现关联。
模型
时序游走：\(t\)时刻之前有交互的一个点\(u\)，提取它的所有交互\(\mathcal{G}_{u,t}=\{(e, t') | t' < t, u \in e, (e, t') \in \mathcal{G}\}\)。定义从\(u\)出发的随机游走:
\[w_0 := u,\ t_0 := t,\\ W = \{(w_i, t_i) | i \in \mathbb{N}, 0 \leq i \leq l, t_0 > t_1 > \dots > t_l, \\ (\{w_i, w_{i-1}\}, t_i) \in \mathcal{G}_{w_{i-1}, t_{i-1}}\ for\ i\ \geq 1\} \]其中\(l\)是游走长度。其实就是在游走的时候增加一个必须要向更新时间方向走的限制。
文中会用W[i][0]和W[i][1]来代表\((w_i, t_i)\)。
这样每个点的随机游走采样结果，其实就可以视作motif。
匿名游走：给一个点\(w\)和一个游走\(W\),匿名化操作：
\[A(w; W) = |\{v_0, \dots, v_{i^*}|v_i \in W\}| \]其中\(i^*\)是满足\(v_{i^*}=w\)的最小索引。
这步操作实际上就是给每个游走中的点重新编号，让模型不能知道不同游走间是否有同一个点，而只让模型去关注结构信息。
此外，文章后面还提到了一个binary的版本。由于目标就是去预测两点的相互作用，所以对于根节点\(u\)和\(v\)和它们的游走组\(M_u\)和\(M_v\)，存在的共同游走\(W \in M_u \cup M_v\)，匿名操作可以是：
\[A(w;M_u, M_v) = A(w;M_u)||A(w;M_v) \]后面会用\(\widehat{W}\)来表示已经匿名了的游走组。
时序游走采样
以往的工作在计算下一个点的概率的方法是\(\exp(\alpha(t'-t))\)，也就是时间越接近越有可能选择。
文中提出了一个增加考虑拓扑信息和树遍历属性的采样方式。
动机有两个：
- 越接近的点应该采样概率越大（\(\propto \exp(\alpha(t'-t))\)）
- 度越大的点越应该被采样（\(\propto \exp(-\beta/d)\)）
这两个概率在实际使用时会进行归一
算法伪代码：
算法1的做法还有隐患，它会过分鼓励进行深度优先搜索，进而难以进行均匀的motif采样，所以增加了第三个概率（\(\propto \exp( - \gamma s_a)\)），这个\(s_a\)指的就是点\(a\)已遍历的次数，也就是被采样的次数越多，再次被采样的概率就越小。
编码
其中的ODESolve是GRU：
\[z_t = \sigma(W_zh_{t-1}+b_z)\\ r_t = \sigma(W_rh_{t-1}+b_r)\\ \hat{h}_t = tanh(W_h(r_t \odot h_{t-1})+b_h)\\ h_t = z_t \odot \hat{h}_t + (1-z_t) \odot h_{t-1} \]最后的\(g_{\phi}\)是RNN网络
Loss部分，就涉及到之前说过的pretext task了。
\[L=-\mathbb{E}[\log\frac{\exp(sim(\overline{h}_u, \overline{h}_v))}{\exp(sim(\overline{h}_u, \overline{h}_v))+\sum_{v' \in \mathcal{G}, v' \neq v}\exp((sim(\overline{h}_u, \overline{h}_{v'})))}]\\ sim(\overline{h}_u, \overline{h}_v) = sigmoid(MLP(\overline{h}_u, \overline{h}_a, \xi)) \]也就是说，得到两点特征后，用mlp做预测。预测结果(0,1)做e的指数，范围是(1,e)。log里最理想的情况是\(\frac{e}{e+n}\)，其中n是负样本数量。这样的loss确实会比一般的更难学习。
此外，如果提供了点和边的特征，可以在RNN里拼入MLP得到的结果中。
整体的训练过程：
实验
数据集
实验结果
