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 '17 at 20:15

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.

| cite | improve this answer | |
  • 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$ – gung - Reinstate Monica Aug 8 '17 at 15:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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