Scalable Graph Topology Learning via Spectral Densification

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 densi.cation 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 e.ective-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 e.ciency and solution quality of a variety of data mining and machine learning applications, such as manifold learning, spectral clustering (SC), and dimensionality reduction (DR).

Automated summary

Graph learning is important in data mining and machine learning. This work introduces a highly-scalable spectral graph densification approach for learning graph topology from data. By limiting the precision matrix to be a graph-Laplacian-like matrix, sparse undirected graphs can be learned from high-dimensional input data. The graphs learned encode similarities between original input data points and enable efficient computing and high-quality solutions.