Uncovering hidden block structure for clustering

Luce le Gorrec, Sandrine Mouysset, Iain S. Duff, Philip A. Knight, Daniel Ruiz

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

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.
Original languageEnglish
Title of host publicationMachine Learning and Knowledge Discovery in Databases
Subtitle of host publicationEuropean Conference, ECML PKDD 2019, Würzburg, Germany, September 16–20, 2019, Proceedings, Part I
EditorsUlf Brefeld, Elisa Fromont, Andreas Hotho, Arno Knobbe, Marloes Maathuis, Céline Robardet
Place of PublicationCham, Switzerland
PublisherSpringer
Pages140-155
Number of pages16
ISBN (Electronic)978-3-030-46150-8
ISBN (Print)978-3-030-46149-2
DOIs
Publication statusPublished - 30 Apr 2020
EventJoint European Conference on Machine Learning and Knowledge Discovery in Databases
- Würzburg, Germany
Duration: 16 Sep 201920 Sep 2019

Publication series

NameLecture Notes in Artificial Intelligence
PublisherSpringer
Volume11906

Conference

ConferenceJoint European Conference on Machine Learning and Knowledge Discovery in Databases
Abbreviated titleECML PKDD 2019
CountryGermany
CityWürzburg
Period16/09/1920/09/19

Keywords

  • clustering
  • unsupervised learning
  • spectral clustering
  • doubly stochastic scaling
  • community detection
  • shape detection

Cite this

le Gorrec, L., Mouysset, S., Duff, I. S., Knight, P. A., & Ruiz, D. (2020). Uncovering hidden block structure for clustering. In U. Brefeld, E. Fromont, A. Hotho, A. Knobbe, M. Maathuis, & C. Robardet (Eds.), Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2019, Würzburg, Germany, September 16–20, 2019, Proceedings, Part I (pp. 140-155). (Lecture Notes in Artificial Intelligence; Vol. 11906). Springer. https://doi.org/10.1007/978-3-030-46150-8_9