Semi-supervised clustering via multi-level random walk
We propose a new semi-supervised clustering algorithm given pairwise constraints. It can expand the influence of the pairwise constraints locally and proportionally. It utilizes the pairwise constraints in an edge?vertex?edge edge ? vertex ? edge  manner. It introduces an intermediate structure to uncover the underlying sub-structures. Given a k-NN sparse similarity matrix, its time complexity is approximately linear.
semi-supervised clustering multi-level random walk pairwise constraint influence expansion spectral clustering