4 Dynamic Graph Representation Learning Via Self-Attention Networks

link：https://arxiv.org/abs/1812.09430

Abstract

提出了在动态图上使用自注意力

Conclusion

本文提出了使用自注意力的网络结构用于在动态图学习节点表示。具体地说，DySAT使用（1）结构邻居和（2）历史节点表示上的自我注意来计算动态节点表示，虽然实验是在没有节点特征的图上进行的，但DySAT可以很容易地推广到特征丰富的图上。另一个有趣的方向是探索框架的连续时间泛化，以包含更细粒度的时间变化。

Figure and table

图1：DySAT的结构，采用了两个自注意力的结构，结构自注意力后接时序自注意力。黑色虚线表示新连接，蓝色虚线表示基于邻居的结构注意力

表1：数据集参数

表2：链接预测的sota（DynGEM在这确实不好 不过毕竟别人的卖点是稳定性）

图2：在不同时间步的表现对照

Introduction

照例提了一下将节点嵌入的方法效果不错，但是动态图有时间信息，前人的工作没有考虑时间信息或者只是用快照+时间正则化的的方法。

注意力机制在序列任务中获得了巨大成功。关键是学习一个函数，该函数可以进行加权求和权重即为注意力，同时关注与特定上下文最相关的部分。当注意机制使用单一序列作为输入和上下文时，通常称为自我注意

DySAT通过在邻居和时间序列上做注意力机制以反映图结构在不同数量的历史快照上的时间演化。与基于时间平滑度的方法相比，DySAT学习的注意力权重能够在细粒度节点级粒度上捕获时间依赖性。

Method

3 PROBLEM DEFINITION

定义了一些参数

动态图定义为一组时间步\(T\)下的快照\(\Bbb{G}=\{ \cal{G^{\mit{1}},...,G^{\mit{T}}}\}\)

其中每个快照表示为\(\cal{G_{\mit{t}}=(V,E^{\mit{t}})}\)

\(\cal{V}\)表示为所有时间步下的共享节点集

\(\cal{E}^\mit{t}\)表示为\(t\)时间下的边集

\(A^t\)表示为\(t\)时间下的邻接矩阵

节点\(v \in \cal{V}\)在\(t = 1,2,...,T\)时间下的嵌入表达为\(\boldsymbol{e}_{v}^{t} \in \mathbb{R}^{d}\),\(d\)是嵌入的维度即向量长度,

4 DYNAMIC SELF-ATTENTION NETWORK

DySAT由两个组件构成：结构注意力块、时间注意力块。与已有的注意机制研究类似，采用多头注意来提高模型容量和稳定性。

DySAT的组成是结构自注意力块后接着时间注意力块，如图1。其中每个组件可能包含对应层类型的多个堆叠层。结构块（结构自注意力块，下同）通过自注意力聚合提取邻居特征，为快照计算该节点嵌入。这些嵌入作为时间快的输入提供，时间块在多个时间步上出现，捕捉图形中的时间变化。

4.1 STRUCTURAL SELF-ATTENTION

基于GAT的思路，结构块的注意力公式如下

\[\boldsymbol{z}_{v}=\sigma\left(\sum_{u \in \mathcal{N}_{v}} \alpha_{u v} \boldsymbol{W}^{s} \boldsymbol{x}_{u}\right), \quad \alpha_{u v}=\frac{\exp \left(\sigma\left(A_{u v} \cdot \boldsymbol{a}^{T}\left[\boldsymbol{W}^{s} \boldsymbol{x}_{u} \| \boldsymbol{W}^{s} \boldsymbol{x}_{v}\right]\right)\right)}{\sum_{w \in \mathcal{N}_{v}} \exp \left(\sigma\left(A_{w v} \cdot \boldsymbol{a}^{T}\left[\boldsymbol{W}^{s} \boldsymbol{x}_{w} \| \boldsymbol{W}^{s} \boldsymbol{x}_{v}\right]\right)\right)} \]

参数解释：

\(\mathcal{N}_{v}=\{u \in \mathcal{V}:(u, v) \in \mathcal{E}\}\)表示为节点\(v\)的邻居\(u\)集合

\(\boldsymbol{W}^{s} \in \mathbb{R}^{D \times F}\)可训练权重，维度是\(D \times F\)

\(a \in \mathbb{R}^{2 F}\)权重向量(原文这里写的维度写错成2D)

||：拼接操作

\(α_{uv}\)：边\(uv\)的注意力权重

在上式中先使用LeakyRELU计算注意力权重，接着使用ELU计算输出表示

上面两种激活函数都是RELU的改版，RELU在值小于0时容易造成梯度消失，所以有一些变种RELU，主要还是改动负半轴的的函数

LeakyRELU将负半轴改为$ x<0 :LeakyRELU(x) = ax $，其中a是一个设定的较小常数

ELU将负半轴改为$ x<0 :ELU(x) = e^x-1 $，其中a是一个设定的较小常数

在我们的实验中，我们使用稀疏矩阵来实现对邻居的mask自注意力。

4.2 TEMPORAL SELF-ATTENTION

该层的输入是特定节点v在不同时间步的一系列表示。

该层的输入是\(\left\{\boldsymbol{x}_{v}^{1}, \boldsymbol{x}_{v}^{2}, \ldots, \boldsymbol{x}_{v}^{T}\right\},\boldsymbol{x}_{v}^{t} \in \mathbb{R}^{D^{\prime}}\)其中\(T\)是时间步数，\(D^{\prime}\)是输入向量维度

该层的输出是\(\left\{\boldsymbol{z}_{v}^{1}, \boldsymbol{z}_{v}^{2}, \ldots, \boldsymbol{z}_{v}^{T}\right\},\boldsymbol{z}_{v}^{t} \in \mathbb{R}^{F^{\prime}}\)其中\(T\)是时间步数，\(F^{\prime}\)是输入向量维度

将以上的向量表示改变为矩阵：

\[\boldsymbol{X}_{v} \in \mathbb{R}^{T \times D^{\prime}} \text { and } \boldsymbol{Z}_{v} \in \mathbb{R}^{T \times F^{\prime}} \]

时间自注意力机制的目标是捕获在图结构上的多个时间步下的时序信息变化，在时间\(t\)下的节点\(v\)嵌入\(\boldsymbol{x}_{v}^{t}\)表示为\(v\)周围当前局部结构的编码.使用\(\boldsymbol{x}_{v}^{t}\)作为query去关注历史表示（<t） ，跟踪v周围的本地社区的演变。因此，时间自注意有助于学习节点在不同时间步上的各种表示之间的依赖关系。、

为了计算\(t\)处节点\(v\)的输出表示，使用缩放的点积注意力，其中查询、键和值被设置为输入节点表示。

说一下为什么要使用缩放的点积注意力（为什么要除\(\sqrt{F^{\prime}}\)）：https://www.zhihu.com/question/339723385/answer/782509914

其中其中查询、键和值被设置为输入节点表示（qkv矩阵）。首先使用线性投影矩阵\(\boldsymbol{W}_{q} \in \mathbb{R}^{D^{\prime} \times F^{\prime}}, \boldsymbol{W}_{k} \in \mathbb{R}^{D^{\prime} \times F^{\prime}} \text { , } \boldsymbol{W}_{v} \in \mathbb{R}^{D^{\prime} \times F^{\prime}}\)将qkv分别进行投影。具体公式如下

\[\boldsymbol{Z}_{v}=\boldsymbol{\beta}_{\boldsymbol{v}}\left(\boldsymbol{X}_{v} \boldsymbol{W}_{v}\right), \quad \beta_{v}^{i j}=\frac{\exp \left(e_{v}^{i j}\right)}{\sum_{k=1}^{T} \exp \left(e_{v}^{i k}\right)}, \quad e_{v}^{i j}=\left(\frac{\left(\left(\boldsymbol{X}_{v} \boldsymbol{W}_{q}\right)\left(\boldsymbol{X}_{v} \boldsymbol{W}_{k}\right)^{T}\right)_{i j}}{\sqrt{F^{\prime}}}+M_{i j}\right) \]

参数解释：

\(\boldsymbol{\beta}_{\boldsymbol{v}} \in \mathbb{R}^{T \times T}\)是注意力权重矩阵，由dot-product attention构成

\(\boldsymbol{M}_{\boldsymbol{v}} \in \mathbb{R}^{T \times T}\)是一个掩模矩阵，防止模型注意到未来的时间步。当\(M_{i j}=-\infty\)，softmax就会让这次计算出来的注意力权重为0

所以将\(\boldsymbol{M}\)定义为

\[M_{i j}=\left\{\begin{array}{ll} 0, & i \leq j \\ -\infty, & \text { otherwise } \end{array}\right. \]

4.3 MULTI-HEAD ATTENTION

本文还采取了多头注意力的机制（类似cnn中的改变通道数，对节点的每个表示使用多通道叠加的概念）

我们在结构和时间自我注意层中使用多个注意头，然后连接：

结构多头自注意力：\(\boldsymbol{h}_{v}=\operatorname{Concat}\left(\boldsymbol{z}_{v}^{1}, \boldsymbol{z}_{v}^{2}, \ldots, \boldsymbol{z}_{v}^{H}\right) \quad \forall v \in V\)

时间多头自注意力：\(\boldsymbol{H}_{v}=\operatorname{Concat}\left(\boldsymbol{Z}_{v}^{1}, \boldsymbol{Z}_{v}^{2}, \ldots, \boldsymbol{Z}_{v}^{H}\right) \quad \forall v \in V\)

\(\boldsymbol{h}_{v} \in \mathbb{R}^{F} \text { ， } \boldsymbol{H}_{v} \in \mathbb{R}^{T \times F^{\prime}}\)

其中\(H\)是注意力头的数目，请注意，虽然结构注意应用于单个快照，但时间注意在多个时间步上运行。

4.4 DYSAT ARCHITECTURE

这节介绍模型结构，整个模型由三个模块构成：

结构块，时序块，图上下文预测

该模型以一组T图快照作为输入，并在每个时间步生成节点嵌入

结构注意力块：该模块由多个堆叠的结构自我注意层组成，用于从不同距离的节点中提取特征。如图1所示，在具有共享参数的不同快照上独立应用每一层，以在每个时间步捕获节点周围的局部邻域结构。该层的输出为\(\left\{\boldsymbol{h}_{v}^{1}, \boldsymbol{h}_{v}^{2}, \ldots, \boldsymbol{h}_{v}^{T}\right\}, \boldsymbol{h}_{v}^{t} \in \mathbb{R}^{f}\)

时间注意力块：通过位置嵌入（position embedding）为时间注意力模块提供顺序信息。将位置嵌入表示为为\(\left\{\boldsymbol{p}^{1}, \ldots, \boldsymbol{p}^{T}\right\}, \boldsymbol{p}^{t} \in \mathbb{R}^{f}\)

然后将位置嵌入与结构注意块的输出相结合\(\left.(\boldsymbol{h}_{v}^{1}+\boldsymbol{p}^{1}, \boldsymbol{h}_{v}^{2}+\boldsymbol{p}^{2}, \ldots, \boldsymbol{h}_{v}^{T}+\boldsymbol{p}^{T}\right)\)用于跨越多个时间步的节点v的时序表示。 他的块也遵循类似的结构，有多个堆叠的时间自我注意层。最终层的输出传递到位置前馈层，以给出最终节点表示\(\left\{\boldsymbol{e}_{v}^{1}, \boldsymbol{e}_{v}^{2}, \ldots, \boldsymbol{e}_{v}^{T}\right\} \forall v \in V\)

图上下文预测：为了确保学习到的表示同时捕获结构和时间信息，我们定义了一个目标函数，该函数跨多个时间步保留节点周围的局部结构。使用节点\(v\)在\(t\)时刻的动态表示\(e_v^t\)去预测在\(t\)时刻\(v\)节点周围出现在局部邻域中的节点。特别的，使用BCE损失在每个时间步以鼓励节点在固定长度的随机游走共同出现以具有相似的表示，损失如下

\[L_{v}=\sum_{t=1}^{T} \sum_{u \in \mathcal{N}_{w a l k}^{t}(v)}-\log \left(\sigma\left(<\boldsymbol{e}_{u}^{t}, \boldsymbol{e}_{v}^{t}>\right)\right)-w_{n} \cdot \sum_{u^{\prime} \in P_{n}^{t}(v)} \log \left(1-\sigma\left(<\boldsymbol{e}_{u^{\prime}}^{t}, \boldsymbol{e}_{v}^{t}>\right)\right) \]

参数解释：

σ：sigmoid

< . >：向量点乘

\(\mathcal{N}_{\text {walk }}^{t}(v)\)：节点v在快照t下时，定长的随机游走后的节点集

\(P^t_n(v)\)：节点v在快照t下时，负采样分布

\(w_n\)：负采样率 可调节参数

Experiment

5 EXPERIMENTS

选取链接预测作为模型性能表示

5.1 DATASETS

数据集是4个，两个通信网络，两个二部图评分网络

具体见表1

5.2 EXPERIMENTAL SETUP

在快照\(\left\{\mathcal{G}^{1}, \ldots, \mathcal{G}^{t}\right\}\)上学习节点表示\(\left\{e_{v}^{t}, \forall v \in \mathcal{V}\right\}\)后，预测快照\(\mathcal{G}^{t+1}\)的链接。论文比较了不同的模型，基于它们将每个示例（节点对）正确分类为链接和非链接的能力。为了进一步分析预测能力，还评估了新的链路预测，重点是在每个时间步出现的新链路（附录B）。

在\(\mathcal{G}^{t+1}\)做链接预测时，使用真实链接和相同数量的负样本采样作为评估示例。用一个占比20%的固定验证集去调整超参数，在后面会丢弃掉这部分数据。我们随机抽取25%的样本进行训练，并使用剩余的75%作为测试集。重复10次随机试验，并在结果中报告平均性能。

除非有明文规定，对于所有的方法，节点对的特征表示都是使用Hadamard积\(\left(\boldsymbol{e}_{u}^{t} \cdot \boldsymbol{e}_{v}^{t}\right)\)Hadamard算子计算两个向量的元素乘积，并密切反映学习节点嵌入中广泛使用的内积运算。我们使用ROC曲线下面积（AUC）分数评估链路预测的性能。我们还在附录表6中报告了平均精度分数。

优化器：Adam。对于 Enron，在结构块和时间块中使用一个单层，每层由16个注意力头组成，每个注意力头计算8个特征（总共128个维度）。在其他数据集中，使用了两个自注意力层，分别有16个和8个头部，每个头部计算16个特征（层大小为256，128）。该模型最多可训练200个轮次，批量大小为256个节点，并选择验证集中性能最好的模型进行评估。

5.3 BASELINE

除了和动态图算法比较，还比较了几种静态图嵌入方法，以分析使用时间信息进行动态链路预测的收益。为了与静态方法进行公平比较，我们通过构建一个到时间t的聚合图来合并快照的整个历史，其中每个链接的权重被定义为到时间t为止的累积权重，与它的发生时间无关。我们为所有基线使用作者提供的实现，并设置最终嵌入维度d=128。

对比了静态方法的node2vec,graphSage,graph autoencoders。在GraphPage中使用不同的聚合器进行实验，即GCN、平均池、最大池和LSTM，以报告每个数据集中性能最好的聚合器的性能。为了与GAT进行公平比较，GAT最初只对节点分类进行实验，论文在GraphSAGE中实现了一个图形注意层作为额外的聚合器，用GraphSAGE+GAT表示。本文还将GCN和GAT训练为自动编码器，用于沿着（Modeling polypharmacy side effects with graph convolutional networks）的建议线路进行链路预测，分别用GCN-AE和GAT-AE表示。

在动态环境中，根据最新的动态图嵌入研究，包括Know Evolve、DynamicRiad和DynGEM，对DySAT进行评估。所有方法的超参数调整详情见附录F。

5.4 EXPERIMENTAL RESULTS

在每个时间步t对模型进行评估，方法是将单独的模型训练到快照t，并在t+1对每个t进行评估，总结了表2中所有模型的微观和宏观平均AUC分数（跨越所有时间步）。从结果中，我们观察到，与所有数据集的最佳基线相比，DySAT实现了3–4%宏观AUC的一致增益。此外，还比较了每个时间步的模型性能（图2），以深入了解它们的时间行为。论文对DySAT的性能进行了优化，使其比其他方法更稳定。这种对比在通信网络（安然和UCI）中表现得尤为明显，观察到静态嵌入方法在特定时间步的性能急剧下降。

在ML-10M上，使用一台配备Nvidia Tesla V100 GPU和28个CPU内核的机器，每小批DySAT的运行时间为0.72秒。相比之下，没有时间注意的模型变量（附录a）需要0.51秒，这说明时间注意的成本相对较低。

6 DISCUSSION

原文提出了一些观察，这里直接翻译了：

实验结果为不同图形嵌入技术的性能提供了一些有趣的观察和见解。

首先，观察到GraphSAGE在不同的数据集上实现了与DynamicRiad相当的性能，尽管它只接受静态图的训练。一种可能的解释是，GraphSAGE使用可训练的邻居聚合函数，而DynamicRiad使用基于Skipgram的方法，并增加了时间平滑度。 所以结构和时间建模与表达聚合功能（如多头注意）的结合，是DySAT在动态链接预测方面始终表现优异的原因。还观察到node2vec实现了与时间信息无关的一致性能，这证明了二阶随机游走采样的有效性。这一观察结果为应用抽样技术进一步改善DySAT指明了方向。

还观察到node2vec实现了与时间信息无关的性能，这证明了二阶随机游走采样的有效性

在DySAT中，我们采用结构注意层，然后是时间注意层。我们之所以选择这种设计，是因为图形结构随着时间的推移并不稳定，这使得在时间注意层之后直接使用结构注意层是不可行的。论文还考虑了另一种替代设计选择，即按照类似于（Shen等人，2018年）的策略，在邻居和时间这两个维度上一起使用自我关注。实际上，由于多个快照中每个节点的邻居数量可变，这在计算上会非常昂贵。

在当前设置中，使用稀疏矩阵将每个快照的邻接矩阵存储在内存中，这在缩放到大型图时可能会带来内存挑战。在未来，作者计划沿着GraphSAGE的路线，探索具有记忆效率的小批量训练策略的DySAT。此外，我们开发了一个增量自我注意网络（IncSAT），作为DySAT的直接扩展，它在计算和记忆成本方面都是有效的。正如附录E所报告的，我们的初步结果是有希望的，这为将来探索增量（或流式）图形表征学习的自我注意架构打开了大门。我们还评估了DySAT在多步链路预测或预测方面的能力，并观察到与现有方法相比平均6%AUC的显著相对改善，如附录C所述。

Summary

这篇论文的embedding是使用独热码作为输入，引入了自注意力机制并尝试在动态图上使用，并且还引入的pos嵌入的思路(Convolutional sequence to sequence learning)以保证顺序，读了四篇论文，慢慢开始有感觉了，现在读一篇论文加上理解内容已经比原来快很多了，很多参数和公式看一眼就知道咋回事了，基本上都是翻来覆去的各种搭积木