## 4 Shannon Entropy and Kullback-Leibler Divergence
### Gaussian BNs
Then, following the derivations in [PERSON] [55] for a general linear regression model, we can write the empirical approximation  
\[\operatorname{KL}\Big{(}X_{i}\mid\Pi_{X_{i}}^{\mathcal{B}}\Big{\|}\,X_{i} \mid\Pi_{X_{i}}^{\mathcal{B}^{\prime}}\Big{)}\approx\frac{1}{2}\Bigg{(}\log \frac{\widehat{\sigma}_{X_{i}}^{2}(\mathcal{B}^{\prime})}{\widehat{\sigma}_{X _{i}}^{2}(\mathcal{B})}+\frac{\widehat{\sigma}_{X_{i}}^{2}(\mathcal{B})}{ \widehat{\sigma}_{X_{i}}^{2}(\mathcal{B}^{\prime})}-1\Bigg{)}+\frac{1}{2n} \Bigg{(}\frac{\|\tilde{\kappa}_{i}(\mathcal{B})-\widehat{\kappa}_{i}( \mathcal{B}^{\prime})\|_{2}^{2}}{\widehat{\sigma}_{X_{i}}^{2}(\mathcal{B}^{ \prime})}\Bigg{)} \tag{23}\]  
where, following a similar notation to (4):  
* \(\widehat{\mu}_{X_{i}}(\mathcal{B})\), \(\widehat{\beta}_{X_{i}}(\mathcal{B})\), \(\widehat{\mu}_{X_{i}}(\mathcal{B}^{\prime})\), \(\widehat{\beta}_{X_{i}}(\mathcal{B}^{\prime})\) are the estimated intercepts and regression coefficients;
* \(\widehat{\kappa}_{i}(\mathcal{B})\) and \(\widehat{\kappa}_{i}(\mathcal{B}^{\prime})\) are the \(n\times 1\) vectors \[\widehat{\kappa}_{i}(\mathcal{B})=\widehat{\mu}_{X_{i}}(\mathcal{B})+\mathbf{x }[\,\boldsymbol{\cdot};\Pi_{X_{i}}(\mathcal{B})]\widehat{\beta}_{X_{i}}( \mathcal{B}),\ \ \ \widehat{\kappa}_{i}(\mathcal{B}^{\prime})=\widehat{\mu}_{X_{i}}(\mathcal{B}^{ \prime})+\mathbf{x}[\,\boldsymbol{\cdot};\Pi_{X_{i}}(\mathcal{B}^{\prime})] \widehat{\beta}_{X_{i}}(\mathcal{B}^{\prime}),\] the fitted values computed from the data observed for \(X_{i}\), \(\Pi_{X_{i}}(\mathcal{B})\), \(\Pi_{X_{i}}(\mathcal{B}^{\prime})\);
* \(\sigma_{X_{i}}^{2}(\mathcal{B})\) and \(\sigma_{X_{i}}^{2}(\mathcal{B}^{\prime})\) are the residual variances in \(\mathcal{B}\) and \(\mathcal{B}^{\prime}\). We can compute the expression in (23) for each node in \[\underbrace{O\big{(}n\big{(}|\Pi_{X_{i}}(\mathcal{B})|+|\Pi_{X_{i}}( \mathcal{B}^{\prime})|+2\big{)}\big{)}}_{\text{compute $\widehat{\kappa}_{i}(\mathcal{B})$ and $\widehat{\kappa}_{i}(\mathcal{B}^{\prime})$}}+\underbrace{O(n)}_{\text{ compute the norm $\|\widehat{\kappa}_{i}(\mathcal{B})-\widehat{\kappa}_{i}(\mathcal{B}^{\prime})\|_{2}^{2}$}} =\] \[O\big{(}n\big{(}|\Pi_{X_{i}}(\mathcal{B})|+|\Pi_{X_{i}}(\mathcal{ B}^{\prime})|+\
icefrac{{5}}{{2}}\big{)}\big{)},\]  
which is linear in the sample size if both \(\mathcal{G}\) and \(\mathcal{G}^{\prime}\) are sparse because \(|\Pi_{X_{i}}(\mathcal{B})|\leqslant c\), \(|\Pi_{X_{i}}(\mathcal{B}^{\prime})|\leqslant c\). In this case, the overall computational complexity simplifies to \(O(nN(2c+5/2))\). Furthermore, as we pointed out in [PERSON] et al. [29], the fitted values \(\widehat{\kappa}_{i}(\mathcal{B})\), \(\widehat{\kappa}_{i}(\mathcal{B}^{\prime})\) are computed as a by-product of parameter learning: if we consider them to be already available, the above computational complexity is reduced to just \(O(n)\) for a single node and \(O(nN)\) overall. We can also replace the fitted values \(\widehat{\mathbf{x}}_{i}(\mathcal{B})\), \(\widehat{\mathbf{x}}_{i}(\mathcal{B}^{\prime})\) in (23) with the corresponding residuals \(\widehat{\mathbf{\varepsilon}}_{i}(\mathcal{B})\), \(\widehat{\mathbf{\varepsilon}}_{i}(\mathcal{B}^{\prime})\) because  
\[\operatorname{tr}(\Sigma_{\mathcal{B}^{\prime}}^{-1}\Sigma_{\mathcal{B}}) \leqslant\operatorname{tr}(\Sigma_{\mathcal{B}^{\prime}}^{-1})\operatorname{ tr}(\Sigma_{\mathcal{B}})=\operatorname{tr}\left((C_{\mathcal{B}^{\prime}}C_{ \mathcal{B}^{\prime}}^{\mathrm{T}})^{-1}\right)\operatorname{tr}(C_{\mathcal{B}}C_ {\mathcal{B}}^{\mathrm{T}})=\|C_{\mathcal{B}^{\prime}}^{-1}\|_{F}^{2}\|C_{ \mathcal{B}}\|_{F}^{2}\,, \tag{22}\]0  
if the latter are available but the former are not. **Example 10** (KL between GBNs with parameters estimated from data). : _For reasons of space, this example is presented as Example A5 in Appendix B._