文章目录
- 论文地址：http://yhwu.me/publications/dysat_wsdm20.pdf
- 源码：DySAT
- 来源：WSDM, 2020
- 关键词：self-attention, representation learning, dynamic graphs,
1 前言
该论文解决的是动态图中的结点表征问题。论文提出了DySAT（Dynamic Self-Attention），以自注意力机制捕捉动态图的结构的动态性。DySAT分别从两个方面捕捉动态性：structural neighborhoods和temporal dynamics，并且使用多头注意力来捕捉多方面的动态性。
2 问题定义
论文中使用图序列来表示动态图。关于动态图的建模，在这里插一句。
2.1 dynamic graph
动态图通常由两种建模方式：图序列（graph snapshots）和基于带时间戳的事件的图（time stamped events，类似于流图）。本质上来看这两种建模方式是等价的，是可以互相转化的。但是不同的建模形式针对这不同的应用场景。snapshot形式的动态图，直观上强调的整体性，图中结点/边的变化是为了整体的图而服务的，这种情况下我们更多的考虑的是作为一个整体的图的应用场景，例如在场景识别中、对图进行分类的任务中。而timestamped形式的动态图，对整体的考虑可能会不是那么强，更强调的是图中结点/边以及这些变化对任务的影响。
作者采用的是snapshots形式的动态图 G = { G 1 , . . . , G T } \mathbb{G} = \{\mathcal{G}^1, ..., \mathcal{G}^T\} G={G1,...,GT}。其中 T T T是时间步的数量， G t = ( V , E t ) \mathcal{G}^t = (\mathcal{V}, \mathcal{E}^t) Gt=(V,Et)。显然，该论文中动态图的结点是不变的，即不涉及结点的增加或删除。最终的目标就是学习图中每个结点在任意时间 t t t时的表征。
3 DySAT思路
DySAT的整体框架如上图所示。DySAT主要分为两个部分：Structural Self-Attention和Temporal Self-Attention。
3.1 Structural Self-Attention
这一部分与GAT中的注意力机制类似，想当于一个邻居结点信息汇聚层。对于每一个snapshot graph，Structural Self-Attention利用当前时刻各个结点的表征计算注意力再进行加权求和，计算公式如下：
z
v
=
σ
(
∑
u
∈
N
v
α
u
v
W
s
x
u
)
,
α
u
v
=
exp
(
e
u
v
)
∑
w
∈
N
v
exp
(
e
w
v
)
e
u
v
=
σ
(
A
u
v
⋅
a
T
[
W
s
x
u
∥
W
s
x
v
]
)
∀
(
u
,
v
)
∈
E
\begin{array}{c} z_{v}=\sigma\left(\sum_{u \in \mathcal{N}_{v}} \alpha_{u v} W^{s} x_{u}\right), \alpha_{u v}=\frac{\exp \left(e_{u v}\right)}{\sum_{w \in \mathcal{N}_{v}} \exp \left(e_{w v}\right)} \\ e_{u v}=\sigma\left(A_{u v} \cdot \boldsymbol{a}^{T}\left[\boldsymbol{W}^{s} \boldsymbol{x}_{u} \| \boldsymbol{W}^{s} \boldsymbol{x}_{v}\right]\right) \forall(u, v) \in \mathcal{E} \end{array}
zv=σ(∑u∈NvαuvWsxu),αuv=∑w∈Nvexp(ewv)exp(euv)euv=σ(Auv⋅aT[Wsxu∥Wsxv])∀(u,v)∈E
3.2 Temporal Self-Attention
这部分是为了捕捉动态图在时间上的变化模式。计算结点
v
v
v在
t
t
t时的表征时，将在
t
t
t之前的
v
v
v的表征作为temporal self-attention模块的输入，输出的是结点
v
v
v在各个事件点的表征（此时的表征考虑了动态性），计算公式如下：
Z
v
=
β
v
(
X
v
W
v
)
,
β
v
i
j
=
exp
(
e
v
i
j
)
∑
k
=
1
T
exp
(
e
v
i
k
)
e
v
i
j
=
(
(
(
X
v
W
q
)
(
X
v
W
k
)
T
)
i
j
F
′
+
M
i
j
)
\begin{array}{r} Z_{v}=\beta_{v}\left(X_{v} 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)} \\ e_{v}^{i j}=\left(\frac{\left(\left(X_{v} W_{q}\right)\left(X_{v} W_{k}\right)^{T}\right)_{i j}}{\sqrt{F^{\prime}}}+M_{i j}\right) \end{array}
Zv=βv(XvWv),βvij=∑k=1Texp(evik)exp(evij)evij=(F′
((XvWq)(XvWk)T)ij+Mij)
上式的形式与self-attention的形式一致。其中的
M
∈
R
T
×
T
\mathbf{M} \in \mathbb{R}^{T \times T}
M∈RT×T是一个掩码矩阵，
M
i
j
=
{
0
,
i
≤
j
−
∞
,
otherwise
M_{i j}=\left\{\begin{array}{ll} 0, & i \leq j \\ -\infty, & \text { otherwise } \end{array}\right.
Mij={0,−∞,i≤j otherwise
通常一个注意力捕捉的是一个方面的性质，为了捕捉动态图中多个方面的动态性，作者引入了多头注意力，Structural和Temporal都引入了多头注意力机制。
为了训练模型中的参数，论文使用类似神经语言模型中的共现率来优化参数，这点与word2vec和Node2vec中的损失函数很像，损失函数如下，
P
n
t
P_n^t
Pnt为负采样的结点：
L
=
∑
t
=
1
T
∑
v
∈
V
(
∑
u
∈
N
walk
t
(
v
)
−
log
(
σ
(
<
e
u
t
,
e
v
t
>
)
)
−
w
n
⋅
∑
u
′
∈
P
n
t
(
v
)
log
(
1
−
σ
(
<
e
u
′
t
,
e
v
t
>
)
)
)
\begin{aligned} L=\sum_{t=1}^{T} \sum_{v \in \mathcal{V}}\left(\sum_{u \in \mathcal{N}_{\text {walk }}^{t}(v)}-\log \left(\sigma\left(<\boldsymbol{e}_{u}^{t}, \boldsymbol{e}_{v}^{t}>\right)\right)\right.\\ &\left.-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)\right) \end{aligned}
L=t=1∑Tv∈V∑⎝⎛u∈Nwalk t(v)∑−log(σ(<eut,evt>))−wn⋅u′∈Pnt(v)∑log(1−σ(<eu′t,evt>))⎠⎞
DySAT是先进行structural self-attention再进行temporal self-attention，作者这样设计是因为：随着时间变化，图的结构是不稳定的。
4 方法的优势与局限性
4.1 优势
- 提出了structural和temporal self-attention来学习动态图中的结点表征
- 使用多头注意力机制捕捉多方面的动态性
- 注意力机制适用于并行
4.2 局限性
- 只能适用于结点不变化的动态图
- 以结点的共现率为损失函数引导模型的训练，这样的损失函数可能重点关注的是图的结构，对于动态性更丰富的图（如结点的特征的变化）是不够的
欢迎访问我的个人博客~~~