Ultrametric Fitting by Gradient Descent

• Prior approaches include greedy agglomerative and divisive heuristics, integer programming, continuous relaxations, and probabilistic formulations; closest-ultrametric fitting also has LP and ILP treatments.Source: §1 · pp. 1–2
• Procedural clustering methods can make their optimized objective difficult to understand, motivating formulations with well-defined cost functions.Source: §1 · p. 2
• The framework optimizes a cost over continuous ultrametrics, implicitly enforcing ultrametricity through a min-max operation.Source: §1 · p. 2
• Experiments on synthetic and real datasets find the proposed cost functions perform as well as Ward method and semi-supervised SVM.Source: §1 · p. 2
• The framework tests four objectives: closest-ultrametric fidelity, cluster-size regularization, semi-supervised triplet regularization, and a Dasgupta fidelity relaxation.Source: §1 · p. 2
• Its automatically differentiable algorithms scale to millions of vertices on sparse graphs.Source: §1 · p. 2

2 Ultrametric fitting

• A graph’s edge weights represent an ultrametric whose pairwise distances are recovered by the min-max distance, allowing compact representation on sparse graphs.The dendrogram associates each pair’s distance with the altitude of its lowest common ancestor.Source: §2 · pp. 2–3

2.1 Optimization framework

• Replacing the nonconvex ultrametricity constraint with a min-max operation yields an unconstrained cost that can be optimized by gradient descent.The authors describe this as the first use of the min-max operator in an optimization framework for ultrametric fitting.Source: §2.1 · p. 3

2.2 Closest ultrametric

• Exact minimization of the closest-ultrametric cost is NP-hard, so the proposed framework computes an approximate solution.The closest-ultrametric objective measures squared errors between the fitted ultrametric and graph edge weights.Source: §2.2 · pp. 3–4

2.3 Cluster-size regularization

• Adding cluster-size regularization prevents small clusters from branching very high in the dendrogram.The regularizer ranks nodes by the size of their smallest child and penalizes ultrametric distances according to node-dependent coefficients.Source: §2.3 · p. 4

2.4 Triplet regularization

• Triplet regularization uses known labels to reduce within-class ultrametric distances and increase distances between classes.A positive constant α sets the minimum prescribed distance between different classes.Source: §2.4 · p. 4

2.5 Dasgupta cost function

• For the Dasgupta cost, a differentiable soft-cardinal measure relaxes dendrogram node size and is optimized directly over ultrametric distances.The measure replaces the nondifferentiable Heaviside function with a continuous approximation such as a sigmoid; unlike, it is not optimized as a probability measure over a fixed tree.Source: §2.5 · p. 5

3 Algorithms

• The algorithms use single-linkage properties, a dual representation of the subdominant ultrametric, to compute the framework’s cost terms.Source: §3 · p. 5

3.1 Subdominant ultrametric

• The subdominant ultrametric is computed from pass-edge weights, with each edge’s pass edge identified through the single-linkage tree’s lowest common ancestor.For sparse graphs, the method uses single linkage and fast LCA preprocessing to achieve O(N log N) computation; its Jacobian has indicator columns for the corresponding pass edges.Source: §3.1 · p. 6, Figure 3 · p. 6, §3 · p. 6

3.2 Regularization terms

• Cluster-size regularization reuses single linkage and fast LCA for O(N log N) computation, while triplet regularization can be evaluated in O(|T| + N log N).Source: §3.2 · pp. 6–7

3.3 Dasgupta cost function

• The Dasgupta cost relaxation replaces the arbitrary reference vertex with a node’s associated pass edge, yielding O(N log N) empirical complexity for usually balanced dendrograms, but O(N^2) in the worst case.Its evaluation sums over a node’s ancestors; the worst-case number of ancestors is O(N), while balanced trees typically have O(log N).Source: §3.3 · p. 7

• On superpixel adjacency graphs generated at increasing scales from a high-resolution image, the proposed gradient-descent approach produced solutions close to optimal while using only a fraction of CUCP’s runtime.Figure 5(a) reports final mean square error normalized against CUCP 40 by number of graph edges; Figure 5(b) compares runtime by edge count, with CUCP capped at 200 seconds per instance.Source: §4 · p. 8, Figure 5 · p. 8
• Closest and Closest+Size handle graphs with millions of edges, while the Dasgupta relaxation is limited to a few hundred thousand edges.Algorithm 1 usually converges in about one hundred iterations.Source: §4 · p. 8, Figure 5 · p. 8
• The proposed Dasgupta and Closest+Size methods are competitive with Ward; Dasgupta performs slightly worse than Closest+Size on Digit1 and Heart.Closest and closest-ultrametric results are omitted because their performance is consistently worst; the Dasgupta relaxation is sensitive to data scaling.Source: §4 · pp. 8–9, Figure 6 · p. 9
• Triplet-regularized clustering performs comparably to semi-supervised SVM and better than spectral clustering on the tested datasets.The comparison uses classification accuracy, with 10%–40% of samples labeled under a 10-fold scheme.Source: §4 · pp. 8–9, Figure 6 · p. 9

5 Conclusion

• The framework fits ultrametrics to sparse edge-weighted graphs and accommodates various cost functions through algorithms designed with automatic differentiation in mind.Experiments on simulated and real data produced good approximate solutions to well-studied problems.Source: §5 · p. 9
• Experiments on simulated and real data show that the approach provides good approximate solutions to well-studied problems.Source: §5 · p. 9
• Theoretical analysis of the optimization framework is beyond the paper’s scope; suggested future directions include statistical-physics modeling and end-to-end neural-network learning.Source: §5 · p. 9

A.1 Algorithms

• Cluster-size regularization penalizes small clusters at large scales and can be restricted to the top-k dendrogram nodes; experiments use k = 10.The algorithm computes the smallest child size for each node and uses it when evaluating edge costs.Source: §A.1 · p. 10
• Triplet regularization penalizes triplets when the reference-positive distance is not sufficiently smaller than the reference-negative distance.The algorithm finds the clusters containing each pair using lowest-common-ancestor queries.Source: §A.1 · p. 11
• The Dasgupta cost implementation uses a soft-cardinal function, whose tree-node sizes are computed recursively from leaves to root.The described computation uses lowest-common-ancestor preprocessing and evaluates contributions along tree ancestors.Source: §A.1 · p. 11

A.2 Framework validation

• The optimization uses the AMSGrad variation of ADAM with step-size 0.01, and the implementation is single-threaded.Source: §A.2 · p. 11
• The mean-normalized convergence curve across 52 instances is smooth in practice and usually reaches convergence in a little over 100 iterations.Figure 8 plots the mean-normalized curve with standard deviation.Source: §A.2 · p. 11, Figure 8 · p. 12
• For each of 52 test instances, Jclosest values at each iteration were normalized from 0 for the lowest achieved cost to 1 for the highest reached cost.Source: §A.2 · p. 11

A.3 Illustrative examples

• Each example uses a 5-nearest-neighbor graph augmented with minimum-spanning-tree edges to ensure connectivity, then thresholds the resulting ultrametric at the prescribed cluster count.Source: §A.3 · p. 12
• The displayed columns compare Closest, Closest+Size, Closest+Triplet, and Dasgupta cost configurations.Closest+Size applies size regularization to the top 10 dendrogram nodes with λ = 0.1; Closest+Triplet uses λ = 1 and α = 3.Source: §A.3 · p. 12
• The example optimization uses the AMSGrad variation of ADAM with step-size 0.1.Source: §A.3 · p. 12

A.4 Average linkage approximates the closest ultrametric problem

• An ultrametric with finitely many values can be represented through functions defining a hierarchical partition.The number of values K is less than |V|.Source: §A.4 · pp. 12–13
• Figure 9 shows fitted ultrametrics and the cluster assignments obtained by thresholding them at two, three, or four clusters.Only the top 30 non-leaf nodes are shown in the dendrograms.Source: Figure 9 · p. 13
• For a fixed hierarchical clustering, the optimal altitudes are given by the criterion derived for Jclosest.Source: §A.4 · p. 13
• Average linkage uses exactly the closest-ultrametric criterion, so it provides an approximate solution to the closest ultrametric problem.Average linkage and Algorithm 1 with Jclosest also produce structurally similar ultrametrics in illustrative examples.Source: §A.4 · p. 13