Spectral Vertex Sparsifiers and Pair-Wise Spanners Over Distributed Graphs

Abstract.

Graph sparsification is a powerful tool in approximating an arbitrary graph and has been used in machine learning over graphs. As real-world networks are becoming very large and usually naturally distributed, distributed graph sparsification has received considerable interests. In this work, we give communication-efficient distributed algorithms for constructing spectral vertex sparsifiers, which approximately preserve effective resistance distances on a subset of vertices of interest in the original graphs, under two well-established communication models namely the message passing and the blackboard models. We further prove that the communication costs are close to their lower bounds with a small gap. We also provide algorithms for constructing pair-wise spanners which approximate shortest distances only for some pairs of vertices, instead of all pairs, and incur communication costs much smaller than existing algorithms in the message passing model. We perform experiments to validate the communication efficiency of the proposed algorithms while guaranteeing the constructed sparsifiers have a good approximation quality.

Click here to download the software package.

Guideline to run the experiments:
1. Run Demo_GenData_hpc.m, to get the graph
2. Run grid_settings.m, to get the Graph, Shur_Complement in each site, and the original SC.
3. Run sparsify_settings.jl, to get the approximation quality.
4. For experiment results visualization, please refer to create*figure*.m files

This is an open source program for non-commercial use only. Please contact either Dr. Jinbo Bi (jinbo.bi@uconn.edu) or Chunjiang Zhu (chunjiang.zhu@uconn.edu) for on-going progress.

Contact Jinbo Bi (jinbo.bi@uconn.edu) for information about this page.