Improving Hybrid Regularized Diffusion Processes with the Triple-Cosine Smoothness Constraint for Re-Ranking

Abstract

In the last few decades, diffusion processes have been widely used to solve visual re-ranking problems. The key point of these approaches is that, by diffusing the baseline similarities in the context of other samples, more reliable similarities or dissimilarities can be learned. This was later found to be achieved by solving the optimization problem underlying the framework of the regularized diffusion process. In this paper, the proposed model differs from previous approaches in two aspects. Firstly, by taking the high-order information of the graph into account, a novel smoothness constraint, named the triple-cosine smoothness constraint, is proposed. The triple-cosine smoothness constraint is generated using the cosine of the angle between the vectors in the coordinate system, which is created based on a group of three elements: the queries treated as a whole and two other data points. A hybrid fitting constraint is also introduced into the proposed model. It consists of two types of predefined values, which are, respectively, used to construct two types of terms: the squared $L_2$ norm and the $L_1$ norm. Both the closed-form solution and the iterative solution of the proposed model are provided. Secondly, in the proposed model, the learned contextual dissimilarities can be used to describe “one-to-many” relationships, making it applicable to problems with multiple queries, which cannot be solved by previous methods that only handle “one-to-one” relationships. By taking advantage of these “one-to-many” contextual dissimilarities, an iterative re-ranking process based on the proposed model is further provided. Finally, the proposed algorithms are validated on various databases, and comprehensive experiments demonstrate that retrieval results can be effectively improved using our methods.

1. Introduction

Object retrieval is an important issue in computer vision and pattern recognition and is widely used in object recognition [1,2,3], tracking [4,5], bioinformatics [6], medical imaging [7], etc. In general, given one or more queries, the most similar objects in a dataset are obtained based on a pairwise measure, and the retrieval results are presented in the form of ranking similarities or distances between the queries and the other objects. Conventionally, the goal of retrieval is achieved through only pairwise comparisons, with the basic premise that the more similar two elements are, the smaller the measured distance. Unfortunately, this idea suffers from the crucial limitation of ignoring the structure of the underlying data manifold, and the objects from the same category of the query element cannot be retrieved correctly [8,9].

To address this problem, a feasible idea is to analyze the manifold structure by considering all the distances between each pair of elements in the database. In the past two decades, more efforts have been focused on learning contextual similarities, and various methods have been developed to capture the geodesic paths on the manifold, either explicitly or implicitly [10,11,12,13]. Among these studies, a widely accepted approach is to focus on the performance of the baseline similarity diffusing on the graph, where the vertices represent the data points, and the edge between two vertices is weighted by their similarity; thus, the contextual similarity can be learned in an iterative manner. In the retrieval domain, this procedure is called the diffusion process [14,15]. Recently, a standard framework named the regularized diffusion process (RDP) was proposed in [16], which consists of two constraints: the smoothness constraint (SC) and the fitting constraint (FC). From the perspective of this framework, many previous methods can be considered variants of the RDP, and the contextual (dis)similarities are obtained by solving an unconstrained quadratic optimization problem.

Since the RDP was proposed, many improvements have been made to this framework from different perspectives [17,18,19]. With the tensor product graph as a replacement for the original graph, it has been verified that the high-order information of the graph has a great effect on improving retrieval results [9,20]. But there are still some issues that deserve attention: (1) how to construct a triplet-based relationship with high-order information within the RDP framework; (2) how to introduce “one-to-many” relationships into the RDP that contain high-order information; and (3) how to solve optimization problems to obtain closed-form or iterative solutions. In light of these issues, a novel variant of the RDP is proposed in this paper, named the triple-cosine hybrid regularized diffusion process (TH-RDP). The proposed model differs from previous works in two aspects.

Firstly, a novel smoothness constraint named the triple-cosine smoothness constraint is proposed, which takes into account the high-order information of the original graph. We set up a group with three elements: the queries viewed as a whole and two other data points. A coordinate system is then built based on this group. Then, the triple-cosine smoothness constraint is generated using the cosine of the angle between the vectors in the coordinate system. A hybrid fitting constraint is introduced into this model, which consists of two types of terms: the squared $L_2$ norm and the $L_1$ norm. These two terms and the corresponding predefined values are adaptively determined by whether there exists at least one edge between the queries and the data points in the graph. Both the closed-form solution and the iterative solution are then deduced for the proposed model.

Secondly, the proposed model can be used to describe “one-to-many” relationships, whereas many other variants can only learn “one-to-many” contextual dissimilarities. This means that our model can be applied to problems with multiple queries, whereas many other models cannot. By taking advantage of “one-to-many” similarities, we further present an iterative re-ranking process based on the proposed model. In this iterative re-ranking process, the relevant objects along the paths are gradually searched from near to far, and the data manifold structure can be explicitly captured.

The rest of this paper is organized as follows. In the next section, we present the related works. In Section 3, the framework of the regularized diffusion process is briefly reviewed. The details of our method are provided and analyzed in Section 4. In Section 5, experiments on some well-known databases are carried out to illustrate the effectiveness of our method. Finally, we summarize the conclusions and future work.

2. Related Works

Compared with object-matching problems that have been studied for a long time [21,22], contextual similarities have only attracted significant attention in recent years. The PageRank (PR) system of Google [23], derived from the random walk model, is one of the most well-known and successful retrieval methods and is used to rank webpages according to the interests of visitors. Using modified random walk models, several methods have been further proposed based on the idea of PageRank, e.g., global PageRank and personalized PageRank. Zhou et al. [24] presented a ranking method that considers the data manifold.

Label prorogation (LP) was introduced by Bai et al. [25] for learning contextual similarities, and the contextual information on the manifold was utilized to improve retrieval results. This strategy originates from the field of semi-supervised learning, which was first employed to solve the problem of image retrieval in [26]. With the label of the query object fixed, the information from the query element propagates to the unlabeled elements iteratively. Without explicitly selecting the shortest paths, LP suffers from drawbacks such as redundant contextual information and noisy elements. For this reason, Wang et al. [27] developed the shortest path propagation (SSP) method, which captures relevant objects on the shortest paths explicitly. A co-transduction approach for retrieval was proposed by Bai et al. [28], and retrieval performance was significantly improved by fusing different distance measures through a semi-supervised learning framework.

To improve retrieval scores, a novel method based on the locally constrained diffusion process (LCDP) on a KNN graph was proposed in [29]. Kontschieder et al. [30] used a modified mutual KNN graph to process pairwise similarities, and an efficient clustering method was further described based on the proposed approach. A meta-shape similarity focusing on local graph structures was proposed by Egozi et al. [31]. In this approach, each object is represented by a meta-descriptor obtained by building the KNN similarity graph, and the meta-similarity between two objects is efficiently computed using the $L_1$ norm. Instead of propagating the similarity information on the original graph, Yang et al. [9] introduced the tensor product of the original graph, named the tensor product graph (TPG), and demonstrated that the proposed framework can be applied not only to shape recognition but also to image retrieval and image segmentation. Donoser and Bischof [14] revisited the diffusion processes on affinity graphs and introduced a generic framework for diffusion processes. Based on this framework, the approaches in this field can be summarized as specific instances.

Recently, a uniform framework named the regularized diffusion process was proposed in [16,20], and the essence of the TPG was explained theoretically. In [19], another variant, named the hybrid regularization diffusion process, was presented, revealing that the proposed model is closely related to the generalized mean first-passage time. In [32], the graph construction step was treated as a regularized function estimation problem, and an alternating diffusion process was proposed to learn the graph and unknown labels alternately. Using diffusion-based affinity learning and the absorbing Markov chain (AMC), a salient object segmentation framework was proposed in [33], which leverages an iterative diffusion process with the same computational complexity as the diffusion processes on the original graph. In [34], a novel manifold learning algorithm, named Rank Flow Embedding (RFE), was proposed based on recently developed manifold learning approaches, and the obtained context-sensitive embeddings were refined following a rank-based processing flow. In [35], with the contextual information encoded in the unlabeled data points, a rank-based model was presented for the task of weakly supervised classification.

3. Framework of Regularized Diffusion Process

Given $S=\{1,2,\cdots ,n\}$ as a collection of all samples, we have $w_{ij}\in \left[0,1\right]$ and $w_{ij}=w_{ji}$, where $w_{ij}$ represents the connection weight between $i\in S$ and $j\in S$. One can find that $\mathbf{W}={\left[w_{ij}\right]}_{n\times n}$ is a symmetric matrix. With all the elements in S as vertices, $W=\{w_{ij}:i\in S,j\in S\}$ can be treated as the edges between $i\in S$ and $j\in S$, and $w_{ij}=0$ means that there is no edge connection between $i\in S$ and $j\in S$. Then, an undirected graph $\mathcal{G}$ can be constructed with S and W. Moreover, unless otherwise noted, we assume that $\mathcal{G}$ is a strongly connected graph. A diagonal matrix $\mathbf{D}$ can be further defined, whose diagonal elements are $d_{ii}={\displaystyle \sum _{j=1}^n}{w}_{ij}$. In the following, $\mathbf{I}$ represents the identity matrix, and $r_k$ denotes a k-dimensional vector, with each element being $r\in \mathbb{R}$. For convenience, $\mathbf{1}$ is used as a replacement for ${\mathbf{1}}_k$.

Let $f_{ik}\in \left[0,+\infty \right)$ denote the contextual similarity between $k\in S$ and $i\in S$, and the vector with contextual similarities can be expressed as ${\mathit{f}}_k={\left[f_{1k},f_{2k},\cdots ,f_{nk}\right]}^{\top }$. The matrix can be generated with n vectors as $\mathbf{F}=\left[{\mathit{f}}_1,\cdots ,{\mathit{f}}_n\right]$. The objective function of the regularized diffusion process derived from $\mathbf{W}$ can be defined as follows:

$$\mathcal{L}\left({\mathit{f}}_k\right)=\mathcal{S}\left({\mathit{f}}_k\right)+\mu \mathcal{F}\left({\mathit{f}}_k\right),$$

(1)

where $\mathcal{S}\left({\mathit{f}}_k\right)$ is a “smoothing constraint” (SC) and $\mathcal{F}\left({\mathit{f}}_k\right)$ is a “fitting constraint” (FC). $\mu$ is used to balance $\mathcal{S}\left({\mathit{f}}_k\right)$ and $\mathcal{F}\left({\mathit{f}}_k\right)$. It is worth noting that $f_{ij}$ can denote not only contextual similarity but also contextual dissimilarity, which is determined by the predefined values of the fitting constraint.

In Equation (1), the smoothing constraint is used to limit the relationship between different contextual similarities ${\mathit{f}}_k$, and the fitting constraint is used to describe the relationship between the contextual similarity ${\mathit{f}}_k$ and a predetermined value. Considering the impacts of the smoothing constraint and the fitting constraint, solving the optimization problem implies the process of implicitly capturing the manifold structure of the sample space.

To achieve desirable retrieval performances, various types of smooth constraints and fitting constraints have been investigated in recent decades. For the smooth constraint, the “dual smooth constraint” (DSC) ${\mathcal{S}}_{\mathrm{D}}\left({\mathit{f}}_k\right)$ and the “quaternary smooth constraint” (QSC) ${\mathcal{S}}_{\mathrm{Q}}\left(\mathbf{F}\right)$ are two typical forms. For the fitting constraint, two typical forms are the “binary fitting constraint” (BFC) ${\mathcal{F}}_{\mathrm{B}}\left({\mathit{f}}_k\right)$ and the “weighted fitting constraint” (WFC) ${\mathcal{F}}_{\mathrm{W}}\left({\mathit{f}}_k\right)$. Different types of smoothing constraints and fitting constraints are reviewed in Section 3.1 and Section 3.2, respectively.

3.1. Smoothness Constraint

The dual smooth constraint ${\mathcal{S}}_{\mathrm{D}}\left({\mathit{f}}_k\right)$ can be obtained as follows:

$${\mathcal{S}}_{\mathrm{D}}\left({\mathit{f}}_k\right)=\frac{1}{2}\sum _{i,j\in S}{w}_{ij}{\left(f_{ik}-f_{jk}\right)}^2=\frac{1}{2}{\mathit{f}}_k^{\top }\left(\mathbf{D}-\mathbf{W}\right){\mathit{f}}_k=\frac{1}{2}{\mathit{f}}_k^{\top }\mathbf{L}{\mathit{f}}_k,$$

(2)

where $\mathbf{L}$ is the Laplace matrix obtained from $\mathbf{W}$. One can find that the connection weight $w_{ij}$ between two samples is used to restrict the difference between the contextual similarities $f_{ik}$ and $f_{jk}$. This means that the larger $w_{ij}$, the closer the contextual similarities $f_{ik}$ and $f_{jk}$ are to each other. Considering the normalization, ${\mathcal{S}}_{\mathrm{D}}^{\mathrm{nrm}}\left({\mathit{f}}_k\right)$ can be obtained as follows:

$${\mathcal{S}}_{\mathrm{D}}^{\mathrm{nrm}}\left({\mathit{f}}_k\right)=\frac{1}{2}\sum _{i,j\in S}{w}_{ij}{\left(\frac{f_{ik}}{\sqrt{d_{ii}}}-\frac{f_{jk}}{\sqrt{d_{jj}}}\right)}^2=\frac{1}{2}{\mathit{f}}_k^{\top }\left(\mathbf{I}-{\mathbf{D}}^{-\frac{1}{2}}\mathbf{W}{\mathbf{D}}^{-\frac{1}{2}}\right){\mathit{f}}_k=\frac{1}{2}{\mathit{f}}_k^{\top }{\mathbf{L}}^{\mathrm{nrm}}{\mathit{f}}_k,$$

(3)

where ${\mathbf{L}}^{\mathrm{nrm}}$ is the Laplace matrix generated by ${\mathbf{D}}^{-\frac{1}{2}}\mathbf{W}{\mathbf{D}}^{-\frac{1}{2}}$. From Equations (2) and (3), it is easy to find that the relationship between $f_{ik}$ and $f_{jk}$ is highly dependent on $w_{ij}$.

The quaternary smooth constraint ${\mathcal{S}}_{\mathrm{Q}}\left(\mathbf{F}\right)$ can be expressed as follows:

$${\mathcal{S}}_{\mathrm{Q}}\left(\mathbf{F}\right)=\frac{1}{2}\sum _{i,j,k,l\in S}{w}_{ij}{w}_{kl}{\left(f_{ki}-f_{lj}\right)}^2=\frac{1}{2}{\overrightarrow{\mathbf{F}}}^{\top }\left(\mathbb{D}-\mathbb{W}\right)\overrightarrow{\mathbf{F}}=\frac{1}{2}{\overrightarrow{\mathbf{F}}}^{\top }\mathbb{L}\overrightarrow{\mathbf{F}},$$

(4)

where $\overrightarrow{\mathbf{F}}\in {\mathbb{R}}^{n^2\times 1}$ is obtained by stacking the columns of $\mathbf{F}$ one after the other into a column vector, and $\mathbb{L}$ is the Laplace matrix obtained from $\mathbb{W}$. $\mathbb{D}=\mathbf{D}\otimes \mathbf{D}\in {\mathbb{R}}^{n^2\times n^2}$, $\mathbb{W}=\mathbf{W}\otimes \mathbf{W}\in {\mathbb{R}}^{n^2\times n^2}$, and ⊗ denotes the tensor product. According to Equation (4), one can find that if $w_{ij}$ and $w_{kl}$ are both large, the learned $f_{ki}$ and $f_{lj}$ should be similar. Compared with the DSC, the QSC provides a more relaxed condition, which largely avoids the influence of noise edges in the graph. After normalization, ${\mathcal{S}}_{\mathrm{Q}}^{\mathrm{nrm}}\left(\mathbf{F}\right)$ can be obtained as follows:

$$\begin{array}{cc}\hfill {\mathcal{S}}_{\mathrm{Q}}^{\mathrm{nrm}}\left(\mathbf{F}\right)& =\frac{1}{2}\sum _{i,j,k,l\in S}{w}_{ij}{w}_{kl}{\left(\frac{f_{ki}}{\sqrt{d_{ii}{d}_{kk}}}-\frac{f_{lj}}{\sqrt{d_{jj}{d}_{ll}}}\right)}^2\hfill \\ \hfill & =\frac{1}{2}{\overrightarrow{\mathbf{F}}}^{\top }\left(\mathbf{I}-{\mathbb{D}}^{-\frac{1}{2}}\mathbb{W}{\mathbb{D}}^{-\frac{1}{2}}\right)\overrightarrow{\mathbf{F}}=\frac{1}{2}{\overrightarrow{\mathbf{F}}}^{\top }{\mathbb{L}}^{\mathrm{nrm}}\overrightarrow{\mathbf{F}},\hfill \end{array}$$

(5)

where ${\mathbb{L}}^{\mathrm{nrm}}$ is the Laplace matrix derived from ${\mathbb{D}}^{-\frac{1}{2}}\mathbb{W}{\mathbb{D}}^{-\frac{1}{2}}$.

3.2. Fitting Constraint

For the binary fitting constraint, the predefined similarity between element $k\in S$ and itself is 1, while the similarities with all other elements are 0. Then, the binary fitting constraint ${\mathcal{F}}_{\mathrm{B}}\left({\mathit{f}}_k\right)$ can be constructed as follows:

$${\mathcal{F}}_{\mathrm{B}}\left({\mathit{f}}_k\right)=\sum _{i\in S}{\left(f_{ik}-b_{ik}\right)}^2={∥{\mathit{f}}_k-{\mathit{b}}_k∥}_2^2,$$

(6)

where ${\mathit{b}}_k=\left[b_{1k},\cdots ,b_{nk}\right]$, $b_{ik}=1$ for $i=k$; and $b_{ik}=0$ for $i\ne k$. It can be seen that there are only two predefined values, which cannot accurately reflect the different relationships.

For the weighted fitting constraint, ${\mathit{w}}_k$ is selected as the predefined values, and ${\mathcal{F}}_{\mathrm{W}}\left({\mathit{f}}_k\right)$ can be obtained based on the $L_2$ norm as follows:

$${\mathcal{F}}_{\mathrm{W}}\left({\mathit{f}}_k\right)=\sum _{i\in S}{\left(f_{ik}-w_{ik}\right)}^2={∥{\mathit{f}}_k-{\mathit{w}}_k∥}_2^2.$$

(7)

After normalization, ${\mathcal{F}}_{\mathrm{W}}\left({\mathit{f}}_k\right)$ can be obtained as follows:

$${\mathcal{F}}_{\mathrm{W}}\left({\mathit{f}}_k\right)=\sum _{i\in S}{\left(f_{ik}-w_{ik}\right)}^2={∥{\mathit{f}}_k-{\mathbf{D}}^{-1}{\mathit{w}}_k∥}_2^2.$$

(8)

As can be seen, the predefined values in Equations (7) and (8) are much more reasonable than those in the BFC; therefore, the underlying manifold structure can be effectively captured by the learned contextual similarities.

4. The Proposed Method

In this section, the relevant notations are given in a preliminary summary in Section 4.1. In Section 4.2 and Section 4.3, the improvements are introduced and analyzed from the perspectives of the smoothness constraint and the fitting constraint, respectively. Finally, the solution of the proposed model is provided in Section 4.4.

4.1. Preliminary

It is assumed that S consists of two subsets, L and U, where $L\subset S$ and $U\subset S$ contain l labeled objects and u unlabeled ones, respectively. We further divide U into two subsets: A with a objects and B with b objects, where $A=\{i:{\sum }_{k\in L}{w}_{ik}>0,i\in U\}$ and $B=\{j:{\sum }_{k\in L}{w}_{jk}=0,j\in U\}$. According to the above definitions, we have $l+u=n$ and $a+b=u$. For the convenience of discussion, all the samples are rearranged so that unlabeled states are placed before labeled ones, and the states in A are listed before those in B. Then, we have $U=\{1,\cdots ,u\}$, $L=\{u+1,\cdots ,n\}$, $A=\{1,\cdots ,a\}$, and $B=\{a+1,\cdots ,u\}$. Then, $\mathbf{W}$ can be partitioned into blocks as follows:

$$\mathbf{W}=\left[\begin{array}{cc}{\mathbf{W}}_{UU}& {\mathbf{W}}_{UL}\\ {\mathbf{W}}_{LU}& {\mathbf{W}}_{LL}\end{array}\right],$$

(9)

where ${\mathbf{W}}_{UU}={\left[w_{i{i}^{\prime }}\right]}_{u\times u}$, ${\mathbf{W}}_{UL}={\left[w_{i{j}^{\prime }}\right]}_{u\times l}$, ${\mathbf{W}}_{LU}={\left[w_{j{i}^{\prime }}\right]}_{l\times u}$, and ${\mathbf{W}}_{LL}={\left[w_{j{j}^{\prime }}\right]}_{l\times l}$. The diagonal matrix $\mathbf{D}$ can be partitioned into blocks as follows:

$$\mathbf{D}=\left[\begin{array}{cc}{\mathbf{D}}_U& \mathbf{0}\\ \mathbf{0}& {\mathbf{D}}_L\end{array}\right],$$

(10)

where ${\mathbf{D}}_U$ and ${\mathbf{D}}_L$ are a $u\times u$ diagonal matrix and an $l\times l$ diagonal matrix, respectively. ${\mathbf{D}}_U$ can also be partitioned into blocks as follows:

$${\mathbf{D}}_U=\left[\begin{array}{cc}{\mathbf{D}}_A& \mathbf{0}\\ \mathbf{0}& {\mathbf{D}}_B\end{array}\right],$$

(11)

where ${\mathbf{D}}_A$ and ${\mathbf{D}}_B$ are an $a\times a$ diagonal matrix and a $b\times b$ diagonal matrix, respectively. We further define two $u\times u$ diagonal matrices, ${\mathbf{E}}_U$ and ${\mathbf{H}}_U$, where the diagonal elements of ${\mathbf{E}}_U$ and ${\mathbf{H}}_U$ are $e_{ii}={\displaystyle \sum _{j=u+1}^n}{w}_{ij}$ and $h_{ii}={\displaystyle \sum _{j=1}^u}{w}_{ij}$. ${\mathbf{E}}_U$ can be partitioned into blocks as follows:

$${\mathbf{E}}_U=\left[\begin{array}{cc}{\mathbf{E}}_A& \mathbf{0}\\ \mathbf{0}& \mathbf{0}\end{array}\right],$$

(12)

where ${\mathbf{E}}_A$ denotes an $a\times a$ diagonal matrix, and we have ${\mathbf{D}}_U={\mathbf{H}}_U+{\mathbf{E}}_U$.

As discussed in Section 3, $f_{ij}$ denotes the contextual similarity between two samples, which can be treated as a “one-to-one” contextual similarity. Referring to the definition of $f_{ij}$, we introduce $g_{kL}\in \left[0,+\infty \right)$ as the “one-to-many” contextual similarity and have ${\mathit{g}}_L={\left[g_{1L},g_{2L},\cdots ,g_{nL}\right]}^{\top }$, where $k\in U$ and $L\subset S$. For $\forall k\in L$, ${\mathit{g}}_L$ is the maximum value in the range for the contextual similarity, and the minimum value in the range for the contextual dissimilarity.

Then, only ${\mathit{g}}_{UL}={\left[g_{1L},\cdots ,g_{uL}\right]}^{\top }$ is needed to be learned, and the objective function based on ${\mathit{g}}_L$ can be obtained as follows:

$$\mathcal{L}\left({\mathit{g}}_{UL}\right)=\mathcal{S}\left({\mathit{g}}_{UL}\right)+\mu \mathcal{F}\left({\mathit{g}}_{UL}\right),$$

(13)

where $\mathcal{S}\left({\mathit{g}}_{UL}\right)$ and $\mathcal{F}\left({\mathit{g}}_{UL}\right)$ are the smoothing constraint and the fitting constraint, and $\mu$ is the hyperparameter used to balance them.

One can find that the “one-to-one” contextual similarity $f_{ij}$ is actually a special case of the “one-to-many” contextual similarity $g_{kL}$. With L containing only one element n, the “one-to-many” contextual similarity $g_{kL}$ degrades into the “one-to-many” contextual similarity $f_{kn}$.

4.2. Triple-Cosine Smoothness Constraint

Given two unlabeled samples $i\in U$ and $j\in U$, and $L\subset S$, a coordinate system $\left(\mathrm{I},\mathrm{J},\mathrm{L}\right)$ can be generated by taking the pairwise similarity as the cosine value of the angle between the coordinate axes. Specifically, as shown in Figure 1, with $\mathrm{O}$ as the origin, the coordinate system includes the $\mathrm{OI}$ axis, the $\mathrm{OJ}$ axis, and the $\mathrm{OL}$ axis, where $\mathrm{OI}\perp \mathrm{OL}$, $\mathrm{OJ}\perp \mathrm{OL}$, and the angle between $\mathrm{OI}$ and $\mathrm{OJ}$ is ${\theta }_{ij}=arccos{w}_{ij}$, $w_{ij}\in \left[0,1\right]$. $\overrightarrow{\mathrm{OM}}$ and $\overrightarrow{\mathrm{ON}}$ are the vectors on the planes IOL and JOL, respectively. The angle between $\overrightarrow{\mathrm{OM}}$ and $\overrightarrow{\mathrm{OL}}$ is $\angle \mathrm{MOL}={\theta }_{iL}=arccos\left(\frac{1}{l}{\displaystyle \sum _{k\in L}}{w}_{ik}\right)$, and the angle between $\overrightarrow{\mathrm{ON}}$ and $\overrightarrow{\mathrm{OL}}$ is $\angle \mathrm{MOL}={\theta }_{iL}=arccos\left(\frac{1}{l}{\displaystyle \sum _{k\in L}}{w}_{ik}\right)$. We have $\left|\overrightarrow{\mathrm{OM}}\right|=1$ and $\left|\overrightarrow{\mathrm{ON}}\right|=1$.

According to the above definitions, the cosine value of $\angle \mathrm{IOJ}$ is determined by the connection between $i\in U$ and $j\in U$. The cosine value of $\angle \mathrm{MOL}$ is calculated as the mean of all the connections between $i\in U$ and each element from $L\subset S$, and $\angle \mathrm{NOL}$ is calculated as the mean of all the connections between $j\in U$ and each element from $L\subset S$. The angle $\angle \mathrm{MON}$ between $\overrightarrow{\mathrm{OM}}$ and $\overrightarrow{\mathrm{ON}}$ is denoted as $\alpha$, and the cosine value of $\alpha$ is referred to as the triple-cosine. As shown in Equation (A1), it can be expressed as follows:

$$cos\alpha =\frac{1}{l^2}\sum _{k\in L}{w}_{ik}\sum _{k\in L}{w}_{jk}+w_{ij}\sqrt{1-{\left(\frac{1}{l}\sum _{k\in L}{w}_{ik}\right)}^2}\sqrt{1-{\left(\frac{1}{l}\sum _{k\in L}{w}_{jk}\right)}^2}.$$

(14)

According to Equation (14), one can find that during the process of calculating $cos\alpha$, the high-order relationships between data points are implicitly considered. Then, the triple-cosine smoothness constraint ${\mathcal{S}}_{\mathrm{C}}\left({\mathit{g}}_{UL}\right)$ can be defined as follows:

$${\mathcal{S}}_{\mathrm{C}}\left({\mathit{g}}_{UL}\right)=\frac{1}{2}\sum _{i,j=1}^{u}cos\alpha {∥g_{iL}-g_{jL}∥}_2^2.$$

(15)

As shown in Equation (A3), $cos\alpha$ is used to limit how close $g_{iL}$ and $g_{jL}$ are. Unlike ${\mathcal{S}}_{\mathrm{D}}\left({\mathit{f}}_k\right)$, which uses one connection weight $w_{ij}$ to restrict contextual similarities, $cos\alpha$ is the result of multiple factors, including $w_{ij}$, ${\displaystyle \sum _{k\in L}}{w}_{ik}$, and ${\displaystyle \sum _{k\in L}}{w}_{jk}$. So, $w_{ij}$ has an impact on $cos\alpha$, but the value of $cos\alpha$ is not entirely determined by $w_{ij}$. For example, if $i\in U$ and $j\in U$ are very close but $w_{ij}$ is incorrectly set to a small value, ${\mathcal{S}}_{\mathrm{D}}\left({\mathit{f}}_k\right)$ cannot correctly reflect the relationship between contextual similarities. However, in Equation (14), even if the value of $w_{ij}$ is small, $cos\alpha$ could still be a large value. This is due to the closeness of $i\in U$ and $j\in U$; the values of ${\displaystyle \sum _{k\in L}}{w}_{ik}$ and ${\displaystyle \sum _{k\in L}}{w}_{jk}$ may be both very large. Therefore, one can find that the proposed smoothness constraint is insensitive to incorrect connections and noise edges and can be used to improve the process of learning contextual similarities.

According to Equations (15) and (A3), the proposed smoothness constraint can be obtained as follows:

$${\mathcal{S}}_{\mathrm{C}}\left({\mathit{g}}_{UL}\right)=\frac{1}{2}{\mathit{g}}_{UL}^{\top }{\mathbf{L}}_{*}{\mathit{g}}_{UL}=\frac{1}{2}{\mathit{g}}_{UL}^{\top }\left({\mathbf{D}}_{*}-{\mathbf{W}}_{*}\right){\mathit{g}}_{UL},$$

(16)

where ${\mathbf{W}}_{*}={\left[w_{ij}^{*}\right]}_{u\times u}$; ${\mathbf{D}}_{*}$, with $d_{ii}^{*}={\displaystyle \sum _{j=1}^u}{w}_{ij}^{*}$, denotes the diagonal matrix generated by ${\mathbf{W}}_{*}$; and ${\mathbf{L}}_{*}$ is the Laplace matrix obtained based on ${\mathbf{W}}_{*}$. ${\mathbf{W}}_{*}$ can be obtained as follows:

$${\mathbf{W}}_{*}=\frac{1}{l^2}{\mathbf{W}}_{UL}{\mathbf{1}}_l{\mathbf{1}}_l^{\top }{\mathbf{W}}_{UL}^{\top }-{\mathbf{W}}_{UU}\circ {\left(\mathbf{P}{\mathbf{P}}^{\top }\right)}^{\circ \frac{1}{2}},$$

(17)

where $\mathbf{P}={\mathbf{1}}_u-\frac{1}{l}{\left({\mathbf{W}}_{UL}{\mathbf{1}}_l\right)}^{\circ 2}$ and ∘ denotes the Hadamard product. After normalization, we have the smoothness constraint as follows:

$$\begin{array}{cc}\hfill {\mathcal{S}}_{\mathrm{C}}^{\mathrm{nrm}}\left({\mathit{g}}_{UL}\right)& =\frac{1}{2}\sum _{i,j=1}^u{w}_{ij}^{*}{\left(\frac{g_{iL}}{\sqrt{d_{ii}^{*}}}-\frac{g_{jL}}{\sqrt{d_{jj}^{*}}}\right)}^2\hfill \\ \hfill & =\frac{1}{2}{\mathit{g}}_{UL}^{\top }\left(\mathbf{I}-{\mathbf{D}}_{*}^{-\frac{1}{2}}{\mathbf{W}}_{*}{\mathbf{D}}_{*}^{-\frac{1}{2}}\right){\mathit{g}}_{UL}=\frac{1}{2}{\mathit{g}}_{UL}^{\top }{\mathbf{L}}_{*}^{\mathrm{nrm}}{\mathit{g}}_{UL}\hfill \end{array},$$

(18)

where ${\mathbf{L}}_{*}^{\mathrm{nrm}}$ is the Laplace matrix obtained from the normalized matrix ${\mathbf{W}}_{*}$.

4.3. Hybrid Fitting Constraint Based on $L_1$ and $L_2$ Norms

Unlike the previous fitting constraints, which treat all the predefined values equally, two different types of restrictions are created according to the confidence of the predefined values. Specifically, based on whether $k\in U$ is directly connected to the elements in L, the elements from U can be classified into two categories. Firstly, for $k\in U$ with ${\displaystyle \sum _{k\in L}}{w}_{ik}>0$, the predefined values can be clearly and precisely generated, and the squared $L_2$ norm is constructed. On the other hand, for $k\in U$ with ${\displaystyle \sum _{k\in L}}{w}_{ik}=0$, we treat each one equally with a rough predefined value, and the $L_1$ norm is selected. Then, we have the hybrid fitting constraint as follows:

$$\begin{array}{cc}\hfill {\mathcal{F}}_{\mathrm{H}}\left({\mathit{g}}_{UL}\right)& =\frac{1}{2}\sum _{i=1}^a{e}_{ii}{\left(g_{iL}-\frac{d_{ii}}{e_{ii}}\right)}^2+\sum _{j=a+1}^u{d}_{jj}\left|g_{jL}-\xi \right|\hfill \\ \hfill & =\frac{1}{2}{∥{\mathbf{E}}_A^{\frac{1}{2}}{\mathit{g}}_{AL}-{\mathbf{D}}_A{\mathbf{E}}_A^{-\frac{1}{2}}\mathbf{1}∥}_2^2+{∥{\mathbf{D}}_B\left({\mathit{g}}_{BL}-{\mathit{\xi }}_b\right)∥}_1\hfill \end{array}$$

(19)

where $d_{ii}$ and $d_{jj}$ are the diagonal elements of $\mathbf{D}$ and $\xi >max\left({\mathit{g}}_{UL}\right)$ denotes the rough predefined value. ${\mathit{g}}_{AL}={\left[g_{1L},\cdots ,g_{aL}\right]}^{\top }$, ${\mathit{g}}_{BL}={\left[g_{a+1L},\cdots ,g_{uL}\right]}^{\top }$, and ${\mathit{g}}_{UL}={\left[{\mathit{g}}_{AL}^{\top },{\mathit{g}}_{BL}^{\top }\right]}^{\top }$.

It is important to note that, $g_{kL}$ in Equation (19) is a contextual dissimilarity rather than a contextual similarity. Specifically, if $k\in U$ is close to $L\subset S$, the predefined value is set to a small value $\frac{d_{ii}}{e_{ii}}=\frac{{\displaystyle \sum _{j=1}^n}{w}_{ij}}{{\displaystyle \sum _{k=u+1}^n}{w}_{ik}}$. Meanwhile, if $k\in U$ is far from $L\subset S$, the predefined value is set to a very large value $\xi$. Since $\xi >max\left({\mathit{g}}_{UL}\right)$, ${\mathcal{F}}_{\mathrm{H}}\left({\mathit{g}}_{UL}\right)$ can be written as follows:

$${\mathcal{F}}_{\mathrm{H}}\left({\mathit{g}}_{UL}\right)=\frac{1}{2}{∥{\mathbf{E}}_A^{\frac{1}{2}}{\mathit{g}}_{AL}-{\mathbf{D}}_A{\mathbf{E}}_A^{-\frac{1}{2}}{\mathbf{1}}_a∥}_2^2-{\left({\mathbf{D}}_B{\mathit{g}}_{BL}\right)}^{\top }\mathbf{1}+const$$

(20)

where $const$ denotes a constant.

4.4. Solution of Proposed Model

For convenience, we first combine ${\mathcal{S}}_{\mathrm{D}}\left({\mathit{g}}_{UL}\right)$ and ${\mathcal{F}}_{\mathrm{H}}\left({\mathit{g}}_{UL}\right)$ to construct the objective function ${\mathcal{L}}_{\mathrm{DH}}\left({\mathit{g}}_{UL}\right)$ and solve the optimization problem.

According to the previous analysis, ${\mathcal{S}}_{\mathrm{D}}\left({\mathit{g}}_{UL}\right)$ can be defined as follows:

$$\begin{array}{cc}\hfill {\mathcal{S}}_{\mathrm{D}}\left({\mathit{g}}_{kL}\right)& =\frac{1}{2}\sum _{i,j=1}^u{w}_{ij}{\left(g_{iL}-g_{jL}\right)}^2\hfill \\ \hfill & =\frac{1}{2}{\mathit{g}}_{kL}^{\top }\left({\mathbf{H}}_U-{\mathbf{W}}_{UU}\right){\mathit{g}}_{kL}=\frac{1}{2}{\mathit{g}}_{kL}^{\top }{\mathbf{L}}_U{\mathit{g}}_{kL},\hfill \end{array}$$

(21)

where ${\mathbf{L}}_U$ is the Laplace matrix obtained from ${\mathbf{W}}_{UU}$. Then, we have ${\mathcal{L}}_{\mathrm{DH}}\left({\mathit{g}}_{UL}\right)$ as follows:

$$\begin{array}{cc}\hfill {\mathcal{L}}_{\mathrm{DH}}\left({\mathit{g}}_{UL}\right)& ={\mathcal{S}}_{\mathrm{D}}\left({\mathit{g}}_{UL}\right)+\mu {\mathcal{F}}_{\mathrm{H}}\left({\mathit{g}}_{UL}\right)\hfill \\ \hfill & =\frac{1}{2}{\mathit{g}}_{UL}^{\top }{\mathbf{L}}_U{\mathit{g}}_{UL}+\frac{1}{2}\mu {∥{\mathbf{E}}_A^{\frac{1}{2}}{\mathit{g}}_{AL}-{\mathbf{D}}_A{\mathbf{E}}_A^{-\frac{1}{2}}1∥}_2^2-\mu {\left({\mathbf{D}}_B{\mathit{g}}_{BL}\right)}^{\top }\mathbf{1}+const.\hfill \end{array}$$

(22)

Since ${\mathit{g}}_{UL}^{*}=arg\underset{{\mathit{g}}_{UL}}{min}{\mathcal{L}}_{\mathrm{DH}}\left({\mathit{g}}_{UL}\right)$, by taking the partial derivative of $\left({\mathit{g}}_{UL}\right)$ with ${\mathit{g}}_{UL}$, we have

$$\frac{\partial {\mathcal{L}}_{\mathrm{DH}}}{\partial {\mathit{g}}_{UL}}=\left({\mathbf{H}}_U-{\mathbf{W}}_{UU}+\mu {\mathbf{E}}_U\right){\mathit{g}}_{UL}-\mu {\mathbf{D}}_U\mathbf{1}.$$

(23)

Then, by setting Equation (23) to zero, ${\mathit{g}}_{UL}^{*}$ satisfies the following equation:

$$\left({\mathbf{H}}_U-{\mathbf{W}}_U+\mu {\mathbf{E}}_U\right)g_{UL}^{*}=\mu {\mathbf{D}}_U\mathbf{1}.$$

(24)

We further introduce a diagonal matrix $\mathbf{\Lambda }={\mathbf{H}}_U+\mu {\mathbf{E}}_U$, and Equation (24) can be transformed as follows:

$$\left(\mathbf{I}-{\mathbf{\Lambda }}^{-1}{\mathbf{W}}_U\right){\mathit{g}}_{UL}^{*}=\mu {\mathbf{\Lambda }}^{-1}{\mathbf{D}}_U\mathbf{1}.$$

(25)

Since the graph $\mathcal{G}$ is strongly connected, similar to the proof in [19], it can be proven that $\rho \left({\mathbf{\Lambda }}^{-1}{\mathbf{W}}_U\right)<1$, where $\rho \left(·\right)$ is the spectral radius. So, $\mathbf{I}-{\mathbf{\Lambda }}^{-1}{\mathbf{W}}_U$ is invertible, and ${\mathit{g}}_{UL}^{*}$ can be written in a closed-form solution as follows:

$${\mathit{g}}_{UL}^{*}\propto {\left(\mathbf{I}-{\mathbf{\Lambda }}^{-1}{\mathbf{W}}_U\right)}^{-1}{\mathbf{\Lambda }}^{-1}{\mathbf{D}}_U\mathbf{1}.$$

(26)

For the problem of object retrieval and re-ranking, instead of the exact values of the learned contextual similarities, we actually care more about the result of their ranking, which can be directly calculated using Equation (26).

The closed-form solution in Equation (26) can be obtained based on the inverse matrix, and it is time-consuming and complicated. Since $\rho \left({\mathbf{\Lambda }}^{-1}{\mathbf{W}}_U\right)<1$, we have ${\sum }_{m=0}^{\infty }{\left({\mathbf{\Lambda }}^{-1}{\mathbf{W}}_U\right)}^m$ as the series expansion of ${\left(\mathbf{I}-{\mathbf{\Lambda }}^{-1}{\mathbf{W}}_U\right)}^{-1}$. Then, the iterative solution can be obtained by directly replacing ${\left(\mathbf{I}-{\mathbf{\Lambda }}^{-1}{\mathbf{W}}_U\right)}^{-1}$ with ${\sum }_{m=0}^{\infty }{\left({\mathbf{\Lambda }}^{-1}{\mathbf{W}}_U\right)}^m$ in Equation (26).

As discussed previously, ${\mathcal{S}}_{\mathrm{C}}\left({\mathit{g}}_{UL}\right)$ and ${\mathcal{F}}_{\mathrm{H}}\left({\mathit{g}}_{UL}\right)$ are selected as the smoothness constraint and the fitting constraint, and the proposed model is referred to as TH-RDP. The objective function can be obtained as follows:

$$\begin{array}{cc}\hfill {\mathcal{L}}_{\mathrm{CH}}\left({\mathit{g}}_{UL}\right)& ={\mathcal{S}}_{\mathrm{C}}\left({\mathit{g}}_{UL}\right)+\mu {\mathcal{F}}_{\mathrm{H}}\left({\mathit{g}}_{UL}\right)\hfill \\ \hfill & =\frac{1}{2}{\mathit{g}}_{UL}^{\top }{\mathbf{L}}_{*}{\mathit{g}}_{UL}+\frac{1}{2}\mu {∥{\mathbf{E}}_A^{\frac{1}{2}}{\mathit{g}}_{AL}-{\mathbf{D}}_A{\mathbf{E}}_A^{-\frac{1}{2}}1∥}_2^2-\mu {\left({\mathbf{D}}_B{\mathit{g}}_{BL}\right)}^{\top }\mathbf{1}+const.\hfill \end{array}$$

(27)

Similar to the solving process of Equation (22), the closed-form solution of ${\mathit{g}}_{UL}^{*}$ can be written as follows:

$${\mathit{g}}_{UL}^{*}\propto {\left(\mathbf{I}-{\mathbf{\Lambda }}_{*}^{-1}{\mathbf{W}}_{*}\right)}^{-1}{\mathbf{\Lambda }}_{*}^{-1}{\mathbf{D}}_U\mathbf{1},$$

(28)

where ${\mathbf{\Lambda }}_{*}={\mathbf{D}}_{*}+\mu {\mathbf{E}}_U$, and ${\mathbf{D}}_{*}$ is the diagonal matrix with the diagonal element $d_{ii}^{*}={\displaystyle \sum _{j=1}^n}{w}_{ij}^{*}$. The iterative solution can be obtained by replacing ${\left(\mathbf{I}-{\mathbf{\Lambda }}_{*}^{-1}{\mathbf{W}}_{*}\right)}^{-1}$ with the series expansion. Then, it is easy to find that the time complexity for the closed-form solution is $O\left(u^3\right)$, and the time complexity for the iterative solution is $O\left(T·u^2\right)$, where T is the number of iterative steps.

4.5. Iterative Re-Ranking Based on Proposed Model

As discussed in [19], the most difficult problem facing the diffusion process is that, for the relevant object very far away from the query, it will take a long time to complete the information propagation. A feasible approach to address this problem is to introduce the RDP into an iterative re-ranking process. Specifically, in each iteration of this process, several top-ranked samples are selected and treated as the queries in the next iteration, together with those from the current iteration. In this way, the relevant objects can be increasingly selected and identified, and the underlying manifold structure can be gradually captured.

Moreover, in each iteration, only a few top-ranked objects are filtered out and added to the set of queries, so the samples with long paths to the queries do not need to be taken into account. In iteration t, given $L^t$ as the set of the labeled samples, $U^t=\{k:{\sum }_{i\in L^t}{w}_{ij}{w}_{jk}>0,k\notin L^t\}$ is generated, containing the set of unlabeled samples to be ranked in this iteration. During the iteration, ${\Delta }^t$ with $\lambda$ top-ranked objects are selected by ${\mathit{g}}_{U{L}^t}$, and then $L^{t+1}=L^t+{\Delta }^t$ is generated for the next iteration. The iterative re-ranking process based on TH-RDP is referred to as I-TH-RDP.

As shown in Section 3, the regularized diffusion process is carried out on the basis of the graph $\mathcal{G}$, which is generated by $\mathbf{W}$. In practice, $w_{ij}$ is obtained from the pairwise measure, which can be either a distance or a similarity. If the baseline is a distance measure $di{s}_{ij}$, the corresponding similarity $si{m}_{ij}$ can be obtained as follows:

$$si{m}_{ij}=exp\left(-\frac{di{s}_{ij}^2}{{\sigma }_{ij}^2}\right),$$

(29)

where ${\sigma }_{ij}$ can be determined by kNN [25]. To eliminate the impact of noisy $si{m}_{ij}$, $\mathbf{W}={\left[w_{ij}\right]}_{n\times n}$ is further constructed on the basis of reciprocal kNN. In Section 3, it is assumed that $\mathcal{G}$ is a strongly connected graph, which, in reality, does not always hold. On the contrary, $\mathcal{G}$ may be composed of multiple connected components. So, after all the elements from the connected components containing queries are re-ranked, to ensure the proposed method is available, one can create temporary connections by using the filtered similarities.

5. Experimental Results

To demonstrate the advantages of our methods, experiments are conducted in this section, and the performance of our methods is evaluated. It is worth noting that in the following experiments, each category of every selected database contains numerous samples, ranging from 20 to 100. This selection is based on two perspectives. On one hand, the underlying manifold structure needs to be supported by sufficient samples from each category so that the contextual information can be effectively reflected. On the other hand, it is highly probable that the underlying manifold structure is complicated with numerous samples for each class. In this way, the designed experimental tasks are very challenging, and the results can reasonably verify the effectiveness of different methods.

On the basis of an identical baseline, the proposed methods, TH-RDP and I-TH-RDP, are compared with the following state-of-the-art algorithms: LP [25], mkNN [30], TPG [9], GDP [14], and SCA [36]. To provide fair comparisons between our algorithms and the competitors, we run the implementations based on the available codes released by the authors.

In the following, the P–R curve is employed to analyze the performance of different methods, with the horizontal axis and vertical axis representing precision and recall, respectively. The precision and recall values are defined as follows:

$$\mathrm{Precision}=\frac{TP}{TP+FP},$$

(30)

and

$$\mathrm{Recall}=\frac{TP}{TP+FN},$$

(31)

where $TP$ denotes the data points of the same category as the query in the top K ranks, $FP$ denotes those from different categories than the query in the top K ranks, and $FN$ denotes those of the same category as the query but outside the top K ranks. In the P–R curve, we set $K=1,2,\cdots ,N_Q$, where $N_Q$ is the number of data points from the same category. Significantly, when $K=N_Q$, the value of precision equals that of recall, and this value is the retrieval score, which is also employed to evaluate performance.

5.1. Tari-1000 Shape Dataset

The proposed methods are tested on the Tari-1000 dataset [37] in this subsection. In this database, 1000 shapes are divided into 50 categories, and each category contains 20 silhouettes. Figure 2 shows examples from each class in the dataset. The retrieval scores of the baselines, SC and IDSC, were 88.01% and 90.43%. IDSC performed better than SC on this database because of the many articulation changes within each class.

Table 1. Retrieval scores on the Tari-1000 dataset. The top three results are marked in boldface and colored blue, green, and orange, respectively.

Baseline	Method	Retrieval Score
SC [38]	-	88.01%
	LP [25]	96.59%
	mkNN [30]	95.44%
	TPG [9]	97.25%
	GDP [14]	95.52%
	SCA [36]	96.97%
	TH-RDP	97.55%
	I-TH-RDP	97.48%
IDSC [39]	-	90.43%
	LP [25]	98.75%
	mkNN [30]	97.11%
	TPG [9]	99.43%
	GDP [14]	98.00%
	SCA [36]	99.34%
	TH-RDP	99.69%
	I-TH-RDP	99.73%

shows the retrieval scores obtained by the proposed methods and other approaches, while the P–R curves for these methods are plotted in Figure 3. With IDSC as the baseline, the proposed methods achieved near-perfect retrieval scores: 99.73% for TH-RDP and 99.69% for I-TH-RDP. With SC as the baseline, our approaches achieved 97.55% for TH-RDP and 97.48% for I-TH-RDP, improving the original scores by over 9%. Specifically, as observed in Figure 3a,b, previous methods, including SCA [36], TPG [9], and LP [25], exhibited similar performance to the proposed approaches but demonstrated lower precision at high ranges of recall. The retrieval scores in Table 1 and the P–R curves in Figure 3 clearly demonstrate that the proposed methods perform better than the other methods based on the same baseline results.

5.2. Animal Shape Dataset

The Animal dataset, which contains 2000 manually extracted shapes across 20 categories, was first introduced in [40]. In this database, each class provides a larger number of images, resulting in greater variation within a single category [40,41]. This dataset was previously used for classification experiments [41]; however, in this subsection, it is selected for testing retrieval performances. The baseline retrieval scores on the Animal dataset were 38.38% for SC and 40.50% for IDSC.

Table 2. Retrieval rates on the Animal dataset. The top three results are marked in boldface and colored blue, green, and orange, respectively.

Baseline	Method	Retrieval Score
SC [38]	-	38.38%
	LP [25]	45.44%
	mkNN [30]	47.09%
	TPG [9]	53.86%
	GDP [14]	46.27%
	SCA [36]	47.26%
	TH-RDP	54.88%
	I-TH-RDP	55.53%
IDSC [39]	-	40.50%
	LP [25]	45.65%
	mkNN [30]	49.53%
	TPG [9]	56.39%
	GDP [14]	50.09%
	SCA [36]	51.43%
	TH-RDP	57.52%
	I-TH-RDP	57.84%

lists the re-ranking results of different methods, while the P–R curves of our approaches and the competitors are plotted in Figure 4. With IDSC as the baseline, the proposed methods clearly provided the best curve performances across ranges of recall, as well as the highest retrieval scores: 57.52% for TH-RDP and 57.84% for I-TH-RDP. Meanwhile, with SC as the baseline measure, TH-RDP and I-TH-RDP outperformed the other methods across most ranges of the P–R curves, achieving retrieval scores of 54.88% and 55.53%, respectively. Overall, the P–R curves and retrieval scores clearly demonstrate that the proposed methods deliver better results and outperform the other methods, and the baseline methods are improved significantly.

5.3. LEAF Dataset from UCI

Another real-world leaf (LEAF) dataset from the UCI datasets is introduced in this subsection. This dataset, as reported in [42], comprises 40 different plant species. A subset of 30 species numbered from 1 to 15 and from 22 to 36 has been constructed, which exhibits simple leaves according to the description of this dataset. Binary images of leaves from the selected species have also been released, together with the original images, and Figure 5 shows some examples of the color images from this database. For the previous databases in this paper, each class provided an identical number of samples. However, the introduced dataset is imbalanced, and the number of leaves for each class from the subset ranges from 8 to 16. So, given the query objects from various species, we set different values of $N_Q$ to evaluate the retrieval scores. We obtained retrieval scores of 66.10% for SC and 65.51% for IDSC.

The retrieval performances based on different methods are listed in

Table 3. Retrieval rates on the LEAF dataset. The best results for each baseline are marked in boldface and colored blue, green, and orange, respectively.

Baseline	Method	Retrieval Score
SC [38]	-	66.10%
	LP [25]	74.39%
	mkNN [30]	71.29%
	TPG [9]	69.61%
	GDP [14]	67.60%
	SCA [36]	70.96%
	TH-RDP	74.44%
	I-TH-RDP	74.92%
IDSC [39]	-	65.51%
	LP [25]	73.40%
	mkNN [30]	73.70%
	TPG [9]	69.84%
	GDP [14]	65.23%
	SCA [36]	68.57%
	TH-RDP	74.06%
	I-TH-RDP	74.19%

. As shown in Table 3, with IDSC as the baseline, we achieved retrieval results of 74.06% for TH-RDP and 74.19% for I-TH-RDP, respectively. On the other hand, with SC as the baseline, the proposed approaches yielded retrieval scores of 74.44% for TH-RDP and 74.92% for I-TH-RDP. The retrieval results in Table 3 demonstrate that the proposed methods achieved significant improvements, even though the shape dataset is unbalanced. Our approaches performed slightly better than state-of-the-art methods. Moreover, as can be seen in Table 3, our methods boosted the retrieval scores of SC and IDSC by over 8%. The baseline results were significantly improved by the proposed methods.

5.4. ORL Face Dataset

In this subsection, an experiment on the ORL face database, downloaded from the website of AT&T Laboratories Cambridge, is carried out. The ORL face database is a well-known dataset widely used for face recognition that contains 400 grayscale face images across 40 different categories. The images from this database were obtained at different times, with varying lighting, facial expressions, and facial details. Similar to [14], with each image downsampled and normalized to zero mean and unit variance, the vectorized representation (VR) was taken as the feature, and the $L_2$ norm was selected as the input pairwise distance. Instead of using the retrieval window ranging in size from 11 to 20 [14,16], we used the retrieval score as the evaluation metric corresponding to a size 10 retrieval window, which is a more rigorous measure. The retrieval score of this baseline method was 57.13%.

The results of different methods are listed in

Table 4. Retrieval scores on the ORL dataset. The top three results are marked in boldface and colored blue, green, and orange, respectively.

Baseline	Method	Retrieval Score
VR	-	57.13%
	LP [25]	75.68%
	mkNN [30]	69.15%
	TPG [9]	73.40%
	GDP [14]	71.17%
	SCA [36]	69.93%
	TH-RDP	74.42%
	I-TH-RDP	74.08%

, and the corresponding P–R curves are plotted in Figure 6. As shown in Table 4, with the VR as the baseline method, TH-RDP and I-TH-RDP achieved retrieval scores of 74.42% and 74.08%, respectively. Therefore, the baseline result was greatly and effectively improved by our approaches, and the original retrieval score was improved by around 14%. It can be seen in Figure 6 that the P–R curves of our methods achieved the second- and third-best re-ranking results on this dataset.

6. Conclusions

In this paper, with the high-order information taken into account, we proposed a novel variant of the regularized diffusion process with the triple-cosine smoothness constraint and the hybrid fitting constraint. The triple-cosine smoothness constraint is constructed using the cosine of the angle in the coordinate system, which is created based on a group with three elements. For the hybrid fitting constraint, the squared $L_2$ norm and the $L_1$ norm can be adaptively generated according to the predefined values. The closed-form solution and the iterative solution of the proposed model are given. Moreover, for the proposed model, since the learned contextual dissimilarities can be used to represent “one-to-many” relationships, an iterative re-ranking process based on the proposed model is further presented. The experimental results on different databases demonstrate that the proposed methods can significantly improve the baselines.

Some issues still need to be addressed in the future. The effectiveness of the proposed method largely depends on the weighted graph, which is generated based on noise filtering for the baselines. So, how to effectively eliminate noise edges will be investigated further. Moreover, the time complexity for learning contextual similarities is about $O\left(N^3\right)$, and reducing it to meet the requirements of real-time applications is worth studying. Finally, with the rapid development of deep learning, deep features have been increasingly used to analyze pairwise (dis)similarities, and desirable results can often be achieved [2]. In this case, improving the retrieval results obtained with deep features is a task that should be continuously considered and studied in the future.