## 4 Shannon Entropy and Kullback-Leibler Divergence
### Conditional Gaussian BNs  
The entropy \(\mathrm{H}(\mathcal{B})\) decomposes into a separate \(\mathrm{H}\left(X_{i}\mid\Pi_{X_{i}}^{\mathcal{B}}\right)\) for each node, of the form (9) for discrete nodes and (12) for continuous nodes with no discrete parents. For continuous nodes with both discrete and continuous parents,  
\[\mathrm{H}\left(X_{i}\mid\Pi_{X_{i}}^{\mathcal{B}}\right)=\frac{1}{2}\sum_{ \delta_{X_{i}}\in\mathcal{Val}(\Delta_{X_{i}})}\pi_{\delta_{X_{i}}}\log\Bigl{(} 2\pi\sigma_{X_{i},\delta_{X_{i}}}^{2}(\mathcal{B})\Bigr{)}+\frac{1}{2}, \tag{24}\]  
where \(\pi_{\delta_{X_{i}}}\) represents the probability associated with the configuration \(\delta_{X_{i}}\) of the discrete parents \(\Delta_{X_{i}}\). This last expression can be computed in \(O\bigl{(}|\mathit{Val}(\Delta_{X_{i}})|\bigr{)}\) time for each node. Overall, the complexity of computing \(\mathrm{H}(\mathcal{B})\) is  
\[O\Biggl{(}\sum_{X_{i}\in\mathbf{X}_{D}}|\Theta_{X_{i}}|+\sum_{X_{i}\in \mathbf{X}_{G}}\max\bigl{\{}1,|\mathit{Val}(\Delta_{X_{i}})|\bigr{\}}\Biggr{)}.\]  
where the max accounts for the fact that \(|\mathit{Val}(\Delta_{X_{i}})|=0\) when \(\Delta_{X_{i}}=\varnothing\) but the computational complexity is \(O(1)\) for such nodes. **Example 11** (Entropy of a CLGBN). : _For reasons of space, this example is presented as Example A6 in Appendix B._  
As for \(\mathrm{KL}(\mathcal{B}\parallel\mathcal{B}^{\prime})\), we could not find any literature illustrating how to compute it. The partition of the nodes in (5) implies that  
\[\mathrm{KL}\bigl{(}\mathcal{B}\parallel\mathcal{B}^{\prime}\bigr{)}=\underbrace {\mathrm{KL}\Bigl{(}\mathbf{X}_{D}^{\mathcal{B}}\Big{\|}\mathbf{X}_{D}^{ \mathcal{B}^{\prime}}\Bigr{)}}_{\mathrm{discrete\ nodes}}+\underbrace{ \mathrm{KL}\Bigl{(}\mathbf{X}_{G}^{\mathcal{B}}\mid\mathbf{X}_{D}^{\mathcal{B} }\Big{\|}\mathbf{X}_{G}^{\mathcal{B}^{\prime}}\mid\mathbf{X}_{D}^{\mathcal{B }^{\prime}}\Big{)}}_{\mathrm{continuous\ nodes}}. \tag{25}\]  
We can compute the first term following Section 4.1: \(\mathbf{X}_{D}^{\mathcal{B}}\) and \(\mathbf{X}_{D}^{\mathcal{B}^{\prime}}\) form two discrete BNs whose DAGs are the spanning subgraphs of \(\mathcal{B}\) and \(\mathcal{B}^{\prime}\) and whose local distributions are the corresponding ones in \(\mathcal{B}\) and \(\mathcal{B}^{\prime}\), respectively. The second term decomposes into  
\[\mathrm{KL}\Bigl{(}\mathbf{X}_{G}^{\mathcal{B}}\mid\mathbf{X}_{D}^{\mathcal{B }}\Big{\|}\mathbf{X}_{G}^{\mathcal{B}^{\prime}}\mid\mathbf{X}_{D}^{\mathcal{B }^{\prime}}\Bigr{)}=\sum_{\mathbf{x}_{D}\in\mathcal{Val}(\mathbf{x}_{D})} \mathrm{P}\Bigl{(}\mathbf{X}_{D}^{\mathcal{B}}=\mathbf{x}_{D}\Bigr{)}\,\mathrm{ KL}\Bigl{(}\mathbf{X}_{G}^{\mathcal{B}}\mid\mathbf{X}_{D}^{\mathcal{B }}=\mathbf{x}_{D}\,\Big{\|}\,\mathbf{X}_{G}^{\mathcal{B}^{\prime}}\mid\mathbf{X }_{D}^{\mathcal{B}^{\prime}}=\mathbf{x}_{D}\Bigr{)} \tag{26}\]  
similarly to (10) and (24). We can compute it using the multivariate normal distributions associated with the \(\mathbf{X}_{D}^{\mathcal{B}}=\mathbf{x}_{D}\) and the \(\mathbf{X}_{D}^{\mathcal{B}^{\prime}}=\mathbf{x}_{D}\) in the global distributions of \(\mathcal{B}\) and \(\mathcal{B}^{\prime}\). **Example 12** (General-case KL between two CLGBNs). : _Consider the CLGBNs \(\mathcal{B}\) from Figure 3 top, which we already used in Examples 3 and 11, and \(\mathcal{B}^{\prime}\) from Figure 3 bottom. The variables \(\mathbf{X}_{D}^{\mathcal{B}^{\prime}}\) identify the following mixture components in the global distribution of \(\mathcal{B}^{\prime}\):_  
\[\{a,c,e\},\{b,c,e\},\{a,d,e\},\{b,d,e\}\mapsto\{e\},\] \[\{a,c,f\},\{b,c,f\},\{a,d,f\},\{b,d,f\}\mapsto\{f\}.\]_Therefore, \(\mathcal{B}^{\prime}\) only encodes two different multivariate normal distributions._  
_Firstly, we construct two discrete BNs using the subgraphs spanning \(\mathbf{X}_{D}^{\mathcal{B}}=\mathbf{X}_{D}^{\mathcal{B}^{\prime}}=\{X_{1},X_{2},X_{3}\}\) in \(\mathcal{B}\) and \(\mathcal{B}^{\prime}\), which have arcs \(\{X_{1}\to X_{2}\}\) and \(\{X_{1}\to X_{2},X_{2}\to X_{3}\}\), respectively.