Semi-Supervised Deep Hashing with a Bipartite Graph

1 Introduction

With the explosion in the volume of image data, it has been raised as a big challenge about how to index and organize these data efficiently and accurately. Approximate Nearest Neighbor (ANN) search [Indyk and Motwani, 1998] has become a popular way to retrieve content from images with both computational efficiency and search quality. Among existing ANN search methods, hashing is advantageous due to its fast query speed and low memory complexity [Gionis et al., 1999; Gong et al., 2013]. It aims to transform high-dimensional images into a set of short binary codes while maintaining similarity of the original data.

Generally speaking, hashing methods can be divided into two categories: unsupervised and supervised. Unsupervised methods utilize some kinds of distance metrics to learn a hash function from unlabeled data. Methods in this category include data-independent ones like Locally Sensitive Hashing

(LSH) [Gionis et al., 1999] and data-dependent ones like Iterative Quantization (ITQ) [Gong et al., 2013], Spectral Hashing (SH) [Weiss et al., 2009], Anchor Graph Hashing (AGH) [Liu et al., 2011]. On the other hand, to deal with more complicated semantic similarity, supervised hashing methods are proposed to exploit label information to improve the hashing quality. Representative supervised methods include Latent Factor Hashing (LFH) [Zhang et al., 2014], Fast Supervised Hashing (FastH) [Lin et al., 2014], Supervised Discrete Hashing (SDH) [Shen et al., 2015]. However, labeling largescale image dataset is inefficient and time-consuming. As a result, Semi-Supervised Hashing (SSH) [Wang et al., 2012] has been developed to make use of labeled data as well as the abundant unlabeled data.

In traditional hashing methods, images are represented by hand-crafted features such as GIST [Oliva and Torralba, 2001], and the choice of features requires heavy manual interventions. Motivated from the great success of deep neural networks in image analysis [Krizhevsky et al., 2012], recently some deep hashing methods have been proposed to learn features and hash codes simultaneously [Li et al., 2016; Zhu et al., 2016; Liu et al., 2016]. Although those deep hashing methods yield better performance compared with the traditional methods, they usually need a large number of labeled instances as training data. To address this limitation, a semisupervised deep hashing, named SSDH, have been developed [Zhang et al., 2016]. SSDH is fundamentally built upon graph-based semi-supervised learning [Zhou et al., 2004] and the loss function contains a graph regularization term which involves both the labeled and unlabeled data. In theory, SSDH needs to construct a nearest neighbor graph of all the data. Unfortunately, this step takes O(n2 ) time, where n is the number of instances, and thus intractable for large scale data.

In this paper, we propose a novel semi-supervised hashing method, named Deep Hashing with a Bipartite Graph (BGDH), which performs graph embedding, feature learning and hash code learning in a unified framework. First, we construct a bipartite graph to capture the information hidden in the labeled and unlabeled data. The bipartite graph could be a semantic graph that describes relationships between images and concepts, an anchor graph that describes similarities between images and landmarks [Liu et al., 2010], or a traditional nearest neighbor graph. Then, inspired by the recent work on graph embedding [Yang et al., 2016], we learn an embedding for each instance to predict the neighborhood context in the graph. Finally, we feed both raw pixels and embeddings to a deep neural network, and concatenate the corresponding hidden layers when producing binary codes. BGDH is a general learning framework in the sense that any loss function of hashing and any type of graph can be incorporated.

Graph-based methods are usually transductive, because they can only handle instances that are already appeared in the graph. Since embeddings of instances are learnt from the graph, the basic BGDH is also transductive. To address the out-of-sample problem, we further propose an inductive variant of BGDH, in which the embeddings are defined as a parametric function of the raw features. In this way, we can produce hash codes for new instances that have not seen during training. To demonstrate the effectiveness of our approach, we conduct extensive experiments on two large-scale datasets: CIFAR-10 and NUS-WIDE. Experimental results show that BGDH outperforms other methods and achieves the state-of-the-art performance in image retrieval.

Finally, we emphasize that although both BGDH and SSDH are semi-supervised deep hashing methods, the proposed BGDH differs from SSDH in the following two aspects:

1. While SSDH is built upon graph regularization, our BGDH relies on graph embedding.
2. SSDH uses graphs to exploit the unlabeled data, in contract BGDH makes use of bipartite graphs, which can be constructed more efficiently since building an anchor graph only costs O(n) time.

2 Notations and ProblemDefinitions

In this section, we introduce notations and problem definitions.

2.1 Notations

We use script letters like X to denote sets, boldface lowercase letters like e to denote vectors and boldface uppercase letters like E to denote matrices. We denote the element at the i-th row and j-th column of E by Eij. ET is the transpose of E. ‖·‖2 denotes the Euclidean norm of a vector and ‖·‖F denotes the Frobenius norm of a matrix. sgn(·) is an element-wise sign function and σ(·) is the sigmoid function. [u; v] denotes the concatenation of two vectors u and v.

2.2 ProblemDefinitions

Given a set of n instances/images X = {xi}ni=1 where xi is the feature vector of the i-th instance. Without loss of generality, we assume the first l instances {x1, . . . , xl} are labeled and the rest are unlabeled. We assume the supervised information is given in term of pairwise labels, though our method can also support other kinds of labels. Specifically, for the first l instances, we have a set of pairwise labels S = {sij} with sij ∈ {0, 1}, where sij = 1 means that xi and xj are similar, sij = 0 means that xi and xj are dissimilar. In addition, a bipartite graph G = (X,O, E) between n instances and m objects are given, where O is a set of objects such as concepts or landmarks, and E is the set of edges.

The goal of our semi-supervised hashing method is to learn a mapping function H : xi → {-1, 1}c , which encodes each point xi into a c-dimensional binary code bi = H(xi) = [h1(xi), h2(xi), · · · , hc(xi)]T ∈ {-1, 1}c . The binary codes B = {bi}ni=1 should preserve the semantic similarity and structure similarity in the Hamming space.

3 Semi-Supervised Deep Hashing with a Bipartite Graph

In this section, we first present the details of our semisupervised Deep Hashing with a Bipartite Graph (BGDH), then introduce an inductive variant and finally discuss the learning procedure.

3.1 The Proposed BGDH Framework

The end-to-end deep learning architecture of our BGDH is shown in Figure 1, which includes three main components: graph embedding, feature learning, and hash code learning. Similar to other semi-supervised learning methods [Yang et al., 2016], the loss function of BGDH can be expressed as

where Ls is a supervised loss designed to preserve the similarity between pairwise instances, and Lg is an unsupervised loss of predicting the graph context. In the following, we first introduce Lg which aims to learn embeddings from the bipartite graph G, then formulate Ls which is used to learn both features and binary codes from hidden layers of deep networks.

Graph embedding

We propose to use a bipartite graph G = (X,O, E) to capture the information hidden in the unlabeled data. It can be constructed in different ways as stated below.

• An anchor graph constructed from the dataset X. In this case, O contains m landmarks and the construction of G takes O(n) time [Liu et al., 2010].
• A nearest neighbor graph. In this case, O = X and the construction of G takes O(n2 ) time.
• A semantic graph constructed from external data. In this case, O may contain m concepts, styles, or owners.

In the following, we briefly introduce one way to construct an anchor graph. We first randomly sample m instances from X as landmarks, denoted by O = {o1, . . . , om}. Then, we put an edge between xi and oj if oj is among k nearest landmarks of xi, or if the distance between them is smaller than some threshold ϵ. Let A ∈ Rn×m be the similarity matrix of G, where Aij denotes the weight of the edge between xi and oj . The value of Aij may be binary, that is, Aij = 1 if there is an edge, otherwise 0. If a real value is preferred, Aij can be set according to the heat kernel: Aij = e-‖xi-oj‖22 /ρ , where ρ > 0 is a parameter.

The goal of graph embedding is to learn an embedding for each instance that predicts the context in the graph. Given an instance and its context, the objective of graph embedding is usually formulated as minimizing certain loss of predicting the context using the embedding of an instance as input feature [Weston et al., 2012; Mikolov et al., 2013]. The context of an instance can be simply defined as its neighbors in the graph, or generated by sophisticated methods such as random

Algorithm 1 Context generation based on random walk

• 1: Input: A bipartite graph G = (X,O, E), parameters r and d
• 2: Uniformly sample an instance i fromX
• 3: Uniformly sample a random variable u from [0, 1]
• 4: if u < r then
• 5: γ ←+1
• 6: Uniformly sample a random walk sequence S of length d started from i
• 7: Uniformly sample a context c from S except i
• 8: else
• 9: γ ←-1
• 10: Uniformly sample context c fromX
• 11: end if
• 12: return (i, c, γ)

network is presented in Table 1, and a detailed explanation can be found in [Li et al., 2016]. The output of the last feature learning layer (full7) of labeled instance xi is represented by φ(xi; θx), where θx denotes all the parameters in the seven layers of feature learning part. In contrast with existing supervised hashing methods, we also learn features from embeddings of labeled instances. The output associated with embedding ei is denoted by ψ(ei; θe), where θe contains all the parameters in hidden layers. In this paper, we only add one fully-connected layer for embeddings, of which the size is determined by the dimension of embeddings.

We concatenate φ(xi; θx) and ψ(ei; θe) as a new feature for instance i, then send it to a hash code learning layer as:

where M ∈ R(4096+d)×c denotes a weight matrix, d is the dimension of embedding, and v ∈ Rc×1 is a bias vector. Note that any supervised loss function of hashing can be used in our framework to learn parametersMand v. In this paper, we

walk [Perozzi et al., 2014]. Following previous studies [Yang et al., 2016], we present a simple procedure for context generation in Algorithm 1, where the parameter d is the length of the random walk and r ∈ (0, 1) determines the ratio of positive contexts.

By invoking Algorithm 1 t times, we obtain a set of triples {(ij, cj, γj)}tj=1 where γj = 1 indicates node cj is a context of node ij, and γj = -1 indicates cj is not a context. Let eij be the embedding of node ij, and wcj be the parameters for predicting node cj as a context. We define the objective function of graph embedding

where ℓ(·, ·) is a loss that measures the discrepancy between e⊤ij wcj and γj. In machine learning, the following losses are commonly used.

• The square loss

• The logistic loss

To constrain the solution space, we may further impose sparse constraints or nonnegative constraints [Lee and Seung, 1999].

Feature learning and hash code learning

We utilize deep neural network model to learn features from the raw pixels and embeddings of labeled instances, and then combine them together to learn the hash codes. BGDH contains a CNN model to learn features from raw image pixels, and the model has seven layers as those of CNN-F [Chatfield et al., 2014] while other networks like AlexNet [Krizhevsky and Hinton, 2009] can be used too. The configuration of the choose the loss function of deep pairwise-supervised hashing (DPSH) [Li et al., 2016], and Ls is given by

where Θij = 1 2 uTi uj and η > 0 is a regularization parameter. By substituting Eq. (3) into Eq. (4), we obtain the final loss function of the supervised part:

The objective of BGDH

We combine the supervised part and unsupervised part to form the transductive version of BGDH. From (2) and (5), the loss function of BGDH is

where λ > 0 is a constant weighting factor. The first two terms are the loss of predicting pairwise labels and the third one is the loss of predicting context. As a result, our BGDH can simultaneously learn embeddings, features, and hash codes. During the training phase, semantic similarity can affect graph embeddings, at the same time structure of data also influence the prediction of pairwise labels.

3.2 An Inductive Variant

Note that the basic BGDH is transductive, because the embeddings of instances are learnt from the graph. Since the hash code of an instance depends on both the raw pixels and its embedding, we need to design a way to infer the embedding of a unseen instance. To this end, we insert hidden layers to connect the raw pixels and embedding [Yang et al., 2016], and in this way, the embedding ei becomes a parameterized function of xi, denoted by ξ(xi; ϑx). The loss function of inductive hashing model can be written as:

We can predict the hash code of any point xq /∈ X as:

3.3 Learning

In the transductive version of BGDH, the optimization variables include M, v, {bi}, θx, θe, {ei} and {wc}. We adopt stochastic gradient descent (SGD) [Bottou, 2010] to train our model.

First, we sample a batch of labeled instances of which set I1 contains indexes. A gradient step is then taken to optimize the supervised loss Ls. For all i ∈ I1, bi can be directly optimized as follow:

For other parameters in Ls, i.e., M, v, θx, θe, and {ei : i ∈ I1}, we use back propagation (BP) to optimize them. Derivatives of Ls w. r. t. ui are presented as follows:

where aij = σ( 12 uTi uj). We can then update other parameters according to

Then, we perform a gradient step to optimize the unsupervised graph embedding loss Lg calculated by sampling triples generated in Algorithm 1. In this case parameters {ei,wc : (i, c) ∈ I2} will be updated where I2 denotes the set containing indexes of sampled instances and contexts. The above procedures are repeated for T1 and T2 iterations respectively.

The whole learning algorithm of BGDH is summarized in Algorithm 2. Notice that before training jointly, we first train unsupervised part for a number of iterations to learn the initialization embeddings {ei}. For the inductive variant, we will update parameters ϑx instead of embeddings {ei}.

Algorithm 2 Learning algorithm for BGDH

• 1: Input: A bipartite graph G = (X,O, E), images X = {xi}ni=1 , pairwise labels S = {sij}, parameters η, λ, batch iterations T1, T2 and sizes N1, N2
• 2: Output: Binary codes B = {bi}ni=1
• 3: Initialization: Initialize θx with the pre-trained CNN-F model on ImageNet; Initialize each entry of M, v, and θe by randomly sampling from a Gaussian distribution with mean 0 and variance 0.01.
• 4: REPEAT
• 5: for t ← 1 to T1 do
• 6: Randomly sample N1 labeled images, and let I1 be the set containing indexes of sampled instances
• 7: Calculate φ(xi; θx) and ψ(ei; θe) for all i ∈ I1 by forward propagation
• 8: Compute ui =MT [φ(xi; θx); ψ(ei; θe)]+v and the binary code of xi with bi = sgn(ui) for all i ∈ I1
• 9: Compute the derivative of Ls w. r. t. {ui : i ∈ I1}
• 10: Update parameters M, v, θx, θe, and {ei : i ∈ I1} by back propagation
• 11: end for
• 12: for t ← 1 to T2 do
• 13: Randomly generate a batch of triples by invoking Algorithm 1 N2 times, and let I2 be the set containing indexes of sampled instances and contexts
• 14: Compute the derivative of Lg w. r. t. {ei,wc : (i, c) ∈ I2}
• 15: Update parameters {ei,wc : (i, c) ∈ I2}
• 16: end for
• 17: UNTIL stopping
• 18: Calculate bi = sgn (MT [φ(xi; θx); ψ(ei; θe)] +v) for i = 1, . . . , n

4 Experiments

In this section, we present experimental results. All the experiments are performed on a NVIDIA K80 GPU server with MatConvNet [Vedaldi and Lenc, 2014].

4.1 Datasets and Setting

We conduct experiments on two widely used benchmark datasets: CIFAR-10 and NUS-WIDE. The CIFAR-10 dataset 1 consists of 60, 000 images from 10 classes (6000 images per class). It is a single-label dataset. The NUS-WIDE dataset 2 contains 269, 648 images from Flickr. Following the settings in [Lai et al., 2015], we use 19,5834 images belonging to the 21 most frequent classes and each class consists at least 5000 images. Additionally, two images are defined as a groundtruth neighbor when they share at least one common label.

In our experiments, BGDH-T denotes transductive model while BGDH-I denotes inductive one. We compare our method with several state-of-the-art methods including unsupervised methods: ITQ [Gong et al., 2013], LSH [Gionis et al., 1999], IsoH [Kong and Li, 2012] and SpH [Heo et al., 2012]; supervised methods: LFH [Zhang et al., 2014], FastH

1 https://www.cs.toronto.edu/ kriz/cifar.html

2 http://lms.comp.nus.edu.sg/research/NUS-WIDE.htm

[Lin et al., 2014], SDH [Shen et al., 2015] and COSDISH [Kang et al., 2016]; supervised deep hashing methods: DPSH [Li et al., 2016], DHN [Zhu et al., 2016] and DSH [Liu et al., 2016]; semi-supervised deep methods SSDH [Zhang et al., 2016].

For hashing methods using hand-crafted features, we represent each image in CIFAR-10 by a 512-dimensional GIST vector. In NUS-WIDE, an image is represented by a 1134dimensional feature vector, including 500-D bag-of-words features, 64-D color histogram, 144-D color correlogram, 73D edge direction histogram, 128-D wavelet texture, 225-D block-wise color moments. For deep methods, we use the raw image pixels as input. The network architectures of these deep models are different from each other, for fair comparison, we adopt the same deep network architecture CNN-F with the same initialization parameters pre-trained on ImageNet [Deng et al., 2009] for all deep hashing methods. The bipartite graph of BGDH is constructed based on handcrafted features with heat kernel, where the hyper-parameter ρ is set as 1 for CIFAR-10 and 10 for NUS-WIDE. The hyperparameter η in BGDH is set as 10 for CIFAR-10 and 100 for NUS-WIDE similar to DPSH [Li et al., 2016]. We simply set T1 = 10, T2 = 5, λ = 0.1 in all the experiments.

4.2 Experimental Results

To evaluate the retrieval accuracy, we use the Mean Average Precision (MAP) as the evaluation metric. Following [Lai et al., 2015; Xia et al., 2014], 1000 images (100 images per class) are randomly selected as the query set in CIFAR-10. We use all the rest of images as training set for the unsupervised methods and for building a neighbour graph G in BGDH. We randomly select 5000 (500 images per class) images as the training set for supervised methods.

In NUS-WIDE, we randomly sample 2100 query images from 21 most frequent labels following the strategy in [Lai et al., 2015; Xia et al., 2014]. We use all the rest of images as training set for the unsupervised methods. To reduce the time complexity, we only use 5000 landmarks sampled randomly to build a bipartite graph for BGDH. For supervised methods, we randomly select 10500 images from dataset. The MAP values are calculated within the top 5000 returned neighbors.

We present the MAP results in Table 2 where BGDH, SSDH, DSH, DHN, DPSH are deep methods. Except for SSDH which uses triplet labels, all deep methods are trained with pairwise labels. To be fair, parameters of these methods are set according to the suggestions of authors. The results show that in most cases our proposed BGDH method substantially outperforms other baselines including unsupervised methods, supervised methods and semi-supervised methods.

In real applications, the number of labeled instances is usually far less than that of unlabeled instances. To further verify the effectiveness of leveraging both pairwise labels and unlabel data, we reduce the number of labeled instances while other settings remain the same. For supervised learning, in CIFAR-10, we randomly select 2500 (250 images per class) images and in NUS-WIDE, we randomly select 5000 images. The MAP results with this experiment setting are listed in Table 3. Note that the results of unlisted unsupervised methods are the same as those in Table 2. We observe that our BGDH

outperforms all the other methods. Specifically, compared to the best baseline in Table 2, we conclude that when labeled data are insufficient, BGDH is able to leverage unlabeled data to deliver a good result.

4.3 Parameter Selection

In BGDH, there is a hyper-parameter λ which controls the tradeoff between supervised loss and unsupervised loss. Figure 2 displays the impacts of λ on the performance of BGDH with the experiment settings being the same as those in Table 3. As can be seen, there is a wide range of λ that BGDH performs well. Thus, to a large extent, BGDH is insensitive to λ and the parameter selection is not a crucial problem in our algorithm. Additionally, by comparing the MAP of λ = 0 and λ = 1, we verify the importance of graph embedding.

5 Conclusion

In this paper, we propose a novel semi-supervised hashing method, named Deep Hashing with a Bipartite Graph (BGDH). To the best of our knowledge, BGDH is the first method that performs graph embedding, feature learning, and hash code learning simultaneously. BGDH constructs a bipartite graph to discover the underlying structure of data, and is much more efficient than methods based on neighborhood graph. Experimental results demonstrate that BGDH outperforms state-of-the-art methods in image retrieval.

Acknowledgements

This work was partially supported by the NSFC (61603177, 61472182), JiangsuSF (BK20160658), and the Collaborative Innovation Center of Novel Software Technology and Industrialization of Nanjing University.