Summary
This paper introduces a novel tree fitting algorithm named HCCRootedTreeFit. First, the authors motivate the need for a better tree fitting algorithm by stating that current methods "assume almost nothing about the underlying discrete point set, when, in fact, many real application data sets are close to hierarchical or nearly so".
Before introducing their new method, the authors introduce new proxy measures of how tree-like a dataset is. These proxy measures are used later on in several bounds, including in their main theoretical result which guarantees the existence of a tree fitting method with some nice bound on the distortion.
In their theoretical analysis, the authors mention a connection between the tree fitting problem and hierarchical correlation clustering (HCC), along with an equivalence result between tree fitting algorithms and ultrametric fitting algorithms. Then, they introduce an adapted HCC problem formulation and three algorithms named HCCTriangle, HCCUltraFit and HCCRootedTreeFit. The first algorithm solves the adapted HCC problem. The second algorithm uses HCCTriangle to solve the ultrametric fitting problem. The last algorithm uses HCCUltraFit to solve the rooted tree fitting problem.
In the experiments, the HCCRootedTreeFit algorithm is tested versus various other methods from the literature. For these experiments the authors have used both common and synthetic datasets. They observe that their method underperforms on common datasets, but performs well on synthetic datasets with respect to the $\ell_1$ norm. They attribute this observation to a lack of tree-like structure in the common datasets. They furthermore observe that their method underperforms with respect to the $\ell_\infty$ norm.
Strengths
1. The paper introduces interesting new notions of hyperbolicity and ultrametricity through their hyperbolicity and ultrametricity vectors.
2. The authors derive an interesting connection between the distortion bounds for tree fitting and ultrametric fitting algorithms.
3. The new notion of hyperbolicity is used to show that, contrary to common belief, the common datasets are not very tree-like.
Weaknesses
The paper is very difficult to read. Due to the very large number of definitions and technical results, the paper reads more like a collection of statements than a paper. Much of the actual content seems to be put in the appendix, adding to the feeling that the paper is not at all self-contained. Moreover, the paper appears to use many tricks from different papers without any description of these tricks. For example, in line 233, the authors refer to some paper to obtain a tree fit without actually explaining the actual procedure.
The structure of the paper also makes it rather difficult to follow, with several forward- and backward references spread throughout the paper. As an example, Subsection 3.2 appears to state several results regarding algorithms that have not yet been introduced. Then, in the next subsection, these algorithms are introduced and following these algorithms, the authors quickly throw in a proof of a result from the previous Subsection.
Another issue with the paper is that they first formulate the tree (ultrametric) fitting problem, but then, after quickly mentioning a connection to hierarchical correlation clustering, seem to actually solve an adapted version of this HCC problem. However, the introduction of their adapted HCC problem is rather unclear and uses, for example, a 'number of disagreement edges' term that is not properly defined in the paper. Also, it is not really clear to me what the connection with this problem and the original problem is.
Due to these issues I cannot adequately judge the validity of the many technical results of this paper.
There is also an issue regarding the newly proposed algorithm within the context of the experimental results. The authors show that their method underperforms on common datasets with respect to both the $\ell_1$ norm and the $\ell_\infty$ norm. Moreover, the method is quite slow compared to two of the other methods. It therefore appears that this method is only useful in synthetic settings.
Questions
1. What is the exact connection between the tree fitting problem and the HCC problem?
2. How is the term $|E_t \Delta E(P_t)|$ defined precisely?
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.
Limitations
Mostly yes. They do not really address the fact that their method does not seem to have a proper use case, but they do point out its weaknesses in the experiments.