Max-linear models on directed acyclic graphs

Introduction

Graphical models are a popular tool to analyze and visualize the conditional independence properties between random variables (see e.g. Koller and Friedman and Lauritzen ). Each node in the graph indicates a random variable, and the absence of an edge between two nodes represents a conditional independence property between the corresponding variables. We focus on directed graphical models, also called Bayesian networks, where edge orientations come along with an intuitive causal interpretation. The conditional independence among the random variables, which is induced by a directed acylic graph (DAG), can be explored using the (directed) Markov property: each variable is conditionally independent of its non-descendants (excluding the parents) given its parents (cf. , Chapter 3.2).

Despite many areas of applications for directed graphical models, ranging from artificial intelligence, decision support systems, and engineering to genetics, geology, medicine, and finance (see e.g. Pourret et al. ), graphical modelling of random vectors has mainly been limited to discrete and Gaussian distributions; see e.g. . In the context of risk assessment, risk exposures are usually modelled by continuous variables, however, the assumption of Gaussianity leads invariably to severe underestimation of large risks and therefore to unsuitable models.

Recursive structural equation models (recursive SEMs) offer a possibility to construct directed graphical models; cf. Bollen , Pearl and Spirtes et al. . For a given DAG $\mathcal{D}=(V,E)$ with nodes $V=\{1,\ldots,d\}$ and edges $E=\{(k,i):i\in V\mbox{ and }k\in{\rm pa}(i)\}$ define

where ${\rm pa}(i)$ denotes the parents of node $i$ in $\mathcal{D}$ and $f_{i}$ is a real-valued measurable function; $Z_{1},\ldots,Z_{d}$ are independent noise variables. Thus, a recursive SEM is specified by an underlying causal structure in terms of a DAG $\mathcal{D}$, the functions $f_{i}$, and the distributions of $Z_{i}$ for $i=1,\ldots,d$. In this setting, the distribution of $\mathbf{X}$ is uniquely defined by the distributions of the noise variables and, denoting by ${{\rm nd}}(i)$ the non-descendants of node $i$,

i.e., the distribution of $\mathbf{X}$ is Markov relative to $\mathcal{D}$ (see Theorem 1.4.1 and the related discussion in Pearl ). Recently, recursive linear SEMs and generalisations in a Gaussian setting have received particular attention; see Bühlmann et al. , Ernest et al. and references therein).

Our focus is not on sums but on maxima, where natural candidates for the noise distributions are the extreme value distributions or distributions in their domain of attraction (see e.g. Resnick ). We introduce a recursive SEM, which is to the best of our knowledge new. Define a recursive max-linear (ML) model $\mathbf{X}=(X_{1},\ldots,X_{d})$ on a DAG $\mathcal{D}$ by

with independent non-negative random variables $Z_{1},\dots,Z_{d}$ and positive weights $c_{ki}$ for all $i\in V$ and $k\in{{\rm pa}}(i)\cup\{i\}$.

In this paper we investigate structural properties as well as graph properties of a recursive ML model $\mathbf{X}$ on a DAG $\mathcal{D}$. We will show that $\mathbf{X}$ is a max-linear (ML) model (for background on ML models in the context of extreme value theory see e.g. de Haan and Ferreira , Chapter 6) in the sense that

with $Z_{1},\ldots,Z_{d}$ as in (1.3), and $B=(b_{ij})_{d\times d}$ is a matrix with non-negative entries. We call $B$ max-linear (ML) coefficient matrix of $\mathbf{X}$ and its entries max-linear (ML) coefficients.

The ML coefficients of $\mathbf{X}$ can be determined by a path analysis of $\mathcal{D}$. Throughout we write $k\to i$, if there is an edge from $k$ to $i$ in $\mathcal{D}$. We assign a weight to every path $p=[j=k_{0}\rightarrow k_{1}\rightarrow\dots\rightarrow k_{n}=i]$, which is the product of the edge weights along $p$ multiplied by the weight of the noise variable $Z_{j}$ (a concept, which goes back to Wright ):

We will show that the ML coefficients are given for $i\in V$ by

where $P_{ji}$ is the set of paths from $j$ to $i$ and ${\rm an}(i)$ the ancestors of $i$.

From (1.6) it is clear that not all paths are needed for representing $\mathbf{X}$ as ML model (1.4). This perception leads to a complexity reduction of the model in different ways and in different situations. For every specific component $X_{i}$ of $\mathbf{X}$ only those paths with terminal node $i$, which carry the maximum weight, are relevant for its representation (1.4), and we call them max-weighted paths. All other paths can be disposed of without changing this representation. It is even sufficient to consider one max-weighted path in $\mathcal{D}$ from every ancestor of $i$ to $i$. Consequently, $X_{i}$ can be represented as component of a recursive ML model on a polytree with node set ${\rm An}(i)$ and with the same weights and noise variables as in the original representation (1.3).

However, in general none of these individual polytrees represents all components of $\mathbf{X}$ in the sense of (1.3) simultaneously. Still there may be subgraphs of $\mathcal{D}$ and weights such that all components of $\mathbf{X}$ have representation (1.3), and we present all such possible subgraphs and weights. In particular, we characterize the smallest subgraph $\mathcal{D}^{B}$ of this kind, which we call minimum max-linear (ML) DAG of $\mathbf{X}$, and point out its prominent role.

We are also interested in all DAGs, which represent $\mathbf{X}$ as a recursive ML model, and show how the corresponding weights in representation (1.3) can be identified from the ML coefficient matrix of $\mathbf{X}$. In this context, we also give necessary and sufficient conditions on a matrix to be the ML coefficient matrix of any recursive ML model.

It is a simple but important observation that there is a natural order between the components of $\mathbf{X}$; from (1.3) we see immediately that $X_{i}\geq c_{ki}X_{k}$ holds for all $i\in V$ and $k\in{\rm pa}(i)$. For every component of $\mathbf{X}$ and some $U\subseteq V$, we find lower and upper bounds in terms of $\mathbf{X}_{U}:=(X_{l},l\in U)$. Often we do not need all components of $\mathbf{X}_{U}$ to compute the best bounds of $X_{i}$ in terms of components of $\mathbf{X}_{U}$. If $i\in U$, then an upper and lower bound is given by $X_{i}$ itself; otherwise, for a lower bound, we only need to consider a component $X_{j}$ of $\mathbf{X}_{U}$ if $j\in{\rm an}(i)$, but no max-weighted path from $j$ to $i$ passes through some node in $U\setminus\{j\}$. A similar result and concept applies for the upper bound of $X_{i}$. Thus, the max-weighted paths also lead in this context indirectly to a complexity reduction. We will also use the max-weighted ancestors of $i$ in $U$ to obtain a minimal representation of $X_{i}$ in terms of $\mathbf{X}_{U}$ and noise variables.

Our paper is organized as follows. In Section 2 we discuss the max-linearity of a recursive ML model $\mathbf{X}$ and express its ML coefficient matrix in terms of a weighted adjacency matrix of a corresponding DAG. Section 3 introduces the important notion of a max-weighted path and studies its consequences for the ML coefficients. In Section 4 we give necessary and sufficient conditions for a ML model being a recursive ML model on a given DAG. Section 5 is devoted to the minimum ML DAG of $\mathbf{X}$ as the DAG with the minimum number of edges within the class of all DAGs representing $\mathbf{X}$ in the sense of (1.3). In Section 6, given a set of node variables, we investigate which information can be drawn for the other components of $\mathbf{X}$. This results in lower and upper bounds for the components. Finally, we derive a minimal representation for the components of $\mathbf{X}$ as max-linear functions of a subset of node variables and certain noise variables.

Max-linearity of a recursive max-linear model

For a recursive ML model $\mathbf{X}$ on a DAG $D=(V,E)$, given by (1.3), we derive its max-linear representation (1.4). We start with our leading example, the diamond-shaped DAG depicted below.

[Max-linear representation of a recursive ML model] Consider a recursive ML model $\mathbf{X}=(X_{1},X_{2},X_{3},X_{4})$ with DAG

and weights $c_{ki}$ for $i\in V$ and $k\in{\rm Pa}(i)$. We obtain for the random variables $X_{1},$ $X_{2}$, $X_{3}$, and $X_{4}$:

Thus $\mathbf{X}$ satisfies (1.4) with ML coefficient matrix

i.e., the ML coefficients satisfy (1.6). Moreover, $B$ is an upper triangular matrix, since $\mathcal{D}$ is well-ordered (cf. Remark 2.3(ii)). $\Box$

The following result shows that such a representation can be obtained in general: every component of a recursive ML model has a max-linear representation in terms of its ancestral noise variables and an independent one. It also provides a general method to calculate the ML coefficients by a path analysis as described in (1.5) and (1.6).

Let $\mathbf{X}$ be a recursive ML model with DAG $\mathcal{D}$, and let $B=(b_{ij})_{d\times d}$ be the matrix with entries as defined in (1.6). Then

i.e., $B$ is the ML coefficient matrix of $\mathbf{X}$.

We know that every DAG may be well-ordered (see Remark 2.3(ii)). Hence, without loss of generality we assume throughout this proof that $\mathcal{D}$ is well-ordered. We prove the identity (2.1) by induction on the number of nodes of $\mathcal{D}$. For $d=1$ we have by (1.3)

where the last equality holds by (1.6). Suppose that (2.1) holds for a recursive ML model $\mathbf{X}$ of dimension $d$; i.e.,

Now consider a $(d+1)$-variate recursive ML model, and note that for every $i\in\{1,\ldots,d\}$ we have $(d+1)\in V\setminus{{{\rm pa}}}(i)$, since $\mathcal{D}$ is well-ordered. Thus, in order to verify (2.1) for the nodes $i\in\{1,\dots,d\}$, it suffices to consider the subgraph $\mathcal{D}[\{1,\dots,d\}]=(\{1,\dots,d\},E\cap(\{1,\dots,d\}\times\{1,\dots,d\}))$. Due to the induction hypothesis, (2.1) holds for $\mathcal{D}[\{1,\dots,d\}]$ and, hence, also for $\mathcal{D}$. So we can use this hypothesis and (A.1) to obtain

Observe that every path from some $j$ to $d+1$ is of the form $p=[j\to\ldots\to k\to d+1]$ for some $k\in{{\rm de}}(j)\cap{{{\rm pa}}}(d+1)$, or an edge $j\to d+1$ corresponding to $j\in{\rm pa}(d+1)$. From (1.5), the path $p$ has weight $d_{j,d+1}(p)=d_{jk}(p)c_{k,d+1}$, and the edge $j\to d+1$ has weight $d_{j,d+1}([j\to d+1])=c_{jj}c_{j,d+1}$. This yields

where we have used that $b_{j,d+1}=\bigvee\limits_{p\in P_{j,d+1}}d_{j,d+1}(p)$ for $j\in{{\rm an}}(d+1)$ and $b_{d+1,d+1}=c_{d+1,d+1}$. ∎

By (1.6) the ML coefficient $b_{ji}$ of $\mathbf{X}$ is different from zero if and only if $j\in{\rm An}(i)$. This information is contained in the reachability matrix $R=(r_{ij})_{d\times d}$ of $\mathcal{D}$, which has entries

If the $ji$-th entry of $R$ is equal to one, then $i$ is reachable from $j$.

Let $\mathcal{D}$ be a DAG with reachability matrix $R$.

The ML coefficient matrix $B$ is a weighted reachability matrix of $\mathcal{D}$; i.e., $R={\rm sgn}(B)$.

Every DAG $\mathcal{D}$ can be well-ordered, which means that the set $V=\{{1},\dots,d\}$ of nodes is linearly ordered in a way compatible with $\mathcal{D}$ such that $k\in{{{\rm pa}}}(i)$ implies $k<i$ (see e.g. Appendix A of Diestel ). If $\mathcal{D}$ is well-ordered, then $B$ and $R$ are upper triangular matrices.

Finding the ML coefficient matrix $B$ from $\mathcal{D}$ and the weights in (1.3) by a path analysis as described in (1.5) and (1.6) would be very inefficient. We may, however, compute $B$ by means of a specific matrix multiplication.

The matrix product $\odot$ allows us to present the problem of characterising representation (2.1) from (1.3) in terms of $B$, involving the weighted adjacency matrix $(c_{ij}{\mathbf{1}}_{{\rm pa}(j)}(i))_{d\times d}$ of $\mathcal{D}$.

Let $\mathbf{X}$ be a recursive ML model with DAG $\mathcal{D}$ and weights $c_{ki}$ for $i\in V$ and $k\in{\rm Pa}(i)$ as in (1.3). Furthermore, define the matrices

Then the ML coefficient matrix $B$ of $\mathbf{X}$ from Theorem 2.2 has representation

For $d=1$ we know from (1.6) that $b_{11}=c_{11}$. Hence, $B=A$. Now assume that $d\geq 2$. First we show that, if $\mathcal{D}$ has a path of length $n$ (a path consisting of $n$ edges) from node $j$ to node $i$, then the $ji$-th entry of the matrix $A_{1}\odot A_{0}^{\odot(n-1)}$ is equal to the maximum weight of all paths of lengths $n$ from $j$ to $i$, otherwise it is zero. The proof is by induction on $n$.

An edge $j\to i$, which is the only path of length $n=1$, has the weight $d_{ji}([j\to i])=c_{jj}c_{ji}$. Since the $ji$-th entry of the matrix $A_{1}\odot A_{0}^{\odot 0}=A_{1}\odot{\rm id}_{d\times d}=A_{1}$ is given by $c_{jj}c_{ji}{\boldsymbol{1}}_{{\rm pa}(i)}(j)$, the statement is true for $n=1$.

Denote by $a_{n,ji}$ and $a_{n+1,ji}$ the $ji$-th entry of $A_{1}\odot A_{0}^{\odot(n-1)}$ and $A_{1}\odot A_{0}^{\odot n}$, respectively. As $A_{1}\odot A_{0}^{\odot n}=(A_{1}\odot A_{0}^{\odot(n-1)})\odot A_{0}$, the $ji$-th entry of $A_{1}\odot A_{0}^{\odot n}$ is given by $a_{n+1,ji}=\bigvee_{k=1}^{d}a_{n,jk}a_{0,ki}=\bigvee_{k=1}^{d}a_{n,jk}c_{ki}\mathbf{1}_{{\rm pa}(i)}(k)$. We obtain from the induction hypothesis and (1.5) that $a_{n,jk}a_{0,ki}$ is zero, if $\mathcal{D}$ does not contain a path of length $n$ from $j$ to $k$ or the edge $k\to i$; otherwise it is equal to the maximum weight of all paths which consist of a path of length $n$ from $j$ to $k$ and the edge $k\to i$. Since every path of length $n+1$ from $j$ to $i$ is of this form for some $k\in V$, the $ji$-th entry of $A_{1}\odot A_{0}^{\odot n}$ is indeed equal to the maximum weight of all paths of length $n+1$ from $j$ to $i$ if there exists such a path, otherwise it is zero.

Finally, recall from (1.6) that for $i\in V$ and $j\in{\rm an}(i)$ the ML coefficient $b_{ji}$ is equal to the maximum weight of all paths from $j$ to $i$, and note that due to acyclicity, a path in $\mathcal{D}$ is at most of length $d-1$. Thus, if $j\in{\rm an}(i)$ then the $ji$-th entry of $\bigvee_{k=0}^{d-2}A_{1}\odot A_{0}^{\odot k}$ is equal to $b_{ji}$, otherwise it is zero. Since by (1.6), $b_{ii}=c_{ii}$ and $b_{ji}=0$ for $j\in V\setminus{\rm An}(i)$, the ML coefficient matrix $B$ is given by

The following has been shown in the proof of Theorem 2.4.

If $\mathcal{D}$ has a path of length $n$ from $j$ to $i$, the $ji$-th entry of the matrix $A_{1}\odot A_{0}^{\odot(n-1)}$ is equal to the maximum weight of all paths of length $n$ from $j$ to $i$, otherwise the entry is zero.

Summarizing the noise variables of $\mathbf{X}$ into the vector $\mathbf{Z}=(Z_{1},\ldots,Z_{d})$, the representation (2.1) of $\mathbf{X}$ can be written by means of the product $\odot$ as

Consequently, the definition of the matrix product $\odot$ modifies and extends the definition given in Wang and Stoev [18, Section 2.1, Eq. (2)].

Max-weighted paths and submodels

Given a recursive ML model $\mathbf{X}$ with DAG $\mathcal{D}=(V,E)$, weights $c_{ki}$ for $i\in V$ and $k\in{\rm Pa}(i)$, and ML coefficient matrix $B=(b_{ij})_{d\times d}$, we investigate the paths of $\mathcal{D}$, their particular weights, relations between the ML coefficients, and an induced subgraph structure.

From (1.6) and (2.1) we know that a path $p$ from $j$ to $i$, whose weight $d_{ji}(p)$ is strictly smaller than $b_{ji}$ does not have any influence on the distribution of $\mathbf{X}$. This fact suggests the following definition.

Let $\mathbf{X}$ be a recursive ML model with DAG $\mathcal{D}=(V,E)$, ML coefficient matrix $B$, and path weights as in (1.5). We call a path $p$ from $j$ to $i$ a max-weighted path (in $\mathcal{D}$) if $b_{ji}=d_{ji}(p)$. $\Box$

A prominent example, where all paths are max-weighted, is the following.

[Polytree] A polytree is a DAG whose underlying undirected graph has no cycles; polytrees have at most one path between any pair of nodes. Thus, assuming that $\mathbf{X}$ is a recursive ML model on a polytree, all paths must be max-weighted. $\Box$

The next example emphasizes the importance and consequences of max-weighted paths, which we will investigate in more detail in the next sections.

[Max-weighted path, graph reduction] Consider a recursive ML model $\mathbf{X}=(X_{1},X_{2},X_{3})$ with DAG

weights $c_{11},c_{12},c_{13},c_{22},c_{23},c_{33}$, and ML coefficient matrix $B$. We distinguish between two situations: (1) If $c_{13}>c_{12}c_{23}$, then the edge $1\to 3$ is the unique max-weighted path from $1$ to $3$. (2) If, however, $c_{13}\leq c_{12}c_{23}$, then $b_{13}=c_{11}c_{12}c_{23}=\frac{b_{12}b_{23}}{b_{22}}$ and the path $[1\to 2\to 3]$ is max-weighted. We obtain in this case

Thus, $\mathbf{X}$ is also a recursive ML model on the DAG

Here $\mathcal{D}^{B}$ is the DAG with minimum number of edges such that ${\rm sgn}(B)$ is its reachability matrix. $\Box$

We present some immediate consequences of the path weights in (1.5) and the definition of max-weighted paths.

If there is only one path between two nodes, it is max-weighted.

Every subpath of a max-weighted path is also max-weighted.

Every path, which results from a max-weighted path by replacing a subpath with another max-weighted subpath, is also max-weighted.

To find for some $i\in V$ and $j\in{\rm an}(i)$ the ML coefficient $b_{ji}$ it suffices to know the weight of $Z_{j}$ and the edge weights along one arbitrary max-weighted path from $j$ to $i$, since every max-weighted path from $j$ to $i$ has the same weight. This allows us to represent every component $X_{i}$ of $\mathbf{X}$ as component of a recursive ML model on a subgraph of $\mathcal{D}$. For this purpose, we introduce the following definition.

Let $\overline{D}=(\overline{V},\overline{E})$ be a subgraph of $\mathcal{D}$, and denote by $\overline{\rm pa}(i)$ the parents of node $i$ in $\overline{\mathcal{D}}$. Define

with the same weights and noise variables as for $X_{i}$ in representation (1.3). We call the resulting recursive ML model $\mathbf{Y}=(Y_{l},l\in\overline{V})$ recursive ML submodel of $\mathbf{X}$ induced by $\overline{\mathcal{D}}$. $\Box$

We summarize some immediate properties of $\mathbf{Y}$.

Let $i\in V$ with ancestors ${\rm an}(i)$ in $\mathcal{D}$. Denote by $\overline{B}=(\overline{b}_{ij})_{|\overline{V}|\times|\overline{V}|}$ the ML coefficient matrix of $\mathbf{Y}$.

Every path in $\overline{\mathcal{D}}$ has the same weight (1.5) as in $\mathcal{D}$.

A path of $\overline{\mathcal{D}}$, which is in $\mathcal{D}$ a max-weighted path, is also in $\overline{\mathcal{D}}$ max-weighted.

For $j\in{\rm an}(i)$, $\overline{\mathcal{D}}$ has one in $\mathcal{D}$ max-weighted path from $j$ to $i$ if and only if $\overline{b}_{ji}=b_{ji}$.

$\overline{\mathcal{D}}$ has at least one in $\mathcal{D}$ max-weighted path from every $j\in{\rm an}(i)$ to $i$ if and only if $X_{i}=Y_{i}$.

By Remark 3.4(ii), for every $i\in V$, there exists a polytree $\mathcal{D}_{i}$ of $\mathcal{D}$ with node set ${\rm An}(i)$, which has exactly one in $\mathcal{D}$ max-weighted path from every ancestor of $i$ to $i$. There may even exist several such polytrees (cf. Example 3.8 below). We learn from the construction of $\mathcal{D}_{i}$ and Remark 3.4(ii) that indeed every path of $\mathcal{D}_{i}$ is in $\mathcal{D}$ max-weighted. Therefore, some component $X_{j}$ of $\mathbf{X}$ coincides by Remark 3.6(iv) with the corresponding one of the recursive ML submodel of $\mathbf{X}$ induced by $\mathcal{D}_{i}$ if and only if $\mathcal{D}_{i}$ has at least one path from every ancestor of $j$ in $\mathcal{D}$ to $j$. By construction of $\mathcal{D}_{i}$ this property holds obviously for $X_{i}$. We summarize this result as follows.

Let $\mathbf{X}$ be a recursive ML model with DAG $\mathcal{D}$ and ML coefficient matrix $B$. For some $i\in V$ and ${\rm An}(i)$ in $\mathcal{D}$ let $\mathcal{D}_{i}$ be a polytree with node set ${\rm An}(i)$ such that $\mathcal{D}_{i}$ has one in $\mathcal{D}$ max-weighted path from every $j\in{\rm an}(i)$ to $i$. Let $\mathbf{Y}_{i}=(Y_{l},l\in{\rm An}(i))$ be the recursive ML submodel of $\mathbf{X}$ induced by $\mathcal{D}_{i}$. Then for all $j\in{\rm An}(i)$, which have the same ancestors in $\mathcal{D}_{i}$ and $\mathcal{D}$, we have $X_{j}=Y_{j}$.

We discuss the recursive ML model from Example 2.1 in the context of Definition 3.1 and Proposition 3.7.

[Continuation of Example 2.1: max-weighted paths, polytrees, conditional independence] We identify all max-weighted paths ending in node $4$. By Remark 3.4(i), the paths $[2\to 4]$ and $[3\to 4]$ are max-weighted. For the weights of the paths from node $1$ to $4$ we have three situations:

In the first situation, both paths from $1$ to $4$, $[1\to 2\to 4]$ and $[1\to 3\to 4]$, are max-weighted. Thus, there are two different polytrees having one in $\mathcal{D}$ max-weighted path from every ancestor of $4$ to $4$, namely,

In the second situation, the path $[1\to 2\to 4]$ is the unique max-weighted path from $1$ to $4$ and, hence, $\mathcal{D}_{4,1}$ is the unique polytree as in Proposition 3.7 for node 4. The third case is symmetric to the second, such that $\mathcal{D}_{4,2}$ is also such a unique polytree.

Now let $\mathbf{Y}_{1}=(Y_{1,1},Y_{1,2},Y_{1,3},Y_{1,4})$ and $\mathbf{Y}_{2}=(Y_{2,1},Y_{2,2},Y_{2,3},Y_{2,4})$ be the recursive ML submodels of $\mathbf{X}$ induced by $\mathcal{D}_{4,1}$ and $\mathcal{D}_{4,2}$. If the path $[1\to 2\to 4]$ is max-weighted, we have by Proposition 3.7 that

We know that the distributions of $\mathbf{X}$, $\mathbf{Y}_{1}$, and $\mathbf{Y}_{2}$ are Markov relative to $\mathcal{D}$, $\mathcal{D}_{4,1}$, and $\mathcal{D}_{4,2}$, respectively. For a DAG, the local Markov property as specified in (1.2), is by Proposition 4 of Lauritzen et al. equivalent to the global Markov property (for a definition see Corollary 3.23 of ). Using this property we find

Thus, if the path $[1\to 2\to 4]$ is in $\mathcal{D}$ max-weighted, we have by (3.1) that $X_{1}\upmodels X_{4}\mid X_{2}$. Accordingly, if $[1\to 3\to 4]$ is max-weighted, $X_{1}\upmodels X_{4}\mid X_{3}$ holds by (3.2). Since the only conditional independence property encoded in $\mathcal{D}$ by the (global) Markov property is $X_{1}\upmodels X_{4}\mid X_{2},X_{3}$, we can identify additional conditional independence properties of $\mathbf{X}$ from the polytrees in Proposition 3.7. $\Box$

(i) Assume the situation of Proposition 3.7. Let $V_{i}$ be the set of all nodes in ${\rm An}(i)$, which have the same ancestors in $\mathcal{D}$ and $\mathcal{D}_{i}$. Since the distributions of $\mathbf{X}$ and $\mathbf{Y}$ are Markov relative to $\mathcal{D}$ and $\mathcal{D}_{i}$, respectively, conditional independence properties of $\mathbf{X}$ are encoded in $\mathcal{D}$ and of $\mathbf{Y}$ in $\mathcal{D}_{i}$. By Proposition 3.7, the conditional independence properties between subvectors of $\mathbf{Y}_{V_{i}}=(Y_{l},l\in V_{i})$, which we can read off from $\mathcal{D}_{i}$, hold also between the corresponding subvectors of $\mathbf{X}$. Since missing edges correspond to conditional independence properties, and $\mathcal{D}_{i}$ is a subgraph of $\mathcal{D}$, we can often identify additional conditional independence properties of $\mathbf{X}$ from $\mathcal{D}_{i}$. (ii) From (i) or Example 3.8 we learn that a recursive ML model with DAG $\mathcal{D}$ is in general not faithful; i.e., not all conditional independence properties are encoded in $\mathcal{D}$ by the (global) Markov property. $\Box$

As can be seen from Example 3.8, any reduction of a recursive ML model depends on the existence of max-weighted paths that pass through some specific node. The following result shows how we can obtain this information from its ML coefficient matrix.

Let $B$ be the ML coefficient matrix of a recursive ML model on the DAG $\mathcal{D}$. Let further $U\subseteq V$, $i\in V$ and $j\in{\rm an}(i)$, and recall from Remark 2.3(i) that $b_{ji}>0$.

There is a max-weighted path from $j$ to $i$, which passes through some node in $U$ if and only if

No max-weighted path from $j$ to $i$ passes through some node in $U$ if and only if

First assume that ${\rm De}(j)\cap U\cap{\rm An}(i)=\emptyset$. Thus no path, hence also no max-weighted path, from $j$ to $i$ passes through some node in $U$, and it suffices to verify (b). Since the right-hand side of (3.4) is zero if and only if ${\rm De}(j)\cap U\cap{\rm An}(i)=\emptyset$, and the ML coefficient $b_{ji}$ is positive, (b) is proven for this case.

Now assume that ${\rm De}(j)\cap U\cap{\rm An}(i)=\{k\}$, which implies that there is a path from $j$ to $i$ passing through $k\in U$. If $k=i$ or $k=j$, there is obviously a max-weighted path from $j$ to $i$ passing through $i$ or $j$ and (3.3) is always valid.

Next assume that $k\in V\setminus\{i,j\}$ and that $p_{1}$ as well as $p_{2}$ are max-weighted paths from $j$ to $k$ and from $k$ to $i$. Denote by $p$ the path from $j$ to $i$ consisting of the subpaths $p_{1}$ and $p_{2}$. By (1.5) and the definition of a max-weighted path we obtain

Since $p$ is max-weighted if and only if $b_{ji}=d_{ji}(p)$, and this is not the case if and only if $b_{ji}>d_{ji}(p)$, we have shown (a) and (b) for the situation of ${\rm De}(j)\cap U\cap{\rm An}(i)=\{k\}$. In particular, it follows that $b_{ji}\geq\frac{b_{jk}b_{ki}}{b_{kk}}$ for all $k\in{\rm De}(j)\cap U\cap{\rm An}(i)$.

Assume now that ${\rm De}(j)\cap U\cap{\rm An}(i)$ contains more than one element, and that a max-weighted path from $j$ to $i$ passes through some node $k\in U$. We know from above that this is equivalent to

which is again equivalent to (3.3). Similarly, we obtain (b). ∎

Recall the matrix product $\odot$ from (2.2). We obtain from $R={\rm sgn}(B)$ (Remark 2.3(i)) that for $i,j\in V$

is the $ji$-th entry of the matrix $B\odot B_{U}$ with $B_{U}=(b_{U,ij})_{d\times d}$. Thus, we may decide whether there is a max-weighted path between two nodes that passes through some node in $U$ by comparing the entries of the matrices $B$ and $B\odot B_{U}$. Such use of the matrix product $\odot$ can be made at various points throughout the paper, for instance in Remark 5.2(i), Theorem 5.3, and Lemma 6.3(b). $\Box$

From Theorem 3.10, recalling from Remark 2.3(a) that $R={\rm sgn}(B)$, we obtain an important property of the ML coefficients.

For all $i\in V$, $k\in{\rm An}(i)$, and $j\in{\rm An}(k)$, $b_{ji}\geq\frac{b_{jk}b_{ki}}{b_{kk}}>0$. Indeed, $b_{ji}\geq\frac{b_{jk}b_{ki}}{b_{kk}}$ holds for all $i,j,k\in V$.

We learn immediately from (1.3) that $c_{ki}X_{k}\leq X_{i}$ for all $i\in V$ and $k\in{{\rm pa}}(i)$. From Corollary 3.12 we find such inequalities also for components, whose nodes are not connected by an edge but by a path of arbitrary length.

For all $i\in V$ and $j\in{\rm An}(i)$, we have $\frac{b_{ji}}{b_{jj}}X_{j}\leq X_{i}$.

Note that ${\rm An}(j)\subseteq{\rm An}(i)$. Using the max-linear representation (2.1) of $X_{i}$ and $X_{j}$ as well as Corollary 3.12, we obtain

ML coefficients leading to a recursive ML model on a given DAG

Recall the definition of a (general) ML model given in (1.4). From Theorem 2.2 we know that every recursive ML model is max-linear. In this section we provide necessary and sufficient conditions on a ML model to be a recursive ML model on a given DAG $\mathcal{D}$.

It can be shown that every ML model, which is a recursive SEM as given in (1.1) with unspecified functions $f_{1},\dots,f_{d}$, must be a recursive ML model. That a recursive ML model on $\mathcal{D}$ is also a recursive SEM follows immediately from its recursive definition. To summarize, a ML model can be represented as a recursive SEM (1.1) with DAG $\mathcal{D}$ if and only if it has a recursive ML representation (1.3) relative to the same DAG $\mathcal{D}$.

We investigate below, when a ML coefficient matrix $B$ as in (1.4) is the ML coefficient matrix of a recursive ML model with given DAG $\mathcal{D}$. Motivated by Remark 2.3(i) in what follows we assume that ${\rm sgn}(B)$ is the reachability matrix $R$ of $\mathcal{D}$. In our investigation the DAG with the minimum number of edges, such that $R={\rm sgn}(B)$, will play an important role. This has already been indicated in Example 3.3.

We give a general definition of the DAG with minimum number of edges that represents the same reachability relation as a given DAG.

Let $\mathcal{D}=(V,E)$ be a DAG. The DAG $\mathcal{D}^{{\rm tr}}=(V,E^{{\rm tr}})$ is the transitive reduction of $\mathcal{D}$ if the following holds:

$\mathcal{D}^{{\rm tr}}$ has a path from node $j$ to node $i$ if and only if $\mathcal{D}$ has a path from $j$ to $i$, and

there is no graph with less edges than $\mathcal{D}^{{\rm tr}}$ satisfying condition (a).

Since we work with finite DAGs throughout, the transitive reduction is unique and is also a subgraph of the original DAG. The transitive reduction of a DAG can be obtained by successively examining its edges, in any order, and deleting an edge $k\to i$, if the original DAG contains a path from $k$ to $i$ which does not include this edge. For these properties and further details see e.g. Aho et al. . In what follows we need the notion of ${{{\rm pa}}}^{{\rm tr}}(i)$, the parents of $i$ in $\mathcal{D}^{\rm tr}$.

We present necessary and sufficient conditions on $B$ to be the ML coefficient matrix of a recursive ML model on $\mathcal{D}$.

Let $\mathcal{D}$ be a DAG with reachability matrix $R$ and $\mathbf{X}$ a ML model as in (1.4) with ML coefficient matrix $B$ such that ${{\rm sgn}}(B)=R$. Define

Then $\mathbf{X}$ is a recursive ML model on $\mathcal{D}$ if and only if the following fixed point equation holds:

First we investigate the fixed point equation (4.1) and compute the $ji$-th entry of $B\odot A_{0}$. By definition, together with ${{\rm sgn}}(B)=R$, it is equal to

We have ${{\rm De}}(j)\cap{{{\rm pa}}}(i)=\emptyset$ for $j\in V\setminus{\rm an}(i)$ and ${{\rm De}}(j)\cap{{{\rm pa}}}(i)={{\rm de}}(j)\cap{{{\rm pa}}}(i)$ for $j\in{\rm an}(i)\setminus{\rm pa}(i)$. Moreover, for $j\in{{{\rm pa}}}^{{\rm tr}}(i)$, using that ${{\rm de}}(j)\cap{{{\rm pa}}}(i)=\emptyset$, we obtain ${{\rm De}}(j)\cap{{{\rm pa}}}(i)=\{i\}$. Thus, taking also the matrix $A$ into account, (4.1) is equivalent to

for all $i,j\in V$. To summarize, the fixed point equation (4.1) is satisfied if and only if for all $i\in V$ the following identities hold:

Thus it suffices to show that, under the conditions above, $\mathbf{X}$ is a recursive ML model on $\mathcal{D}$ if and only if (4.2) and (4.3) hold for all $i\in V$.

First assume that $\mathbf{X}$ is a recursive ML model on $\mathcal{D}$, and let $i\in V$ and $j\in{\rm an}(i)$. Since every path from $j$ to $i$ passes through at least one parent node of $i$, there must be a max-weighted path from $j$ to $i$ passing through some node in ${\rm pa}(i)$. Using (3.3) with $U={\rm pa}(i)$ and noting that $j\in{\rm De}(j)\cap U\cap{\rm An}(i)={\rm De}(j)\cap{\rm pa}(i)$, we find for $j\in{\rm an}(i)\setminus{\rm pa}(i)$ Eq. (4.2) and for $j\in{\rm pa}(i)\setminus{\rm pa}^{\rm tr}(i)$ Eq. (4.3).

For the converse statement, assume that (4.2) and (4.3) hold. For $j\in{\rm pa}^{\rm tr}(i)$ we have ${\rm de}(j)\cap{\rm pa}(i)=\emptyset$, such that the right-hand side of (4.3) is equal to $b_{ji}$. Thus (4.3) holds for all $j\in{\rm pa}(i)$. Since ${\rm sgn}(B)=R$, we have $X_{i}=\bigvee_{j=1}^{d}b_{ji}Z_{j}=\bigvee_{j\in{\rm An}(i)}b_{ji}Z_{j}$. We split up the index set and use (4.2) in the first place and (4.3) for all $j\in{\rm pa}(i)$ in the second place to obtain

Interchanging the first two maximum operators by (A.1) yields

In the proof of Theorem 4.2 we have shown that under the required conditions the fixed point equation (4.1) holds if and only if (4.2) and (4.3) hold. We summarize this in part (a) of the following corollary. Part (b) has also been verified in the proof of Theorem 4.2. The final statement is based on the fact that for $k\in{\rm pa}(i)$ we have ${\rm de}(k)\cap{\rm pa}(i)=\emptyset$ if and only if $k\in{\rm pa}^{\rm tr}(i)$.

(a) Assume the situation of Theorem 4.2. Then $\mathbf{X}$ is a recursive ML model on $\mathcal{D}$ if and only if for every $i\in V$,

(b) Let $\mathbf{X}$ be a recursive ML model with DAG $\mathcal{D}$ and ML coefficient matrix $B$. Then for every $i\in V$ and $k\in{\rm pa}(i)$,

Moreover, the right-hand side is equal to 0 if and only if $k\in{\rm pa}^{\rm tr}(i)$.

By (4.4) and (4.5) exactly those ML coefficients $b_{ki}$, such that $k\to i$ is an edge in $\mathcal{D}^{\rm tr}$, do not have to meet any specific conditions apart from being positive.

In summary, given a DAG $\mathcal{D}$ with node set $V=\{1,\ldots,d\}$, both Theorem 4.2 and Corollary 4.3(a) characterize all ML coefficient matrices of any recursive ML model possible on $\mathcal{D}$ as all non-negative $d\times d$ matrices that are weighted reachability matrices of $\mathcal{D}$ and satisfy (4.1), equivalently (4.4) or (4.5). If we can verify these two properties for a non-negative $d\times d$ matrix $B$, then it is the ML coefficient matrix of a recursive ML model on $\mathcal{D}$, and for $i\in V$ weights in its representation (1.3) are given by $c_{ki}=\frac{b_{ki}}{b_{kk}}$ for $k\in{\rm pa}(i)$ and $c_{ii}=b_{ii}$.

Graph reduction for a recursive max-linear model

From Proposition 3.7 we know that every component $X_{i}$ of a recursive ML model $\mathbf{X}$ with DAG $\mathcal{D}=(V,E)$ satisfies (1.3) on a subgraph of $\mathcal{D}$. These subgraphs, however, usually vary from one vector component to another. On the other hand, we know from Example 3.3 that the whole vector $\mathbf{X}$ may also be a recursive ML model on a subgraph of $\mathcal{D}$. This raises the question of finding the smallest subgraph of $\mathcal{D}$ such that $\mathbf{X}$ is a recursive ML model on this DAG. We define and characterize this unique minimal DAG before we point out its prominent role in the class of all DAGs representing $\mathbf{X}$ in the sense of (1.3).

Let $\mathbf{X}$ be a recursive ML model with DAG $\mathcal{D}=(V,E)$ and ML coefficient matrix $B$. We call the DAG

the minimum max-linear (ML) DAG of $\mathbf{X}$. $\Box$

We summarize some properties of $\mathcal{D}^{B}$ as follows.

(i) By Theorem 3.10(b) the minimum ML DAG $\mathcal{D}^{B}$ contains exactly those edges $k\to i$ of $\mathcal{D}$, where no max-weighted path from $k$ to $i$ passes through some node in ${\rm pa}(i)\setminus\{k\}$. This means that $\mathcal{D}^{B}$ has an edge $k\to i$ if and only if it is the only max-weighted path from $k$ to $i$ in $\mathcal{D}$. The DAG $\mathcal{D}^{B}$ can be obtained from $\mathcal{D}$ by deleting an edge $k\to i$, if $\mathcal{D}$ contains a max-weighted path from $k$ to $i$, which does not include this edge. The algorithm is by comparison of the ML coefficients: for all $i\in V$ and $k\in{\rm pa}(i)\setminus{\rm pa}^{{\rm tr}}(i)$ remove the edge $k\to i$ from $\mathcal{D}$ if

Note the analogy to finding the transitive reduction $\mathcal{D}^{{\rm tr}}$ of $\mathcal{D}$ below Definition 4.1. (ii) The minimum ML DAG $\mathcal{D}^{B}=(V,E^{B})$ is a subgraph of the original DAG $\mathcal{D}=(V,E)$. Recall that the transitive reduction $\mathcal{D}^{\rm tr}=(V,E^{\rm tr})$ of $\mathcal{D}$ is also a subgraph of $\mathcal{D}$ and that every edge $k\to i$ in $\mathcal{D}^{\rm tr}$ is the only – and hence also max-weighted – path from $k$ to $i$ in $\mathcal{D}$. Thus, the transitive reduction $\mathcal{D}^{\rm tr}$ is also a subgraph of $\mathcal{D}^{B}$. In summary, we have $E^{\rm tr}\subseteq E^{B}\subseteq E$. This implies that the DAGs $\mathcal{D}^{B}$ and $\mathcal{D}$ have the same reachability matrix ${\rm sgn}(B)$. $\Box$

The method described in Remark 5.2(i) determines $\mathcal{D}^{B}$ from $\mathcal{D}$ and $B$. Indeed, we can also identify $\mathcal{D}^{B}$ directly from $B$ without knowing $\mathcal{D}$.

Let $\mathbf{X}$ be a recursive ML model with ML coefficient matrix $B$. Then the minimum ML DAG of $\mathbf{X}$ can be represented as

in particular, $\mathcal{D}^{B}$ is identifiable from $B$.

Let $\mathcal{D}$ be a DAG, which describes $\mathbf{X}$ in the sense of (1.3). Since $R={\rm sgn}(B)$ (Remark 2.3(i)) we have

We show that the edge set in (5.2) coincides with $E^{B}$ as defined in (5.1). Assume first that $(k,i)$ is contained in the edge set in (5.2). Such a DAG exist by the definition of a recursive ML model. Since the right-hand side of (5.3) is non-negative, we must have $b_{ki}>0$ and, hence, $k\in{\rm an}(i)$. By Theorem 3.10(b) no max-weighted path from $k$ to $i$ passes through some node in $V\setminus\{i,k\}$. Thus the edge $k\to i$ must be the only max-weighted path from $k$ to $i$ and, hence, by Remark 5.2(i) it must be an edge $E^{B}$ as in (5.1).

For the converse, let $(k,i)\in E^{B}$. Since by Remark 5.2(i) this edge is the only max-weighted path from $k$ to $i$, there is no max-weighted path passing through some node in $V\setminus\{i,k\}$. This is by Theorem 3.10(b) equivalent to (5.3) and $(k,i)$ belongs to the edge set in (5.2). ∎

We characterize all DAGs and specify all weights such that $\mathbf{X}$ satisfies (1.3). The minimum ML DAG $\mathcal{D}^{B}$ of $\mathbf{X}$ is the smallest DAG of this kind and has unique weights in representation (1.3) in the sense that all irrelevant weights are set to zero. We can add edges into $\mathcal{D}^{B}$ with weights $c_{ki}\in(0,\frac{b_{ki}}{b_{kk}}]$ representing $\mathbf{X}$ again in the sense of (1.3) as long as the graph represents the same reachability relation as $\mathcal{D}^{B}$. As a consequence, to find $B$ by a path analysis as described in (1.6) it suffices to know $\mathcal{D}^{B}$ and the weights in representation (1.3) relative to $\mathcal{D}^{B}$.

Let $\mathbf{X}$ be a recursive ML model with ML coefficient matrix $B$. Let further $\mathcal{D}^{B}=(V,E^{B})$ be the minimum ML DAG of $\mathbf{X}$ and ${\rm pa}^{B}(i)$ be the parents of node $i$ in $\mathcal{D}^{B}$.

The minimum ML DAG $\mathcal{D}^{B}$ of $\mathbf{X}$ is the DAG with the minimum number of edges such that $\mathbf{X}$ satisfies (1.3). The weights in (1.3) are uniquely given by $c_{ii}=b_{ii}$ and $c_{ki}=\frac{b_{ki}}{b_{kk}}$ for $i\in V$ and $k\in{\rm pa}^{B}(i)$.

Every DAG with node set $V$ that has at least the edges of $\mathcal{D}^{B}$ and the same reachability matrix as $\mathcal{D}^{B}$ represents $\mathbf{X}$ in the sense of (1.3) with weights given for all $i\in V$ by

There are no further DAGs and weights such that $\mathbf{X}$ has representation (1.3).

(a) Let $\mathcal{D}$ be a DAG and $c_{ki}$ for $i\in V$ and $k\in{\rm Pa}(i)$ weights such that $\mathbf{X}$ has representation (1.3). By Remark 5.2(ii) $\mathcal{D}^{B}$ is a subgraph of $\mathcal{D}$.

First we prove that $\mathbf{X}$ is a recursive ML model on $\mathcal{D}^{B}$ with weights $c_{ki}$ for $i\in V$ and $k\in{\rm Pa}^{B}(i)$ by showing that all components of $\mathbf{X}$ coincide with those of the recursive ML submodel of $\mathbf{X}$ induced by $\mathcal{D}^{B}$ (see Definition 3.5). By Remark 3.6(iv), it suffices to verify for all $i\in V$ and $j\in{\rm an}(i)$ that $\mathcal{D}^{B}$ has one in $\mathcal{D}$ max-weighted path from $j$ to $i$. Among all max-weighted paths from $j$ to $i$ in $\mathcal{D}$, let $p$ be one with maximal length, and assume that $p$ includes an edge, say $k\to l$, which is not contained in $\mathcal{D}^{B}$. The DAG $\mathcal{D}$ has by Remark 5.2(i), however, a max-weighted path $p_{1}$ from $k$ to $l$, which does not include the edge $k\to l$. Note that $p_{1}$ consists of more edges than the path $[k\to l]$. Thus by replacing in $p$ the edge $k\to l$ by $p_{1}$ we obtain by Remark 3.4(iii) a max-weighted path from $j$ to $i$ consisting of more edges than $p$. Since this a contradiction to the fact that $p$ has maximal length among all max-weighted paths from $j$ to $i$, $p$ must be in $\mathcal{D}^{B}$.