# Square Hellinger Subadditivity for Bayesian Networks and its Applications to Identity Testing

arXiv: https://arxiv.org/abs/1612.03164 · HTML: https://mlsanity.com/paper/1612.03164/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Dec 2016.

## Built on by (most cited first, 11 of 11)

- [Private High-Dimensional Hypothesis Testing](https://mlsanity.com/paper/2203.01537/) (2022)
- [Learning and Testing Latent-Tree Ising Models Efficiently](https://mlsanity.com/paper/2211.13291/) (2022)
- [Independence Testing for Bounded Degree Bayesian Network](https://mlsanity.com/paper/2204.08690/) (2022)
- [Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling](https://mlsanity.com/paper/2207.09102/) (2022)
- [Near-Optimal Degree Testing for Bayes Nets](https://mlsanity.com/paper/2304.06733/) (2023)
- [Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning](https://mlsanity.com/paper/2502.16355/) (2025)
- [Product distribution learning with imperfect advice](https://mlsanity.com/paper/2511.10366/) (2025)
- [Asymptotic Causal Inference](https://mlsanity.com/paper/2109.09653/) (2021)
- [Dimension Agnostic Testing of Survey Data Credibility through the Lens of Regression](https://mlsanity.com/paper/2508.20616/) (2025)
- [Graph-Informed Adversarial Modeling: Infimal Subadditivity of Interpolative Divergences](https://mlsanity.com/paper/2603.20025/) (2026)
- [Entropy Equivalence Testing](https://mlsanity.com/paper/2605.23225/) (2026)

## Abstract (arXiv)

We show that the square Hellinger distance between two Bayesian networks on the same directed graph, G, is subadditive with respect to the neighborhoods of G. Namely, if P and Q are the probability distributions defined by two Bayesian networks on the same DAG, our inequality states that the square Hellinger distance, H2(P,Q), between P and Q is upper bounded by the sum, sumv H2(P_v cup Piv, Q_v cup Piv), of the square Hellinger distances between the marginals of P and Q on every node v and its parents Piv in the DAG. Importantly, our bound does not involve the conditionals but the marginals of P and Q. We derive a similar inequality for more general Markov Random Fields. As an application of our inequality, we show that distinguishing whether two Bayesian networks P and Q on the same (but potentially unknown) DAG satisfy P=Q vs drm TV(P,Q)>ε can be performed from tildeO(|Sigma|3/4(d+1) · n/ε2) samples, where d is the maximum in-degree of the DAG and Sigma the domain of each variable of the Bayesian networks. If P and Q are defined on potentially different and potentially unknown trees, the sample complexity becomes tildeO(|Sigma|4.5 n/ε2), whose dependence on n, ε is optimal up to logarithmic factors. Lastly, if P and Q are product distributions over 0,1n and Q is known, the sample complexity becomes O(√n/ε2), which is optimal up to constant factors.