An interactive image retrieval system learns which images in the databasebelong to a user's query concept, by analyzing the example images and feedbackprovided by the user. The challenge is to retrieve the relevant images withminimal user interaction. In this work, we propose to solve this problem byposing it as a binary classification task of classifying all images in thedatabase as being relevant or irrelevant to the user's query concept. Ourmethod combines active learning with graph-based semi-supervised learning(GSSL) to tackle this problem. Active learning reduces the number of userinteractions by querying the labels of the most informative points and GSSLallows to use abundant unlabeled data along with the limited labeled dataprovided by the user. To efficiently find the most informative point, we use anuncertainty sampling based method that queries the label of the point nearestto the decision boundary of the classifier. We estimate this decision boundaryusing our heuristic of adaptive threshold. To utilize huge volumes of unlabeleddata we use an efficient approximation based method that reduces the complexityof GSSL from $O(n^3)$ to $O(n)$, making GSSL scalable. We make the classifierrobust to the diversity and noisy labels associated with images in largedatabases by incorporating information from multiple modalities such as visualinformation extracted from deep learning based models and semantic informationextracted from the WordNet. High F1 scores within few relevance feedback roundsin our experiments with concepts defined on AnimalWithAttributes and Imagenet(1.2 million images) datasets indicate the effectiveness and scalability of ourapproach.