Overlapping hierarchical clustering (OHC)
Algorithms AIMech:OverlappingHierarchicalClustering DRAFT
Aliases: OHC clustering
A graph-based agglomerative clustering algorithm that expands clusters across increasing distance thresholds when the change in induced edge density is within a tolerance, retaining overlapping groups in a cluster-inclusion hierarchy.
Identity Notes & Concept Scope
At the start of this three-candidate batch, compared all 442 pinned AIO and 662 native IDs, names, aliases and scoped synonyms against OHC, exact PoClustering and the PoClustering edge-clique-cover heuristic; no normalized identity match. Ignored- and hidden-inclusive fixed-string searches of the recovery, older discovery and original Documents checkouts returned 17, 0, 64 lines for the combined candidate terms. All lines were read. Recovery matches are pending discovery/source-reading notes; the older checkout has no matches; original-checkout hits are ECC certificate-authority names and eccenca namespaces in ignored dependency files, not clustering records. Semantic search including clustering, clique, poset, pyramid, fuzzy and DAG terms covered 41 AIO and 225 native definitions. The 41 AIO and 224 previously read native definitions were unchanged; the new Llama definition and full record were read. Eleven complete annotated AIO node/edge/generated contexts and five full native records were assessed. Retain the Jeantet et al. graph-density-tolerance expansion, distinct from nearest-neighbor Llama union rounds, SCC weak-component partitions, DBSCAN core-density connectivity, HDBSCAN persistence and OPTICS reachability ordering.
Claims & Grounded Evidence
6 Claims
Mechanism
#density-controlled-expansion
Increase pairwise-distance thresholds to grow a neighborhood graph. For each newly affected cluster, consider its most-linked neighboring points and accept expansion when the absolute change in induced graph-edge density is at most a supplied tolerance. Continue permitted growth, remove old clusters contained in the expanded ones and retain the new level. The density is 2E/[n(n−1)], with singleton density defined as one.
Mechanism
#overlapping-hierarchy
The intended output is a quasi-dendrogram: a directed acyclic cluster-inclusion structure with singleton leaves, a full-data root and potentially overlapping covers at intermediate levels. Hard membership in several clusters differs from a fuzzy membership probability. Graph-edge density is not the core-neighbor-count criterion of DBSCAN.
Scope
#parameter-extremes
The paper relates zero density tolerance to clique-like clusters and tolerance one to single-linkage-like connected grouping. Its statements about exactly the cliques or connected subgraphs must not be read as enumerating every contained subgraph: Algorithm 1 removes contained clusters. Simultaneous tied-neighbor expansion can also have a different density from each separate expansion. No exhaustive-clique or order-invariance guarantee is asserted here.
Limitation
#printed-specification-boundaries
The printed algorithm leaves the initialization and reset of its new-cluster list implicit and does not fully settle tied-neighbor and equal-distance edge processing. The neighborhood definition uses a metric and a less-than-or-equal threshold, while experiments use cosine dissimilarity and the path wording of Definition 3 says strictly less than the threshold. These passages are not adopted as a complete executable or universally metric specification.
Scope
#hierarchy-comparison
The proposed comparison averages best-match Jaccard similarities in both directions between cluster levels. Repeated levels with the same cluster count are paired by a greedy ordered correspondence before averaging across levels. This is a structural comparison of the produced hierarchies; the paper does not supply a proof that the greedy matching globally optimizes the stated correspondence objective.
Scope
#evaluation-and-runtime
Experiments compare SLINK, Ward and HDBSCAN* on 1000 random two-dimensional points and yearly sets of 1000 word vectors learned from Wiley abstracts. There is no known ground-truth hierarchy for the comparison. A fitted runtime trend of approximately n^2.45 at a particular density tolerance is empirical, not a worst-case complexity theorem or portable speed guarantee.
⚠️ Curated Limitations & Negative Results
- This record denotes the Jeantet, Miklós and Gross-Amblard OHC algorithm, not all overlapping hierarchical clustering methods.
- Exact graph density, tolerance, tie handling and edge ordering affect the construction. Properties about parameter extremes are retained as qualified source descriptions, not independently certified theorems.
- Standalone calculations test a static tied expansion and subset removal. They do not establish that the tied state is reached by a complete OHC execution or measure empirical clustering quality.
- The full 13-page primary chapter, all figures, equations, algorithm and references were read. Author code and alternative revisions were not inspected or executed; no benchmark replication or formal proof certification was performed. This record remains DRAFT.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:HierarchicalClustering
Hierarchical Clustering
|
related_match | OHC constructs an overlapping cluster hierarchy; this AIO target denotes the related task, not the specific graph-density algorithm or equivalence to a strict tree. |
AIO:UnsupervisedClustering
Unsupervised Clustering
|
related_match | Groups are constructed from supplied distances without reference labels. Structural comparisons to other hierarchies do not make the construction a supervised classifier. |
Evidence Sources & Primary Literature
1 Source| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
ohc2020
|
Ian Jeantet, Zoltán Miklós, David Gross-Amblard
|
primary paper
full_text
|
ID: doi:10.1007/978-3-030-44584-3_21
sha256:a27ca0bd28b6…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-14T00:19:00Z
Updated: 2026-10-14T00:19:00Z
Source File:
data/curated/OverlappingHierarchicalClustering.yaml