Uncovering hidden block structure for clustering

le Gorrec, Luce and Mouysset, Sandrine and Duff, Iain S. and Knight, Philip A. and Ruiz, Daniel; Brefeld, Ulf and Fromont, Elisa and Hotho, Andreas and Knobbe, Arno and Maathuis, Marloes and Robardet, Céline, eds. (2020) Uncovering hidden block structure for clustering. In: Machine Learning and Knowledge Discovery in Databases. Lecture Notes in Artificial Intelligence . Springer, DEU, pp. 140-155. ISBN 978-3-030-46150-8 (https://doi.org/10.1007/978-3-030-46150-8_9)

[thumbnail of Le-Gorrec-etal-ECML-PKDD-2019-Uncovering-hidden-block-structure]
Preview
 Text. Filename: Le_Gorrec_etal_ECML_PKDD_2019_Uncovering_hidden_block_structure.pdf
Accepted Author Manuscript
Download (1MB)| Preview

Abstract

We present a multistage procedure to cluster directed and undirected weighted graphs by finding the block structure of their adjacency matrices. A central part of the process is to scale the adjacency matrix into a doubly-stochastic form, which permits detection of the whole matrix block structure with minimal spectral information (theoretically a single pair of singular vectors suffices). We present the different stages of our method, namely the impact of the doubly-stochastic scaling on singular vectors, detection of the block structure by means of these vectors, and details such as cluster refinement and a stopping criterion. Then we test the algorithm’s effectiveness by using it on two unsupervised classification tasks: community detection in networks and shape detection in clouds of points in two dimensions. By comparing results of our approach with those of widely used algorithms designed for specific purposes, we observe that our method is competitive (for community detection) if not superior (for shape detection) in comparison with existing methods.

CORE (COnnecting REpositories)