# A Novel Approach to Incremental Diffusion for Continuous Dataset Updates in Image Retrieval
## 4 Problem Formulation  
We consider the image retrieval task using global features. Specifically, such a global feature represents the visual content of an image as a high-dimensional vector. By convention, a benchmark dataset consists of the query set and the gallery set. To better distinguish them, we define the query set by \(\mathcal{Q}=\{\mathbf{q}_{1},\ldots,\mathbf{q}_{m}\}\) and the gallery set by \(\mathcal{G}=\{\mathbf{x}_{1},\ldots,\mathbf{x}_{n}\}\), where \(m\) and \(n\) represent the number of images of the query and the gallery. Both query features and gallery features are extracted from the same neural network and share the same dimension, i.e., \(\mathcal{Q}\subset\mathbb{R}^{d}\) and \(\mathcal{G}\subset\mathbb{R}^{d}\). Here, we assume all the features are \(\ell_{2}\) normalized so that the similarity between any two images can be measured by simply using the cosine similarity:  
\[\text{sim}(\mathbf{x}^{i},\mathbf{x}^{i})=\mathbf{x}_{i}^{\top}\mathbf{x}_{j} \in[-1,1],\ \forall i,j\in\{1,\ldots,n+m\}, \tag{1}\]  
where \(\mathbf{x}_{(\cdot)}\in\mathcal{Q}\cup\mathcal{G}\). This assumption follows the recent trend of representation learning toward image retrieval tasks. Image features learned by other metrics can also be adapted by choosing appropriate similarity measurements.  
Under the above definitions, the similarity scores for each query \(\mathbf{q}_{i}\) are simply measured by \(\text{sim}(\mathbf{q}_{i},\mathbf{x}_{j})\), for all \(j\) in \(\{1,\ldots,n\}\). Image retrieval, as a ranking problem, in essence, is achieved by sorting these similarity scores in descending order. Ideally, the top-ranked gallery images should be relevant to the query. However, the features of relevant images are not always located in the neighborhood of each other. To overcome this issue, diffusion is proposed to traverse over the data manifolds by exploiting the local structure of data.  
In diffusion, a graph consisting of image nodes is constructed by connecting images with their nearest neighbors. Such a graph is first denoted by an affinity matrix \(\mathbf{A}\), where its elements are the pairwise similarities between adjacent image nodes. For the further random walk step, such an affinity matrix \(\mathbf{A}\) is converted to be a transition matrix \(\mathbf{S}\) by normalization [2]:  
\[\mathbf{S}=\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}. \tag{2}\]  
Here, the degree matrix \(\mathbf{D}\) is a diagonal matrix with each diagonal element equal to the corresponding row-wise sum of the affinity matrix. Now the graph is represented by the transition matrix and each edge indicates the probability of randomly walking from one node to another. The random walk starts from an initial state denoted by a one-hot vector \(\mathbf{f}^{0}\) where the index of 1 implies the query and iterates the following step:  
\[\mathbf{f}^{t+1}=\alpha\mathbf{S}\mathbf{f}^{t}+(1-\alpha)\mathbf{f}^{0},\ \alpha\in(0,1). \tag{3}\]  
where \(t\) denotes the diffusion iteration index, \(\mathbf{f}^{t}\in\mathbb{R}^{n}\) represents the state vector at iteration \(t\) containing relevance scores for all gallery images, and \(\mathbf{f}^{0}\) is the initial one-hot query vector where only the query position has value 1.  
The diffusion process can be understood as a relevance propagation mechanism over iterations--\(\mathbf{f}^{t}\) encodes the accumulated relevance scores after \(t\) propagation steps, starting from the initial query activation \(\mathbf{f}^{0}\). The parameter \(\alpha\) controls the propagation strength between iterations.  
The state vector is mathematically guaranteed to converge to a closed-form solution:  
\[\mathbf{f}^{\infty}=(1-\alpha)(\mathbf{I}-\alpha\mathbf{S})^{-1}\mathbf{f}^{0}. \tag{4}\]