Improved Dynamic Graph Learning through Fault-Tolerant Sparsification.

ABSTRACT: Graph sparsification has been used to improve the computational cost of learning over graphs, e.g., Laplacian-regularized estimation, graph semisupervised learning (SSL) and spectral clustering (SC). However, when graphs vary over time, repeated sparsification requires polynomial order computational cost per update. We propose a new type of graph sparsification namely fault-tolerant (FT) sparsification to significantly reduce the cost to only a constant. Then the computational cost of subsequent graph learning tasks can be significantly improved with limited loss in their accuracy. In particular, we give theoretical analysis to upper bound the loss in the accuracy of the subsequent Laplacian-regularized estimation, graph SSL and SC, due to the FT s

SUBMITTER: Zhu CJ 

PROVIDER: S-EPMC9270720 | biostudies-literature | 2019 Jun

REPOSITORIES: biostudies-literature