Graph Convolutional Network Hashing for Cross-Modal Retrieval

1 Introduction

With the development of social network and the Internet, visual data (e.g., photos and videos) have experienced an explosive growth, thus introducing renew enthusiasm in nearest neighbor search field. Cross-modal retrieval is one of the most popular approaches, which aims to search semantically similar data points in one modality (e.g., image) by using a query from another modality (e.g., text). Besides, hashing method has received wide attention because of its low storage requirements and fast query speed, which maps high dimensional multi-modal data points into common Hamming space, endowing similar cross-modal data points with similar hash codes. However, the modality gap caused by the heterogenous nature of data from different modalities still remains a challenge for accurate cross-modal hashing.

Many cross-modal hashing methods have been proposed [Bronstein et al., 2010; Ding et al., 2014; Shen et al., 2015; Deng et al., 2016], most of which adopt shallow structures and hand-crafted features. However, there is a main drawback indwelling in these methods, that the handcrafted feature extraction procedure is independent of hash code learning procedure, limiting the capacity of achieving accurate hash codes.

∗Contact Author

On the other hand, deep network-based methods [Yang et al., 2017; Deng et al., 2018; Yang et al., 2018; Li et al., 2018; Li et al., 2019] extract features with convolution neural networks and then learn hash code simultaneously in an endto-end training fashion, which generates more accurate hash codes. Unfortunately, most of these methods design different networks for image and text data, such as two-stream network utilized in Deep Cross-Modal Hashing [Jiang and Li, 2017], and directly employ similarity matrix as semantic constraints to generate hash codes. Such naive approaches can not fully exploit semantic correlations to guide the hash code learning procedure. Furthermore, semantic structural similarities between data points can be very helpful when generating semantic-preserving hash codes, which is often ignored. Therefore, how to incorporate semantic relevance and structural similarities between different data points into hash code learning procedure is of unprecedented importance.

Data points being independent of each other is a core assumption of existing machine learning algorithms. However, this assumption does not hold for graph data where each data point (node) is related to others (neighbors) via some complex link information, which can capture the interdependence among data points. The same intuition also exists in crossmodal retrieval, since every data pair in both modalities is linked with neighboring pairs, and employing such interdependence can be beneficial to accurate retrieval. Deep structure operates on graph-structured data, such as Graph Convolutional Networks (GCNs), has attracted increasing attention because of its fine capacity of exploiting relationships between nodes [Huang and Chen, 2017; Yang et al., 2019]. One of the first research on GCNs is presented in [Bruna et al., 2013], many variants and improvements have been proposed since then, showing promising results in applications such as node classification [Duvenaud et al., 2015; Kipf and Welling, 2016]. The basic idea of GCNs is updating one node's feature based on neighboring nodes' according to the adjacent matrix of this graph, therefore, GCN can pay attention to the semantic structure of data points via adjacency relationships, incorporating such networks in cross-modal hashing can be favorable for learning structural similarity-preserving hash codes and further boosting crossmodal retrieval performance.

In this paper, we propose a graph convolution network hashing (GCH) for cross-modal retrieval, which consists of three main components: a semantic encoder, two feature encoding networks and a graph convolution network (GCN) based fusion module. The proposed method utilizes GCN to produce an exhausted relation description between different data points, employs semantic encoder to guide the feature encoding process and preserves semantic together with structure similarities in feature learning at the same time, which is beneficial to generating more discriminative hash codes. The highlights of our work are as follows:

• We propose a novel graph convolution networks based cross-modal hashing method to alleviate the modality gap and improve cross-modal retrieval.
• To fully and effectively explore the semantic information, we train the semantic encoder to discover semantic relevance, which acts as 'teacher module' guiding feature encoding networks to learn discriminative and semantic-rich features. Then GCN is used to further enrich features with semantic structure, obtaining a beacon feature for further updating encoded features.
• Experiments on three benchmarks demonstrate that our proposed GCH notably outperforms the current state-ofthe-art cross-modal hashing methods, including both traditional and deep learning based methods.

2 RelatedWork

Cross-modal hashing methods can be categorized into two different settings: unsupervised and supervised approaches. As an unsupervised method, in Collective Matrix Factorization Hashing (CMFH) [Ding et al., 2014], unified hash codes for multiple modalities are generated using collective matrix factorization from different views.In contrast, CMSSH [Bronstein et al., 2010], which is a supervised approach, presents a cross-modal hashing by preserving intraclass similarity via eigen-decomposition and boosting.

Models based on deep networks [Cao et al., 2016; Li et al., 2018; Jiang and Li, 2017; Cao et al., 2018] are widely regarded and can better access to more discriminative features than those utilizing hand-crafted features, which leads to a boost in the performance of deep cross-modal retrieval. In recently proposed Cross-Modal HammingHashing (CMHH) [Cao et al., 2018], favorable hash codes are generated for accurate retrieval by jointly optimizing a novel exponential focal loss and an exponential quantization loss in a Bayesian learning framework. In addition, similar to our approach, Deep Cross-Modal Hashing (DCMH) [Jiang and Li, 2017] and Self-Supervised Adversarial Hashing (SSAH) [Li et al., 2018] both learn hash codes by preserving label similarity correlation, making full use of semantic information. These two methods achieve satisfying results, yet DCMH forces hash codes to keep semantic relevance for similar data points using similarity matrix in an obvious way, without paying too much attention to latent structure of cross-modal data. On the other hand, SSAH notices semantic structure lying beneath data points, but the algorithm is very time-consuming. Therefore, how to efficiently connect different modalities and explore modality consistency under the supervised information to produce favorable hash codes is the key to improve search accuracy for cross-modal hashing.

Different from existing deep network based cross-modal hashing methods, our work employs GCN to excavate data structural information and utilizes semantic encoder to extract semantic information from different modalities, which are transferred into encoded features, thus both semantic and structure similarities are well preserved, leading to optimal hash codes and better retrieval performance.

3 The Proposed GCHModel

In this work, we focus on retrieval between image and text modalities, which are two most commonly used modalities in daily life. Figure 1 shows the flowchart of the proposed GCH model. It consists of three main components: a semantic encoder, two feature encoding networks for both modalities, and a graph convolution network based fusion module, which will all be introduced concretely in the framework subsection.

3.1 ProblemFormulation

Given a cross-modal dataset O = {oi}ni=1 with n data points, oi = (xi, yi, li), where xi and yi are original image and text of the i-th data point, and li = [li1, . . . , lic] is the groundtruth label assigned to oi, where c is the class number. If oi belongs to the j-th class, lij = 1, otherwise lij = 0. Specifically, we utilize multi-label similarity matrix S to denote similarity of two data points m, n: if they belong to at least one same class, Smn = 1, otherwise Smn = 0. The goals of cross-modal hashing are to learn a unified K-bit hash code for both modalities: B ∈ {-1, 1}K , and to simultaneously preserve the original similarity between data pairs. Furthermore, to measure the similarity between two hash codes hi and hj, we can calculate their Hamming distance with their inner product 〈hi, hj〉. In order to obtain hash code for either modality, we can simply perform a non-linear transformation on the encoded feature, which can be depicted as:

where ∗ = {x, y, l}, h(·) denotes the non-linear transformation, and the obtained hash code is denoted as H∗ .

3.2 Framework

In order to discover abundant semantic information in labels and transfer such information to encoded features, inspired by the idea of 'Teacher-Student' strategy, we construct a novel semantic encoder as a teacher module to fully exploit the knowledge of semantic information lying in labels, and guide the feature encoding process with these knowledge. The encoder can be formulated as follows:

where θl is network parameter. Concretely, it is an end-to-end full-connected deep neural network. We hope the semantic encoder Gl can well preserve the similarities between semantic features and corresponding hash codes, to this end, the objective function of semantic encoder is formulated as follows:

where Γlij = 1 2 (Hl i )(H l j )⊤, α and β are hyper-parameters, ‖·‖F is the Frobenius norm. Hl∗i is the predicted hash code transformed from the feature gl and ˆLl is the predicted label, which can also be obtained from the feature. In Eq. (3), the first term is negative log-likelihood function, which is used to preserve similarities between features, and the second one is classification loss between the original label L and the predicted label ˆLl . The output of semantic encoder is very helpful in guiding feature encoding networks to learn a semanticrich feature, which favors the generation of hash codes for both modalities.

Furthermore, in order to build correlation between different modalities and further learn reliable hash codes, we construct two feature encoding networks to encode cross-modal data into common representation under the supervision of semantic encoder. For the i-th data point oi, we model the image feature encoding function Ex (x, θx ) with convolutional neural network to extract high-level image feature f x . Furthermore, we construct text feature encoding network Ey (y, θy ) with four fully-connected layers, where θx and θy are network parameters. The feature encoding networks can be written as:

In addition, we wish to preserve the knowledge distilled from labels, i.e., the semantic relevance, in encoding networks. Therefore, an end-to-end training procedure under the guidance of semantic encoder must be adopted for both encoding processes. In this way, knowledge, i.e., the semantic relevance, is transferred from 'Teacher' (semantic encoder) to 'Students' (feature encoding networks). In order to introduce the supervision of semantic encoder, similar to Eq. (3), the objective function of feature encoder takes following form:

Like those defined in Eq. (3), Γl∗ ij = 1 2 (Hl i )(H ∗ j )⊤, α, β and γ are hyper-parameters, ‖·‖F is the Frobenius norm. H∗ are predicted hash codes for both modalities and ˆL∗ are predicted labels. Specifically, Hb is the beacon hash code generated by GCN, which contributes to encoding more discriminative features and will be discussed in the later section. It is worth noting that in Eq. (3), we encode features for each modality under the guidance of semantic encoder, which takes form of Hl in Γl∗ ij . By doing so, semantic relevance obtained from semantic encoder is well preserved in encoded features for both modalities. Similarly to Eq. (3), here J3 is employed to keep categorical information by reducing the difference between ˆL and the original label L.

To further enhance encoded features, we first need to fuse encoded features without losing too much semantic relevance. Inspired by [Vaswani et al., 2017], self-attention mechanism is chosen for semantic-preserving fusing method in our work. Concretely, features from two modalities are reweighted using features from relative modality, which can be formulated as follows:

where ˜ W = norm(f x × f y⊤) serves as the normalized weight matrix, f x and f y are original features from respective modality, f x s-a and f y s-a are the processed features and fr is the fused feature. As for operative symbols, × denotes matrix inner product, and norm is matrix normalization.

Based in this fusion module, we can formulate out graph convolution network as follow: given Nb pairs of training Algorithm 1 Semantic encoder guided learning for graph convolutional network hashing (GCH).

• 1: Input: Image set X; text set Y ; label set L;
• 2: Output: Learned network parameters θx,y,l,G;
• 3: Initialization: network parameters θx,y,l,G; hyperparameters: α, β, γ; learning rate: µ; mini-batch size: N x,y,l b = 128; maximum iteration number: Tmax, iter=0;
• 4: while iter < Tmax do
• 5: Update θl by BP algorithm.
• 6: Update θx,y under guidance of semantic encoder.
• 7: Update θG under guidance of semantic encoder, calculate beacon feature.
• 8: Re-update θx,y using beacon feature.
• 9: end while

data points {xi, yi, li}Nb i=i , after feeding corresponding data points to each feature encoding networks, we will have two feature matrices fx ∈ RNb×d and fy ∈ RNb×d , which will be fused using afore mentioned self-attention fusing mechanism. After obtaining the fuse semantic-rich feature fr, it needs to be further enhanced with structural similarities to make up for the deficiency of the modality gap. To this end, we employ a multi-layer GCN, in which way in-batch features with strong latent structural relations will interact during parameter updating, leading to optimal hash codes to unify both modalities and to improve retrieval accuracy eventually.

The fused feature is fed into multi-layer GCN along with the adjacency matrix A ∈ RNb×Nb concerning the adjacent relationships of Nb in-batch data pairs. Suggested by [Kipf and Welling, 2016], the layer-wise propagation rule of multilayer GCN can take the following form:

Here, ˜ A = A + IN is the normalized adjacency matrix of the undirected graph G. Entries of A can be computed as A(i, j) = li × lj, here li is the ground truth label of data point i. IN is the identity matrix, indicating every node is connected to itself, ˜Dii = ∑j ˜ Aij is the degree matrix of ˜ A and σ(·) denotes an activation function, such as ReLU. H(l) and H(l+1) are the input and output feature matrices of the lth layer, representing features learned by the preceding layer and the present layer. W (l) acts like convolutional filter in conventional CNNs in l-th layer, whose parameters will be updated during training.

Updating parameters in GCN during training is beneficial to dynamically updating nodes' features. It can be learned from Eq. (7) that, for a node Vi, graph convolution concatenates the features of Vi's neighboring nodes by a weighted summation and simultaneously assigns new features to Vi based on ˜ A, indicating that features of neighboring nodes are encouraged to be closer. In this way, the fused feature of two modalities are tightened by structural similarities. Accordingly, the overall objective is defined as:

where ΓGij = 1 2 (Hb i )(H b j )⊤. The output of GCN is denoted as beacon feature, which denotes as Hb in Eq. (8) and Eq. (5), serves as a 'beacon' in the common feature space for encoded features to approach. In this way, the structural similarities are well preserved in encoded features. The remaining parameters in Eq. (8) are as same as those in Eq. (3).

3.3 Training Strategy

Combining the four aforementioned objective functions, the overall objective function of GCH can be formulated as:

In particular, we regard them of equal importance as discussed earlier in the paper. The objective Eq. (9) is learned via iterative optimization. Concretely, the optimization order is Ll ⇒ L∗ ⇒ LG ⇒ L∗ , where ∗ = {x, y}. It is noted that network parameters are fixed when training other parts of the network and are learned by utilizing stochastic gradient descent (SGD) with a back-propagation (BP) algorithm, which are widely used in existing deep methods. Algorithm 1 outlines the whole learning algorithm in detail.

After the whole network is well-trained in the end-to-end fashion, hash codes for the unseen data points can be obtained directly by feeding the original feature into feature encoding networks:

4 Experiments and Discussions

Three popular benchmark datasets in cross-modal retrieval: MIRFLICKR-25K [Huiskes and Lew, 2008], NUSWIDE [Chua et al., 2009], and Microsoft COCO [Lin et al., 2014] are adopted to validate our proposed method. Our GCH is implemented with TensorFlow [Abadi et al., 2016] and executed on a server with one NVIDIA TITAN Xp GPU.

4.1 Datasets

MIRFLICKR-25K contains 25,000 data points collected from Flickr. In total, 20,015 data points are selected in our experiment, using 10,000 data points for training and 2,000 for query. The remaining part is used for retrieval. The text for each point is represented as a 1,386-dimensional bag-ofwords vector, and each point is annotated with at least one of the 24 unique labels.

NUS-WIDE contains about 269,648 web images with 81 ground truth concepts. After pruning the data without any label or tag information, a subset of 188,321 data points that belong to the 21 most-frequent concepts are selected, including 10,500 data points for training and 2,100 data points for query. The rest serves as retrieval set.

MS-COCO contains about 80,000 training images and 40,000 validation images. 117,218 data points are used in our experiment, 10,000 data points for training and 5,000 for query. The rest of data points serve as retrieval set. Each text is represented as a 2,000-dimension bag-of-words vector.

4.2 Implementation Details

We adopt the first seven layers of CNNF [Chatfield et al., 2014] neural network as image feature encoder, which is one variation of AlexNet [Krizhevsky et al., 2012] pretrained on Imagenet dataset [Deng et al., 2009]. For texts, a neural network with four fully-connected layers is constructed to extract high-level features, (i.e., T → 512 → 512 → N). N is number of nodes in output layer, which equals to the length of hash code K or total class label c for different datasets, depending on different types of the output. For the inputs of these networks, raw images are resized into 224 × 224 × 3 and texts are represented with bag-of-words vectors.

Semantic encoder is built with a three-layer feed-forward network to project label to binary codes, (i.e., L → 512 → 512 → N), N equals to the length of hash code K or total class label c for different datasets, depending on different types of the output.

A two-layer GCN with each layer's output feature dimensions being Nb × 1024 and Nb × K is employed, where Nb is batch size. Activations for these two layers are ReLU and sigmoid respectively.

Regarding the activate function used in GCH: Sigmoid activation is used to output predicted labels; tanh activation is used to output hash codes; and the rest of the layers are all uniformly activated by the LReLU function.

4.3 Metrics and Baselines

We adopt two common used protocols in cross-modal retrieval: Hamming ranking and hash lookup, where three evaluation criteria: Mean Average Precision (MAP) with MAP@R=500, precision-recall curve (PR curve) and Precision@N curve with N=1000, are utilized.

As for baselines, five cross-modal hashing state-of-theart methods are compared, including STMH [Wang et al.,

2015], CMSSH [Bronstein et al., 2010], SCM [Zhang and Li, 2014] and SePH [Lin et al., 2015], which are all shallow structure based cross-modal retrieval hashing methods, and DCMH [Jiang and Li, 2017], which is a deep network based approach. We additionally compare GCH with the recently proposed CMHH [Cao et al., 2018], which is also a deep network based cross-modal retrieval method.

4.4 Performance Evaluation

Table 1 reports the MAP for our GCH and peer methods on three popular datasets in cross-modal retrieval. During image data processing, deep CNNF features are extracted for all shallow structure-based methods to facilitate fair competition. Our GCH takes the raw images as input. From Table 1, we can see that: 1) Compared with the shallow baselines STMH, CMSSH, SCM and SePH, our GCH achieves an average of 38%/43%, 52%/52%, 53%/62%, 11%/29% increase in MAP evaluated on MIRFLICKR-25K dataset; 2) While compared with DCMH, it can be seen that GCH can also achieve average improvement by 17%/18%. Evaluation on NUS-WIDE and MS-COCO datasets with more complex test scenarios and vast amounts of data, which are more challenging, GCH always outperforms peer methods. The main reason is that the proposed semantic encoder can well acquire the semantic information and use it to guide the encoding process for features. In addition, GCN enhances features with semantic relevance and data structure, thus more reliable hash codes can be produced and retrieval performance is improved.

We plot the PR curve for the returned points given Hamming radius varying from 0 to 1, 000 with a stepsize of 1. Left two columns in Figure 2 illustrate PR curves of all state-of-the-art methods with 64-bit hash code on three benchmark datasets, and the right two columns demonstrate Precision@1000 curves, which all show that our GCH notably outperforms all competitors.

The ablation study of GCH is quite straightforward, by simply replacing GCN with fully-connected layers, we use Table 2 to show the comparison MAP with code length 16 on three datasets. The variant of GCN is denoted as GCH-A. For simplicity, we use abbreviation for each dataset name. From the results, we can see that our method can achieve a higher performance when using the designed modules, meaning that GCN has significantly improved the overall performance.

Specially, we compare our method with Cross-Modal Hamming Hashing. CMHH is one recently proposed method on cross-modal hashing, whose source codes are not publicly available. For fair comparison, we follow the settings used in CMHH on MIRFLICKR25K dataset. Table 3 shows the experiment results, the underlined results are reported in CMHH. It can be seen that our method outperforms CMHH significantly, demonstrating the effectiveness of the proposed method.

5 Conclusion

We have presented a novel graph convolutional networks based cross-modal hashing, for large-scale cross-modal retrieval. The main contribution of our method is that we propose a GCN based hashing network for cross-modal retrieval. In addition, we utilize a novel semantic encoder to preserve rich semantic in feature encoding process. Extensive experiments on popular datasets show that our model achieves stateof-the-art performance in cross-modal retrieval task.

Acknowledgments

This work is supported in part by the National Natural Science Foundation of China under Grant 61572388 and 61703327, in part by the Key R&D Program-The Key Industry Innovation Chain of Shaanxi under Grant 2018ZDXMGY-176, and in part by the National Key R&D Program of China under Grant 2017YFE0104100.