Sparsity-aware Clustering based on Graph Matching

Supervised by: Aylin Tastan

If you are interested in this topic or have further questions, do not hesitate to contact me.

Context/Background/Current State

The construction of an informative graph model plays a crucial role to learn the intrinsic relationships hidden in data and it has numerous applications such as in clustering/classification, subspace learning and semi-supervised learning. In cluster analysis, the graph model represents each feature vector as a vertex and describes the association relationships using an affinity matrix in which block diagonal structure is a commonly desired feature [1].

Partly motivated by the natural occurrence of block diagonally structured affinity matrices in cluster analysis, block diagonal representation has been the subject of intense scientific research. Sparse representation is one of the most common ways of constructing a block diagonal affinity matrix [1,2]. However, a major challenge for almost all sparse representation methods is to determine the level of sparsity, i.e. the regularization parameter. The choice of the sparsity level has been researched by analyzing the similarity coefficients’ distribution [3], via supervised learning algorithms [4,5], geometric interpretations [6], connectedness [7], eigenvalues [8] and eigenvectors [9].

To the best of available knowledge, a graph clustering algorithm that controls the level sparsity using graph matching has not been proposed in the literature. Motivated by this, a plan of the proposed project, that controls the sparsity level in clustering using graph matching, is provided in the following.


The aim of this research project is to design a sparsity-aware graph clustering algorithm using the advantageous property of graph matching algorithms. The detailed description of the research goals are provided in the following.

  • Demonstrating the applicability of graph matching algorithms to sparsity-aware graph clustering: In [8] and [9], sparsity-aware graph clustering has been performed by approximating spectral properties of a sparse graph. Motivated by its promising performance about determining sparsity level, this work aims to demonstrate applicability of graph matching algorithms to sparsity-aware clustering which enables evaluating similarity to a defined target sparse graph model in graph domain.
  • Design of a sparsity-aware graph clustering algorithm: In addition to determining sparsity level using a graph matching algorithm, a time-efficient design of sparsity-aware graph clustering algorithm is another research interest for the planned project.
  • Analyzing the performance of graph matching-based sparsity level control in comparison to existing methods: After designing main steps of the algorithm, it is important to benchmark its performance against state-of-the-art sparsity control methods in terms of clustering.


  • Literature review.
  • Determination of the sparse graph model.
  • Sparsity level control based on graph matching algorithms.
  • Application of graph matching to sparsity-aware clustering.
  • Analyzing performance of the proposed sparsity-level control.

Required Skills

  • Basic knowledge about graph theory and algorithms
  • Good programming skills
  • Good level of mathematical understanding

In addition to the above requirements, the following abilities are helpful to conduct the project:

  • Basic knowledge about graph clustering algorithms
  • Basic knowledge about graph matching algorithms
  • Having an experience in real-world data set analysis


This project is mainly structured on sparsity-aware graph clustering which necessitates understanding fundamental mathematical concepts of graph theory and algorithms. In particular, a basic theoretical background in linear algebra and graph theory is helpful to understand the applicability of graph clustering ideas to sparsity-aware clustering.

Further Reading

  1. Lu, C., Feng, J., Lin, Z., Mei, T., & Yan, S. (2018). Subspace clustering by block diagonal representation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 41, 487-501.
  2. Xie, X., Guo, X., Liu, G., & Wang, J. (2017). Implicit block diagonal low-rank representation. IEEE Transactions on Image Processing, 27, 477-489.
  3. Taştan, A., Muma, M., & Zoubir, A. M. (2021). Sparsity-aware Robust Community Detection. Signal Processing, 187, 108147.
  4. García-Pedrajas, N., Del Castillo, J. A. R., & Cerruela-García, G. (2015). A proposal for local k values for k-nearest neighbor rule. IEEE Transactions on Neural Networks and Learning Systems, 28, 470-475.
  5. Mullick, S. S., Datta, S., & Das, S. (2018). Adaptive learning-based k-nearest neighbor classifiers with resilience to class imbalance. IEEE Transactions on Neural Networks and Learning Systems, 29, 5713-5725.
  6. Arora, S., Rao, S., & Varizani, U. (2009). Expander flows, geometric embeddings and graph partitioning. Journal of the ACM, 56, 1-37.
  7. Nasihatkon, B., & Hartley, R. (2011). Graph connectivity in sparse subspace clustering. In Proceedings of CVPR 2011 (pp. 2137-2144).
  8. Taştan, A., Muma, M., & Zoubir, A. M. (2022). Eigenvalue-Based Block Diagonal Representation and Application to p-Nearest Neighbor Graphs. In Proceedings of the 30th European Signal Processing Conference (pp. 1761-1765).
  9. Taştan, A., Muma, M., Ollila, E., & Zoubir, A. M. (2023). Sparsity-Aware Block Diagonal Representation for Subspace Clustering. In Proceedings of the 31st European Signal Processing Conference (Accepted).
  10. Taştan, A. (2023). Contributions to Robust Graph Clustering: Spectral Analysis and Algorithms. Ph.D. thesis, Technische Universität Darmstadt. Available: