This work stands apart: there is almost nothing nearby, with the nearest neighbor at a distance of 0.523. Surrounding studies address the large-scale structure of the universe, machine learning, and convolutional neural networks, but they tackle different problems. This paper fills a gap in spectral clustering by proposing a method that does not require a pre-specified number of clusters and relies on the intrinsic structure of the data.
The SP-MGM algorithm builds a similarity matrix and computes the eigenvectors of the unnormalized Laplacian corresponding to the smallest positive eigenvalues. For each vector, the components are sorted in ascending order, and the maximum gap between adjacent values is found. This gap splits the vertices into two subsets. By intersecting such binary partitions across several eigenvectors, the algorithm forms clusters. The mathematical justification relies on perturbation theory for eigenvectors: if clusters are well separated, gaps in the eigenvectors precisely indicate cluster boundaries.
On LFR benchmark graphs with 50 and 100 nodes, SP-MGM consistently outperformed KMEANS, spectral KMEANS, and agglomerative clustering in terms of NMI and ARS across the full range of the mixing parameter. At low average degree and low mixing, only SP-MGM gave reasonable results. For larger networks, it performed comparably or better, only falling behind the agglomerative method at very large sizes. The algorithm automatically determined the number of clusters: with m eigenmodes, it almost always produced m+1 clusters. On sea surface temperature data in the Niño 3.4 region from 1955 to 2016, SP-MGM identified seven clusters corresponding to different phases of El Niño, La Niña, and neutral conditions, and the clusters were not determined solely by the ONI index, indicating different 'flavors' of the phenomenon.
Unlike neighboring works that apply machine learning to cosmological data or images, this paper proposes a new clustering algorithm with mathematical justification and validation on climate data. It shows that a simple analysis of gaps in eigenvectors can compete with popular methods and automatically reveal structure without external parameters. This expands the toolkit of spectral clustering and provides a way to detect subtle differences in climate regimes.
The algorithm can be scaled to larger networks through a hierarchical approach, where spectral methods are applied to subsets of data. Adaptation to other types of graphs and comparison with a broader set of algorithms, including deep learning-based methods, is possible. For climate applications, it would be interesting to explore how the identified clusters relate to regional precipitation and temperature.
The method could be useful in neuroscience, social networks, computer vision, and digital forensics, where identifying natural groups is required. In climatology, it helps classify El Niño states and improve forecasts.
Conduct a systematic comparison of SP-MGM with other spectral algorithms on diverse benchmark sets. Investigate the algorithm's behavior on graphs with overlapping clusters and noise.
In climatology, the question of how different 'flavors' of El Niño affect regional climate remains open. This work shows that clustering spatially distributed temperature anomalies can reveal such subtypes, but their physical interpretation and predictive value require further study.
The SP-MGM algorithm almost always outputs exactly m+1 clusters for m eigenmodes, although theoretically there could be up to $2^m$. This points to a deep connection between gaps in eigenvectors and graph structure.
The idea of finding hidden structures by gaps in data recalls the analysis of 'patterns' in William Gibson's novel 'Pattern Recognition', where the protagonist intuitively finds anomalies in video streams. The algorithm formalizes such a search for graphs.