gasper

Graph signal processing in R.

Download and Install

Install the devtools package if you haven’t already.

install.packages("devtools")

To install the development package, type the following at the R command line:

devtools::install_github("fabnavarro/gasper")
library(gasper)

To install the CRAN version of the package, type the following:

install.packages("gasper")

To obtain the complete list of package functions, simply type

help(package = "gasper")

Getting Started

See the package vignette or documentation for more details. You could also build and see the vignette associated with the package using the following lines of code

devtools::install_github("fabnavarro/gasper", build_vignettes = TRUE)
library(gasper)

Then, to view the vignette

vignette("gasper_vignette")

For an illustration of the features of the package, you can also refer to the following repo SGWT-SURE which provides an effective generalization of the Stein Unbiased Risk Estimate (SURE) for signal denoising/regression on graphs using Spectral Graph Wavelet Transform.

Interface to the SuiteSparse Matrix Collection

The package also provides an interface to the SuiteSparse Matrix Collection, which is a large and actively growing set of sparse matrix benchmarks gathered from a broad spectrum of applications (for details see https://sparse.tamu.edu/).

Included in the package, the SuiteSparseData dataset contains data from the SuiteSparse Matrix Collection. The structure of this dataframe mirrors the structure presented on the SuiteSparse Matrix Collection website, allowing users to query and explore the dataset directly within R.

Here is a sample of the SuiteSparseData dataset, showing the first 15 rows of the table:

SuiteSparseData_subset <- head(SuiteSparseData, 15)

ID	Name	Group	Rows	Cols	Nonzeros	Kind	Date
1	1138_bus	HB	1138	1138	4054	Power Network Problem	1985
2	494_bus	HB	494	494	1666	Power Network Problem	1985
3	662_bus	HB	662	662	2474	Power Network Problem	1985
4	685_bus	HB	685	685	3249	Power Network Problem	1985
5	abb313	HB	313	176	1557	Least Squares Problem	1974
6	arc130	HB	130	130	1037	Materials Problem	1974
7	ash219	HB	219	85	438	Least Squares Problem	1974
8	ash292	HB	292	292	2208	Least Squares Problem	1974
9	ash331	HB	331	104	662	Least Squares Problem	1974
10	ash608	HB	608	188	1216	Least Squares Problem	1974
11	ash85	HB	85	85	523	Least Squares Problem	1974
12	ash958	HB	958	292	1916	Least Squares Problem	1974
13	bcspwr01	HB	39	39	131	Power Network Problem	1981
14	bcspwr02	HB	49	49	167	Power Network Problem	1981
15	bcspwr03	HB	118	118	476	Power Network Problem	1981

Here’s an example to retrieve all undirected weighted graphs with the number of columns and rows between 50 and 150:

filtered_mat <- SuiteSparseData[SuiteSparseData$Kind == "Undirected Weighted Graph" & 
                                SuiteSparseData$Rows >= 50 & SuiteSparseData$Rows <= 150 &
                                SuiteSparseData$Cols >= 50 & SuiteSparseData$Cols <= 150, ]

	ID	Name	Group	Rows	Cols	Nonzeros	Kind	Date
1506	1506	Journals	Pajek	124	124	12068	Undirected Weighted Graph	2000
1519	1519	Sandi_authors	Pajek	86	86	248	Undirected Weighted Graph	1999
2400	2400	lesmis	Newman	77	77	508	Undirected Weighted Graph	1993
2858	2858	breasttissue_10NN	ML_Graph	106	106	1412	Undirected Weighted Graph	2020
2872	2872	iris_dataset_30NN	ML_Graph	150	150	5518	Undirected Weighted Graph	2020

The download_graph function allows to download a test matrix from this collection. For example:

matrixname <- "usroads-48"
groupname <- "Gleich"
download_graph(matrixname,groupname)
attributes(`usroads-48`)
#> $names
#> [1] "sA"   "xy"   "dim"  "temp"

usroads-48 is composed of the sparse matrix sA (in compressed sparse column format), coordinates xy (if present, in a data.frame), dim the number of rows, columns and numerically nonzero elements and temp path to the temporary directory where the matrix and downloaded files (including singular values if requested) are stored. Information about the matrix can be display via file.show(paste(usroads-48$temp,"usroads-48",sep="")) or in the console:

cat(readLines(paste(`usroads-48`$temp,"usroads-48",sep="")), sep = "\n")
#> %%MatrixMarket matrix coordinate pattern symmetric
#> %-------------------------------------------------------------------------------
#> % UF Sparse Matrix Collection, Tim Davis
#> % http://www.cise.ufl.edu/research/sparse/matrices/Gleich/usroads-48
#> % name: Gleich/usroads-48
#> % [Continental US road network (with xy coordinates)]
#> % id: 2332
#> % date: 2010
#> % author: D. Gleich
#> % ed: T. Davis
#> % fields: name title A id date author ed kind aux
#> % aux: coord
#> % kind: undirected graph
#> %-------------------------------------------------------------------------------
#> 126146 126146 161950

download_graph function has an optional svd argument; setting “svd = TRUE” downloads a “.mat” file containing the singular values of the matrix, if available. To access the temporary folder use, for example,

list.files(`usroads-48`$temp)
#> [1] "usroads-48"           "usroads-48_coord.mtx" "usroads-48.mtx"

In addition, the get_graph_info function allows to retrieve detailed information about the matrix from the SuiteSparse Matrix Collection website (rvest package needs to be installed to use it). This function extracts and formats various properties and metadata associated with the matrix (i.e., it fetches the two to three tables with “MatrixInformation,” “MatrixProperties” and, if available, “SVDStatistics”), providing a convenient way to access this overview of the graph directly within R. Here is how you can use it:

graph_info <- get_graph_info(matrixname, groupname)
graph_info

MatrixInformation Name usroads-48 Group Gleich Matrix ID 2332 Num Rows 126,146 Num Cols 126,146 Nonzeros 323,900 Pattern Entries 323,900 Kind Undirected Graph Symmetric Yes Date 2010 Author D. Gleich Editor T. Davis

MatrixProperties Structural Rank Structural Rank Full Num Dmperm Blocks Strongly Connect Components 1 Num Explicit Zeros 0 Pattern Symmetry 100% Numeric Symmetry 100% Cholesky Candidate no Positive Definite no Type binary

The download_graph function has an optional argument add_info which, when set to TRUE, automatically calls get_graph_info and appends the retrieved information to the output of download_graph. This makes it easy to get both the graph data and its associated information in a single function call.

downloaded_graph <- download_graph(matrixname, groupname, add_info = TRUE)
downloaded_graph$info

It is also possible to plot a (planar) graph and plot signals defined on top of it. For example:

f <- sin(rnorm(nrow(`usroads-48`$xy)))
plot_graph(`usroads-48`, size = 0.05)
plot_signal(`usroads-48`, f, size = f/4)

In cases where these coordinates are not supplied, plot_graph employs simple spectral graph embedding to calculate some node coordinates (nodes that are connected or share structural similarities in the graph are placed close to each other in the spectral drawing). This is done using the function spectral_coords, which computes the spectral coordinates based on the eigenvectors associated with the smallest non-zero eigenvalues of the graph’s Laplacian.

matrixname <- "delaunay_n10"
groupname <- "DIMACS10"
download_graph(matrixname,groupname)
attributes(delaunay_n10)
#> $names
#> [1] "sA"   "dim"  "temp"
plot_graph(delaunay_n10)
plot_signal(delaunay_n10,
            cos(1:nrow(delaunay_n10$sA)))

graph_info <- get_graph_info(matrixname, groupname)
graph_info

SVDStatistics Structural Rank Structural Rank Full Num Dmperm Blocks Strongly Connect Components 1 Num Explicit Zeros 0 Pattern Symmetry 100% Numeric Symmetry 100% Cholesky Candidate no Positive Definite no Type binary

SVD Statistics Matrix Norm 6.293702e+00 Minimum Singular Value 1.875512e-03 Condition Number 3.355724e+03 Rank 1,024 sprank(A)-rank(A) Null Space Dimension 0 Full Numerical Rank? yes