# Cross-Modal Manifold Propagation for Image Recommendation
## 3 Cross-Modal Manifold Propagation
### Visual Manifold Propagation
Gain of modularity \(\Delta Q\) by allotting an image \(v_{i}\) into a specific submanifold is calculated by Equation (5). \[ \begin{split}\Delta Q&=\Bigg{[}\frac{a_{in}+k_{i, in}}{2m}-\bigg{(}\frac{a_{tot}+k_{i}}{2m}\bigg{)}^{2}\Bigg{]}\\ &-\Bigg{[}\frac{a_{in}}{2m}-\Big{(}\frac{a_{tot}}{2m}\Big{)}^{2} -\bigg{(}\frac{k_{i}}{2m}\bigg{)}^{2}\Bigg{]}\\ &=\frac{1}{2m}\bigg{(}k_{i,in}-\frac{a_{tot}k_{i}}{m}\bigg{)}\end{split}  \tag{5}\]  
where \(k_{i,in}\) denotes the sum of the weights between image \(v_{i}\) and images in its neighboring submanifold \(a\). The image is then allotted to submanifold \(a\), taking the maximal gain of modularity \(\Delta Q\). In \(max\Delta Q>0\), image \(v_{i}\) is allotted to corresponding submanifold \(a\). Otherwise, without positive gain, \(max\Delta Q\leq 0\), image \(v_{i}\) would stay in its original submanifold. It is repeated until the submanifold to which each image belongs does not change anymore. Lastly, with stable maximized modularity \(Q\), the global visual manifold was separated into several semantic submanifolds \(A\) containing locally compact semantic distribution. The visual manifold modularization is summarized in Algorithm 1. It provides relatively dominant semantic distribution for the sequential manifold propagation to infer pairwise user-image interactions. ```
0:\(V=[v_{1},\cdots,v_{n}]\)--visual image database. 0: Modularized visual manifold. 1: Images in \(V=[v_{1},\cdots,v_{n}]\) are individually treated as a single submanifold. 2: For each image \(v_{i}\), calculate change in modularity \(\Delta Q\) with Equation (5) in cases of assigning \(v_{i}\) to its neighboring submanifolds. 3: If \(max\Delta Q\ >\ 0\), assign image \(v_{i}\) to the submanifold with maximal gain of modularity \(\Delta Q\). 4: Until a stable modularity is achieved, the global manifold is modularized into several submanifolds. ```  
**Algorithm 1** Visual manifold modularization. With manifold modularization, the proposed CMP method conducts manifold learning to individually propagate users' records along each visual submanifold \(a\in A\) by optimizing Equation (6). \[F_{v}^{*}=\bigcup\limits_{a\in A}\operatorname*{arg\,min}_{F_{v}}(1-\alpha)\|F _{v}-Y\|_{F}^{2}+\alpha tr(<F_{v},L^{a}F_{v}>) \tag{6}\]  
where \(\bigcup\limits_{a\in A}\) is the union operation over submanifold \(a\in A\), \(F_{v}=[f_{ij}^{v}]_{n\times\mathbb{C}}\) is gathered over all semantic submanifolds \(a\in A\), denoting the estimated semantic correlation degree \(f_{ij}^{v}\) of image \(v_{i}\) to user \(u_{j}\) propagated through the visual semantic manifold. \(\alpha\) acts as a trade-off parameter between the global smoothness over visual semantic distribution and the discriminative features of images. \(L^{a}=I-D^{-1/2}W^{a}D^{-1/2}\) is the graph Laplacian matrix of \(W^{a}=[w_{ij}^{a}]_{p\times p}\) with identity matrix \(I\) and degree matrix \(D\) of column sum of \(W^{a}\), \(tr(*)\) calculates the trace of matrix, \(p\) is the size of images in submanifold \(a\). Higher \(f_{ij}^{v}\) implies more semantic correlation in image \(v_{i}\) to interest of user \(u_{j}\). An analytical solution of semantic visual manifold propagation can be derived in Equation (6) for user-image correlation estimation as  
\[F_{v}^{*}=\bigcup\limits_{a\in A}((1-\alpha)I+\alpha L^{a})^{-1}Y \tag{7}\]  
The visual-based recommendation module produces semantic-aware user-image correlation \(F_{v}\) to infer users' potential preference to images from the view of global visual distribution.