Hierarchical Graph Neural Networks for Causal Discovery and Root Cause
  Localization
In this paper, we propose REASON, a novel framework that enables the
automatic discovery of both intra-level (i.e., within-network) and inter-level
(i.e., across-network) causal relationships for root cause localization. REASON
consists of Topological Causal Discovery and Individual Causal Discovery. The
Topological Causal Discovery component aims to model the fault propagation in
order to trace back to the root causes. To achieve this, we propose novel
hierarchical graph neural networks to construct interdependent causal networks
by modeling both intra-level and inter-level non-linear causal relations. Based
on the learned interdependent causal networks, we then leverage random walks
with restarts to model the network propagation of a system fault. The
Individual Causal Discovery component focuses on capturing abrupt change
patterns of a single system entity. This component examines the temporal
patterns of each entity's metric data (i.e., time series), and estimates its
likelihood of being a root cause based on the Extreme Value theory. Combining
the topological and individual causal scores, the top K system entities are
identified as root causes. Extensive experiments on three real-world datasets
with case studies demonstrate the effectiveness and superiority of the proposed
framework.
Dongjie Wang, Zhengzhang Chen, Jingchao Ni, Liang Tong, Zheng Wang, Yanjie Fu, Haifeng Chen
# Hierarchical Graph Neural Networks for

###### Abstract.

The goal of root cause analysis is to identify the underlying causes of system problems by discovering and analyzing the causal structure from system monitoring data. It is indispensable for maintaining the stability and robustness of large-scale complex systems. Existing methods mainly focus on the construction of a single effective isolated causal network, whereas many real-world systems are complex and exhibit interdependent structures (_i.e._, multiple networks of a system are interconnected by cross-network links). In interdependent networks, the malfunctioning effects of problematic system entities can propagate to other networks or different levels of system entities. Consequently, ignoring the interdependency results in suboptimal root cause analysis outcomes.

In this paper, we propose REASON, a novel framework that enables the automatic discovery of both intra-level (_i.e._, within-network) and inter-level (_i.e._, across-network) causal relationships for root cause localization. REASON consists of Topological Causal Discovery and Individual Causal Discovery. The Topological Causal Discovery component aims to model the fault propagation in order to trace back to the root causes. To achieve this, we propose novel hierarchical graph neural networks to construct interdependent causal networks by modeling both intra-level and inter-level nonlinear causal relations. Based on the learned interdependent causal networks, we then leverage random walk with restarts to model the network propagation of a system fault. The Individual Causal Discovery component focuses on capturing abrupt change patterns of a single system entity. This component examines the temporal patterns of each entity's metric data (_i.e._, time series), and estimates its likelihood of being a root cause based on the Extreme Value theory. Combining the topological and individual causal scores, the top \(K\) system entities are identified as root causes. Extensive experiments on three real-world datasets with case studies demonstrate the effectiveness and superiority of the proposed framework.

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and

+
Footnote †: journal: Computer Science and
system failures, Chen _et al._(Chen et al., 2018) constructed a directed acyclic graph that depicts the invoking relations among microservice applications. These methods have been applied to some uncomplicated systems with isolated network structures.

However, a real-world complex system usually consists of multiple networks that coordinate in a highly complex manner (Beng et al., 2015; Chen et al., 2017). These networks are interconnected, and if one network's system entity fails, it may spread to its dependent entities in other networks, which may then cause cascading damages or failures (Chen et al., 2017; Chen et al., 2018) that could circulate throughout the interconnected levels with catastrophic consequences. For instance, Figure 1 shows the malfunction of the pod _Django-search_ first spreads to the server network and causes the fault of the server _Compute-1_; Then, the malfunctioning effects spread to the pod network of _Compute-2_ and causes the faults of the pod _Mongodb_ and _Mysql_; Finally, the pod _Sdn_ in _Infra-1_ is also affected, resulting in the system failure. In this failure case, it is quite difficult to pinpoint the root cause _Django-search_ if we only model the server network (_i.e._, the three servers) or one of the three pod networks of the microservice system. Thus, modeling the interconnected multi-network structures is vital for comprehensive understanding of the complex system and effective root cause localization.

Recently, a promising approach for modeling such interconnected structures in complex systems has emerged through the concept of interdependent networks (or network of networks) (Beng et al., 2015; Chen et al., 2017; Chen et al., 2018; Chen et al., 2018). In interdependent networks, each node of the main network can be represented as a domain-specific network. Let us elaborate using the example in Figure 1 again. Here, the dashed network represents a server/machine network (the main network), where the nodes are three different servers and edges/links indicate the causal relations among different servers. Each node of this main network is further represented as a pod network (the domain-specific network), where nodes are pods and edges denote their causal relations. Collectively, we call this structure a (server-pod) interdependent networks. And since all the edges in these interdependent networks indicate causal dependencies, we further call it _interdependent causal networks_. Interdependent networks have been widely used in the study of various topics, including the academic influence of scholars (Shen et al., 2016), the spreading pattern of rumors in the complex social network (Shen et al., 2016), and etc. However, existing methods only consider physical or statistical correlations, but not causation, and thus cannot be directly applied for locating root causes.

Enlightened by the interdependent networks, this paper aims to learn interdependent causal relationships from monitoring metrics in multi-network systems for accurately identifying root causes when a system failure/fault occurs. Formally, given the system KPI data, the multi-level interconnected system entities, and their metrics data (_i.e._, time series), our goal is to learn interdependent causal structures for discovering the root causes of system failures. There are two major challenges in this task:

* **Challenge 1: Learning interdependent causal networks and modeling fault propagation in interdependent causal networks**. As aforementioned, in real-world systems with interdependent networks structures, malfunctioning effects of root causes can propagate to other nodes of the same level or different levels (_i.e._, main network level and domain-specific network level), resulting in catastrophic failure of the entire system. To capture such propagation patterns for root cause localization, we need to learn the causal relationships not only within the same level but also across levels. After modeling the interdependent causal relationships, we still need to model the propagation of malfunctioning effects in the learned causal interdependent networks.
* **Challenge 2: Identifying abrupt change patterns from the metrics data of an individual system entity.** In addition to the topological patterns, metrics data associated with the system entities can exhibit abrupt change patterns during the incidence of system faults, particularly those that are short-lived (_e.g._, fail-stop failures). The malfunctioning effects of the root cause may end quickly before they can spread. Thus, the temporal patterns from the metrics data can provide individual causal insights for locating root causes. The challenge is how to capture abrupt change patterns and determine the individual causal effect associated with the system failure.

To address these challenges, in this paper, we propose REASON, a generic interdependent causal networks based framework, for root cause localization in complex systems with interdependent network structures. REASON consists of Topological Causal Discovery (TCD) and Individual Causal Discovery (ICD). For the TCD component, the assumption is that the malfunctioning effects of root causes can propagate to other system entities of the same level or different levels over time (Chen et al., 2017; Chen et al., 2018). To capture such propagation patterns, we propose a hierarchical graph neural networks based causal discovery method to discover both intra-level (_i.e._, within-network) and inter-level (_i.e._, across-network) non-linear causal relationships. Then, we leverage a random walk with restarts to model the network propagation of a system fault. The ICD component, on the other hand, focuses on individual causal effects, by analyzing the metrics data (_i.e._, time series) of each system entity. Especially considering the short-lived failure cases (_e.g._, fail-stop failures), there may be no propagation patterns. We design an Extreme Value theory based method to capture the abrupt fluctuation patterns and estimate the likelihood of each entity being a root cause. Finally, we integrate the findings of TCD and ICD, and output the system entities with the top-\(K\) greatest causal scores as the root causes. Extensive experiments and case studies are conducted on three real-world datasets to validate the efficacy of our work.

## 2. Preliminaries

**System Key Performance Indicator (KPI).** A KPI is a monitoring time series that indicates the system status. For instance, in a microservice system, the latency or connection time can be used to assess the system status. The smaller the latency, the higher the system's performance quality. If the connection time is too long, it is likely that the system has failed.

**Entity Metrics.** Entity metrics data can be collected by monitoring different levels of system entities. It usually contains a number of metrics, which indicate the status of a system's underlying entity. For example, in a microservice system, the underlying entity can be a physical machine, container, virtual machine, pod, etc. And the
corresponding metrics can be CPU utilization, memory utilization, disk IO utilization, etc. The data for all these metrics are essentially time series. An anomalous metric of a microservice's underlying entity can be the potential root cause of an anomalous system latency/connection time, which indicates a microservice failure.

**Interdependent Networks (INs).** Interdependent networks model the interconnections of multiplex networks (Srivastava et al., 2017; Wang et al., 2018). Given a \(g\times g\) main network G, a set of domain-specific networks \(\mathcal{A}=\{\mathbf{A}_{1},\cdots,\mathbf{A}_{g}\}\), and an edge set E that represents the edges between the nodes in \(\mathcal{A}\) and the nodes in G, INs are defined as a triplet \(\mathcal{R}=<\mathbf{G},\mathcal{A},\mathbf{E}>\). The node set in G, _a.k.a._ high-level nodes, is denoted by \(\mathbf{V}^{\mathcal{G}}\), and the node set in \(\mathcal{A}\), _a.k.a._ low-level nodes, is denoted by \(\mathbf{V}^{\mathcal{M}}=(\mathbf{V}^{A_{1}},\cdots,\mathbf{V}^{A_{g}})\). As a special type of INs, interdependent causal networks represent the INs with the edges indicating causal relations.

Take Figure 1 as an example, the dashed network is the main network G, which has three server nodes, including _Compute-1_, _Compute-2_, and _Infra-1_. Each of these main nodes contains a domain-specific network that is made up of several applications/pods. For instance, the main node _Compute-2_ is further represented as a domain-specific network with three pod nodes, including _Mysql_, _Mongodb_, and _Dispatch_. And the solid edges indicate the causal relationships between different pods, while the dashed edges indicate the causal relationships between different servers.

Without loss of generality, we focus on two levels of system entities. Our goal is to identify root causes by automatically learning interdependent causal relations between different levels of system entities and the system KPI. The identified root causes are low-level system entities to reflect fine-grained root cause detection.

**Problem Statement**. Given metrics/sensor data of multi-level system entities corresponding to high-level and low-level nodes in main and domain-specific networks \(\{\mathbf{X}^{G},\mathbf{X}^{\mathcal{M}}\}\), and system key performance indicator \(\mathbf{y}\), the problem is to construct an interdependent causal network \(\mathcal{R}=<\mathbf{G},\mathcal{A},\mathbf{E}>\), and identify the top \(K\) low-level nodes in \(\mathbf{V}^{\mathcal{M}}\) that are most relevant to \(\mathbf{y}\).

## 3. Methodology

We present REASON, an interdependent causal network based framework for root cause localization. As illustrated in Figure 2, REASON includes three major steps: 1) topological causal discovery; 2) individual causal discovery; and 3) causal integration.

### Topological Causal Discovery

Root causes (_i.e._, the system entities that cause the system failures or faults) could propagate malfunctioning or fault effects to other system entities of the same network or across different networks over time (Beng et al., 2016; Wang et al., 2018; Wang et al., 2018), which makes real root causes hard to locate. To address this challenge, we propose a hierarchical graph neural network based causal discovery method to construct interdependent causal graphs among low-level and high-level system entities. Failure propagation is modeled on the learned causal structures to provide topological guidance for locating root causes by simulating the malfunctioning effects of root causes.

#### 3.1.1. Hierarchical Graph Neural Network based Interdependent Causal Discovery

There can be more than one entity metric (_i.e._, multi-variate time series) per system entity (refer to Section 2). For each individual metric, we learn interdependent causal graphs among different system entities using the same learning strategy. To ease the description, we take one metric of system entities as an example to illustrate the interdependent causal discovery process.

The metric of system entities (_i.e._, high-level or low-level) is a multivariate time series \(\{\mathbf{x}_{0},\cdots,\mathbf{x}_{T}\}\). The metric value at the \(t\)-th time step is \(\mathbf{x}_{t}\in\mathbb{R}^{d}\), where \(d\) is the number of entities. The data can be modeled using the VAR model (Wang et al., 2018; Wang et al., 2018), whose formulation is given by:

\[\mathbf{x}_{t}^{\top}=\mathbf{x}_{t-1}^{\top}\mathbf{B}_{1}+\cdots+\mathbf{x} _{t-p}^{\top}\mathbf{B}_{p}+\mathbf{\epsilon}_{t}^{\top},\quad t=\{p,\cdots,T\} \tag{1}\]

where \(p\) is the time-lagged order, \(\mathbf{\epsilon}_{t}\) is the vector of error variables that are expected to be non-Gaussian and independent in the temporal dimension, \(\{\mathbf{B}_{1},\cdots,\mathbf{B}_{p}\}\) are the weighted matrix of time-lagged

Figure 2. The overview of the proposed framework REASON. It consists of three major steps: topological causal discovery, individual causal discovery, and causal integration.
data. In the VAR model, the time series at \(t\), \(\mathbf{x}_{t}\), is assumed to be a linear combination of the past \(p\) lags of the series.

Assuming that \(\{\mathbf{B}_{1},\cdots,\mathbf{B}_{p}\}\) is constant across time, the Equation (1) can be extended into a matrix form:

\[\mathbf{X}=\tilde{\mathbf{X}}_{1}\mathbf{B}_{1}+\cdots+\tilde{\mathbf{X}}_{p} \mathbf{B}_{p}+\epsilon \tag{2}\]

where \(\mathbf{X}\in\mathbb{R}^{m\times d}\) is a matrix and its each row is \(\mathbf{x}_{t}^{\top}\); \(\{\tilde{\mathbf{X}}_{1},\cdots,\tilde{\mathbf{X}}_{p}\}\) are the time-lagged data.

To simplify Equation 2, let \(\tilde{\mathbf{X}}=[\tilde{\mathbf{X}}_{1}|\cdots|\tilde{\mathbf{X}}_{p}]\) with its shape of \(\mathbb{R}^{m\times pd}\) and \(\mathbf{B}=[\mathbf{B}_{1}|\cdots|\mathbf{B}_{p}]\) with its shape of \(\mathbb{R}^{m\times pd}\). Here, \(m=T+1-p\) is the effective sample size, because the first \(p\) elements in the metric data have no sufficient time-lagged data to fit Equation 2. After that, we apply the QR decomposition to the weight matrix \(\mathbf{B}\) to transform Equation 2 as follows:

\[\mathbf{X}=\tilde{\mathbf{X}}\hat{\mathbf{W}}+\epsilon \tag{3}\]

where \(\hat{\mathbf{B}}\in\mathbb{R}^{m\times pd}\) is the weight matrix of time-lagged data in the temporal dimension; \(\mathbf{W}\in\mathbb{R}^{d\times d}\) is the weighted adjacency matrix, which reflects the relations among system entities.

A nonlinear autoregressive model allows \(\mathbf{x}_{t}\) to evolve according to more general nonlinear dynamics [9]. In a forecasting setting, one promising way is to jointly model the nonlinear functions using neural networks [9, 24]. By applying neural networks \(f\) to Equation 3, we have

\[\mathbf{X}=f(\tilde{\mathbf{X}}\hat{\mathbf{B}}\mathbf{W};\mathbf{\Theta})+\epsilon \tag{4}\]

where \(\mathbf{\Theta}\) is the set of parameters of \(f\).

Given the data \(\mathbf{X}\) and \(\tilde{\mathbf{X}}\), here our goal is to estimate weighted adjacency matrices \(\mathbf{W}\) that correspond to directed acyclic graphs (DAGs). The causal edges in \(\mathbf{W}\) go only forward in time, and thus they do not create cycles. In order to ensure that the whole network is acyclic, it thus suffices to require that \(\mathbf{W}\) is acyclic. Minimizing the least-squares loss with the acyclicity constraint gives the following optimization problem:

\[\min\frac{1}{m}\left\|\mathbf{X}-f(\tilde{\mathbf{X}}\hat{\mathbf{B}} \mathbf{W};\mathbf{\Theta})\right\|^{2}\quad s.t.\ \mathbf{W}\ \text{is acyclic}, \tag{5}\]

To learn \(\mathbf{W}\) in an adaptive manner, we adopt the following layer:

\[\mathbf{W}=\text{RELU}(\tanh(\mathbf{W}_{+}\mathbf{W}_{-}^{\top}-\mathbf{W}_ {-}\mathbf{W}_{+}^{\top})), \tag{6}\]

where \(\mathbf{W}_{+}\in\mathbb{R}^{d\times d}\) and \(\mathbf{W}_{-}\in\mathbb{R}^{d\times d}\) are two parameter matrices. This learning layer aims to enforce the asymmetry of \(\mathbf{W}\), because the propagation of malfunctioning effects is unidirectional and acyclic from root causes to subsequent entities. In the following sections, \(\mathbf{W}^{G}\) denotes the causal relations between high-level nodes and \(\mathbf{W}^{\mathcal{H}}\) denotes the causal relations between low-level nodes.

Then, the causal structure learning for the interdependent networks can be divided into intra-level learning and inter-level learning. Intra-level learning is to learn the causation among the same level of nodes, while inter-level learning is to learn the cross-level causation. To model the influence of low-level nodes on high-level nodes, we aggregate low-level information into high-level nodes in inter-level learning. Figure 3 shows the learning process.

For **intra-level learning**, we adopt the same learning strategy to learn causal relations among both high-level nodes and low-level nodes. Specifically, we first apply \(L\) layers of GNN to the time-lagged data \(\{\mathbf{x}_{t-1},\cdots,\mathbf{x}_{t-p}\}\in\mathbb{R}^{d\times p}\) to obtain its embedding. In the \(l\)-th layer, the embedding \(\mathbf{z}^{(l)}\) is obtained by aggregating the nodes' embedding and their neighbors' information at the \(l-1\) layer. Then, the embedding at the last layer \(\mathbf{z}^{(L)}\) is used to predict the metric value at the time step \(t\) by an MLP layer. This process can be represented as

\[\left\{\begin{array}{l}\mathbf{z}^{(0)}=[\mathbf{x}_{t-1},\cdots,\mathbf{x }_{t-p}],\\ \mathbf{z}^{(l)}=\text{GNN}(\text{Cat}(\mathbf{z}^{(l-1)},\mathbf{W}\cdot \mathbf{z}^{(l-1)})\cdot\mathbf{B}^{(l)}),\\ \tilde{\mathbf{x}}_{t}=\text{MLP}(\mathbf{z}^{(L)};\mathbf{\Theta}),\end{array}\right. \tag{7}\]

where Cat is the concatenation operation; \(\mathbf{B}^{(l)}\) is the weight matrix of the \(l\)-th layer; GNN is activated by the RELU function to capture non-linear correlations in the time-lagged data. Our goal is to minimize the difference between the actual value \(\mathbf{x}_{t}\) and the predicted value \(\tilde{\mathbf{x}}_{t}\). Thus, the optimization objective is defined as follows

\[\mathcal{L}=\frac{1}{m}\sum_{t}(\mathbf{x}_{t}-\tilde{\mathbf{x}}_{t})^{2} \tag{8}\]

As shown in Figure 3, we conduct intra-level learning for the low-level and high-level system entities for constructing \(\mathbf{W}^{\mathcal{H}}\) and \(\mathbf{W}^{G}\), respectively. The optimization objectives for the low-level and high-level causal relations, in the same format as Equation 8, are denoted by \(\mathcal{L}_{\mathcal{H}}\) and \(\mathcal{L}_{G}\), respectively.

For **inter-level learning**, we aggregate the information of low-level nodes to the high-level nodes for constructing the cross-level causation. So, the initial embedding of high-level nodes \(\mathbf{z}^{(0)}\) is the concatenation of their time-lagged data \(\{\mathbf{x}_{t-1},\cdots,\mathbf{x}_{t-p}\}\) and aggregated low-level embeddings, which can be formulated as follows

\[\mathbf{z}^{(0)}=\text{Cat}([\mathbf{x}_{t-1},\cdots,\mathbf{x}_{t-p}],\mathbf{ W}\cdot\mathbf{z}^{(L)}) \tag{9}\]

where \(\mathbf{W}\) is a weight matrix that controls the contributions of low-level embeddings to high-level embeddings. As shown in Figure 3, there are two inter-level learning parts. The first one is used to learn the cross-level causal relations between low-level and high-level nodes, denoted by \(\mathbf{W}^{\mathcal{H}G}\). The second one is used to construct the causal linkages between high-level nodes and the system KPI, denoted by \(\mathbf{W}^{GS}\). During this process, we predict the value of the system KPI at the time step \(t\) and aim to make the predicted values close to the actual ones. Hence, we formulate the optimization objective \(\mathcal{L}_{S}\), whose format is the same as Equation 8.

In addition, the learned interdependent causal graphs must meet the acyclicity requirement. Since the cross-level causal relations \(\mathbf{W}^{\mathcal{H}G}\) and \(\mathbf{W}^{GS}\) are unidirectional, only \(\mathbf{W}^{\mathcal{H}}\) and \(\mathbf{W}^{G}\) need to be

Figure 3: The learning process of hierarchical GNNs. Intra-level learning captures causation within the same-level system entities. Inter-level learning aggregates low-level information to high-level for constructing cross-level causation.
acyclic. To achieve this goal, inspired by the work (Wang et al., 2017), we use the trace exponential function: \(h(\mathbf{W})=tr(e^{\mathbf{W}\cdot\mathbf{W}})-d=0\) that satisfies \(h(\mathbf{W})=0\) if and only if \(\mathbf{W}\) is acyclic. Here, \(\circ\) is the Hadamard product of two matrices. Meanwhile, to enforce the sparsity of \(\mathbf{W}^{\mathcal{A}}\), \(\mathbf{W}^{G}\), \(\mathbf{W}^{\mathcal{A}G}\), and \(\mathbf{W}^{GS}\) for producing robust causation, we use the \(L1\)-norm to regularize them. So, the final optimization objective is

\[\mathcal{L}_{final}=(\mathcal{L}_{\mathcal{A}}+\mathcal{L}_{G}+ \mathcal{L}_{S})\] \[+\lambda_{1}(\left\|\mathbf{W}^{\mathcal{A}}\right\|_{1}+\left\| \mathbf{W}^{G}\right\|_{1}+\left\|\mathbf{W}^{\mathcal{A}G}\right\|_{1}+ \left\|\mathbf{W}^{GS}\right\|_{1})\] \[+\lambda_{2}(h(\mathbf{W}^{\mathcal{A}})+h(\mathbf{W}^{G})) \tag{10}\]

where \(\left\|\cdot\right\|_{1}\) is the element-wise \(L1\)-norm; \(\lambda_{1}\) and \(\lambda_{2}\) are two parameters that control the contribution of regularization items. We aim to minimize \(\mathcal{L}_{final}\) through the L-BFGS-B solver. When the model converges, we construct interdependent causal networks through \(\mathbf{W}^{\mathcal{A}}\), \(\mathbf{W}^{G}\), \(\mathbf{W}^{\mathcal{A}G}\), and \(\mathbf{W}^{GS}\).

#### 3.1.2. Network Propagation on Interdependent Causal Graphs

As aforementioned, starting from the root cause entity, malfunctioning effects will propagate to neighboring entities (Han et al., 2017), and different types of system faults can trigger diverse propagation patterns. This observation motivates us to apply network propagation to the learned causal structure to mine the hidden actual root causes.

The learned interdependent causal structure is a directed acyclic graph, which reflects the causal relations from the low-level to the high-level to the system level. In order to trace back the root causes, we need to conduct a reverse analysis process. Thus, we transpose the learned causal structure to get \(<<\mathbf{G}^{\top},\mathcal{A}^{\top},\mathbf{E}>,\text{KPI}>^{1}\), then apply a random walk with restart on the interdependent causal networks to estimate the topological causal score of each entity.

Specifically, the transition probabilities of a particle on the transposed structure can be denoted by

\[H=\begin{bmatrix}H_{\mathbf{G}\mathbf{G}}&H_{\mathcal{G}\mathcal{A}}\\ H_{\mathcal{H}\mathbf{G}}&H_{\mathcal{H}\mathcal{A}\mathcal{A}}\end{bmatrix} \tag{11}\]

where \(H_{\mathbf{G}\mathbf{G}}\) and \(H_{\mathcal{H}\mathcal{A}\mathcal{A}}\) depict the walks within the same-level network. \(H_{\mathbf{G}\mathcal{A}}\) and \(H_{\mathcal{H}\mathcal{A}\mathcal{A}}\) describe the walks across different level networks. Imagine that from the KPI node, a particle begins to visit the networks. The particle randomly selects a high-level or low-level node to visit, then the particle either jumps to the low-level nodes or walks in the current graph with a probability value \(\Phi\in[0,1]\). The higher the value of \(\Phi\) is, the more possible the jumping behavior occurs. In detail, if a particle is located at a high-level node \(i\) in \(\mathbf{G}\), the probability of the particle moving to the high-level node \(j\) is

\[H_{\mathbf{G}\mathbf{G}}(i,j)=(1-\Phi)\mathbf{G}^{\top}(i,j)/\sum_{k=1}^{g} \mathbf{G}^{\top}(i,k) \tag{12}\]

or jumping to the low-level node \(b\) with a probability

\[H_{\mathbf{G}\mathcal{A}}(i,b)=\Phi\mathbf{W}(i,b)/\sum_{k=1}^{gd}\mathbf{W}( i,k) \tag{13}\]

We apply the same strategy when the particle is located at a low-level node. The particle walking between different low-level nodes has a visiting probability of \(H_{\mathcal{A}\mathcal{A}}\), whose calculation equation is similar to \(H_{\mathbf{G}\mathbf{G}}\). Moreover, the visiting probability from a low-level node to a high-level node is \(H_{\mathcal{A}\mathcal{A}}\), whose calculation equation is similar to \(H_{\mathbf{G}\mathcal{A}}\). The probability transition evolving equation of the random walk with restart can be formulated as

\[\tilde{\mathbf{p}}_{t+1}^{\top}=(1-\varphi)\tilde{\mathbf{p}}_{t}^{\top}+ \varphi\tilde{\mathbf{p}}_{rs}^{\top} \tag{14}\]

where \(\tilde{\mathbf{p}}_{t+1}^{\top}\in\mathbb{R}^{g+gd}\) and \(\tilde{\mathbf{p}}_{t}^{\top}\in\mathbb{R}^{g+gd}\) are the visiting probability distribution at different time steps; \(\tilde{\mathbf{p}}_{rs}^{\top}\in\mathbb{R}^{g+gd}\) is the initial visiting probability distribution that depicts the visiting possibility of high-level or low-level nodes at the initialization step. \(\varphi\in[0,1]\) is the restart probability. When the visiting probability distribution is convergence, we regard the probability score of the low-level nodes as the associated topological causal score.

### Individual Causal Discovery

In addition to the topological causal effects, the entity metrics of root causes themselves could fluctuate stronger than those of other system entities during the incidence of some system faults. And for some short-lived failure cases (_e.g._, fail-stop failure), there may even be no propagation patterns. Thus, we propose to individually analyze such temporal patterns in order to provide individual causal guidance for locating root causes.

Compared with the values of entity metrics in normal time, the fluctuating values are extreme and infrequent. Inspired by (Zhou et al., 2017), such extreme value follows the extreme value distribution, which is defined as:

\[U_{\zeta}:x\to exp(-(1+\zeta x)^{-\frac{1}{\zeta}}),\quad\zeta\in\mathbb{R}, \quad 1+\zeta x>0. \tag{15}\]

where \(x\) is the original value and \(\zeta\) is the extreme value index depending on the distribution of \(x\). Let the probability of potential extreme value in \(x\) be \(q\), the boundary2\(\varrho\) of normal value can be calculated through \(\mathbb{P}(X>\varrho)=q\) based on \(U_{\zeta}\). However, since the distribution of \(x\) is unknown, \(\zeta\) should be estimated. The Pickands-Bellema-de Haan theorem (Pickands and Blekema, 1992) provides an approach to estimate \(\zeta\), which is defined as follows:

Footnote 2: The boundary can be upper bound or lower bound of normal values.

Theorem 3.1 ().: _The extrema of a cumulative distribution \(F\) converge to the distribution of \(U_{\zeta}\), denoted as \(F\in D_{\zeta}\), if and only if a function \(\delta\) exists, for all \(x\in\mathbb{R}\) s.t. \(1+\zeta x>0\):_

\[\frac{\overline{F}(\eta+\delta(\eta)x)}{\overline{F}(\eta)}\quad\overline{\eta \longrightarrow\frac{1}{\zeta}}\quad(1+\zeta x)^{-\frac{1}{\zeta}}, \tag{16}\]

where \(U_{\zeta}\) refers to the extreme value distribution; \(D_{\zeta}\) refers to a Generalized Pareto Distribution; \(\eta\) is a threshold for peak normal value; and \(\tau\) is the boundary of the initial distribution. Assuming that \(\eta\) is a threshold for peak normal value, \(X-\eta\) follows a Generalized Pareto Distribution (GPD) with parameters \(\zeta\) and \(\delta\) according to the theorem, which is defined as:

\[\mathbb{P}(X-\eta>x|X>\eta)\sim(1+\frac{\zeta x}{\delta(\eta)})^{-\frac{1}{ \zeta}}. \tag{17}\]

We can utilize the maximum likelihood estimation method (Duffuffas and Blekema, 1992) to estimate \(\zeta\) and \(\delta\). Then, the boundary value \(\varrho\) can be calculated by

\[\varrho\simeq\eta+\frac{\delta}{\zeta}((\frac{qn}{N_{\eta}})^{-\zeta}-1). \tag{18}\]
where \(\eta,q\) can be provided by domain knowledge, \(n\) is the total number of observations, and \(N_{\eta}\) is the number of peak values (_i.e.,_ the number of \(X>\eta\)).

Individual causal discovery is devised based on Equation (18). Specifically, we divide the metric data of one system entity into two segments. The first segment is used for initialization, and the second one is used for detection. For initialization, we first provide the probability of the extreme value \(q\) and the threshold of the peak value \(\eta\) using a mean excess plot-based method (Bahdan et al., 2017). Then, we use the first time segment to estimate the boundary \(\varrho\) of normal value according to Equation (18). Here, \(\eta\) should be lower than \(\varrho\). For detection, we compare each value in the second time segment with \(\varrho\) and \(\eta\). If the value is larger than \(\varrho\), the value is abnormal, so we store it. If the value is less than \(\varrho\) but larger than \(\eta\), which means the boundary \(\varrho\) has been changed. Hence, we add it to the first segment and re-evaluate the parameters \(\zeta\) and \(\delta\) to get new boundaries. If the value is less than \(\eta\), it is normal, so we ignore it. Finally, we can collect all abnormal values and normalize them using the Sigmoid function. The mean of the normalized values is regarded as the individual causal score of the associated system entity.

### Causal Integration

Finally, we integrate the individual and topological causal scores of low-level system entities through the integration parameter \(0\leq\gamma\leq 1\), which can be represented as \(\mathbf{q}_{final}=r\mathbf{q}_{indio}+(1-\gamma)\mathbf{q}_{topol}\). After that, we rank low-level nodes using \(\mathbf{q}_{final}\) and select the top \(K\) results as the final root causes.

## 4. Experiments

### Experimental Setup

#### 4.1.1. Datasets

We evaluated REASON on the following three real-world datasets for the task of root cause localization. **1) AIOps**: This dataset was collected from a real micro-service system. This system has 234 microservice pods/applications (low-level system entities) that are deployed to 5 cloud servers (high-level system entities). The operators collected metrics data (_e.g.,_ CPU Usage, Memory Usage) of high-level and low-level system entities from May 2021 to December 2021. There are 5 system faults during this time period. **2) WADI (Bahdan et al., 2021)**: This dataset was collected from a water distribution testbed, which owns 3 stages (high-level entities) and 123 sensors (low-level entities). It has 15 system faults collected in 16 days. In these datasets, low-level entities affiliate with high-level entities, and same-level entities invoke each other. **3) Swat (Sandel, 2021)**: This dataset was collected from a water treatment testbed, which consists of 6 stages (high-level entities) that have 51 sensors (low-level entities). It has 16 system faults collected in 11 days.

#### 4.1.2. Evaluation Metrics

We evaluated the model performance with the following three widely-used metrics (Zhu et al., 2017; Wang et al., 2018):

**Precision@K (PR@K)**. It denotes the probability that the top-\(K\) predicted root causes are real, defined as

\[\text{PR@K}=\frac{1}{|A|}\sum_{a\in\mathbb{A}}\frac{\sum_{i<K}R_{a}(i)\in V_ {a}}{min(K,|V_{a}|)}, \tag{19}\]

where \(\mathbb{A}\) is the set of system faults; \(a\) is one fault in \(\mathbb{A}\); \(V_{a}\) is the real root causes of \(a\); \(R_{a}\) is the predicted root causes of \(a\); and \(i\) refers to the \(i\)-th predicted cause of \(R_{a}\).

**Mean Average Precision@K (MAP@K)**. It assesses the model performance in the top-\(K\) predicted causes from the overall perspective, defined as

\[\text{MAP@K}=\frac{1}{K|A|}\sum_{a\in\mathbb{A}}\sum_{1\leq j\leq K}\text{PR@ j}, \tag{20}\]

where a higher value indicates better performance.

**Mean Reciprocal Rank (MRR)**. This metric measures the ranking capability of models. The larger the MRR value is, the further ahead the predicted positions of the root causes are; thus, operators can find the real root causes more easily. MRR is defined as

\[\text{MRR}=\frac{1}{A}\sum_{a\in\mathbb{A}}\frac{1}{rank_{R_{a}}}, \tag{21}\]

where \(rank_{R_{a}}\) is the rank number of the first correctly predicted root cause for system fault \(a\).

#### 4.1.3. Baselines

We compared REASON with the following five causal discovery models: **1) PC(Rang et al., 2018)** is a classic constraint-based method. It first identifies the skeleton of the causal graph with the independence test, then generates the orientation direction using the v-structure and acyclicity constraints. **2) C-LSTM(Wang et al., 2018)** captures the nonlinear Granger causality that existed in multivariate time series by using LSTM neural networks. **3) Dynotas(Rang et al., 2018)** is a score-based method that uses the structural vector autoregression model to construct dynamic Bayesian networks. **4) GOLEM(Wang et al., 2018)** employs a likelihood-based score function to relax the hard DAG constraint in NOTEARS. **5) GNN** is a simplified version of our causal discovery method. It only uses GNN to learn causal structures among low-level system entities.

Since none of the above baselines can be directly applied to learn the hierarchical interdependent causation, we only utilized the entity metrics to construct causation between low-level system entities and the system KPI. We then selected the top-\(K\) entities with the highest causal scores as the root causes. To verify the effectiveness of the network propagation module (see Section 3.1.2), we applied it to the causal structures learned by these baselines and analyzed model performance changes.

In addition, to study the impact of each technical component of REASON, we developed the following model variants: (1) To assess the benefits of inter-level learning (see Section 3.1), we implemented REASON-N by removing the inter-level learning in topological causal discovery while keeping the intra-level learning of low-level system entities, network propagation and individual causal discovery. (2) To evaluate the necessity and effectiveness of integrating the individual and topological causal discovery, we developed two variants: REASON-I, which only keeps the individual causal discovery, and REASON-T, which solely keeps the topological causal discovery. (3) To verify the efficacy of hierarchical GNN-based causal discovery, we replaced the causal discovery component of REASON with PC, C-LSTM, Dynotears, and GOLEM, respectively, to implement model variants denoted as REASON-P, REASON-C, REASON-D, and REASON-G.
All experiments were conducted on a server running Ubuntu 18.04.5 with Intel(R) Xeon(R) Silver 4110 CPU @ 2.10GHz, 4-way GeForce RTX 2080 Ti GPUs, and 192 GB memory. In addition, all methods were implemented using Python 3.8.12 and PyTorch 1.7.1.

### Performance Evaluation

#### 4.2.1. Overall Performance

Table 1, Table 2, and Table 3 present the overall performance of all models, where a larger value indicates better performance. We have two key observations: First, REASON can significantly outperform all the baselines on all three datasets. For example, compared to the second-best method, REASON can improve PR@10, MAP@10, and MRR by at least 21.9%, 15.7%, and 6.29%, respectively. The underlying driver is that REASON can capture more complex malfunctioning effects by integrating individual and topological analyses, and learning interdependent causal networks. Second, GNN is the best baseline model that outperforms others on most datasets. A possible explanation is that graph neural

\begin{table}
\begin{tabular}{c|c|c|c|c|c|c|c|c|c|c} \hline  & PR@1 & PR@3 & PR@5 & PR@7 & PR@10 & MAP@3 & MAP@5 & MAP@7 & MAP@10 & MRR \\ \hline REASON & **25.0\%** & **28.13\%** & **66.67\%** & **76.04\%** & **84.38\%** & **23.96\%** & **35.0\%** & **46.73\%** & **57.60\%** & **40.99\%** \\ GNN & 18.75\% & 19.79\% & 43.75\% & 52.08\% & 62.50\% & 18.06\% & 27.92\% & 33.63\% & 41.88\% & 34.77\% \\ PC & 12.5\% & 13.54\% & 34.38\% & 47.92\% & 58.33\% & 12.85\% & 20.42\% & 26.64\% & 35.0\% & 26.16\% \\ C-LSTM & 12.5\% & 13.54\% & 28.13\% & 40.63\% & 52.08\% & 13.89\% & 17.71\% & 23.81\% & 31.88\% & 29.35\% \\ Dynotears & 12.5\% & 29.17\% & 32.29\% & 34.38\% & 42.71\% & 20.14\% & 24.38\% & 26.93\% & 30.83\% & 27.85\% \\ GOLEM & 6.25\% & 7.29\% & 12.5\% & 39.58\% & 47.92\% & 7.64\% & 9.58\% & 16.96\% & 25.0\% & 22.36\% \\ \hline \end{tabular}
\end{table}
Table 1. Overall performance _w.r.t._ Swat dataset.

\begin{table}
\begin{tabular}{c|c|c|c|c|c|c|c|c|c|c|c} \hline  & PR@1 & PR@3 & PR@5 & PR@7 & PR@10 & MAP@3 & MAP@5 & MAP@7 & MAP@10 & MRR \\ \hline REASON & **28.57\%** & **59.52\%** & **65.0\%** & **76.19\%** & **79.76\%** & **42.46\%** & **50.62\%** & **57.41\%** & **63.76\%** & **53.35\%** \\ GNN & 14.28\% & 26.19\% & 34.28\% & 42.86\% & 54.76\% & 21.83\% & 25.31\% & 30.15\% & 37.54\% & 32.71\% \\ PC & 7.14\% & 27.38\% & 35.0\% & 44.05\% & 50.0\% & 16.27\% & 23.90\% & 28.47\% & 34.57\% & 27.74\% \\ C-LSTM & 0\% & 20.24\% & 35.0\% & 47.62\% & 51.19\% & 11.51\% & 18.55\% & 25.83\% & 32.73\% & 24.40\% \\ Dynotears & 7.14\% & 14.29\% & 30.00\% & 29.76\% & 47.62\% & 10.71\% & 17.43\% & 20.95\% & 26.81\% & 22.23\% \\ GOLEM & 0\% & 19.05\% & 40.0\% & 46.43\% & 53.57\% & 9.92\% & 20.38\% & 27.82\% & 34.83\% & 23.48\% \\ \hline \end{tabular}
\end{table}
Table 2. Overall performance _w.r.t._ WADI dataset.

\begin{table}
\begin{tabular}{c|c|c|c|c|c|c|c|c|c|c} \hline  & \multicolumn{2}{c|}{PC} & \multicolumn{2}{c|}{GLOEM} & \multicolumn{2}{c|}{Dynotears} & \multicolumn{2}{c|}{C-LSTM} & \multicolumn{2}{c}{GNN} \\ \cline{2-11}  & Original & Propagate & Original & Propagate & Original & Propagate & Original & Propagate & Original & Propagate \\ \hline Swat & 35.0\% & **37.39\%** & 25.0\% & **33.44\%** & 30.83\% & **37.08\%** & 31.87\% & **34.16\%** & 41.87\% & **49.16\%** \\ \hline WADI & 34.57\% & **35.71\%** & 34.83\% & **38.05\%** & 26.81\% & **33.76\%** & 32.72\% & **42.61\%** & 37.53\% & **45.98\%** \\ \hline AIOPS & 28.0\% & **30.0\%** & 38.0\% & **54.0\%** & 38.0\% & **58.0\%** & 18.0\% & **48.0\%** & 38.0\% & **60.0\%** \\ \hline \end{tabular}
\end{table}
Table 4. The influence of network propagation in terms of MAP@10

\begin{table}
\begin{tabular}{c|c|c|c|c|c|c|c|c|c|c|} \hline  & \multicolumn{2}{c|}{PC} & \multicolumn{2}{c|}{GLOEM} & \multicolumn{2}{c|}{Dynotears} & \multicolumn{2}{c|}{C-LSTM} & \multicolumn{2}{c}{GNN} \\ \cline{2-11}  & Original & Propagate & Original & Propagate & Original & Propagate & Original & Propagate & Original & Propagate \\ \hline Swat & 26.16\% & **32.27\%** & 22.36\% & **30.42\%** & 27.85\% & **33.98\%** & 29.35\% & **32.85\%** & 34.77\% & **40.43\%** \\ \hline WADI & 27.74\% & **30.74\%** & 23.48\% & **25.89\%** & 22.22\% & **34.28\%** & 24.39\% & **33.27\%** & 32.71\% & **36.40\%** \\ \hline AIOPS & 14.0\% & **25.35\%** & 31.22\% & **37.74\%** & 30.79\% & **50.77\%** & 10.82\% & **24.73\%** & 30.65\% & **62.48\%** \\ \hline \end{tabular}
\end{table}
Table 5. The influence of network propagation in terms of MRR
networks can facilitate the learning of non-linear causal relations among system entities via message passing. Thus, the experimental results on three datasets demonstrate the superiority of REASON in locating root causes over other baselines.

#### 4.2.2. Influence of Network Propagation

Here, we applied our network propagation mechanism (see Section 3.1.2) to the causal structures learned by each baseline model to evaluate its effect on performance. The results are shown in Table 4 and Table 5. Our first finding is that network propagation can always improve the model performance for all models on all datasets. This observation strongly supports our assumption that network propagation is beneficial for capturing the propagation patterns of malfunctioning effects, resulting in a superior root cause localization performance. Moreover, we observe that across all models, network propagation yields greater performance enhancement on AIOps than the other two datasets. A possible reason is that AIOps contains explicit invoking relations among different pods, resulting in learning stronger causation compared with Swat and WADI.

#### 4.2.3. Ablation studies of REASON

Figure 4 shows ablation studies of REASON to examine the necessity of each technical component using PR@K and MAP@K. We can find that REASON significantly outperforms REASON-N on Swat and WADI. The underlying driver is that since REASON-N focuses on modeling causation among low-level entities only, using such causal structures, REASON-N is unable to capture cross-network propagation patterns of malfunctioning effects, leading to worse model performance. The second finding is that REASON is superior to both REASON-T and REASON-I in most cases. This observation indicates that integrating individual and topological causal discovery results can sufficiently capture the fluctuation and propagation patterns of malfunctioning effects for precisely locating root causes. Thus, each technical component of REASON is indispensable for keeping excellent root cause localization performance.

#### 4.2.4. Impact of Hierarchical GNN-based Causal Discovery

Figure 5 evaluates the effectiveness of the proposed hierarchical GNN-based causal discovery method. Our key observations are two-fold. First, we find that REASON significantly outperforms all model variants. The underlying driver is that the message-passing mechanism of GNN can learn more robust non-linear causal relations through

Figure 4. Ablation studies of REASON.

Figure 5. The impact of hierarchical GNN-based causal learning process.
sharing neighborhood information. Moreover, REASON-P outperforms REASON-C across all datasets in terms of MAP@10, while the result is the opposite in terms of MRR. A possible explanation is that PC learns more causal relations between system entities than C-LSTM. As a result, REASON-P is able to identify more actual root causes by propagating on the learned causal structures, but their ranks are not at the top owing to more root cause candidates.

#### 4.2.5. Parameter Analysis

We investigated the integration parameter \(\gamma\) and the number of layers \(L\) in GNN. \(\gamma\) controls the contribution of the individual and topological causal discovery for root cause localization. The number of layers \(L\) in GNN impacts the learning scenario of interdependent causal structures. Figure 6 presents our parameter analysis results. It can be seen that although the optimal \(\gamma\) values for different datasets vary, REASON can achieve optimal or near-optimal results on all three datasets using a similar small \(\gamma\) value. For instance, the best value of \(\gamma\) for Swat, WADI, and AIOps is 0.2, 0.1, and 0.8, respectively. But when we use \(\gamma=0.1\), the best value for WADI, the overall performance of REASON only drops a little in terms of both MAP@10 and MRR. For instance, compared with the optimal results, the MRR value only decreased by 0.01 on Swat and 0.04 on AIOps, respectively. This indicates that although the propagation of malfunctioning effects varies amongst datasets, the topological component contributes more to the model performance than the individual component, which further supports our findings in Section 4.2.3. Thus, in most cases, a small \(\gamma\) value (_e.g._, \(\gamma=0.1\)) would be a good choice. Second, when the number of GNN layers rose, we did not observe improved model performance. This is because a large number of GNNs may cause the information of each node to become highly similar, hindering the learning of robust causal relationships.

#### 4.2.6. A Case Study

Finally, we conducted a case study to further illustrate the learned interdependent causal networks by utilizing the system failure of AIOps on September 1, 2021. Operators built up a microservice system and simulated system faults to collect metrics data for analysis. The detailed collection procedure is as follows: First, the operators deployed the system on three servers that are _compute-2_, _infra-1_, and _control-plane-1_. Then, they sent requests periodically to the pod _sdn-c7kq_ to observe the system's latency. Next, to simulate the malfunctioning effects of the root cause, the operators used an _opensall_ command to make the pod _catalogue-xfjp_ have an extremely high CPU load, which affected some other pods on different servers, and eventually caused the system fault. Finally, the operators collected all entity metrics (_e.g._, CPU Usage, Memory Usage) of all system entities (_e.g._, servers, pods).

Based on the collected metrics data, we applied REASON to learn the interdependent causation between system entities and the system KPI for locating root causes, which reflects the real operation circumstances. Figure 7 shows the learned interdependent causal structures based on the CPU Usage metric. According to it, _infra-1_ server is the one most likely to increase in system latency. In this server, _catalogue-xfjp_ is the root cause, whose negative effects propagate to _'sdn-c7kqg_, resulting in the malfunction of _infra-1_. This observation illustrates that REASON can precisely locate the root causes and provide an explanation for the located outcomes.

## 5. Related Work

**Root Cause Analysis (RCA)**, also known as fault localization, focuses on identifying the root causes of system failures/faults from symptom observations (Zhou et al., 2017). In recent years, many domain-specific RCA approaches (Zhou et al., 2017; Wang et al., 2018; Wang et al., 2018) have been proposed for maintaining the robustness of complex systems in various domains. For instance, in the energy management domain, Capozzoli _et al._ utilized statistical techniques and DNNs to identify the reason for abnormal energy consumption in smart buildings (Brandon et al., 2016). In the web development domain, Brandon _et al._ proposed a graph representation framework to localize root causes in microservice systems by comparing anomalous situations and graphs (Brandon et al., 2016). Different from the existing works, the proposed REASON framework is a generic RCA approach that analyzes the surveillance multi-variate time series data from both individual and topological perspectives. Moreover, REASON captures the interdependent network properties present in many real-world systems to enhance RCA performance.

**Causal Discovery in Time Series** aims to learn causal relationships from observational time series data (Brandon et al., 2016). Existing methods can be broadly classified into four categories: (i) Granger causality approaches (Zhou et al., 2017; Wang et al., 2018), in which the causation is assessed based on whether one time series is helpful in predicting another; (ii)

Figure 6. Parameter analysis of REASON.
Constraint-based approaches (Liu et al., 2017; Wang et al., 2018; Wang et al., 2018), in which a causal structure is learned based on the conditional independence test and v-structure rules; (iii) Noise-based approaches (Wang et al., 2018; Wang et al., 2018), in which the causation is depicted by equations that reflect the causation between different variables and noises; (iv) Score-based approaches (Wang et al., 2018; Wang et al., 2018), in which a causal structure's quality is assessed by a scoring function. REASON belongs to the score-based causal discovery category. Existing causal discovery methods could only handle time series or isolated graphs, ignoring the structural and dynamical features one may want to model explicitly. In this paper, we propose a hierarchical graph neural networks based method that could model interdependent causal structures from multi-variable time series.

**Interdependent Networks** are often referred to as network of networks (NoN), in which complex networks interact and influence one another (Wang et al., 2018; Wang et al., 2018). Numerous real-world systems exhibit such structural and dynamical features that differ from those observed in isolated networks. To overcome the limitation of prior efforts on isolated graph analysis, in recent years, increasing research efforts have been focused on interdependent networks and their applications. For example, Ni _et al._ employed interdependent networks to illustrate the academic influence of scholars based on their research area and publications (Liard et al., 2018). Laird _et al._ studied the interdependent relationship between cancer pain and depression (Laird et al., 2018). These examples demonstrate the efficiency of modeling complicated systems via interdependent networks. In recent years, several studies (Liu et al., 2017; Wang et al., 2018; Wang et al., 2018) have begun to explore how the interdependent networks model can be applied to root cause analysis. However, there are two key differences between REASON and other previous works: 1) Existing works only consider physical or statistical correlations, but not causation. 2) Existing interdependent networks are constructed using domain knowledge or system rules. REASON can automatically discover the interdependent causal graphs from monitoring metrics data for root cause analysis.

## 6. Conclusion

In this paper, we investigated the challenging problem of root cause localization in complex systems with interdependent network structures. We proposed REASON, a generic framework for root cause localization through mining interdependent causation and propagation patterns of faulted effects. Hierarchical graph neural networks were used to represent non-linear intra-level and inter-level causation and to improve causal discovery among system entities via message transmission. We conducted comprehensive experiments on three real-world datasets to evaluate the proposed framework. The experimental results validate the effectiveness of our work. Additionally, through ablation studies, parameter analysis, and case studies, the importance of capturing interdependent structures for root cause localization has been well verified. An interesting direction for further exploration would be incorporating other sources of data, such as system logs, with the time series data for root cause analysis in complex systems.

Figure 7. Interdependent causal structures learned from AIOps dataset. Applications/pods are denoted by solid nodes, in which the red solid node is the root cause. The numbers on each causal relation edge with black color indicates the causal score between two connected nodes. The red dashed line reflects the backtracing process of the root cause.