Flexible Models for Microclustering with Application to Entity Resolution
Most generative models for clustering implicitly assume that the number of data points in each cluster grows linearly with the total number of data points. Finite mixture models, Dirichlet process mixture models, and Pitman-Yor process mixture models make this assumption, as do all other infinitely exchangeable clustering models. However, for some applications, this assumption is inappropriate. For example, when performing entity resolution, the size of each cluster should be unrelated to the size of the data set, and each cluster should contain a negligible fraction of the total number of data points. These applications require models that yield clusters whose sizes grow sublinearly with the size of the data set. We address this requirement by defining the microclustering property and introducing a new class of models that can exhibit this property. We compare models within this class to two commonly used clustering models using four entity-resolution data sets.
The paper proposes a distribution over partitions of integers that supports micro-clustering. Specifically, the paper shows that that for existing infinitely exchangeable clustering models, such as Dirichlet Process (DP) and Pitman-Yor Process (PYP) mixture models, the cluster sizes grow linearly with the number of data points N. For applications such as entity resolution, the paper defines the micro-clustering property, where the ratio of the cluster size and number of data points N goes to 0 as N goes to infinity. The paper proposes a general distribution framework over partitions of integers that satisfies this micro-clustering property. This is done by first sampling the number of clusters from a distribution with positive integers as support, and then explicitly sampling each of the cluster sizes from a distribution over cluster sizes again with positive integers as support. This model achieves the micro-clustering property by sacrificing consistency of marginals, while preserving exchangeability. The paper then proposes two specific instances of this framework. The first uses the negative binomial for both distributions. The second uses a Dirichlet with an infinite dimensional base distribution for the distribution over cluster sizes to provide more flexibility for large datasets. Reseating algorithms similar to the Chinese Restaurant Process and the Pitman-Yor Process are provided for both models. Making use of the exchangeability property, sampling based algorithms are used for inference in both models. Experiments over 4 semi-synthetic datasets are used to illustrate that the proposed models outperform models without the micro-clustering property (DP and PYP) for the entity resolution task.
The following are the main strengths of the paper. + It points out and defines an important property of cluster sizes that existing infinitely exchangeable clustering models do not satisfy. There could be many applications, including and not limited to entity resolution, that require this property to be satisfied. + It proposes a framework for defining infinitely exchangeable clustering models that satisfy this micro-clustering property, and analyzes why the DP mixture model is an unsatisfactory instance of this class. It then proposes two specific and interesting instances of this class using specific distributions for the number of clusters and cluster sizes and derives reseating algorithms for these instances. + Detailed experimental results over semi-synthetic data illustrate usefulness of the proposed models to some extent for the entity resolution task. Experiments in the supplement show that draws from the proposed model satisfy the micro-clustering property. (This should be moved to the main paper.)  But the paper also has certain deficiencies, some of which are probably fixable. - The paper points out towards the beginning that it preserves exchangeability and sacrifices consistency of the marginal distributions to achieve the micro-clustering property. While I can see the benefits of preserving exchangeability (e.g. in designing sampling based inference algorithms), the price of sacrificing consistency is not clear. The paper has a vague statement in line 109: "It does not produce an exact sample if used to incrementally construct a partition". What does this mean? Is this related to the consistency issue? - While the paper has empirical comparisons with the Pitman-Yor Process, there is no theoretical analysis of the differences in the reseating algorithms. I can understand that the goal is to have significantly heavier tails in the cluster size distribution compared to the DP / CRP. The PYP addresses this by making the probability of picking a new table proportional to the current number of clusters. The reseating algorithm for both proposed models looks similar. Which aspect of the proposed reseating helps it to satisfy the micro-clustering property while the PYP does not? - The paper also does not satisfactorily analyze the relationship between the two proposed models. The Negative Binomial in the first model is replaced by a Dirichlet with an infinite dimensional base distribution in the second. In the second case, I could think of the cluster size probabilities as drawn from a GEM / Poisson-Dirichlet with two parameters. Would this also become too restricted? Or is the difference due to two different priors over infinite dimensional multinomial parameters, e.g. Negative Binomial and GEM?  - Early on, the paper mentions related work (the Uniform Process) that achieves the same goal differently: by sacrificing exchangeability instead of consistency. This work is never mentioned later in the paper. Some discussion of this earlier paper is necessary to understand the contributions of the proposed framework. - The experiments are not convincing enough for appreciating the usefulness of the proposed models for the entity resolution task. Judging by the error rates for all the models, the task for the first two datasets seem too simple for these datasets to be significant. For the other two datasets (which the paper claims are too hard), the two baseline models seem to be doing better.  Some less important comments: - Where is alpha in the reseating algorithm in lines 131-133? - If the authors feel that the Chaperones algorithm is significant, they need to describe it at least at a high level in the main paper. Mentioning it just by name in the main paper is not helpful. - The flow of the paper could be changed for better understanding. Lines 112-115 and 134-139 could be moved to the inference section, and lines 116-118 and 140-144 could be moved to the experiments section.  - The authors should reconsider the name of the proposed model. They should at least change it to the Flexible Micro-clustering Model instead of the Flexible Model for Micro-clustering model.  - In Eqn 3 and line 85, |C|_N should be |C_N|. In line 84, cluster |c| should be cluster c. - Eqn 5 should have a,q in the conditional. Eqn 7 should have a,q,alpha in the conditional. - What does "K is one observation" in line 122 mean? - In Eqn 11, please explain that theta_lk is the lth feature for the kth partition. - (The partition features of) One synthetic dataset can be imagined as one draw from (the entity features of) the corresponding real dataset. Are experimental results reported over a single random synthetic dataset or averaged over multiple samples? Though the noise parameters may be set to achieve low noise in expectation, it is possible to get high noise in a single random draw.  - What is the difference between the two Syria datasets?  - How are the error rates defined accounting for the label permutation issue? Are these defined over pairs of data points? - Some sentences contain unnecessary repetitions, e.g. in lines 150 and 214-216