Estimating Correlation Clustering Cost in Node-Arrival Stream

We study the correlation clustering problem in the node-arrival data stream model. Unlike previous work, where the stream consists of the graph's edges, we focus on the setting in which the stream contains only the nodes. This model better reflects many real-world scenarios in which the data stream naturally consists of raw objects (e.g., images, tweets), and the similar/dissimilar edges are derived through a similarity function. We present *C*$^4$*Approx*, a streaming algorithm that approximates the cost of correlation clustering using sublinear space in the number of nodes and a constant number of passes. We further complement this result with lower bounds. Experiments on real-world datasets show that by storing only 2\% of the nodes, our algorithm achieves performance comparable to the classic *Pivot* algorithm and the more recent *PrunedPivot* algorithm, even on sparse graphs.

This paper studies how to estimate whether a huge dataset is easy or hard to cluster when the data arrives one item at a time and cannot all fit in memory. In correlation clustering, pairs of items are marked as similar or dissimilar, and the goal is to group items while minimizing “mistakes,” such as splitting similar items apart or putting dissimilar items together. The aim of the paper is to estimate the minimum number of such mistakes, which serves as a measure of how clusterable or inconsistent the data is. We propose *C*$^4$*Approx*, a streaming algorithm that stores only a small sample of nodes and uses it to estimate clustering cost with much less memory than storing the whole dataset. Our experiments on Wikipedia, LiveJournal, and ImageNet-21K show that the method can give estimates close to standard clustering algorithms while storing only a small fraction of the data.