Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17) Semi-Supervised Deep Hashing with a Bipartite Graph Xinyu Yan,Lijun Zhang,Wu-Jun Li National Key Laboratory for Novel Software Technology,Nanjing University,Nanjing 210023,China yanxy,zhanglj@lamda.nju.edu.cn,liwujun @nju.edu.cn Abstract (LSH)[Gionis et al.,1999]and data-dependent ones like Iter- ative Quantization (ITQ)Gong et al.,2013].Spectral Hash- Recently,deep learning has been successfully ap- plied to the problem of hashing,yielding remark- ing(SH)[Weiss et al,2009],Anchor Graph Hashing (AGH) able performance compared to traditional method- [Liu et al.,2011].On the other hand,to deal with more com- plicated semantic similarity,supervised hashing methods are s with hand-crafted features.However,most of proposed to exploit label information to improve the hash- existing deep hashing methods are designed for ing quality.Representative supervised methods include La- the supervised scenario and require a large num- tent Factor Hashing (LFH)[Zhang et al.,2014],Fast Super- ber of labeled data.In this paper,we propose vised Hashing (FastH)[Lin et al.,2014],Supervised Discrete a novel semi-supervised hashing method for im- age retrieval,named Deep Hashing with a Bipar- Hashing(SDH)[Shen et al.,2015].However,labeling large- scale image dataset is inefficient and time-consuming.As a tite Graph(BGDH),to simultaneously learn em- result,Semi-Supervised Hashing (SSH)[Wang et al.,2012] beddings,features and hash codes.More specifi- has been developed to make use of labeled data as well as the cally,we construct a bipartite graph to discover the abundant unlabeled data. underlying structure of data,based on which an em- bedding is generated for each instance.Then,we In traditional hashing methods,images are represented feed raw pixels as well as embeddings to a deep by hand-crafted features such as GIST [Oliva and Torralba. neural network,and concatenate the resulting fea- 2001],and the choice of features requires heavy manual in- tures to determine the hash code.Compared to ex- terventions.Motivated from the great success of deep neu- isting methods,BGDH is a universal framework ral networks in image analysis [Krizhevsky et al.,2012],re- that is able to utilize various types of graphs and cently some deep hashing methods have been proposed to losses.Furthermore,we propose an inductive vari- learn features and hash codes simultaneously [Li et al..2016: ant of BGDH to support out-of-sample extensions Zhu et al..2016:Liu et al..2016.Although those deep hash- Experimental results on real datasets show that our ing methods yield better performance compared with the tra- BGDH outperforms state-of-the-art hashing meth- ditional methods,they usually need a large number of labeled ods instances as training data.To address this limitation,a semi- supervised deep hashing,named SSDH,have been develope- d [Zhang et al.,2016].SSDH is fundamentally built upon 1 Introduction graph-based semi-supervised learning [Zhou et al.,2004]and With the explosion in the volume of image data,it has been the loss function contains a graph regularization term which raised as a big challenge about how to index and organize involves both the labeled and unlabeled data.In theory,SS- these data efficiently and accurately.Approximate Nearest DH needs to construct a nearest neighbor graph of all the da- Neighbor (ANN)search [Indyk and Motwani.1998]has be- ta.Unfortunately,this step takes O(n2)time,where n is the come a popular way to retrieve content from images with both number of instances,and thus intractable for large scale data. computational efficiency and search quality.Among existing In this paper,we propose a novel semi-supervised hash- ANN search methods.hashing is advantageous due to its fast ing method,named Deep Hashing with a Bipartite Graph query speed and low memory complexity [Gionis et al.,1999; (BGDH),which performs graph embedding,feature learning Gong et al.,2013].It aims to transform high-dimensional im- and hash code learning in a unified framework.First,we con- ages into a set of short binary codes while maintaining simi- struct a bipartite graph to capture the information hidden in larity of the original data. the labeled and unlabeled data.The bipartite graph could be Generally speaking,hashing methods can be divided into a semantic graph that describes relationships between images two categories:unsupervised and supervised.Unsupervised and concepts,an anchor graph that describes similarities be- methods utilize some kinds of distance metrics to learn a hash tween images and landmarks [Liu et al.,2010],or a tradition- function from unlabeled data.Methods in this category in- al nearest neighbor graph.Then,inspired by the recent work clude data-independent ones like Locally Sensitive Hashing on graph embedding [Yang et al.,20161,we learn an embed- 3238Semi-Supervised Deep Hashing with a Bipartite Graph Xinyu Yan, Lijun Zhang, Wu-Jun Li National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China {yanxy, zhanglj}@lamda.nju.edu.cn, liwujun@nju.edu.cn Abstract Recently, deep learning has been successfully ap￾plied to the problem of hashing, yielding remark￾able performance compared to traditional method￾s with hand-crafted features. However, most of existing deep hashing methods are designed for the supervised scenario and require a large num￾ber of labeled data. In this paper, we propose a novel semi-supervised hashing method for im￾age retrieval, named Deep Hashing with a Bipar￾tite Graph (BGDH), to simultaneously learn em￾beddings, features and hash codes. More specifi- cally, we construct a bipartite graph to discover the underlying structure of data, based on which an em￾bedding is generated for each instance. Then, we feed raw pixels as well as embeddings to a deep neural network, and concatenate the resulting fea￾tures to determine the hash code. Compared to ex￾isting methods, BGDH is a universal framework that is able to utilize various types of graphs and losses. Furthermore, we propose an inductive vari￾ant of BGDH to support out-of-sample extensions. Experimental results on real datasets show that our BGDH outperforms state-of-the-art hashing meth￾ods. 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 be￾come 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 im￾ages into a set of short binary codes while maintaining simi￾larity 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 in￾clude data-independent ones like Locally Sensitive Hashing (LSH) [Gionis et al., 1999] and data-dependent ones like Iter￾ative Quantization (ITQ) [Gong et al., 2013], Spectral Hash￾ing (SH) [Weiss et al., 2009], Anchor Graph Hashing (AGH) [Liu et al., 2011]. On the other hand, to deal with more com￾plicated semantic similarity, supervised hashing methods are proposed to exploit label information to improve the hash￾ing quality. Representative supervised methods include La￾tent Factor Hashing (LFH) [Zhang et al., 2014], Fast Super￾vised Hashing (FastH) [Lin et al., 2014], Supervised Discrete Hashing (SDH) [Shen et al., 2015]. However, labeling large￾scale 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 in￾terventions. Motivated from the great success of deep neu￾ral networks in image analysis [Krizhevsky et al., 2012], re￾cently 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 hash￾ing methods yield better performance compared with the tra￾ditional methods, they usually need a large number of labeled instances as training data. To address this limitation, a semi￾supervised deep hashing, named SSDH, have been develope￾d [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, SS￾DH needs to construct a nearest neighbor graph of all the da￾ta. Unfortunately, this step takes O(n 2 ) time, where n is the number of instances, and thus intractable for large scale data. In this paper, we propose a novel semi-supervised hash￾ing 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 con￾struct 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 be￾tween images and landmarks [Liu et al., 2010], or a tradition￾al nearest neighbor graph. Then, inspired by the recent work on graph embedding [Yang et al., 2016], we learn an embed￾Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17) 3238