ICML 2021 | 基于因果匿名游走的时序网络归纳表示学习模型

论文标题｜ Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks
论文来源｜ ICML 2021
论文链接｜ https://arxiv.org/abs/2101.05974
源码链接｜ https://github.com/snap-stanford/CAW

TL;DR

为了学习到时序网络中的三元闭包规律，论文中提出了因果匿名游走 Causal Anonymous Walks (CAWs) 的方法对时序网络进行归纳表示学习，CAWs 主要是基于时序网络进行随机游走，以此捕获时序网络中 motifs 来表示网络的动态变化；CAWs 采用新的匿名策略，以节点的命中次数代替节点的区分特征，以保持算法的归纳性能力。为了学习 CAWs 特征，论文中还提出了模型 CAW-N 进行编码，可以达到常量级的内存和时间开销。实验部分采用 6 个真实网络数据集中验证了 CAW-N 在归纳学习的链路预测任务中平均优于当前 baselines 15% AUC，同时在 5-6 个数据集上的直推学习也优于当前 baselines。

Problem Definition

在复杂网络领域解释下上述名词：

三元闭包规律：三元闭包是一种非常直观和自然关系的描述，即当 B 和 C 有一个共同的朋友 A 那么 B 和 C 很有可能成为朋友。
motifs：与随机网络相比，出现频繁的 subgraph 结构。

时序网络由带有时间标签的边组成 $\mathcal{E}=\left\{\left(e_{1}, t_{1}\right),\left(e_{2}, t_{2}\right), \ldots\right\}$ ，其中边 $e_i$ 表示 $t$ 时刻节点 $u_i, v_i$ 间的事件。

以 $\mathcal{E}_{v, t}=\left\{\left(e, t^{\prime}\right) \in \mathcal{E} \mid t^{\prime}\lt t, v \in e\right\}$ 表示 $t$ 时刻前节点 $v$ 连接的边。随机游走序列表示为

$W=\left(\left(w_{0}, t_{0}\right),\left(w_{1}, t_{1}\right), \ldots,\left(w_{m}, t_{m}\right)\right), t_{0}\geq t_{1}\geq \cdots\geq t_{m},\left(\left\{w_{i-1}, w_{i}\right\}, t_{i}\right) \in \mathcal{E}$

主要任务就是根据历史的边信息来预测未来两个节点间是否存在边，即链路预测。

Algorithm/Model

CAW 模型有非常重要的两个属性，整体过程如下图所示

主要包括两部分：

因果提取「Causal Extraction」，生成的每个 walk 表示时序网络中的 motif。
匿名策略「Set-based Anonymization」，去除节点身份以适应归纳学习。
相比以往的匿名游走不共享节点标识，文章用节点的命中次数来代替节点身份，能够对多次游走进行区分。效果区别如下

因果关系提取

此外，在进行随机游走时，文章提出了新的边采样策略来采样随机游走，并最终提出编码策略对游走进行编码。算法的伪代码如下所示

文章通过确定一个时间，反向从过去的交互中进行采样生成游走路径，并引入了一个非负超参数 $\alpha$ 来控制选择边的概率，这个概率与事件有关，即 $exp(a(t-t_p))$ 。其中， $t$ 是当前时间， $t_p$ 是先前时间， $\alpha$ 越大越意味着发生时间较近的交互越容易被选中，而当 $\alpha$ 为0时，即随机选择。此外，文章还在附录中给出了更加灵活的采样策略，避免了每次游走都要对每条边进行概率的计算。

文章提出的采样策略分为两部分：在线概率计算和迭代采样。其中，在线概率计算是对一条边 $(u,v)$ 计算一对概率，即在众多边中选择该边的权重，有兴趣可以参考原文中计算公式不再细述哦。

集合匿名策略

基于节点 $u,v$ 随机游走后得到集合 $S_u, S_v$ ,算法可以对任意节点 $w$ 进行匿名化标识，这些节点至少会在一次游走中出现，它们被定义为：

$I_{C A W}\left(w ;\left\{S_{u}, S_{v}\right\}\right)$

与匿名游走不同，因果关系的匿名游走可以捕捉不同游走路径间的关系，从而作为一个重要的枢纽反映出时序网络的动态变化规律。在此，文章进行了举例说明如下：

假设在节点交互过程中存在着一条规律：一个节点只有在另一个节点与其交互至少两次的情况下才会与其他节点交互。那么捕捉了因果关系的匿名游走CAW就要比单纯的CAW更能够捕捉到这一规律。

因果关系匿名游走还在匿名化节点身份时采取了命中次数的策略；可以理解为，S中存放的是M个m步基于节点w开始的随机游走。那么其中出现的节点，都可以用出现位置计数的方式来表示。针对单次游走而言，节点的 id 就可以替换为在S中游走各位置出现的次数编码。

CAW 编码

论文中对每次匿名游走，都编码成向量的形式：

$\operatorname{enc}(\hat{W})=\operatorname{RNN}\left(\left\{f_{1}\left(I_{C A W}\left(w_{i}\right)\right) \oplus f_{2}\left(t_{i-1}-t_{i}\right)\right\}_{i=0,1, \ldots, m}\right), \text { where } t_{-1}=t_{0}$

该编码分为两部分：一部分是基于游走过程中位置计数的编码，另一部分是对时间的编码，对于一些有附加信息的网络，同样可以将其编码为向量进行结合。

对前一部分，由于文章设定的游走路径一般为1-5，因此使用基本的 RNN 结构就能够完成很好地编码效果：

$f_{1}\left(I_{C A W}\left(w_{i}\right)\right)=\operatorname{MLP}\left(g\left(w, S_{u}\right)\right)+\operatorname{MLP}\left(g\left(w, S_{v}\right)\right)$

对后一部分，文章使用随机傅里叶变换来编码， $\omega$ 为学习参数；

$f_{2}(t)=\left[\cos \left(\omega_{1} t\right), \sin \left(\omega_{1} t\right), \ldots, \cos \left(\omega_{d} t\right), \sin \left(\omega_{d} t\right)\right]$

在对单条游走编码完成后，最终要回到对游走集合的编码，文章采用两种编码方式：

基于平均化编码
$\operatorname{Mean}-\mathrm{AGG}\left(S_{u} \cup S_{v}\right): \frac{1}{2 M} \sum_{i=1}^{2 M} \operatorname{enc}\left(\hat{W}_{i}\right)$
基于自注意力机制
$\text {Self-Att- } \mathrm{AGG}\left(S_{u} \cup S_{v}\right): \frac{1}{2 M} \sum_{i=1}^{2 M} \operatorname{softmax}\left(\left\{\operatorname{enc}\left(\hat{W}_{i}\right)^{T} Q_{1} \operatorname{enc}\left(\hat{W}_{j}\right)\right\}_{1<j<n}\right) \operatorname{enc}\left(\hat{W}_{i}\right) Q_{2}$