Variation Of Information For Partition Comparison

Why Compare Partitions With Entropy?

Two subgrouping procedures can assign different labels to the same subjects even when their partitions are identical: “Group 1” and “Group 2” have no intrinsic meaning. The comparison must therefore depend on which subjects are grouped together, not on the names attached to groups. Variation of information (VI) compares two partitions in this label-invariant way. Its two components also distinguish two directions of disagreement: how much one partition subdivides groups of the other, and how much the other subdivides groups of the first.

For a fair comparison, both partitions must be defined on the same set of subjects. In a stability analysis, that requirement matters: if runs include different subjects, first decide how the comparison set is being defined. A distance computed on only the shared subjects describes agreement on that subset, not on the full cohort.

Definition and Interpretation

The labels themselves are arbitrary; their probabilities, and the joint probabilities \(P(C=c,D=d)\), are determined by the overlap of the groups. In a contingency table, the entry in row \(c\), column \(d\) is the number of subjects assigned to group \(c\) by \(\mathcal{C}\) and group \(d\) by \(\mathcal{D}\). Dividing each count by \(n\) gives the corresponding joint probability.

The term \(H(C\mid D)\) measures the remaining uncertainty about a subject’s \(\mathcal{C}\) group after its \(\mathcal{D}\) group is known. If a \(\mathcal{D}\) group contains subjects from several \(\mathcal{C}\) groups, it contributes uncertainty to this term. Conversely, \(H(D\mid C)\) measures uncertainty about \(\mathcal{D}\) when \(\mathcal{C}\) is known. Thus a split of an original group and a merge of original groups can contribute in different directions. Neither term is a count of errors; both are entropy-weighted summaries.

The equivalent expression \(VI=2H(C,D)-H(C)-H(D)\) follows from the entropy chain rule, \(H(C,D)=H(D)+H(C\mid D)=H(C)+H(D\mid C)\). This form can be convenient when calculating from a joint table. The two conditional entropies are usually more useful for interpretation.

Calculating VI From Overlap

Properties and a Justification

VI has several properties that make it useful for comparing partitions. It is symmetric: exchanging \(\mathcal{C}\) and \(\mathcal{D}\) swaps the two conditional entropies but leaves their sum unchanged. It is nonnegative because entropy is nonnegative. It is zero exactly when the partitions are identical up to relabeling: both conditional entropies are zero precisely when each label in either partition determines the label in the other. For partitions, that means the same groups of subjects.

VI also satisfies the triangle inequality, so it is a metric on partitions when partitions that differ only by label names are treated as the same. The key justification is that conditioning cannot increase entropy: \(H(C\mid D,Z)\leq H(C\mid D)\). For any third partition with label \(Z\), the chain rule gives:

Applying the same argument with \(C\) and \(Z\) exchanged gives \(H(Z\mid C)\leq H(D\mid C)+H(Z\mid D)\). Adding the two inequalities yields \(VI(\mathcal{C},\mathcal{Z})\leq VI(\mathcal{C},\mathcal{D})+VI(\mathcal{D},\mathcal{Z})\), as required.

For \(n\) subjects, \(0\leq VI\leq\log_2 n\). To see the upper bound, use the equivalent expression \(VI=H(C,D)-I(C;D)\), where \(I(C;D)=H(C)+H(D)-H(C,D)\) is mutual information. Mutual information is nonnegative, so \(VI\leq H(C,D)\). There are at most \(n\) distinct observed pairs of labels among \(n\) subjects, hence \(H(C,D)\leq\log_2 n\). The bound is attained by comparing a single-group partition with the partition into \(n\) singletons.

Worked Comparisons

Diagnostics, Alternatives, and Limitations

A reliable calculation begins with the overlap table and its margins. Check that all counts are nonnegative integers, that the grand total is \(n\), and that the row and column totals match the sizes of the groups in each partition. Convert counts to probabilities using the same denominator \(n\). Calculate conditional entropy as a weighted average over conditioning groups; omitting the weights is a common source of incorrect results. Terms with zero probability contribute zero, not an undefined quantity.

Use a consistent log base: base 2 reports bits, while natural logarithms report nats. The numerical value changes with the base, so comparisons and any normalization must use a consistent convention. Also verify that the subject identities match across partitions. A table built after inadvertently pairing different subjects has no meaningful interpretation as partition disagreement.

VI complements, rather than replaces, other agreement summaries. The adjusted Rand index is a chance-adjusted pair-counting measure; VI is an entropy-based distance that reports uncertainty in bits. Cluster-wise Jaccard stability focuses on the overlap of individual groups and can help identify which particular subgroup is poorly matched. These summaries answer different questions: a single VI value does not identify the group or subjects driving disagreement, and a single group-wise overlap does not summarize the full partition in the same way.

VI weights subjects through their probabilities in the partition, so large groups contribute more to the overall entropy calculation than equally sized summaries of tiny groups would suggest. A low VI can coexist with a consequential mismatch in a small subgroup. Conversely, a larger value can reflect a broad restructuring of memberships. Inspect the overlap table and subgroup-specific summaries alongside VI when the scientific question concerns particular subtypes. A normalized value such as \(VI/\log_2 n\) lies between zero and one for \(n>1\), but normalization does not remove the dependence of the raw distance on the number of subjects or reveal which groups disagree.

The measure describes disagreement, not its cause. It cannot by itself determine whether a difference arose from sampling variation, feature selection, preprocessing, or algorithmic randomness, and it does not establish that either partition is biologically meaningful. Interpret it in the context of how the partitions were generated and what subjects they cover.