GRASS: GRAph Spectral Sparsifier (Download)

Zhuo Feng

Michigan Technological University

Spectral drawings of the original and the sparsified graphs

GRASS: GRAph Spectral Sparsifier (Academic Version )

Author:

Zhuo Feng (zhuofeng at mtu dot edu)

Michigan Technological University & LeapLinear Solutions

Latest News (January 20, 2018):

An iterative edge weight scaling function and a testing function for comparing effective resistances in the original graph and the sparsifier have been added to GRASS. Now it allows us to keep much fewer edges for approximating the effective resistances, as well as the first few Laplacian eigenvalues and eigenvectors. For example, the 200X200 2D mesh only needs 0.02|V| off-tree edges to be added to the spanning tree to well preserve the first 30 smallest eigenvalues.

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 social (data) networks may allow for more efficiently modeling, mining and analysis of large social (data) networks, sparsified neural networks allow for more scalable model training and processing in emerging machine learning tasks, 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 ] input Laplacian matrix file (market format: *.mtx)

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

-t [ --testPCG ] test Preconditioned CG solver

-s [ --edgeSca ] spectral edge scaling iterations

-c [ --condNum ] arg (=100) 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: GRASS will only load the lower triangular off-diagonal entries A(i,j) (with i>j) of the input matrix and build the entire Laplacian matrix (lower+upper+diagonal components) based on the loaded lower matrix; if the input matrix is not a Laplacian, the program will convert the lower triangular off-diagonal entries 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, unit weight (weight=1) will be adopted 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 budget value will be set based on the desired relative condition number.

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

3) Using option "-t" will leverage the PCG solver (using sparsifier as the preconditioner) to compute the effective resistances between randomly picked nodes and compare to the approximate ones computed by directly solving the graph sparsifier.

4) Using option "-s" will iteratively scale up edge weights in the sparsified graph to more accurately match the eigenvectors and effective resistances.

Outputs:

The output matrices include the original and sparsified Laplacian matrices "Gmat.mtx" and "Pmat.mtx". GRASS also reports the final estimated eig_max, eig_min and relative condition number (eig_max/eig_min). If the edge scaling function is chosen, the cost function value of each gradient descent step is also printed into a file "cost_vec.m".

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] Zhuo Feng, Similarity-Aware Spectral Sparsification by Edge Filtering, arXiv:1711.05135, November, 2017.

Last updated in January 2018. Copyright by Zhuo Feng.