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 designs sublinear algorithms for hierarchical clustering in dynamic streaming model, query model and MPC model over very large graphs. Minimum cost hierarchical partitioning is the optimization objection (Dasgupta’s cost function). From the theoretical aspect, this paper proved the bounds including lower and upper bound respectively for the three given models. They prove a general structural result that shows that a cut sparsifier can be used to recover a (1 +o(1))-approximation to the underlying HC instance.


strengths_and_weaknesses: Although this research problem is not novel, sublinear algorithms for hierarchical clustering is one of the fundamental issue in the studies of graphs. Lots of applications need the sublinear algorithms especially for massive graphs. The paper is well written with a good presentation. It supplies enough theoretical proofs for the complexity and (1 +o(1))-approximation is a good general structural result in the three models. However, I have some concerns about the approach and applications.
1.	Some recent works prove a seem better bound for the same problem. The authors should compare to them. For example, Assadi S, Chatziafratis V, Mirrokni V, et al. Hierarchical Clustering in Graph Streams: Single-Pass Algorithms and Space Lower Bounds[C]//Conference on Learning Theory. PMLR, 2022: 4643-4702.
2.	Although proofs on bounds are good evidence for showing the performance, it would be better and attractive to give some practical experimental studies to show the real effectiveness in massive graphs. In some cases, a well theoretical complexity still be not enough for the real huge graphs.

Minor problem:
Although the presentation is relatively well, some necessary examples are needed for the readers to follow clearly. 
questions: none
limitations: 1.	Some recent works prove a seem better bound for the same problem. The authors should compare to them. For example, Assadi S, Chatziafratis V, Mirrokni V, et al. Hierarchical Clustering in Graph Streams: Single-Pass Algorithms and Space Lower Bounds[C]//Conference on Learning Theory. PMLR, 2022: 4643-4702.
2.	Although proofs on bounds are good evidence for showing the performance, it would be better and attractive to give some practical experimental studies to show the real effectiveness in massive graphs. In some cases, a well theoretical complexity still be not enough for the real huge graphs.
review_title: null

final_score: 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.
review_content: summary: This paper considers developing resource efficient algorithms for hierarchical clustering of weighted graphs in several settings (streaming, graph query model, mpc model).  Following recent work which developed an objective function for hierarchical clustering (Dasgupta 2016), the goal is to develop algorithms with sublinear resource usage (in the number of edges) in each model while producing an $O(\phi)$-approximation to the optimal tree for Dasgupta's objective function.  The main results of this paper are to achieve exactly this.  By making a key observation about the structure of the objective function, the authors show that this problem reduces to efficiently constructing a cut sparsifier.  In some settings (e.g. streaming using $\tilde{O}(n)$ space), this can be done immediately via known techniques for constructing cut sparsifiers.  For the other settings (graph query model and the mpc model), a more relaxed notion of cut sparsifier is proposed (which allows for some additive error in addition to the multiplicative error), and the authors give sublinear algorithms for constructing such a relaxed cut sparsifier in the remaining settings.  Lower bounds showing near optimality of the results are also given.
strengths_and_weaknesses: There has been significant interest in hierarchical clustering recently and one issue that many algorithms suffer from is scalability.  This paper helps to address this problem in several settings from the perspective of Dasgupta's objective function.  The techniques are natural and are well explained.

One thing that is missing from this paper (but not probably not necessary) is an experimental evaluation to demonstrate the practical effectiveness of the proposed algorithms.
questions: How would the proposed algorithms compare to practically efficient algorithms? e.g. Sumengen, Baris, et al. "Scaling hierarchical agglomerative clustering to billion-sized datasets." arXiv preprint arXiv:2105.11653 (2021).
limitations: N/A
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: Hierarchical clustering over graphs ha been mathematically formalized with a natural objective function introduced by Dasgupta [STOC2016]. Unfortunately, this function is hard to optimize and approximation algorithms have been proposed in the TCS literature. This paper studies this problem in the regime of sublinear computational resources, specifically, for three models of computations:
- streaming model = sublinear space
- query model = sublinear time
- MPC model = sublinear communication
For each model, upper and lower bounds are provided.
strengths_and_weaknesses: The paper presents informal statements for the main results proven in Appendix. The results appear to be new. There is a recent COLT paper [5] with similar results in the streaming setting.
This paper is well-written and deals with theoretical results.
The motivation for these results is very far from any practical application.
questions: I am not sure I understand the motivation for the authors to submit this paper to Neurips and I would like to hear their arguments explaining why it is more appropriate to publish this work at Neurips instead of a TCS conference like SODA, STOC, FOCS? I did count 12 references in JACM, STOC, SODA and FOCS. 
I like cross-disciplinary work but then you need a lot more work to motivate your results. As it is written, I hardly see any possible impact for this paper in the ML community. Even the computational models will only be known from a minority of the audience, so that the main results will not be understood.
Similarly, the lower bounds are obtained by constructing very contrived graphs. I understand that these hard instances are instructive in order to understand the worst-case performance of algorithms. But what is the motivation for these bounds in a machine learning setting?
limitations: NA
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 hierarchical clustering over graphs with the objective function of Dasgupta. Sublinear algorithms w.r.t. the number of edges in the input graph are developed in three models of computation, including the dynamic streaming model, the query model, and the massively parallel computation (MPC) model. Interesting matching lower bounds are provided for the upper bounded resource above. Specifically, a 1-pass semi-streaming algorithm naturally follow from existing algorithm [1] and their observation. In the query model, combining existing methods [14,37] and their observation leads to sublinear time algorithms for graphs of different sparsity. For the MPC model, a 2-round $\tilde{O}(m)$-memory algorithm and a 1-round $\tilde{\Theta}(m^{4/3})$-memory algorithm are developed based on [1]. All above algorithms rely on the crucial observations that, from a graph cut perspective, the objective function can be well approximated in a cut sparsifier of the input graph. Moreover, two hard instances are designed to derive time and communication lower bounds in the query and MPC models, respectively. Finally, the extensions to other related hierarchical clustering objectives such as the dissimilarity [15] are discussed.
strengths_and_weaknesses: Strengths:
1. The idea of using cut sparsifiers in improving the computational resource of graph algorithms has been widely used. But using it in hierarchical clustering and providing theoretical analysis on the required resource and approximation factor is not well studied with only a few related work, e.g., [5]. The problem of hierarchical clustering is reduced to the problem of constructing cut sparsifiers with limited resource based on the observations that cut sparsifiers can approximately preserve the cost of a dendrogram. Comprehensive studies on 3 models of computation are performed and upper bounds are complemented with almost matching lower bounds.
2. The developed lower bounds in the query and MPC models are quite interesting and need to overcome multiple challenges. The authors are able to describe the high-level overview in the main text and then refer to the full details in the Appendix.
3. The organization of this work is good. I like the discussions in Sections 4 and 5, providing context on related works and extensions to other objective functions of hierarchical clustering. I browsed some contents in the Appendix and the quality of writing remains good compared to the main text.

Weaknesses:
1. The computational upper bounds developed in Section 2 are not very challenging and based on existing methods in the respective models. The upper and lower bounds in the dynamic streaming model are straightforward.
2. As a reader of a hierarchical clustering paper in NeurIPS, I would expect to see some experimental results on the developed algorithm unless the theoretical contributions are very novel and significant. It would be much better if experiments on some of the algorithms had been implemented and evaluated in real-world datasets.

questions: In the alternative view of the objective based on S-T cut, a sparsifier approximately preserving all S-T cut values suffers from the lower bound of $\Omega(m)$. When transforming the S-T cut to graph cut ($S,\bar{S}$)-cut, why the barrier of lower bound can be broken?
limitations: No
review_title: null

Meta-review: metareview: The paper presents new algorithm for hierarchical clustering in different regimes. In particular they show a new algorithm for a (dynamic) edge streaming model, for a neighbor query model and for the MPC model. The paper contains both nice theory results and in the rebuttal phase the author(s) supported them with interesting experimental results.

Overall, we suggest to accept the paper as poster.
confidence: Certain
Decision: Accept