Resampled Mutual Information for Clustering and Community Detection

Cheaheon Lim

REVIEW 3 major objections 3 minor 18 references

Resampled Mutual Information for Clustering and Community Detection

T0 review · 3 major / 3 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Resampled mutual information gives clustering comparisons a zero baseline without correction terms.

desk verdict ResMI is a genuinely new measure, but its flagship claim—constant baseline without chance correction—only holds for a special null model and fails under the standard permutation model. read the letter →

arxiv 2412.03584 v1 pith:DY4KSOTG submitted 2024-11-21 cs.SI cs.LG

Cheaheon Lim This is my paper · ORCID

classification cs.SIcs.LG MSC 62H30

keywords clusteringsimilaritymutualinformationconstantbaselinepropertychancecorrectioncommunitydetectionpaircountingmodelindependenceadjustedrandindex

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper introduces resampled mutual information (ResMI), a measure for comparing two clusterings, and argues that it solves a known defect of standard scores: the expected similarity between two independent clusterings should be zero, yet normalized mutual information (NMI) and the Rand index (RI) are not zero on average. ResMI instead draws two objects at random and records, for each labeling, whether the two objects land in the same cluster, then takes the normalized mutual information between those two Bernoulli indicators. The paper's central claim is that this resampling step gives the constant baseline property automatically, without a chance-correction term, so ResMI remains bounded in $[0,1]$, model-independent, and interpretable as shared information. Synthetic experiments and two real contact-tracing networks are used to show that ResMI avoids the cluster-count bias of NMI and the asymmetric-cluster bias of the adjusted Rand index.

What carries the argument

The machinery is the replacement of the labels themselves by pairwise agreement events. Let $G=\{(i,j):g(i)=g(j), i>j\}$; with $q_f$ the co-clustering rate under $f$, $q_g$ under $g$, and $q_{f|G}$, $q_{f|G^c}$ the conditional rates inside and outside $G$, the numerator of ResMI is $$I_{\mathrm{ResMI}}(f;g)=h_b(q_f)-\left[q_g h_b(q_{f|G})+(1-q_g)h_b(q_{f|G^c})\right],$$ where $h_b$ is the binary entropy function. This identity turns the pair-counting intuition of the Rand index into an information-theoretic quantity and makes the mutual information depend only on four co-clustering probabilities rather than on the full contingency table. The same object delivers the constant baseline property: under independent random labelings of the uniform-label kind, the expected value of this expression is zero, so no chance-correction term is required.

What would settle it

Compute the expected ResMI between two random partitions of $n=3$ objects with cluster sizes $2$ and $1$, drawn uniformly from all fixed-size partitions; the expected value is about $0.515$, not $0$, which would directly contradict the claim that the constant baseline holds in generality.

Watch

Extended reading notes

Core claim

The central claim is that the right information-theoretic object for comparing clusterings is the mutual information between pair-co-clustering indicators, not between label assignments. Formally, for labelings $f,g$ and a uniformly random pair $(Z_1,Z_2)$ drawn without replacement, ResMI is $$\mathrm{ResMI}(f,g)=\frac{I(\mathbf{1}\{f(Z_1)=f(Z_2)\};\mathbf{1}\{g(Z_1)=g(Z_2)\})}{\frac{1}{2}\left(H(\mathbf{1}\{f(Z_1)=f(Z_2)\})+H(\mathbf{1}\{g(Z_1)=g(Z_2)\})\right)}.$$ Because the two Bernoulli variables have probabilities $q_f$ and $q_g$ equal to the empirical co-clustering rates of the two labelings, the trivial labelings (all objects in one cluster, or each object in its own cluster) contribute zero information, and the author reports that the expected value under independently drawn random labelings is zero. This is exactly the constant baseline property that NMI and RI lack, achieved without subtracting an expected-value adjustment term. On this basis the paper claims ResMI is free of cluster-count bias, free of the symmetry bias that distorts ARI, and more conservative than NMI and RMI when clusterings depart from a ground truth.

Load-bearing premise

The zero baseline depends on the two Bernoulli co-clustering indicators being independent when labelings are generated at random, which holds for independent uniform label assignment but fails when cluster sizes are fixed as in the permutation model.

Editorial extensions

If this is right

ResMI can be used as a standalone, bounded clustering-similarity score without choosing a chance-correction model, removing a source of ambiguity documented for AMI and ARI.
It avoids NMI's tendency to reward labelings with many clusters and ARI's distortion under asymmetric cluster-size distributions, so rankings of competing clusterings can change in settings where those biases operate.
In the second contact-tracing network, ResMI agrees with AMI and ARI in selecting $c=10$ communities, where RMI chooses too few and NMI too many; if this pattern generalizes, ResMI is a more reliable guide for choosing the number of communities.
Because the measure is defined entirely through mutual information and entropy, it remains interpretable as shared information between two random variables, which chance-corrected scores lose.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

An extension the paper leaves implicit is that the constant-baseline claim is tied to the uniform independent-label null model; deriving the closed-form expectation of ResMI under the fixed-cluster-size permutation model would delimit exactly when the baseline holds, and the $n=3$, sizes $(2,1)$ case suggests it does not hold there.
The pair-event formulation could transfer to overlapping or hierarchical clusterings by redefining the event 'same cluster' as 'share at least one community' or 'belong to a common nested block'; the paper does not test these variants.
Because ResMI depends only on four co-clustering probabilities, it may be computable in near-linear or quadratic time from the contingency table, making it a plausible direct objective for clustering algorithms; the paper mentions this direction but does not implement it.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here's the one thing you should know: the paper introduces a new clustering similarity measure, ResMI, defined as the normalized mutual information between two Bernoulli variables indicating whether a random pair of objects shares a label under each clustering. This is a clean, novel combination of pair counting and information theory, and it does fix the cluster-count bias that NMI has. The synthetic experiments are clearly described and the qualitative real-data analysis is reasonable.

The soft spot is the central theoretical claim. The abstract and Section II-C say ResMI satisfies the constant baseline property without chance correction. That only holds if the two Bernoulli variables are independent, which happens when labels are assigned to objects independently and uniformly. Under the permutation model used by AMI and ARI—where cluster sizes are fixed and labels are permuted—the shared random pair couples the two indicators. A concrete counterexample: for n=3 with a (2,1) partition, two independent uniform such partitions give expected ResMI ≈ 0.516, not 0. The paper's statement that "experimental results establish this result in generality" is not a proof; the n=1024 experiments only show the bias is numerically small in that setting.

There is also a typo in the definition of qf|G: it divides by C(|G|,2), but |G| counts pairs, so the correct normalizer is |G| (and C(1,2)=0, so the formula is undefined for the common case where a cluster has one pair). No code is provided, which makes the exact implementation hard to verify.

All that said, the core idea may still be useful. The measure behaves sensibly in the experiments and avoids the symmetry bias that hits ARI. But the paper overclaims the theoretical property. With a corrected definition and a clearly stated null model—one where the constant baseline actually holds, or a revised claim about approximate behavior—it could be a fine contribution.

Bottom line: worth sending to a serious referee, but the referee should be told to check the null model carefully and demand a fix to the formula. I probably wouldn't cite it in its current form.

Referee Report

3 major / 3 minor

Summary. The paper introduces ResMI, a clustering-similarity measure defined as the normalized mutual information between two co-membership indicators obtained by resampling a pair of objects without replacement. The authors claim that ResMI satisfies the constant baseline property without chance-correction terms, is model-independent, stays in [0,1], and avoids the cluster-count and symmetry biases of NMI, AMI, ARI, and RMI. These claims are supported by four synthetic experiments with n=1024 and by community-detection experiments on two contact-tracing networks.

Significance. If the central claims were correct, ResMI would be a practically attractive measure: it is interpretable in information-theoretic terms, bounded, and free of a user-specified null model. The paper also has useful experimental scaffolding, including comparisons with standard libraries and real network data. However, the main theoretical advantage advertised in the abstract and in Sec. II-C—exact constant baseline without chance correction—is not proven and is in fact false under the standard permutation model. The empirical results only show small finite-sample bias at n=1024 for one generative model. As a result, the paper's principal contribution, as stated, is not established.

major comments (3)

[Sec. II-C, Eq. (7)] The constant baseline claim is load-bearing and is false under the standard permutation model. In Eq. (7), X=1{f(Z1)=f(Z2)} and Y=1{g(Z1)=g(Z2)} are functions of the same random pair (Z1,Z2); independence of the random labelings f and g does not make X and Y independent. Concretely, for n=3, fix f to be the partition {12}|{3} and let g be drawn uniformly from the three partitions of [3] with block sizes (2,1). If g=f, ResMI=1 (probability 1/3). If g={13}|{2} or {23}|{1} (probability 2/3), then qf=qg=1/3, qf|G=0, and qf|Gc=1/2, so ResMI=(h_b(1/3)-2/3)/h_b(1/3)≈0.274. Hence E_g[ResMI(f,g)]≈0.516, not 0. Since ResMI is nonnegative, an exact constant baseline would require ResMI=0 on essentially the whole support; this counterexample shows it does not. The n=1024 simulations in Fig. 1(a) only show that the bias is numerically small in one large-n setting, and the sentence claiming that the experiments 'establish this result in generality' is not a proof.
[Sec. II-C, definition of qf|G] The definition of qf|G is inconsistent with G being a set of pairs. The printed expression normalizes by binom(|G|,2), but the conditional probability is the average over the pairs in G, so the denominator should be |G|; the same correction applies to qf|Gc. As written, the formula is undefined when |G|=1 and otherwise scales the conditional probability incorrectly, which materially changes the value of ResMI and compromises the reproducibility of the experiments.
[Sec. III, Fig. 1 and Table II] The experimental results are used to support the 'Constant Baseline ✓' entry for ResMI in Table II, but the experiments average over one particular generative process (random assignment to c clusters with n=1024) and do not establish an exact property of the measure. Table II should not list the constant baseline as an exact property unless a theorem is supplied; at most, the paper can claim low large-n baseline bias for the specific null models tested. The authors should either prove a precise asymptotic statement or remove the claim.

minor comments (3)

[Sec. II-A, Eq. (3)] The displayed formula for AMI is not the standard adjusted mutual information of Vinh et al., which corrects the mutual information I(f;g) rather than NMI; please reconcile the formula with the implementation in aricode used in the experiments.
[Sec. II-C, Eq. (7)] The behavior of ResMI is not specified when both H(1{f(Z1)=f(Z2)}) and H(1{g(Z1)=g(Z2)}) are zero; the paper should state a convention for this degenerate case.
[Sec. III, Fig. 1(c)] The claim that NMI and RMI 'fail to satisfy' the monotonicity property appears to be based on visual inspection of the plotted curves; a quantitative criterion or a statistical comparison would make the claim more precise.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: ResMI is a direct definition evaluated against external benchmarks; constant-baseline caveats are correctness issues, not self-referential reductions.

full rationale

The paper does not fit parameters to target results and then rename those fits as predictions; ResMI is introduced directly in Eq. (7) as a normalized mutual information between two Bernoulli variables derived from pair co-clustering indicators. Its claimed properties, including the constant baseline property, are supported by synthetic experiments against independently constructed labelings and by real-network comparisons with SCORE+ communities, not by a derivation whose output is assumed in its input. There are no load-bearing self-citations, no imported uniqueness theorem, and no ansatz smuggled in through citation; the cited works are standard methodology or datasets used for benchmarking. The reader's note that the constant-baseline claim may fail for small or unequal cluster sizes (e.g., n=3 with block sizes 2 and 1) is a mathematical/validity concern about the strength of the claim, not a circularity: an unsupported or false assertion is different from a derivation that reduces to its own inputs. Accordingly, the circularity score is 0.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

ResMI has no fitted parameters or invented entities. The key unstated assumption is the independence of the pair-co-membership indicators under the null, which is model-dependent and not proven.

assumptions (3)

standard math Standard definitions of mutual information and entropy (Eq. 1) are used throughout.
The paper builds ResMI on the standard information-theoretic quantities H and I.
domain assumption The pair (Z1,Z2) is sampled uniformly without replacement from [n].
This defines the probability model in Eq. (7).
ad hoc to paper The Bernoulli indicators for pair co-membership are independent under independent clusterings.
Required for the claimed constant baseline property; not generally true, especially under the permutation model.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Resampled Mutual Information for Clustering and Community Detection." pith.science (2026). https://pith.science/paper/DY4KSOTG

@misc{pith2026241203584,
  author       = {Pith},
  title        = {Pith review of: Resampled Mutual Information for Clustering and Community Detection},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DY4KSOTG}},
  note         = {Machine review of arXiv:2412.03584}
}

read the original abstract

We introduce resampled mutual information (ResMI), a novel measure of clustering similarity that combines insights from information theoretic and pair counting approaches to clustering and community detection. Similar to chance-corrected measures, ResMI satisfies the constant baseline property, but it has the advantages of not requiring adjustment terms and being fully interpretable in the language of information theory. Experiments on synthetic datasets demonstrate that ResMI is robust to common biases exhibited by existing measures, particularly in settings with high cluster counts and asymmetric cluster distributions. Additionally, we show that ResMI identifies meaningful community structures in two real contact tracing networks.

Figures

Figures reproduced from arXiv: 2412.03584 by the authors.

**Figure 2.** Similarity between ground truth and estimated community labels by [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗

**Figure 3.** (a) Ground truth and (b) estimated community labels (with [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: (a) Ground truth community labels, and estimated community labels [PITH_FULL_IMAGE:figures/full_fig_p005_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

[3]

Improved mutual infor- mation measure for clustering, classification, and community detection,

M. Newman, G. Cantwell, and J.-G. Young, “Improved mutual infor- mation measure for clustering, classification, and community detection,” Physical Review E , vol. 101, 2020

work page 2020
[1]

Information theoretic measures for clusterings comparison: Is a correction for chance necessary?

N. Vinh, J. Epps, and J. Bailey, “Information theoretic measures for clusterings comparison: Is a correction for chance necessary?” in Inter- national Conference on Machine Learning , 06 2009

work page 2009
[2]

Information theoretic measures for clusterings comparison: Vari- ants, properties, normalization and correction for chance,

——, “Information theoretic measures for clusterings comparison: Vari- ants, properties, normalization and correction for chance,” Journal of Machine Learning Research , vol. 11, 2010

work page 2010
[4]

Element-centric clustering comparison unifies overlaps and hierarchy,

A. J. Gates, I. B. Wood, W. P. Hetrick, and Y .-Y . Ahn, “Element-centric clustering comparison unifies overlaps and hierarchy,”Scientific Reports, vol. 9, 06 2019

work page 2019
[5]

Objective criteria for the evaluation of clustering meth- ods,

W. M. Rand, “Objective criteria for the evaluation of clustering meth- ods,” Journal of the American Statistical Association , vol. 66, 1971

work page 1971
[6]

Comparing partitions,

L. Hubert and P. Arabie, “Comparing partitions,” Journal of Classifica- tion, vol. 2, 12 1985

work page 1985
[7]

The impact of random models on clustering similarity,

A. J. Gates and Y .-Y . Ahn, “The impact of random models on clustering similarity,” Journal of Machine Learning Research , vol. 18, 2017

work page 2017
[8]

Understanding the adjusted rand index and other partition comparison indices based on counting object pairs,

M. Warrens and H. van der Hoef, “Understanding the adjusted rand index and other partition comparison indices based on counting object pairs,” Journal of Classification , vol. 39, 07 2022

work page 2022

Show all 18 references

[9]

Comparing clusterings—an information based distance,

M. Meil ˘a, “Comparing clusterings—an information based distance,” Journal of Multivariate Analysis , vol. 98, 2007

2007
[10]

Data on face-to-face contacts in an office building suggest a low-cost vaccination strategy based on community linkers,

M. G ´enois, C. L. Vestergaard, J. Fournet, A. Panisson, I. Bonmarin, and A. Barrat, “Data on face-to-face contacts in an office building suggest a low-cost vaccination strategy based on community linkers,” Network Science, vol. 3, 2015

2015
[11]

Can co-location be used as a proxy for face- to-face contacts?

M. G ´enois and A. Barrat, “Can co-location be used as a proxy for face- to-face contacts?” EPJ Data Science , vol. 7, 2017

2017
[12]

Robust data clustering,

L. Ana and A. Jain, “Robust data clustering,” in IEEE Computer Society Conference on Computer Vision and Pattern Recognition , vol. 2, 2003

2003
[13]

Comparing community structure identification,

L. Danon, J. Duch, A. Diaz-Guilera, and A. Arenas, “Comparing community structure identification,” Journal of Statistical Mechanics: Theory and Experiment , vol. 2005, 06 2005

2005
[14]

Proof of biased behavior of normal- ized mutual information,

A. Mahmoudi and D. Jemielniak, “Proof of biased behavior of normal- ized mutual information,” Scientific Reports, vol. 14, 04 2024

2024
[15]

Chiquet, A

P. Chiquet, A. Saade, and E. C ˆome, aricode: Efficient Computation of Standard Clustering Comparison Measures , 2018. [Online]. Available: https://cran.r-project.org/package=aricode

2018
[16]

G. K. Androulakis and I. Kalatzis, clustAnalytics: Cluster Validation via Statistical Analysis of Clustering Consistency, 2020. [Online]. Available: https://cran.r-project.org/package=clustAnalytics

2020
[17]

Improvements on score, especially for weak signals,

J. Jin, Z. Ke, and S. Luo, “Improvements on score, especially for weak signals,” Sankhya A, vol. 84, 03 2021

2021
[18]

Fast community detection by score,

J. Jin, “Fast community detection by score,” The Annals of Statistics , vol. 43, 2015

2015

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [3]

Improved mutual infor- mation measure for clustering, classification, and community detection,

M. Newman, G. Cantwell, and J.-G. Young, “Improved mutual infor- mation measure for clustering, classification, and community detection,” Physical Review E , vol. 101, 2020

work page 2020

[2] [1]

Information theoretic measures for clusterings comparison: Is a correction for chance necessary?

N. Vinh, J. Epps, and J. Bailey, “Information theoretic measures for clusterings comparison: Is a correction for chance necessary?” in Inter- national Conference on Machine Learning , 06 2009

work page 2009

[3] [2]

Information theoretic measures for clusterings comparison: Vari- ants, properties, normalization and correction for chance,

——, “Information theoretic measures for clusterings comparison: Vari- ants, properties, normalization and correction for chance,” Journal of Machine Learning Research , vol. 11, 2010

work page 2010

[4] [4]

Element-centric clustering comparison unifies overlaps and hierarchy,

A. J. Gates, I. B. Wood, W. P. Hetrick, and Y .-Y . Ahn, “Element-centric clustering comparison unifies overlaps and hierarchy,”Scientific Reports, vol. 9, 06 2019

work page 2019

[5] [5]

Objective criteria for the evaluation of clustering meth- ods,

W. M. Rand, “Objective criteria for the evaluation of clustering meth- ods,” Journal of the American Statistical Association , vol. 66, 1971

work page 1971

[6] [6]

Comparing partitions,

L. Hubert and P. Arabie, “Comparing partitions,” Journal of Classifica- tion, vol. 2, 12 1985

work page 1985

[7] [7]

The impact of random models on clustering similarity,

A. J. Gates and Y .-Y . Ahn, “The impact of random models on clustering similarity,” Journal of Machine Learning Research , vol. 18, 2017

work page 2017

[8] [8]

Understanding the adjusted rand index and other partition comparison indices based on counting object pairs,

M. Warrens and H. van der Hoef, “Understanding the adjusted rand index and other partition comparison indices based on counting object pairs,” Journal of Classification , vol. 39, 07 2022

work page 2022