Home / Curated / Algorithms / Exact PoClustering

Exact PoClustering

Algorithms AIMech:ExactPoClustering DRAFT

Aliases: Maximal-clique PoClustering

A dissimilarity-based clustering construction that accumulates maximal cliques of pairwise-distance threshold graphs and organizes their sets by inclusion with diameter labels, allowing overlapping clusters and multiple parents.

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 exhaustive threshold maximal-clique construction with diameter labels, distinct from PoClustering edge-cover pruning, OHC density-tolerance expansion, Llama neighbor unions and SCC weak-component partitions.

Claims & Grounded Evidence

6 Claims

Mechanism #threshold-maximal-cliques

At each distinct dissimilarity threshold, form the graph whose edges connect pairs at or below that value and enumerate its maximal cliques. Accumulate distinct clique sets across thresholds, label them by their diameters and order them by inclusion. Maximal means not contained in a larger clique at that threshold; it does not mean a single largest clique.

supports Source: Clustering Pair-wise Dissimilarity Data into Partially Ordered Sets · Locator: Section 3, Definitions 3.1–3.2 and Property 3.1, pp. 3–4; Section 4 and Algorithm 1, p. 4
supports Source: PoClustering: Lossless Clustering of Dissimilarity Data · Locator: Sections 3–4, Equation 3.1 and Theorem 4.1, PDF pp. 3–4

Scope #diameter-labelled-representation

Exact threshold edge coverage supplies a cluster containing each pair at its own dissimilarity threshold. Its dissimilarity is therefore recoverable as the minimum diameter among retained clusters containing that pair. The diameter labels are essential: scaling every nonzero distance preserves the unlabelled inclusion family while changing the numerical distances. The 2007 paper defers its broader correspondence-theorem proof to an uninspected technical report.

supports Source: Clustering Pair-wise Dissimilarity Data into Partially Ordered Sets · Locator: Section 3, Definitions 3.1–3.2 and Property 3.1, PDF pp. 3–4
supports Source: PoClustering: Lossless Clustering of Dissimilarity Data · Locator: Sections 3–4 and Theorem 4.1, PDF pp. 3–4; reference 12, p. 6

Limitation #inclusion-and-zero-distance

A smaller cluster diameter does not imply inclusion between arbitrary clusters, despite the biconditional wording in the 2007 abstract. The main construction uses inclusion as a separate relation. Also, allowing zero dissimilarity between distinct objects conflicts with simultaneously requiring every singleton and strictly increasing diameter along inclusion. A positive off-diagonal restriction or an explicit treatment of zero-distance equivalence is needed for those additional conditions.

supports Source: Clustering Pair-wise Dissimilarity Data into Partially Ordered Sets · Locator: Section 3 and Property 3.1, PDF pp. 3–4
supports Source: PoClustering: Lossless Clustering of Dissimilarity Data · Locator: Abstract, p. 1; Sections 3–4, pp. 3–4

Scope #exact-versus-heuristic

Enumerating all maximal cliques can produce exponentially many sets. The later edge-clique-cover heuristic retains a potentially smaller family intended to cover graph edges, rather than enumerating every maximal clique. Pairwise-distance information and full cluster-family recovery are different requirements, so this exact construction is kept distinct from that heuristic.

supports Source: Clustering Pair-wise Dissimilarity Data into Partially Ordered Sets · Locator: Sections 3–4, PDF pp. 3–4
supports Source: PoClustering: Lossless Clustering of Dissimilarity Data · Locator: Sections 4–5, PDF pp. 4–5

Limitation #pseudocode-boundaries

The 2006 printed driver updates a threshold-specific edge set while its loop condition names the original edge set, and leaves some initial collections implicit. Its incremental clique-update deletion test compares raw intersections with endpoint cliques; without adding the new edge endpoints that test does not perform the stated containment pruning. Equal-weight edges also require careful threshold-level handling. The mathematical threshold construction is not a certification of that literal pseudocode.

supports Source: Clustering Pair-wise Dissimilarity Data into Partially Ordered Sets · Locator: Algorithms 1–2 and accompanying text, PDF pp. 4–5

Scope #evaluation-scope

The 2006 Gene Ontology study derives gene dissimilarities from annotation categories and assesses recovery of those categories, rather than independently predicting function from expression alone. Its best-match Jaccard score is directional. Table values qualify conflicting prose summaries of accuracy and recovery, and they do not establish universal biological or clustering superiority.

supports Source: Clustering Pair-wise Dissimilarity Data into Partially Ordered Sets · Locator: Section 5, Tables 2–4 and evaluation definitions, PDF pp. 5–6

⚠️ Curated Limitations & Negative Results

This record covers the exact maximal-clique construction, not the later PoClustering edge-clique-cover heuristic or every abstract partially ordered set.
Numerical distance recovery requires retained diameter information and threshold edge coverage. The cited UNC technical report was not located in the bounded search and was not read; no general theorem certification is claimed.
Zero off-diagonal distances, tied thresholds and literal pseudocode require the stated qualifications. No unqualified NP-completeness claim is adopted from wording that lacks an explicit decision problem.
Finite exact examples illustrate representation, scaling, zero-distance and clique-cover boundaries; they are not an author implementation or benchmark.
All six pages of each 2006 and 2007 paper were read, including figures, algorithms, tables and references. No author code, datasets or alternative revisions were audited or executed. 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	The construction produces a cluster-inclusion partial order that generalizes a tree hierarchy. This maps to the related task, not a tree-equivalence or algorithm/task is-a assertion.
`AIO:UnsupervisedClustering` Unsupervised Clustering	related_match	The generic construction groups objects from supplied pairwise dissimilarities; annotation-derived evaluation inputs do not make its identity a supervised classifier.

Evidence Sources & Primary Literature

2 Sources

Source ID	Publication / Document	Type / Access	Reference & Checksum
`poclustering2006`	Clustering Pair-wise Dissimilarity Data into Partially Ordered Sets Jinze Liu, Qi Zhang, Wei Wang, Leonard McMillan, Jan Prins	primary paper full_text	sha256:35e67bb4051d…
`poclustering2007`	PoClustering: Lossless Clustering of Dissimilarity Data Jinze Liu, Qi Zhang, Wei Wang, Leonard McMillan, Jan Prins	primary paper full_text	ID: doi:10.1137/1.9781611972771.61 sha256:8cd93ac9ab3a…

Curation Provenance

Curator: Codex

Method: ai_assisted

Model: GPT-6

Created: 2026-10-14T00:19:02Z

Updated: 2026-10-14T00:25:48Z

Source File: data/curated/ExactPoClustering.yaml