A Non-Convex Optimization Approach to Correlation Clustering

Erik Thiel, Morteza Haghir Chehreghani, Devdatt P. Dubhashi

AAAI 2019 pp. 5159-5166

doi:10.1609/AAAI.V33I01.33015159 /aaai/2019/thiel2019aaai-non/

Abstract

We develop a non-convex optimization approach to correlation clustering using the Frank-Wolfe (FW) framework. We show that the basic approach leads to a simple and natural local search algorithm with guaranteed convergence. This algorithm already beats alternative algorithms by substantial margins in both running time and quality of the clustering. Using ideas from FW algorithms, we develop subsampling and variance reduction paradigms for this approach. This yields both a practical improvement of the algorithm and some interesting further directions to investigate. We demonstrate the performance on both synthetic and real world data sets.

PDF AAAI Semantic Scholar

Cite

Text

Thiel et al. "A Non-Convex Optimization Approach to Correlation Clustering." AAAI Conference on Artificial Intelligence, 2019. doi:10.1609/AAAI.V33I01.33015159

Markdown

[Thiel et al. "A Non-Convex Optimization Approach to Correlation Clustering." AAAI Conference on Artificial Intelligence, 2019.](https://mlanthology.org/aaai/2019/thiel2019aaai-non/) doi:10.1609/AAAI.V33I01.33015159

BibTeX

@inproceedings{thiel2019aaai-non,
  title     = {{A Non-Convex Optimization Approach to Correlation Clustering}},
  author    = {Thiel, Erik and Chehreghani, Morteza Haghir and Dubhashi, Devdatt P.},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2019},
  pages     = {5159-5166},
  doi       = {10.1609/AAAI.V33I01.33015159},
  url       = {https://mlanthology.org/aaai/2019/thiel2019aaai-non/}
}