Source-linked AI summary
Normalized Mutual Information to evaluate overlapping community finding algorithms
Aaron F. McDaid, Derek Greene, Neil Hurley
TL;DR
Accurate evaluation of overlapping community-finding requires normalized measures for comparing true and detected covers. The paper analyzes a popular mutual-information measure, identifies unintuitive behavior, and proposes conventional normalization that produces more intuitive results.
Problem
Overlapping community-finding needs quantitative measures for comparing true and detected covers, but the popular NMILF K measure can overestimate similarity.
Method
The authors analyze NMILF K's normalization and replace its normalization steps with a conventional normalization based closely on the original measure.
Results
0.5 is the NMILF K score when Y has only one community, while NMImax rises linearly from 0 to 1 as Y's community count increases.
Takeaways & Limitations
Conventional normalization can produce more intuitive behavior for normalized mutual-information comparison of overlapping covers.
Abstract
from arXiv · showhide
Given the increasing popularity of algorithms for overlapping clustering, in particular in social network analysis, quantitative measures are needed to measure the accuracy of a method. Given a set of true clusters, and the set of clusters found by an algorithm, these sets of clusters must be compared to see how similar or different the sets are. A normalized measure is desirable in many contexts, for example assigning a value of 0 where the two sets are totally dissimilar, and 1 where they are identical. A measure based on normalized mutual information, [1], has recently become popular. We demonstrate unintuitive behaviour of this measure, and show how this can be corrected by using a more conventional normalization. We compare the results to that of other measures, such as the Omega index [2].
A C++ implementation is available online. 1
Overlapping community covers allow nodes to belong to multiple or no clusters, requiring measures that compare such covers. The Omega index compares covers using shared-cluster counts across node pairs and corrects for chance.
- In overlapping clustering, a node may belong to multiple communities or none, and the resulting cluster set is called a cover.
- The Omega index compares two covers by checking whether node pairs have identical shared-cluster counts.
- Omega reports the proportion of node pairs with matching shared-cluster counts, subject to a correction for chance.
I. MUTUAL INFORMATION
The paper extends mutual-information comparison to overlapping covers by matching cluster-membership vectors and aggregating their information differences. It retains a restriction against counting negatively correlated complements as informative while preparing a differently normalized measure.
- The mutual-information measure extends comparison from disjoint clusterings to covers and is used for community-finding algorithms.
- Each cover is represented as a node-by-cluster membership matrix, with binary entries indicating whether a node belongs to a cluster.
- The vector-level information calculation distinguishes agreement patterns using counts of jointly present, jointly absent, and mismatched memberships.
- Cluster pairs are compared through binary membership vectors, and each vector in X is matched to its best match in Y before summation.
II. USEFUL IDENTITIES
The section reviews mutual-information identities and contrasts the non-standard normalization used by NMILF K with the paper’s conventional alternative.
- The two theoretical definitions of mutual information should agree, but approximation in equation (3) can make them differ.
- Mutual information and variation of information partition total information as H(X, Y) = H(X|Y) + I(X : Y) + H(Y|X).
- The paper averages the two mutual-information definitions because the approximation can produce different values.
- NMILF K uses a non-standard normalization of variation of information rather than dividing by a conventional upper-bound quantity.
- The proposed alternative removes NMILF K’s normalization steps and uses a more conventional normalization form.
III. UNINTUITIVE BEHAVIOUR
The paper identifies cases where NMILF K reports moderate similarity despite intuitively dissimilar covers. These cases motivate replacing its normalization with a conventional alternative.
- NMILF K can overestimate similarity when one cover contains far more clusters than the other.
- With one matching cluster in Y and many clusters in X, NMILF K is at least 0.5 instead of the intuitive value of approximately 1/KX.The zero conditional entropy H(Y|X) contributes 0.5 to the score.
- A power-set cover contains every nonempty subset of n objects, producing 2^n − 1 clusters.
- For the power-set example, every cluster in X has a perfect match, yielding H(X|p(n)) = 0 and an NMILF K score slightly above 0.5.
- In both examples, the intuitive similarity score should be close to 0, but NMILF K gives a score slightly above 0.5.
- Removing NMILF K’s normalization and using a conventional strategy produces more intuitive behaviour.
IV. NORMALIZATION
The paper explains NMILF K’s failure through its normalization when covers differ greatly in complexity, then motivates a conventional normalized mutual-information alternative.
- As more communities are found, NMILF K and NMImax scores increase; the proposed measure instead gives a small value when few communities are found.
- Normalization typically divides an absolute quantity by an upper bound, producing a value between zero and one.
- Vinh et al. provide five possible normalization expressions, including one based on max(H(X), H(Y)).
- The paper uses normalized mutual information corresponding to a distance convention where zero means perfect similarity and one means dissimilarity.
- The NMILF K problem arises when one cover has many more clusters than the other, making one information circle much larger than the other.
- When the overlap nearly fills the smaller information circle, one term becomes small and drives NMILF K toward 0.5.
V. EVALUATION
A controlled experiment increases the number of perfectly copied communities in Y from 1 to 20 while X remains fixed. The conventional normalization gives an intuitive 0-to-1 progression, whereas NMILF K reports 0.5 when only one community is found and both measures reach 1.0 for identical covers.
- Experimental setup: The experiment fixes X as 20 non-overlapping communities and increases Y from 1 to 20 copied communities.Each community contains 10 of the 200 nodes, and Y contains an increasing subset of X.
- Results: 1.0 is the NMI reported by both measures when all 20 copied communities are used and X equals Y.At this endpoint, the covers are identical.
- Results: The proposed NMImax increases linearly from 0 to 1 as the number of communities in Y increases.The paper characterizes this progression as intuitive.
VI. CONCLUSION
The paper identifies unintuitive behavior in the normalized mutual information measure proposed by Lancichinetti et al. and uses a simple experiment to demonstrate a more intuitive alternative. It argues that conventional normalization provides the most intuitive normalized-mutual-information measure among several possible cover-similarity measures.
- Findings: The paper identifies unintuitive behavior in the normalized mutual information measure proposed by.A simple experiment confirms that behavior and demonstrates the alternative.
- Evaluation: A simple experiment confirms the unintuitive behavior and demonstrates more intuitive behavior under the proposed measure.The experiment is presented as evidence for the paper's correction.
- Conclusion: Among several normalized measures for cover similarity, the authors suggest their measure is the most intuitive definition based on normalized mutual information.They note that no unique evaluation criteria determine the best measure.