TY - GEN
T1 - Scalable graph topology learning via spectral densification
AU - Wang, Yongyu
AU - Zhao, Zhiqiang
AU - Feng, Zhuo
N1 - Publisher Copyright:
© 2022 ACM.
PY - 2022/2/11
Y1 - 2022/2/11
N2 - 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).
AB - 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).
KW - Dimensionality reduction
KW - Graph topology learning
KW - Spectral clustering
KW - Spectral graph theory
UR - http://www.scopus.com/inward/record.url?scp=85125775896&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85125775896&partnerID=8YFLogxK
U2 - 10.1145/3488560.3498480
DO - 10.1145/3488560.3498480
M3 - Conference contribution
AN - SCOPUS:85125775896
T3 - WSDM 2022 - Proceedings of the 15th ACM International Conference on Web Search and Data Mining
SP - 1099
EP - 1108
BT - WSDM 2022 - Proceedings of the 15th ACM International Conference on Web Search and Data Mining
T2 - 15th ACM International Conference on Web Search and Data Mining, WSDM 2022
Y2 - 21 February 2022 through 25 February 2022
ER -