Timezone: »

Spectral vertex sparsifiers and pair-wise spanners over distributed graphs
Chunjiang Zhu · Qinqing Liu · Jinbo Bi

Wed Jul 21 05:45 AM -- 05:50 AM (PDT) @ None

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.

Author Information

Chunjiang Zhu (University of North Carolina Greensboro)
Qinqing Liu (University of Connecticut)
Jinbo Bi (University of Connecticut)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors