online read us now
Paper details
Number 1 - March 2019
Volume 29 - 2019
Constrained spectral clustering via multi-layer graph embeddings on a Grassmann manifold
Aleksandar Trokicić, Branimir Todorović
Abstract
We present two algorithms in which constrained spectral clustering is implemented as unconstrained spectral clustering
on a multi-layer graph where constraints are represented as graph layers. By using the Nystrom approximation in one of
the algorithms, we obtain time and memory complexities which are linear in the number of data points regardless of the
number of constraints. Our algorithms achieve superior or comparative accuracy on real world data sets, compared with
the existing state-of-the-art solutions. However, the complexity of these algorithms is squared with the number of vertices,
while our technique, based on the Nyström approximation method, has linear time complexity. The proposed algorithms
efficiently use both soft and hard constraints since the time complexity of the algorithms does not depend on the size of the
set of constraints.
Keywords
spectral clustering, constrained clustering, multi-layer graph, Grassmann manifold, Nyström method, Laplacian matrix