# How to measure the distance between two Bayesian networks?

Given a set of random variables $\{X_1, X_2, \dots, X_M \}$ and a (complete) dataset $D$, I have used some standard (greedy) algorithms to find good candidates to be the "true" bayesian network modeling/behind the joint probability distribution of these variables.

At the end, I have a set of different bayesian networks with a "high score" (given $D$). I would like to compute some kind of distance between these networks before choosing one. I read about the Kullback-Leibler divergence, but of course I don't know the real network. Is there any useful metric to compare two probability distributions?

• Do the networks have different structures? different variables? different parameters? Why is KL divergence unsuitable? – Bitwise Jul 25 '13 at 17:26
• The networks have different structures and parameters, but same variables (vertex set). The KL divergence somehow measures the distance between a probability distribution $P$ and an approximation $\bar{P}$, but all I have are different approximations $\bar{P_i}$ and not the real underlying distribution $P$. So I don't know how to use KL. It is not even symmetric! – Carlos Jul 25 '13 at 17:29
• Here are some options: en.wikipedia.org/wiki/Statistical_distance – Bitwise Jul 25 '13 at 17:35
• BTW KL divergence is indeed non-symmetric and does not fulfill the triangle inequality, but it does not require that one of the distributions be an approximation of the other. If you don't need symmetry etc. it should be ok to use. – Bitwise Jul 25 '13 at 17:38

You can use Structural Hamming Distance. This paper can help you: A Comparison of Structural Distance Measures for Causal Bayesian Network Models.

I second user43748's recommendation of the Hamming Distance. However, this is only useful for comparing structures; the parameterization of the networks will not affect the distance.

If you are interpreting the DAGs as causal networks, and you are interested in the differences between the causal statements each graph encodes, you can use Peters & Bühlmann's Structural Intervention Distance. Unfortunately however the SID is not symmetric either.

If you're unhappy using Kullback-Leibler divergence the closely-related Jensen-Shannon distance is a true metric (symmetric, triangle inequality etc.).

http://en.wikipedia.org/wiki/Jensen%E2%80%93Shannon_divergence