## 4 Application to Gaussian Graphical Models
### Junction Tree Representation
#### 4.3.1 Experiment 1: Block Diagonal Graph Structure  
Consider a graph \(G_{p}\) formed by stacking the adjacency matrix \(A_{G_{5}}\) of \(G_{5}\) (given in Figure 1) \(r\) times along a block diagonal. Using the notation in Section 4.1, \(A_{G_{p}}\ =\ I_{r}\otimes A_{G_{5}}\), for \(r=1,10,20,30\). Similarly, for a randomly generated scale matrix \(\Lambda\in\mathbb{R}^{5\times 5}\), the corresponding scale matrix for \(G_{p}\) is \(\Lambda_{p}=I_{r}\otimes\Lambda\), where \(p=5r\) denotes the dimension of the vertex set of \(G_{p}\). For specific graphs, the corresponding GW normalizing constants can be computed analytically. In particular, for \(G_{5}\), we can use the formula in Equation (4.1) from [PERSON] et al. (2012) to compute \(I_{G_{5}}(\delta,\Lambda)\), which can then be plugged into Equation (13) to obtain the normalizing constant of \(\operatorname{GW}_{G_{5}}(\delta,\Lambda)\). Since \(G_{p}\) explicitly uses \(G_{5}\) to create its dependence structure, we can then easily calculate the normalizing constant of \(\operatorname{GW}_{G_{p}}(\delta,\Lambda_{r})\).  
The results in Table 2 indicate that both GNORM and EPSOM-HybJT produce accurate estimates, with EPSOM-HybJT having a slightly lower relative error. However, the time savings that accompany EPSOM-HybJT are substantial. In the case of \(\operatorname{GW}_{G_{5}}(\delta,\Lambda)\), GNORM is notably faster, but for high-dimensional graphs, there is a dramatic slowdown. Indeed, for \(p=150\), GNORM is more than 100 times slower than EPSOM-HybJT.  
```
Input :Graph \(G\), prior parameters \((\delta,\Lambda)\) for the GW\({}_{G}\) density. Output :Estimate of the logarithm of the normalizing constant of GW\({}_{G}(\delta,\Lambda)\).  Obtain the JT representation of \(G\mapsto\mathcal{J}_{G}=\{P_{1},S_{2},P_{2},S_{3},\ldots,P_{m-1},S_{m},P_{m}\}\). for\(i\in\{1,\ldots,m\}\)do if\(i>1\)then \(\log\widehat{\mathcal{Z}}_{S_{i}}\leftarrow\log h\big{(}S_{i},\delta,\Lambda_{S _{i}}\big{)}\). end if\(P_{i}\) is completethen \(\log\widehat{\mathcal{Z}}_{P_{i}}\leftarrow\log h\big{(}P_{i},\delta,\Lambda_{P _{i}}\big{)}\). else  Compute the Cholesky decomposition, \(\Lambda_{P_{i}}^{-1}=T_{i}^{\prime}T_{i}\). for\(j\in\{1,\ldots,\}\)do  Sample \(\Omega_{(j)}\sim\text{GW}_{P_{i}}\big{(}\delta,\Lambda_{P_{i}}\big{)}\).  Compute the Cholesky decomposition, \(\Omega_{(j)}=\phi_{(j)}^{\prime}\phi_{(j)}\). \(\zeta_{(j)}\leftarrow\phi_{(j)}T_{i}^{-1}\).  Extract the free parameters \(u_{j}\) from \(\zeta_{(j)}\).  end for  Fit a CART model, \(\mathcal{T}_{i}\), to \((u_{1},\Psi_{P_{i}}(u_{1})),\ldots,(u_{I},\Psi_{P_{i}}(u_{I}))\).  Extract the partition \(\mathcal{A}=\{A_{k}\}_{1\leq k\leq K}\) from \(\mathcal{T}_{i}\) of the bounding box \(A\) of \(\mathcal{U}\).  Calculate the global mode, \(u_{0}\), of \(\Psi_{P_{i}}\). for\(k\in\{1,\ldots,K\}\)do \(u_{k}\leftarrow\text{argmin}_{u\in A_{k}}||u-u_{0}||_{1}\). \(\lambda_{k}\leftarrow\
abla\Psi_{P_{i}}(u_{k})\). \(H_{k}\leftarrow\
abla^{2}\Psi_{P_{i}}(u_{k})\). \(C_{k}\leftarrow(2\pi)^{d/2}|H_{k}|^{-1/2}\exp\Big{(}\frac{1}{2}\Big{(}u_{k}^{ \prime}H_{k}^{-1}u_{k}-2\lambda_{k}^{\prime}u_{k}+\lambda_{k}^{\prime}H_{k}^{ -1}\lambda_{k}\Big{)}\Big{)}\). \(b_{k}\gets H_{k}u_{k}-\lambda_{k}\). \(G_{k}\leftarrow\int_{A_{k}}\mathcal{N}\Big{(}u\mid H_{k}^{-1}b_{k},H_{k}^{-1} \Big{)}\,du\). \(\widehat{\mathcal{Z}}_{k}\gets C_{k}\cdot G_{k}\).  end for \(\log\widehat{\mathcal{Z}}_{P_{i}}\leftarrow\text{log-sum-exp}\big{(}\log \widehat{\mathcal{Z}}_{1},\ldots,\log\widehat{\mathcal{Z}}_{K}\big{)}\).  end for  end for return\(\log\widehat{\mathcal{Z}}=\sum_{i}\log\widehat{\mathcal{Z}}_{P_{i}}-\sum_{i} \log\widehat{\mathcal{Z}}_{S_{i}}\).
```  
**Algorithm 2**EPSOM-HybJT