# Mutual information and the encoding of contingency tables

arXiv: https://arxiv.org/abs/2405.05393 · HTML: https://mlsanity.com/paper/2405.05393/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 34 references that are in the map.
- First posted on arXiv 8 May 2024.

## Builds on (most cited first, 7 of 7)

- [From Louvain to Leiden: guaranteeing well-connected communities](https://mlsanity.com/paper/1810.08473/) (2018)
- [A Comparative Analysis of Community Detection Algorithms on Artificial Networks](https://mlsanity.com/paper/1608.00763/) (2016)
- [Nonparametric Bayesian inference of the microcanonical stochastic block model](https://mlsanity.com/paper/1610.02703/) (2016)
- [Evaluating accuracy of community detection using the relative normalized mutual information](https://mlsanity.com/paper/1501.03844/) (2015)
- [Spatial regionalization based on optimal information compression](https://mlsanity.com/paper/2111.01813/) (2021)
- [Inference of dynamic hypergraph representations in temporal interaction data](https://mlsanity.com/paper/2308.16546/) (2023)
- [Comment on "Improved mutual information measure for clustering, classification, and community detection"](https://mlsanity.com/paper/2005.07007/) (2020)

## Built on by (most cited first, 2 of 2)

- [Unifying Information-Theoretic and Pair-Counting Clustering Similarity](https://mlsanity.com/paper/2511.03000/) (2025)
- [Scalable inference of spatial regions and temporal signatures from time series](https://mlsanity.com/paper/2605.05008/) (2026)

## Abstract (arXiv)

Mutual information is commonly used as a measure of similarity between competing labelings of a given set of objects, for example to quantify performance in classification and community detection tasks. As argued recently, however, the mutual information as conventionally defined can return biased results because it neglects the information cost of the so-called contingency table, a crucial component of the similarity calculation. In principle the bias can be rectified by subtracting the appropriate information cost, leading to the modified measure known as the reduced mutual information, but in practice one can only ever compute an upper bound on this information cost, and the value of the reduced mutual information depends crucially on how good a bound is established. In this paper we describe an improved method for encoding contingency tables that gives a substantially better bound in typical use cases, and approaches the ideal value in the common case where the labelings are closely similar, as we demonstrate with extensive numerical results.