Expected Probabilistic Hierarchies

We thank the reviewer for their valuable feedback. We updated the manuscript based on the feedback with important text modifications highlighted in blue. In the following, we address their comments.

Comment: Similarity to FPH.
Response: While our work builds upon the work of Zügner et al., it addresses multiple drawbacks of FPH. We prove that Soft-Das is a lower bound of the discrete Dasgupta cost (Sec. 4.2) and present a simple example where it fails to find the minimizing hierarchy. Based on these observations, we propose our cost functions, the expected metrics (Sec. 4.1). We motivate them by showing that the optimal hierarchies align with their discrete counterparts, unlike Soft-Das (Sec. 4.2). Furthermore, we introduce an unbiased subgraph sampling scheme, allowing us to employ both, FPH and EPH, to vector datasets. In an exhaustive empirical evaluation, we demonstrate the superiority of EPH on graph and vector datasets.

Comment: Weighted example where FPH fails.
Response: We decided to show the unweighted $K_4$ graph as an example since it is the most simple case. We included another weighted example with four nodes in Appendix A.7. As in the previous case, EPH finds the minimizing hierarchy, while FPH fails to do so.

We hope that we have satisfactorily addressed the reviewer's questions and concerns. We are happy to address any remaining remarks.

Thanks for your response. I have further questions about the subgraph sampling procedure.

The process of sampling edges from the edge distribution $P(v_i, v_j)$ entails an $\Omega(n^2)$ complexity (for vector data). Is this approach less scalable compared to the node-sampling method employed in [1]? Intuitively, the node-sampling technique does not require the preparation of weights for all edges, potentially having a much better scalability.

[1] End-to-End Learning of Probabilistic Hierarchies on Graphs

We want to thank the reviewer for their feedback and questions. We updated the manuscript based on the feedback with important text modifications highlighted in blue. In the following, we address their comments.

Comment: How much more expensive is this process compared to the baseline?
Response: We include the runtimes for the experiments in Tab. 18 and Tab. 19 in the Appendix. While EPH is slower than the heuristic-based baselines, it performs similarly to the optimization-based baselines HypHC and FPH. EPH has a shorter runtime than HypHC on the graphs and large vector datasets. Furthermore, it matches the runtime of FPH for large vector datasets, as the number of sampled hierarchies is set to 1.

Comment: How does the quality change with changes in the number of samples used?
Response: We show the normalized Dasgupta cost across a different number of sampled hierarchies and edges in Fig.3. As expected, the Dasgupta cost decreases when the number of samples increases. For the edges, we can already observe an improvement towards the average linkage algorithm when sampling $\sqrt{n}$ many edges. For the number of sampled hierarchies, we observe that on most of the datasets, 20 samples are sufficient. However, even when using only one sample, EPH outperforms FPH, the second-best method:

We hope that we have satisfactorily answered the questions by the reviewer. If so, we kindly ask the reviewer to consider raising their scores. We are happy to address any remaining concerns.

We want to thank the reviewer for their constructive and valuable feedback. We updated the manuscript based on the feedback with important text modifications highlighted in blue. In the following, we address their remarks and questions.

Comment: How do the proposed cost functions relate to downstream tasks of clustering, and how do the continuous cost functions relate to the discrete ones?
Response: To analyze the relationship between the different cost functions and downstream tasks, we performed an external evaluation, as detailed in Appendix B.2. Here, we flatten the hierarchies derived from the different methods and compare the resulting clusters with the available ground-truth labels (see Table 12).

To perform an external evaluation on graph datasets, we use two synthetic HSBMs. Our goal was to answer two questions: First, how well do the inferred hierarchies align with the ground-truth hierarchies? And second, how well do the distances correlate between graphs and hierarchies? To address the first question, we calculated the Normalized Mutual information (NMI) across the different levels of the hierarchies. For the second question, we compute the Cophenetic correlation based on the shortest path and Euclidean distances of DeepWalk embeddings (see Table 4). Exp-Das and Exp-TSD almost perfectly recover the first three levels of the ground-truth hierarchy and achieve a notably high cophenetic correlation comparable to the ground truth. In both cases, Exp-TSD achieves slightly better scores, implying a better capability to recover the ground truth.

Comment: When are such methods used in practice? E.g., are there End-to-end applications?
Response: End-to-end trainable hierarchical clustering methods are particularly useful in an offline setting where results are not required in real-time. Practical use cases include jet physics and genomics [1] or clustering of products in E-commerce [2], where linkage algorithms are commonly used.

Comment: More details about the line: "To obtain these for EPH and FPH, we take the most likely edge for each row in A and B..."
Response: After the training process, EPH yields two probabilistic hierarchies, represented as matrices $\mathbf{A}\in[0,1]^{n\times n'}$ and $\mathbf{B}\in[0,1]^{n'\times n'}$. In these matrices, each row corresponds to a categorical distribution, i.e., $\mathbf{A}$ and $\mathbf{B}$ are row-stochastic matrices. As we are interested in discrete hierarchies, we convert these into discrete counterparts, $\mathbf{\hat{A}}\in\{0,1\}^{n\times n'}$ and $\mathbf{\hat{B}}\in\{0,1\}^{n'\times n'}$, respectively. While one approach is to sample an entry in each row weighted by their probability, we select the entry with the highest probability, i.e., the most likely edge. We refined this in the updated manuscript.

Comment: Are the trees produced by EPH binary?
Response: EPH allows non-binary hierarchies, providing more flexibility. While the Dasgupta cost favors binary hierarchies, TSD does not. We can observe these in our qualitative evaluation in Fig. 4. While the hierarchies inferred using Exp-TSD have multiple branches, the hierarchies inferred by Exp-Das tend to be binary.

We thank the reviewer again for their comments and feedback. We hope that we have satisfactorily answered the reviewer's questions. We are happy to address any remaining concerns.

[1]: Macaluso, Sebastian, Craig Greenberg, Nicholas Monath, Ji Ah Lee, Patrick Flaherty, Kyle Cranmer, Andrew McGregor, and Andrew McCallum. "Cluster trellis: Data structures & algorithms for exact inference in hierarchical clustering." In International Conference on Artificial Intelligence and Statistics, pp. 2467-2475. PMLR, 2021.

[2]: Brinkmann, Alexander, and Christian Bizer. "Improving Hierarchical Product Classification using Domain-specific Language Modelling." IEEE Data Eng. Bull. 44, no. 2 (2021): 14-25.