Constrained spectral clustering via multi-layer graph embeddings on a Grassmann manifold

Trokicić, Aleksandar ; Todorović, Branimir

International Journal of Applied Mathematics and Computer Science, Tome 29 (2019) no. 1, pp. 125-137.

Résumé

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.

Détail

Keywords: spectral clustering, constrained clustering, multilayer graph, Grassmann manifold, Nyström method, Laplacian matrix
Mots-clés : grupowanie widmowe, graf wielowarstwowy, metoda Nyströma, macierz Laplaciana

Bibliographie

[1] Choromanska, A., Jebara, T., Kim, H., Mohan, M. and Monteleoni, C. (2013). Fast spectral clustering via the Nyström method, International Conference on Algorithmic Learning Theory, Singapore, Republic of Singapore, pp. 367–381.

[2] Coleman, T., Saunderson, J. and Wirth, A. (2008). Spectral clustering with inconsistent advice, 25th International Conference on Machine Learning, Helsinki, Finland, pp. 152–159.

[3] De Bie, T., Suykens, J. and De Moor, B. (2004). Learning from general label constraints, Joint IAPR International Workshops on Statistical Techniques in Pattern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR), Lisbon, Portugal, pp. 671–679.

[4] Dong, X., Frossard, P., Vandergheynst, P. and Nefedov, N. (2014). Clustering on multi-layer graphs via subspace analysis on Grassmann manifolds, IEEE Transactions on Signal Processing 62(4): 905–918.

[5] Fowlkes, C., Belongie, S., Chung, F. and Malik, J. (2004). Spectral grouping using the Nystrom method, IEEE Transactions on Pattern Analysis and Machine Intelligence 26(2): 214–225.

[6] Golub, G.H. and Van Loan, C.F. (1996). Matrix Computations, Johns Hopkins University Press, Baltimore, MD, pp. 374–426.

[7] Hamm, J. and Lee, D.D. (2008). Grassmann discriminant analysis: A unifying view on subspace-based learning, Proceedings of the 25th International Conference on Machine Learning, Helsinki, Finland, pp. 376–383.

[8] Hamm, J. and Lee, D.D. (2009). Extended Grassmann kernels for subspace-based learning, in D. Koller et al. (Eds.), Advances in Neural Information Processing Systems 21, Curran Associates, Inc., Vancouver, pp. 601–608.

[9] Harandi, M.T., Sanderson, C., Shirazi, S. and Lovell, B.C. (2011). Graph embedding discriminant analysis on Grassmannian manifolds for improved image set matching, IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Colorado Springs, CO, USA, pp. 2705–2712.

[10] Kamvar, S.D., Klein, D. and Manning, C.D. (2003). Spectral learning, 18th International Joint Conference on Artificial Intelligence, Acapulco, Mexico, pp. 561–566.

[11] Kumar, S., Mohri, M. and Talwalkar, A. (2009). Sampling techniques for the Nyström method, 12th International Conference on Artificial Intelligence and Statistics, Barcelona, Spain, pp. 304–311.

[12] Li, J., Xia, Y., Shan, Z. and Liu, Y. (2015). Scalable constrained spectral clustering, IEEE Transactions on Knowledge and Data Engineering 27(2): 589–593.

[13] Li, M., Lian, X.-C., Kwok, J.T. and Lu, B.-L. (2011). Time and space efficient spectral clustering via column sampling, IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Colorado Springs, CO, USA, pp. 2297–2304.

[14] Li, Z., Liu, J. and Tang, X. (2009). Constrained clustering via spectral regularization, IEEE Conference on Computer Vision and Pattern Recognition, Miami, FL, USA, pp. 421–428.

[15] Lichman, M. (2013). UCI machine learning repository, University of California Irvine, Irvine, CA, http://archive.ics.uci.edu/ml.

[16] Lu, Z. and Carreira-Perpinan,M.A. (2008). Constrained spectral clustering through affinity propagation, IEEE Conference on Computer Vision and Pattern Recognition, Anchorage, AK, USA, pp. 1–8.

[17] Manning, C.D., Raghavan, P. and Schütze, H. (2008). Introduction to Information Retrieval, Cambridge University Press, New York, NY.

[18] Ng, A.Y., Jordan, M.I. and Weiss, Y. (2002). On spectral clustering: Analysis and an algorithm, Advances in Neural Information Processing Systems 2(14): 849–856.

[19] Turk, M. and Pentland, A. (1991). Eigenfaces for recognition, Journal of Cognitive Neuroscience 3(1): 71–86.

[20] Von Luxburg, U. (2007). A tutorial on spectral clustering, Statistics and Computing 17(4): 395–416.

[21] Wang, X. (2014). On constrained spectral clustering and its applications (Matlab code), https://sites.google .com/site/gnaixgnaw/home.

[22] Wang, X., Qian, B. and Davidson, I. (2014). On constrained spectral clustering and its applications, Data Mining and Knowledge Discovery 28(1): 1–30.

[23] White, S. and Smyth, P. (2005). A spectral clustering approach to finding communities in graphs, Proceedings of the 2005 SIAM International Conference on Data Mining, Newport Beach, CA, USA, pp. 274–285.

[24] Xu, Q., des Jardins, M. and Wagstaff, K. (2005). Constrained spectral clustering under a local proximity structure assumption, 18th International Conference of the Florida Artificial Intelligence Research Society (FLAIRS-05), Clearwater Beach, FL, USA, pp. 866–867.