Improved Dynamic Graph Learning through Fault-Tolerant Sparsification
Improved Dynamic Graph Learning through Fault-Tolerant Sparsification
复制标题
DOI：
--
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
Chun Jiang Zhu;Sabine Storandt;K. Lam;Song Han;J. Bi
中科院分区：
文献类型：
--
作者：
Chun Jiang Zhu;Sabine Storandt;K. Lam;Song Han;J. Bi
图稀疏化已被用于改善在图上学习的计算成本，例如，Laplacian正则化估计，图半监督学习（SSL）和谱聚类（SC）。然而，当图形随时间变化时，重复稀疏化需要每次更新的多项式阶计算成本。我们提出了一种新型的图稀疏化即容错（FT）稀疏化显着降低成本只有一个常数。然后，后续图学习任务的计算成本可以显着提高，其准确性损失有限。特别是，我们给出了理论分析上界损失的准确性，随后的拉普拉斯正则化估计，图SSL和SC，由于FT稀疏化。此外，FT频谱稀疏化可以推广到FT切割稀疏化，用于基于切割的图学习。大量的实验已经证实了所提出的动态图学习方法的计算效率和准确性。
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 sparsification. In addition, FT spectral sparsification can be generalized to FT cut sparsification, for cut-based graph learning. Extensive experiments have confirmed the computational efficiencies and accuracies of the proposed methods for learning on dynamic graphs.