Uncovering hidden block structure for clustering

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

doi:10.1007/978-3-030-46150-8_9

Uncovering hidden block structure for clustering

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

Mathematics And Statistics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution book

3 Citations (Scopus)

55 Downloads (Pure)

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 language	English
Title of host publication	Machine Learning and Knowledge Discovery in Databases
Subtitle of host publication	European Conference, ECML PKDD 2019, Würzburg, Germany, September 16–20, 2019, Proceedings, Part I
Editors	Ulf Brefeld, Elisa Fromont, Andreas Hotho, Arno Knobbe, Marloes Maathuis, Céline Robardet
Place of Publication	Cham, Switzerland
Publisher	Springer
Pages	140-155
Number of pages	16
ISBN (Electronic)	978-3-030-46150-8
ISBN (Print)	978-3-030-46149-2
DOIs	https://doi.org/10.1007/978-3-030-46150-8_9
Publication status	Published - 30 Apr 2020
Event	Joint European Conference on Machine Learning and Knowledge Discovery in Databases - Würzburg, Germany Duration: 16 Sept 2019 → 20 Sept 2019

Publication series

Name	Lecture Notes in Artificial Intelligence
Publisher	Springer
Volume	11906

Conference

Conference	Joint European Conference on Machine Learning and Knowledge Discovery in Databases
Abbreviated title	ECML PKDD 2019
Country/Territory	Germany
City	Würzburg
Period	16/09/19 → 20/09/19

Keywords

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

Access to Document

10.1007/978-3-030-46150-8_9

Le-Gorrec-etal-ECML-PKDD-2019-Uncovering-hidden-block-structureAccepted author manuscript, 1.73 MB

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

le Gorrec, Luce ; Mouysset, Sandrine ; Duff, Iain S. et al. / Uncovering hidden block structure for clustering. Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2019, Würzburg, Germany, September 16–20, 2019, Proceedings, Part I. editor / Ulf Brefeld ; Elisa Fromont ; Andreas Hotho ; Arno Knobbe ; Marloes Maathuis ; Céline Robardet. Cham, Switzerland : Springer, 2020. pp. 140-155 (Lecture Notes in Artificial Intelligence).

@inproceedings{4ad8f98482754928be77cf7b90535a1b,

title = "Uncovering hidden block structure for clustering",

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{\textquoteright}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.",

keywords = "clustering, unsupervised learning, spectral clustering, doubly stochastic scaling, community detection, shape detection",

author = "{le Gorrec}, Luce and Sandrine Mouysset and Duff, {Iain S.} and Knight, {Philip A.} and Daniel Ruiz",

year = "2020",

month = apr,

day = "30",

doi = "10.1007/978-3-030-46150-8_9",

language = "English",

isbn = "978-3-030-46149-2",

series = "Lecture Notes in Artificial Intelligence",

publisher = "Springer",

pages = "140--155",

editor = "Ulf Brefeld and Elisa Fromont and Andreas Hotho and Arno Knobbe and Marloes Maathuis and C{\'e}line Robardet",

booktitle = "Machine Learning and Knowledge Discovery in Databases",

note = "Joint European Conference on Machine Learning and Knowledge Discovery in Databases<br/>, ECML PKDD 2019 ; Conference date: 16-09-2019 Through 20-09-2019",

}

le Gorrec, L, Mouysset, S, Duff, IS , Knight, PA & 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. Lecture Notes in Artificial Intelligence, vol. 11906, Springer, Cham, Switzerland, pp. 140-155, Joint European Conference on Machine Learning and Knowledge Discovery in Databases
, Würzburg, Germany, 16/09/19. https://doi.org/10.1007/978-3-030-46150-8_9

Uncovering hidden block structure for clustering. / le Gorrec, Luce; Mouysset, Sandrine; Duff, Iain S. et al.
Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2019, Würzburg, Germany, September 16–20, 2019, Proceedings, Part I. ed. / Ulf Brefeld; Elisa Fromont; Andreas Hotho; Arno Knobbe; Marloes Maathuis; Céline Robardet. Cham, Switzerland: Springer, 2020. p. 140-155 (Lecture Notes in Artificial Intelligence; Vol. 11906).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution book

TY - GEN

T1 - Uncovering hidden block structure for clustering

AU - le Gorrec, Luce

AU - Mouysset, Sandrine

AU - Duff, Iain S.

AU - Knight, Philip A.

AU - Ruiz, Daniel

PY - 2020/4/30

Y1 - 2020/4/30

N2 - 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.

AB - 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.

KW - clustering

KW - unsupervised learning

KW - spectral clustering

KW - doubly stochastic scaling

KW - community detection

KW - shape detection

UR - https://ecmlpkdd2019.org/

U2 - 10.1007/978-3-030-46150-8_9

DO - 10.1007/978-3-030-46150-8_9

M3 - Conference contribution book

SN - 978-3-030-46149-2

T3 - Lecture Notes in Artificial Intelligence

SP - 140

EP - 155

BT - Machine Learning and Knowledge Discovery in Databases

A2 - Brefeld, Ulf

A2 - Fromont, Elisa

A2 - Hotho, Andreas

A2 - Knobbe, Arno

A2 - Maathuis, Marloes

A2 - Robardet, Céline

PB - Springer

CY - Cham, Switzerland

T2 - Joint European Conference on Machine Learning and Knowledge Discovery in Databases<br/>

Y2 - 16 September 2019 through 20 September 2019

ER -

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

Uncovering hidden block structure for clustering

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Philip Knight

Cite this

Uncovering hidden block structure for clustering

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Profiles

Philip Knight

Cite this