Density-Aware Pairwise Constraint Propagation via Bidirectional Trees

Pairwise Constraints are widely used in semi-supervised learning. However, their limited quantity often restricts performance. To address this issue, pairwise constraint propagation (PCP) algorithms have been proposed to extend initial must-link and cannot-link constraints to more samples. In this paper, we propose an algorithm for density-aware pairwise constraint propagation via bidirectional trees to overcome the limitations of existing methods on complex manifold data. The approach constructs a hierarchical topology driven by local density, where each sample is associated with leader and follower points, forming bidirectional propagation trees. A sparse similarity matrix is built using both density differences and Euclidean distances, and a multi-path weighted mechanism computes propagation scores. Finally, an empirically selected optimal threshold is used to binarize the results and produce refined pairwise constraints. Experimental results demonstrate that the proposed method outperforms state-of-the-art PCP algorithms in terms of constraint accuracy and clustering performance.