- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper considers the classical correlation clustering problem in the recent node-arrival streaming model (Liu et al., ICML 2026). In this model the objects are the set of nodes, which arrive one at a time. A similarity query can be executed only between two objects stored in memory. The goal is to minimize the space complexity.
Since the output of correlation clustering is linear in the number of nodes, the goal in this model is to output the correlation cost (an estimation of). A -approximation is a solution with cost that is at most .
The paper directly improve the previous work of Liu et al. by suggesting two algorithms ONCE and TWICE: ONCE: A single pass randomized algorithm that provide -approximation in O_\epsilon(\min{n,n^2/\Delta) words. TWICE: A 2 passes randomized algorithm that provide -approximation in words.
Additionally, the paper contains lower bounds that show the results are optimal in terms of memory.
Critical strengths
- The paper significantly improves over previous work by utilizing algorithms from query efficient correlation clustering (Garcia-Soriano et al., 2020) and streaming algorithm (Behnezhad et al., 2023).
- The results are tight (matching lower bounds).
- The paper is sounds and well written.
Critical weaknesses
- The model is not motivated enough. Also, in my opinion the previous paper shows that in this model we cannot hope to obtain useful results. So I am not sure further study of this model is interesting.
- The techniques seem to be only suitable for unweighted case.
- The number of nodes must be known before the steam, although this limitation is inherent by Corollary 4.3.
- The discussion of related work on correlation clustering in restricted computational models, such as streaming and parallel settings, is incomplete and should be expanded.
- The algorithm does not seem to improve the results of previous work in practice.
- The improvement of lower bounds is incremental over previous work.
Questions for authors
- Is there an intuition why the algorithms performs slightly worse in practice?