Comparing mutual information between non-co-occurring variables

Let us focus on the pairs $u,v$ that do not co-occur, i.e., for which $N_{uv}=0$. For such a pair, the mutual information $I_{uv}$ is a function of $N_u, N_v$ and $N$. Let us analyze the variation of the mutual information with respect to $N_{v}$ by taking the corresponding partial derivative:

$$\frac{\partial I_{uv}}{\partial N_v}\; = \; \log \frac{N-N_v}{N-N_u-N_v} \;>\;0$$ (11)

This result implies that for a given variable $u$ and any two variables $v,v'$ for which $N_{uv} =N_{uv'}=0$ we have:

$$N_v>N_{v'}\; {\rm implies}\;{\rm that} \; I_{uv}>I_{uv'}.$$

This observation allows us to partially sort the mutual information values $I_{uv}$ for non-co-occurring pairs $u,v$, without computing them. First, we have to sort all the variables by their number of occurrences $N_v$. We store the result in a list $L$. This gives a total ordering ``$\succ$'' for the variables in $V$:

$$v\;\succ \;u\;\;\Leftrightarrow\;\; v\; {\rm preceeds}\; u ... ...rm in}\; {\rm list}\; L \;\; \Rightarrow\;\; N_v\;\geq\;N_u .$$

For each $u$, we define the list of variables following $u$ in the ordering ``$\succ$'' and not co-occurring with it:

$$V_0(u)\;=\;\{v\in V,\;v\prec u,\; N_{uv}=0\} .$$

This list is sorted by decreasing $N_v$ and therefore, implicitly, by decreasing $I_{uv}$. Since the data are sparse, most pairs of variables do not co-occur. Therefore, by creating the lists $V_0(u)$, a large number of values of the mutual information are partially sorted. Before showing how to use this construction, let us examine an efficient way of computing the $N_{uv}$ counts when the data are sparse.

Figure 20: The data structure that supplies the next candidate edge. Vertically on the left are the variables, sorted by decreasing $N_u$. For a given $u$, there are two lists: $C(u)$, sorted by decreasing $I_{uv}$ and (the virtual list) $V_0(u)$, sorted by decreasing $N_v$. The maximum of the two first elements of these lists is inserted into an Fibonacci heap. The overall maximum of $I_{uv}$ can then be extracted as the maximum of the Fibonacci heap.