Leveraging Click Completion for Graph-based
Image Ranking
Xiaohong Qin, Yu He, Jun Wu
Beijing Key Lab of Traffic Data Analysis and Mining
Beijing Jiaotong University
Beijing 100044, China
Email: {14120420, 15120398, wuj}@bjtu.edu.cn
Yingpeng Sang
School of Information Science and Technology
Sun Yat-Sen University
Guangzhou 510006, China
Email: sangyp@mail.sysu.edu.cn
Abstract—Image ranking is a critical component in the image
search systems, and graph-based ranking has become a promising
way to enhance the retrieval effectiveness. Leveraging the click-
through data to facilitate the ranking is one of the current trends.
However, the sparse and noisy properties of the click-through
data make the exploitation of such resource difficult. To this
end, this paper proposes a click completion solution for graph-
based image ranking, which consists of two coupled components.
The first one is a click completion algorithm to handle the
sparseness. Another one is a soft-label graph ranking solution
to exploit the completed click-through data noise-tolerantly. We
conduct extensive experiments to evaluate the performance of
the proposed scheme for image retrieval, in which encouraging
results validate the effectiveness of the proposed techniques.
I. INTRODUCTION
Graph-based ranking has been extensively exploited recently
due to its effectiveness in various visual retrieval tasks, such
as natural image search [1], shape retrieval [2], cross-media
retrieval [3], 3D object retrieval [4], etc. Unlike traditional
ranking approaches that consider only pairwise similarity for
visual ranking, graph-based methods aim at exploring the
intrinsic manifold structure collectively hidden in images,
hoping to refine the similarity measure. Despite these suc-
cesses, the performance of graph-based ranking approaches is
still limited by the so-called semantic gap existing between
low-level image pixels captured by machines and high-level
semantic concepts perceived by humans, especially when the
visual targets are dispersed in the feature space.
In order to boost the performance of image retrieval and
overcome the semantic gap, a relevance feedback mechanism
[5] is incorporated into the graph-based ranking framework
[1], [6], [7], which encourages the user to label a few images
returned as either positive or negative in terms of whether
they are relevant to user’s query or not. The labeled instances
is then used to refine the ranking model towards the user’s
query intends. Nonetheless, it is not easy to obtain sufficient
and explicit user feedback as users are often reluctant to
provide enough feedback to search engines. It is noted that
search engines can record queries issued by users and the
corresponding clicked images. Although the clicked images
cannot reflect the explicit user preference on relevance of
particular query-image pairs, they statistically indicate the
implicit relationship between individual images in the ranked
list and the given query [8]. Therefore, we can regard click-
through data as the ’implicit’ user feedback based on an
assumption that, in a same query session, most clicked images
are relevant to the given query, and the reliability of this
assumption has been validated by [9].
We consider a particular ranking scenario where the click-
through data is incomplete and inaccurate, which makes the
exploration of such click-through data difficult. Concretely,
incompleteness may lead to an underfitting ranker, while
inaccuracy may mislead the ranker. To this end, we propose
a Click completion solution for Graph-based Visual Ranking
framework, CGVR for short. As shown in Fig. 1, our frame-
work first builds a neighbor graph on the image collection
to be ranked, then completes the user-image matrix using
a collaborative filter with the visual side-information of the
image graph, and lastly applies a soft-label graph ranker to
rank the images based on the completed click-through data
and the neighborhood graph.
The rest of this paper is organized as follows. Section 2
reviews the related works. Section 3 presents the proposed
CGVR method. Section 4 reports on the experiments. Finally,
section 5 concludes this paper and raises the problem for future
works.
II. R
ELATED WORK
In this section, we survey related works on graph-based
visual ranking and the use of click-through data/implicit
feedback. We do not survey the online relevance feedback
mechanisms [5] as our method requires no user intervention
once the query has been issued. This is motivated by empirical
evidence suggesting that few users are willing to perform any
form of feedback to improve their search results.
A. Graph-based visual ranking
Graph-based visual ranking has been extensively studied in
the multimedia retrieval area. Its main idea is to describe the
dataset as a graph and then decide the importance of each
vertex based on local or global structure drawn from the graph.
One canonical graph-based ranking technique is the Manifold
Ranking (MR) algorithm [10], and He et al.[1] first applied
MR to image retrieval. Its limitations are addressed by latter
research efforts. For example, Wang et al. [11] improved the
2016 17th International Conference on Parallel and Distributed Computing, Applications and Technologies
978-1-5090-5081-9/16 $31.00 © 2016 IEEE
DOI 10.1109/PDCAT.2016.43
155