---
title: "Introduction to Extremal Graphical Models"
output:
    bookdown::html_document2:
        fig_width: 5
        fig_height: 5
        number_sections: true
        toc: true
        toc_depth: 1
bibliography: ../inst/REFERENCES.bib
vignette: >
    %\VignetteIndexEntry{Introduction to Extremal Graphical Models}
    %\VignetteEngine{knitr::rmarkdown}
    %\VignetteEncoding{UTF-8}
---

<!-- Rmarkdown requries 4 spaces of indentation -->

\DeclareMathOperator{\Var}{Var}
\newcommand{\g}[1]{\mathbf{#1}}
\DeclareMathOperator{\MST}{mst}
\DeclareMathOperator{\argmin}{arg\,min}
\DeclareMathOperator{\argmax}{arg\,max}

```{r, include = FALSE}
knitr::opts_chunk$set(
    collapse = TRUE,
    comment = '#>',
    error = TRUE
)
```

```{r setup, include=FALSE}
library(graphicalExtremes)
library(dplyr)
library(ggplot2)
theme_set(theme_bw() +
    theme(
        plot.background = element_blank(),
        legend.background = element_blank(),
        strip.background = element_rect(fill = "white"),
        plot.caption = element_text(
            size = 7.5, hjust = 0,
            margin = margin(t = 15)
        ),
        text = element_text(size = 11),
        axis.ticks = element_blank(),
        panel.grid.major = element_line(size = 0.25)
    )
)
```

# Danube Data

```{r, fig.show='hold', out.width="50%"}
danube <- graphicalExtremes::danube

X <- danube$data_clustered

ggplot(X %>% as_tibble()) +
    geom_point(aes(x = X1, y = X2))
ggplot(X %>% as_tibble()) +
    geom_point(aes(x = X22, y = X28))
```

```{r, fig.align='center'}
danube_flow <- igraph::graph_from_edgelist(danube$flow_edges)
danube_plot_coords <- as.matrix(danube$info[, c("PlotCoordX", "PlotCoordY")])
plot(danube_flow, layout = danube_plot_coords, edge.arrow.size = .3)
```



# Multivariate Pareto distributions

## Definition

The goal is to study the extremal tail of a multivariate random vector $\g{X} = (X_1,\dots, X_d)$. Here, we are interested only in the extremal dependence and therefore normlaize the marginal distributions $F_j$ of $X_j$ to standard Pareto distributions by
\begin{equation}
1 /\{1- F_j(X_j)\}, \quad j=1,\dots, d. (\#eq:pareto)
\end{equation}
We assume in the sequel that the vector $X$ has been normalized to standard Pareto margins.

A multivariate Pareto distribution (MPD) is defined as the limiting distribution the exceedances of $\g{X}$ over a high threshold, where the multivariate threshold is chosen in terms of the $l_\infty$-norm. For any $u>0$, we define exceedance distribution as
\begin{equation}
\g{X}_u = \g{X} \mid \| \g{X} \|_\infty > u  (\#eq:exc)
\end{equation}
By sending $u\to \infty$ and normalizing properly, the random vector $\g X_u$ converges to a limiting distribution $\g Y$ called the MPD:
$$ \g{Y} = \lim_{u\to \infty} \g{X}_u /u,$$
where the limit is in terms of convergence in distribution. By construction, the distribution of the MPD $\g Y$ is defined on the space $\mathcal L = \{\g x \in [0,\infty)^d : \| \g x \|_\infty > 1\}$, and if $\g Y$ possesses a density $f_{\g Y}$, then it is proportional to the so-called exponent measure density $\lambda$; for details see @eng2019.

In practice, we use the approximation $\g Y \approx \g X_u$ for some large value $u$, where $u$ can be chosen as the $p$th quantile of the distribution of $\|\g{X}\|_\infty$.
Given $n$ oberservations $\g X_1, \dots, \g X_n$ of $\g X$, the function `data2mpareto()` first computes the standardization in \@ref(eq:pareto) based on the empirical distribution functions $\hat F_j$ and then selects the exceedances $\g X_u$ according to \@ref(eq:exc). 


```{r, fig.align='center'}
Y <- data2mpareto(data = X, p = .8)
```


## Examples

::: {.example}
The extremal logistic distribution with parameter $\theta\in(0,1)$ induces a multivariate
Pareto distribution with density
\begin{equation}
f_{\g Y}(\g y) = \frac{1}{d^{\theta}} \left(y_1^{-1/\theta}+\dots+y_d^{-1/\theta}\right)^{\theta-d}\prod_{i=1}^{d-1}\left(\frac{i}{\theta}-1\right) \prod_{i=1}^{d} y_i^{-1/\theta-1}, \quad \g y \in \mathcal L.
\end{equation}
The parameter $\theta$ governs the extremal dependence, ranging from complete dependence for $\theta\to 0$ and independence for $\theta \to 1$. 
:::




::: {.example}
The $d$-dimensional H&uuml;sler--Reiss distribution [@hue1989] is parameterized by the variogram matrix $\Gamma = \{\Gamma_{ij}\}_{1\leq i,j\leq d}$. The corresponding density of the exponent measure can be written for any $k\in\{1,\dots, d\}$ as \citep[cf.,][]{Engelke2015}
\begin{equation}
    \lambda(\g y) = y_k^{-2}\prod_{i\neq k} y_i^{-1} \phi_{d-1}\left(\g{\tilde y}_{\setminus k}; \Sigma^{(k)}\right), \quad \g y \in \mathcal L,  (\#eq:fYHR)
\end{equation}
where $\phi_p(\cdot; \Sigma)$ is the density of a centred $p$-dimensional normal distribution with covariance matrix $\Sigma$, $\g{\tilde y} = \{\log(y_i/y_k) + \Gamma_{ik}/2\}_{i=1,\dots, d}$ and 
\begin{equation}\label{sigma_k}
    \Sigma^{(k)}  =\frac{1}{2} \{\Gamma_{ik}+\Gamma_{jk}-\Gamma_{ij}\}_{i,j\neq k} \in\mathbb R^{(d-1)\times (d-1)}. (\#eq:Sigmak)
\end{equation}
The matrix $\Sigma^{(k)}$ is positive definite and will play an important role in the theory of extremal graphical models. The representation of the density in \@ref(eq:fYHR) seems to depend on the choice of $k$, but, in fact, the value of the right-hand side of this equation is independent of $k$. 
The H&uuml;sler--Reiss multivariate Pareto distribution has density 
$f_{\g Y}(\g y) \propto \lambda(\g y)$ and the
strength of dependence between the $i$th and $j$th component is parameterized by $\Gamma_{ij}$, ranging from complete dependence for $\Gamma_{ij} \to 0$ and independence for $\Gamma_{ij} \to \infty$. 

The extension of H&uuml;sler--Reiss distributions to random fields are
Brown--Resnick processes [@kab2009], which are widely used models for spatial
extremes.   
:::

The function `rmpareto()` generates samples from a MPD $\g Y$ based on the exact algorithm described in @eng2019.


```{r, fig.align='center'}
G <- cbind(c(0, 1.5), c(1.5, 0))
Ysim <- rmpareto(n = 100, model = "HR", d = 2, par = G)

theta <- .5
Ysim <- rmpareto(n = 100, model = "logistic", d = 2, par = theta)
```

Note that we can also generate samples from the corresponding max-stable distribution with the function `rmstable()`, following the exact algorithm in @dom2016.


## Measures of extremal dependence

### Extremal correlation

The extremal correlation $\chi_{ij}\in [0,1]$ measures the dependence between the largest values of the random variables $X_i$ and $X_j$. It is defined as
\begin{equation}\label{EC}
    \chi_{ij} = \lim_{p\to 1} \chi_{ij}(p) = \lim_{p\to 1} \mathbb P\left\{F_i(X_i) > p\mid  F_j(X_j) > p \right\},
\end{equation}
where the boundary cases $0$ and $1$ correspond to asymptotic independence and complete dependence, respectively. 

For $n$ observations $X_1,\dots, X_n$ of the $d$-dimensional vector $X$, we can empirically estimate the $d\times d$ matrix of all pairwise extremal correlations for a fixed threshold $p$ close to 1. 

```{r}
chi_hat <- emp_chi(data = X, p = .8)
```

In this function, and in all subsequent functions, if the variable `p = NULL` then the data is already expected to be on MPD scale, and no thresholding is performed. For the `danube()` data, we may therefore directly use $\g Y$ instead of $\g X$:

```{r}
chi_hat <- emp_chi(data = Y)
```


::: {.example}
For the H&uuml;sler--Reiss distribution with parameter matrix $\Gamma = \{\Gamma_{ij}\}_{1\leq i,j\leq d}$, the extremal correlation is given by
$$ \chi_{ij} =  2 - 2 \Phi(\sqrt{\Gamma_{ij}}/2),$$
    where $\Phi$ is the standard normal distribution function. We can use the functions `Gamma2chi()` and `chi2Gamma()` to switch between the two coefficients.
:::


### Extremal variogram

There exist several other summary statistics for extremal dependence. The extremal variogram was introduced in \cite{engvolg} and turns out to be particularly useful for inference of extremal graphical models discussed below. 

For any root node $k\in V$, the pre-asymptotic extremal variogram is defined as the matrix $\Gamma^{(k)}$ with entries
\begin{equation*}
    \Gamma_{ij}^{(k)}(p) = \Var \left[\log\{1 -  F_i(X_{i})\}- \log\{1 - F_j(X_j)\} \mid F_k(X_k) > p\right], \quad i,j\in V,
    \end{equation*}  
whenever right-hand side exists. Note that $-\log\{1 -  F_i(X_{i})\}$ transforms $X_i$ to a standard exponential distribution, such that $\Gamma^{(k)}$ is simply the variogram matrix of $\g X$ on exponential scale, condtioned on the $k$th variable being large. 

The limit as $p\to 1$ is called the extremal variogram and can be expressed in terms of the MPD $\g Y$:
\begin{equation*}
 \Gamma_{ij}^{(k)} = \lim_{p\to 1} \Gamma_{ij}^{(k)}(p) = \Var \left\{ \log Y^k_{i} - \log Y^k_j \mid Y_k > 1 \right\}, \quad i,j\in V.
\end{equation*}  
Weak/strong extremal dependence is indicated by large/small values of the extremal variogram, respectively. The function `emp_vario()` estimates the (pre-asymptotic) extremal variogram, for instance for $k=1$.

```{r}
Gamma_1_hat <- emp_vario(data = X, k = 1, p = 0.8)
```

In general, the matrices $\Gamma^{(k)}$ can be different for $k \in V$, but for example for the H&uuml;sler--Reiss distribution, they all coincide.


::: {.example}
For the H&uuml;sler--Reiss distribution with parameter matrix $\Gamma$, the extremal variogram matrices satisfy
$$ \Gamma = \Gamma^{(1)} = \dots = \Gamma^{(d)}.$$
:::

In this case it makes sense to estimate the extremal variogram $\hat \Gamma$ as the average of the estimators $\hat \Gamma^{(k)}$:
```{r}
Gamma_hat <- emp_vario(data = X, p = 0.8)
Gamma_hat <- emp_vario(data = Y)
```




# Extremal graphical models

Let $G=(V,E)$ be an undirected graph with index set $V = \{1,\dots, d\}$ and edges $E \subset V \times V$. The figure below shows examples of different graphical structure: a tree, a decomposable graph and a non-decomposable graph. @eng2019 introduce a new notion of extremal conditional independence for MTPs, denoted by $\perp_e$. They define an extremal graphical model on $G$ as a MPD $Y = (Y_j : j\in V)$ that satisfies the pairwise Markov property
$$   Y_i \perp_e Y_j \mid  Y_{\setminus \{i,j\}}, \quad  (i,j)\notin E.$$
that is, $Y_i$ and $Y_j$ are conditionally independent in the extremal sense $\perp_e$ given all other nodes whenever there is no edge between $i$ and $j$ in $G$.

If the MPD possesses a density $f_{\g Y}$, then the graph $G$ has to be connected. @eng2019 then show a Hammersley--Clifford theorem stating that for an extr emal graphical model on a decomposable graph $G$, the density $f_{\g Y}$ factorizes into the marginal density on the cliques.

```{r, echo = FALSE, fig.align='center', out.width="50%"}
# All defaults
knitr::include_graphics("images/graphs.png")
```


## Trees

A tree $T = (V,E)$ is a particularly simple type of graph, which is connected and does not have cycles. This implies that there are exactly $|E| = d-1$ edges. The Hammersley--Clifford theorem shown in @eng2019 yields that the density of an extremal tree model $\g Y$ on the tree $T= (V,E)$ factorizes into 
\begin{equation}
    f_{\g Y}(\g y) \propto  \prod_{\{i,j\}\in E} {\lambda_{ij}(y_i,y_j) \over y_i^{-2} y_j^{-2}} \prod_{i\in V} y_i^{-2},  (\#eq:treedens)
\end{equation}
where $\lambda_{ij}$ are the bivariate marginals of the exponent measure density $\lambda$ corresponding to $\g Y$. The $d$-dimensional density of the MPD is therefore reduced to bivariate interactions only. 

For extremal graphical models on trees, the extremal variograms $\Gamma^{(k)}$, $k \in V$, are very natural since they define a so-called additive tree metric, that is,  
\begin{equation}
\Gamma_{ij}^{(k)} = \sum_{(s,t) \in \text{ph}(ij)} \Gamma^{(k)}_{st}, (\#eq:treemetric)
\end{equation}
where $\text{ph}(ij)$ denotes the path between node $i$ and $j$ on the tree $T$. 


### Simulation

By representation \@ref(eq:treedens) we can specify any models bivariate $\lambda_{ij}$ for $(i,j) \in E$ and combine them to a valid tree model. For instance, if we use bivariate H&uuml;sler--Reiss distributions on all edges of the tree $T$, the resulting $d$-dimensional tree model is again H&uuml;sler--Reiss and its parameter matrix $\Gamma$ is implied by \@ref(eq:treemetric). If we use bivariate logistic distributions on all edges, the results extremal tree model is not a $d$-dimensional logistic model, but a more flexible model with $d-1$ parameters.

The function `rmpareto_tree()` generates samples from an extremal tree model $\g Y$.

```{r}
set.seed(42)

my_model <- generate_random_model(d = 4, graph_type = "tree")
Ysim <- rmpareto_tree(
    n = 100, model = "HR",
    tree = my_model$graph,
    par = my_model$Gamma
)

theta_vec <- c(.2, .8, .3)
Ysim <- rmpareto_tree(
    n = 100, model = "logistic",
    tree = my_model$graph,
    par = theta_vec
)
```

Note that we can also generate samples from the corresponding max-stable distribution with the function `rmstable_tree()`.

### Estimation

For a given tree $T= (V,E)$ and a parametric model $\{f_{\g Y}(\g y; \theta): \theta \in \Theta\}$ of MPDs on the tree $T$, estimation of the model parameters is fairly straight-forward. If $\theta = \{ \theta_{ij}: (i,j) \in E\}$ consists of one parameter per edge, then thanks to the factorization \@ref(eq:treedens) we may fit each parameter $\theta_{ij}$ separately. This can be done by (censored) maximum likelihood methods, or by other methods such as M-estimation. This can be done by (censored) maximum likelihood methods, or by other methods such as M-estimation. 

If provided with a tree and data, the function `fmpareto_graph_HR()` estimates the $d-1$ parametres of a H&uuml;sler--Reiss model on that tree. As an example, we fit an extremal tree model to the (undirected) tree resulting from the flow connections in the `danube()` data set and compare the the fitted with the empirical extremal coefficients.

```{r, fig.align='center'}
danube_tree <- igraph::as.undirected(danube_flow)
danube_flow_fit <- fmpareto_graph_HR(data = X, graph = danube_tree, p = .8)
```



### Structure learning

In practice, the underlying conditonal independence tree $T = (V,E)$ is usually unknown and has to be estimated in a data-driven way. For extremal tree models, it turns out that this can be done efficiently in a completely non-parametric way; see @eng2020 for details.

The method is based on the notion of a minimum spanning tree. For a set of symmetric weights $\rho_{ij} > 0$ associated with any pair of nodes $i,j\in V$, $i\neq j$, the latter is defined as the tree structure
\begin{align}\label{Tmin}
    T_{\MST} = \argmin_{T' = (V,E)} \sum_{(i,j)\in E} \rho_{ij},
\end{align}
that minimizes the sum of distances on that tree.

@eng2020 showed that if $\g Y$ is an extremal graphical model on an unkown tree $T$, then the minimum spanning tree with the extremal variogram $\rho_{ij} = \Gamma_{ij}^{(k)}$ as weights is unique and satisfies $T_{\MST} = T$. Using empircal estimates $\hat \Gamma_{ij}^{(k)}$ as weights, we can thus consistently recover the underlying tree structure in a fully non-parametric way.

In fact, taking the average of all $\hat \Gamma^{(k)}$, $k \in V$, and using this as weights $\rho_{ij} = \hat \Gamma_{ij}$ makes better use of the data and usually improves the performance of structure estimation significantly. @eng2020 further show that the empircal extremal correlation $\rho_{ij} = \hat \chi_{ij}$ may also be used for consistent tree recovery, but the performance is typically inferior to extremal variogram based algorithms.


The function `emst()` estimates the extremal tree structure by a minimum spanning tree algorithm based on the different summary statistics for extremal dependence. It provides the estimated tree and the implied extremal variogram matrix through \@ref(eq:treemetric).


```{r, fig.align='center'}
danube_emst_fit <- emst(data = X, p = .8, method = "vario")
plot(danube_emst_fit$graph, layout = danube_plot_coords)
```

```{r, fig.align='center'}
ggplot() +
    geom_point(aes(x = c(Gamma2chi(danube_flow_fit)), y = c(chi_hat))) +
    geom_abline(slope = 1, intercept = 0) +
    xlab("Fitted") +
    ylab("Empirical") +
    coord_cartesian(xlim = c(0.4, 1), ylim = c(0.4, 1))
```


## H&uuml;sler--Reiss graphical models

The H&uuml;sler--Reiss Pareto distribution $\g Y$
is parametrized by the variogram matrix $\Gamma$. Using the linear transformation \@ref(eq:Sigmak), we obtain the covariance matrix $\Sigma^{(k)}$ for $k\in V$. The inverse, called a precision matrix, is denoted by $\Theta^{(k)}$. @eng2019 showed that for any $k\in V$ this precision matrix contains the conditional independence structure of $\g Y$, since for $i,j\in V$ with $i\neq j$,
    \begin{equation*}
        Y_i\perp_e Y_j\mid \g Y_{V\setminus \{i,j\}} \quad \iff \quad
        \begin{cases}
             \Theta^{(k)}_{ij}= 0,  &\text{ if } i,j \neq k,\\
             \sum_{l\neq k} \Theta^{(k)}_{jl} = 0, & \text{ if } i = k,j \neq k.
        \end{cases} 
    \end{equation*}
This means, if $Y$ is an extremal graphical on the graph $G = (V,E)$, the missing edges can be read off from the matrix $\Theta^{(k)}$ as zeros on the off-diagonal and zero row sums. 

Note that the matrices $\Theta^{(k)}$ are $(d-1)\times(d-1)$ dimensional. To combine all these precision matrices for $k\in V$, we may in fact a positive semi-definite precision matrix $\Theta \in \mathbb R^{d\times d}$ as
\begin{equation*}
 \Theta_{ij} = \Theta^{(k)}_{ij} \text{ for some } k \neq i,j,
\end{equation*}
which contains all extremal conditional independencies as zeros on the off-diagonal:
    \begin{equation*}
        Y_i\perp_e Y_j\mid \g Y_{V\setminus \{i,j\}} \quad \iff \quad
             \Theta_{ij}= 0,  \quad i,j \in V.
\end{equation*}


### Transformations

While the H&uuml;sler--Reiss distribution is parameterized by the variogram matrix $\Gamma$, other objects such as $\Sigma^{(k)}$, $\Theta^{(k)}$ and $\Theta$ are often required, for instance, to identify the extremal graphical structure. The functions `Gamma2Sigma()`, `Sigma2Gamma()`, `Gamma2Theta()` and `Theta2Gamma()` are often useful. Note that all of these function are bijections. The function `Gamma2graph()` creates an `igraph::graph()` object and plots it.

```{r, eval=FALSE}
Gamma <- cbind(
    c(0, 1.5, 1.5, 2),
    c(1.5, 0, 2, 1.5),
    c(1.5, 2, 0, 1.5),
    c(2, 1.5, 1.5, 0)
)
Gamma2Sigma(Gamma, k = 1)
Gamma2Theta(Gamma)
my_graph <- Gamma2graph(Gamma)
```

```{r, fig.align='center', echo=FALSE}
Gamma <- cbind(
    c(0, 1.5, 1.5, 2),
    c(1.5, 0, 2, 1.5),
    c(1.5, 2, 0, 1.5),
    c(2, 1.5, 1.5, 0)
)
Gamma2Sigma(Gamma, k = 1)
round(Gamma2Theta(Gamma), 3)
my_graph <- Gamma2graph(Gamma)
```



### Completion of $\Gamma$

For H&uuml;sler--Reiss graphical models it suffices to specify the graph structure $G = (V,E)$ on all entries of the parameter matrix $\Gamma_{ij}$ for $(i,j) \in E$. The remaining entries of the matrix $\Gamma$ are then implicitely implied by the graph structure. 

The function `complete_Gamma()` takes as an input the partially specified $\Gamma$ matrix and the corresponding graph structure $G$, and completes the $\Gamma$ matrix. The mathematical theory for completion is different depening on whether the graph is decomposable or non-decomposable.

The simplest case is a tree, where the entries $\Gamma_{ij}$ for $(i,j) \notin E$ can be easily obtained
from the additive tree metric property \@ref(eq:treemetric).

```{r, fig.align='center'}
set.seed(42)
my_tree <- generate_random_model(d = 4, graph_type = "tree")$graph
Gamma_vec <- c(.5, 1.4, .8)
complete_Gamma(Gamma = Gamma_vec, graph = my_tree)
plot(my_tree)
```

This also works for more general decomposable graphs, where the matrix $\Gamma$ has to be specified on all cliques. For decomposable graphs, the graph structure can also be implied by $\Gamma_{ij} = \text{NA}$ for $(i,j)\notin E$.

```{r, fig.align='center'}
G <- rbind(
    c(0, 5, 7, 6, NA),
    c(5, 0, 14, 15, NA),
    c(7, 14, 0, 5, 5),
    c(6, 15, 5, 0, 6),
    c(NA, NA, 5, 6, 0)
)
complete_Gamma(Gamma = G)
my_graph <- Gamma2graph(complete_Gamma(G))
```

For non-decomposable graphs, a valid $\Gamma$ matrix and an undirected, connected graph has to be provided.


```{r, fig.align='center'}
set.seed(42)
G <- rbind(
    c(0, 5, 7, 6, 6),
    c(5, 0, 14, 15, 13),
    c(7, 14, 0, 5, 5),
    c(6, 15, 5, 0, 6),
    c(6, 13, 5, 6, 0)
)
my_graph <- generate_random_model(d = 5, graph_type = "general", m = 5)$graph
complete_Gamma(Gamma = G, graph = my_graph)
plot(my_graph)
```


### Estimation

Let us first suppose that a connected graph $G$ is given. For some data set, the function `fmpareto_graph_HR()` fits a H&uuml;sler--Reiss graphical model on the graph $G$.

If the graph is decomposable, then the parameters of each clique can be fitted separately and combined together to a full $\Gamma$ matrix. If the cliques are small enough, then (censored) maximum likelihood estimation is feasible, otherwise the empirical extremal variogram is used.
Combining the clique estimates relies on the same principle as in the `complete_Gamma()` function, but with some care required to ensure that the $\Gamma_{ij}$ estimates are consistent if $(i,j)$ belongs to a separator set between two or more cliques. 

```{r, fig.align='center'}
set.seed(42)
d <- 10
my_model <- generate_random_model(d = d, graph_type = "decomposable")
plot(my_model$graph)
Ysim <- rmpareto(n = 100, d = d, model = "HR", par = my_model$Gamma)
my_fit <- fmpareto_graph_HR(data = Ysim, graph = my_model$graph, p = NULL)
ggplot() +
    geom_point(aes(x = c(Gamma2chi(my_fit)), y = c(Gamma2chi(my_model$Gamma)))) +
    geom_abline(slope = 1, intercept = 0) +
    xlab("Fitted") +
    ylab("True") +
    coord_cartesian(xlim = c(0, 1), ylim = c(0, 1))
```


If the graph $G$ is non-decomposable, then the empirical extremal variogram is first computed and then it is fitted to graph structure of $G$ using the function `complete_Gamma()`.


```{r, fig.align='center'}
set.seed(42)
d <- 20
my_model <- generate_random_model(d = d, graph_type = "general")
plot(my_model$graph)
Ysim <- rmpareto(n = 100, d = d, model = "HR", par = my_model$Gamma)
my_fit <- fmpareto_graph_HR(data = Ysim, graph = my_model$graph, p = NULL, method = "vario")
ggplot() +
    geom_point(aes(x = c(Gamma2chi(my_fit)), y = c(Gamma2chi(my_model$Gamma)))) +
    geom_abline(slope = 1, intercept = 0) +
    xlab("Fitted") +
    ylab("True") +
    coord_cartesian(xlim = c(0, 1), ylim = c(0, 1))
```


### Extremal graphical lasso

For structure learning of more general, possibly non-decomposable graphs, we can use the extremal graphical lasso for H&uuml;sler--Reiss distributions. Given an estimate $\widehat \Gamma$ of the parameter matrix, e.g., obtained by `emp_vario()`, we compute the corresponding matrices $\widehat \Sigma^{(k)}$ through the function `Gamma2Sigma()`.

In order to enforce sparsity, we compute the $\ell_1$-penalized precision matrices for each $k\in V$. For a tuning parameter $\rho\geq 0$, the extremal graphical lasso is 
\begin{align*}  
\widehat \Theta^{(k)}_{\rho} = \underset{{\Theta} \succeq 0}{\argmax} \,\,   \log \det{\Theta}-\operatorname{tr}(\widehat \Sigma^{(k)}\Theta) -\rho \sum_{\substack{i\neq j \\ i,j\neq k}} \left|\Theta_{ij}\right|.
\end{align*}
Since we run $d$ different graphical lasso algorithms and the $k$th only enforces sparsity for all edges that do not involve the $k$th node, we determine the estimated graph structure $\widehat{G}_\rho = (\widehat E_\rho,V)$ by majority vote:
 $$ (i,j) \in \widehat E_\rho \quad \Leftrightarrow \quad \frac1{d-2} \# \left\{k \in V \setminus \{i,j\}: \right(\widehat\Theta^{(k)}_\rho \left)_{ij} \neq 0 \right\} \geq 1/2.$$

The best parameter $\rho$ can be chosen for instance as the minimizer of the BIC of the resulting models. The extremal graphical lasso is implemented in the `eglasso()` function. It returns the (sequence) of estimated graphs and, if desired, the corresponding $\widehat \Gamma_\rho$ estimates.

```{r, fig.align='center', message=FALSE, warning=FALSE}
set.seed(42)
# (Ysim from previous example is used)
rholist <- seq(1e-5, 0.04, length.out = 10)
eglasso_fit <- eglearn(
    data = Ysim,
    rholist = rholist,
    complete_Gamma = TRUE
)

eglasso_loglik <- sapply(1:length(rholist), FUN = function(j) {
    loglik_HR(
        data = Ysim, p = .8, Gamma = eglasso_fit$Gamma[[j]],
        graph = eglasso_fit$graph[[j]]
    )
})

emst_fit <- emst(Ysim)

danube_loglik_tree <- loglik_HR(
    data = Ysim, p = .8, Gamma = emst_fit$Gamma,
    graph = emst_fit$graph
)

ggplot(mapping = aes(x = rholist, y = eglasso_loglik[3, ])) +
    geom_line() +
    geom_point(shape = 21, size = 3, stroke = 1, fill = "white") +
    geom_hline(aes(yintercept = danube_loglik_tree[3]), lty = "dashed") +
    xlab("rho") +
    ylab("BIC") +
    scale_x_continuous(
        breaks = rholist,
        labels = round(rholist, 3),
        sec.axis = sec_axis(
            trans = ~., breaks = rholist,
            labels = sapply(eglasso_fit$graph, igraph::gsize),
            name = "Number of edges"
        )
    )
```

```{r, fig.align='center', message=FALSE, warning=FALSE}
best_Gamma <- eglasso_fit$Gamma[[which.min(eglasso_loglik[3, ])]]
chi_hat <- emp_chi(Ysim)

ggplot() +
    geom_point(aes(x = c(Gamma2chi(best_Gamma)), y = c(chi_hat))) +
    geom_abline(slope = 1, intercept = 0) +
    xlab("Fitted") +
    ylab("Empirical") +
    coord_cartesian(
        ylim = c(0, 1),
        xlim = c(0, 1)
    )
```

## Exercises
For some exercises and solutions see `vignette("exercises")`.


# References
