Spectral vertex sparsifiers and pair-wise spanners over distributed graphs

Chunjiang Zhu, Qinqing Liu, Jinbo Bi
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:12890-12900, 2021.

Abstract

Graph sparsification is a powerful tool to approximate an arbitrary graph and has been used in machine learning over graphs. As real-world networks are becoming very large and naturally distributed, distributed graph sparsification has drawn considerable attention. In this work, we design communication-efficient distributed algorithms for constructing spectral vertex sparsifiers, which closely preserve effective resistance distances on a subset of vertices of interest in the original graphs, under the well-established message passing communication model. We prove that the communication cost approximates the lower bound with only a small gap. We further provide algorithms for constructing pair-wise spanners which approximate the shortest distances between each pair of vertices in a target set, instead of all pairs, and incur communication costs that are much smaller than those of existing algorithms in the message passing model. Experiments are performed to validate the communication efficiency of the proposed algorithms under the guarantee that the constructed sparsifiers have a good approximation quality.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-zhu21c, title = {Spectral vertex sparsifiers and pair-wise spanners over distributed graphs}, author = {Zhu, Chunjiang and Liu, Qinqing and Bi, Jinbo}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {12890--12900}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/zhu21c/zhu21c.pdf}, url = {https://proceedings.mlr.press/v139/zhu21c.html}, abstract = {Graph sparsification is a powerful tool to approximate an arbitrary graph and has been used in machine learning over graphs. As real-world networks are becoming very large and naturally distributed, distributed graph sparsification has drawn considerable attention. In this work, we design communication-efficient distributed algorithms for constructing spectral vertex sparsifiers, which closely preserve effective resistance distances on a subset of vertices of interest in the original graphs, under the well-established message passing communication model. We prove that the communication cost approximates the lower bound with only a small gap. We further provide algorithms for constructing pair-wise spanners which approximate the shortest distances between each pair of vertices in a target set, instead of all pairs, and incur communication costs that are much smaller than those of existing algorithms in the message passing model. Experiments are performed to validate the communication efficiency of the proposed algorithms under the guarantee that the constructed sparsifiers have a good approximation quality.} }
Endnote
%0 Conference Paper %T Spectral vertex sparsifiers and pair-wise spanners over distributed graphs %A Chunjiang Zhu %A Qinqing Liu %A Jinbo Bi %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-zhu21c %I PMLR %P 12890--12900 %U https://proceedings.mlr.press/v139/zhu21c.html %V 139 %X Graph sparsification is a powerful tool to approximate an arbitrary graph and has been used in machine learning over graphs. As real-world networks are becoming very large and naturally distributed, distributed graph sparsification has drawn considerable attention. In this work, we design communication-efficient distributed algorithms for constructing spectral vertex sparsifiers, which closely preserve effective resistance distances on a subset of vertices of interest in the original graphs, under the well-established message passing communication model. We prove that the communication cost approximates the lower bound with only a small gap. We further provide algorithms for constructing pair-wise spanners which approximate the shortest distances between each pair of vertices in a target set, instead of all pairs, and incur communication costs that are much smaller than those of existing algorithms in the message passing model. Experiments are performed to validate the communication efficiency of the proposed algorithms under the guarantee that the constructed sparsifiers have a good approximation quality.
APA
Zhu, C., Liu, Q. & Bi, J.. (2021). Spectral vertex sparsifiers and pair-wise spanners over distributed graphs. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:12890-12900 Available from https://proceedings.mlr.press/v139/zhu21c.html.

Related Material