Divide-and-Cluster: Spatial Decomposition Based Hierarchical Clustering
Authors: Narendra Ahuja
Akshat Sharma
Divyam Goel
Venue: Submitted to ICLR 2023 (2023)
Keywords: Unsupervised Learning
High-dimensional features
World Centered Clustering
Points Centered Clustering
Hierarchical Clustering
Complexity
Minimal Spanning Tree

Abstract: This paper is about increasing the computational efficiency of clustering algorithms. Many clustering algorithms are based on properties of relative locations of points, globally or locally, e.g., interpoint distances and nearest neighbor distances. This amounts to using a lower dimensional space than the full dimensionality $D$ of the space in which the points are embedded.  We present a clustering algorithm, Divide-and-Cluster (DAC), which detects local clusters in small neighborhoods obtained by recursive tessellation of space, and then merges them hierarchically, following the Divide-and-Conquer paradigm. This significantly reduces computation time which may otherwise grow nonlinearly number $n$ of points. We define locality as hypercubical neighborhoods in a recursive hypercubical decomposition of space, represented by a tree. Clusters are detected within each hypercube, and merged with those from neighboring hypercubes while traversing up the tree. We expect DAC to perform better than many other algorithms because (a) as clusters merge into larger clusters (components), their number steadily decreases vs the number of points, and (b) we cluster only neighboring components. The ordering of component appearances also simultaneously yields a cluster hierarchy (tree). Further, our use of small neighborhoods allows piecewise uniform approximation of large, nonuniform, arbitrary shaped clusters, thus avoiding the need for global cluster models. We experimentally verify the correctness of detected clusters on a variety of datasets, posing a variety of challenges, as well as show that DAC’s runtime is significantly better than representative algorithms of other types, particularly for increasing values of $n$.


Under review as a conference paper at ICLR 2023
DIVIDE-AND-CLUSTERR SPATIAL DECOMPOSITION BASED HIERARCHICAL CLUSTERING
Anonymous authors Paper under double-blind review
ABSTRACT
This paper is about increasing the computational efficiency of clustering algo- rithms. Many clustering algorithms are based on properties of relative locations of points, globally locally, e.g., interpoint distances and nearest neighbor dis- tances. This amounts to using less than the full dimensionality in which the points are embedded. We present clustering algorithm, Divide- and-Cluster (DAC), which detects local clusters in small neighborhoods and then merges adjacent clusters hierarchically, following the paradigm. This significantly reduces computation time which may otherwise grow nonlinearly in the number n of points. We define local clusters as those within hy- percubes in a recursive hypercubical decomposition of space, represented by a tree. Clusters within each hypercube neighboring hypercubes to form clusters of the parent hypercube at the next level. We expect DAC to perform better than many other algorithms because (a) as clus- ters merge into larger clusters (components). their number steadily decreases vs the number of points, and we cluster (b) only neighboring (c) components (not points). The recursive merging yields cluster hierarchy (trec). Further, use small neighborhoods allows piecewise uniform approximation of large, nonuni- form, arbitrary shaped clusters, thus avoiding the need for global cluster models. We present DAC's complexity and experimentally verify the correctness of de- tected clusters on several datasets, posing a variety of challenges, and show that DAC's runtime is significantly better than representative algorithms of other types, for increasing values of n and D.
of the space
tree level are merged with those from
INTRODUCTION
Finding clusters formed by n data points D-dimensional space very frequent operation in machine learning, even more in unsupervised learning. This paper is about increasing the computational efficiency of clustering. The notion of cluster is fundamentally a perceptual one; its precise definition, used implicitly or explicitly by clustering algorithms, varies. Given set of points æ ..,, Fn. in a D-dimensional space (x: E RD), clustering is aimed at identifying dif- ferent groupings/componntis of nearby points according to the definition of cluster being used. In this paper, we model a cluster as a contiguous overlapping set of small neighborhoods such that: points in each neighborhood are distributed (nearly) uniformly, the cluster shape is arbitrary, and their closest approach any two clusters are separated by distance larger than the distance between nearby within-cluster neighbors. Many common clustering algorithms are based on assumptions about global properties of point positions, such as distances between points or sets of points, as in K-means. Another class of algorithms uses local structure, defining locality via edge-connectivity in different types of graphs defined by the points. Other algorithms use nearby points, e.g., lo- cated within chosen size neighborhood. There are a few approaches that make full use of the D-dimensional geometry, e.g., those based on Voronoi neighborhoods (Ahuja & Tuceryan 1989); while they work well, their constituent algorithms (e.g., for Voronoi tessellation) are available for only small values of D.
In this paper, we present a clustering algorithm, called divide-and-Cluster (DAC), that detects clus- ters in small local neighborhoods formed by hierarchically decomposing the D-space and then

---

Under review as a conference paper at ICLR 2023
peatedly grows them outwards, by remerging chopped parts of cluster stretching across neigh- borhood boundaries. This implements the Divide-and-Come Conquer paradigm of computation. We use hypereubical neighborhoods formed by recursive hypercubical tessellation of the D-space, rep- resented by a tree. Clusters straddling boundaries of neighboring hypercubes/nodes at one level combined form clusters of their common parent node the next level, in bottom up tree traversal. Once the recursive merger is completed at the tree root level, all detected clusters are agglomeratively merged, closest clusters first, form a cluster hierarchy.
We evaluate our algorithm against other algorithms in the following ways. (1) Correctness of De- tected Clusters: We compare detected clusters in the standard, Fundamental Clustering Problems Suite of 2D and 3D datasets (FCPS), which poses a variety of important clustering challenges. (2) Runtimes: We compare runtimes on datasets having a range of n and values. (3) Downstream Task: We observe the impact of DAC as clustering substitute in CNN.
The advantages of the proposed algorithm lead to the following contributions:
1. Spatial Divide-and-Conquer: Our approach recursively divides the D space in using fixed, predetermined geometric criterion. This helps divide the points without using additional computa- tion that may be needed to evaluate the division criteria, The resulting logarithmic run-time increases with E. DAC also offers a new mechanism for trade-off among n. D and F.
2. Point Components: DAC's time complexity over global/points based algorithms further bene- fits from the use of components of points instead of individual points: (a) limits computation of closest distance between neighboring components to mutually visible points (e.g.. half) of the com- ponent boundaries (instead of all points in the components), and (b) the agglomerative generation of hierarchical clusters need only merge entire, closest components, implying complexity in terms of the smaller number of components vs points.
DAC's local cluster detection allows arbitrarily simple local models of clusters, avoiding cluster wide global models. For example, by repeated division, DAC can increasingly improve the validity of piecewise uniform approximation of cluster density.
3. Cluster Shape:
4. Cluster Density:Compositional detection of a cluster from its contiguous small pieces also allows detection of clusters of arbitrary shapes, thus avoiding shape models such as isotropy/compacteess used by K-means.
In the following, we first review related work (Sec 2), followed by spatial decomposition (tree rep- resentation) used to define DAC (Sec 3), DAC algorithm (Sec 4), computational complexity (Sec 5), experimental results (Sec 6), and limitations and conclusions (See 7).
2 RELATED WORK
Clustering obtains partition of the points that minimizes a cost function chosen to reflect the types of clusters to be detected, often along with some user specified parameters. An example of cost function is the Sum of Squared Error (SSE), the sum of the squares of distances of points from their cluster centers. Hierarchical clustering approaches derive an agglomerative tree (hierarchy) of clusters formed by repeatedly merging, bottom up, lowest cost first. Partitioning algorithms form the hierarchy by repeatedly splitting the clusters, maximally reducing the cost at each step. Following are some broad categories of algorithms:
Graph-based clustering algorithms typically use a partitioning strategy on graph of data points with weighted edges. Examples are Minimal Spanning Tree (MST) and Shared Nearest Neighbor (SNN) clustering algorithms. MST defines edge weight as distance between two points and removes k highest weighted edges from the MST of the graph to obtain & clusters, where k is a parameter. SNN defined similarity of two points as threshold overlap in nearest neighbors (where K' nearest neighbors are found for each point), similar vertices are connected, and connected components are discovered to return the clusters.
Spectral approaches aim to partition graph such that similar points together and dissimilar are not. It defines a similarity matrix that contains similarity score for each pair of points, and uses this matrix find the graph cut with minimum cost.
2

---

Under review as a conference paper at ICLR 2023
Density-based clustering algorithms start with some core clusters (e.g.. individual points) and gradually grow each cluster by including proximal points until a growth criterion allows. Examples include DBSCAN (Ester et al. 1996), OPTICS (Ankerst et al. 1999) and Mean shift based (Cheng) 1995) clustering. DBSCAN defines a core cluster as consisting of those points that have more than minimum number minpoints of points in their E-neighhourhoods. Each core cluster grows by including all points lying in E-neighbourhoods of its current points, and repeating this process until no growth is possible. The process then repeats from a new unclustered point until all data points are clustered.
Mesh-based clustering algorithms quantize the data space into small units (mesh cells) and aggre- gate all points within one mesh cell into one indivisible unit. This may be interpreted as working on a coarse resolution, where the algorithm is unable to distinguish between points in the same mesh cell. Then, all computation is performed on the mesh cells rather than the data points. The time complexity of the operations then is function of the number of mesh cells, not the number of data points. This presents a trade-off between the cluster quality (coarser meshes would produce poorer clustering) and the time required to compute the clusters (proportional to number of mesh cells). Some examples are STING (Wang et al. 1997). CLIQUE (Agrawal et al. 2005) and WaveCluster (Sheikholeslami et al. 1998).
Approximate clustering algorithms offer trade-offs between complexity and the degree to which the detected clusters satisfy the clustering criteria. Other algorithms focus on hierarchical, single linkage clustering. Yet others present variations of tree representations but not directly impacting or related to the algorithm we propose. Examples include (urttnn et al. (2013); Abboud et al. (2019); Liu et al. (1970); [Bruvvka (1926). Because of this difference their objective, we do not consider them any further in this paper.
3 TREE REPRESENTATION
For concreteness, we first discuss the case of D = 3, the octree representation (Shi & Malik 2000
Jackins & Tanimoto 1980 Meagher 1982 Zahn 1971 VanderPlas] 2016; Liao al. 2004 of
the occupancy of space by non-point objects. obtained using recursive decomposition of the space into octants. Given an object, we start with the entire space single (starting) cube (block). At any stage, if a block under consideration is completely contained within the object it is left alone; otherwise, it is divided into its eight octants which are added to a pool of blocks to be processed; this procedure is repeated for each unprocessed block until the pool is empty (all blocks are either completely within or completely outside the object, or they are of the smallest, specified (preci- sion/resolution level) mesh cell size.
This recursive subdivision yields an octree description of the occupancy of 3D space. Each block corresponds to a node in the tree. The root (level 0) of the octree represents the largest size block, representing the limit of object size that can be represented. Successive levels represent blocks whose side lengths halve with each lower level, does the separation between adjacent blocks. We denote the side length of the smallest block, the mesh cell, by unity. For the largest (universe) hypervolume [0, EJD, the maximum number of levels L then is log2 E. An octree may also have fewer than L levels if all object blocks turn out to be of side lengths larger than unity; the nodes corresponding these larger blocks form octree's leaves and may occur any of the L levels. We label leaf node black/white if its block is completely contained within the object/free space. If node neither black nor white, then is labelled gray. meaning has both black and white descendants. Black nodes not contained inside other black nodes are termed "maximal" black nodes.
To generalize to the case of points in the D-dimensional space, we recursively divide the space using D-dimensional hypercubes. Each dimension 'x' of the universe hypervolume [0, EJ is split into two halves by the half plane r = E/2. This partitions each D-dimensional block into 2D children hypercubes, each of half the edge length, and 1/2" times the volume, of the parent block, yielding hypertree of order 2". To associate a child node's ' id with one of its 2d possible positions (r,r, 0. 2, 2n - 1). we use the binary representation of r; itself as the node's id. We associate the lower/upper half of each dimension with 0/1. This maps all the 2n children to unique positions inside the parent (Fig a)).
3

---

Under review as a conference paper at ICLR 2023
Maximal Black Nede
Component
=
[1,1] 3
Bixck Node
Point
= [1,0] 2
Cumpunvnt 1
comgonentis
Figure I: Overview: (a) A parent node's decomposition into its 2D children. A child node's id is binary number in which each bit corresponds one dimension and is 0(1) if the child position is in the lower(upper) half in that direction. For example, the bottom right child's ' id is 10, being in the upper half along x-axis and lower along y-axis. (b) An illustration of the major steps DAC via an image. The smallest squares stand for mesh cells. Black nodes are the largest hypercubes filled with black mesh cells. Neighboring Black nodes (nonsiblings in hypertree) concatenate to form the largest hypercube or Maximal Black Node (MBN) and MBNs concatenate to form the largest black region, or component corresponding to a dense cluster (Component 1). During hierarchical clustering, components merge in the order of increasing intercomponent distance. (c) Boundary construction. The mesh cells in red constitute mutually visible boundary between blue and green nodes. Only these cells are involved in computing distance between the nodes. The yellow node has holes that expose mesh cells in the center of green node to the green visible boundary.
ALGORITHM
4.1 INSERTION OF POINTS INTO THE HYPERTREF
The first step is to associate each data point with the smallest block (mesh cell unit hypercube) leaf nodes the hypertree. Points are inserted a top-down traversal the tree to the leaves. Since storing all 2D children of non-leaf nodes is infeasible for large D, and DAC requires only black grey (non-white) nodes, we explicitly store only these nodes. This can achieved using, e.g., a Linked List of non-white child nodes, Hash Map of (key, value) pairs with E {0, 1, 1, 2,2 2 1} key and the child node as value, respectively. We use the latter as it has a faster look up time.
4.2 FINDING MAXIMAL BLACK NODES (MBN)
We call the black nodes not contained any other black nodes as Maximal Black Nodes (MBN). They may occur at the leaf level at an interior level. The latter are identified in depth first traversal, by coloring every parent black if all its children are black (Appendix [A.]- procedure set color). and then deleting all the children (Appendix [A.2] procedure find maximal black nodes). MBN are represented by (m...., where (n2) denotes the number of maximal black nodes (Fig Tb)).
4.3 COMPUTING THE ADIACENCY MATRIX OF MBN
MBN adjacency matrix holds the shortest distance between each pair of MBN, which is the shortest distance between pair of mesh cells in the two MBN. compute these distances, we exploit the fact that these mesh cells must lie on the mutually visible boundaries of the nodes.
The shortest distance between two MBN is given by the straight line distance between two mutually visible (nonmaximal) black nodes at the boundaries of the MBN located. To identify these boundary node pairs, we start at the MBN and move up the hypertree. At each next level, we use the boundaries of sibling nodes to update the adjacency matrix of the two MBN and compose the parent node boundary using the sibling node boundaries. Fig (bb) illustrates these steps, which are also given in the following top-down, recursive fill matrix procedure:
4

---

Under review as a conference paper at ICLR 2023
1. Traverse the tree to access the leaves.
2. Adjacency Matrix: From each leaf, traverse bottom up to recursively compute the adjacency ma- trix values for the parent node using the mutually visible boundaries of all pairs of parent node's s non-empty children. For a pair of sibling nodes [$1.82) their visible boundary is computed as the union of their mutually visible pairs of faces. A sibling's face is visible if it is in those dimensions (axes, directions) along which the sibling is shifted. In the binary representation of a child hyper- cube, a 0/1 represents the child's position coordinate along dimension being in the lower/higher half along that dimension; if the siblings {si, 82) have coordinates 0 and 1, respectively, the visible boundary would include the higher boundary face of {si} and the lower boundary face of {s2) The union of these face pairs from all directions constitutes the visible boundary shared between the two siblings. Then the distance between the siblings is the minimum of the distances for each pair of cross-sibling mesh cells on the visible parts of the boundaries. If less than the current entry, the adjacency matrix is updated (Fig
3. Boundary Construction: A node boundary consists of mesh cells which are visible when view- ing the node from along positive and negative along each axis. A node's boundary is composed from the appropriate boundaries of each of its children. For example in 2D (F). the boundary of the bottom-left child B1 may extend the bottom left boundary of the parent While doing so, the boundary of sibling hidden behind each child node (say B2) also need to be checked in case mesh cells from B2 are exposed through any holes in Bj. Starting at the root of the hypertree, this recursive boundary construction ends at black node by returning its boundary and updates to the adjacency matrix (Appendix A.4 procedure get node boundary). Appendix A.4 procedure ger node boundary gives details.
4.4 CREATING COMPONENTS BY MERGING MBN
This step identifies neighboring components, formed by MBN separated by unit distance (i.e., pixels in one MBN have neigbhoring pixels in the other), represented by (S1, C2.... (n.). A component is the largest set of MBN such that any two MBN can be reached from each other following a chain of neighboring MBN. An MBN thus represents point cluster split across different hypertree nodes, corresponding to neighboring hypercubes. This reduces the original problem of clustering points into one of clustering components. Since the number of components is usually much smaller that the number of points, it reduces the time required to extract clusters (Sec 5).
To find the neighboring MBN, locate unit distance entries in the MBN adjacent matrix, and merge the corresponding MBN using a union find algorithm. This yields an identifier f'(-) for each MBN. Two MBN belonging to the same component have the same f.) value. The adjacency matrix is updated to hold the pairwise distance between components: each entry (i,j) in the original matrix updated with (f()).(()) giving a new, component adjacency matrix (ng X ne).
4.5 COMPONENT CLUSTERING
The components obtained are embedded into a graph as vertex nodes. The weight of the edge connecting two vertices is the shortest distance between their mesh cells, which must be for two mesh cells lying on mutually visible boundaries of the components. Hierarchical clustering can then be done using graph based clustering algorithm. We use the MST clustering algorithm. We first compute the MST of the component graph to form a single component (cluster) connecting all nodes with minimum length (weight) edges. Then, as in Zahn (177I). we remove the longest edge to create two components. By repeatedly removing an edge with the largest weight, we repeatedly increase the component (cluster) count by one. This yields a cluster tree, from which any desired number of clusters i may be obtained by removing the k longest edges, along with their adjacency matrix. This algorithm amounts to a single linkage hierarchical clustering algorithm, but the links are between MBN (clusters of points) and not points themselves, and therefore usually much smaller in number.
5 TIME COMPLEXITY
The algorithm consists of the procedures:
5

---

Under review as a conference paper at ICLR 2023
1. Insertion of points into the hypertree: Each of the data points is inserted at each of the logz(E) tree levels, resulting in a time complexity of O(n log E). Storing each data point and non-white nodes (neglecting the smaller needs, e.g,, for hash storage) leads space complexity of O(n + Now), where Naw indicates the number of non-white nodes in the hypertree.
2. Coloring (set color procedure): As each black node is accessed recursive call is made to color each non-white child. Hence, the time complexity is O(Nww). Since the color has to be stored for each non-white node the space requirement is (NN.)..
3. Marking maximal black nodes (find maximal black nodes procedure): This step involves depth first traversal of the tree extract maximal black nodes and associate them with their children nodes. Hence both time and space complexities are (NNww)
Computing the adjacency matrix (fill matrix procedure): This step consists of two procedures
(a) Computing distance between points on the visible boundary: between pairs of mutually visible mesh cells on the boundaries of the two sibling nodes and updates the sibling udjacency matrix Hence the time complexity is ((S4²), where SA denotes the surface area of the sibling nodes. To store the visible boundaries requires ((SA) space.
This step computes the distance
(b) Boundary construction: The time and space required to insert mesh cells from child nodes into the parent's boundary OSSA of the parent boundary). However, this is dominated by the identification of mesh cells exposed to the boundary via holes in its neighbours, which grows with the child nodes surface area as O(SA log(S (Appendii 4b)).
5. Merging maximal black nodes into components: This step consists of two procedures
(a) Finding maximal black nodes at a unit distance from each other: This requires traversing the adjacency matrix and has time complexity O(ng), ny being the number of maximal black nodes.
(b) Merging proximal maximal black nodes into components: This requires running a union find algorithm over the maximal black nodes and has time complexity O(m log(na)) where m is the number union operations, i.e. the number of pairs of maximal black nodes at unit distance from each other. In the worst-case, this complexity could become Onn log(m)))-
This step involves running the traditional MST algorithm on the compo- nent graph. The time complexity to obtain the cluster tree is O log(n.)). To extract (4) disjoint clusters, the (k- 1) longest edges are removed. Clusters can be obtained by running any graph traversal algorithm (BFS/DFS) on the disjoint cluster tree.
Component clustering:
The set color and find maximal black node are grid-based procedures. Like all such algorithms, their time complexities are dependent the grid size and hence the spatial extent of the data, and independent of the number of points in the tree. However, the additional operations of computing pairwise distances between visible boundaries, and boundary construction are AS?). In practice, since many mesh cells combine to form components (instead of being independent, isolated mesh cells), this yields a significant empirical speed up.
The overall time complexity is the dominant value among the complexities of various procedures above, namely among the terms On (n-log ()O WN OSSA²),
Om,)), (m log( (n))) and On? log((n))) The exact complexity achieved will depend on the data at hand. The worst-case time complexity occurs in the rare case when most mesh cells occur very low- dimensional subspace (extreme case: points lined up along an axis), forming very thin components with mesh predominantly lying at the component boundaries and few in the interior. This takes away the advantage of the reducing the computation due to intercomponent distances being determined by the (usually smaller number) of boundary cells. The time complexity of the various pre-hierarchy (hierarchical clustering) steps is then dominated by the large value of SA (nx) which approach n. In comparison, mesh based algorithms such as STING have a worst case time complexity of O()), density based algorithms such DBSCAN have a worst case time complexity of O(n?) and graph based techniques such as spectral clustering have a worst case time complexity of O(n3).

---

Under review as a conference paper at ICLR 2023
6 EXPERIMENTS
Our experiments are aimed at verify the properties of DAC. (1) In See 6.1 we first evaluate the correctness of DAC clusters in the Fundamental Clustering Problems Suite (FCPS) which are easy to evaluate visually due to FCPS dimensionality. (2) We next evaluate DAC for expected run time speedups one representative algorithm from each of the three categories reviewed See on the FCPS datasets for increasing number of n with fixed D (3) We then evaluate the quality of DAC clusters in high dimensions by matching its clusters with those detected by CNN. (4) Finally, evaluate DAC's s run time in high dimensions for an increasing number of n, as well as for various combinations of n and D.
6.1 EXPERIMENTS WITH FCPS DATASETS
We have experimented with four datasets. The challenges offered by these datasets and our cluster- ing results on them are presented below.
6.1.1 HEPTA DATASET
This dataset includes clusters with different densities. To ensure separability among different dat- apoints, the number of grid points must be above the number of datapoints. We scale up the grid a 50x50x50 cube (of 125000 grid points), with a vertex at the origin. Fig 2 shows the clus- ters obtained by DAC; in addition, it illustrates the operation of DAC by showing outputs at two intermediate stages of the algorithm.
Figure 2: Hepta Dataset: Left to Right (1) Inputs points, (2) Maximal black node extracted by DAC. Points of the same color belong to maximal black node.
(3) Components extracted by DAC, points in each component shown in the same color. Note that the set of one-step reachable maximal black nodes merged into larger single component, indicated by more mesh cells of the same color. (4) Final seven (A: = 7) clusters.
6.1.2 CHAINLINK DATASET
The chainlink dataset consists of two intertwined tori that not linearly separable. Like any suitably designed proximity based algorithm, DAC able to segregate the two tori clusters (Fig 3)
6.1.3
TARGET DATASET
The target dataset contains large clusters with 4 small outliers. Note that DAC can detect
the four outlier clusters (Fig.
6.1.4
ENGYTIME DATASET
The Engytime dataset is a mix of two Gaussian clusters, one isotropic with unit variance, and the other, inclined one, has variances 2 and 1.6 along its principal axes.
6.2 COMPARISON OF RUN TIMES
To test the speedups expected from DAC, we compare runtimes of our algorithm for increasing num- ber of with three other algorithms: DBSCAN (density based), spectral clustering (graph based),
7

---

Under review as a conference paper at ICLR 2023
Figure 3: Input data (Fig and 3 from left), and final clusters (Fig 2 and 4) produced for the chainlink and target datasets.
Figure 4: Clusters detected by DAC in the Engytime dataset. Left to Right: (1) Input data points, (2) Maximal black nodes, (3) Components, (4) Output clusters for k = 2 Note that separation between the two clusters at their closest approach is comparable to their local, within-cluster hearest-neighhor distances; hence they are detected as a single cluster, not two as (as per cluster definition in Sec 1).
and CLIQUE (mesh based). Since we do not have datasets with varying number of datapoints for the same cluster geometry, we modify the FCPS datasets by increasing the density of each of the datasets to obtain three versions having n 5, 000, 50, 000, 500, 000. We run all four algorithms and record their runtimes. Fig shows how the runtime of each algorithm increases with n. We see that DAC has the slowest increase.
Figure 5: Runtimes of four different types of clustering algorithms on the FCPS datasets modified to obtain three different values of n: 5,000, 50,000 and 500,000, by increasing cluster density while maintaining cluster geometry. The plots show runtimes for the algorithms CLIQUE(blue), DB- SCAN(red) and DAC(green) for different n (shown on log scale). In general, DAC has the slowest rate of increase and its runtime advantage over other algorithms increases with n. The runtime for spectral clustering is too large to in the figure.
6.3 CLUSTER QUALITY AND RUN TIME PERFORMANCE IN HIGH DIMENSIONS
Quality: We also evaluate DAC by matching them with the clusters detected by an independent algorithm a CNN classifier. The dataset we use is a of 10,000 features (datapoints) 512-dimensional space. F is output of the convolutional layers of a VGG-16 CNN classifier, with input being the 10-class CIFAR-10 test dataset. The output can be modeled as containing a cluster for each of the 10 classes. The classifier has been reported to yield test accuracy A of 93.54% We test our algorithm by obtaining the best clusters in F, and then computing the average label-purity of the clusters. The P value we have obtained using DAC is 95. 79% which is almost the same as A. The reason P is better than A is likely due to the fact that we are detecting clusters in the test data, not predicting them from training data, like CNN classifier has to), This agreement validates the quality DAC clusters because they match the clusters obtained by CNN which indeed correspond to class clusters (Fig
8

---

Under review as a conference paper at ICLR 2023
Run Time: Finally, compare the run times for the same four algorithms for the same CNN data for increasing n ((igg 6 (c)), and for different combinations of n and D. for a synthetic dataset consisting of cluster hypercube, surrounded by another cluster in hypereubical ring (Fig (d)). The maximum values of n and D we choose are determined by the CPU memory limits.
rlen pointo turrdd noko Lompor cnly
vs parity plot
0-1
2.40
8.4
3:55
23
15
nomber clastere extracted
Runtime on the DW classifier dataset
Runtime on the Rypercube dataset
"LECE
data points
data points
Figure 6: (a) DAC's low time complexity results in part from the expectation that the number of components increase slower than number of points, as seen in the observed increases here. (b) Validation of the correctness of clusters detected by DAC in high-dimensional data. The best clusters (35 here) detected by DAC in a 512-dimensional space for features output by CNN for CIFAR 10 dataset. This achieves 0.95 purity of labels (labels unknown to DAC but known to CNN) which is also the accuracy obtained by the CNN. This suggests that the clusters detected by DAC and CNN are similar. (c) For the dataset in (c), observed run times of different algorithms for increasing n. The runtime for Spectral clustering is too large to fit in the figure. The runtime and performance of the Clique algorithm is highly dependent on it's parameters, and its runtime too large to in the figure when its parameters chosen to get reasonable clusters. (d) Run times observed for a synthetic dataset number of and d (here hypercubical ring cluster surrounding hyeprcube core cluster, for varying choose both freely). Again, Spectral clustering and Clique times are out range as (c). In both (c) and (d), DAC shows the slowest rate of increase with n for all values of D).
6.4 NUMBER OF COMPONENTS EXTRACTED BY DAC NUMBER OF POINTS
Towards verifying that the number of components is indeed much smaller than the number points (which translates into runtime advantage for DAC, as discussed in Algorithm and Complexity sec- tions), we show in Fig Gla) a) that the observed numbers of maximal black nodes as well as components in the modified chainlink dataset indeed grows very sublinearly with n.
7 LIMITATIONS AND CONCLUSIONS
We have presented an algorithm for local global detection of clusters. Its advantage over many other clustering algorithms becomes particularly pronounced increases. The complexity results we have presented are for typical (average) cases; as we have noted the main paper and more in Appendix, the worst case, degenerate data, although rare, may wipe out DAC's advantages. Further, since there is not much large-D) D data with ground truth available, evaluation of DAC on large D data has been difficult. We have used CNN classifier output for this purpose, treating CNN's class label outputs as ground truth. This is incorrect but may be adequate the classifier accuracy high. We plan to further test the performance of DAC by integrating it incorporating into complex learning algorithms requiring clustering.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Amir Abboud, Vincent Cohen-Addad, and Hussein Houdrouge. Subquadratic high-dimensional hierarchical clustering. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' d'Alché-Buc Buc, Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14. 2019, Vancouver, BC. Canada, pp. 11576 11586, 2019. URL htttp:://proceeddnng nwwriieuippp.. httpppppee//1///aaaaaae.. d98c 5455765666 61 9bd99b8111
9111999811733333 7cb31 Abst html
Rakesh Agrawal, Johannes Gehrke, Dimitrios Gunopulos, and Prabhakar Raghavan. Automatic subspace clustering of high dimensional data. Data Mining and Knowledge Discovery, 11(1): 5-33, 2005.
Narendra Ahuja and Mihran Tuceryan. Extraction of early perceptual structure in dot patterns: integrating region, boundary, and component gestalt. Computer Vision, Graphics, and Image Processing, 48(3):304 -36,,, 1989.
Mihael Ankerst, Markus M Breunig, Hlans-Petes Kriegel, and Jörg Sander. Optics: Ordering points to identify the clustering structure. ACM Sigmod record, 28(2):49-60, 1999.
Otakar Borûvka. O jistém problému minimálním [About certain minimal problem], pp. 37-58. 1926.
Yizong Cheng, Mean shift, mode seeking, and clustering. IEEE transactions on pattern analysis and machine intelligence, 17(8):790-799, 1995.
Ryan Curtin, William March, Parikshit Ram, David Anderson, Alexander Gray, and Charles Isbell. Tree-independent dual-tree algorithms. In Sanjoy Dasgupta and David McAllester (eds.), Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research. pp. 1435-1443 Atlanta, Georgia, USA, 17-19 Jun 2013. PMLR. URL [tR[/ttttps///rcceddinn
mir press /v2///2/////// wt2//urrtinn....... i.tttinn1.hmmll
Martin Ester, Hans-Peter Kriegel. Jörg Sander, Xiaowei Xu, et al. A density-based algorithm for discovering clusters in large spatial databases with noise. In kdd, volume 96, pp. 226-231, 1996.
Chris Jackins and Steven L Tanimoto. Oct-trees and their use in representing dine-diimessioal objects. Computer Graphics and Image Processing, 14(3):249-22 270, 1980.
Wei-keng Liao, Ying Liu, and Alok Choudhary. A grid-based clustering algorithm using adap- tive mesh refinement. In 7th workshop on mining scientific and engineering datasets of SIAM international conference data mining, volume 22, pp. 61 61-69, 2004.
B. Liu, Y. Xia, and Philip Yu. Clustering Via Decision Tree Construction, pp. 97-124. 01 1970. ISBN 978-3-540-25057-9, doi: 10. 10.1007/11332199555
Donald Meagher. Efficient synthetic image generation of arbitrary 3-d objects. In Proceeding of the IEEE Conference on Pattern Recognition and Image Processing, volume 473, 1982.
Gholamhosein Sheikholeslami, Surojit Chatterjee, and Aidong Zhang. Wavecluster: A multi- resolution clustering approach for very large spatial databases. In VLDB, volume 98, pp. 428 439, 1998.
Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on pattern analysis and machine intelligence, 22(8):888-90) 2000.
Jake VanderPlas. mst clustering: Clustering via euclidean minimum spanning trees. J. Open Source Softw. 1(1):12, 2016.
Wei Wang, Jiong Yang, Richard Muntz, et al. Sting: A statistical information grid approach to spatial data mining. Vldb, volume 97, pp. 186-195. Citeseer, 1997.
Charles Zahn. Graph-theoretich methods for detecting and describing gestalt clusters. IEEE Transactions computers, 100(1): (0(1))68-866 1971.
10

---

Under review as a conference paper at ICLR 2023
A APPENDIX
A.1 SET COLOR
Set color
Input: root of the tree
1. if (edge length of root = =1): root.color
// Black nodes are numbered 1.
else :
hain_of_black_chhleeee = 0
for children (cl) of the root:
num_of num_of_black, children += Set color(cl).
_blacckchildreen
if (num_of_bi liarin_f_blac...om bback_children== == 2²):
root.color = 1
// all children are black
else root.color 0
2. return root.color
A.2 FIND MAXIMAL BLACK NODES
Find Maximal Black Nodes
Input: : root of the tree Output Maximal black nodes Y₁ Yy " (n.) denotes the number maximal black nodes
Initialization : node =1
1. if(root.color 1):
set_node_id(rot, node id) //recursively sets the node_id for nodes rooted root
node id root, isblack True
node id = node id +
2. else
children (cl) the Find Maximal Black Nodes(cl)

---

Under review as a conference paper at ICLR 2023
A.3 FILL MATRIX
Representation of node boundaries: : In D-dimensional space a node has 2D boundaries, two in every dimension. We dictionary to maintain the node boundary wherein the boundary corresponding to the i-th dimension is stored with the key (2i) and (2i + 1) (similar to how heaps are represented using linear arrays). Hence the node boundary dictionary contains the keys 0, 1, 2D-22D-222 -
Fill Fillmix
Outline: top down procedure compute node boundaries fill the adjacency matrix Recursively
computes and the input node boundary to update the matrix
Imput: root of the tree (root)
Output: Boundary
input node (roof), updated matrix 4.
Initiallization : E it de,otees the number maximal black nodes). All entries are initiallised to + oo
1. Pase When root black node, return boundary.
root. tsblack: return wtw_noood_boundr(rererr d None)
2. Find the boundary of all child nodes to construct the boundary of the node roof. boundaries & // empty dictionary
for rank, child in root, root.children: boundaries(rank| fill_ matrii((((()))
3. Compute the visible boundary between every pair of children and use to update the matrix A.
for rank1 in woo..chllrre..keee...... keys():
boundary1 boundaries(rank1] fetch child boundary.
location1 binayy_epressenattonnnnnn
for rank2 root.children. keys():
boundary2 boundarles(rank2]
location2 = binary reppresentation((nkk)
relative_position = location2 location1
visible_ 1, visible_2 =
// contains nodes on the visible boundary of child with rank1 and rank2.
for dimension, direction inrumerate(elative_posttto
if(directton
visible_1 spperd(houndary1 [2*dimension+ 1)
visible_ wpp.pppdddddd/uuuurrarr.. [2*dimension))
if(direction -1::
visible_ 11 1.apperd(boouddary [2*dimension]] ))
visible apperddbouundrry2 [2*dimension ))
Update matrix using boundaries visible_1 and visible_2.
4. Construct roat boundary using child node boundaries.
5. return root boundary.
The fill matrix procedure contains the following steps:
1. Recursively compute the node boundaries of all children
2. Use the child boundaries to update the adjacency matrix with the minimum distance be- tween maximal black nodes:
Worst-case time complexity: Worst case time complexity arises when the visible bound- ary is computed between each pair of siblings at each level the hypertree. At a certain level in the tree, each pair of siblings (with edge length say (?)) can share at most (D) faces, each containing at most (E) D-1 mesh cells. Hence, for this visible boundary we
compute distance between (D- (5) D-1) pairs of mesh cells. There are (22) such pairs of
siblings inside the parent node. This gives a time complexity of O O((²)) (())))(())))) (D(E)
(DD))) for all sibling pairs in one parent. However multiple such parent exist at each level in the tree. The parent with side length (s) belongs to the level I. loga (
where (E) denotes the side length of the root. The level (L) contains 2DD nodes, each with edge length (s). Hence the time complexity at each level in the tree given by O D2 (D-i() = O(D2 D-2), Summing over all levels s = E, ..... ...... gives
the total time complexity of this step
12

---

Under review as a conference paper at ICLR 2023
E D-2
+..))
TC 0 D2ED. ED--2
(I)
= ED EE (1+
Note that the time complexity grows as the square of the surface area of the hypertree.
3. Update the adjacency matrix using the visible boundary between a pair of sibling nodes:
Once the visible boundary between pair of sibling nodes is computed in the fill matrix procedure, the pairwise distance between every mesh cell on the boundary is used to update the matrix A. The algorithm uses the maximal black node identifier set during the find maximal black nodes procedure to find which entry of the matrix is to be updated.
Procedure to update adjacency matrix A given pair of visible boundaries
Input:
Visible boundaries R,, P,. adjacency matrix
Output: : Updated adjacency matrix A.
1. For cell_ in B, For cell_2 2 in B mib_nod__1,bb_not distance <- euclidean distance(cell__ cell_2)
cell_ id, cell_2.node maximal black node identifier
If distance Almb_node_ foadd__]llb_mmteeeee 1][mb_node__]
baabb_node_lllbb..... _ distance // update matrix entries
distance
4. Construct the root boundary using the child node boundaries
This procedure computes the boundary of non-black nodes given the boundary of all chil- dren nodes.
For every child, the while(dimension D) loop used to iterate over all the neighhouring siblings which may contain points to be included on the boundary. For each child (rank: 1) and dimension (d) the procedure contains three steps
(a) Insertion of points from the current boundary the parent boundary The entry to be updated in the parent's 's boundary determined via the child's position inside the parent.
Worst case time complexity For a parent with edge length (s), each face may con- tain a maximum of (s--1) mesh cells. Hence, the time complexity of adding points from the children boundaries would be (-- per face, giving time complexity of O(D DD-1) for each parent with length (s).
(b) Inserting exposed points from the neighbouring siblings Let us indicate the bound- aries of the current child (rank_1) and the sibling (rank_2) as (B1) and (B2) respec- tively. To determine whether some mesh cell from B3 visible through holes B1 we must determine if there exists a mesh cell n. in Bi which has the same coordinates as n in dimensions other than (d). We accomplish this by creating scalar encoding E(.) for each point on B₁ and Bz. The encoding is function of the mesh cell, parent edge length s and the dimension parameter (d).
To motivate the use of the encoding function
propose the following lemma. B2 would not be exposed through holes in B, iff there exists a mesh cell n. E By such that E(n.) = E(n)
Lemma Any mesh cell
Proof: : Let the child (rank 1) be at position (ln, 4,... Ip-1> 1) and have edge length
5. As the child with rank (rank 2) is the neighbour along the dimension (d) it has the

---

Under review as a conference paper at ICLR 2023
Construct node boundary using child node boundaries
Input: node root, boundaries children root: boundaries
Output: : Boundary
node root: boundary
Initialization boundary &
for rank_1 boundaries keyy):: iterate over non-white children
boundary_1 boundaries(rank.1 1]
binary_rank bhnar_eepresentaiionnnnkk]]]
dimension 0
transform 1 used to access neighbours of child with rank_1 using the xor operation.
while (dimension D)
boundary key 2*dimension binary [ which entry of the boundary is to be filled.
boundarybounndryy. key] boundarylboundaryKes key] u boundary boundary.(bouunday.. |[bonndaryy...... _e_y] extend boundary rank_2 = rank_1 transform //toggles the bit at position (dimension) to give the neighbouring child
if child with rank exists:
boundary 2 boundaries(rank.2 2]
encoded_ encoded_boundaryy encode_ boundary (boundary_1 iariiaar___obuudiiae [boundary_ dimension)
for point boundary 2|boundary key]:
encoded_poime encode_poiie pooode_point(point, dimension)
encoded_ _ponn not in encoded_ bouuddrr_
boundarylboundary.kk key] boundarybbuundary.e)) [point]
encoded_ wwwdddoooudddrrreoee hrnnndariinser(encddee_ppppi
else:
binary_rank. hary_rrnn_ssbbingggg iinary_rerreeettaiionnnnn._ binary of the empty sibling (rank2)
boundary_key 2*dimension hamaaryrrnnkssbbinggdieeee
encoded encoded_boundaryy boundary
for point boundary_1:
encoded point encode, ponttpooint dimension)
if encoded_point not bounddd_boundry:
boundarylboundary.
key] boundarylboundary.ke [point] mncoded_bounddry..oo www.inn(eecoddd__ooiiiiooe
dimension +=1
transform *= 2
// the next power of would produce the next neighbour of child (rank_1)
return boundary
encode_poine
Input: point (p,, P.. "", Po-.) E R", dimension (d).
Output The point encoding. 1. < edge length of caller node
2. encoding p, + p,e p,o² Pan eat + Panee e + "t pos D-1
return encoding

---

Under review as a conference paper at ICLR 2023
position (lv, 11: -p- 1, la 11+1, . 1D-1). Let the mesh cell n,, be the coordi- nate (40 + po. 11 + p1. .1D-1 + PD-1) and the mesh cell (n) be at the coordinate (4 + 4 i,,.. ......... La-1 14-1,
+ dd la+1 + d.-1.- -.-..----p --- + ip-1). The difference between the encoding the mesh cell follows from the definition of the encoding function.
E(n.) F(n)) -(n in) 8. (pr -1) 4... sd1 (ps-1 id-1)
(2)
+ +dt (pd+1 - id+1) +... ....... (pD11- -
Note that each (pR, denotes the offset of the mesh cells from the node position and are whole numbers in the range s0... Hence the encoding function can be interpreted as a base-s representation of the mesh cell offsets, i.c. (po.PI. PD..)- The two encodings would be equal iff for all (k + d) p is i.e. when the mesh cell (nz) has the same coordinates as (n) in all dimensions other than (d). This ensures that the mesh cell (n) is not exposed to the visible boundary through holes in boundary (B1).
The lemma shows that if we encode each mesh cell on (B1) beforehand we can determine any mesh cell on (B2) must be included in the parent boundary by simple search in the set of encodings of all mesh cells on (B1) (denoted by E B1))- Note that performing coordinate comparison to determine which mesh cell goes into the parent boundary would require an O(D) computation per pair of mesh cells on (B1), (B2). This would give a time complexity
O( Bg D), where [Bal denotes the size of boundary B1. However, if we use the encoding function we would only require O + B2l) D) time to encode both the boundaries and O B2) log((B:l)) time to search for matching encoding in the set E(B1). Hence, the time complexity for this computation would scale as O A log(SA) rather than O(SA²), where SAA denotes the surface area of the child nodes.
certain level in the tree, for each child (rank_1) and dimension (d) to determine mesh cells exposed through holes we must compute mesh cell encodings on the boundary face along dimension (d). A face of the boundaries (Bi), (B2) can contain a maximum of D-1 mesh cells. Encoding each mesh cell requires (D) time, giving a time complexity O(D ( D-1). Once mesh cells on (B₂) have been encoded we search for encoded mesh cells E(B2) in the set E E(B1), resulting in time complexity of (({)) D-1 log (()) ))))) ))
Worst case time complexity
O ( D log(s)). Accumulating over all (rank_1, d) pairs gives the time complexity of O(D- D ($) (s) in the tree. The node with side length (s) belongs to the level L = logg (E), where (E) denotes the side length of the root. The level (L) contains 2DD nodes, each with edge length (s). Hence the time complexity each level in the tree given by O(2 D. D-1 log(s)) = O E log(d)) Summing over time complexity at each level in the tree, i.e. = E, E ... gives the cumulative time complexity as
1-aD-11 ( log(s)) O log(s)) for each node with side length
TC = D² ED (log(F))
log(F./2) +...)
+
E
E/2
= O(D2 ED log( (E) (1+++++
O(D3 E log2 (E))
A.4 GET NODE BOUNDARY
As the base case of the recursive fill matrix procedure, the get node boundary procedure computes the boundary of black node by merging the boundaries of its child nodes. This procedure differs from part 3 of fill matrix as it computes the boundary of a black node, which is shaped as hypercube. The procedure is described below.
2

---

Under review as a conference paper at ICLR 2023
Outline: find the boundary of a black node in certain direction.
Input: Black node y, boundary direction (d)
Output : Node boundary B;
Initialization B +
if sum (d) == D: // each entry in (d) is return +p
2. Base case : Boundary of mesh cell.
If edge length of y, 1:
if (d) None: return B, (key: key E (0, 1,, 2D 1)) boundary in every direction is Y,
else:
for dimension, direction in enumerate(d):
If direction 1=
1 dimension + direction] = Y;
return B.
3. for rank, node in y, children. items():
direction (eaaar__eppeeentationrrnnk))
(d) is None
directions direction! = d] (- 1) assign directions where no node boundary is required.
mode_boundary get_node__tt www.nneennoonnrnnoooooooooo direction) get boundary of child node in the specified
direction recursive call.
for key, item in boudddrrtrtytt.s // expand node boundary using child's node boundary. B extend)etted(((emm
return B.

---

Under review as a conference paper at ICLR 2023
To obtain the boundary of node, compute the boundary of each child node using recursive call but with a (d) parameter corresponding to its rank inside the parent. The function is called with the parameter boundary direction (d) which is a D-dimensional vector whose entries indicate which boundary to be fetched. For certain dimension, corresponding (0) entry in (d) would fetch the left boundary, (1) entry would fetch the right boundary and (-1) signifies that boundary is to be returned in this dimension.
As example consider the following wwo-dimensional node with edge length 2 called with (d) [0.1], which means that the left and upper boundary is required along the x and y-dimension respectively. For this purpose we only need the left boundary from the child with rank [0,0] (the bottom-left child), the top-left boundary from the child with rank [0,1] (the top-left child) and the top boundary from the child with rank [1,1] (the top-right child). This is accomplished by matching
the child rank and (d). The top-left child is called with boundary direction = [0,-1], which signifies that only the left boundary needed along the x-dimension. Others child nodes are called similar manner.
Called with [0, 1]
Called with d [-1, 1]
Called with d = [0, -1]
Called with d [-1,-1]


Reviews:
[{"review_id": "uvM_4eL2XNk", "reviewer": "Reviewer_snwo", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "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.", "strength_and_weaknesses": "**Strengths**\n* 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. \n* The algorithm has novel characteristics and the authors have taken care to develop a method suited for the kinds of data they are considering. \n\n**Weaknesses**\n* 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? \n* 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. \n* 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.\n* 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?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "a3U2dcdVKzQ", "reviewer": "Reviewer_1fFd", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "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.", "strength_and_weaknesses": "I really like the paper is not overselling the proposed method, the limitations of the method is discussed in the paper. \n\nWeaknesses:\n\n1. 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.\n\n2. 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? \n\n3. 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.\n\n4. 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.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "N91xBez-3ML", "reviewer": "Reviewer_Sm2r", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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)).", "summary_of_the_review": "The main claim of the paper is that efficiency has been increased. However, since \n- recent work is not cited,\n- the approach is rather complicated, and\n- it's not clear in which situations/domain such an approach would result in more meaningful clusters\n- the detected clusters are not evaluated by comparison with other techniques (recent or old)\nI don't really know whether the claim is supported. \n\nSome 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.", "strength_and_weaknesses": "+ The authors have procedures used in their algorithm in detail \n- 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\n- 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 ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "4ct2SAqVAi", "reviewer": "Reviewer_ZhK4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "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. ", "strength_and_weaknesses": "Strengths:\n\n- 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.\n- The algorithm returns reasonable results on the datasets tested. The clustering quality and efficiency seem to be promising, if not sufficient.\n\nWeaknesses:\n- 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.\n- 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.\n- 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.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject