Clustering graph data: the roadmap to spectral techniques

Abstract

Abstract Graph data models enable efficient storage, visualization, and analysis of highly interlinked data, by providing the benefits of horizontal scalability and high query performance. Clustering techniques, such as K-means, hierarchical clustering, are highly beneficial tools in data mining and machine learning to find meaningful similarities and differences between data points. Recent developments in graph data models, as well as clustering algorithms for graph data, have shown promising results in image segmentation, gene data analysis, etc. This has been primarily achieved through research and development of algorithms in the field of spectral theory, leading to the conception of spectral clustering algorithms. Spectral clustering algorithms have been one of the most effective in grouping similar data points in graph data models. In this paper, we have compiled 16 spectral clustering algorithms and compared their computational complexities, after an overview of graph data models and graph database models. Furthermore, we provided a broad taxonomy to classify most existing clustering algorithms and discussed the taxonomy in detail.

Keywords

• Graph data
• Clustering
• Laplacian
• Spectral