HPCI：电信网络中基于影响力的根源告警挖掘方法

论文标题｜ An Influence-based Approach for Root Cause Alarm Discovery in Telecom Networks
论文来源｜ ICSOC(B) 2020
论文链接｜ https://arxiv.org/abs/2105.03092
源码链接｜ https://github.com/shaido987/alarm-rca

TL;DR

论文中提出了一种数据驱动不需要专家知识的根因告警定位框架，其中结合了因果推理和网络表示学习方法。关于告警间因果图挖掘部分论文中设计了一种混合因果图学习方法 HPCI，主要思想是将霍克斯过程与 PC 算法相结合。此外，论文中还提出一种基于因果传播的表示学习算法 CPBE 来推理因果图中边的权重。在得到加权的因果图后使用了一种影响力最大化算法 IRIE 来定位图中的根因告警。实验部分在人工数据集和真实数据集中验证了论文提出的框架优于当前 baselines。

Preliminaries

在了解正文的方法前需要知道两种概念：霍克斯过程 (Hawkes process) 和 PC 算法，可以参考其它两篇文章。

Algorithm/Model

论文中提出的系统架构图如下所示

主要包含三个模块：

告警数据预处理：主要任务是有效告警过滤，根据网络拓扑聚合告警等。
影响图构建：主要根据历史告警数据构造影响关系因果图，并且是周期性执行。因果图中节点是告警类型，边是推理出来的因果关系。这部分涉及了两种方法：
- HPCI (Hawkes process and conditional independence)：结合 Hawkes 过程和条件独立性测试构建因果图结构。
- CPBE (Causal Propagation-Based Embedding)：结合网络表示学习方法推理因果图中边的权重。
告警排序：故障发生时根据构造的告警因果图进行告警排序，选择 top-K 进行推荐。

以下详细介绍每个模块中的方法细节。

告警预处理

输入数据：

Network Topology：网络设备间的架构拓扑。
Alarms：网络告警数据，(alarm_id, alarm_type, network_device, occurence_time)

告警预处理步骤如下：

由于一个故障会导致相连设备发生告警，因此将同一个连通子拓扑中的告警进行聚合。🧐 个人感觉可有可无，一般数据给定一个连通拓扑图。
同一故障相关的告警一般会在较短的时间窗口 $w_i$ 内发生，因此可以根据告警发生时间对告警进行分组。时间窗口 $w_i$ 的大小需要根据实际的网络特征来判断。
分组后的告警定义为一个告警序列 $S_{i}=\left\{\left(a_{i j}, t_{i j}\right)\right\}_{j=1}^{n_{i}}$ ， $w_i$ 是时间窗口大小， $a_{ij}\in A$ 为告警类型。 $t_{ij}\in w_i$ 是发生时间， $n_i$ 是告警数量。
每个告警序列需要转化为告警事务表示为 $T_i=\{(a,t,n)|a\in A_i\}$ ，其中 $a, t, n$ 分别表示告警类型，最早发生时间和发生次数， $A_i$ 表示时间窗口 $w_i$ 内的每个告警类型。

告警因果图构建

HPCI

多维 Hawkes 过程可以挖掘出告警指标间的某种因果影响关系，即影响矩阵 $A$ 可以理解因果图的邻接矩阵。但是会有些冗余或者间接的边也会被推断出来，因为条件密度函数在实际数据中难以捕获事件直接的因果关系？因此，论文中提出了结合 Hawkes process 和 PC 的混合算法 HPCI 来挖掘告警类型间的因果结构。

主要过程如下：

利用未添加惩罚项的多维 Hawkes 过程挖掘告警类型间的影响强度。使用告警序列 $\mathcal{S}=\{S_i\}$ 作为输入得到初始的加权图，边 $(u,v)$ 的权重 $\alpha_{uv}>0$ 表示在告警类型 $v$ 发生后告警类型 $u$ 才发生的时间期望。所有权重为正的边被保留。
注：使用未添加惩罚项的 Hawkes process 是因为方法可解释性更好而且实验效果更好。
利用 CI 条件独立性测试消除冗余的边。使用告警事务 $\mathcal{T}=\{T_i\}$ 作为输入，对于每个告警 $a_i$ 的发生数量序列为 $N_{i}=\left\{n \mid T_{k} \in \mathcal{T},(a, t, n) \in T_{k}, a=a_{i}\right\}$ ，其中 $n$ 为 0 如果事件类型在当前时间窗口 $w_i$ 没有发生。对于每一对告警类型 $(a_i, a_j)$ 使用 CI 来判断条件独立性并删除边。
迭代执行步骤 2 删除 $\alpha_{uv}$ 最小的边直至因果图为有向无环图 DAG 表示为 $G^C$ 。