Optimal Tradeoffs for Correlation Clustering Cost Estimation in Node-Arrival Streams

Large collections of embeddings induce similarity graphs whose edges can be computed on demand rather than stored explicitly. We study estimation of the optimal correlation clustering cost in the node-arrival streaming model. Here, the nodes themselves are the data objects arriving sequentially, and edges can be implicitly derived between stored nodes. We present ONCE and TWICE, our one- and two-pass algorithms, respectively. For an $n$-node graph, additive error $\Delta$, and constant $0<ϵ<1$, ONCE gives a $(3+ϵ,\Delta )$-approximation using $O(n^2/\Delta )$ stored nodes and additional words, and TWICE gives a $(5+ϵ,\Delta )$-approximation using $\tilde{O}(n/\sqrt{\Delta })$ stored nodes and additional words. We prove matching lower bounds that characterize the tradeoff between space and additive error in the one- and constant-pass regimes, up to polylogarithmic factors and the representation size of the nodes. Experiments on 100 million image embeddings show that ONCE and TWICE give accurate estimates while storing less than 2% of the nodes.