Hierarchical clustering with dot products recovers hidden tree structure

Summary

For agglomerative clustering, this paper proposes a method where the affinity of clusters at each hierarchy is naturally visualized as their height. Section 2 describes its statistical model (a nonparametric model based on first order moments) and the clustering algorithm derived from it (Algorithm 1) is presented. Algorithm 1 is extremely simple (needless to say, this simplicity is a virtue of the proposed method), and is only a slight modification of many of the standard agglomerative clustering methods. However, despite its simplicity, the deep insights of the algorithm are explained in Section 3. Remarkably, very roughly speaking, the affinity of each hierarchical cluster is expressed as the height of its dendrogram, which, under certain assumptions, asymptotically approaches its true value. Finally, Section 4 describes the effectiveness of the proposed algorithm on real data, as well as its limitations, and provides code for follow-up studies. Note: I was not able to understand the details (techniques in the supplementary material) of some of the theoretical analysis in this paper within the initial review period. For Theorem 1, I was able to follow the outline of its key mathematical induction. For Theorem 2, I have not been able to grasp the details. However, the statements in the text are very reliable, and the authors have made an effort to add intuitive explanations to these theoretical results.

Strengths

- This paper is an excellent combination of a simple methodology and deep insights behind it. Needless to say, methodological simplicity is a virtue of the proposed method at this time. - The phenomenon of affinities between clusters at each level of hierarchy appearing visualized as heights on the dendrogram will be the attractive results for a wide range of readers, both theoretically and in terms of application. - It is excellent that the theoretical results (Theorem 1 and Theorem 2) are carefully interpreted in Section 3.3 as detailed intuitions. - Authors also share the code (Jupyter Notebook) for re-experimentation with the community, which is a great contribution to subsequent researchers. - In Section 5, the paper explicitly mentions the slightly stronger assumption of the proposed model and clarifies for what cases (what data) it has a negative impact. This is an essential finding in the development of science and technology.

Weaknesses

I have not been able to find any convincing weaknesses for this paper in the initial peer review. However, I have some concern about whether the statistical model assumed by the proposed method is causing model specification for data with so-called multiple clusters. I have inquired about this concern with the author in the following question. If the concern is resolved, I have not found any major weakness in this paper.

Questions

I am very grateful to authors for sharing very insightful and interesting ideas. I have some questions because this paper contains simple methodology but very surprising (and perhaps intuitively non-trivial) results. These questions are the reason I am not giving this paper a higher score at this time for its overall rating. These may simply be my lack of insight, but perhaps a brief mention in the text or in the supplementary material would make the advantages of the proposed method clearer to some readers. I would be very grateful if a response from the authors could clear up some of my questions. (1) Another aspect of the model assumptions (Section 2.1). It is very interesting to note that the only model mentioned in this paper is the chain rule by Equation 3, and everything else can be expressed nonparametrically. However, does Equation 3 imply that "all data are i.i.d. samples from a single cluster (a single nonparametric distribution that assumes only first order moments)"? In other words, is there model misspecification occurring for data sets with multiple clusters (e.g., a 2-cluster Gaussian mixture model)? If we use the chaining rule in Equation 3 to marginalize the random variables at each node in turn from the terminal node to the root node of the tree structure, this may be a model in which all data are sampled i.i.d. from some nonparametric distribution with identical mean values (only the first order moments are specified). Is this intuition wrong? If this intuition is correct, then surely the "PCA does not do anything wrong" in the second half of Theorem 2 (Equation 9) makes a lot of sense. Conversely, if the proposed statistical model is such that it has multiple clusters (like a Gaussian mixture model, where each cluster tends to gather data at its center), then it is highly counterintuitive that "still PCA does not do anything bad". In summary, my question comes down to whether the proposed model assumes a one-cluster i.i.d. model. (2) The validity of greedily searching for the closest affinity pair in row 3 of Algorithm 1. From the viewpoint of an agglomerative algorithm, it seems quite reasonable to greedily look for the closest affinity pair in line 3 of the algorithm. On the other hand, from the perspective of a statistical model, a probabilistic selection (i.e., Markov chain selection), such as finding a single pair from a categorical distribution weighted by affinity proportions, also seems natural. Does the fact that this row 3 is a greedy selection play an important role in the theoretical analysis in section 3? The actual intent of this question can be attributed to something that is also closely related to question (1), as follows. For example, if the true data distribution is like a Gaussian mixture model with multiple clusters, is it possible to recover the true data distribution (mixture model structure) by, for example, truncating the tree at some hierarchy (resolution) of the tree structure obtained with the proposed model? In other words, would there not be a misspecification problem as a statistical model? My rough intuition tells me that it is not easy to recover the structure of a statistical model in the case of a greedy merge. I also know that such a topic is a bit off the author's actual intent for this paper. However, the question arises because I am very curious as to why the statistical model behind the proposed method leads to very good properties (Theorem 1 and Theorem 2) in Algorithm 1. (3) (Very minor.) Reason why DAG is first introduced. Is there a reason why when the tree model is introduced in lines 68-69, it is broadly defined as directed acyclic graphs (DAGs) rather than restricted to binary trees? DAGs are often used as the structure of Bayesian networks. Are there any indications that the theoretical results of this study for binary trees may be extended to DAGs or Bayesian networks? Finally, once again, I appreciate your sharing of some very interesting ideas.

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.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

The paper carefully questions the weaknesses of the proposed method in Section 5. It is well explained what kind of data and in what cases the proposed method is unlikely to show its true value. On another point, I am slightly concerned whether the statistical model in the proposed method implicitly assumes i.i.d. data with a single cluster, as I have asked the authors in my question. However, this concern may be addressed by a response from the authors.

Summary

This paper presents new analysis and perspectives on one of the most widely used clustering algorithms, hierarchical agglomerative clustering (HAC). In particular, the authors consider the relationship between a particular generative process of data and a dot-product based linkage of HAC. Empirical and theoretical results are presented.

Strengths

This paper presents an interesting perspective on a widely studied clustering algorithm. I don't think that the intention of the paper is to yield surprise that for certain kinds of data there might be one linkage function (dot product) that works better than others. Rather I think the intention of the paper is to draw connections between clustering models and HAC. In particular, I see the strengths as: * Connections between the model for latent tree structures in Eq. 1 and Theorem 2 and dot-product based average linkage * Connections between models for trees with heights and HAC. * Empirical analysis of some of the theoretical scaling properties: Figure 2.

Weaknesses

I think that the paper could be improved in the following ways: * W1. I think that more explicit treatment of Eq. (2) and (3) would improve the presentation; e.g., showing where/why these hold under the model in Eq. (1). * W2. My understanding is that Lemma 4 & Prop 1 looks quite similar to standard HAC proofs about reducibility? I think it would greatly improvement the treatment of the result to explain the differences / distinctions. Apologies if I have missed something. * W3. While the evaluation metric seems quite reasonable, might also be interesting to show results across other metrics such as dendrogram purity or similar metrics. I see this as a minor point though. * W4. In the advent of distributed (typically relatively low) dimensional representations from deep neural encoder models. I wonder if the authors could provide perspective on "theorem 2 says that affinity estimation error vanishes if the dimension p grows faster enough relative to n". E.g., should we think of this method as appropriate in such circumstances where p is likely in range of 128-1024 or so and n might be in the millions or billions?

Questions

* Q1. How could the presentation be modified to address W1? * Q2. (W2) How does reducibility related to the proofs of Lemma 4 / Prop 1? * Q3. (W3) did you consider using any other metrics for evaluation? If you were to add another metric to provide a new slice of information, which metrics/measurements would you want to add? * Q4. Please see W4

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

Yes.

Summary

The authors discuss a phylogenetic reconstruction problem (I'm not 100% clear on the exact problem, though) and suggest to use the dot product as a measure of similarity (or affinity). In particular, they seem to use the UPGMA algorithm (Alg. 1) where similarity is defined by dot product (scaled by $1/p$). The proposed method is shown to recover the underlying tree structure with guaranteed accuracy under reasonable theoretical assumptions. Empirical results indicate good performance in a number of cases where the ground-truth hierarchy is known.

Strengths

- the theoretical guarantees appear very strong

Weaknesses

- presentation should be improved so that the problem under study is clearer - it seems that methodologically, there is no novelty beyond proposing to use the dot product as a similarity measure in the UPGMA method - limited set of benchmark methods in the empirical part

Questions

I am familiar with phylogenetics and probabilistic graphical models, but despite reasonable efforts, I fail to be able to comprehend the modeling setup. The authors should clearly explain what the model in Eq. (1) means. In particular, the meaning of the latent variables $Z_i$, and the two mappings, $X(Z_i)$ and $S(Z_i)$, that generate the observed data from the latent variables and the random noise, $E_i$, should be explained. Another general thing I was left wondering is the logic behind the dot product as an affinity measure. It is common to use the cosine similarity $\cos \theta = \frac{\langle x, y\rangle}{||x|| ||y||}$, where $\theta$ is the angle between the vectors $x$ and $y$, and $\langle x, y\rangle$ is the dot product between them. In other words, the cosine similarity is the dot product scaled by the product of the Euclidean norms of the two vectors. Such scaling can be motivated by noting that without normalization, the dot product has the peculiar property that, for instance, $\langle Cx, x\rangle = C \langle x, x\rangle$, i.e., for $C>1$, the vectors $Cx$ and $x$ are more similar (in terms of the dot product) to each other than the vectors $x$ and $x$ (so the vector $x$ to itself). For normalized vectors, the dot product and the cosine similarity are identical. (Further, for normalized vectors, the Euclidean distance equals $\sqrt{2 - 2{\langle x, y\rangle}}$ so it too is a monotonic function of the dot product.) I would appreciate some comments on the motivation of using the dot product as opposed to commonly used metrics such as the Euclidean distance or the cosine similarity, and on when it is likely to be appropriate (and when not). detailed comments: - I suppose some would prefer to use the $x \cdot y$ notation for dot product since $\langle x,y \rangle$ often denotes the (more general) inner product - p. 2: "distributional properties $\mathbf{X}$": should this be "... of $\mathbf{X}$"? - p. 7: When you say you compare against the UPGMA method, you should say what distance metric you use in UPGMA. In fact, it would be interesting to see the results of UPGMA (and other methods) based on various distance metrics (dot product, cosine, Euclidean, ...). And indeed, why not include more phylogenetic methods such as Neighbor-Joining (NJ), etc? - appendix C, proof of Lemma 2: the second line of the displayed equation should have a factor 2 in front of the dot product term (as in $||x+y||^2 = ||x||^2 + 2 \langle x,y \rangle + ||y||^2$)

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.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

See above

Summary

The paper studies hierarchical agglomerative clustering under a specified generative process for the underlying data vectors. The main focus of the paper is similarity based clustering that deals with inner products between vectors rather than computing pairwise distances that has been studied before. The goal of the paper is to provide recovery guarantees for the underlying tree structure. The paper provides such guarantees under their specified generative model and they bound the maximum merge distortion by the affinity estimation error (see Theorem 1). Moreover, they provide tradeoffs for the estimation error based on the dimension of the data vectors and the sample size. Finally, the authors test their method in terms of runtime and quality against several other methods from the literature.

Strengths

+hierarchical tree recovery is not a well-understood problem so the overall research direction is interesting +dot products are used a lot in real-world applications so having analyses based on them is important +the flavor of the guarantees seem to be towards the right direction for what we would mean "hierarchical tree recovery" +the technical aspects of the proofs

Weaknesses

-The generative model should be better explained and compared to other previously studied models for hierarchical clustering. In particular, it was not clear to me how to think of your model given that Hierarchical Stochastic Block Models and well-clusterable graphs are defined and seem more natural to me, see e.g. papers below: Cohen-Addad, Kanade, Mallmann-Trenn, Mathieu: "Hierarchical clustering: Objective functions and algorithms" Chatziafratis, Mahdian, Ahmadian: "Maximizing Agreements for Ranking, Clustering and Hierarchical Clustering via MAX-CUT" Manghiuc, Sun: "HierarchicalClustering: O(1)-Approximation for Well-Clustered Graphs" So overall, having a better exposition and examples for why this particular model you proposed is a natural one, would help the readers a lot. -The difference from other papers that focus on distance-based hierarchical clustering is important for the mathematics, but conceptually the algorithm is very related. So here the innovation in terms of conceptual contribution is slightly weakened. However, from technical viewpoint there are interesting ideas the paper introduces. -In the statement of the Theorems 1 and 2, I missed some interpretaion of the results and especially some comparison to related work on distance-based methods. Do we learn something interesting by this dot-product analysis? How are the dimension/sample/estimation tradeoffs different that those other papers? -The numerical experiments: I am not sure they convey the benefits of your algorithm in terms of estimation error and recovery. In Table 1, I would clarify what are the most significant advantages of your algorithm as currently it is hard to grasp.

Questions

From above: Q1: Do we learn something interesting by this dot-product analysis and how are the dimension/sample/estimation tradeoffs different that those other papers that did distance-based analyses? Q2: Perhaps easy, but giving more evidence to motivate your particular hierarchical tree model would be appreciated. Q3: Technical question: Perhaps to help illustrate some of your techniques/ideas, it would be helpful to instantiate your model to a small-depth hierarchy. Say there are only 2 or 3 levels like you had in some of your experimental datasets (S&P500, 20Newsgroups etc). Can your theorems be more interpretable in this scenario?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

I like the paper and I find that the authors addressing the concerns mentioned above will significantly improve their paper. I don't find any major limitations, apart from better motivating their model, comparing it with the existing ones, and better illustrating their Theorems and what we learn from them (in comparison to distance-based methods).

Summary

The paper discusses a new perspective on hierarchical clustering using the dot product as similarity measure instead of some distance. Under mild conditions on the probabilistic graphical model that generates the data, the proposed algorithm is shown to faithfully recover the underlying tree geometry. Surprisingly, the theoretical results show that the performance of the approach does not suffer, but instead benefits from high-dimensional data.

Strengths

The paper is well written and all theoretical results and definitions are accompanied by intuitive explanations (e.g., lines 84-90, lines 159-166, Fig. 1, or Sec. 3.3). This makes the paper accessible to an audience not versed in graphical models, for example. The results seem quite promising; it is noteworthy that the authors also included "negative" results for the S&P500 dataset, and that they made an effort in investigating the limitations of the proposed method.

Weaknesses

I see very little weaknesses in the paper (see below for a list of typos). There are only few points unclear (see Questions below). The only concern I have is that the results claim that the performance of the method improves if the dimensionality of the data increases. This is probably caused by the mixing condition, which ensures that more dimensions deliver more relevant information. This assumption is quite questionable in my opinion, as usually more dimensions do not reveal substantially more information about the underlying distribution. As an example, consider natural images: going from low resolutions to higher resolutions may at first improve clustering performance, but at some point increasing the resolution will bring only diminishing returns. The reason is that, as the resolution increases, also the correlation between dimensions increases, which is in contrast to A1. I would appreciate seeing results based on, e.g., lower numbers of TF-IDF features to understand how this affects clustering performance. Another concern is that Fig. 3a and 3c seem to be inconsistent. In 3a, at the position of comp.windows.x, there are three dark blue squares, one light blue square, and (maybe?) a hidden pink x. In 3c, the top five topics contain two dark blue and two light blue squares. Please check if there was a mistake in generating the figure. ## Minor: - line 56: "interpretation to in all..." - line 78: "distributional properties OF $\mathbf{X}$"

Questions

- In line 102, it is not clear why $\mathbb{E}[< Y_i, Y_j>|Z_1,\dots,Z_n]$ is conditioned on all $Z_n$ - What is the meaning of the operator $O_{\mathbb{P}}$? - In Table 1, the results for simulated data do not depend on whether PCA was applied or not. Is this caused by the fact that the dimensions are independent? - Since the PCA version of the algorithm operates on fixed dimension $r$, it is not clear to my why in (9) an increase of $p$ should bring any benefit. Could you expand on that?

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

The authors clearly outline the limitations of their study, which is highly appreciated. A possible further limitation of the method is that, apparently, good performance guarantees can only be given for high-dimensional data, which is slightly counterintuitive. Societal implications are not to be expected.

Thanks!

Thank you very much for your detailed answer, especially to my main concern. I agree with your observations that large $p$ helps to decrease noise (even in the absence of mixing), and that mixing is a realistic assumption in many practically relevant cases. I will, for now, keep my score, but may revise it based on the discussion with other reviewers.

Still not following the intuition about dot product affinity -- but overall, changing my rating to accept

Thanks for the response. The clarification about the underlying model is helpful. However, I'm still equally puzzled by the intuition behind usingt the dot product (rather than its normalized version, the cosine similarity) as an affinity measure. I had indeed not read Appendix E since I expect that any content that is essential for understanding the main ideas presented in the paper are included in the main paper (otherwise one can asek what is the point of the page limit). In Appendix E, the authors provide some remarks on the relationship between dot product and cosine similarity -- concluding, e.g., that under norm constraints, cosine similarity and dot product affinity approximate each other (Thn. 3), which is (on an informal level) obvious as pointed out in my review above. The authors interpret this as showing that the cosine similarity can work well under such constraints. Still, it doesn't help in building intuition about why dot product would be a sensible choice in cases where the norms are not nearly uniform. In any case, having also read the other reviews and the rebuttals related to them, I can only conclude that the theoretical results (mainly Thm. 1) seem to support the authors' claims about the good performance, and since this is (at least to my intuition) somewhat unexpected, I believe the paper is worth publishing and exposing to the wider community's evaluation. Considering all of the above, I am changing my rating to accept.

Thank you for your detailed and insightful answers.

Thank you for your detailed and insightful answers. The author has given satisfactory answers to my three questions. I now have a better understanding of the current value of this study and new perspectives on future research. I would like to maintain my score as per my initial positive impression.

Author Response

I would like to thank the authors for their detailed response. My initial positive score remains the same.