# Markov-Embedded Affinity Learning with Connectivity Constraints for Subspace Clustering
## 4 Proposed Method  
In Figure 2, we illustrate the flowchart of the proposed method. Firstly, the data matrix and parameters are provided as inputs. Subsequently, the similarity matrix is derived from the data, which is used to compute the Markov transition probability matrix and the fine-grained neighborhood matrix. After this, leveraging the optimization results from Section 5, all variables are iteratively solved. Finally, spectral clustering as described in Section 5 is performed on affinity matrix Z, resulting in the final clustering outcome. As described in Section 2, the representation matrix obtained from the self-expressive property preserves the similarity information of the data. Meanwhile, the Markov transition  
Figure 2: The flowchart of Markov-Embedded Affinity Learning with Connectivity Constraints for Subspace Clustering (MKSC). probability matrix retains the neighbor information. Generally, samples that are neighbors to each other tend to have higher similarity. Inspired by this, in order to retain the discriminative similarity and neighbor information of the data, we embed the Markov transition probability matrix into the self-expression framework and obtain the following model:  
\[ \begin{split}\min_{Z}&\frac{1}{2}\|X-XZ\|_{F}^{2}+ \frac{\alpha}{2}\|P-Z\|_{F}^{2}+\gamma\|Z\|_{F}^{2},\\ &\textit{s.t.}\;\textit{diag}(Z)=0,\end{split}  \tag{6}\]  
where \(\alpha\geq 0\) is the balance parameter and \(P\) is the Markov transition probability matrix. In Equation (6), \(P\) reveals the one-step random walk probability of the samples, which directly fuses such information with subspace clustering. However, it is insufficient to only adopt the first-order neighbor information. Besides the first-order neighbor information, high-order neighbor information is also important. This type of relationship can preserve more potential structures between the samples and improve the clustering capability of the algorithm. The high-order neighbor relationships of samples can be measured by the probability of a multi-step random walk. In order to fully mine the high-order neighbor information, we define \(P_{[a]}\in R^{n\times n}\) as the high-order Markov transition probability matrix, which reveals the probability of establishing a neighbor relationship between any two samples through \(a\) random walk and is defined as  
\[P_{[a]}=\underbrace{P\cdot P\cdot\cdots\cdot P}_{a\;\textit{times}}=(P)^{a}. \tag{7}\]  
Using \(P_{[a]}\) to preserve the \(a^{th}\)-order neighbor information of the data, we may recover the latent structure of the data in the representation matrix. To fully utilize the diverse-order neighbor information of the samples, we propose a fine-grained neighbor matrix:  
\[P_{N}=\sum_{a=1}^{N}\frac{P_{[a]}+(P_{[a]})^{T}}{2}, \tag{8}\]  
where \(N\) is the highest order of the sample neighbor information. Here, the matrix transpose ensures the symmetry of the neighbor relation, which is natural and necessary. Since \(P_{N}\) preserves the high-order neighbor relationships and complementary information, we adopt \(P_{N}\) to further extend our model as  
\[ \begin{split}\min_{Z}&\frac{1}{2}\|X-XZ\|_{F}^{2}+ \frac{\alpha}{2}\|P_{N}-Z\|_{F}^{2}+\gamma\|Z\|_{F}^{2},\\ &\textit{s.t.}\;\textit{diag}(Z)=0.\end{split}  \tag{9}\]  
In Equation (9), we construct a fine-grained neighbor matrix through the Markov transition probability matrix. At the same time, this fine-grained neighbor matrix is embedded into the self-expression framework of subspace clustering. However, nonlinear structures commonly exist in real-world data and are crucial in revealing the underlying true structural information. In order to better deal with the nonlinear relationships, manifold learning is often integrated into the learning model to capture the latent structures of the data on a manifold. Differing from the traditional manifold learning used in [16], we propose to use the cross-order neighbor graph \(P_{N}\) for manifold learning, which enables our model to capture the comprehensive latent structures of the data.