Correlation Clustering in Data Streams

KookJin Ahn, Graham Cormode, Sudipto Guha, Andrew McGregor, Anthony Wirth
Proceedings of the 32nd International Conference on Machine Learning, PMLR 37:2237-2246, 2015.

Abstract

In this paper, we address the problem of \emphcorrelation clustering in the dynamic data stream model. The stream consists of updates to the edge weights of a graph on n nodes and the goal is to find a node-partition such that the end-points of negative-weight edges are typically in different clusters whereas the end-points of positive-weight edges are typically in the same cluster. We present polynomial-time, O(n⋅\textpolylog n)-space approximation algorithms for natural problems that arise. We first develop data structures based on linear sketches that allow the “quality” of a given node-partition to be measured. We then combine these data structures with convex programming and sampling techniques to solve the relevant approximation problem. However the standard LP and SDP formulations are not obviously solvable in O(n⋅\textpolylog n)-space. Our work presents space-efficient algorithms for the convex programming required, as well as approaches to reduce the adaptivity of the sampling. Note that the improved space and running-time bounds achieved from streaming algorithms are also useful for offline settings such as MapReduce models.

Cite this Paper

BibTeX
@InProceedings{pmlr-v37-ahn15, title = {Correlation Clustering in Data Streams}, author = {Ahn, KookJin and Cormode, Graham and Guha, Sudipto and McGregor, Andrew and Wirth, Anthony}, booktitle = {Proceedings of the 32nd International Conference on Machine Learning}, pages = {2237--2246}, year = {2015}, editor = {Bach, Francis and Blei, David}, volume = {37}, series = {Proceedings of Machine Learning Research}, address = {Lille, France}, month = {07--09 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v37/ahn15.pdf}, url = {https://proceedings.mlr.press/v37/ahn15.html}, abstract = {In this paper, we address the problem of \emphcorrelation clustering in the dynamic data stream model. The stream consists of updates to the edge weights of a graph on n nodes and the goal is to find a node-partition such that the end-points of negative-weight edges are typically in different clusters whereas the end-points of positive-weight edges are typically in the same cluster. We present polynomial-time, O(n⋅\textpolylog n)-space approximation algorithms for natural problems that arise. We first develop data structures based on linear sketches that allow the “quality” of a given node-partition to be measured. We then combine these data structures with convex programming and sampling techniques to solve the relevant approximation problem. However the standard LP and SDP formulations are not obviously solvable in O(n⋅\textpolylog n)-space. Our work presents space-efficient algorithms for the convex programming required, as well as approaches to reduce the adaptivity of the sampling. Note that the improved space and running-time bounds achieved from streaming algorithms are also useful for offline settings such as MapReduce models.} }
Endnote
%0 Conference Paper %T Correlation Clustering in Data Streams %A KookJin Ahn %A Graham Cormode %A Sudipto Guha %A Andrew McGregor %A Anthony Wirth %B Proceedings of the 32nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2015 %E Francis Bach %E David Blei %F pmlr-v37-ahn15 %I PMLR %P 2237--2246 %U https://proceedings.mlr.press/v37/ahn15.html %V 37 %X In this paper, we address the problem of \emphcorrelation clustering in the dynamic data stream model. The stream consists of updates to the edge weights of a graph on n nodes and the goal is to find a node-partition such that the end-points of negative-weight edges are typically in different clusters whereas the end-points of positive-weight edges are typically in the same cluster. We present polynomial-time, O(n⋅\textpolylog n)-space approximation algorithms for natural problems that arise. We first develop data structures based on linear sketches that allow the “quality” of a given node-partition to be measured. We then combine these data structures with convex programming and sampling techniques to solve the relevant approximation problem. However the standard LP and SDP formulations are not obviously solvable in O(n⋅\textpolylog n)-space. Our work presents space-efficient algorithms for the convex programming required, as well as approaches to reduce the adaptivity of the sampling. Note that the improved space and running-time bounds achieved from streaming algorithms are also useful for offline settings such as MapReduce models.
RIS
TY - CPAPER TI - Correlation Clustering in Data Streams AU - KookJin Ahn AU - Graham Cormode AU - Sudipto Guha AU - Andrew McGregor AU - Anthony Wirth BT - Proceedings of the 32nd International Conference on Machine Learning DA - 2015/06/01 ED - Francis Bach ED - David Blei ID - pmlr-v37-ahn15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 37 SP - 2237 EP - 2246 L1 - http://proceedings.mlr.press/v37/ahn15.pdf UR - https://proceedings.mlr.press/v37/ahn15.html AB - In this paper, we address the problem of \emphcorrelation clustering in the dynamic data stream model. The stream consists of updates to the edge weights of a graph on n nodes and the goal is to find a node-partition such that the end-points of negative-weight edges are typically in different clusters whereas the end-points of positive-weight edges are typically in the same cluster. We present polynomial-time, O(n⋅\textpolylog n)-space approximation algorithms for natural problems that arise. We first develop data structures based on linear sketches that allow the “quality” of a given node-partition to be measured. We then combine these data structures with convex programming and sampling techniques to solve the relevant approximation problem. However the standard LP and SDP formulations are not obviously solvable in O(n⋅\textpolylog n)-space. Our work presents space-efficient algorithms for the convex programming required, as well as approaches to reduce the adaptivity of the sampling. Note that the improved space and running-time bounds achieved from streaming algorithms are also useful for offline settings such as MapReduce models. ER -
APA
Ahn, K., Cormode, G., Guha, S., McGregor, A. & Wirth, A.. (2015). Correlation Clustering in Data Streams. Proceedings of the 32nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 37:2237-2246 Available from https://proceedings.mlr.press/v37/ahn15.html.

Related Material