Home / Curated / Algorithms / Genie clustering

Genie clustering

Algorithms AIMech:GenieClustering DRAFT

Aliases: Genie linkage, Genie hierarchical clustering

An agglomerative clustering algorithm that normally selects a nearest pair by single-link distance and, when cluster-size inequality exceeds a threshold, restricts that selection to pairs containing a globally smallest cluster.

Identity Notes & Concept Scope Compared all 442 pinned AIO and 656 native IDs, names, aliases and scoped synonyms; no normalized identity match. Ignored- and hidden-inclusive fixed-string searches of the recovery, older discovery and original Documents checkouts returned 30, 0, 0 lines. All distinct match contents were read, including pending discovery entries and source-reading observations. Recovery hits concern pending Genie discovery notes and primary-source context; none identifies an existing standalone Genie record. Both other checkouts returned no matches including ignored and hidden files. Semantic matching covered 26 AIO and 173 native definitions, all read; unchanged definitions were byte-compared with the preceding full assessment. 9 full annotated AIO node/edge/generated contexts and 5 full native records were inspected. Retain the original inequality-triggered single-link merge rule. It differs from fixed linkage-preserving chains, global cached-bound search, Ward variance minimization, BIRCH compression and RS tree pruning. Genieclust names a later software package with extensions, not an exact alias for all original-method claims.

Claims & Grounded Evidence

6 Claims

Mechanism #inequality-triggered-merging

Start with singleton clusters. If the current cluster-size inequality is at or below a threshold g, choose a minimum single-link-distance pair. Otherwise, restrict eligible pairs to those containing at least one cluster of globally minimum size, then minimize the same distance. The paper allows an inequality index such as normalized Gini or Bonferroni; its implementation study uses Gini. For the paper’s g in (0,1], g=1 recovers single linkage.

supports Source: Genie: A new, fast, and outlier-resistant hierarchical clustering algorithm · Locator: Sections2.2–3.1, PDF pp.5–8, Equations1–2
supports Source: Genie1.0.0 author implementation: src/hclust2_mstbased_gini.cpp · Locator: HClustMSTbasedGini::compute, conditional edge exclusion

Mechanism #mst-and-conditional-edge-selection

The method can operate on a minimum spanning tree of the complete dissimilarity graph. Maintain component sizes and select a minimum eligible remaining tree edge; an edge skipped during a small-cluster correction must remain available when eligibility changes. The inspected implementation caches skipped edges and restores them when the minimum component size changes or the inequality condition no longer requires correction.

supports Source: Genie: A new, fast, and outlier-resistant hierarchical clustering algorithm · Locator: Section4, Theorem1 and Figure5, PDF pp.14–17
supports Source: Genie1.0.0 author implementation: src/hclust2_mstbased_gini.cpp · Locator: HClustMSTbasedGini::compute, pq_cache restoration

Scope #distance-and-storage-scope

The base linkage requires symmetric nonnegative dissimilarities with zero self-distance. The inspected Prim-style tree builder computes each unordered point-pair distance once and maintains linear auxiliary arrays without materializing a full distance matrix. The paper’s alternative VP-tree acceleration uses the triangle inequality for pruning; it is not a guarantee for every dissimilarity, dimension or implementation.

supports Source: Genie: A new, fast, and outlier-resistant hierarchical clustering algorithm · Locator: Introduction, PDF p.2; Sections4.1–4.3, Figures6–7, PDF pp.17–22
supports Source: Genie1.0.0 author implementation: src/hclust2_mstbased_gini.cpp · Locator: HClustMSTbasedGini::getMST

Scope #threshold-and-height-boundaries

The threshold triggers a correction from the current partition; it does not impose a hard ceiling or require every corrective merge to lower inequality. Raw merge distances can decrease. The pinned Genie1.0.0 implementation marks corrective distances internally, and its R wrapper adjusts displayed heights by interpolation and cumulative maxima. Those plotted heights are not identical to the raw selected dissimilarities.

supports Source: Genie: A new, fast, and outlier-resistant hierarchical clustering algorithm · Locator: Section3.1, PDF p.8; Section4.1, PDF pp.16–17
supports Source: Genie1.0.0 author implementation: src/hclust2_mstbased_gini.cpp · Locator: HClustMSTbasedGini::compute, signed res.link distance
supports Source: Genie1.0.0 author implementation: R/hclust2.R · Locator: hclust2, final height adjustment
supports Source: Genie1.0.0 author implementation: DESCRIPTION · Locator: Package, Version and Date fields

Scope #worked-example-discrepancy

The paper’s Example1 states that points 0,1,3,6,10 with Gini threshold 0.3 merge the last two singletons at the third step. Its formal rule, Figure5 and inspected original implementation instead permit the nearer merge between the size-three cluster and point 6, because one endpoint is a smallest cluster. The worked example is therefore retained as a source inconsistency rather than used to redefine the algorithm.

supports Source: Genie: A new, fast, and outlier-resistant hierarchical clustering algorithm · Locator: Section3.1, PDF pp.7–8; Figure5, PDF p.15; Example1, PDF p.16
supports Source: Genie1.0.0 author implementation: src/hclust2_mstbased_gini.cpp · Locator: HClustMSTbasedGini::compute, both-size-greater-than-minimum exclusion

Performance #reported-evaluation

The paper reports Fowlkes–Mallows agreement on 29 benchmark datasets, using the known reference number of clusters to cut each hierarchy and medians over ten input permutations. Gini threshold 0.2 has the highest reported aggregate mean and median among the nine compared hierarchical methods, but individual datasets favor other methods. These comparisons do not establish universal outlier recovery, accuracy or runtime superiority.

Evaluation Context:

Task: External agreement between a hierarchy cut and a reference clustering.

Dataset: 29 datasets, comprising 21 Euclidean and eight non-Euclidean sets; no held-out threshold-selection split established. SIPU selection excludes datasets above 10000 points and cases where all methods performed perfectly.

Model: Original Genie linkage, as described in the 2022 arXiv deposit of the 2016 paper; thresholds 0.2 through 0.6. Historical genie and later genieclust are not equated.

Metric: Fowlkes–Mallows index in [0,1]; per-dataset median over ten randomly permuted input orders.

Result: Table2 reports mean 0.850 and median 0.921 for Gini threshold 0.2. These are aggregates over the selected 29 datasets, not per-dataset guarantees. (Baseline: Single, complete, average and Ward linkage, with five Genie thresholds; the separate 21-set comparison also includes k-means and BIRCH.)

supports Source: Genie: A new, fast, and outlier-resistant hierarchical clustering algorithm · Locator: Sections3.2–3.3, PDF pp.9–14, Tables1–3

⚠️ Curated Limitations & Negative Results

The record covers the original linkage and inspected Genie1.0.0 source revision. Later genieclust mutual-reachability, noise-label, deadwood and other extensions are not aliases or inherited guarantees.
The current-partition inequality trigger can be exceeded after a merge, and a corrective merge can increase it. Outlier resistance is an empirical motivation, not a proof of recovery or an explicit noise classifier.
Paper Example1 conflicts with the formal OR eligibility rule and inspected merge predicate. Curator exact arithmetic makes the distinction explicit without executing the author implementation.
Finite checks compare full eligible-pair and MST selection on 2880 distinct-weight and 2916 tied four-point cases and verify Gini update arithmetic. They do not prove universal tie equivalence, floating-point correctness or statistical performance.
The normalized Gini formula is undefined for one remaining cluster. The curator calculation stops its inequality assessment there; the implementation’s final normalization and clamping are not certified numerically.
The paper defines g in (0,1], while the inspected R documentation also permits zero. Distance ties and input order can affect the hierarchy. Plot-height adjustment must not be mistaken for raw merge distances.
Only the Prim route has the stated once-per-unordered-pair property. The paper reports VP-tree cases exceeding that pair count, and high-dimensional speedups are conditional. Historical runtime minima and individual Ward comparisons are not transferred to present hardware.
All 30 pages of arXiv2209.05757v1 and the cited pinned code files were read. Static inspection and curator arithmetic only: no author R/C++ execution, training, benchmark replication or later implementation audit.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:HierarchicalClustering` Hierarchical Clustering	related_match	The algorithm constructs nested partitions. The AIO target denotes the task, not this inequality-conditioned linkage or an equivalent algorithm.
`AIO:UnsupervisedClustering` Unsupervised Clustering	related_match	Merge selection uses distances and cluster sizes without reference labels. Benchmark labels determine evaluation cuts, which is separate from the merge rule.

Evidence Sources & Primary Literature

4 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`genie2016`	Genie: A new, fast, and outlier-resistant hierarchical clustering algorithm Marek Gagolewski, Maciej Bartoszuk, Anna Cena	primary paper full_text	ID: arXiv:2209.05757v1 sha256:173888c12079…
`genie-merge`	Genie1.0.0 author implementation: src/hclust2_mstbased_gini.cpp Marek Gagolewski, Maciej Bartoszuk, Anna Cena	official documentation documentation	sha256:5af3cf1e3d2f…
`genie-wrapper`	Genie1.0.0 author implementation: R/hclust2.R Marek Gagolewski, Maciej Bartoszuk, Anna Cena	official documentation documentation	sha256:8330e818daae…
`genie-description`	Genie1.0.0 author implementation: DESCRIPTION Marek Gagolewski, Maciej Bartoszuk, Anna Cena	official documentation documentation	sha256:b84da1dc41bd…

Curation Provenance

Curator: Codex

Method: ai_assisted

Model: GPT-6

Created: 2026-10-13T22:47:35Z

Updated: 2026-10-13T22:47:35Z

Source File: data/curated/GenieClustering.yaml