Scalable graph topology learning via spectral densification

Yongyu Wang, Zhiqiang Zhao, Zhuo Feng

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

11 Scopus citations

Abstract

Graph learning plays an important role in many data mining and machine learning tasks, such as manifold learning, data representation and analysis, dimensionality reduction, data clustering, and visualization, etc. In this work, we introduce a highly-scalable spectral graph densification approach (GRASPEL) for graph topology learning from data. By limiting the precision matrix to be a graph-Laplacian-like matrix, our approach aims to learn sparse undirected graphs from potentially high-dimensional input data. A very unique property of the graphs learned by GRASPEL is that the spectral embedding (or approximate effective-resistance) distances on the graph will encode the similarities between the original input data points. By leveraging high-performance spectral methods, sparse yet spectrally-robust graphs can be learned by identifying and including the most spectrally-critical edges into the graph. Compared with prior state-of-the-art graph learning approaches, GRASPEL is more scalable and allows substantially improving computing efficiency and solution quality of a variety of data mining and machine learning applications, such as manifold learning, spectral clustering (SC), and dimensionality reduction (DR).

Original languageEnglish
Title of host publicationWSDM 2022 - Proceedings of the 15th ACM International Conference on Web Search and Data Mining
Pages1099-1108
Number of pages10
ISBN (Electronic)9781450391320
DOIs
StatePublished - 11 Feb 2022
Event15th ACM International Conference on Web Search and Data Mining, WSDM 2022 - Virtual, Online, United States
Duration: 21 Feb 202225 Feb 2022

Publication series

NameWSDM 2022 - Proceedings of the 15th ACM International Conference on Web Search and Data Mining

Conference

Conference15th ACM International Conference on Web Search and Data Mining, WSDM 2022
Country/TerritoryUnited States
CityVirtual, Online
Period21/02/2225/02/22

Keywords

  • Dimensionality reduction
  • Graph topology learning
  • Spectral clustering
  • Spectral graph theory

Fingerprint

Dive into the research topics of 'Scalable graph topology learning via spectral densification'. Together they form a unique fingerprint.

Cite this