Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper focuses on designing a hierarchical clustering (hc) algorithm with improved efficiency. The algorithm, named DAC (divide-and-conquer), detects local clusters in small neighborhoods and then merge them in a hierarchical order. The algorithm starts with a hyperrectangle (block) that contains all the data points, and iteratively dissecting the current hyperrectangle into 2^D smaller hyperrectangles and thus creating a hypertree. The dissection of blocks continues until every point has found its own block (mesh cells). The algorithm then adopts a bottom-up approach to merge the blocks. The method is tested on several datasets. The algorithm is tested on several datasets and compared with general clustering baselines.
strength_and_weaknesses: Strengths:

- I like the idea of relying on growing and merging high-dimensional hyperrectangles in Euclidean space to speed up agglomerative hc. This seems to be a natural approach that is worth studying.
- The algorithm returns reasonable results on the datasets tested. The clustering quality and efficiency seem to be promising, if not sufficient.

Weaknesses:
- After taking a closer look, the partition of the whole space into small blocks and construction of the hypertree representation based on mesh cells looks similar to rescaling and dicretizing the different dimensions of the data points. The agglomerative algorithm built on top of that looks like a generalization of single-linkage, or MST rule (iteratively choosing two clusters with smallest shortest distance between any two points cross-clusters ) for mesh cells. In that sense, I wonder if the algorithm is significantly or only moderately different from existing approaches. I think it might help if the authors could emphasize this aspect.
- The idea is somewhat similar to a recent line of existing work, which constructs hc trees efficiently by geographically constructing local buckets or blocks that contain only very few points and merging on top of that (add citations) using Approximate Nearest Neighbor techniques. This line of work is not mentioned in the paper. In fact the community has witnessed sub-quadratic run time bounds on general agglomerative HC algorithms using this approach. See for example the following papers: Abboud, Amir, Vincent Cohen-Addad, and Hussein Houdrougé. "Subquadratic high-dimensional hierarchical clustering." Advances in Neural Information Processing Systems 32 (2019); Moseley, Benjamin, Sergei Vassilvtiskii, and Yuyan Wang. "Hierarchical clustering in general metric spaces using approximate nearest neighbors." International Conference on Artificial Intelligence and Statistics. PMLR, 2021.
- The experiment design is not very thorough. The datasets used seem to be limited: a few datasets with similar cluster constructions, and low-dimensional.  I would be interested in seeing how the algorithm performs on high-dimensional datasets to see if the tree construction grows fast as D becomes big. Further, since the paper focuses on hierarchical clustering, the baseline should also include other hc approaches such as single- average- and centroid-linkage.
clarity,_quality,_novelty_and_reproducibility: The structure of the paper is clear, but it will help if the authors could further clarify certain details in the algorithm design and emphasize the design of the merging rule of subclusters. It will also help if the authors could include a small-sized example dataset and show how the algorithm works. Figure 2 seems confusing to me.
For example there are some minor issues:
1) On page 3, the second paragraph of section 3, I think the notation E is used before it is formally defined?
2) Same thing applies to "mutually visible boundary". It might be better to remind readers of the definition.
3) The authors can also emphasize certain definitions such as maximal black nodes to make the algorithm description more clear.
summary_of_the_review: Overall this paper contains some interesting ideas, which could potentially give rise to efficient hc algorithms indeed. However, after reading the paper, I feel the design of the hypertree and the rule of merging maximal black nodes, even when combined together, does not really help us go beyond the dilemma of agglomerative hc algorithms being very slow. Rather than a new agglomerative algorithm with novel merging rules, the approach is closer to a variant of the MST, or single-linkage, algorithm. To that end, the experiment design does not seem to be sufficiently convincing either. It might not be ready for this venue yet.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper presents a spatial-partition-based hierarchical clustering approach. Efficiency comes from a decomposition of the space into bins and using the structure of the space to determine which clusters can be merged. The authors present experiments on spatial clustering datasets with clear visual clusters. The authors demonstrate scalability compared to DBSCAN, spectral clustering, and a mesh-based method as well as use of the method, DAC, in a downstream task.
strength_and_weaknesses: **Strengths**
* This paper explores interesting ideas about how methods for scaling hierarchical clustering by efficient data structures / algorithms for selecting which clusters can merge in a levelwise manner. 
* The algorithm has novel characteristics and the authors have taken care to develop a method suited for the kinds of data they are considering. 

**Weaknesses**
* It would be helpful to have more motivation for algorithms in this low-dimensional settings, when does such data occur in practice? What are the inductive biases of approaches that work well? Why does the proposed method achieve those inductive biases? It is hard to understand the generality of the method to datasets with high dimension? 
* I think there needs to be a comparison to other well known clustering algorithms such as hierarchical agglomerative clustering. This would help readers understand how challenging the datasets can be. It would strengthen the paper further to consider a wider range of hierarchical clustering methods. 
* It would help to understand to more clearly the properties of the algorithm in what it can recover and how quickly compared to competing methods. Theoretically, Big-O notation or more empirical performance. As it is, I am left as a reader uncertain about when to use the proposed method. Further I am left with not fully understanding what aspects of previous work the proposed method is offering an improvement on.
* I think that the paper would be higher impact in a conference that has greater focus on algorithmic techniques than what I think of ICLR's "typical paper", which is more aligned with representation learning. I think conferences such as KDD, CKIM, SDM, could be a better fit?

clarity,_quality,_novelty_and_reproducibility: I think that the following statement is quite strong and not always true. It would be helpful to add citations to the cost functions the authors are referring to here. 

> Hierarchical clustering approaches derive a tree (hierarchy) of clusters in which clusters at each
level correspond to a local minimum of the cost function with a level-specific value. Each cluster
at a level splits into multiple sub-clusters at the level immediately below, where the sub-clusters are
more compact than the parent clusters, corresponding to stronger local minima of the objective function. Hierarchical clustering can be top-down (recursively split clusters) or bottom-up (recursively
combine clusters).

Nit: When citing multiple papers it is nice to combine the citations e.g., \cite{A,B,C} rather than \cite{A}, \cite{B}, \cite{C}

The following statement is a bit strong, there are things that could be done for metric MST and various very scalable and parallelizable methods like Boruvka's algorithm as well as ways to use nearest-neighbor indexes (e.g. cover tree) to make computation more efficient (e.g., [Curtin et al, (2013)'s dual tree methods](http://proceedings.mlr.press/v28/curtin13.pdf)). 

> unlike the MST algorithm which computes pairwise distance over all pairs of points
summary_of_the_review: The paper explores an interesting algorithmic idea for hierarchical clustering. However, the advantages of the proposed method are not greatly clear to me. The paper could be improved with a comparison to a wider array of techniques (including classic methods like HAC) and clarifying (1) importance of low-dimensional data (2) inductive biases of the algorithm that lead to its effectiveness.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper presents a hierarchical algorithm based on the locality of data points. Entities are represented in the D dimensional space as D-dimensional hypercubes and are assigned colors based on whether they are completely/partially contained within another entity. The algorithm first inserts entities into a tree, colors nodes, computes the adjacency matrix and components based on maximal black nodes, and finally runs the MST algorithm on the components. The worst time complexity is O(n^2log(n)).
strength_and_weaknesses: + The authors have procedures used in their algorithm in detail 
- It is not clear whether the quality of clusters or the efficiency of the approach is better than simple hierarchical algorithms that are capable of using the numeric features representing spatial location and have lower time complexity. The paper discusses that STING and DBscan also have better time complexity. It would be good if the authors clarify this
- The papers discussed in the related work are old. It would be useful if recent work is cited, since more recent work is available on spatial hierarchical clustering 
clarity,_quality,_novelty_and_reproducibility: I think all of the above can be improved. For example, my recommendation would be to write the algorithm in Section 4 as pseudocode for clarity, and also to use consistent terminology in the calculation of the time complexity. Since the references are rather old, and recent work has not been cited, this raises a question mark on the novelty of the algorithm as well as its effectiveness in discovering useful clusters. 
summary_of_the_review: The main claim of the paper is that efficiency has been increased. However, since 
- recent work is not cited,
- the approach is rather complicated, and
- it's not clear in which situations/domain such an approach would result in more meaningful clusters
- the detected clusters are not evaluated by comparison with other techniques (recent or old)
I don't really know whether the claim is supported. 

Some other points in the paper also raise questions. For example, according to the authors 'degenerate data may wipe out DAC's advantages'. Moreover, the authors have pointed out themselves that STING and DBScan has lower time complexity. So unless there is a clear advantage in using the presented approach, it is difficult to understand the claim.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposes an algorithm to use tree-based algorithm for the purpose of clustering. The tree-based approach first partite the data into different chuncks hierarchically and merges smaller pieces into clusters via efficient algorithms. Compare to conventional clustering algorithms, the authors claim that the method is computationally efficient.
strength_and_weaknesses: I really like the paper is not overselling the proposed method, the limitations of the method is discussed in the paper. 

Weaknesses:

1. Computational efficiency is one of the selling point of the proposed method. However, both in the description and the experiment, the reviewer do not see enough evidence that the proposed method is more efficient especially in higher dimensions. The reviewer suggests the authors either put a table to list the computational cost of various approach and compare the computational complexity theoretically or conduct more experiments to show this empirically.

2. Additional work on related work. There are other tree-based clustering methods that the authors do not discuss, such as [this](http://web.cs.ucla.edu/~wwc/course/cs245a/CLTrees.pdf). Anothe paper that has a similar flavor is [this](https://arxiv.org/pdf/1802.04397.pdf). The reviewer suggests the authors to have a more detailed disucssion on the related work. Although the distance is not direclty used, the ajacency matrix implicitly uses the information of the distances, can the authors highlight the difference of the proposed method and other distance based approaches? 

3. In the experiment, only the computational time are compared quantitatively, it would be very helpful and more convincing if quantitative metrics for the agreement of different clustering approaches is also used. Section 6.3 only reports the purity score, more metrics should be used for comparison.

4. The description in the paper requires the readers to have a lot of background knowledge in tree-based algorithm. It would be really helpful if either 1) visualize the description in section 3 or 2) refer the readers to some useful resources.

clarity,_quality,_novelty_and_reproducibility: *Clarity*: the description of the method in the paper is relatively easy to follow though it requires some background knowledge on tree traverse etc.

*Quality*: the paper needs to be carefully proofread. There are many typos in the paper. Moreover, to illustrate the effectiveness of the proposed methods, the author also need to compare with other clustering approaches, current experiment is not enough.

*Novelty*: the proposed method is novel to the best of the reviewer's knowledge.

*Reproducibility*: the algorithm details are given in the appendix, but the description of the experiment details  in section 6.3 are not enough to reproduce the experiment.

summary_of_the_review: The major concern is that the experimental results and the description are not convincing for the reviewer to take the proposed method if there is a need for clustering. More thorough discussion and comparison with existing methods to demonstrate the method is indeed better than existing ones. Hence, the reviewer believes additional work needs to be done before the paper can be published.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper proposes a two-step procedure for spatial clustering. It first performs recursive discretization of data points to divide them into smaller blocks, followed by merging them into hierarchy of clusters, which naturally leads to a tree structure of clusters. The efficiency and the effectiveness of the proposed method is empirically evaluated on several real-world datasets.

### Strength
- The proposed method is empirically shown to be more efficient than CLIQUE, which is the popular mesh-based clustering algorithm.

### Weakness
- Experiments are not thorough and the performance of the proposed algorithm is not convincing at the moment. I imagine that the effectiveness of such discretization-based methods quickly vanishes if the dimensionality of data gets higher due to the curse of dimensionality; that is, every data point is immediately isolated into a single block at the first couple of divisions. If this is not the case of the proposal, the authors should show it theoretically and/or empirically. Unfortunately, all datasets used in the experiments are low-dimensional. Although the authors argue that it is difficult to visualize results for high-dimensional data, it is not problematic. It is enough to present the resulting quality score like NMI for various datasets, and some dimensionality reduction methods like tSNE or UMAP can be used for visualization.

- As reviewers pointed out, the advantage of efficiency is questionable. For example, KD-tree is popularly used with DBSCAN, which can speed-up the algorithm especially for low-dimensional data. The advantage of the proposal compared to such space-partitioning algorithms is not clear at the moment.

- Presentation should be improved. There are inaccurate sentences as reviewers pointed out. I also recommend revising plots, as fonts are too small and hard to read.

Overall, the current manuscript is not ready for publication.

justification_for_why_not_higher_score: The weaknesses of the paper that I have listed above are crucial and should be addressed for publication of this paper. I strongly recommend addressing these issues, that is, experiments on high-dimensional data, discussion and comparison with related space-partitioning methods, and revision of presentation.
Decision: Reject