InvGC: Robust Cross-Modal Retrieval by Inverse Graph Convolution

In this paper, we focus on the representation degeneration problem in cross-modal retrieval Wang et al. (2020b). Two modalities are denoted as $\mathcal{X}$ and $\mathcal{Y}$. $\mathcal{X}$ is the query modality, while $\mathcal{Y}$ is the gallery modality. The (test) gallery, denoted $G=\{\mathbf{g}_{1},\ldots,\mathbf{g}_{N_{g}}\}$, contains all the representations of the (test) gallery data, where $N_{g}$ is the size. The query set is $Q=\{\mathbf{q}_{1},\ldots,\mathbf{q}_{N_{q}}\}$, where $N_{q}$ is the number of queries. Usually, in cross-modal retrieval, the gallery data does not overlap with the training data. Additionally, as InvGC requires training (or validation) data to address the representation degeneration problem, we define the set of representations of training (or validation) query and gallery data as $\hat{Q}=\{\hat{\mathbf{q}}_{1},\ldots,\hat{\mathbf{q}}_{N_{\hat{Q}}}\}$ and $\hat{G}=\{\hat{\mathbf{g}}_{1},\ldots,\hat{\mathbf{g}}_{N_{\hat{G}}}\}$, respectively, where $N_{\hat{Q}}$ and $N_{\hat{G}}$ are the size of the training (or validation) query and gallery set, respectively. The similarity between two embeddings $\mathbf{a}$ and $\mathbf{b}$ is defined as $s_{\mathbf{a},\mathbf{b}}=\operatorname{sim}(\mathbf{a},\mathbf{b})$, where $\operatorname{sim}(\cdot,\cdot)$ could be some measure of distance.

Taking inspiration from Liang et al. (2022), we define the representation degeneration problem as the average similarity of pairs that are closest to each other,

where $\mathbf{y}$ is the closest data point to $\mathbf{x}$ while $m$ is the number of data points. A higher score, as shown in Section C.3, indicates a more severe representation degeneration issue, with each data point being closer to its nearest neighbors in the set.

To understand the relationship between the degeneration score (Equation 2) and the retrieval performance, we present the following theorems.

Due to space limitation, the proofs are deferred to Section D.1.

InvGC originates from graph convolution, which is widely employed in graph neural networks Kipf and Welling (2017); Gilmer et al. (2017); Velickovic et al. (2018).

Specifically, graph convolution will concentrate all the embeddings of similar nodes which might lead to the concentration of similarity de la Pena and Montgomery-Smith (1995) and the data degeneration problem  Baranwal et al. (2023). On the other side, a similar operation, average pooling, has been employed in computer vision He et al. (2016); Wang and Shi (2023). Average pooling will aggregate the features that are location-based similar³³3The details of graph convolution and average pooling discussed in this study are deferred to the Sections B.1 and B.2, respectively..

As a result, graph convolution and average pooling concentrate the representation of all the similar nodes and force them to become very similar to each other, potentially leading to representation degeneration problem. This observation inspires us to pose the following research question:

Can the issue of representation degeneration problem in cross-modal retrieval be alleviated by conducting inverse graph convolution (InvGC)?

To answer this question, we first give an inverse variant of graph convolution as follows,

where $A$ is the adjacency matrix for the data in the gallery set. Since the adjacency matrix is not available, to encourage separating the nearest neighbor in terms of the similarity score of each node, we choose $A_{ij}=\operatorname{sim}(i,j)\coloneqq S_{ij}$ with detailed discussion in Section 3.2. Therefore, based on the inverse graph convolution, we propose the basic setting of InvGC as shown in Equation 1, which only considers one modality. We notice that it is able to alleviate the representation degeneration problem as shown in Figure 1.

Note that the ultimate goal of InvGC is to reduce $\Delta_{deg}$ score of the distribution of the representation of the gallery instead of merely the gallery set $G$, which can be regarded only as a sampled subset of the distribution with very limited size in practice. Therefore, the best approximation of the distribution is the training (or validation) gallery set $\hat{G}$ since it is the largest one we can obtain⁴⁴4In practice, the test queries are invisible to each other as the queries do not come at the same time. So the size of the query set $N_{g}$ is equal to 1..

Similarly, the distribution of the query set $\hat{Q}$ is theoretically expected to be similar to that of $\hat{G}$ as a basic assumption in machine learning Bogolin et al. (2022). A detailed explanation of the claims is included in Section B.3. Moreover, as CMR needs to contrast the data points from both modalities, we utilize the (train or validation) gallery set $\hat{G}$ and the (train or validation) query set $\hat{Q}$ to better estimate the hidden distribution as shown in Equation 4,

where $r_{g}$ and $r_{q}$ are two hyperparameters, $\mathcal{S}^{g}\in\mathbb{R}^{N_{g}\times N_{\hat{G}}}$ and $\mathcal{S}^{q}\in\mathbb{R}^{N_{q}\times N_{\hat{Q}}}$ is the adjacency matrices between every pair of embedding from $G$ and $\hat{G}$ and that from $Q$ and $\hat{Q}$, respectively.

To the best of our knowledge, InvGC is the first to utilize the (inverse) graph convolution for separating the representation of data. Instead of the commonly used capability of aggregation and message passing, we introduce an inverse variant of convolution that separates data representations compared to the vanilla graph convolution.

Next, we need to establish the graph structure, i.e., build the adjacency matrix $\mathcal{S}^{g}$ and $\mathcal{S}^{q}$, since there is no natural graph structure in the dataset. The simplest idea will be that the edge weight between $i$ and $j$ equals 1, i.e., $S_{ij}=1$, if the cosine similarity between $\mathbf{x_{i}}$ and $\mathbf{x_{j}}$, i.e., $\operatorname{sim}(\mathbf{x_{i}},\mathbf{x_{j}})$, is larger than 0 (or some thresholds). InvGC with this form of the adjacency matrix is an inverse variant of average pooling. It serves as a baseline in this study, denoted as AvgPool.

However, this scheme is not capable to reflect the degree of the similarity between $\mathbf{x_{i}}$ and $\mathbf{x_{j}}$ since it cannot precisely depict the relation between different data points.

As the magnitude of $S_{ij}$ directly controls how far will $\mathbf{x_{i}}$ go in the opposite direction of $\mathbf{x_{j}}$, a greedy design will be using the similarity score between them as the edge weight, i.e., $S_{ij}=\operatorname{sim}(\mathbf{x_{i}},\mathbf{x_{j}})$.

Therefore, we can calculate the adjacency matrix $\mathcal{S}^{g}$, which contains the similarity score between every pair of embedding from $G$ and $\hat{G}$, respectively. Specifically, the $(i,j)$-entry of $\mathcal{S}^{g}$ follows,

Similarly, the matrix $\mathcal{S}^{q}$ containing the similarity score between every pair of embedding from $G$ and $\hat{Q}$ is calculated as follows,

Now, with the well-defined $\mathcal{S}^{q}$ and $\mathcal{S}^{g}$, we can finally perform InvGC to alleviate representation degeneration problem.

As shown in Theorem 1, given any data point, the similarity of the nearest neighbor in the representation space is critical to retrieval performance. Inspired by this, when performing the inverse convolution on a node, we force InvGC to pay attention to those most similar nodes to it. This can be achieved by assigning edge weight only to the nodes having the top $k$ percent of the largest similarity scores relative to the given node. Specifically, each entry of $\mathcal{S}^{g}$ and $\mathcal{S}^{q}$ in this case is calculated as follows,

where $P_{i}(\hat{G},k)$ is the value of $k$-percentage largest similarity between node $i$ and all the nodes in $\hat{G}$. The same approach applies to $P_{i}(\hat{Q},k)$ as well. We denote this refined adjacency matrix as LocalAdj since it focuses on the local neighborhoods of each node.

With the well-formed adjacency matrices , we formally define InvGC to obtain the updated embedding of $G$, denoted as $G^{\prime}$, in a matrix form as,

where $\operatorname{norm}(\cdot)$ normalizes a matrix with respect to rows, which is employed for uniformly distributing the intensity of convolution when cosine similarity is used and should be removed when adopting other similarity metrics and the adjacency matrices $\mathcal{S}^{g}$ and $\mathcal{S}^{q}$ can be calculated as Equations 5, 6 and 7. Note that, compared to Equation 4, we separate the convolution on $\hat{G}$ and $\hat{Q}$ to pursue more robust results, for avoiding the distribution shifts between $\hat{G}$ and $\hat{Q}$ due to the imperfection of the representation method.

In summary, InvGC, as shown in Equation 9, is a brand new type of graph operation performed on the specifically designed graph structures (adjacency matrix) of data points in the cross-modal dataset. It helps alleviate the representation degeneration problem by separating data points located close to each other in the representation space.

After obtaining $G^{\prime}$, the similarity between the $i$-th gallery points $\mathbf{g}^{\prime}$ and a query point $\mathbf{q}$ is calculated as $sim(\mathbf{q},\mathbf{g}^{\prime})$.

The implementation of InvGC exactly follows Equation 9 with the adjacency matrix defined in Equations 5 and 6 and a separate pair of tuned hyperparameters $r_{g}$ and $r_{q}$ for each retrieval model of each dataset. To balance the edge weight in $\mathcal{S}^{q}$ and $\mathcal{S}^{g}$ and make sure the scale of weights is stable, they subtract their average edge weights, respectively.

The only difference between InvGC w/LocalAdj and InvGC is the adjacency matrix applied. Instead of the ones from Equations 5 and 6, we apply $\mathcal{S}^{q}$ and $\mathcal{S}^{g}$ defined in Equations 7 and 8. We choose the value of $k$ to be 1 (i.e., top 1% nearest neighbors) throughout the study while the proposed method is very robust to the value of the $k$. There is a large range of reasonable values that can boost the performance, proved by the ablation study in Section 4.3.

AvgPool is the simplest variant of inverse graph convolution with binary adjacency matrix where the edge weight between a pair of nodes is 1 if they are neighbors, or 0 otherwise. Then, following the approach in LocalAdj, we update the embeddings using only the top $p$ percent of nearest neighbors. To provide a more comprehensive benchmark, we pick four values of $p$ from $10\%$ to $100\%$. Note that we also independently tune $r_{g}$ and $r_{q}$ for AvgPool to make sure the evaluation is fair. The comparison with AvgPool validates not only the effectiveness of InvGC but also the importance of the similarity-based adjacency matrix. The detailed setting is included in Section C.4.

While we mainly focus our experiments on standard benchmarks for text-image retrieval, i.e., MSCOCO Lin et al. (2014) and Flickr30k Plummer et al. (2017), we also explore the generalization of InvGC by selecting four text-video retrieval benchmarks (MSR-VTT Xu et al. (2016), MSVD Chen and Dolan (2011), Didemo Hendricks et al. (2017), and ActivityNet Fabian Caba Heilbron and Niebles (2015)) and two text-audio retrieval benchmark (AudioCaps Kim et al. (2019) and CLOTHO Drossos et al. (2020)). The details of the benchmarks are deferred to Section C.1.

To evaluate the retrieval performance of InvGC, we use recall at Rank K (R@K, higher is better), median rank (MdR, lower is better), and mean rank (MnR, lower is better) as retrieval metrics, which are widely used in previous retrieval works Luo et al. (2022); Ma et al. (2022); Radford et al. (2021).

In this section, to answer a series of questions relating to InvGC and InvGC w/LocalAdj, we investigate its performance on MSCOCO with CLIP given different settings. Due to space limitations, discussions of the sensitivity of InvGC w/LocalAdj to $k$ and the complexity of both methods are included in the Appendix.

RQ1: Is the data degeneration problem alleviated? This problem can be firstly explained by the change of the similarity measure within the test gallery set $G$. As presented in Table 1, we collect the mean similarity of the gallery set of both tasks for three scenarios, the overall mean (MeanSim), the mean between the nearest neighbor(MeanSim@1), and the mean between nearest 10 neighbors (MeanSim@10). Note that MeanSim@1 is strictly equivalent to $\Delta_{deg}(G)$. It is very clear that InvGC and InvGC w/LocalAdj do reduce the similarity on all accounts, especially MeanSim@1, indicating a targeted ability to alleviate the data degeneration issue.

Besides, given the assumption that the distribution of the test query set $Q$ is close to that of $G$, the similarity score of the gallery set to the query set for both tasks is also worth exploring. Since any point in $G$ should theoretically share an identical representation with its corresponding query in $Q$ and we try to maximize the similarity between them, we exclude this similarity score between them. Consequently, we want the similarity to be as small as possible since it reflects the margin of the retrieval task, as a gallery point is supposed to be as far from the irrelevant queries as possible to have a more robust result. We adopt the same metrics as Table 1, and the results are presented in Table 2. Again, we observe a comprehensive decrease in the similarity score, especially between the nearest neighbors. Note that, compared to InvGC, InvGC w/LocalAdj can better address the representation degeneration problem, validating that the design of LocalAdj does help alleviate the problem by focusing more on the local information. Not for MSCOCO alone, we witness exactly similar results across all the datasets and methods, whose detail is included in Continuation on RQ1 Section C.7.

RQ2: Is InvGC (or InvGC w/LocalAdj) sensitive to the hyperparameter $r_{g}$ and $r_{q}$? To answer the question, we evaluate the R@1 metrics of InvGC with a very large range of hyperparameters respective to the optimal choice adopted. We defer the analysis of InvGC w/LocalAdj to Section C.7. For each task, we fix one of $r_{g}$ or $r_{q}$ and tune the other to show the change on the R@1 metrics. The results of the MSCOCO dataset are shown in Figure 2. Although subject to some variation, InvGC constantly outperforms the baseline, which is presented as the red dashed line. This indicates that the proposed method can consistently improve performance with a very large range of parameters.

RQ3: How much data is needed for both proposed methods? Since we use the training query and gallery set as a sampled subset from the hidden distribution of representation, it is quite intuitive to ask if the performance of InvGC or InvGC w/LocalAdj is sensitive to the size of this sampled subset. Therefore, we uniformly sample different ratios of data from both the training query and gallery set at the same time and evaluate the performance of both methods with the identical hyperparameters, as presented in Figure 3. From the results, we conclude that both proposed methods perform stably and robustly regardless of the size of the training data.

RQ4: Is InvGC w/LocalAdj sensitive to the hyperparameter $k$? To address the question, we evaluate the R@1 metrics of InvGC w/LocalAdj with a very large range of possible $k$ values (even in logarithmic scale) compared to the optimal choice adopted(i.e.,$k=1$). For each task, we fix everything except the $k$ value.The results of MSCOCO dataset are shown in Figure 4. Compared with the baseline, it is safe to claim that the proposed InvGC w/LocalAdj is very robust to the choice of $k$.

In this section, we present the quantitative results of four cross-modal retrieval benchmarks. Across eight different benchmarks, InvGC and InvGC w/LocalAdj significantly improve upon the baselines, demonstrating the superiority of our proposed methods.

Text-Image Retrieval. Results are presented in Tables 3 and 4. We observe that one of our methods achieves the best performance on R@1, R@5, and R@10 by a large margin. When evaluated on the CLIP method, InvGC w/LocalAdj outperforms the baselines on both the MSCOCO and Flickr30k datasets, improving R@1 and R@5 by at least 2% compared to all baselines.

Text-Video Retrieval. Results are presented in Tables 5, 6 and 7. We can also conclude that one of our methods achieves the best performance on R@1, R@5, and R@10. Specifically, on the ActivityNet dataset, InvGC w/LocalAdj shows excellent performance with both CLIP4CLIP and X-CLIP methods, significantly outperforming all the baselines on R@1 and R@5 roughly by 2%.

Text-Audio Retrieval. Results are presented in Tables 8 and 9. On the CLOTHO dataset, InvGC exhibits significantly better performance compared to all the baselines while InvGC w/LocalAdj achieves the best results on the AudioCaps dataset.

In summary, our experiments demonstrate that employing InvGC consistently improves retrieval performance across different datasets and retrieval tasks. The models with InvGC demonstrate better accuracy and ranking in retrieving relevant videos, images, and textual descriptions based on given queries. The complete results of retrieval performance can be found in Section C.6.