  Clustering is a fundamental task in machine learning and data science, and
similarity graph-based clustering is an important approach within this domain.
Doubly stochastic symmetric similarity graphs provide numerous benefits for
clustering problems and downstream tasks, yet learning such graphs remains a
significant challenge. Marcus theorem states that a strictly positive symmetric
matrix can be transformed into a doubly stochastic symmetric matrix by diagonal
matrices. However, in clustering, learning sparse matrices is crucial for
computational efficiency. We extend Marcus theorem by proposing the Marcus
mapping, which indicates that certain sparse matrices can also be transformed
into doubly stochastic symmetric matrices via diagonal matrices. Additionally,
we introduce rank constraints into the clustering problem and propose the
Doubly Stochastic Adaptive Neighbors Clustering algorithm based on the Marcus
Mapping (ANCMM). This ensures that the learned graph naturally divides into the
desired number of clusters. We validate the effectiveness of our algorithm
through extensive comparisons with state-of-the-art algorithms. Finally, we
explore the relationship between the Marcus mapping and optimal transport. We
prove that the Marcus mapping solves a specific type of optimal transport
problem and demonstrate that solving this problem through Marcus mapping is
more efficient than directly applying optimal transport methods.
