Variation of Information for Comparing Partitions

Why Compare Partitions With Information?

Two clustering runs can assign the same cells to different numbers of groups, and cluster labels such as “1” and “2” are arbitrary. A useful comparison should therefore depend on which cells share groups, not on the names assigned to those groups or on having the same number of groups. Variation of information (VI) measures how much information about one partition is missing when the other partition is known.

For a valid comparison, both partitions must classify the same set of cells, with each cell assigned to exactly one cluster in each partition. Unless otherwise stated, each cell receives equal weight, so a cell selected uniformly at random defines the probability distribution used below. This makes the calculation empirical: cluster proportions and joint proportions are counts divided by the number of cells.

The joint probabilities \(P(C=c,D=d)\) are obtained from the contingency table of the two partitions. A row represents a cluster in \(C\), a column a cluster in \(D\), and each entry counts cells assigned to that pair of clusters. Empty combinations have probability zero and do not contribute to the sums. The labels themselves do not matter: permuting rows or columns changes neither the probabilities nor VI.

From Mutual Information to Conditional Entropy

Conditional entropy \(H(C\mid D)\) is the average uncertainty about \(C\) that remains after \(D\) is known. In terms of entropies, \(H(C\mid D)=H(C,D)-H(D)\), where \(H(C,D)\) is the entropy of the joint cluster-pair distribution. Mutual information satisfies \(I(C;D)=H(C)+H(D)-H(C,D)\). Substituting this identity into the definition of VI gives

This form gives the measure its direct interpretation: one term records the uncertainty about \(C\) left by \(D\), and the other records the uncertainty about \(D\) left by \(C\). Both directions matter. If one clustering splits a group in the other, for example, the extra distinctions are counted even if the reverse comparison would appear less complicated.

Comparing Different Numbers of Clusters

Nothing in the definition requires the partitions to have the same number of clusters. Each partition contributes its own marginal entropy, and the joint table simply has as many rows and columns as its partitions have observed clusters. This is useful when comparing clustering resolutions: VI accounts for disagreement in cell membership and for distinctions introduced or lost when the number of groups changes.

Why VI Is a Distance

VI is nonnegative because each conditional entropy is nonnegative. It is symmetric because \(H(C\mid D)+H(D\mid C)\) is unchanged when \(C\) and \(D\) are swapped. It is zero exactly when each partition determines the other: every cluster in one corresponds to exactly one cluster in the other, up to relabelling. Thus zero means the same grouping of cells, not necessarily the same cluster names.

The triangle inequality also holds. For three partitions \(A,B,C\), conditional entropy cannot increase when additional information is supplied. By the chain rule and this fact, \(H(A\mid C)\leq H(B\mid C)+H(A\mid B)\): first, \(H(A\mid C)\leq H(A,B\mid C)\); then \(H(A,B\mid C)=H(B\mid C)+H(A\mid B,C)\leq H(B\mid C)+H(A\mid B)\). Reversing the roles gives \(H(C\mid A)\leq H(B\mid A)+H(C\mid B)\). Adding the inequalities yields

The triangle inequality means that VI behaves coherently as a distance across partitions, rather than merely assigning an arbitrary disagreement score. For a fixed set of \(n\) cells, it also satisfies \(0\leq VI(C,D)\leq\ln n\). To see the upper bound, \(VI=2H(C,D)-H(C)-H(D)\leq H(C,D)\), since \(H(C,D)\leq H(C)+H(D)\); and the joint distribution has at most \(n\) observed cell-pairs, so \(H(C,D)\leq\ln n\). The bound depends on the number of cells and the log base.

Diagnostics, Alternatives, and Limitations

Before interpreting a value, check that the partitions refer to exactly the same cells and that the contingency-table margins agree with the stated cluster sizes. A row or column of all zeros is not an observed cluster and should be omitted. Confirm that probabilities sum to one and that the same logarithm base is used throughout. A calculation producing negative VI indicates an error in the table, probabilities, or arithmetic.

VI differs from label matching and pair-count-based measures. Relabelling clusters is unnecessary, and unequal cluster counts pose no special problem. Measures such as the adjusted Rand index instead summarize agreement among pairs of cells and adjust for chance agreement under a specified model; they answer a related but not identical question and have a different scale. VI is interpretable through uncertainty and has units that depend on the logarithm base. Changing from natural logarithms to base-2 logarithms multiplies every value by \(1/\ln2\), expressing the distance in bits instead of nats.

A common mistake is to interpret a larger VI as a fixed amount of biological instability, or to compare values across datasets without considering their size and composition. VI describes disagreement between two observed partitions; it does not establish which partition is biologically correct, and it does not identify the source of disagreement. Comparisons are most informative when the same cells, preprocessing choices, and weighting convention are used. If runs contain different cells, a direct contingency table is not defined until the comparison set is specified; comparing only shared cells changes the target population and should be reported as such.