Summary
This paper demonstrates that the celebrated Pivot algorithm for (unweighted, complete) correlation clustering (with the min disagreements objective) can be adapted to the single-pass, semi-streaming setting, to yield a (3+\eps)-approximation in expectation using O(n/eps) words of memory. (Note that the original Pivot algorithm gives a 3-approximation in expectation.) This improves on previous works that show a (3+\eps)-approximation using O(n\log n) words of memory, and a 5-approximation using O(n) words of memory. In the single-pass, semi-streaming setting, edges and their labels arrive online adversarially and the stream can only be read once. It is assumed that only positive edges arrive and the remaining edges in the complete graph are implicitly negative.
The Pivot algorithm chooses a random permutation of the vertices, visits each vertex in this order, and if a vertex is unclustered, makes that vertex a "pivot." The pivot grabs its unclustered positive neighbors from the remaining sequence and forms a cluster. The algorithm proposed in this paper tweaks the Pivot algorithm by again choosing a random permutation of the vertices, but for each vertex it only retains positive edges to the top-k ranked neighbors in this permutation. It then runs Pivot on this subgraph, using the chosen random permutation. The analysis rests on controlling the cost of (positive) edges cut by special vertices called "singleton vertices." These are vertices u whose top-k positive neighbors all come before u, but none are chosen as pivots, so u ends up in a singleton cluster. (Controlling the cost of other edges is done by reusing the analysis of Pivot, since these edges are cut by the pivot vertices.) The crux of the argument controlling the cost of singleton vertices is to show that a certain potential function is always positive in expectation, which in turn comes from showing it is a submartingale.
Strengths
- The algorithm is a pleasingly simple variant of the Pivot algorithm. It lends insight into just how much "wiggle room" there is in the original Pivot algorithm, as it might a priori seem surprising that we only need retain the top-k ranked neighbors of each vertex.
- The analysis (particularly the main lemma, which designs a novel potential function and shows it is a submartingale) is quite elegant. Moreover, it is substantially simpler than analyses in the aforementioned previous works on the semi-streaming setting.
- This paper contributes to the growing literature on how the Pivot algorithm can be adapted to other models of computation (in addition to streaming, parallel models such as MapReduce). While the result itself is not a significant improvement over known results, and the algorithm is of comparable simplicity to previous ones, it provides a much cleaner analysis.
Weaknesses
While the paper is overall clear and well-written, it would be useful to give a bit more background comparing the proposed algorithm to those in prior work in the semi-streaming setting.
Some typos / omissions in the writing:
- U_t on pg. 6 is seemingly meant as the complement of how it is defined on pg. 4
- D^+(v) = |N(v)| on pg. 5
- It would be good to add a line stating formally what it means to "cut" at an edge (although it is clear from context)
And a suggestion: The use of the term singleton is a bit confusing, since, as the authors mention, not all singleton clusters correspond to "singletons" as defined in the Pivot selection and clustering section of Figure 1. It may be worth just using a distinct term altogether for such vertices.
Rating
8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.