acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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 -node graph, additive error , and constant , ONCE gives a -approximation using stored nodes and additional words, and TWICE gives a -approximation using 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.

Primary area:
learning theory
Keywords:
correlation clustering, graph streaming, node-arrival, cost estimation, approximation algorithms

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_Q21SOpenReview ↗
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 (c,Δ)(c,\Delta)-approximation is a solution with cost that is at most cOPT+ΔcOPT+\Delta.

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 (3+ϵ,Δ)(3+\epsilon,\Delta)-approximation in O_\epsilon(\min{n,n^2/\Delta) words. TWICE: A 2 passes randomized algorithm that provide (5+ϵ,Δ)(5+\epsilon,\Delta)-approximation in Oϵ(n/Δ)O_\epsilon(n/\sqrt{\Delta}) words.

Additionally, the paper contains lower bounds that show the results are optimal in terms of memory.

Critical strengths
  1. 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).
  2. The results are tight (matching lower bounds).
  3. The paper is sounds and well written.
Critical weaknesses
  1. 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.
  2. The techniques seem to be only suitable for unweighted case.
  3. The number of nodes nn must be known before the steam, although this limitation is inherent by Corollary 4.3.
  4. The discussion of related work on correlation clustering in restricted computational models, such as streaming and parallel settings, is incomplete and should be expanded.
  5. The algorithm does not seem to improve the results of previous work in practice.
  6. The improvement of lower bounds is incremental over previous work.
Questions for authors
  1. Is there an intuition why the algorithms performs slightly worse in practice?
Reviewer_4e6WOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the correlation clustering problem, in the node streaming setting. The paper focusses on the tradeoff between memory usage and approximation quality. For this reason, the focus of the paper is on estimating the optimal objective function value rather than on returning clusters directly.

The paper gives matching upper and lower bounds for this problem in the single-pass and multi-pass regimes, where the approximation guarantee is parameterised by an additive factor. This improves on previous work by tightening both the upper and lower bound.

Critical strengths
  1. The new theoretical results provide matching upper and lower bounds for the problem, and so the paper gives a well-rounded view of the correlation clustering problem in this node-streaming setting. This is a valuable theoretical contribution.
  2. The overall presentation of the paper is generally clear and readable. This includes a clear comparison with previous work which places the paper in context.
Critical weaknesses
  1. The algorithms analysed in this paper are not novel - they are essentially estimators built from the clustering algorithms proposed by Garcia-Soriano et al. (2020) and Behnezhad et al. (2023). Thus, the value in this paper seems to be in demonstrating the tightness of the analysis, rather than in proposing novel algorithms.
  2. Some aspects of the presentation could be improved.
    • The objective function of the optimisation problem is not formally stated in the paper.
    • The notation of the problem set up is unclear. How is the input graph defined and notated? Do we consider it a complete graph, with signed edges, or are there only edges between nodes which are considered similar (or dissimilar)? Based on the notation on lines 132-137, it appears that there is an edge between uu and vv if they are dissimilar. On the other hand, line 70 seems to imply that there is an edge between nodes only if they are considered similar.
    • The presentation of the experimental results is unclear. What do the axes in Figure 2 represent?
Questions for authors
  • Could you clarify the precise objective function you are considering, and how you consider the input graph to be represented in your notation?
  • Could you clarify how Figure 2 should be interpreted? What do the axes represent?
  • What is the typical range of OPT, and so what values of Δ\Delta are reasonable?
Reviewer_34XiOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

The paper discusses Correlation Clustering, where each pair of nodes have a similar/dissimilar (binary) label and provide streaming algorithms in the node arrival model. The main result is a 2 pass almost 5 approximation using sublinear (in number of nodes) space for estimating the cost of clustering. The main technique of the paper is combination of different but existing sampling ideas. The main idea beyond prior work seems to be a parallel repetition analysis.

From a contribution point of view the paper continues a long tradition of results. However it is not clear if a problem is being solved or a technique is being sharpened. For example (a) the binary notion of similar and dissimilar is unfortunate -- similarity is a score with a variation and making it 0/1 defeats the entire mathematics of likelihood/machine learning that is tied to similarity. Foe example, in Figure 2, the authors threshold a graph with cosine similarity 0.7 (one would assume, not fully spelt out, higher is similar and lower is dissimilar). But that means a value of cosine = -1 (or 0, if vectors are all nonnegative) between a pair is the same as being in a 60 degree cone (cosine = 1/2). The same holds for the radius 400 setting. That means to get value of out of this entire research line we would have to try to find different thresholding, which means multiple passes and quite a bit of space which is not discussed in the problem setting. If the goal is to show the usability/simplicity of a randomized algorithm then the above criticism does not apply and Ailon etal's paper should be viewed in that context. (b) if we are storing n objects in a multipass streaming environment, then why do we care about a tilde{O}(n/sqrt{Delta}). Maybe someone does, and there is at least 1 user of this result. But then that is the motivation and not that it is a fundamental problem from 2004. This actually relates to the "prebuttal" in lines 40-45; if we are storing all the points somewhere why will anyone ever think of realizing all pairs of distances. Yes storing quadratic 0/1 numbers that can be regenerated at will is a bad idea, but no was (hopefully) was thinking about implementing that bad idea. (c) It is unclear what is accomplished by the estimation of the clustering. In general clustering has a challenge that it is seldom the final goal -- but estimation is even further removed. There can be an application -- but that needs to be written down in the introduction, with the differentiation vis-a-vis the 2023/similar Neurips paper. It is quite possible that paper was also attempting something else which was the true value of the paper and estimation of correlation clustering was an example. (d) The entire section 2 is "Run Garcia-Soriano 2020, 1/epsilon times in parallel". This did not need an algorithm box and the space could have been used for a critical discussion of why this paper is different from the other papers in terms of new ideas.

Critical strengths
  1. The paper improves the number of passes of a prior result from k+4 passes (noted that k was not defined in the introduction, before use -- if incorrect, please provide pointers) to 2 passes. One would assume k is the number of clusters; in any case 4 is larger than 2.

  2. The method uses standard constructions in graph streaming -- like spanners, but if the application was unknown in this context then that can be a contribution, but it seems the overall ideas were known. It is possible that the knowledge of the solution was spread across different sub-communities, and in that case using them together is a contribution -- but that would have a high bar for expositional clarity.

Critical weaknesses
  1. The net result is (approximation of) estimation of a 0/1 (approximate thresholding) of similarity. The authors would really help themselves if they can convince if there is a concrete user/space which would need this estimation solved. The techniques in this paper were not that difficult or novel -- but then everything rests on the question "how critical is the problem"? Clustering itself has criticism about use -- but at least is explanatory. Estimation of clustering can only be useful in an interactive loop in which case number of passes, space usage are less relevant because of the loop (and if not, that is what the paper should specify and not simple algorithm boxes).
Questions for authors

Please consider addressing weakness 1, and the (a)-(d) in the paper summary. Also it'll be helpful to clarify k in the result table.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.