I am from Computer Science background and need to apply Kullback Leibler Divergence to find the divergence between two distributions of unknown types. Let's say I have a graph G(V,E) and I make a small sample out of it Gs(Vs,Es). Now I have two degree distributions, the PDF of graph G (lets call it X) and that of Gs (lets call it Y). I apply KLD(X||Y) and get the results and results seems fine. What I want to discuss is that:

  1. Since KL is non-symmetric and not a true metric, is it a good test in my case or not? I am confused with the non-symmetric nature of KL and cannot properly grasp the idea if KL test is good in my case or not?
  2. what if I calculate the divergence as 0.5*[KLD(X||Y) + KLD(Y||X)]. I read a few papers in my field and both formulas (in 1 & 2) have been used by researchers without any explanation. I would like to know from a Statistician which one is better (if any) and why?
  • $\begingroup$ It seems to me that graph $G$ does not vary (it is given). Then what do you mean by the KL divergence between these two distributions? $\endgroup$
    – Yair Daon
    Jul 11, 2017 at 20:15

1 Answer 1


The symetric divergence of your formula (2) is called Jensen-Shannon divergence.

I believe you will find the explanation you are looking for on the following paper. On Results section there is an explanation of Jensen-Shanon divergence for graphs.

There is also a book called "Mathematical Foundations and Applications of Graph Entropy" and a more detailed explanation is available at chapter 6.

  • 1
    $\begingroup$ Welcome to the site, @TaianeRamos. Can you post a full citation & a summary of the information at the link, in case it goes dead? $\endgroup$ Aug 8, 2017 at 15:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.