<abstract xmlns="http://www.w3.org/1999/xhtml"><p>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.</p></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.

Constrained spectral clustering via multi–layer graph embeddings on a grassmann manifold

International Journal of Applied Mathematics and Computer Science

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

We present two algorithms in which constrained spectral clustering is implemented as unconstrained spectral clustering on a multi-layer graph where constraints...

Constrained spectral clustering via multi–layer graph embeddings on a grassmann manifold

Published Online: Mar 29, 2019

Page range: 125 - 137

Received: Feb 02, 2018

Accepted: Oct 16, 2018

DOI: https://doi.org/10.2478/amcs-2019-0010

Keywords
spectral clustering, constrained clustering, multi-layer graph, Grassmann manifold, Nyström method, Laplacian matrix

© 2019 Aleksandar Trokicić et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Constrained spectral clustering via multi–layer graph embeddings on a grassmann manifold

Published Online: Mar 29, 2019

Page range: 125 - 137

Received: Feb 02, 2018

Accepted: Oct 16, 2018

DOI: https://doi.org/10.2478/amcs-2019-0010

Keywordsspectral clustering, constrained clustering, multi-layer graph, Grassmann manifold, Nyström method, Laplacian matrix

© 2019 Aleksandar Trokicić et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Keywords
spectral clustering, constrained clustering, multi-layer graph, Grassmann manifold, Nyström method, Laplacian matrix