# A Novel Approach to Incremental Diffusion for Continuous Dataset Updates in Image Retrieval
## 5 Proposed Methodology  
In previous methods, the transition matrix is usually decomposed into four blocks to separate the query from the gallery, namely  
\[\mathbf{S}= \begin{bmatrix}\mathbf{S}_{qq}&\mathbf{S}_{qg}\\ \mathbf{S}_{gq}&\mathbf{S}_{gg}\end{bmatrix} , \tag{5}\]  
where \(\mathbf{S}_{qq}\in\mathbb{R}^{m\times m}\), \(\mathbf{S}_{qg}=\mathbf{S}_{gq}^{\top}\in\mathbb{R}^{m\times n}\), and \(\mathbf{S}_{gg}\in\mathbb{R}^{n\times n}\). This leads to a decomposed closed-form solution on the gallery side:  
\[\mathbf{f}_{g}^{\infty}=\alpha(1-\alpha)(\mathbf{I}-\alpha\mathbf{S}_{gg})^{ -1}\mathbf{S}_{gq}\mathbf{f}_{q}^{0}. \tag{6}\]  
After ignoring the positive constant multiplier \(\alpha(1-\alpha)\) that has no effect on ranking, the entire process of diffusion can be simply described by  
\[\mathbf{f}_{g}^{\infty}\propto(\mathbf{I}-\alpha\mathbf{S}_{gg})^{-1}\mathbf{ S}_{gq}\mathbf{f}_{q}^{0}. \tag{7}\]  
By convention, \(\mathbf{I}-\alpha\mathbf{S}_{gg}\) is a Laplacian matrix \(\mathcal{L}_{g}\). There are two main approaches to solve Equation (7): (1) building a truncated graph at runtime after the query is given or (2) pre-computing the inverse of the Laplacian on the gallery side. The first one, also called online diffusion, constructs a graph for every single query. It naturally has the ability to handle new gallery images while its computational cost on the graph construction is inevitable. The second method has the advantage in terms of speed since it moves most heavy computations offline. However, such an efficiency gain makes it difficult to be used for growing data. Once new data are added to the gallery, the reconstruction of the graph and recomputation of the inverse of the Laplacian are required, which is very costly, as shown on the left side of Figure 1.  
For the purpose of handling new data, we first introduce an anchor graph into diffusion. The anchor graph serves as a rational approximation of the complete gallery graph, balancing computational tractability with structural fidelity. These anchors are created by applying clustering to the entire gallery set or a portion of the gallery set. In practice, we take the cluster centers from the result of the K-Means algorithm as anchor points. Let the set of cluster centers be \(\mathcal{C}=\{\mathbf{c}_{1},\ldots,\mathbf{c}_{k}\}\), where \(k\) is the num  
Figure 1: Comparison between the offline diffusion (**left**) and the proposed diffusion (**right**). In the gallery, we use black to indicate existing samples and red to indicate newly added samples. The upper branch refers to the diffusion on an existing dataset, while the lower branch refers to the diffusion on an incremented dataset. K-Means clustering. In addition, we adopt a technique called local anchor embedding (LAE) proposed in [17] to reconstruct every gallery feature by a weighted sum of its nearest cluster centers. By reconstructing gallery features via LAE, we preserve the intrinsic data manifold while enabling incremental updates--a rational trade-off for real-world scalability. Suppose the gallery features and cluster centers are kept in matrices \(\mathbf{X}_{\mathcal{G}}\in\mathbb{R}^{n\times d}\) and \(\mathbf{X}_{\mathcal{C}}\in\mathbb{R}^{k\times d}\), respectively; we learn the reconstruction weights by optimizing  
\[\min_{\mathbf{z}_{i}}\left\|\mathbf{x}_{i}-\mathbf{X}_{\mathcal{C}}^{\top} \mathbf{z}_{i}\right\|^{2},\;s.t.,\mathbf{1}^{\top}\mathbf{z}_{i}=1,\mathbf{ z}_{i}\leq 0,|\mathbf{z}_{i}|=c. \tag{8}\]  
Now, we obtain a weight matrix \(\mathbf{Z}\in\mathbb{R}^{n\times k}\) whose \(i\)-th column is \(\mathbf{z}_{i}\). This leads to our first approximation:  
\[\mathbf{X}_{\mathcal{G}}\approx\mathbf{Z}\mathbf{X}_{\mathcal{C}}. \tag{9}\]  
It allows us to approximate the diffusion on the gallery by the diffusion on the anchor graph. Following [4], we define an affinity matrix \(\mathbf{A}_{cc}\in\mathbb{R}^{k\times k}\) for the set \(\mathcal{C}\), whose element is obtained by  
\[a_{ij}=