Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics

1 Introduction

• Dasgupta’s cost scores candidate hierarchy trees from pairwise similarities, addressing agglomerative methods specified procedurally rather than by an objective.A heavy edge incurs less cost when its endpoints are separated deeper in the tree.Source: §1 · p. 2

1.1 Related Work

• Related work includes flat-clustering objectives that require choosing a cut level, consistency studies, noise-robust agglomerative methods, and an independent spreading-metric result by Roy and Pokutta.Source: §1.1 · p. 3

1.2 Our results and structure of the paper

• Recursive sparsest cut using an α_n-approximation achieves O(α_n) for HC, improving Dasgupta’s O(α_n log n) guarantee [Das16].The authors say this removes the log n factor from the earlier analysis.Source: §1.2 · p. 3, §1.1 · p. 3
• The RSC analysis extends the O(α_n) guarantee to the generalized HC cost function studied by Dasgupta [Das16].Source: §1.2 · p. 3
• Under the Small Set Expansion Hypothesis, the HC objective is hard to approximate within any constant factor.Source: §1.2 · p. 3
• The spreading-metric SDP has integrality gap at most O(√log n) and supplies an explicit lower bound that could support a better approximation.The SDP analysis also inspired the improved RSC analysis.Source: §1.2 · p. 3
• Combining spreading metrics with Bartal’s result gives an O(log n) approximation through a linear program.Source: §1.2 · p. 4
• Charging a cluster split to partition levels t ∈ [r/4, r/2] is the key to removing the log n factor from the approximation guarantee.Source: §1.2 · p. 4

2.1 Analysis of RSC heuristic

• RSC charges a cut of a cluster of size r against edges cut by the optimal clustering at level ⌊r/2⌋.The cut contributes its crossing-edge count multiplied by r to the hierarchical clustering objective.Source: §2.1 · p. 5
• RSC achieves an O(αn) approximation for hierarchical clustering on unweighted graphs.The analysis improves on the earlier O(αn log n) guarantee.Source: §2 · p. 4, §2.1 · p. 5

2.2 Generalized Cost Function and RSC

• For weighted graphs and strictly increasing f with f(0)=0, RSC achieves an O(cf · αn) approximation for the generalized objective.The analysis uses the increments g(t)=f(t+1)−f(t).Source: §2.2 · pp. 6–7
• The generalized guarantee is useful when cf is constant or slowly growing; for logarithmic f it is approximately O(αn log n), while exponential f makes it uninteresting.The paper notes that arbitrary f has no known direct polynomial-time implementation of this heuristic, though a balanced-cut heuristic gives similar guarantees.Source: §2.2 · pp. 6–7

3.2 Hierarchical Clustering Hardness

• Under the Small Set Expansion hypothesis, hierarchical clustering on unweighted graphs is hard to approximate within any constant factor.The hardness result distinguishes instances with a low-cost decomposition from those where every decomposition has high cost.Source: §3 · p. 8, §3.2 · p. 8

3.1 SSE and hardness amplification

• The SSE hypothesis posits NP-hardness of distinguishing a graph with a small non-expanding set from one where all sets of that size expand highly.The formal promise fixes the set size at δ and contrasts expansion at most η with expansion at least 1−η.Source: §3.1 · p. 8
• SSE-hardness amplification yields q disjoint low-expansion sets of volume 1/q in the yes case, versus a Gaussian-expansion lower bound for every set in the no case.The lower bound is ΦG(1−ǫ/2)(µ(S))−γ/µ(S).Source: §3.1 · p. 8

3.2 Hierarchical Clustering Hardness

• The no-case argument transfers a lower bound for Minimum Linear Arrangement to hierarchical clustering because every tree induces a vertex ordering whose edge stretches are bounded by the corresponding subtree sizes.The paper states that Minimum Linear Arrangement’s objective is always less than the hierarchical clustering cost.Source: §3.2 · p. 9

4.1 Writing the SDP

• At each level, pair-separation variables encode nested partitions; the SDP imposes metric structure and constraints reflecting spreading and cluster size.The hierarchy is represented by partitions for levels n−1 through 1, with each lower-level partition refining the preceding one.Source: §4.1 · pp. 9–10

4.2 Connections of SDP-HC with Balanced Partitioning

• The rounding recursively applies a 4-balanced-partitioning algorithm to each cluster, using the SDP solution restricted to that cluster.Each split produces pieces of size at most half the cluster size under the stated bicriteria guarantee.Source: §4.2 · p. 10
• The SDP-HC rounding algorithm gives an O(√log n)-approximation for hierarchical clustering, with its cost within O(√log n) of the SDP value.The SDP optimum is computable in polynomial time and lower-bounds the optimal hierarchical-clustering cost.Source: §4.1 · p. 10, log n) approximation for Hierarchical… · p. 11

4.4 The case of the generalized cost function

• For the generalized cost function, SDP-HC-gen modifies the objective weights and its rounding algorithm retains the stated O(√log n) guarantee.The objective weights are multiplied by g(t) = f(t + 1) − f(t).Source: §4 · p. 9, §4.4 · p. 11

Conclusion

• Recursive sparsest cut achieves an O(αn)-approximation, and the spreading metric SDP gives an O(√log n)-approximation; the LP gives O(log n).The sparsest-cut guarantee also extends to Dasgupta’s generalized cost function.Source: §5 · p. 11
• Under the Small Set Expansion Hypothesis, the hierarchical clustering objective is hard to approximate within any constant factor.The authors describe this as the first strong inapproximability result for the problem, to their knowledge.Source: §5 · p. 11

Further Research

• Improving hierarchical clustering’s approximation guarantee may be difficult before the current guarantee for Minimum Balanced Bisection improves.The authors also identify finding other suitable hierarchical-clustering cost functions as an open direction.Source: §5 · p. 11
• The authors propose studying exact recovery on γ-stable instances and whether an SDP can recover a hierarchy close to an underlying hierarchy drawn from a probability distribution.They also suggest formalizing guarantees for stable instances to explain the success of sparsest-cut heuristics.Source: §5 · pp. 11–12

Sparsest Cut

• The preliminaries introduce sparsest cut as minimizing a ratio over nontrivial vertex sets and note that improving its approximation ratio remains an open question.They also mention LP and SDP relaxations for the problem.Source: A Preliminaries · p. 16

Small-Set Expansion

• The Small-Set Expansion Hypothesis concerns distinguishing graphs with a small set having few outgoing edges from graphs where every small set has many outgoing edges.The passage notes its connection to the Unique Games Conjecture and its use in inapproximability results.Source: A Preliminaries · p. 16

k-Balanced Partitioning

• k-balanced partitioning divides a weighted graph into roughly equal-sized components while minimizing the total weight of edges between components.The passage identifies minimum bisection as the k=2 case and notes that a bicriteria approximation allows pieces of size 2n/k.Source: A Preliminaries · p. 16

Minimum Linear Arrangement

• Prior work gives MLA approximation algorithms and hardness results, including SSE-hardness of constant-factor approximation and the absence of a PTAS unless randomized subexponential-time solutions exist for NP-complete problems.The cited hardness results are attributed to and, respectively.Source: A Preliminaries · p. 16

Recursive decomposition

• Bartal’s graph decomposition finds a low-diameter cluster whose cut weight is small relative to the cluster’s weight.The decomposition refines an earlier graph decomposition to obtain a more refined bound on the cut-to-cluster-weight ratio.Source: B Spreading Metrics and Bartal’s… · p. 17

Recursive cost bound

• For recursively decomposed subgraphs, the cost recurrence adds the costs of both sides and a term equal to diameter times cut weight.The recurrence applies to nonnegative cost functions that are zero on singletons.Source: B Spreading Metrics and Bartal’s… · pp. 17–18
• The general cost bound is O(log(φ/φ0)) times φ(G), where φ0 is the minimum volume among non-singleton subgraphs.Associating volume φ(G)/n with nodes ensures φ0 ≥ φ(G)/n, yielding an O(log n) bound.Source: B Spreading Metrics and Bartal’s… · p. 18

Spreading metrics

• The spreading-metrics paradigm has an O(log n) approximation guarantee for problems covered by its decomposition framework.The section invokes Bartal’s result to establish this guarantee.Source: B Spreading Metrics and Bartal’s… · p. 18

Spreading-metrics application

• A spreading metric must lower-bound optimal cost through its weighted edge-length volume and provide a diameter bound for every vertex subset.The diameter must be at least the specified scale associated with the induced subgraph.Source: C LP Spreading Metrics and O(log n)… · p. 18

LP relaxation

• The LP can be solved in polynomial time using a separation oracle that checks the spreading constraint over distance-sorted prefixes.The formulation assigns edge lengths and uses shortest-path distances.Source: C LP Spreading Metrics and O(log n)… · p. 19
• The proven diameter bound for a subset U is only |U|/10, versus the required greater-than-|U| guarantee, a factor-10 shortfall that affects only the approximation-factor constant.Source: C LP Spreading Metrics and O(log n)… · p. 19
• The LP’s optimal value is a lower bound on the optimal hierarchical-clustering cost.The proof constructs a feasible metric from any binary clustering tree whose weighted edge-length volume equals that tree’s cost.Source: C LP Spreading Metrics and O(log n)… · p. 20

Spreading-metrics application

• Hierarchical clustering falls within the spreading-metrics paradigm, yielding an O(log n)-approximation.The application uses the lower-bound and diameter properties together with Bartal’s decomposition.Source: C LP Spreading Metrics and O(log n)… · p. 20

• O(α_n) approximation: Recursive Sparsest Cut achieves this guarantee for hierarchical clustering on unweighted graphs.Source: D Omitted Proofs · p. 20
• O(cf·α_n) approximation: RSC achieves this guarantee for the generalized hierarchical clustering objective.Source: D Omitted Proofs · p. 20
• The generalized RSC analysis combines bounds across clusters to obtain an overall cost of at most 8cfα_n·OPT.Source: D Omitted Proofs · pp. 20–21
• Restricting SDP-HC to a cluster A at level r/4 gives a valid 4-balanced partitioning solution for A.The proof compares the SDP-HC and SDP-k-BP constraints.Source: D Omitted Proofs · p. 21
• SDP-HC-gen rounding has cost within O(log n)·cf·SDP-HC when f is polynomially growing.Source: D Omitted Proofs · p. 21
• For a cluster of size r, the SDP rounding proof compares OPT's split cost with SDPA(t) over levels t=r/8+1 through r/4.Source: D Omitted Proofs · p. 21