GRASS: GRAph Spectral Sparsifier (Academic Version )

Author:

Zhuo Feng (zhuo.feng at stevens dot edu)

Stevens Institute of Technology & 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.

Our recent work (DAC'16, DAC'18, TCAD'20) introduces GRASS to allow extracting ultra-sparse subgraphs that can well mimic the original graph by approximately preserving the original Laplacian eigenvalues and eigenvectors. Our latest work SF-GRASS (ICCAD'20) introduces a more scalable solver-free spectral sparsification framework. The extracted subgraphs (running GRASS with a relative condition number K) will have the following desired properties:

• The effective-resistance distance on the subgraph will be no greater than K times the original resistance distance. So spectrally-similar subgraphs well preserve the original resistance distances.

• A spectrally-similar subgraph is a low-stretch subgraph or t-spanner graph (with t=K) of the original graph.

• Any cut in the original graph will be no greater than K times the cut in the subgraph. So spectrally-similar subgraphs well preserve the original cuts.

• The sparsified Laplacian can be used as a preconditioner (the relative condition number is K) for iteratively solving the original Laplacian, as shown in our recent work (ICCAD'17, TCAD'20, TCAD'21).

• Our latest work introduces a practically-efficient algorithm for spectral sparsification of directed graphs leveraging a spectrum-preserving Laplacian symmetrization scheme (arXiv:1812.04165).

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, #1618364 and #1909105

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, in Proceedings of ACM/IEEE Design Automation Conference (DAC), June, 2018.

[3] Zhiqiang Zhao, Zhuo Feng, Effective-Resistance Preserving Spectral Reduction of Graphs, in Proceedings of ACM/IEEE Design Automation Conference (DAC), June, 2019.

[4] Zhuo Feng, GRASS: Graph Spectral Sparsification Leveraging Scalable Spectral Perturbation Analysis, Zhuo Feng, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020.

Last updated in May 2022. Copyright by Zhuo Feng.