- Tytuł:
- Weighted Laplacians of grids and their application for inspection of spectral graph clustering methods
- Autorzy:
-
Kłopotek, Mieczysław
Wierzchoń, Sławomir
Kłopotek, Robert - Powiązania:
- https://bibliotekanauki.pl/articles/1954572.pdf
- Data publikacji:
- 2021
- Wydawca:
- Politechnika Gdańska
- Tematy:
-
grid graph
analytical form of graph Laplacians
spectral clustering
graph cuts
graf siatkowy
analityczna forma grafu Laplacianie
grupowanie spektralne
graf cięcia - Opis:
- This paper investigates the relationship between various types of spectral clustering methods and their kinship to relaxed versions of graph cut methods. This predominantly analytical study exploits the closed (or nearly closed) form of eigenvalues and eigenvectors of unnormalized (combinatorial), normalized, and random walk Laplacians of multidimensional weighted and unweighted grids. We demonstrate that spectral methods can be compared to (normalized) graph cut clustering only if the cut is performed to minimize the sum of the weight square roots (and not the sum of weights) of the removed edges. We demonstrate also that the spectrogram of the regular grid graph can be derived from the composition of spectrograms of path graphs into which such a graph can be decomposed, only for combinatorial Laplacians. It is impossible to do so both for normalized and random-walk Laplacians. We investigate the in-the-limit behavior of combinatorial and normalized Laplacians demonstrating that the eigenvalues of both Laplacians converge to one another with an increase in the number of nodes while their eigenvectors do not. Lastly, we show that the distribution of eigenvalues is not uniform in the limit, violating a fundamental assumption of the compact spectral clustering method.
- Źródło:
-
TASK Quarterly. Scientific Bulletin of Academic Computer Centre in Gdansk; 2021, 25, 3; 329-353
1428-6394 - Pojawia się w:
- TASK Quarterly. Scientific Bulletin of Academic Computer Centre in Gdansk
- Dostawca treści:
- Biblioteka Nauki
Artykuł