Towards Scalable Spectral Embedding and Data Visualization via Spectral Coarsening

Zhiqiang Zhao, Ying Zhang, Zhuo Feng

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

9 Scopus citations

Abstract

This paper proposes a scalable multilevel framework for the spectral embedding of large undirected graphs. The proposed method first computes much smaller yet sparse graphs while preserving the key spectral (structural) properties of the original graph, by exploiting a nearly-linear time spectral graph coarsening approach. Then, the resultant spectrally-coarsened graphs are leveraged for the development of much faster algorithms for multilevel spectral graph embedding (clustering) as well as visualization of large data sets. We conducted extensive experiments using a variety of large graphs and datasets and obtained very promising results. For instance, we are able to coarsen the "coPapersCiteseer"graph with 0.43 million nodes and 16 million edges into a much smaller graph with only 13K (32X fewer) nodes and 17K (950X fewer) edges in about 16 seconds; the spectrally-coarsened graphs allow us to achieve up to 1,100X speedup for multilevel spectral graph embedding (clustering) and up to 60X speedup for t-SNE visualization of large data sets.

Original languageEnglish
Title of host publicationWSDM 2021 - Proceedings of the 14th ACM International Conference on Web Search and Data Mining
Pages869-877
Number of pages9
ISBN (Electronic)9781450382977
DOIs
StatePublished - 3 Aug 2021
Event14th ACM International Conference on Web Search and Data Mining, WSDM 2021 - Virtual, Online, Israel
Duration: 8 Mar 202112 Mar 2021

Publication series

NameWSDM 2021 - Proceedings of the 14th ACM International Conference on Web Search and Data Mining

Conference

Conference14th ACM International Conference on Web Search and Data Mining, WSDM 2021
Country/TerritoryIsrael
CityVirtual, Online
Period8/03/2112/03/21

Keywords

  • data visualization
  • graph clustering
  • spectral embedding
  • spectral graph theory

Fingerprint

Dive into the research topics of 'Towards Scalable Spectral Embedding and Data Visualization via Spectral Coarsening'. Together they form a unique fingerprint.

Cite this