MSHTrans文献速递(KDD, 2025)
MSHTrans: 带有时间序列分解的多尺度超图Transformer实现时间异常检测。
Abstract
目前已有的异常检测方法在理解重构模型的机理过程中存在2个主要挑战：1. 对于时间标签的长期和短期依赖性的挖掘不足；2. 同时挖掘长期与短期特征的框架缺失。为了解决这个问题，作者提出了MSHTrans，其充分使用了超图建模多阶时间依赖关系方面的能力。
作者的模型使用了多尺度下采样来获取互为补充的细粒度和粗粒度表示，并与可训练的超图神经网络结合，该网络可以自适应地学习时间标签之间的关联性。这个框架进一步结合了时间序列分解来从多粒度特征中系统地提取周期性与趋势性成分。
Introduction
时间序列异常检测是真实世界领域中的一个基础工作，尤其是在工业、医疗和金融领域，该领域主要有3大问题：1. 大规模数据；2. 异质性；3. 多模态特征。为了解决这3大问题，目前已有的模型可以被简单分为2类：基于预测的方法：该方法采用历史数据预测未来数据并根据预测误差来定量评估异常，但是这个方法对于时间特征快速改变的情形并不适用；基于重构的方法在近年获得重视，其通过从学习到的潜在表示重构数据并与真实数据比较以进行异常检测。
以上两种方法均需要能够捕捉长期和短期时间依赖性的模型，考虑到时间相关性的潜在性，最近的研究都使用了GNN来构建基于相似性的时间标签相关性。超图通过灵活、无度限制的超边（hyperedge）连接多个时间戳，从而实现高阶交互建模，突破了普通图结构在表示能力上的局限。此外，在实际的时间序列应用中，每个时间戳的传感器测量值往往同时表现出短期波动与长期趋势之间的复杂交互。这种多尺度的时间依赖性对传统的固定图方法构成了根本性限制，因为这些方法在拓扑结构上的刚性约束使其难以有效刻画不同粒度下的时间模式。因此，如何利用超图构建可训练的长短期时间戳关联，成为亟需解决的关键问题。
在时间序列重构任务中，短期关系有助于模型从相邻时间戳中传播局部关键特征，而长期关系则从全局角度为序列重建提供支持。除了由超图在长距离相关性中带来的全局信息，分解时间序列也可以为粗颗粒度的全局模型重建引入季节与趋势信号。提出的模型通过双相重构机制构建：(1) 粗颗粒度重建使用了基于超图的长期时间依赖性和序列固有的季节性与趋势性；(2) 高精度的重构是通过基于超图的短期时间依赖性构建，通过残差模式分析来实现本地细化。最后，文章的难点在于：如何有效将这两种方法融合并解释这样分层重构机制可以本质上提升准确率的原因。
Preliminary
多变量时间数据如下定义：$\mathbf{X}\in \mathbb{R}^{T\times D}$其中T是时间序列的长度，D为变量数，为了捕捉时间序列的趋势，产生上下文窗$\mathbf{W}^{(t)}\in \mathbb{R}^{S \times D}$在第t个时间点，其中$\mathbf{W}^{(t)}=[\mathbf{X}^{(t-S+1)};\dots; \mathbf{X}^{(t)}]for \space t \geq t$。其中S为预定义的最大窗宽，提出的模型旨在重构输入窗W，并基于W产生异常评分S，异常检测指示器$y = { y_1, \cdots, y_T }$通过异常评分和阈值计算，其中$y_{t}\in {0,1}$且$y_{t}=1$代表异常时间标签。
The Proposed Model
Overview
MSHTrans使用了多尺度编码器，该编码器用于使用可训练超图模型将输入数据编码。可学习的不同尺度的季节性特征和趋势信息最终聚合。另外MSHTrans使用了解码器来基于超图的相关性和编码器学习到的潜在特征来重构原始的时间序列。最终，模型根据解码器重构的质量来计算异常评分，以此预测异常的时间标签。我们接下来继续丰富MSHTrans的框架。
Multi-Scale Window Generator
为了捕捉L个不同颗粒度的潜在特征，一个多尺度窗生成器被提出来构建窗$\mathbf{W}^{(t)}_{(s)}\in \mathbb{R}^{N_{s}\times D}$简写为$\mathbf{W}_{(s)}$在尺度为s时。$\mathbf{W}^{\text{conv}}_{(0)} =\mathbf{W}^{\text{sample}}_{(0)} =\mathbf{W}$。生成器如下定义：
$$
\begin{array}{c}\mathbf{W}_{(s)}^{\text {conv }}=\operatorname{Conv1D}\left(\mathbf{W}_{(s-1)}^{\text {conv }} \mid \Theta_{(s-1)}, \mathcal{K}\right), \\ \mathbf{W}_{(s)}^{\text {sample }}=\operatorname{DownSample}\left(\mathbf{W}_{(s-1)}^{\text {sample }} \mid \mathcal{K}\right), \\ \mathbf{W}_{(s)}=\left[\mathbf{W}_{(s)}^{\text {conv }}, \mathbf{W}_{(s)}^{\text {sample }}\right],\end{array}
$$
其中$[\cdot,\cdot]$为concat操作，$\text{Conv1D}$为1-D卷积操作，其具有参数$\Theta_{(s-1)}$与$\mathcal{K}$，$\text{DownSample}(\cdot)$代表以从s-1的尺度下以$\mathcal{K}$的间隔进行采样，因此我们有$N_{s}=\left\lfloor\frac{N_{s-1}}{\mathcal{K}}\right\rfloor$，特别的，最大大小$N_{0}=S$。以上式子代表，高尺度的信息是从低尺度的信息计算而来。s处对于点的相关性对应于s-1处对于组的相关性（当s>=1）。当s=0时，对于点的相关性就是每个时间标签之间高精度的相关性。因此，提出的MHSTrans可以探索高尺度的窗和粗颗粒度时间之间的相关性和低尺度的窗和细颗粒度时间之间的相关性。
Hypergraph Transformer
为了捕捉复杂的长短期相关性，我们构建了超图transformer: $\mathcal{G}_{(s)}=\left \{ \mathcal{V}_{(s)}, \mathcal{E}_{(s)} \right \}$在尺度为s时，在这里$\mathcal{V}_{(s)}={v_{1},\dots,v_{N_{s}}}$为节点集，其对应了在尺度为s时的窗内不同时间标签。$\mathcal{E}_{(s)}={e_{1},\dots,e_{M_{s}}}$代表了在节点之间的超边。超图的拓扑结构如下记载：关联矩阵（incidence matrix）$\mathbf{H}_{(s)}\in \mathbb{R}^{N_{s}\times M_{s}}$，其定义如下：
$$
\left[\mathbf{H}_{(s)}\right]_{n m}=\left\{\begin{array}{ll}1 & \text { if } v_{n} \in e_{m} \\ 0 & \text { if } v_{n} \notin e_{m}\end{array}\right.
$$
在不同的时间点，我们假设对应的时间窗共享相同的节点间长短程依赖性。最终，我们在相同的尺度s下构建了一个窗级别的超图来学习泛化后的依赖性，让其可以保留不同时间窗之间的不变性。
Trainable Hypergraphs
为了获得一个可学习的超图，让这个图可以通过可训练的关联矩阵以描述不同尺度下的相关性，我们计算基于相似度的指标$\mathbf{H}_{(s)}$：
$$
\mathbf{H}_{(s)}=\sigma(\text{ReLU}(\mathbf{F}^{\text{node}}_{(s)}(\mathbf{F}^\text{edge}_{(s)})^T))
$$
其中$\mathbf{F}^\text{node}_{(s)}\in \mathbb{R}^{N_{s}\times d},\space \mathbf{F}^\text{edge}_{(s)}\in \mathbb{R}^{M_{s}\times d}$均为可训练的节点与超边的嵌入，对应的，在这里$\sigma(\cdot)$为激活函数，$\text{ReLU}$用于保证结果的非负性和嵌入的稀疏性。
在每个训练epoch，超图的关联矩阵通过如下方式更新$\mathbf{H}_{(s)}=(1-\tau)\mathbf{H}_{(s)}+\tau \tilde{\mathbf{H}}_{(s)}$。其中$\tilde{\mathbf{H}}_{(s)}$为超图上一个epoch的关联矩阵。特别的，初始化关联矩阵的方法为：
$$
\left[\mathbf{H}_{(s)}\right]_{n m}=\left\{\begin{array}{ll}1 & \text { if } N_{s}-M_{s}-k+m \leq n \leq N_{s}-M_{s}+m \\ 0 & \text { otherwise }\end{array}\right.
$$
其中，k为预先定义的超参，用于决定每个超边初始连接的超节点。上式子表示初始的超边倾向于连接邻接的时间标签，这个想法与时间序列重构的基本想法相一致。另外，这个方法也会发现未知的长时间的相关性在更新过程中。
稀疏矩阵$\mathbf{H}_{(s)}$接下来将会选择k个最显著的连接，来限制连接点的数目并减少计算量
$$
\left[\mathbf{H}_{(s)}\right]_{n m}=\left\{\begin{array}{ll}1 & \text { if }\left[\mathbf{H}_{(s)}\right]_{n m} \in \operatorname{TopK}\left(\left[\mathbf{H}_{(s)}\right]_{n}\right), \\ 0 & \text { if }\left[\mathbf{H}_{(s)}\right]_{n m} \notin \operatorname{TopK}\left(\left[\mathbf{H}_{(s)}\right]_{n}\right),\end{array}\right.
$$
其中$\text{TopK}(\cdot)$为最前面k个选择器。
Intra-scale Hypergraph Attention
首先，我们将训练窗中第n个节点的再采样变量记为$[\mathbf{W}_{(s)}]_{n}$。为了实现不同尺度的超图tranformer模块，我们首先使用图注意力机制
$$
\left[\hat{\mathbf{H}}_{(s)}\right]_{n m}=\frac{\exp \left(\sigma\left(\left[\left[\mathbf{W}_{(s)}\right]_{n},\left[\mathbf{E}_{(s)}\right]_{m}\right] \Theta_{(s)}^{A t t}\right)\right)}{\sum_{\mathcal{E}_{(s)}^{k} \in \mathcal{N}\left(\mathcal{V}_{(s)}^{n}\right)} \exp \left(\sigma\left(\left[\left[\mathbf{W}_{(s)}\right]_{n},\left[\mathbf{E}_{(s)}\right]_{k}\right] \Theta_{(s)}^{A t t}\right)\right)}
$$
其中$\Theta_{(s)}^{Att}$为可训练的权重，$\mathcal{N}\left(\mathcal{V}_{(s)}^{n}\right)$为节点n邻接的超边，$[\mathbf{E}_{(s)}]_{m}$为通过聚合连接节点m变量计算的边特征：
$$
\left[\mathrm{E}_{(s)}\right]_{m}=\operatorname{Agg}\left(\sum_{\mathcal{V}_{(s)}^{k} \in \mathcal{N}\left(\mathcal{E}_{(s)}^{m}\right)}\left[\mathbf{W}_{(s)}\right]_{k}\right)
$$
作者将不同尺度下超图的注意力模型记为$\hat{\mathbf{H}}_{(s)}=\text{IntraHAtt}(\mathbf{W}_{(s)}, \mathcal{G}_{(s)})$.
Multi-Head Hypergraph Convolutions
我们可以如下进行多头超图卷积操作：
$$
\mathbf{Z}_{(s)} =[\mathbf{Z}_{(s)}^1,\dots,\mathbf{Z}_{(s)}^H]
$$
其中H为多头的数目，第h个头的输出为：
$$
\begin{array}{l}\mathbf{Z}_{(s)}^{h}= \\ \sigma\left(\left(\mathbf{D}_{(s)}^{v}\right)^{-\frac{1}{2}} \hat{\mathbf{H}}_{(s)}^{h} \Phi_{(s)}^{h}\left(\mathbf{D}_{(s)}^{e}\right)^{-1}\left(\hat{\mathbf{H}}_{(s)}^{h}\right)^{T}\left(\mathbf{D}_{(s)}^{v}\right)^{-\frac{1}{2}} \mathbf{W}_{(s)} \Theta_{(s)}^{h}\right)\end{array}
$$
其中$\Phi_{(s)}^{h}=\text{diag}(\Phi_{1}^{h},\dots,\Phi_{N_{s}}^{h})$为可训练的超图边权重，$\Theta^h_{(s)}$为可训练的权重，用于捕捉潜在的特征。$\mathbf{D}^v_{(s)}\in \mathbb{R}^{N_{s}\times N_{s}},\mathbf{D}^v_{(e)}\in \mathbb{R}^{M_{s}\times M_{s}}$为对角节点度数和对角边度数矩阵，其中$[\mathbf{D^v_{(s)}}]_{nn}=\sum^{M_{s}}_{m=1}[\mathbf{H}_{(s)}]_{nm}$且$[\mathbf{D^e_{(s)}}]_{mm}=\sum^{N_{s}}_{n=1}[\mathbf{H}_{(s)}]_{nm}$。多头超图卷积模块可以被记为$\mathbf{Z}=\text{MHConv}(\tilde{\mathbf{H}}_{(s)}, \mathbf{W}_{(s)})$。
Hypergraph Learning Consistency Constraint
首先，不同时间标签在之间的关系，例如邻接矩阵$\mathbf{A}_{(s)}\in \mathbb{R}^{N_{s}\times N_{s}}$在不同的尺度下可以通过$\mathbf{A}_{(s)}=\mathbf{H}_{(s)}\mathbf{H}_{(s)}^T$获得，在此，我们假设学习到的超参数必须满足Laplacian限制，保证在超图连接的时间点之间的不同尺度特征一致性，为了学习到这样的一致性，作者使用了Laplacian限制在不同的邻接矩阵上，以保证最大化连接节点之间的相似性(原文为minimize similarities)。
$$
\begin{aligned} \min _{\mathbf{A}_{(0)}, \cdots, \mathbf{A}_{(L-1)}} & \mathcal{L}_{(s)}^{\text {Laplacian }}\left(\mathbf{W}_{(s)}^{\text {sample }}, \mathbf{L}_{(s)}\right) \\ & =\sum_{s=0}^{L-1} \operatorname{Tr}\left(\left(\mathbf{W}_{(s)}^{\text {sample }}\right)^{T} \mathbf{L}_{(s)} \mathbf{W}_{(s)}^{\text {sample }}\right),\end{aligned}
$$
注：Laplacian Constraint
$$
\begin{aligned}
&\mathcal{L}^\text{Laplacian}(\mathbf{W}, \mathbf{L})\\
=&\text{Tr}(\mathbf{W}^T \mathbf{L} \mathbf{W})\\
=& \frac{1}{2}\sum_{i,j} \mathbf{A}_{ij}||\mathbf{W}_{i} - \mathbf{W}_{j}||^2
\end{aligned}
$$
代表了相连接的节点之间表示的距离之和，如果相连接，则节点的表示应该也相近。
其中$\mathbf{L}_{(s)}=\mathbf{D}_{(s)}-\mathbf{A}_{(s)}$其中D为度数的对角矩阵，A为邻接矩阵。由于${ \mathbf{W}^\text{sample}_{(s)} }^{L-1}_{s=1}$由同样的窗W下采样获得。上式子是为了获得在窗内的多个尺度中超图的一致性。
Similarity-based Hypergraph Constraints
作者希望超边中连接的节点尽量相似，因此基于相似度的权重如下计算：
$$
\alpha_{i j}^{(s)}=\frac{\left[\mathrm{E}_{(s)}^{\mathrm{ori}}\right]_{i}\left[\mathrm{E}_{(s)}^{\mathrm{ori}}\right]_{j}^{T}}{\left|\left[\mathrm{E}_{(s)}^{\mathrm{ori}}\right]_{i}\right|_{2}\left|\left[\mathrm{E}_{(s)}^{\mathrm{ori}}\right]_{j}\right|_{2}}
$$
其中$[\text{E}^{\text{ori}}_{(s)}]_{i}$为第i个超边的初始特征，由与之连接的节点计算而来：
$$
\left[\mathbf{E}_{(s)}^{\text {ori }}\right]_{i}=\operatorname{Agg}\left(\sum_{\mathcal{V}_{(s)}^{k} \in \mathcal{N}\left(\mathcal{E}_{(s)}^{i}\right)}\left[\mathbf{W}_{(s)}^{\text {sample }}\right]_{k}\right)
$$
既然我们要最小化学习到的边嵌入和初始边特征的距离，我们如下定义超边的限制：
$$
\begin{aligned} & \min _{\mathbf{F}_{(s)}^{\text {edge }}} \mathcal{L}_{(s)}^{\text {hyperedge }}\left(\mathbf{F}_{(s)}^{\text {edge }}, \mathbf{E}_{(s)}^{\text {ori }}\right) \\ = & \frac{1}{\left(M_{s}\right)^{2}} \sum_{j=1}^{M_{s}} \sum_{j=1}^{M_{s}}\left(\alpha_{i j}^{(s)} \mathcal{D}_{i j}+\left(1-\alpha_{i j}^{(s)}\right) \max \left(\gamma-\mathcal{D}_{i j}, 0\right)\right)\end{aligned}
$$
其中$\gamma$为超参数，学习到的边嵌入的距离通过如下方式计算：$\mathcal{D}_{i j}=\left|\left[\mathrm{F}_{(s)}^{\text {edge }}\right]_{i}-\left[\mathrm{F}_{(s)}^{\text {edge }}\right]_{j}\right|_{2}$。因为更高的$\alpha_{ij}^{(s)}$代表超边之间的更高的相关性，这个式子将会最小化嵌入之间的距离$\mathcal{D}_{ij}$；相反的，一个更小的$\alpha_{ij}^{(s)}$代表这个模型将会更多学习具有更远距离的超边嵌入。总之，这个最小化问题是为了推进学习到的超边嵌入和初始超边特征之间的一致性，并借此提高从$\mathbf{F}_{(s)}^\text{egde}$中学到的超图的质量。
同时，作者也希望学习到的节点嵌入$\mathbf{F}_{(s)}^\text{node}$和出事的边特征一致，我们定义节点限制为：
$$
\begin{aligned} & \min _{\mathbf{F}_{(s)}^{\text {node }}} \mathcal{L}_{(s)}^{\text {node }}\left(\mathbf{F}_{(s)}^{\text {node }}, \mathbf{E}_{(s)}^{\text {ori }}\right) \\ = & \frac{1}{N_{s}} \sum_{i=1}^{N_{s}} \sum_{\mathcal{V}_{(s)}^{i} \in \mathcal{N}\left(\mathcal{E}_{(s)}^{j}\right)} \operatorname{Abs}\left(\operatorname{Proj}\left(\left[\mathbf{F}_{(s)}^{\text {node }}\right]_{i}\right)-\left[\mathbf{E}_{(s)}^{\text {ori }}\right]_{j}\right)\end{aligned}
$$
其中$\text{Proj}(\cdot)$是用于维持超边和节点的初始特征数目一致的映射函数。
Time Series Decomposition Module
时间序列分解模块旨在分解输入窗来转化为季节性的特征和趋势性。首先，作者使用fourier transformer operator DFT来将输入序列$\mathcal{Z}$从时域转化为频域。
$$
\left\{f_{1}, \cdots, f_{k}\right\}, \mathrm{A}, \Gamma=\operatorname{TopK}(\operatorname{DFT}(\mathcal{Z}))
$$
其中${ f_{1},\dots,f_{k} }$为k个最显著的频率，A为振幅，$\Gamma$为相位。
在k个最显著的频率下，周期性信号$\mathcal{Z}^\text{sea}$可以使用逆向DFT运算IDFT计算得出。
$$
\mathcal{Z}^{\text {sea }}=\operatorname{IDFT}\left(\left\{f_{1}, \cdots, f_{k}\right\}, \mathrm{A}, \Gamma\right)
$$
对于趋势，作者使用K个平均池化核来进行计算MA用于捕捉趋势特征，即：
$$
\mathcal{Z}^{\text {trend }}=\sum_{i=1}^{K} \alpha_{i} \operatorname{AvgPool}_{i}(\mathcal{Z})
$$
其中$\alpha_{i}$为第i个核的权重，$\boldsymbol{\alpha}=\left[\alpha_{1}, \cdots, \alpha_{K}\right]$通过Softmax函数进行归一化，总之，时间序列分解模块可以如下记录$\mathcal{Z}^\text{sea},\mathcal{Z}^\text{trend}=\text{TSDecom}(\mathcal{Z})$. 基于季节性和趋势性序列，我们可以获得演化时间序列
$$
\mathcal{Z}^{\text {evo }}=
\text{FeedForward}\left(\left[\mathbf{W}, \mathcal{Z}^{\text {sea }} \Theta^{\text {evo }}, \mathcal{Z}^{\text {trend }}\right]\right)
$$
其中$\Theta^\text{evo}$为可训练的权重，FeedForward为feed-forward layer，我们记作$\mathcal{Z}^\text{evo} = \text{STFusion}(\mathbf{W}, \mathcal{Z}^\text{sea}, \mathcal{Z}^\text{trend})$。
Multi-scale Hypergraph Fusion Process
为了融合学习到的多尺度窗特征，我们首先上采样学习到的$\mathcal{Z}^\text{evo}_{(s)}$在尺度s时，以让所有尺度的输出均为相同的维度，因此，我们可以直接将这些上采样的输出加起来得到一个融合表示，具体公式如下：
$$
\mathcal{Z}^\text{evo}_{(s)}=\mathcal{Z}^\text{evo}_{(s)}+\text{Padding}\big(\text{ConvTranspose1D}(\mathcal{Z}^\text{evo}_{(s+1)})\big)
$$
对于$1\leq s\leq L-1$，其中L为尺度的数量，1维转置卷积层记为ConvTranspose1D。最终，我们使用一个feedforward层接收初始尺度下学习到的特征：$\mathcal{Z}^{\text{fusion}} = \left(\text{FeedForward}(\mathcal{Z}_{(0)}^{\text{evo}})\right)$
我们同时需要将学习到的多尺度超图${ \mathbf{H}_{(s)} }^{L-1}_{s=0}$结合到模型中，该超图将会用于解码器的信息传递，因为在高尺度中的超边连接可以反映低尺度的分组连接结构。我们可以上采样高尺度下的超边连接：
$$
\left[\tilde{\mathbf{H}}_{(s)}\right]_{n}=\left[\mathbf{H}_{(s+1)}\right]_{\lfloor n / \mathcal{K}\rfloor}
$$
其中，$\mathcal{K}$为数据采样的步长，$\tilde{\mathbf{H}_{(0)}}=\mathbf{H}_{(0)}$。最终，多尺度超边融合可以如下进行：
$$
\mathbf{H}^{\text {fusion }}=\left[\tilde{\mathbf{H}}_{(0)} ; \tilde{\mathbf{H}}_{(1)} ; \cdots ; \tilde{\mathbf{H}}_{(L-1)}\right] \in \mathbb{R}^{N \times\left(\sum_{s=0}^{L-1} M_{s}\right)}
$$
因此，$\mathbf{H}^\text{fusion}$包括时间窗内按照点和按照组的交互信息。
Model Training
总而言之，MSHTrans是一个多通道编码器-解码器架构用于从多尺度输入中重构时间窗数据。短期依赖性由可训练的超图实现，长期依赖性由可训练超图和时间序列分解分析实现。损失函数包括Laplacian loss, Hyperedge loss, node loss和重构损失。
$$
\mathcal{L}^{all} = \sum^{L-1}_{s=0}\left ( \mathcal{L}^{\text{Laplacian}}_{(s)}+\mathcal{L}^{\text{hyperedge}}_{(s)}+\mathcal{L}^{\text{node}}_{(s)}\right)+\mathcal{L}^{\text{rec}}
$$
其中$\mathcal{L}^{\text{rec}}$为重构的损失，由在解码器中重构的时间窗$\mathcal{Z}^\text{evo}_{\text{de}}$和原始的时间窗：
$$
\mathcal{L}^{\mathrm{rec}}\left(\mathbf{W}, \mathcal{Z}_{\mathrm{de}}^{\mathrm{evo}}\right)=\frac{1}{S D}\left|\mathbf{W}-\mathcal{Z}_{\mathrm{de}}^{\mathrm{evo}}\right|_{F}^{2}
$$
正如对于异常检测任务，这里的异常分数如下计算：
$$
\mathcal{S}_{t}=\frac{1}{D}\left|\left[\mathbf{W}^{(t)}\right]_{-1},\left[\mathcal{Z}_{\mathrm{de}}^{\mathrm{evo}(t)}\right]_{-1}\right|_{F}^{2}
$$
MSE为均方差，异常标签由特定阈值决定。
