Understanding the entropy of edge counts at each hSBM layer
Dear Tiago, I am trying to understand each value of NestedBlockState.level_entropy that contributes to the entropy of a hierarchical SBM (hSBM). In particular, I am focusing on the “prior for the edge counts“. In PRE 95, 012317 (2017), we have used the multigraph entropy for _all levels_ of the hSBM because of the dominance of parallel edges at higher levels. Nevertheless, for each level (l=k; 1 <= k < L), we assume its connectivity pattern is generated by some NDC-SBM at a higher level (l=k+1), rendering the sum of the entropy terms of all levels smaller than that of a flat prior, avoiding under-fitting. There will be 2 questions along with the thread. To see what arguments BlockState.entropy() uses, I added,
print("eargs.###: {}".format(eargs.###))
before the return line of the entropy() function in the graph_tool/inference/blockmodel.py file, where ### can be _degree_dl_, _edges_dl_, and _multigraph_, etc. Taking the “lesmis” dataset as an example, if we run minimize_nested_blockmodel_dl() on it, we (may) obtain two levels, i.e. [(77, 6), (6, 1)]. Now using this commands,
nested_state.level_entropy(0)
which outputs: eargs.dense: False eargs.edges_dl: False eargs.multigraph: True Out[•]: 630.133156768878 And, with this command,
nested_state.level_entropy(1)
It outputs: eargs.dense: True eargs.edges_dl: True eargs.multigraph: True Out[•]: 71.0082133080805 Which constitute the two levels of entropies that sum up to nested_state.entropy(). Here is my 1st question: 🧐 Why is `edges_dl` excluded except the highest level? I expected `edges_dl` at the lowest to be something nonzero, but _less_ than `69.21645383885243`, i.e. the exact negative logarithm of Eq. (40) of the PRE paper, using B=6 and e=254 (the number of edges of the “lesmis” dataset). Am I thinking it the right way? 🧐 <— this is the 2nd question. Sincerely thanks, Tzu-Chi -- Sent from: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/
Am 09.11.18 um 03:42 schrieb Tzu-Chi Yen:
🧐 Why is `edges_dl` excluded except the highest level?
The `edges_dl` parameter corresponds to the flat prior for the edge counts, i.e. ((B(B+1)/2 E)). We need to turn this off for the intermediate layers, since this is replaced by the SBM at the upper layer.
I expected `edges_dl` at the lowest to be something nonzero, but _less_ than `69.21645383885243`, i.e. the exact negative logarithm of Eq. (40) of the PRE paper, using B=6 and e=254 (the number of edges of the “lesmis” dataset). Am I thinking it the right way? 🧐 <— this is the 2nd question.
No, `edges_dl` corresponds precisely to Eq. 40, this is why it needs to be disabled in the intermediate layers. Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>
Now I understand that `edges_dl` specifically encodes the flat prior. I have 2 following questions: 🤔- How could I access the terms in Eq.(41) of the PRE paper, i.e. each term is the level-wise entropy of edge counts, as Eq.(42) describes? For the "lesmis" dataset, the bottom-most layer has the entropy:
nested_state.level_entropy(0) Out[•]: 630.133156768878
This is exactly the sum of these three entropic terms: "adjacency" (332.24632), "degree_dl" (170.10951), and "partition_dl" (127.77732). I could not find a rationale about the missing entropy for edge counts. 🤔- I found that `nested_state.levels[0].entropy(deg_entropy=True) - nested_state.levels[0].entropy(deg_entropy=False) < 0`. This command is expected to print the negative logarithm of Eq.(28) of the paper, which is positive. I am not sure what went wrong. Thanks, Tzu-Chi -- Sent from: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/
Am 09.11.18 um 16:30 schrieb Tzu-Chi Yen:
Now I understand that `edges_dl` specifically encodes the flat prior. I have 2 following questions:
🤔- How could I access the terms in Eq.(41) of the PRE paper, i.e. each term is the level-wise entropy of edge counts, as Eq.(42) describes?
These are given by the different hierarchy levels, level_entropy(1), level_entropy(2), etc.
For the "lesmis" dataset, the bottom-most layer has the entropy:
nested_state.level_entropy(0) Out[•]: 630.133156768878
This is exactly the sum of these three entropic terms: "adjacency" (332.24632), "degree_dl" (170.10951), and "partition_dl" (127.77732). I could not find a rationale about the missing entropy for edge counts.
This is given by the upper layers, as answered above.
🤔- I found that `nested_state.levels[0].entropy(deg_entropy=True) - nested_state.levels[0].entropy(deg_entropy=False) < 0`. This command is expected to print the negative logarithm of Eq.(28) of the paper, which is positive. I am not sure what went wrong.
No, 'deg_entropy` controls the degree part of the likelihood, not the prior. The parameter you want is `degree_dl`. Best, Tiago -- Tiago de Paula Peixoto <tiago@skewed.de>
Thanks you, now I could rationalize how these level_entropies work. Perhaps lastly, I would like to make sure what `deg_entropy` returns. When it means the degree part of the likelihood, does it compute the negative log of the numerator of Eq. (2) of the PRE paper? Its value could not be justified by the term-by-term summation of these gammaln(k)'s. Warmest thanks, Tzu-Chi -- Sent from: http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/
Am 15.11.18 um 11:27 schrieb Tzu-Chi Yen:
Thanks you, now I could rationalize how these level_entropies work.
Perhaps lastly, I would like to make sure what `deg_entropy` returns. When it means the degree part of the likelihood, does it compute the negative log of the numerator of Eq. (2) of the PRE paper?
Yes, that's right. -- Tiago de Paula Peixoto <tiago@skewed.de>
participants (2)
-
Tiago de Paula Peixoto -
Tzu-Chi Yen