Error bounds for correlation clustering

Thorsten Joachims, John E. Hopcroft

Abstract

This paper presents a learning theoretical analysis of correlation clustering (Bansal et al., 2002). In particular, we give bounds on the error with which correlation clustering recovers the correct partition in a planted partition model (Condon & Karp, 2001; McSherry, 2001). Using these bounds, we analyze how the accuracy of correlation clustering scales with the number of clusters and the sparsity of the graph. We also propose a statistical test that analyzes the significance of the clustering found by correlation clustering.
BibTeX
@inproceedings{joachims2005error,
  author = {Thorsten Joachims and John E. Hopcroft},
  title = {{Error bounds for correlation clustering}},
  booktitle = {International Conference on Machine Learning},
  year = {2005},
  doi = {10.1145/1102351.1102400},
}

Loading related content...

Figure