{'fraction_non_alphanumeric': 0.032376298106292, 'fraction_numerical': 0.013477397678680513, 'mean_word_length': 4.607578676942839, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Bounding and Comparing Methods for Correlation Clustering Beyond ILP

We evaluate several heuristic solvers for correlation clustering, the NP-hard problem of partitioning a dataset given pairwise affinities between all points. We experiment on two practical tasks, document clustering and chat disentanglement, to which ILP does not scale. On these datasets, we show that the clustering objective often, but not always, correlates with external metrics, and that local search always improves over greedy solutions. We use semi-definite programming (SDP) to provide a tighter bound, showing that simple algorithms are already close to optimality.


Introduction
Correlation clustering is a powerful technique for discovering structure in data. It operates on the pairwise relationships between datapoints, partitioning the graph to minimize the number of unrelated pairs that are clustered together, plus the number of related pairs that are separated. Unfortunately, this minimization problem is NP-hard (Ailon et al., 2008). Practical work has adopted one of three strategies for solving it. For a few specific tasks, one can restrict the problem so that it is efficiently solvable. In most cases, however, this is impossible. Integer linear programming (ILP) can be used to solve the general problem optimally, but only when the number of data points is small. Beyond a few hundred points, the only available solutions are heuristic or approximate.
In this paper, we evaluate a variety of solutions for correlation clustering on two realistic NLP tasks, text topic clustering and chat disentanglement, where typical datasets are too large for ILP to find a solution. We show, as in previous work on consensus clustering (Goder and Filkov, 2008), that local search can improve the solutions found by commonly-used methods. We investigate the relationship between the clustering objective and external evaluation metrics such as F-score and one-toone overlap, showing that optimizing the objective is usually a reasonable aim, but that other measurements like number of clusters found should sometimes be used to reject pathological solutions. We prove that the best heuristics are quite close to optimal, using the first implementation of the semidefinite programming (SDP) relaxation to provide tighter bounds.
The specific algorithms we investigate are, of course, only a subset of the large number of possible solutions, or even of those proposed in the literature. We chose to test a few common, efficient algorithms that are easily implemented. Our use of a good bounding strategy means that we do not need to perform an exhaustive comparison; we will show that, though the methods we describe are not perfect, the remaining improvements possible with any algorithm are relatively small.

Previous Work
Correlation clustering was first introduced by Ben- Dor et al. (1999) to cluster gene expression patterns. The correlation clustering approach has several strengths. It does not require users to specify a parametric form for the clusters, nor to pick the number of clusters. Unlike fully unsupervised clus-tering methods, it can use training data to optimize the pairwise classifier, but unlike classification, it does not require samples from the specific clusters found in the test data. For instance, it can use messages about cars to learn a similarity function that can then be applied to messages about atheism.
Correlation clustering is a standard method for coreference resolution. It was introduced to the area by Soon et al. (2001), who describe the firstlink heuristic method for solving it. Ng and Cardie (2002) extend this work with better features, and develop the best-link heuristic, which finds better solutions. McCallum and Wellner (2004) explicitly describe the problem as correlation clustering and use an approximate technique (Bansal et al., 2004) to enforce transitivity. Recently Finkel and Manning (2008) show that the optimal ILP solution outperforms the first and best-link methods. Cohen and Richman (2002) experiment with various heuristic solutions for the cross-document coreference task of grouping references to named entities.
Finally, correlation clustering has proven useful in several discourse tasks. Barzilay and Lapata (2006) use it for content aggregation in a generation system. In Malioutov and Barzilay (2006), it is used for topic segmentation-since segments must be contiguous, the problem can be solved in polynomial time. Elsner and Charniak (2008) address the related problem of disentanglement (which we explore in Section 5.3), doing inference with the voting greedy algorithm. Bertolacci and Wirth (2007), Goder and Filkov (2008) and Gionis et al. (2007) conduct experiments on the closely related problem of consensus clustering, often solved by reduction to correlation clustering. The input to this problem is a set of clusterings; the output is a "median" clustering which minimizes the sum of (Rand) distance to the inputs. Although these papers investigate some of the same algorithms we use, they use an unrealistic lower bound, and so cannot convincingly evaluate absolute performance. Gionis et al. (2007) give an external evaluation on some UCI datasets, but this is somewhat unconvincing since their metric, the impurity index, which is essentially precision ignoring recall, gives a perfect score to the all-singletons clustering. The other two papers are based on objective values, not external metrics. 1 A variety of approximation algorithms for correlation clustering with worst-case theoretical guarantees have been proposed: (Bansal et al., 2004;Ailon et al., 2008;Demaine et al., 2006;Charikar et al., 2005;Giotis and Guruswami, 2006). Researchers including (Ben-Dor et al., 1999;Joachims and Hopcroft, 2005;Mathieu and Schudy, 2008) study correlation clustering theoretically when the input is generated by randomly perturbing an unknown ground truth clustering.

Algorithms
We begin with some notation and a formal definition of the problem. Our input is a complete, undirected graph G with n nodes; each edge in the graph has a probability p ij reflecting our belief as to whether nodes i and j come from the same cluster. Our goal is to find a clustering, defined as a new graph G ′ with edges x ij ∈ {0, 1}, where if x ij = 1, nodes i and j are assigned to the same cluster. To make this consistent, the edges must define an equivalence relationship: x ii = 1 and x ij = x jk = 1 implies Our objective is to find a clustering as consistent as possible with our beliefs-edges with high probability should not cross cluster boundaries, and edges with low probability should. We define w + ij as the cost of cutting an edge whose probability is p ij and w − ij as the cost of keeping it. Mathematically, this objective can be written (Ailon et al., 2008;Finkel and Manning, 2008) as: There are two plausible definitions for the costs w + and w − , both of which have gained some support in the literature. We can take w + ij = p ij and w − ij = 1 − p ij (additive weights) as in (Ailon et al., 2008) and others, or w + ij = log(p ij ), w − ij = log(1 − p ij ) (logarithmic weights) as in (Finkel and Manning, 2008). The logarithmic scheme has a tenuous mathematical justification, since it selects a maximumlikelihood clustering under the assumption that the p ij are independent and identically distributed given the status of the edge ij in the true clustering. If we obtain the p ij using a classifier, however, this assumption is obviously untrue-some nodes will be easy to link, while others will be hard-so we evaluate the different weighting schemes empirically.

Greedy Methods
We use four greedy methods drawn from the literature; they are both fast and easy to implement. All of them make decisions based on the net weight w ± ij = w + ij − w − ij . These algorithms step through the nodes of the graph according to a permutation π. We try 100 random permutations for each algorithm and report the run which attains the best objective value (typically this is slightly better than the average run; we discuss this more in the experimental sections). To simplify the pseudocode we label the vertices 1, 2, . . . n in the order specified by π. After this relabeling π(i) = i so π need not appear explicitly in the algorithms.
Three of the algorithms are given in Figure 1. All three algorithms start with the empty clustering and add the vertices one by one. The BEST algorithm adds each vertex i to the cluster with the strongest w ± connecting to i, or to a new singleton if none of the w ± are positive. The FIRST algorithm adds each vertex i to the cluster containing the most recently considered vertex j with w ± ij > 0. The VOTE algorithm adds each vertex to the cluster that minimizes the correlation clustering objective, i.e. to the cluster maximizing the total net weight or to a singleton if no total is positive. Ailon et al. (2008) introduced the PIVOT algorithm, given in Figure 2, and proved that it is a 5approximation if w + ij + w − ij = 1 for all i, j and π is chosen randomly. Unlike BEST, VOTE and FIRST, which build clusters vertex by vertex, the PIVOT algorithm creates each new cluster in its final form. This algorithm repeatedly takes an unclustered pivot vertex and creates a new cluster containing that vertex and all unclustered neighbors with positive weight.

Local Search
We use the straightforward local search previously used by Gionis et al. (2007) and Goder and Filkov k ← 0 // number of clusters created so far  (2008). The allowed one element moves consist of removing one vertex from a cluster and either moving it to another cluster or to a new singleton cluster. The best one element move (BOEM) algorithm repeatedly makes the most profitable best one element move until a local optimum is reached. Simulated Annealing (SA) makes a random singleelement move, with probability related to the difference in objective it causes and the current temperature. Our annealing schedule is exponential and designed to attempt 2000n moves for n nodes. We initialize the local search either with all nodes clustered together, or at the clustering produced by one of our greedy algorithms (in our tables, the latter is written, eg. PIVOT/BOEM, if the greedy algorithm is PIVOT).

Bounding with SDP
Although comparing different algorithms to one another gives a good picture of relative performance, it is natural to wonder how well they do in an absolute sense-how they compare to the optimal solution.
For very small instances, we can actually find the optimum using ILP, but since this does not scale beyond a few hundred points (see Section 5.1), for realistic instances we must instead bound the optimal value. Bounds are usually obtained by solving a relaxation of the original problem: a simpler problem with the same objective but fewer constraints. The bound used in previous work (Goder and Filkov, 2008;Gionis et al., 2007;Bertolacci and Wirth, 2007), which we call the trivial bound, is obtained by ignoring the transitivity constraints entirely. To optimize, we link (x ij = 1) all the pairs where w + ij is larger than w − ij ; since this solution is quite far from being a clustering, the bound tends not to be very tight.
To get a better idea of how good a real clustering can be, we use a semi-definite programming (SDP) relaxation to provide a better bound. Here we motivate and define this relaxation.
One can picture a clustering geometrically by associating cluster c with the standard basis vector e c = (0, 0, . . . , 0, This gives a nice geometric picture of a clustering, with objects i and j in the same cluster if and only if r i = r j . Note that the dot product r i • r j is 1 if i and j are in the same cluster and 0 otherwise. These ideas yield a simple reformulation of the correlation clustering problem: To get an efficiently computable lower-bound we relax the constraints that the r i s are standard basis vectors, replacing them with two sets of constraints: r i • r i = 1 for all i and r i • r j ≥ 0 for all i, j. Since the r i only appear as dot products, we can rewrite in terms of x ij = r i • r j . However, we must now constrain the x ij to be the dot products of some set of vectors in R n . This is true if and only if the symmetric matrix X = {x ij } ij is positive semi-definite. We now have the standard semidefinite programming (SDP) relaxation of correlation clustering (e.g. (Charikar et al., 2005;Mathieu and Schudy, 2008)): This SDP has been studied theoretically by a number of authors; we mention just two here. Charikar et al. (2005) give an approximation algorithm based on rounding the SDP which is a 0.7664 approximation for the problem of maximizing agreements. Mathieu and Schudy (2008) show that if the input is generated by corrupting the edges of a ground truth clustering B independently, then the SDP relaxation value is within an additive O(n √ n) of the optimum clustering. They further show that using the PIVOT algorithm to round the SDP yields a clustering with value at most O(n √ n) more than optimal.

Scalability
Using synthetic data, we investigate the scalability of the linear programming solver and SDP bound. To find optimal solutions, we pass the complete ILP 2 to CPLEX. This is reasonable for 100 points and solvable for 200; beyond this point it cannot be solved due to memory exhaustion. As noted below, despite our inability to compute the LP bound on large instances, we can sometimes prove that they must be worse than SDP bounds, so we do not investigate LP-solving techniques further.
The SDP has fewer constraints than the ILP (O(n 2 ) vs O(n 3 )), but this is still more than many SDP solvers can handle. For our experiments we used one of the few SDP solvers that can handle such a large number of constraints: Christoph Helmberg's ConicBundle library (Helmberg, 2009;Helmberg, 2000). This solver can handle several thousand datapoints. It produces loose lower-bounds (off by a few percent) quickly but converges to optimality quite slowly; we err on the side of inefficiency by running for up to 60 hours. Of course, the SDP solver is only necessary to bound algorithm performance; our solvers themselves scale much better.

Twenty Newsgroups
In this section, we test our approach on a typical benchmark clustering dataset, 20 Newsgroups, which contains posts from a variety of Usenet newsgroups such as rec.motorcycles and alt.atheism. Since our bounding technique does not scale to the full dataset, we restrict our attention to a subsample of 100 messages 3 from each newsgroup for a total of 2000-still a realistically large-scale problem. Our goal is to cluster messages by their newsgroup of origin. We conduct experiments by holding out four newsgroups as a training set, learning a pairwise classifier, and applying it to the remaining 16 newsgroups to form our affinity matrix. 4 Our pairwise classifier uses three types of features previously found useful in document clustering. First, we bucket all words 5 by their log document frequency (for an overview of TF-IDF see (Joachims, 1997)). For a pair of messages, we create a feature for each bucket whose value is the proportion of shared words in that bucket. Secondly, we run LSA (Deerwester et al., 1990) on the TF-IDF matrix for the dataset, and use the cosine distance between each message pair as a feature. Finally, we use the same type of shared words features for terms in message subjects. We make a training instance for each pair of documents in the training set and learn via logistic regression.
The classifier has an average F-score of 29% and an accuracy of 88%-not particularly good. We should emphasize that the clustering task for 20 newsgroups is much harder than the more common classification task-since our training set is entirely disjoint with the testing set, we can only learn weights on feature categories, not term weights. Our aim is to create realistic-looking data on which to test our clustering methods, not to motivate correlation clustering as a solution to this specific problem. In fact, Zhong and Ghosh (2003) report better results using generative models.
We evaluate our clusterings using three different metrics (see Meila (2007) for an overview of clustering metrics). The Rand measure counts the number of pairs of points for which the proposed clustering agrees with ground truth. This is the metric which is mathematically closest to the objective. However, since most points are in different clusters, any solution with small clusters tends to get a high score. Therefore we also report the more sensitive F-score with respect to the minority ("same cluster") class.
We also report the one-to-one score, which measures accuracy over single points. For this metric, we calculate a maximum-weight matching between proposed clusters and ground-truth clusters, then report the overlap between the two. When presenting objective values, we locate them within the range between the trivial lower bound dis-cussed in Section 4 and the objective value of the singletons clustering (x ij = 0, i = j). On this scale, lower is better; 0% corresponds to the trivial bound and 100% corresponds to the singletons clustering. It is possible to find values greater than 100%, since some particularly bad clusterings have objectives worse than the singletons clustering. Plainly, however, real clusterings will not have values as low as 0%, since the trivial bound is so unrealistic.
Our results are shown in Table 1. The best results are obtained using logarithmic weights with VOTE followed by BOEM; reasonable results are also found using additive weights, and annealing, VOTE or PIVOT followed by BOEM. On its own, the best greedy scheme is VOTE, but all of them are substantially improved by BOEM. First-link is by far the worst. Our use of the SDP lower bound rather than the trivial lower-bound of 0% reduces the gap between the best clustering and the lower bound by over a factor of ten. It is easy to show that the LP relaxation can obtain a bound of at most 50% 6 -the SDP beats the LP in both runtime and quality! We analyze the correlation between objective values and metric values, averaging Kendall's tau 7 over the four datasets (Table 2). Over the entire dataset, correlations are generally good (large and negative), showing that optimizing the objective is indeed a useful way to find good results. We also examine correlations for the solutions with objective values within the top 10%. Here the correlation is much poorer; selecting the solution with the best objective value will not necessarily optimize the metric, although the correspondence is slightly better for the log-weights scheme. The correlations do exist, however, and so the solution with the best objective value is typically slightly better than the median.
In Figure 3, we show the distribution of one-toone scores obtained (for one specific dataset) by the best solvers. From this diagram, it is clear that logweights and VOTE/BOEM usually obtain the best scores for this metric, since the median is higher than other solvers' upper quartile scores. All solvers have quite high variance, with a range of about 2% between quartiles and 4% overall. We omit the F-6 The solution xij = 1 2 1 1`w − ij > w + ij´f or i < j is feasible in the LP. 7 The standard Pearson correlation coefficient is less robust to outliers, which causes problems for this data.  score plot, which is similar, for space reasons.

Chat Disentanglement
In the disentanglement task, we examine data from a shared discussion group where many conversations are occurring simultaneously. The task is to partition the utterances into a set of conversations. This task differs from newsgroup clustering in that data points (utterances) have an inherent linear order. Ordering is typical in discourse tasks including topic segmentation and coreference resolution.
We use the annotated dataset and pairwise classi-fier made available by Elsner and Charniak (2008); 8 this study represents a competitive baseline, although more recently Wang and Oard (2009) have improved it. Since this classifier is ineffective at linking utterances more than 129 seconds apart, we treat all decisions for such utterances as abstentions, p = .5. For utterance pairs on which it does make a decision, the classifier has a reported accuracy of 75% with an F-score of 71%. As in previous work, we run experiments on the 800-utterance test set and average metrics over 6 test annotations. We evaluate using the three metrics reported by previous work. Two node-counting metrics measure global accuracy: one-to-one match as explained above, and Shen's F (Shen et al., 2006): Here i is a gold conversation with size n i and j is a proposed conversation with size n j , sharing n ij utterances; F (i, j) is the harmonic mean of precision ( n ij n j ) and recall ( n ij n i ). A third metric, the local agreement, counts edgewise agreement for pairs of nearby utterances, where nearby means "within three utterances." In this dataset, the SDP is a more moderate improvement over the trivial lower bound, reducing the gap between the best clustering and best lower bound by a factor of about 3 ( Table 3).
Optimization of the objective does not correspond to improvements in the global metrics (Table 3); for instance, the best objectives are attained with FIRST/BOEM, but VOTE/BOEM yields better oneto-one and F scores. Correlation between the objective and these global metrics is extremely weak ( Table 5). The local metric is somewhat correlated.
Local search does improve metric results for each particular greedy algorithm. For instance, when BOEM is added to VOTE (with log weights), oneto-one increases from 44% to 46%, local from 72% to 73% and F from 48% to 50%. This represents a moderate improvement on the inference scheme described in Elsner and Charniak (2008). They use voting with additive weights, but rather than performing multiple runs over random permutations, they process utterances in the order they occur. (We experimented with processing in order; the results are unclear, but there is a slight trend toward worse performance, as in this case.) Their results (also 8 Downloaded from cs.brown.edu/∼melsner shown in the table) are 41% one-to-one, 73% local and .44% F-score. 9 Our improvement on the global metrics (12% relative improvement in one-to-one, 13% in F-score) is modest, but was achieved with better inference on exactly the same input.
Since the objective function fails to distinguish good solutions from bad ones, we examine the types of solutions found by different methods in the hope of explaining why some perform better than others. In this setting, some methods (notably local search run on its own or from a poor starting point) find far fewer clusters than others (Table 4; log weights not shown but similar to additive). Since the classifier abstains for utterances more than 129 seconds apart, the objective is unaffected if very distant utterances are linked on the basis of little or no evidence; this is presumably how such large clusters form. (This raises the question of whether abstentions should be given weaker links with p < .5. We leave this for future work.) Algorithms which find reasonable numbers of clusters (VOTE, PIVOT, BEST and local searches based on these) all achieve good metric scores, although there is still no reliable way to find the best solution among this set of methods.

Conclusions
It is clear from these results that heuristic methods can provide good correlation clustering solutions on datasets far too large for ILP to scale. The particular solver chosen 10 has a substantial impact on the quality of results obtained, in terms of external metrics as well as objective value.
For general problems, our recommendation is to use log weights and run VOTE/BOEM. This algorithm is fast, achieves good objective values, and yields good metric scores on our datasets. Although objective values are usually only weakly correlated with metrics, our results suggest that slightly better scores can be obtained by running the algorithm many times and returning the solution with the best objective. This may be worth trying even when the datapoints are inherently ordered, as in chat. 9 The F-score metric is not used in Elsner and Charniak (2008); we compute it ourselves on the result produced by their software. 10 Our C++ correlation clustering software and SDP bounding package are available for download from cs.brown.edu/∼melsner.  Table 3: Score of the solution with best objective found by each solver on the chat test dataset, averaged over 6 annotations, sorted by objective.
Whatever algorithm is used to provide an initial solution, we advise the use of local search as a postprocess. BOEM always improves both objective and metric values over its starting point.
The objective value is not always sufficient to select a good solution (as in the chat dataset). If possible, experimenters should check statistics like the number of clusters found to make sure they conform roughly to expectations. Algorithms that find far too many or too few clusters, regardless of objective, are unlikely to be useful. This type of problem can be especially dangerous if the pairwise classifier abstains for many pairs of points. SDP provides much tighter bounds than the trivial bound used in previous work, although how much   tighter varies with dataset (about 12 times smaller for newsgroups, 3 times for chat). This bound can be used to evaluate the absolute performance of our solvers; the VOTE/BOEM solver whose use we recommend is within about 5% of optimality. Some of this 5% represents the difference between the bound and optimality; the rest is the difference between the optimum and the solution found. If the bound were exactly optimal, we could expect a significant improvement on our best results, but not a very large one-especially since correlation between objective and metric values grows weaker for the best solutions. While it might be useful to investigate more sophisticated local searches in an attempt to close the gap, we do not view this as a priority.