Improved Dynamic Graph Learning through Fault-Tolerant Sparsification

Chun Jiang Zhu; Sabine Storandt; Kam-Yiu Lam; Song Han; Jinbo Bi

Improved Dynamic Graph Learning through Fault-Tolerant Sparsification

Chun Jiang Zhu
, Sabine Storandt
, Kam-Yiu Lam
, Song Han
, Jinbo Bi^*

^*Corresponding author for this work

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

4 Citations (Scopus)

Abstract

Graph sparsification has been used to improve the computational cost of learning over graphs, e.g., Laplacian-regularized estimation, graph semi-supervised 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. © 2019 by the author(s).

Original language	English
Title of host publication	Proceedings of the 36^th International Conference on Machine Learning
Editors	Kamalika Chaudhuri, Ruslan Salakhutdinov
Publisher	ML Research Press
Pages	7624-7633
Publication status	Published - Jun 2019
Event	36th International Conference on Machine Learning (ICML 2019) - Long Beach, United States Duration: 9 Jun 2019 → 15 Jun 2019 https://icml.cc/

Publication series

Name	Proceedings of Machine Learning Research
Volume	97
ISSN (Electronic)	2640-3498

Conference

Conference	36th International Conference on Machine Learning (ICML 2019)
Place	United States
City	Long Beach
Period	9/06/19 → 15/06/19
Internet address	https://icml.cc/

Bibliographical note

Full text of this publication does not contain sufficient affiliation information. With consent from the author(s) concerned, the Research Unit(s) information for this record is based on the existing academic department affiliation of the author(s).

Funding

This work was supported by NSF grants: DBI1356655, CCF-1514357 and IIS-1718738. Jinbo Bi was also supported by NIH grants 5R01DA037349-04 and 5K02DA043063-03.

Access Output

https://proceedings.mlr.press/v97/zhu19b.html

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Zhu, C. J., Storandt, S., Lam, K.-Y., Han, S., & Bi, J. (2019). Improved Dynamic Graph Learning through Fault-Tolerant Sparsification. In K. Chaudhuri, & R. Salakhutdinov (Eds.), Proceedings of the 36^th International Conference on Machine Learning (pp. 7624-7633). (Proceedings of Machine Learning Research; Vol. 97). ML Research Press. https://proceedings.mlr.press/v97/zhu19b.html

@inproceedings{517c2ee1978745b893483147f2714d70,

title = "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 semi-supervised 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. {\textcopyright} 2019 by the author(s). ",

author = "Zhu, \{Chun Jiang\} and Sabine Storandt and Kam-Yiu Lam and Song Han and Jinbo Bi",

note = "Full text of this publication does not contain sufficient affiliation information. With consent from the author(s) concerned, the Research Unit(s) information for this record is based on the existing academic department affiliation of the author(s).; 36th International Conference on Machine Learning (ICML 2019) ; Conference date: 09-06-2019 Through 15-06-2019",

year = "2019",

month = jun,

language = "English",

series = "Proceedings of Machine Learning Research",

publisher = "ML Research Press",

pages = "7624--7633",

editor = "Kamalika Chaudhuri and Ruslan Salakhutdinov",

booktitle = "Proceedings of the 36th International Conference on Machine Learning",

url = "https://icml.cc/",

}

Zhu, CJ, Storandt, S, Lam, K-Y, Han, S & Bi, J 2019, Improved Dynamic Graph Learning through Fault-Tolerant Sparsification. in K Chaudhuri & R Salakhutdinov (eds), Proceedings of the 36^th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 97, ML Research Press, pp. 7624-7633, 36th International Conference on Machine Learning (ICML 2019), Long Beach, California, United States, 9/06/19. <https://proceedings.mlr.press/v97/zhu19b.html>

Improved Dynamic Graph Learning through Fault-Tolerant Sparsification. / Zhu, Chun Jiang; Storandt, Sabine; Lam, Kam-Yiu et al.
Proceedings of the 36^th International Conference on Machine Learning. ed. / Kamalika Chaudhuri; Ruslan Salakhutdinov. ML Research Press, 2019. p. 7624-7633 (Proceedings of Machine Learning Research; Vol. 97).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Improved Dynamic Graph Learning through Fault-Tolerant Sparsification

AU - Zhu, Chun Jiang

AU - Storandt, Sabine

AU - Lam, Kam-Yiu

AU - Han, Song

AU - Bi, Jinbo

N1 - Full text of this publication does not contain sufficient affiliation information. With consent from the author(s) concerned, the Research Unit(s) information for this record is based on the existing academic department affiliation of the author(s).

PY - 2019/6

Y1 - 2019/6

N2 - Graph sparsification has been used to improve the computational cost of learning over graphs, e.g., Laplacian-regularized estimation, graph semi-supervised 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. © 2019 by the author(s).

AB - Graph sparsification has been used to improve the computational cost of learning over graphs, e.g., Laplacian-regularized estimation, graph semi-supervised 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. © 2019 by the author(s).

UR - https://www.scopus.com/pages/publications/85078063076

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85078063076&origin=recordpage

M3 - RGC 32 - Refereed conference paper (with host publication)

T3 - Proceedings of Machine Learning Research

SP - 7624

EP - 7633

BT - Proceedings of the 36th International Conference on Machine Learning

A2 - Chaudhuri, Kamalika

A2 - Salakhutdinov, Ruslan

PB - ML Research Press

T2 - 36th International Conference on Machine Learning (ICML 2019)

Y2 - 9 June 2019 through 15 June 2019

ER -

Improved Dynamic Graph Learning through Fault-Tolerant Sparsification

Abstract

Publication series

Conference

Bibliographical note

Funding

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this