Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors consider the problem of inferring a hierarchal clustering of dataset instances.  The problem has typically been approached as either a discrete optimization problem or a continuous, relaxed form of the discrete problem.  In the discrete setting one searches over all possible hierarchies - with each instance having a single internal parent node and each internal node (other than the root) having a single internal parent node.  In the continuous setting, nodes are softly assigned to more than one parent node.  The authors focus on probabilistic hierarchical clustering, which maintains a distribution over discrete hierarchies and introduce Expected Probabilistic Hierarchies (EPH) as a means to optimize two hierarchical clustering cost metrics - Dasgupta cost and Tree-Sampling Divergence - in expectation.  They show that maximizing these two cost methods in expectation is consistent with the non-probabilistic variant, introduce a method for efficiently sampling hierarchies as the number of instances grows and demonstrate the effectiveness of the method on some real datasets and synthetic datasets.
strength_and_weaknesses: Overall, I thought the paper was well written and had a clear and natural development.  The main idea is a logical extension of prior work, but to the best of my knowledge is novel and is a non-trivial extension. The main theoretical results are intuitive and provide a nice justification for the proposed sampling procedure.

While the paper was well written, I do think the authors could have devoted more time to explaining the reasons for using the Dasgupta cost and TSD?  Is it because prior art already existed for them?  Also, I am not an expert in probabilistic hierarchical clustering methods and the distinction between EHC and Zugner et al.’s FPH method was unclear.  In addition, I would liked to have seen a more formal description of the proposed algorithm, including the subgraph sampling procedure.  EPH seems primarily like a way to model distributions over hierarchies under different cost metrics. The reader is left to infer the steps needed to actually optimize over this model.

clarity,_quality,_novelty_and_reproducibility: I am a bit confused by a few aspects of Theorem 1.  Does the equality make some assumption about the matrices A and B?  It seems to me if these matrices had zeros, then not every tree structure could be sampled.  In an extreme case, the zeros could cause the induced hierarchy to be disconnected.  Along these lines, where do the initial values for A and B come from in practice?  In the experiments section it seems as if a uniform transition distribution is assumed.  Similarly, where do the edge weights w_ij connection nodes i and j come from? For a dataset of n instances, do we need to provide (and normalize) over all n choose two pairs of instances?

Figure 1 did not provide much value.  I don’t think it was referenced or explained in the paper and the caption did not provide any context or explanation. As I said above, I really would like there to be a formal algorithm description.  In its current presentation, there are too many gaps for me to reasonably recreate the experiments.  

I found the experiments section a bit difficult to follow.  I appreciate that the authors wanted to be exhaustive in their comparison, but the discrete single, average complete and ward linkage based approaches did not seem like reasonable methods to compare with in the main results section.  They are heuristic and don’t try to optimize the Dasgupta or TSD metrics. Can you provide a justification for why “we use n′ = 512 internal nodes, compress hierarchies using the scheme presented by Charpentier & 
Bonald (2019), and use 10 and 32-dimensional DeepWalk embeddings (Perozzi et al., 2014) on the graphs for methods that require features”?  These steps were quite unclear to me and I am not able to discern their effect on the experimental results.  Why did you choose n’=512?  

The tables seem to show that EPH finds low cost hierarchies.  Can you comment on the run time needed for the different methods?  If the EPH takes 10 hours, but the other methods take only 5 minutes, then I’d argue the comparison should be based on computation time rather than fixing 5 random seeds.  

Figure 3 is very noisy.  What’s happening with the citeseer dataset?  Why doesn’t score decrease as function of increased number of samples? Also, are there error bars on the markers in Fig 3?  I would hope the variance in dasgupta costs decreases as num sampled hierarchies is increased too.
summary_of_the_review: Overall, I like this paper.  The idea of sampling over a distribution of hierarchies is appealing and I think the authors did a nice job of illustrating how to use the probabilistic model to optimize over the dasgupta cost and TSD.  However, I’m not sure if the paper in its current form is quite good enough.  With additional clarity of the procedure and of the theoeretical result, it could be good enough.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper considers hierarchical clustering with expected objectives.  This problem aims to optimize the expected objective (e.g. Dasgupta cost or Tree-sampling divergence) over a distribution of discrete hierarchies. They show that this problem has the same global objective as its discrete counterpart.  They propose a new method called the expected probabilistic hierarchies (EPH), which is an end-to-end gradient-descent-based optimization by using a differentiable hierarchy sampling. They also scale this method to large graphs with an unbiased subgraph sampling approach. They show that their algorithm performs well on real-world datasets.
strength_and_weaknesses: Strengths:
1. They propose an expected optimization problem over hierarchies.
2. They propose a new end-to-end learning framework for this problem.
3. Their method outperforms baselines on real-world datasets. 

Weaknesses:
1. The proposed two expected optimization problems seem identical to their discrete counterparts.
2. How would this new method compare with the method based on iterative sparsest cuts for Dasgupta's cost?
clarity,_quality,_novelty_and_reproducibility: This paper is well-written and easy to understand. The method in this paper is original and reproducible. However, the techniques used in this paper are more or less standard and similar to previous works. 
summary_of_the_review: The problem considered in this paper is essentially the same as its discrete counterpart. They propose a new end-to-end learning framework for this problem while the techniques are quite standard. Their method achieve better performance than baselines while the improvement is very marginal and the objectives of some baselines are different from the evaluation objective.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper builds on a recent modelling of the hierarchical clustering of [Zugner et al. 2021] to learn discrete structures by gradient descent.
The structure is modelled using two row-stochastic parameter matrices: $A$ parametrizes the probability distributions of each sample of belonging to a cluster ($n$ distributions); $B$, a strictly upper triangular matrix, parametrizes the hierarchy between clusters, i.e. the probability of a cluster of being a child of another cluster up in the ordering ($n'-1$ distributions).

While [Zugner et al. 2021] optimizes soft-version of the objectives Das and TDS, the current work proposes to optimize a Monte Carlo approximation of the expected objectives using a perturb-and-MAP sampling scheme, more precisely leveraging the gumbel-softmax trick.
Because in the considered parametrization each probability distribution is an independent categorical, this optimization procedure is unbiased in the space of continuous hierarchies. 

The method is finally applied on graph and vector data, and shown to outperform existing methods when optimizing the metric used for evaluation (not when evaluating accuracy).
strength_and_weaknesses: ### Strengths
The paper is very well-written: the motivation is convincing and the contributions are stated clearly. The theoretical and model contributions are somehow novel, as they correspond to a novel application (i.e., hierarchical clustering) of well-known techniques and results in discrete optimization.

### Weaknesses
1. Several times in the paper (e.g., abstract, introduction) it is claimed that **"the optimum of the expected scores is equal to the optimum of their discrete counterparts"**. This statement **is not accurate**: the optimal score is the same (and this is what is proved in the appendix) but the optima are the same only in the case that the optimum of the discrete score is unique (i.e., not degenerate).
Furthermore, **this claim coupled with the statement that "EPH provides an unbiased estimate of Exp-Das and Exp-TSD" misleads the reader to think that the overall optimization is unbiased w.r.t. the discrete hierarchy**, which is not true (see discussion in [1] and [2]). Although these claims are partially rectified in Section 4.3, under Limitations, I encourage the authors to clarify all these points from the beginning.

2. Regarding the chosen parametrization of the hierarchies from [Zugner et al. 2021], I have a concern about the modelling of the cluster hierarchy by B.  Because it is row-stochastic, the only constraint enforced is that the probabilities of a non-root node of being a child of the other nodes sum to 1. This means that non-hierarchical structures are allowed in this parametrization. 
To give an example, suppose we have 3 clusters: the root $z_3$, and $z_1$, $z_2$ internal nodes. if z_2 belongs to z_3 and z_1 belongs to z_2, with the chosen parametrization $z_1$ can also belong to z_3. Could the authors elaborate on this point?

3. In Eq. 3 it would be helpful to specify which variables are given by the task at hand and which are optimized. While reading the paper, it is not clear whether the node and edge probabilities are determined by the dataset (e.g., by the similarities). This confusion stems from the existence of two different graphs in the problem formulation: the undirected graph given by the dataset and the learned directed acyclic graph for the hierarchy. It would help the reader to stress this difference and use different terms for the edges and nodes of the dataset graph.

4. In Figure 2, without the similarities between nodes in the $K_4$ graph it is hard to appreciate that hierarchies (b) and (d) model the problem better than (c). As all the nodes are connected to all the others, hierarchy (c) seems on the contrary more suited as it assigns all nodes to the same cluster. Moreover, without the similarities the scores given in the caption come out of the blue. 

5. In the empirical evaluation, it is not clear whether the datasets are split into training/test samples. It is important to clarify this point in order to appreciate the results of Table 2 and 3. Are the scores reported for EPH and FPH the training losses? Also, which objective is used when reporting accuracy: Das or TSD? In general, the standard deviations of the results should be also reported, in order to assess the significance of the gaps.

### Minors
- page 4: "of which $z$ is an ancestor of" -> whose ancestor is $z$
- page 7: hierarchical -> hierarchy

[1] Chris J. Maddison, Andriy Mnih, Yee Whye Teh: The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables. ICLR, 2017

[2] Shakir Mohamed, Mihaela Rosca, Michael Figurnov, Andriy Mnih: Monte Carlo Gradient Estimation in Machine Learning. J. Mach. Learn. Res., 2020

clarity,_quality,_novelty_and_reproducibility: **Several points have to be clarified**, concerning the theoretical contribution and the empirical analysis (see Weaknesses). In particular, two inaccurate claims and missing details on the experimentation affect the quality of the paper.

**The contributions have limited novelty** in that they constitute a novel application of well-known results in discrete optimization leveraging a recently proposed probabilistic formulation of hierarchical clustering. 

The implementation and the code for running the experiments were not submitted. The paper do not report all the details for reproducing the results, but this can be easily fixed.

summary_of_the_review: The paper has several weaknesses, that I believe should be easy to fix. The most concerning one is the inaccuracy on the unbiasedness of the learning procedure.
Otherwise, the paper is well-written. The contributions have limited novelty, but could have a good impact in the hierarchical clustering domain.

**update after discussion**

The authors addressed the concerns I raised and revised the paper accordingly. Because of this, I raised my score to 6.
I am not willing to increase it more as the work boils down to an application of well-known techniques in discrete optimization that (i) did not require deriving any new results and (ii) in practice does not provide better structures (see Table 3 - accuracy).
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper extends the work of Zügner et al. (2021), called FPH, to developing a hierarchical clustering method. They extend the soft hierarchy scores of FPH to expected hierarchy scores, prove results about it and present experimental support for the method, showing small improvements over FPH.  This achieves a continuous approach to hierarchical clustering.  The approach is an improvement on the prior FPH work.

The paper is well written.  The presentation has good components, with theory, experiments and discussion.  The theory tightens up the earlier FPH work. 

The reviewers, however, felt the improvement over FPH was smallish and the contribution is really a cleanup of FPH rather than a major original contribution.   Thus the reviewers felt the work was not strong enough.




justification_for_why_not_higher_score: The authors did a great job of addressing the reviewers concerns.
Decision: Reject