TriHex-Cluster: Multi-Level Overlapping Clustering from Triangular Graph Stars

Abstract

We introduce TriHex-Cluster, a hierarchical overlapping clustering framework built on the self-similar geometry of the triangular lattice (6-regular planar graph). The primary algorithm is regime C (greedy 2-packing followed by Voronoi completion), a practical hierarchical clustering method producing disjoint clusters with the Voronoi-contact graph GVor(k+1) as the next-level graph and aggregation complexity O(nlogn) (embedding cost excluded). On regular triangular domains with near-perfect packings, regime C achieves n(k+1)≤n(k)/7+O(n(k)) per level; the measured depth on finite data is K*=⌈log7n⌉±1. Two variants complete the framework: regime A (full-overlap edge-induced, C(k)=V(k)) adds native overlap semantics by preserving the EI meta-graph 6-regularity without reducing the vertex count; regime B (deterministic index-7 sublattice, C(k)=Λk with a=2−ω) is a theoretical construction establishing an exact sublattice density ratio of 7 per level on the infinite lattice T, and exact termination in K=log7n levels on finite periodic domains with n=7K. Unconditional results: EI 6-regularity in regime A; perfect star-tiling and exact index-7 structure in regime B; strict hierarchy via Voronoi-completed clusters in regime C; tile-shape alternation proven at levels 1–2 (hexagonal, then triangular-like) and conjectured, with numerical verification, beyond; hWard (as an unnormalised SSE) strictly admissible and hmax weakly admissible. Aggregation complexity, embedding excluded: O(nlogn) in regime C, O(n) in regime B, O(n·Kmax) in regime A. We provide a fully reproducible reference implementation (trihex2, MIT-licensed) with extensive parameter sweeps on UCI benchmarks, synthetic Gaussians, non-convex shapes, and overlapping distributions. The genuine contributions of the framework are the multi-scale hierarchical structure with provable geometric guarantees and, in regime A, native overlap semantics that no hard-clustering baseline can provide. A central empirical finding concerns the embedding: an ablation isolating the 2D-lattice projection shows it to be the main bottleneck, and a lattice-free variant that runs the same combinatorial core directly on a k-nearest-neighbour graph in the original feature space—with no embedding and no quantisation—removes the projection entirely and improves accuracy on six of seven pilot datasets. With a frozen, fully unsupervised meta-selection rule (graph-geodesic arbitration between a convex-consensus and a graph-min-cut candidate, no per-dataset tuning), this variant reaches ARI 0.871 on moons and 1.000 on circles, where k-means, HAC, and GMM all collapse to ≤0.43 and ≤0.00, respectively. On a 73-dataset benchmark (23 real UCI, 50 synthetic, all loaded with validated class labels), TriHex is the most frequently best method on the synthetic panel (46% win rate) and close behind GMM overall (34% versus 36%), while having the lowest mean ARI—the signature of a specialist: it dominates on non-convex structure (rings, spirals, manifolds) and is outperformed on convex tabular data, where we make no claim of superiority. We also report a genuine robustness limitation: with the default configuration, TriHex fails on Cancer (ARI 0.042, essentially uncorrelated with the ground truth) because the default lattice over-fragments a two-class problem; competitive performance requires a dataset-appropriate configuration, and we report this explicitly rather than only the best configurations. On overlapping Gaussians, regime A detects the boundary points that the data-generating process itself classifies as ambiguous with precision 1.00 at heavy overlap (δ=0.5); the detector over-flags as the clusters separate (precision falls to 0.43 at δ=3.0), so its usefulness is confined to the strong-overlap regime. Within that regime, it provides a measurable capability unavailable to hard-clustering baselines.