Relevance and irrelevance graph based marginal Fisher analysis for image search reranking

•This paper presents a novel “Ranking Dimensionality Reduction” scheme and two dimensionality reduction algorithms.•The proposed scheme discovers the intrinsic structure of data and keeps the ordinal information in ranking and retrieval.•The proposed RMFA algorithm models the pairwise constraints of relevance-link and irrelevance-link into the relevance graph and irrelevance graph.•The proposed Semi-RMFA algorithm offers a more general solution for the real-world application.•The promising results on two popular, real-world image datasets demonstrate the robustness and effectiveness of the proposed scheme and algorithms.

Learning-to-rank techniques have shown promising results in the domain of image ranking recently, where dimensionality reduction is a critical step to overcome the “curse of dimensionality”. However, conventional dimensionality reduction approaches cannot guarantee the satisfying performance because the important ranking information is ignored. This paper presents a novel “Ranking Dimensionality Reduction” scheme specifically designed for learning-to-rank based image ranking, which aims at not only discovering the intrinsic structure of data but also keeping the ordinal information. Within this scheme, a new dimensionality reduction algorithm called Relevance Marginal Fisher Analysis (RMFA) is proposed. RMFA models the proposed pairwise constraints of relevance-link and irrelevance-link into the relevance graph and the irrelevance graph, and applies the graphs to build the objective function with the idea of Marginal Fisher Analysis (MFA). Further, a semi-supervised RMFA algorithm called Semi-RMFA is developed to offer a more general solution for the real-world application. Extensive experiments are carried on two popular, real-world image search reranking datasets. The promising results demonstrate the robustness and effectiveness of the proposed scheme and methods.