Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper develops a parallel hierarchical agglomerative clustering (HAC) algorithm ParHAC which achieves $(1+\epsilon)$-approximation with $\tilde{O}(m)$ work and poly-log depth. It also shows that the graph-based HAC using average-linkage is P-complete. The experiments on real datasets verifies the accuracy and scalability of ParHAC.
strengths_and_weaknesses: The speedup and scalability of ParHAC are significant, and the P-completeness result is new. The key idea of layering, which is a common proof skill in approximation algorithms, is novel for the proof of $(1+\epsilon)$-approximation, but it seems to be enlightened by [23]. The result of $(1+\epsilon)$-approximation and its proof seem similar to those in [23] also, except for the poly-log depth. It is better for the authors to make a thorough comparison with [23] and clarify the difference.
questions: (1) What is the relationship of this work with [23]?

(2) The authors explain the "work" as the number of operations performed in Sec 1.1. What kinds of operations does it count? Are they MultiMerge and Neighborhood Primitives? Why do the authors use work rather than running time in Th 1.1? What is the running time of the algorithm?
limitations: I cannot find any issue with negative societal impact. The main concerns have been listed in questions.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper focuses on a parallel approximation algorithm for hierarchical agglomerative clustering (HAC) with average—linkage function. Given $n$ data points, it constructs a similarity graph by considering each point as a vertex and connecting it to its $k$ nearest neighbors. The algorithm then separates the graph into logarithmic geometric layers such that each layer only contains edges of the same weight (up to 1+eps factor). Within each layer, all edges with weight within 1+eps factor of the maximum weight called heavy edges are merged to a larger cluster in parallel. Here a smart randomized algorithm is designed to merge all heavy edges. It can be proved that the algorithm runs in $\tilde{O}(m+n)$ work, and more importantly, in polylogarithmic depth with high probability. Finally, extensive experiments have been performed in graphs of different scales, to answer questions including: what is the clustering quality of the approximate algorithm compared to the exact HAC, HAC with complete similarity matrix, and existing works; how to tune the approximate parameter eps and similarity graph parameter $k$ for high quality results in practice; what is the run-time performance compared with the baselines mentioned above. Overall, the proposed algorithm empirically achieves a good balance between clustering quality and running time, and can scale to graphs of hundreds of billions edges.
strengths_and_weaknesses: Strengths:
1. Develops a simple yet efficient parallel algorithm for approximating HAC with average-linkage function. The poly-logarithmic depth is proposed for the first time, although it is based on a standard geometric layering for converting weighted graphs to unweighted graphs (within 1+eps factor).
2. Conduct comprehensive experimental evaluation and compare against recent baselines, exact counterpart, HAC based on complete similarity matrix, and end-to-end pointset-based clustering. Compared with the exact counterparts, this approximate algorithm achieves a clustering quality close to that of the exact algorithm across different metrics. The parallel algorithm provides an order of magnitude speedup over the sequential algorithm it is based on. 
3. The presentation of this work is good. The main text well summarizes the high-level ideas of their algorithm, with sufficient details included in the Appendix. Similarly, the experimental parts demonstrate the benefits of their algorithm, analyze the efficiency aspect, and refer to complete results in the Appendix.

Weaknesses:
1. The computational cost in terms of running time required by the current algorithm is an order of magnitude worse than Affinity, ~1.2 times worse than SCC on average. As in Figure 1, the clustering quality of SCC are comparable to ParHAC for a small value of $k$, which is the best parameter range one will choose.
2. It is kind of counter-intuitive to see that a larger value of $k$ in building similarity graphs results in worse clustering quality. But, when the complete similarity graphs are used as in SciPy package (k=n), the performance is not too bad. It is unknown why this phenomenon is observed across the implementations of multiple algorithms. 
3. Existing works that can scale to trillion-edge graphs have been reported such as SCC. ParHAC cannot achieve that scale because of memory constraints. Does this mean that ParHAC is an in-memory algorithm? Then what is the challenge when adapting it to an on-disk algorithm that poses less requirements on the memory?

questions: See Weaknesses items 2 and 3.
limitations: No
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper presents an efficient parallel hierarchical agglomerative clustering (HAC) algorithm with sublinear depth for the average linkage function. In particular, the authors provide a (1+$\epsilon$)-approximation algorithm on $m$ edge graphs using $\tilde{O}(m)$ time and poly-logarithmic depth. Experiments show that the proposed ParHAC algorithm enjoys huge speedup compared with state-of-the-art sequential and parallel baselines while achieving similar quality.

** Post Rebuttal Update **
I've read the rebuttal and the other reviewers' comments. I appreciate the update the authors have made, and I have no further questions given the inputs.
strengths_and_weaknesses: ** Strengths **

S1. The theoretical analysis provides a good understanding of the algorithm design's general idea (Thm 1.1, 1.2), the hardness (lower bound), and the performance (Thm 2.3).

S2. Experiments show substantial speedup over the baselines.

** Weaknesses **

W1. The presentation of algorithm design is unclear.

W2. The presentation of experiments is unclear. The authors might want to put more tables in the main text.

W3. The presentation seems to focus on speed and discuss less on quality. Usually one might expect a trade-off between speed and quality. Thus, discussing both should be of interest.


questions: Q1. For the pointset experiment, one might want to discuss the methods of generating the pairwise similarity.

Q2. Since the experiments include a variety of datasets, the authors might want to summarize and compare the datasets.
limitations: No conclusion. No discussion on potential societal impact.
review_title: null

Meta-review: metareview: Average score is 6. I also believe that this is a good paper. Please update the final version based on the reviewer feedback.
confidence: Certain
Decision: Accept