# Construction of the similarity matrix for the spectral clustering method: numerical experiments

arXiv: https://arxiv.org/abs/1904.11352 · HTML: https://mlsanity.com/paper/1904.11352/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Apr 2019.

## Built on by (most cited first, 2 of 2)

- [A New Similarity Function for Spectral Clustering with Application to Plant Phenotypic Data](https://mlsanity.com/paper/2312.14920/) (2023)
- [Advanced spectral clustering for heterogeneous data in credit risk monitoring systems](https://mlsanity.com/paper/2509.00546/) (2025)

## Abstract (arXiv)

Spectral clustering is a powerful method for finding structure in a dataset through the eigenvectors of a similarity matrix. It often outperforms traditional clustering algorithms such as k-means when the structure of the individual clusters is highly non-convex. Its accuracy depends on how the similarity between pairs of data points is defined. Two important items contribute to the construction of the similarity matrix: the sparsity of the underlying weighted graph, which depends mainly on the distances among data points, and the similarity function. When a Gaussian similarity function is used, the choice of the scale parameter σ can be critical. In this paper we examine both items, the sparsity and the selection of suitable σ's, based either directly on the graph associated to the dataset or on the minimal spanning tree (MST) of the graph. An extensive numerical experimentation on artificial and real-world datasets has been carried out to compare the performances of the methods.