GDP: Relation-Preserving Constrained Clustering from Graded Pairwise Supervision

Pairwise constrained clustering typically uses binary supervision, while graded relations may reflect weak evidence, mixed membership, or coarser-resolution agreement. The same intermediate grade can imply different cluster structures, while relational orderings may appear on different numerical scales. Preserving graded relations and forming explicit cluster assignments are distinct but coordinated tasks. We introduce Graded DualPair (GDP), separating these roles across Local and Global representations, coordinating their pairwise relations while using relative grade ordering for direct Global supervision. GDP-Hier extends this principle across prescribed hierarchy resolutions. Our theory analyzes the relation–partition design and establishes sufficient conditions for multi-resolution hierarchy recovery. Across diverse benchmarks, GDP achieves consistently strong and frequently leading clustering performance and remains robust to targeted grade recalibration, while GDP-Hier yields strong multi-resolution clustering with cross-level coherence.