LRGCN-SAPE：时序图中的故障路径预测模型

论文标题｜ Predicting Path Failure In Time-Evolving Graphs
论文来源｜ KDD 2019
论文链接｜ https://arxiv.org/abs/1905.03994
源码链接｜ https://github.com/chocolates/Predicting-Path-Failure-In-Time-Evolving-Graphs

TL;DR

论文中提出一种新颖的神经网络架构 LRGCN (Long Short-Term Memory R-GCN) 来动态捕获时序图中两个相邻图快照间的关系和跨时间维度的节点特征融合，根据节点特征再提出一种基于自注意力机制的路径编码模型 SAPE(self-attentive path embedding)，可以将图中任意长度的路径编码成固定长度的向量再进行分类判断路径是否正常。实验中在通信网络和交通网络中验证了 LRGCN-SAPE 模型的有效性。

Problem Definition

给定节点集合 $V=\{v_1, v_2, \cdots, v_N\}$ 表示实体， $t$ 时刻实体间的联系可以使用邻接矩阵 $A^{t}$ 表示， $A_{i j}^{t} \in\{0,1\}$ 为节点 $v_j$ 到节点 $v_i$ 是否有边相连，注意是有向图； $X^{t}=\left\{x_{1}^{t}, x_{2}^{t}, \ldots, x_{N}^{t}\right\}$ 为每个节点 $t$ 时刻的观测特征， $x_{i}^{t} \in \mathbb{R}^{d}$ 表示节点 $v_i$ 在 $t$ 时刻 $d$ 个不同信号值。

graph snapshot： $t$ 时刻对应的邻接矩阵 $A^t$ 和特征信号 $X^t$ ；

Time-evolving graph：graph snapshot 组成的特征信号和邻接矩阵序列 $\boldsymbol{X}=\left\{X^{0}, X^{1}, \ldots, X^{t}\right\}$ ， $\boldsymbol{A}=\left\{A^{0}, A^{1}, \ldots, A^{t}\right\}$ ，每个节点 $v_i\in V$ 对应特征信号为时间序列 $\left\{x_{i}^{0}, x_{i}^{1}, \ldots, x_{i}^{t}\right\}$ 。

path：时序图中长度为 $m$ 的路径为 $p=\left\langle v_{1}, v_{2}, \ldots, v_{m}\right\rangle$ ，对应节点的特征信号为 $s^{t}=\left\langle x_{1}^{t}, x_{2}^{t}, \ldots, x_{m}^{t}\right\rangle$

需要解决的问题是给定 $t$ 时刻路径 $p$ ，根据历史 $M$ 步时间窗口数据判断未来 $F$ 步时间窗口该条路径是否存在问题，可以形式化的表示为一个分类任务：在训练集 $D$ 中学习到函数 $f(\cdot)$ 可以最小化目标函数

$\arg \min \mathcal{L}=-\sum_{\boldsymbol{P}_{j} \in D} \sum_{c=1}^{C} Y_{j c} \log f_{c}\left(\boldsymbol{P}_{j}\right)$

其中 $\boldsymbol{P}_{j}=\left(\left[s_{j}^{t-M+1}, \ldots, s_{j}^{t}\right], p_{j},\left[A^{t-M+1}, \ldots, A^{t}\right]\right)$ 是训练样本， $Y_{j} \in\{0,1\}^{C}$ 表示在未来 $F$ 步中路径是否正常， $f_{c}\left(\boldsymbol{P}_{j}\right)$ 表示预测路径是否正常的类别，论文中仅包含两种类型 $C=2$ 。

例如通信网络示例如下：

Algorithm/Model

论文中提出的 LRGCN-SAPE 模型架构图如下所示：

主要包括两部分：

LRGCN：捕获动态图结构和时序相关的节点特征。
SAPE：学习路径中节点重要性并将路径编码成固定长度向量来进行分类。

LRGCN

论文中基于 R-GCN(Relational GCN) 进行改进提出了 LRGCN(Long Short-Term Memory R-GCN) 模型，主要为了对时序图中节点进行嵌入表示，同时能够包含图结构特征和时序依赖特征。

论文 Modeling relational data with graph convolutional networks 中提出 R-GCN 主要是对知识图谱中的实体和关系进行预测，定义的特征卷积形式为

$Z=\sigma\left(\sum_{\phi \in R}\left(D_{\phi}^{t}\right)^{-1} A_{\phi}^{t} X^{t} W_{\phi}+X^{t} W_{0}\right)$

其中 $R=\{i n, o u t\}, A_{i n}^{t}=A^{t}$ 表示入边关系， $A_{i n}^{t}=(A^{t})^T$ 表示出边关系， $(D^t_{\phi})_{ii}=\sum_{j}\left(A_{\phi}^{t}\right)_{i j}$ ， $\sigma(\cdot)$ 表示激活函数。

为了将 R-GCN 泛化论文中对卷积形式简化成如下形式，将自环视为出度和入度线性组合

$Z_{s}=\sigma\left(\sum_{\phi \in R} \tilde{A}_{\phi}^{t} X^{t} W_{\phi}\right)$

其中 $\tilde{A}_{\phi}^{t}=\left(\hat{D}_{\phi}^{t}\right)^{-1} \hat{A}_{\phi}^{t}, \hat{A}_{\phi}^{t}=A_{\phi}^{t}+I_{N},\left(\hat{D}_{\phi}^{t}\right)_{i i}=\sum_{j}\left(\hat{A}_{\phi}^{t}\right)_{i j}$ 。

那么堆积两层 R-GCN 表达式如下

$\Theta_{s} \star g X^{t}=\sum_{\phi \in R} \tilde{A}_{\phi}^{t} \sigma\left(\sum_{\phi \in R} \tilde{A}_{\phi}^{t} X^{t} W_{\phi}^{(0)}\right) W_{\phi}^{(1)}$

📢 与原始 GCN 的区别在于

原始 GCN 处理的是无向图，会使 $W_{in}=W_{out}$ ;
原始 GCN 归一化方法是 $D^{-\frac{1}{2}} A D^{-\frac{1}{2}}$ 得到对称矩阵，但是有向图中邻接矩阵是非对称的因此使用 $D^{-1}A$ 进行归一化。
有向图可以视为一个多关系图，入边和出边。

以上仅考虑了静态图中节点嵌入，以下说明时序图中节点的嵌入。

主要分为两种类型的关系：inter-time 和 intra-time

对于 $t$ 时刻相邻的两个 graph snapshots，节点计算方式如下

$G_{-} \operatorname{unit}\left(\Theta,\left[X^{t}, X^{t-1}\right]\right)=\sigma\left(\Theta_{s} \star g X^{t}+\Theta_{h} \star g X^{t-1}\right)$

其中 $\Theta_{h}$ 表示图间固定的特征相关参数。接着为了处理时间窗口内 graph snapshots 间的特征关联，作者基于 LSTM 思路将隐藏特征进行关联

$H^{t}=\sigma\left(\Theta_{H} \star g\left[X^{t}, H^{t-1}\right]\right)$

其中 $\Theta_{H}$ 包括了 $\Theta_s,\Theta_h$ ，最终得到节点表示 $\Omega \in \mathbb{R}^{N \times u}$ ；

详细的计算公式可以参考论文，不再赘述，玄学的设计可以达到理论创新吧！

SAPE

这部分主要介绍如何将路径编码成固定长度的特征向量然后进行分类，还需要考虑路径中节点的重要性！

SAPE 主要的框架如下所示

对于路径 $P \in \mathbb{R}^{m \times u}$ ，首先使用 LSTM 捕获路径上节点间的依赖关系，

$\Gamma=\mathrm{LSTM}(P)$

输出节点特征维度为 $\Gamma \in \mathbb{R}^{m \times v}$ ，然后使用自注意机制学习节点的重要性

$S=\operatorname{softmax}\left(W_{h 2} \tanh \left(W_{h 1} \Gamma^{T}\right)\right)$

其中 $W_{h 1} \in \mathbb{R}^{d_{s} \times v}$ 和 $W_{h 2} \in \mathbb{R}^{r \times d_s}$ 表示权值矩阵，得到 $r$ 个视角的 $S \in \mathbb{R}^{r \times m}$ 节点重要性表示，将节点权重和特征相乘得到最终固定大小的路径向量表示 $E \in \mathbb{R}^{r \times v}$