# Markov-Embedded Affinity Learning with Connectivity Constraints for Subspace Clustering
## 1 Introduction  
In the era of the data explosion, the demand for high-dimensional data is increasing in various fields, such as computer vision [1; 2], gene expression analysis [3], and hyperspectral image processing [4; 5]. The effective handling and representation of high-dimensional data has received the most attention. In fact, high-dimensional data have underlying low-dimensional structures [6]. This motivates us to effectively represent high-dimensional data in low-dimensional subspaces [6]. To retrieve these low-dimensional subspaces, it is typically necessary to cluster the data into distinct groups. Each of these groups can be fitted with a subspace, and this procedure is referred to as subspace clustering or subspace segmentation [7]. As an unsupervised learning approach, subspace clustering can be applied in numerous cases. For example, in supervised learning, data labeling is an important and costly operation. As a clustering method, subspace clustering can assist in data labeling, thereby reducing the learning costs. Over the past few years, various subspace clustering algorithms have been developed [8; 9; 10]. Among them, methods based on spectral clustering have attracted a great deal of attention due to their excellent clustering performance and theoretical guarantees. Typically, the key to spectral clustering methods lies in finding an accurate affinity matrix and utilizing it to derive clustering results. To obtain an affinity matrix that accurately characterizes the relationships among samples, researchers have proposed numerous innovative methods. The low-rank representation clustering algorithm (LRR) and sparse subspace clustering algorithm (SSC) are classic subspace clustering methods [8; 9]. The SSC employs the L-1 norm as a regularization term to achieve sparse representation while preserving local data information. The LRR utilizes the nuclear norm as a regularization term to achieve low-rank representation and preserve the global structure of the data. The classic algorithms mentioned above have achieved excellent clustering performance and have been widely applied. However, there are still some shortcomings. First, the approaches to retaining the clustering information are limited. For example, both LRR and SSC solely utilize the self-expressive property, while other properties of the data can also be explored to extract clustering information [11; 12]. Second, it is difficult for these methods to capture the high-order neighbor information. These methods usually focus on the first-order neighbor information, whereas higher-order information plays a crucial role in clustering [13]. Meanwhile, existing methods learn the manifold structure based on the first-order neighbor graph and neglect the high-order nonlinear information. Third, the algorithms do not impose a direct constraint on the block-diagonal representation of the affinity matrix. To this end, this paper proposes a new clustering algorithm, Markov-Embedded Affinity Learning with Connectivity Constraints for Subspace Clustering (MKSC). We briefly summarize the key contributions of this paper as follows. (1) Leveraging the Markov transition probability matrix, Markov transition probability information is embedded into the self-expression framework. This enables the algorithm to preserve more comprehensive clustering information. (2) We use the Markov transition probability matrix to construct a fine-grained neighbor matrix embedded in the MKSC algorithm, fully exploiting the high-order neighbor information and complementary neighbor information. (3) We incorporate the high-order local neighbor relationship and complementary information of the data into manifold learning, thereby learning the underlying manifold structure from a cross-order local neighbor graph. This strategy is starkly different from traditional manifold learning. (4) We enforce a connectivity constraint on the representation matrix, which is more suitable for clustering. The remainder of this paper is structured as follows.