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

Identyfikatory

DOI

10.34808/tq2021/25.3/d

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

grid graph; analytical form of graph Laplacians; spectral clustering; graph cuts

PL

graf siatkowy; analityczna forma grafu Laplacianie; grupowanie spektralne; graf cięcia

• Wydawca: Politechnika Gdańska
• Czasopismo: TASK Quarterly : scientific bulletin of Academic Computer Centre in Gdansk
• Rocznik: 2021
• Tom: Vol. 25, No 3
• Strony: 329--353
• Opis fizyczny: Bibliogr. 21 poz., rys.

Twórcy

autor

Kłopotek Mieczysław

• Institute of Computer Science, Polish Academy of Sciences, ul. Jana Kazimierza 5, 01-248 Warsaw, Poland

autor

Wierzchoń Sławomir

• Institute of Computer Science, Polish Academy of Sciences, ul. Jana Kazimierza 5, 01-248 Warsaw, Poland

autor

Kłopotek Robert

• Faculty of Mathematics and Natural Sciences, The Cardinal Stefan Wyszyński University, ul. Wóycickiego 1/3, 01-938 Warsaw, Poland

Bibliografia

• [1] Wierzchoń S T and Kłopotek M A 2018 Modern Clustering Algorithms, Studies in Big Data, Springer Verlag, 34
• [2] von Luxburg U 2007 A tutorial on spectral clustering., Statistics and Computing 17 (4) 395
• [3] Dingo C H Q, He X, Zha H, Gu M, and Simon H D 2001 A min-max cut algorithm for graph partitioning and data clustering., Proceedings of the 2001 IEEE International Conference on Data Mining, IEEE Computer Society 107
• [4] Dhillon I S, Guan Y and Kulis B 2005 A unified view of kernel k-means, spectral clustering and graph cuts., Technical Report TR-04-25, University of Texas Dept. of Computer Science
• [5] Shi J and Malik J 2000 Normalized cuts and image segmentation., IEEE Trans. Pattern Anal. Mach. Intell. 22 (8) 888
• [6] Meila M and Shi J 2001 A random walks view of spectral segmentation, AI and STATISTICS (AISTATS) 203
• [7] Afsar M M and Tayarani-N M-H 2014 Clustering in sensor networks: A literature survey., Journal of Network and Computer Applications 46 198
• [8] Shahraki A, Taherkordi A, Haugen O and Eliassen F 2020 Clustering objectives in wireless sensor networks: A survey and research direction analysis., Computer Networks 180 107376
• [9] Li X, Claramunt Ch and Ray C 2010 A grid graph-based model for the analysis of 2d indoor spaces, Computers, Environment and Urban Systems 34 532
• [10] Weisstein E W 2017 Grid graph., From MathWorld - A Wolfram Web Resource
• [11] Edwards T 2013 The discrete laplacian of a rectangular grid.
• [12] Bos A 2012 Index notation of grid graphs., https://sites.math.washington.edu/~reu/papers/2013/tom/Discrete(2013)
• [13] Fiedler M 1973 Algebraic connectivity of graphs, Czech. Math. J. 23 (98) 298
• [14] Pozrikidis C 2014 An Introduction to Grids, Graphs, and Networks, OUP USA
• [15] Sorkine O 2005 Laplacian mesh processing., Eurographics 2005 – State of the Art Reports, The Eurographics Association 53
• [16] Kłopotek M A 2019 Spectral Analysis of Laplacian of a Multidimensional Grid Graph - Combinatorial versus Normalized and Random Walk Laplacians, arXiv:1707.05210
• [17] Cvetković D, Rowlinson P, and Simić S 2007 Signless laplacians of finite graphs, Linear Algebra and its Applications 423 (5) 155
• [18] Grady L and Schwartz EL 2006 Isoperimetric graph partitioning for image segmentation, IEEE Trans. on Pat. Anal. and Mach. Int 28 469
• [19] Gallier J 2017 Spectral Theory of Unsigned and Signed Graphs. Applications to Graph Clustering: a Survey, arXiv:1601.04692
• [20] Tremblay N, Puy G, Gribonval R and Vandergheynst P 2016 Compressive spectral clustering., Proc. of the 33rd Intl. Conf. on Machine Learning 48 1002
• [21] Davies E, Gladwell G, Leydold J, and Stadler P 2001 Discrete nodal domain theorems, Linear Algebra and its Applications

Uwagi

PL

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).