Abstract
Hierarchical clusterings compactly encode multiple granularities of clusters within a tree structure. Hierarchies, by definition, fail to capture different flat partitions that are not subsumed in one another. In this paper, we advocate for an alternative structure for representing multiple clusterings: a directed acyclic graph (DAG). By allowing nodes to have multiple parents, DAG structures are not only more flexible than trees but also allow for points to be members of multiple clusters. We describe a scalable algorithm, Llama, which merges nearest neighbor substructures to form a DAG. Llama discovers structures that are more accurate than state-of-the-art tree-based techniques while remaining scalable to large-scale clustering benchmarks. Additionally, we support the proposed algorithm with theoretical guarantees on separated data, including types of data that cannot be correctly clustered by tree-based algorithms.
Introduction: The Limitation of Trees
Traditional hierarchical clustering produces a tree structure where each data point belongs to a nested sequence of clusters. While useful, trees have a major limitation: they cannot represent overlapping or non-nested relationships. In a tree, a leaf node has exactly one parent, meaning a data point cannot simultaneously belong to two different clusters unless one is a subset of the other.
In the real world, data is often "fuzzy" or multi-faceted. For example, in natural language, the word "shepherd" belongs to the category of "dog breeds" and "farm professions." A tree forces a choice or a merger that loses this distinction. Previous attempts to build DAG-structured clusterings existed but were computationally expensive and failed to scale beyond a few thousand points.
The Llama Algorithm
The authors propose Llama (Lattices by Leveraging Agglomerations and Multiple Ancestors), a round-based agglomerative algorithm inspired by Reciprocal Nearest Neighbors. The process follows these steps:
- Initialization: Start with every data point in its own cluster.
- Nearest Neighbor Merging: In each round, every cluster $C$ identifies its nearest neighbor $C'$ based on a linkage function (like average or single linkage).
- DAG Construction: A new node is created for the union $C \cup C'$. Crucially, because the nearest neighbor relationship is asymmetric (the nearest neighbor of $A$ might be $B$, but the nearest neighbor of $B$ might be $C$), a single cluster can be merged into multiple different "parent" clusters in the same round. This creates the DAG structure.
Llama is designed for parallelism and uses $k$-nearest neighbor graph sparsification to keep the search space manageable, allowing it to run on datasets with over a million points. The authors also provide a theoretical framework showing that Llama can recover ground-truth partitions in "noisy model-based separated data"—a class of data where traditional tree-based methods like HAC or Grinch are mathematically guaranteed to fail.
Experimental Evaluation
The algorithm was evaluated on three types of benchmarks:
- Standard Clustering: Speaker (audio), ALOI (object images), and ILSVRC/ImageNet (large-scale image embeddings).
- Covering Benchmarks (Multi-label): MediaMill, Delicious, BibTeX, EURLex-4k, and Wiki10-31K. These datasets are specifically chosen because points naturally belong to multiple categories.
- Lexical Reconstruction: WordNet, where the goal is to reconstruct the overlapping "synsets" (synonym sets) of English words from vector embeddings.
Key Insights
- Asymmetry as a Feature: In traditional clustering, asymmetry is often treated as a hurdle. Llama embraces it; the fact that $NN(A) = B$ but $NN(B) \neq A$ is precisely what allows the algorithm to discover multiple valid "paths" or contexts for a data point.
- Beyond Partitions: For many tasks, a "cover" (where sets can overlap) is a more natural fit than a "partition" (where sets are disjoint).
- New Evaluation Metrics: Since standard tree metrics like dendrogram purity don't work for DAGs, the authors advocate for Jaccard-based metrics (Mean Jaccard Per Label, Per Point, and Per Node) to measure how well the structure captures ground-truth clusters without becoming an unmanageably large "spaghetti" graph.
Results and Scalability
Llama consistently outperformed tree-based methods (Affinity Clustering, Grinch, and Reciprocal Nearest Neighbors) across nearly all datasets in both precision and recall-focused metrics. Notably, Llama successfully processed the ILSVRC (Lg.) dataset (1.2 million images), a feat previous DAG-based clustering methods could not achieve.
Qualitatively, in the WordNet experiment, Llama successfully identified distinct lineages for polysemous words. For example, it placed "blossoming" into lineages related to "budding/emerging" as well as "flowered/planted."
Conclusion
While Llama shows significant promise, it relies on hyperparameters like the number of rounds and the maximum parents per node ($p$) to prevent the DAG from growing too large. Future work could explore more complex linkage functions tailored for DAG structures and expand theoretical guarantees to broader, less-rigid data distributions.
Summary updated