GRASS: GRAph Spectral Sparsifier (Download)

Zhuo Feng

Michigan Technological University

Spectral drawings of the original and the sparsified graphs

The spectrum-preserving graph sparsification framework [2]

GRASS: GRAph Spectral Sparsifier (Academic Version )

Author:

Zhuo Feng (zhuofeng at mtu dot edu)

Michigan Technological University & LeapLinear Solutions

September 5th, 2017

Introduction:

Spectral graph sparsification aims to find an ultra-sparse subgraph that can well preserve the original graph Laplacian eigenvalues and eigenvectors. The spectrally sparsified graph can approximately preserve the distances or effective resistances between vertices so that much faster numerical and graph-related algorithms can be developed based on these sparsified graphs. For example, spectrally sparsified transportation networks may enable developing much faster navigation (routing) algorithms in large transportation systems, spectrally sparsified social (data) networks may allow for more efficiently modeling, mining and analysis of large social (data) networks, spectrally sparsified circuit networks may lead to more efficient simulation, optimization and verification of large integrated circuit systems, etc.

Executable: GRASS (Download link)

GRASS is a highly efficient graph spectral sparsification engine that scales almost linearly with the size of the input graph Laplacian. GRASS has been compiled using gcc version 4.8.5 under Red Hat Enterprise Linux Workstation release 7.2.

Usage:

You can use -h for help message. For example: "./grass -h" gives you the following message

Options:

-h [ --help ] help screen

-m [ --matrix ] arg input Laplacian matrix file (market format: *.mtx)

-b [ --budget ] arg (=1) desired budget (>=0.02) for adding off-tree edges

-t [ --testPCG ] test Preconditioned CG solver

-c [ --condNum ] arg (=50) desired relative condition number (10<condNum<1000) after sparsification

To run the program, you may pass the following input parameters to GRASS:

1) an input graph Laplacian matrix in market format (mtx file)

2) a desired off-tree edge budget (optional)

3) a desired relative condition number for adding off-tree edges (optional)

Note: if the input matrix is not a Laplacian, the program will convert the lower triangular off-diagonal entries A(i,j) (with i>j) into the corresponding entries of a graph Laplacian by setting the edge weight as |A(i,j)|, while the Laplacian diagonal entries will be created according to the edge weights. If no edge weights have been provided in the matrix file, we will use unit weight (weight=1) for all edges.

Optional parameters for graph spectral sparsification are also allowed:

1) Using option "-b 0.1" will add no more than 10% |V| off-tree edges to the initial spanning forest, where |V| is the number of nodes. If no parameter is given by the user, a default value of "-b 1" is used.

2) Using option "-c 100" will stop adding off-tree edges if a relative condition number of 100 is reached, which is based on estimated generalized eigenvalues (relative condition number) [3]. If no parameter is given by the user, a default value of "-c 50" is used.

3) Using option "-t" will test the PCG solver using sparsifier as a preconditioner.

Outputs:

The output matrices include the original and sparsified Laplacian (w/o edge scaling) matrices "Gmat.mtx" and "Pmat.mtx". GRASS also reports the final estimated eig_max, eig_min and relative condition number (eig_max/eig_min).

Extras:

The Matlab code for drawing graphs based on the output Laplacian matrices also has been provided. It allows spectral graph drawing of the original and sparsified graph Laplacians using their first two or three non-trivial eigenvectors as coordinates (e.g. x, y, and z coordinates). The spectral graph drawing function here will only work for connected graphs. Another option that uses the Matlab internal drawing function is also offered.

Three sample input Laplacian matrices (2D mesh, airfoil and 10-nearest-neighbor USPS graphs) have been included as well.

Acknowledgements:

PhD students: Xueqian Zhao, Lengfei Han, Zhiqiang Zhao, Yongyu Wang

NSF CCF CAREER grant #1350206, NSF CCF grants #1318694 and #1618364

Reference:

[1] Zhuo Feng, Spectral Graph Sparsification in Nearly-Linear Time Leveraging Efficient Spectral Perturbation Analysis, in Proceedings of ACM/IEEE Design Automation Conference (DAC), June, 2016.

[2] Yongyu Wang and Zhuo Feng, Towards Scalable Spectral Clustering via Spectrum-Preserving Sparsification, arXiv:1710.04584, October, 2017.

[3] Zhuo Feng, Similarity-Aware Spectral Sparsification by Edge Filtering, arXiv:1711.05135, November, 2017.

Last updated in September 2017. Copyright by Zhuo Feng.