Set and Rebase: Determining the Semantic Graph Connectivity for Unsupervised Cross-Modal Hashing

1 Introduction

The era of big data has witnessed continuous research attention in cross-modal hashing because of its low computational complexity and storage requirement for large-scale multimedia retrieval [Zhang et al., 2018a]. The key challenges of this realm are preserving as much similarity information as possible and simultaneously mitigating the modality heterogeneity.

Among the existing methods, supervised cross-modal hashing [Jiang and Li, 2017; Shen et al., 2017; Erin Liong et al., 2017; Tang et al., 2016; Bronstein et al., 2010; Zhang and Li, 2014] obtains better retrieval performance. These techniques utilize label information which can be shared by both image and text data to exploit similarity between samples of different modalities. However, labeled dataset is limited and it may cause huge cost to label large scale multi-modal datasets by hand, which constraints the practicality of supervised algorithms despite their outstanding performance.

∗Equal contribution.

†Contact Author.

Exempted from manual data labeling, unsupervised crossmodal hashing is regarded as a more practical alternative compared with its supervised counterpart. There are two main kinds of unsupervised cross-modal retrieval algorithms nowadays, whose main focus lie on quantization and similaritysearch respectively. Cross-modal quantization minimizes the gap between binary codes and low dimension projection of origin data [Zhang and Wang, 2016; Irie et al., 2015; Long et al., 2016]. The second kind cross-modal similaritysearch methods includes Cross View Hashing (CVH) [Kumar and Udupa, 2011], Collective Matrix Factorization Hashing (CMFH) [Ding et al., 2014], Predictable Dual-view Hashing (PDH) [Rastegari et al., 2013] and Inter-Media Hashing (IMH) [Song et al., 2013]. Though impressive progress have these models made, there still exist several challenges in this field. Hence, we motivate our work according to the following three issues.

First, the hardness in determining data semantic relations without label. Unsupervised hashing techniques basically have no access to the actual data semantics. To obtain reasonable retrieval results, several existing single-modal [Liu et al., 2011; 2014; Su et al., 2018; Zhang et al., 2018b;

Liu et al., 2017] and cross-modal approaches [Jian et al., 2018] resort to the heuristic geometric prior, i.e., determining the degree of data relevance according to the original feature distances and leaving it fixed during training. This solution is obviously sub-optimal as the original features are usually not designed for nearest-neighbor search and the distances between them can be heavily biased. One solution is to gradually update these semantic relations during training, which has been proven to be effective in [Shen et al., 2018]. However, [Shen et al., 2018] is designed for single-modal hashing only, fail to handle multi-modal data.

Second, the cross-modal consistency of empirical similarity. With the heuristic semantic simulation discussed above, each modality would have its own similarity connections according to its geometric prior. It is possible that two samples undergo similarity disagreement under different modalities/views, which confuses the training process. This problem also necessities similarity updating together with optimization to come up with a modal-unified graph.

Third, the sparsity of data semantic connection during training. A sparse similarity graph saves the time of training, while a densely-connected one may introduce undesired noise. In this sense, one needs to simplify the similarity graph during training, only keeping the manifest connections.

In this paper, to tackle the aforementioned issues, we propose a novel unsupervised method called Semantic-Rebased Cross-modal Hashing (SRCH). We define a special 'Set-andRebase' routine to learn semantic-aware graphs for better encoding performance. The 'set' operation constructs a geometric sparse graph which contains unimodal neighborhood relationship in each modal, and then the 'rebase' operation is alternately coupled with binary code learning to tune and fit the geometric graph structures according to the code learning results. Our method uses sparse graph structure inspired by RCC [Shah and Koltun, 2017] and COMIC [Peng et al., 2019] to preserve similarity information hidden in original data from different modals. To map data from different modalities into one common space, we suppose generated binary codes of the same sample from different modals are the same on training set for simplicity. This is reasonable because different modal data of a sample describes the same object and can use only one code to represent it. As a powerful unsupervised convention, the auto-encoding fashion is employed to improve the robustness of our model. The overview structure of our method can be found in Fig. 2. The main contributions of this method are summarized as below.

1. We propose a 'Set-and-Rebase' mechanism to learn a sparse graph structure over the training set including geometric and semantic graphs to preserve similarity information for binary code learning.
2. Different from those existing unsupervised cross-modal hashing methods, our method focus on both similarity preserving and quantization to gain satisfied retrieval performance. Besides, the auto-encoding structure is included to improve our model, which is seldom used in cross-modal hashing.
3. Comprehensive experimental evaluations are conducted on four popular datasets, including Wiki [Rasiwasia et

al., 2010], MIRFlickr-25K [Huiskes and Lew, 2008], MSCOCO [Lin et al., 2014] and NUS-WIDE [Chua et al., 2009], showing the proposed model significantly outperforms the state-of-the-art unsupervised methods.

2 Methodology

Although our method can be used in multi-modal datasets, we conduct our experiment on two modal datasets for simplicity. Let XV ∈ RdV ×n and XT ∈ RdT×n represents normalized image features and text vectors respectively of n training samples, where dV and dT are the dimensions of image feature and text vector respectively. Our task is to map these image features and text vectors into l bit binary hashing codes BV or BT where Bg ∈ {+1, -1}l×n , g ∈ {V, T}. Because we want to map image features and corresponding text vectors into the same Hamming space in training process, we set BV =BT =B on training set for simplicity.

2.1 Model Overview

The overall pipeline of SRCH is shown in Fig. 2. Our model follows an auto-encoding schema where image and text samples feed their own projectors. The latent codes on the bottleneck are therefore quantized as the final hash codes. We set, i.e., initialize, the cross-modal semantic graph according to the geometric prior of the original feature space and rebase the graph together with other model parameters in an alternating manner.

2.2 Sparse Graph Setting and Rebasing

Set the Semantic Geometric Prior

In our setting stage, geometric sparse graph structures in different modalities are built, and these geometric graphs are fixed during training. The ways to construct sparse graph structure are various due to different algorithms. One typical method is to search the nearest several nodes for any node, which can avoid isolated points and is more flexible. We use this strategy to construct our sparse graph which can be formulated like Eq. (1). e(i,j) in equation represents undirected edge connecting sample xi and xj , and NN(xj , k) means the set of k nearest neighbors of sample xj. The threshold of the neighbor number k decides the amount of containing similarity information,

The left half of Fig. 1 is a schematic diagram of our geometric sparse graph constructed on both image (up) and text (down) domain. The circles with the same color are samples from the same class and there are some wrong connections with red color in this figure due to the lack of label information as these sample pairs are close to each other in specific domain, like a cat and a dog. Those close samples are connected together through their similarity information, constituting several clusters whose number depends on the threshold.

Rebase the Graph by Code Similarity

In rebasing stage, we use continuous real values ranging from 0 to 1 to represent the probability of semantic connection between samples pairs instead of binary values to perform graph fusion. These probability values are learned according to the similarity of two samples in various modalities written as Eq. (2), where the detailed representation of Φ(xi, xj) will be given in following part. In general, the probability of those connections which exist in both graphs are larger than those only exist in one graph. For those connections which neither exist in image domain nor in text domain, the probability values are set to zero. The iterative learning process is illustrated as the right half of Fig. 1.

2.3 Objective Function

Auto-Encoding Objective

In order to generate efficient binary codes which contain sufficient similarity information in both image domain and text domain, the structure of auto-encoder is utilized with its loss function as formulated below.

where g ∈ {V, T} and the second constraint BBT = nI is aimed to generate mutually independent binary codes.

In Eq. (3), the first item aims to reduce the gap between mapped low dimension feature and discrete binary codes. For simplicity, the transpose matrix of W is used to replace the inverse mapping matrix and thus a constraint W T g Wg = I is added on the projection matrix. In this case the regularization term ‖Wg‖2F is unnecessary due to the fact that ‖Wg‖2F = tr(W T g Wg) = tr(I) = const.

Semantic Loss

Aiming to allow generated binary codes to retrieve crossmodal samples, a sparse semantic graph S is learned from both image and text set and is used to improve the quality of hashing codes B and S(i,j) represents the probability of connection between sample i and j. The updating process of S will be presented detailedly in the next part.

Here Z is continuous low-dimensional embedding of input features which is shared by both modalities similar to binary codes of training set B. For simplicity, we suppose the dimension of Z is equal to B. In this equation, binary codes B is replaced by Z due to that the distance of continuous Euclidean space contain more information than that of discrete Hamming space. Besides, we hope they are close to each other, as formulated below.

Besides, the symbol εg in Eq. (4) is our constructed sparse graph in image domain (g = V ) or text domain (g = T), and Cg(g ∈ {V, T}) are the weights of edges in this sparse graph to balance the contribution of each data point in objective function. And the computation of Cg(i,j) is presented in Eq. (6).

The variable ag(m) in Eq. (6) is the degree of m-th data point in the graph and the numerator is the average degree of data points.

Toward Semantic Graph Sparsity

To strengthen the semantic connection for edges which exist in εg, Least Square Error constraint is added on semantic graph S with all ones matrix. And the objective function in each domain g ∈ {V, T} is presented below.

where g ∈ {V, T}.

Our final loss of each modality is presented as following.

And our whole loss can be written as:

2.4 Optimization

In this part, we try to solve the optimal value of B and Wg from Eq. (9). As there are four variables in total and they are coupled with each other, the problem is split into four steps as stated below.

W-step. In this stage, B is fixed. Considering the constraint W T g Wg = I, the whole loss function related to Wg can be simplified as following expression,

where the condition BBT = nI is also used during simplifying process. The optimal solution of Wg can be written in closed-form as Eq. (11) with SVD algorithm, which is proved in [Hu et al., 2018],

where U and Q are the left and right singular vectors of the compact Singular Value Decomposition (SVD) of XgBT .

Z-step. Fix all the other variables except Z, and then take the derivative of (9) with regard to Z, we can get

and H = HI +HT . From Eq. (12), we can directly get the optimal solution of Z∗ , presented as below,

S-step (graph rebase). Due to the complexity of optimizing whole semantic graph S, we update the graph values by element for simplicity and thus the sub-problem turns into a quadratic optimization of scalars. And we can get the solution of S∗ (i,j) directly through its gradient,

from which we can find that S(i,j) = 1 only when zi = zj . And in other cases, S(i,j) is ranging from 0 to 1.

B-step. Due to the discreteness of hash codes B, the gradient method is not suitable for solving it from such a loss function. We rewrite Eq. (9) related to B as following expression,

Algorithm 1 The detailed process of SRCH

Input:

Normalized image Features XV and text Vectors XT ;

Parameters k, α, β, and λ;

Output:

Projection matrices in image domain WV and text domain WT ; Hash codes B;

• 1: Construct a sparse graph εg of Xg using m-kNN algorithm on image (g = V ) and text (g = T) domain respectively;
• 2: Pre-compute weights of εg using Eq. (6);
• 3: Initialize hash codes of training set B and sparse semantic graph S (Graph Set);
• 4: while stopping criterion not satisfied do
• 5: Fix B, optimizeWg, g ∈ {V, T} using Eq. (11);
• 6: Fix Wg(g ∈ {V, T}), B and S, update Z with Eq. (14);
• 7: Fix Z, update S using Eq. (15) (Graph Rebase);
• 8: FixWg(g ∈ {V, T}) and Z, update B using Eq. (17).
• 9: end while

where the condition BBT = nI is used in (16). In fact, here B can also be solved by SVD like Wg, just dividing B by √n, and then binarize intermediate solution. However, twostep optimization can also increase potential quantization loss and we omit the constraint when solving B like ITQ [Gong et al., 2013]. Thus, the optimal binary code B∗ can be obtained as follows,

Since the iterative processes of Wg, Z, S and B are dependent on each other, at the beginning of iteration, initializing the value of B and S is required. For simplicity, we set the initial value of B as uniformly distributed random integer from the set of {+1,-1}. As for S, we set S(i,j) with 1 if the edge (i, j) exists in at least one geometric sparse graph and 0 in other cases. When the optimization begins, the objective function Eq. (9) is computed in iterative manner. The stopping criterion works when the difference of the objective function value between two nearest iterations is less than a preset threshold, and the latest value of Wg, Z, S and B is our optimal result when the stopping condition is met. It should be noted that the objective function value is set to infinity at the beginning of the iteration. The whole iterative optimization process is summarized in Alg. 1.

2.5 Out-of-Sample Code Computation

For those samples which are outside the training set, their binary codes in image domain (BI) or text domain (BT ) can be computed using following formulation.

where g ∈ {V, T}. Therefore, hashing codes of those data from test set or the whole retrieval set can be calculated with optimal projection matrix W ∗ g .

3 Experiments

3.1 Experimental Settings

Datasets. We conduct our experiments on four typical datasets, including Wiki [Rasiwasia et al., 2010], MIRFlickr25K [Huiskes and Lew, 2008], MSCOCO [Lin et al., 2014] and NUS-WIDE [Chua et al., 2009]. Detailed experimental settings are listed as Tab. 2.

Implementation details. For all of our experiments, we follow the recent convention to use the VGG-16 fc7 features as the image-side input with the dimension of 4096 and the universal sentence encoder feature [Cer et al., 2018] for text representation whose dimension is 512. α, β, and λ are all hyper parameters of our experiment, and their values are set to 0.0001, 0.001 and 10 respectively in our model. And parameter k in the m-kNN algorithm is set to 10.

3.2 Comparison with ExistingMethods

Baselines. As unsupervised cross-modal hashing algorithms are limited till now, especially in recent years, we compare our SRCH with six non-deep methods in this paper, including CVH [Kumar and Udupa, 2011], CMFH [Ding et al., 2014], PDH [Rastegari et al., 2013], ACQ [Irie et al.,

2015], IMH [Song et al., 2013] and QCH [Wu et al., 2015]. Besides, we also make comparisons with one supervised nondeep model SCM [Zhang and Li, 2014] and two deep unsupervised models UGACH [Jian et al., 2018] and UCH [Chao et al., 2019] to prove our improvement. It is noticeable that these methods except SCM are all unsupervised cross-modal hashing techniques. All of these methods use identical features to ours as inputs and we reproduce all results using the codes provided by the original authors.

Quantitative results. Results of Mean Average Precision (MAP) on text retrieval by image query (I2T) and image retrieval by text query (T2I) are listed in Tab. 1. It can be observed that our method outperforms other methods on all four datasets regardless of the cross-modal retrieval tasks and code lengths, which demonstrates the effectiveness of this method. Concretely, our text retrieval performance by image query on Wiki dataset obtains at least 17% improvement on 16 bits, 32 bits and 64 bits compared with the other non-deep algorithms while our image retrieval performance by text query surpasses those compared methods more than 3.18%, 3.33% and 2.55% for different lengths of binary codes. On the other three datasets, the improvements of our method are also obvious, especially compared with those unsupervised non-deep cross-modal hashing techniques. The corresponding Precision-Recall (P-R) curves of all unsupervised nondeep cross-modal hashing techniques are also reported in Fig. 3.

Qualitative results. Some retrieval results are selectively reported to illustrate the empirical performance of our model. Fig. 4 shows a randomly picked T2I query and the corresponding retrieval results. Our method manages to retrieve correct images while other methods have some failures according to label matching results. Concretely, our top 10 retrieval images contain the majority of text information while others' correct results only match one keyword with query sentence.

3.3 Ablation Study

Component analysis. In this section, the structure of our model is modified to see the significance of each component. For simplicity, the first item of Eq. (3) is abbreviated as QL (Quantization Loss) while the second term is called as RL (Reconstruction Loss), and the last three terms of Eq. (8) are simplified as SL (Similarity-preserving Loss). The results of our ablation study are listed in Tab. 3 and the symbol 'w/o' in table means 'without'. Tab. 3 suggests that removing any component of our learning objective leads to retrieval performance degradation. Among these three loss structures, the effect of similarity preserving loss is larger than the other two parts of losses. Specifically, this part of loss can improve at least 8.7% on MSCOCO. The quantization loss and reconstruction loss have similar effects on cross-modal results while the later one appears to be more important. From the table, we can find that all these components are significant in our method, and this experiment reflects our advantage compared with other unsupervised methods.

Hyper-parameters. The hyper-parameters are also analyzed. We illustrate the influence of different loss penalties of α, β and λ in Fig. 5 (a), (b) and (c) respectively on the Wiki dataset [Rasiwasia et al., 2010]. It can be clearly seen that our model is not extremely sensitive to these penalty weights, suggesting that it can be conveniently trained and extended on other datasets and the results are highly reproducible with minimal training tricks. We also evaluate different values of k for the Set operation of our training graph. Again, the model accepts different values of k as our Rebase step can always find the optimal graph connectivity for hashing during training. The idea of involving graph update in training is therefore endorsed as the graph initialization is no longer dominating the final retrieval performance.

4 Conclusion

This paper proposed a new kind of unsupervised crossmodal hashing method which utilized sparse graph structures to exploit similarity information to address the degradation problem in unsupervised algorithms. We made full use of similarity-preserving and quantization strategies along with reconstruction, and therefore this method can obtain more satisfied performance than other unsupervised hashing algorithms. This advantage can be found in terms of MAP values, P-R curves and qualitative retrieving results on four popular cross-modal retrieval datasets above. Furthermore, our ablation study and hyper-parameter analysis demonstrated the effectiveness of this model in many aspects.

Acknowledgements

This work was supported in part by National Natural Science Foundation of China (No.61872187) and in part by the "111" Program (No.B13022).