Density-aware Hierarchical Clustering Based on Element-Categorized Connection Subgraphs

This paper, titled Density-aware Hierarchical Clustering Based on Element-Categorized Connection Subgraphs by Yuning Yu, José Rodríguez-Piñeiro, Xuefeng Yin, and Bin Feng, proposes a novel two-stage density-aware hierarchical clustering algorithm (DHC-ECS) that integrates hierarchical clustering, density-based clustering, and graph clustering principles.

The authors identify that traditional hierarchical clustering methods calculate inter-cluster similarity predominantly from pairwise distances (minimum, maximum, average, centroid), which overlooks density variations and structural connectivity in graphs. They note that these simple similarity definitions have some drawbacks and cannot cope with the datasets close to each other, or without hyperspherical shapes and nonuniform sizes. Although algorithms like Chameleon consider relative interconnectivity and relative closeness, existing graph-based hierarchical clustering algorithms primarily evaluate inter-cluster similarity according to global graph cut criteria, while the structural characteristics of the connection region between adjacent sub-clusters are only implicitly considered. The authors emphasize the duality between vertices and edges as an intrinsic property of the fully connected graph of the original data, arguing that Vertices and edges provide complementary characterizations of the underlying data structure, analogous to the concept of 'yin' and 'yang' in traditional Chinese philosophy.

A key motivation is that existing approaches "predominantly focus on constructing density-driven hierarchical structures... they mainly characterize clusters from the perspective of density distribution, and graph or tree structures primarily serve as computational substrates for density-based hierarchy construction. The open challenge remains how to jointly exploit density consistency, structural consistency, adaptive cluster merging, and automatic hierarchy selection within a unified framework."

The paper also addresses the challenge of parameter selection, positing the existence of intrinsic and dataset-independent thresholds under a specified clustering evaluation criterion. The authors argue that "instead of relying on manually specified parameters or parameter-free strategies that implicitly search for optimal configurations, an alternative direction is to identify and explicitly exploit the intrinsic threshold induced by the underlying data structure."

The proposed algorithm operates in two stages:

First stage (Greedy merging): Each observation is initially regarded as a separate cluster, and sub-clusters are merged iteratively through a greedy method, where similarity is calculated based on the average distance between points in different clusters:

• di,j = (1/(CiCj)) Σ Σ dist(p,q), with wi,j = 1/(di,j + 1), and Si,j = wi,j.

• Geodesic distance is adopted rather than Euclidean distance for datasets with manifold structures, computed via KNN-based shortest path calculations.

• The stopping condition for this stage is when the number of sub-clusters equals the threshold Tn, commonly set to √N.

Second stage (Refined merging): Since sub-clusters become larger, the average similarity is insufficient. The algorithm constructs a KNN graph for the entire dataset, defined as GKNN = (V, EKNN), where EKNN = u,v u ∈ Nk(v)(v) or v ∈ Nk(u)(u).

The core novelty is the KNN connection subgraph, defined as a subgraph constructed from the vertices in two clusters Ci, Cj involved in inter-cluster KNN linkage and their KNN neighbors, denoted Gi,jKNN = (Vi,jKNN, Ei,jKNN). The vertices and edges within this connection region are explicitly categorized:

• Linkage points: the set of vertices connecting the two neighboring sub-clusters — points in one cluster that have KNN connections to points in the other cluster.

• Linkage edges: the set of edges connecting Vi and Vj in Vi,jlinkage — edges that straddle the two sub-clusters.

• Internal points: the set of points connected to linkage points but not contributing to the KNN connection between the two sub-clusters.

• Internal edges: the set of edges that connect the linkage points and internal points... but are not part of the linkage edge set.

• Point density: defined as kernel density, D(x) = Σy∈Nk(x)(x) exp(−dist(x,y)).

The similarity between two sub-clusters is defined as:

Si,j = 2·LC / ((LS − 1 + 1) alpha · (DS − 1 + 1) alpha)

This metric integrates four key indices:

• Link Compactness (LC): the ratio between the sum of weights of linkage edges and internal edges, representing the linkage compactness between two sub-clusters.

• Link Similarity (LS): the ratio between the average weights of linkage edges and internal edges.

• Density Similarity (DS): the ratio between average density of linkage points and average density of internal points connecting to linkage points.

• Coefficient of Variation (CV): CV = std(W(elinkage ∪ einternal)) / mean(W(elinkage ∪ einternal)), used to adapt to randomness in point distribution. The parameter alpha = e(−r·CV), where r is fixed to 3.

According to the paper, When the variation of edge weights and point density is large, corresponding to a large CV, the similarity decreases automatically as alpha approaches 0... the link compactness LC becomes more significant. The algorithm terminates when the similarity for any pair of clusters is lower than the predefined threshold Ts, or the number of clusters equals the predefined value.

The paper highlights that the proposed algorithm differs from traditional methods in three key aspects: "(1) providing a more detailed description of the KNN connection subgraph structure through element categorization to separate vertices and edges into internal and interconnected components, representing intra-cluster and inter-cluster similarity respectively; (2) incorporating density and randomness information into similarity estimation; and (3) focusing on boundary connection regions of sub-clusters to achieve a more refined characterization."

The algorithm was evaluated on ten synthetic datasets: 2circles, Halfkernel, Aggregation, Flame, Jain, Pathbased, R15, Spiral, Two circle noise, and Compound. It was compared against hierarchical clustering with traditional similarity metrics (minimum, maximum, centroid, mean distance), ACHAMELEON, RNN-DBSCAN, McDPC, and G-RMS, using four external evaluation indices: NMI, ARI, FMI, and Purity.

Key findings from the experiments:

1. Hierarchical clustering method based on traditional similarity metrics performs quite unstably on these datasets, due to the different features of data distributions.

2. Apart from Spiral, Pathbased, and Compound, the ACHAMELEON algorithm performs well on most datasets with NMI larger than 0.97.

3. RNN-DBSCAN and McDPC perform well on most datasets except Halfkernel for RNN-DBSCAN, and Compound for McDPC. In addition, the parameter tuning for these two algorithms is heuristic and time-consuming...

4. "Although the clustering results of the proposed DHC-ECS algorithm are not the best for all datasets, it exhibits better robustness and obtains good results for all these datasets (e.g., the NMI values for all the 10 datasets are larger than 0.95)."

Notably, the authors report that "although these datasets exhibit distinct features, the parameter applied to all the datasets are quite similar... except the threshold of similarity for stop condition (the mean value of Ts is around 0.38 and the variation is moderate). This provides empirical evidence for the existence of intrinsic thresholds. The parameter Ts has an intuitive interpretation: a smaller threshold allows more sub-clusters to be merged, resulting in coarser clustering results, whereas a larger threshold produces finer partitions."

The overall worst-case computational complexity of DHC-ECS is O(N3), dominated by the first-stage hierarchical merging, with space complexity of O(N2). The first stage complexity is consistent with the naive hierarchical clustering and can be reduced to O(N2 log N) through a priority-queue implementation. The second-stage complexity is significantly smaller, approximately O(Tn2), because "DHC-ECS computes the proposed similarity only for cluster pairs connected through the ECS... the practical computational cost of the second-stage is usually much lower than that of exhaustive hierarchical merging, especially for sparse neighborhood graphs."

The paper concludes that "the proposed algorithm exhibits superior robustness and performs well across all these datasets compared to the aforementioned algorithms. This highlights the effectiveness and applicability of the DHC-ECS algorithm to obtain more refined clustering results across datasets with different features, including convex and non-convex shapes, uniform and non-uniform densities, balanced or unbalanced distributions, single-centered or multi-centered structures. The authors note that due to the influence of the 'curse of dimensionality', both distance and density estimations, as well as structural information should be re-evaluated in the high-dimensional spaces, and future work includes conducting extended experiments on high-dimensional datasets, and searching for improvements on computational complexity to accommodate to larger datasets."

Improvement 1: Density- and structure-aware cluster merging for AI clustering modules

Replace conventional inter-cluster similarity metrics (minimum, maximum, average, centroid) with the proposed ECS-based similarity that jointly uses link compactness (ratio of linkage-edge weights to internal-edge weights), link similarity, density similarity (ratio of average density of boundary points to internal connection points), and a coefficient-of-variation penalty. The improved AI system can cluster datasets with non-convex shapes, non-uniform densities, unbalanced cluster sizes, and close/overlapping boundaries without requiring hyperspherical cluster assumptions.

Improvement 2: Explicit categorization of connection subgraphs for graph-based learning

Adopt the element-categorized KNN connection subgraph (ECS) concept: separate vertices/edges into linkage points, linkage edges, internal points, internal edges when evaluating relationships between clusters or communities. The improved AI system can detect meaningful boundaries between communities in graph data, quantify inter-community versus intra-community connectivity, and produce more interpretable merging decisions in hierarchical graph clustering or graph neural network pooling.

Improvement 3: Automatic, intrinsic threshold selection based on structural consensus

Replace manual parameter tuning (e.g., distance thresholds, cluster count) with the identification of intrinsic thresholds that are dataset-independent under a given evaluation criterion, as demonstrated by the stable stopping threshold (≈0.38) across 10 distinct synthetic datasets. The improved AI system can automatically choose when to stop merging clusters in unsupervised learning pipelines, reducing user intervention and improving generalization across varied real-world datasets.

Improvement 4: Two-stage hierarchical merging for scalability and robustness

Use a two-stage process: (1) fast greedy merging based on average pairwise distances (with geodesic distances for manifold data) until a compact initial partition is reached, and (2) refined merging using ECS-based similarity only on cluster pairs connected in the KNN graph. The improved AI system can handle large datasets more efficiently than exhaustive hierarchical clustering, while retaining the ability to model complex, low-density connection regions and avoid premature merging of distinct clusters.

Improvement 5: Adaptive similarity recalibration via coefficient of variation

Apply the proposed adaptive exponent α = e(−r·CV), where CV measures the variation of edge weights and point density in the connection region, to automatically down-weight unreliable similarity estimates. The improved AI system can adjust its sensitivity based on local randomness and density fluctuations, preventing spurious cluster merges when boundary data are noisy and emphasizing connectivity when boundary data are consistent.

Improvement 6: Improved density estimation at cluster boundaries

Use kernel-density-based point density (with KNN-neighbor distances) to characterize linkage points and internal points, rather than raw point counts or average distances. The improved AI system can distinguish clusters of highly different local densities and correctly identify bridge points that weakly connect dense regions, leading to more accurate cluster separation in applications like anomaly detection, image segmentation, and document topic modeling.

What the improved AI system can do as a whole

The enhanced AI system can perform end-to-end unsupervised clustering and graph-structured data analysis with:

• High robustness on benchmarks with convex/non-convex shapes, uniform/non-uniform densities, balanced/unbalanced distributions, and single/multi-centered structures (achieving NMI > 0.95 across all tested datasets).

• Automatic determination of final cluster numbers without exhaustive parameter sweeps.

• Explicit modeling of both vertex (density) and edge (connection) information, leveraging the duality between vertices and edges to capture richer structural semantics.

• Scalability to larger datasets through sparse KNN graphs and connectivity-restricted merging, while preserving the quality of fine-grained boundary analysis.