Automatic graph pruning based on kernel alignment for spectral clustering

•A graph pruning approach, Kernel Alignment based Graph Pruning (KAGP), is proposed.•KAGP enhances both the local and global data consistencies.•KAGP enhances the clustering performance in most of the cases.•KAGP avoids the need of a comprehensive user knowledge about its free parameters.•KAGP is a suitable alternative to support spectral clustering algorithms.

Detection of data structures in spectral clustering approaches becomes a difficult task when dealing with complex distributions. Moreover, there is a need of a real user prior knowledge about the influence of the free parameters when building the graph. Here, we introduce a graph pruning approach, termed Kernel Alignment based Graph Pruning (KAGP), within a spectral clustering framework that enhances both the local and global data consistencies for a given input similarity. The KAGP allows revealing hidden data structures by finding relevant pair-wise relationships among samples. So, KAGP estimates the loss of information during the pruning process in terms of a kernel alignment-based cost function. Besides, we encode the sample similarities using a compactly supported kernel function that allows obtaining a sparse data representation to support spectral clustering techniques. Attained results shows that KAGP enhances the clustering performance in most of the cases. In addition, KAGP avoids the need for a comprehensive user knowledge regarding the influence of its free parameters.

Graphical abstractFigure optionsDownload full-size imageDownload high-quality image (109 K)Download as PowerPoint slide