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

2 Citations (Scopus)
8 Downloads (Pure)


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
Number of pages16
ISBN (Electronic)978-3-030-46150-8
ISBN (Print)978-3-030-46149-2
Publication statusPublished - 30 Apr 2020
EventJoint European Conference on Machine Learning and Knowledge Discovery in Databases
- Würzburg, Germany
Duration: 16 Sept 201920 Sept 2019

Publication series

NameLecture Notes in Artificial Intelligence


ConferenceJoint European Conference on Machine Learning and Knowledge Discovery in Databases
Abbreviated titleECML PKDD 2019


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


Dive into the research topics of 'Uncovering hidden block structure for clustering'. Together they form a unique fingerprint.

Cite this