PaperlayerView exact revision on arXiv

Source-linked AI summary

TeraHAC: Hierarchical Agglomerative Clustering of Trillion-Edge Graphs

Laxman Dhulipala, Jason Lee, Jakub Łącki, Vahab Mirrokni

arXiv:2308.03578v2cs.DScs.DBcs.DCcs.IR

TL;DR

HAC has been difficult to scale because prior approaches were quadratic or required many distributed rounds for quality guarantees. TeraHAC combines approximate HAC with a locally decidable nearest-neighbor-chain approach, scales to graphs with trillions of edges, and achieves quality close to exact HAC while outperforming SCC in speed and quality.

  • Problem

    HAC has faced limited scalability, while distributed methods have not simultaneously provided few rounds and provable quality guarantees.

  • Method

    TeraHAC combines (1 + 𝜖)-approximate HAC with a locally decidable nearest-neighbor-chain approach suitable for distributed computation.

  • Results

    TeraHAC scales to graphs with up to 8 trillion edges, preserves quality close to exact HAC, and is 8.3x faster than SCC while achieving 1.16x higher quality.

  • Takeaways & Limitations

    TeraHAC may be an algorithm of choice for clustering large-scale graph datasets.

  • Takeaways & Limitations

    Best performance requires pruning that limits the output to the bottom, high-similarity part of the dendrogram.

Abstract

from arXiv · show

We introduce TeraHAC, a $(1+\epsilon)$-approximate hierarchical agglomerative clustering (HAC) algorithm which scales to trillion-edge graphs. Our algorithm is based on a new approach to computing $(1+\epsilon)$-approximate HAC, which is a novel combination of the nearest-neighbor chain algorithm and the notion of $(1+\epsilon)$-approximate HAC. Our approach allows us to partition the graph among multiple machines and make significant progress in computing the clustering within each partition before any communication with other partitions is needed. We evaluate TeraHAC on a number of real-world and synthetic graphs of up to 8 trillion edges. We show that TeraHAC requires over 100x fewer rounds compared to previously known approaches for computing HAC. It is up to 8.3x faster than SCC, the state-of-the-art distributed algorithm for hierarchical clustering, while achieving 1.16x higher quality. In fact, TeraHAC essentially retains the quality of the celebrated HAC algorithm while significantly improving the running time.

1 INTRODUCTION

HAC offers high-quality hierarchical clustering but has faced severe scalability limits, motivating distributed methods that combine quality guarantees with few rounds. TeraHAC addresses this gap with approximate, locally checkable merges and achieves substantial scalability and performance improvements while retaining high clustering quality.

  • 1 INTRODUCTION: HAC repeatedly merges the most similar clusters into a dendrogram, with average linkage especially attractive because of its empirical quality.Approximate HAC and sparse similarity graphs enable near-linear and parallel implementations without observed degradation in empirical quality.
  • 1 INTRODUCTION: Existing distributed methods either require many rounds for quality guarantees or lack provable guarantees, leaving few-round, high-quality hierarchical clustering as an open problem.Earlier HAC algorithms were quadratic in the number of points and commonly assumed a complete similarity matrix, while distributed methods reached trillion-edge scales with this quality–rounds trade-off.
  • 1.1 Our Contribution: TeraHAC generalizes nearest-neighbor chain and RAC methods by allowing locally checkable (1+ε)-good merges in any order, including in parallel.Performing these good merges yields a (1+ε)-approximate dendrogram, enabling distributed progress within graph partitions before communication.
  • 1.1 Our Contribution: Over 100x fewer rounds and 3.5–10.5x faster running time result from TeraHAC’s greater merge parallelism than RAC and ParHAC.TeraHAC can merge a superset of the edges mergeable by RAC and ParHAC; with ε=0.1 it uses at most 17 rounds across the evaluated datasets.
  • 1.1 Our Contribution: 8.3x faster and 1.16x higher quality than SCC in its highest-quality setting, while scaling to graphs with up to 8 trillion edges.On large real-world web graphs, TeraHAC is 8.3x faster than SCC using 100 rounds; on an 8 trillion-edge web-query graph, it is 30%–50% faster and can improve recall by up to 20% relative.
  • 1.1 Our Contribution: With ε=0.1, TeraHAC’s quality differs from exact HAC by only 1%–3% according to standard clustering similarity measures, ARI and NMI.

2 PRELIMINARIES

The preliminaries formalize HAC on weighted graphs, its merge and dendrogram representations, and the reducibility property used by the algorithmic results.

  • HAC starts with singleton clusters and repeatedly merges two clusters with nonzero similarity, producing a dendrogram whose internal nodes represent merges.
  • TeraHAC models each clustering state as a graph formed by contracting current clusters, with edge weights equal to average linkage between their members.
  • A reducible similarity function satisfies f(x,y∪z) ≤ max(f(x,y), f(x,z)); the weighted similarity used here is reducible, as are several standard linkage functions.
  • A merge is (1+ε)-approximate when its similarity is within a factor 1+ε of the maximum edge weight in the current graph.
  • A (1+ε)-approximate dendrogram admits a merge sequence consistent with its merge tree that completes all nonzero-similarity merges using (1+ε)-approximate steps.

3 APPROXIMATE NEAREST-NEIGHBOR CHAIN ALGORITHM

This section extends nearest-neighbor-chain reasoning with locally testable good merges, showing that arbitrary valid merge orders still yield (1+ε)-approximate dendrograms.

  • The nearest-neighbor-chain algorithm exactly reproduces HAC’s dendrogram up to ties while deciding merges using local information, motivating its parallel extension.
  • A merge is judged using the cluster’s minimum creation similarity M, which is essential for ε>0 even though it disappears when ε=0.For ε=0, the criterion reduces to the reciprocal-nearest-neighbor condition.
  • The invariant w_max(v)/M(v) ≤ 1+ε holds after any sequence of good merges, relying on reducibility and the good-merge condition.
  • Greedy ordering of a fixed merge tree minimizes the maximum merge error, and its maximum error exactly characterizes the dendrogram’s approximation ratio.
  • (1+ε)-good merges can be applied in any valid order, including parallel orderings, while still producing a (1+ε)-approximate dendrogram.This removes HAC’s greedy ordering requirement and enables greater parallelism.

4 TeraHAC ALGORITHM

TeraHAC partitions the graph, computes long sequences of locally good merges within each partition, and combines them while preserving approximation guarantees; thresholded flattening produces flat clusterings.

  • 4 TeraHAC ALGORITHM: TeraHAC partitions each graph round, runs SubgraphHAC on partition neighborhoods, and applies the resulting disjoint merge sequences globally.Partitioning affects running time but may be arbitrary for correctness when t=0.
  • 4 TeraHAC ALGORITHM: SubgraphHAC selects merges by goodness = max(w_max(u), w_max(v))/M(u∪v), stopping above 1+ε and guaranteeing near-maximal good-merge processing.
  • 4 TeraHAC ALGORITHM: SubgraphHAC runs in O((m+n) log2 n) time on a graph with n vertices and m edges.
  • 4 TeraHAC ALGORITHM: For t=0, any partitioning method yields a (1+ε)-approximate dendrogram because partition-local merge sequences can be arbitrarily interleaved while remaining good.
  • 4.1 Flattening the Dendrogram: Flattening selects clusters whose linkage similarity reaches threshold t while their ancestors remain below t, yielding a flat clustering with minimum constituent merge similarity at least t/(1+ε).
  • 4.1 Flattening the Dendrogram: The best performance requires pruning the bottom part of the dendrogram, which the authors identify as a limitation, although it has little quality impact on their studied datasets.

5 TeraHAC IMPLEMENTATION

The implementation combines distributed graph processing, affinity-based partitioning, local SubgraphHAC, contraction, pruning, and reproducible shared-memory components.

  • Affinity clustering partitions each round’s graph by marked highest-weight edges, with a size constraint limiting clusters to at most 10 million edges.
  • Each partition is processed on one machine by SubgraphHAC, which returns merge nodes, cluster assignments, and minimum merge similarities for contraction.
  • The distributed implementation contracts cluster IDs, updates edge metadata, and removes vertices without outgoing edges to reduce subsequent graph size.
  • The shared-memory implementation includes faithful affinity clustering, efficient SubgraphHAC, and weighted graph contraction, and consistently outperforms ParHAC in the reported setting.

6 EMPIRICAL EVALUATION

TeraHAC is evaluated on clustering quality, scalability, shared-memory performance, and an 8-trillion-edge web-query graph. Across these settings, it preserves high quality while reducing running time and graph size relative to scalable HAC baselines.

  • 6.1 Quality: Larger thresholds require fewer rounds, while t=0.01 preserves quality relative to t=0 and achieves the same NMI across the evaluated datasets.At t=0.01, ARI is within 0.4%, Purity within 2.6%, and Dasgupta cost within 1.6% of t=0 on average.
  • 6.1 Quality: For 𝜖≤0.1, outputs are within 1.3% of the best ARI, 0.25% of the best NMI, 2.6% of the best Purity, and 1.6% of the best Dasgupta score on average.All four TeraHAC settings achieve high-quality results across the evaluated datasets and measures.
  • 6.1 Quality: TeraHAC with 𝜖=0.1 is superior to SCC except on digits, where SCC-5 achieves 0.4% better ARI and 1.2% better NMI.Compared with DBSCAN, HAC-based methods generally provide higher quality, although DBSCAN performs better on Wine.
  • 6.2 Scalability: 8.3x faster than SCC-100 on average across five large real-world graphs, while TeraHAC runs between the SCC-5 and SCC-25 performance levels.SCC-100 could not finish within four days on the Hyperlink graph.
  • 6.2 Scalability: On shared-memory experiments, TeraHAC is 1.45–8x faster than ParHAC and 48.5–185x faster than SeqHAC.It is also 1.04–5.28x faster than ParHAC with the same vertex-pruning optimization.
  • 6 EMPIRICAL EVALUATION: TeraHAC scales from synthetic and real-world graphs to an 8-trillion-edge web-query graph, using up to 48,000 cores across 6,000 machines.The web-query graph contains about 31 billion vertices and 8 trillion edges.
  • 6.3 Large Scale Clustering of Web Queries: On the web-query dataset, TeraHAC achieves the highest recall at every evaluated precision and about 20% better recall than SCC-5.It runs about 2x faster than SCC-50 and about 2x slower than SCC-5; DBSCAN is faster but has over 2x smaller recall.
  • 6.3 Large Scale Clustering of Web Queries: After 10 rounds on the web-query graph, TeraHAC retains 41 billion edges versus 561 billion for SCC-50 and 799 million nodes versus 5.4 billion.The remaining edge and node counts are respectively 13.4x and 6.7x lower for TeraHAC.

7 CONCLUSION

TeraHAC combines high quality with scalability to graphs containing up to 8 trillion edges, while leaving theoretical round bounds and broader dendrogram coverage as open questions.

  • TeraHAC demonstrates high quality and scalability on graphs of up to 8 trillion edges.
  • The number of rounds required by TeraHAC still lacks a theoretical bound, potentially depending on graph partitioning.
  • Extending TeraHAC from the bottom, high-similarity dendrogram portion to the entire dendrogram remains open.
  • The notion of (1 + 𝜖)-good merges may support efficient HAC algorithms in other models, including dynamic settings.

A MISSING PROOFS

The proofs establish monotonicity and preservation properties for merge values and (1 + 𝜖)-good merges, supporting the correctness of the partitioned HAC process and thresholded outputs.

  • w_max(v) is nonincreasing across successive graph states while vertex v persists through arbitrary merges.
  • Under 1-good merges, an edge is 1-good exactly when its weight equals the larger endpoint w_max value.
  • The proof’s contradiction argument bounds the relevant merge ratio by 1 + 𝜖 using the prior merge sequence and cluster decomposition.
  • A merge remains (1 + 𝜖)-good in the global graph when it is (1 + 𝜖)-good within a partition and involves only active vertices.
  • The proof uses the fact that SubgraphHAC sees the same graph after a local merge as after applying that merge globally and then restricting the graph.
  • After flattening with threshold t, the output is unchanged for any preliminary threshold t′ in [0,t].

B SubgraphHAC

SubgraphHAC computes near-linear-time sets of approximate-good merges within graph partitions, addressing the difficulty of maintaining changing goodness values efficiently.

  • B SubgraphHAC: SubgraphHAC performs only (1 + 𝜖)-good merges and terminates when no (1 + 𝜖′)-good merges remain for 𝜖′ = O(𝜖).
  • B SubgraphHAC: The algorithm operates on partitions with active vertices, inactive external neighbors, min-merge values M(v), and cluster sizes.
  • B SubgraphHAC: Exact goodness maintenance can require O(n^2) work because merges alter neighboring weights and goodness values up to two hops away.
  • B SubgraphHAC: A heap over active edges alone is insufficient because SeqHAC cannot merge edges below a (1 + 𝜖) factor of the current maximum.
  • B SubgraphHAC: The lazy approach uses a vertex priority queue, approximate goodness values, multiplicative broadcasts, and edge reassignment by approximate w_max.

Graph Representation

The graph representation supports approximate goodness queries, vertex merging, and lowest-goodness edge selection in near-linear total time while controlling approximation through 𝜖 and 𝛼.

  • Graph Representation: 𝜖 controls merge accuracy, while 𝛼 controls broadcast frequency and the goodness range with guaranteed edge selection.
  • Graph Representation: The representation supports four operations—approximate goodness, approximate w_max, active-vertex merging, and lowest-goodness queries—in ˜O(m+n) total time.
  • Graph Representation: The representation supports its lowest-goodness query only for edges whose true goodness lies in a specified range [1,T].
  • Graph Representation: Approximate edge weights satisfy w(u,v) ≤ ˜w(u,v) ≤ w(u,v)(1 + 𝛼), providing an upper-bounded approximation.
  • Graph Representation: Stored goodness values satisfy ĝ(u,v) ≤ g(u,v)(1 + 𝛼), so small true goodness implies small stored goodness.
  • Graph Representation: Approximate w_max values and goodness values are each at most a (1 + 𝛼) multiplicative over-approximation of their exact counterparts.
  • Graph Representation: Merging only edges with approximate goodness at most 1 + 𝜖 guarantees that the merged edge is truly (1 + 𝜖)-good.

Graph Representation Operations

The algorithm implements approximate HAC through size-aware merges, neighborhood updates, threshold-triggered broadcasts, and approximate best-neighbor searches.

  • Graph Representation Operations: Merging the smaller cluster into the larger updates neighborhood weights in O(|N(u)|) time using average linkage.Edges assigned to the merged vertex are deferred for later repair.
  • Graph Representation Operations: Broadcasts occur when cluster size or the approximate maximum weight changes by a factor of 1 + α.These broadcasts refresh neighboring edge weights or reassign edges toward the endpoint with larger approximate maximum weight.
  • Graph Representation Operations: BestAssignedNeighbor scans assigned edges by stored goodness until finding an approximate goodness below 1 + ε or exhausting the relevant threshold range.The threshold range is [1, (1 + ε)/(1 + α)].
  • Graph Representation Operations: Each unsuccessfully considered edge can be checked only O(log n) times because its stored goodness must change by a multiplicative factor before another unsuccessful check.The gap between stored and approximate goodness provides the amortization argument.

Correctness

The correctness analysis shows that merges preserve the algorithm’s two invariants and that termination excludes edges whose goodness falls below the approximation threshold.

  • Correctness: Merge(u, v) preserves Invariants 1 and 2.The lemma establishes preservation across the merge operation.
  • Correctness: Invariant 1 remains valid because affected weights become exact after the relevant cluster-size broadcast.Only edges incident to the surviving vertex v are affected by the merge.
  • Correctness: Invariant 2 bounds stored goodness by a factor of (1 + α)^2 relative to true goodness, with broadcasts correcting stale values after sufficient decreases.The update trigger depends on the approximate maximum-weight value decreasing by a factor of 1 + α.
  • Correctness: At termination, no edge has goodness in [1, T], where T = (1 + ε)/(1 + α)^3.Otherwise, the maintained goodness bound would imply that BestAssignedNeighbor missed an edge in its search range.

Running Time Analysis

The running-time analysis bounds broadcasts and unsuccessful edge checks logarithmically, yielding an overall complexity of O((m + n) log^2 n) under a polynomially bounded aspect ratio.

  • Running Time Analysis: The approximate maximum-weight increase across merges is controlled by the cluster-size sequence, whose total multiplicative growth is O(n^ε).For cluster sizes p ≥ q, one merge increases the value by at most ((1 + ε)q + p)/(p + q).
  • Running Time Analysis: The broadcast bound relies on a polynomially bounded initial edge-weight aspect ratio, Wmax/Wmin ∈ O(poly(n)).This assumption limits the overall range of best values over a vertex’s lifetime.
  • Running Time Analysis: O(log n) broadcasts are performed by each vertex for constants ε > 0 and α > 0 under a polynomially bounded aspect ratio.The bound follows from controlling the cumulative range of approximate maximum weights over merges.
  • Running Time Analysis: O(log n) unsuccessful checks occur for each edge across all BestAssignedNeighbor calls.Stored goodness can rise through U or fall through D only logarithmically many times when the graph’s aspect ratio is bounded.
  • Running Time Analysis: O((m + n) log^2 n) is the algorithm’s overall running time.Broadcast updates, unsuccessful-edge reinsertion, and node-heap extraction together produce this bound.
Loading 2308.03578v2…