Heterogeneous Constraint Propagation with Constrained Sparse Representation

This paper presents a graph-based method for heterogeneous constraint propagation on multi-modal data using constrained sparse representation. Since heterogeneous pair wise constraints are defined over pairs of data points from different modalities, heterogeneous constraint propagation is more challenging than the transitional homogeneous constraint propagation on single-modal data which has been studied extensively in previous work. The main difficulty of heterogeneous constraint propagation lies in how to effectively propagate heterogeneous pair wise constraints across different modalities. To address this issue, we decompose heterogeneous constraint propagation into semi-supervised learning sub problems which can then be efficiently solved by graph-based label propagation. Moreover, we develop a constrained sparse representation method for graph construction over each modality using homogeneous pair wise constraints. The experimental results in cross-modal retrieval have shown the superior performance of our heterogeneous constraint propagation.