Source-linked AI summary
GSPBOX: A toolbox for signal processing on graphs
Nathanaël Perraudin, Johan Paratte, David Shuman, Lionel Martin, Vassilis Kalofolias, Pierre Vandergheynst, David K. Hammond
TL;DR
GSPBox provides a signal-processing framework for graph-related problems and connects theoretical concepts with technical documentation. It organizes the toolbox around graph objects and describes modules for visualization, operators, filters, and optimization.
Problem
GSPBox addresses the need for a framework and documentation connecting graph signal processing concepts with practical software for graph-related problems.
Method
The toolbox uses a central graph object defined by a sparse weight matrix and provides modules for plotting, spectral operators, filters, and convex optimization.
Results
The document describes the toolbox organization, core graph representation, and functions supporting graph visualization, signal processing, filtering, and predefined optimization problems.
Takeaways & Limitations
Readers can use the document and tutorials to connect theoretical graph signal processing concepts with the toolbox's technical functions and modules.
Abstract
from arXiv · showhide
This document introduces the Graph Signal Processing Toolbox (GSPBox) a framework that can be used to tackle graph related problems with a signal processing approach. It explains the structure and the organization of this software. It also contains a general description of the important modules.
1 Toolbox organization
GSPBox organizes graph signal processing around graph objects and modular MATLAB/Python implementations. Its modules cover operators, filters, optimization, and graph machine learning, with language-specific conventions and documentation.
- Documentation: The documentation and tutorials connect the toolbox modules with the theoretical concepts underlying graph signal processing.The authors recommend reading both before using the toolbox.
- Python implementation: The Python port, PyGSP, provides the main modules but had not yet ported all MATLAB functionality at the time of writing.Its object-oriented graph implementation permits method calls and on-the-fly computation of additional graph attributes.
- Core organization: GSPBox uses a graph object to store data and attributes required by most algorithms.Additional fields can be added when algorithms require them, such as exact filtering.
- MATLAB conventions: MATLAB functions use the gsp_ prefix and take the graph as the first argument when applying graph algorithms to graph signals.The graph Fourier transform of f is computed through gsp_gft(G,f).
- Modules: The toolbox separates graph operators, filters, optimization routines, and graph machine learning into dedicated modules.Filters receive their own module because specialized filter kernels are important; optimization routines support convex graph problems through UNLocBoX-compatible tools.
2 Graphs
The graph is GSPBox’s central data structure, defined primarily by a sparse weight matrix and enriched with Laplacian and other attributes. The toolbox supports standard, random, nearest-neighbor, point-cloud, and image-patch graphs.
- Graph representation: The graph object stores nodes, edges, and attributes, with the weight matrix W as its only required attribute.Because most graphs are not fully connected, W is implemented as a sparse matrix.
- Graph representation: The toolbox computes and stores a Laplacian from W, alongside attributes such as coordinates, degree information, and vertex and edge counts.The complete attribute list appears in Table 1.
- Graph construction: Graph creation initializes the Laplacian and other attributes, while alternative Laplacian definitions can be selected explicitly.The Laplacian definition should be chosen first because nearly all functions depend on it.
- Graph families: Helper functions construct deterministic examples, random graphs, nearest-neighbor graphs, 3D point-cloud graphs, and image patch-graphs.Nearest-neighbor construction supports large point sets through FLANN, while patch graphs can vary from local to non-local.
- Examples: Figure 1 displays examples of two-moons, community, airfoil, and sensor-network graphs.These examples illustrate several graph families supported by the toolbox.
3 Plotting
GSPBox provides visualization helpers for graphs, graph signals, and spectral filters. These routines support graph display, color- or bar-coded signal values, and filter-bank inspection, with results shown in Figures 1 and 2.
- Graph visualization: Graphs can be plotted with gsp_plot_graph or pygsp.plotting.plot_graph when 2D or 3D coordinates are available.Some graphs, such as Erdos-Renyi graphs, do not have default coordinates.
- Signal visualization: Graph signals can be plotted with gsp_plot_signal or pygsp.plotting.plot_signal, currently supporting only 1D signals.Signal values are color-coded by default, with bars available through parameters.
- Figures: Figure 1 shows classical graph examples including two moons, community, airfoil, and sensor-network graphs.Use the panel positions to identify the four graph examples.
- Filter visualization: Spectral filters can be plotted with gsp_plot_filter or pygsp.plotting.plot_filter.The routine also supports filter-banks and automatic inspection of their associated frames.
- Figures: The outputs of the three plotting functions are shown in Figure 2.The figure brings together graph, signal, and filter visualization results.
4 Operators
The operators module provides spectral graph functions built around attributes stored in the graph object, including Fourier transforms, localization, gradients, divergence, and pyramid decomposition.
- The operators module contains spectral graph functions for Fourier transforms, localization, gradients, divergence, and pyramid decomposition.
- The graph object stores the attributes needed by most algorithms, including those underlying operator computations.
- Graph Fourier transforms require a Fourier basis, while gradient and divergence require an edge-matrix representation.These underlying objects can be computed once; Python computes them automatically when needed and stores the results as graph attributes.
- The Multi-scale Pyramid Transform precomputes a graph pyramid before analyzing and synthesizing graph signals.
- The Laplacian is stored as a sparse matrix in the graph object's L field, with multiple definitions summarized in Table 2.
5 Filters
The filters module represents graph filters as element-wise anonymous or lambda functions, provides predefined designs and filter banks, and applies accelerated algorithms to graph signals.
- Filters are linear operators represented as anonymous functions in MATLAB or lambda functions in Python, and filter banks gather these functions together.
- The toolbox applies filters through gsp_filter_analysis in MATLAB or the analysis method of a Python filter object.
- Accelerated filtering algorithms scale almost linearly with the number of samples.
- Predefined filter designs include wavelets, Gabor filters, low-pass filters, and high-pass/low-pass separation filter banks.The separation filter bank is described as a tight frame that loses no energy.
- The WarpedTranslates design adapts filters to the graph eigen-distribution.
6 UNLocBoX Binding
The UNLocBoX binding provides wrappers for solving convex optimization problems containing graph terms and includes predefined graph signal-processing problems.
- The optimization module wraps UNLocBoX to solve convex problems containing graph terms.
- It provides a proximal operator for the graph total-variation norm and predefined solvers for graph basis pursuit and wavelet denoising.
- The optimization module remains under active development and is expected to expand in future toolbox releases.
7 Toolbox conventions
The toolbox conventions standardize naming, argument order, data organization, module structure, matrix operations, and plotting-library support across MATLAB and Python implementations.
- Vectors use lowercase letters and matrices use uppercase letters whenever possible.Nearest-neighbor graph creation is noted as an exception.
- The toolbox avoids global variables and variable names that conflict with existing MATLAB or Python functions.These conventions are intended to improve readability, reduce errors, simplify debugging, and support parallelization.
- Function names are lowercase, begin with gsp_, and describe the performed action rather than an algorithm or inventor.
- Graph algorithms receive the graph as the first argument, filters as the second, and optional parameters last.Optional arguments are generally stored in a graph structure named param.
- Matrix transforms operate along columns by default, while matrix operations use NumPy and SciPy when porting MATLAB code to Python.
- Python functionality is organized into modules, with no direct calls from pygsp, and plotting supports matplotlib and pyqtgraph.When both plotting libraries are installed, pyqtgraph is preferred unless explicitly overridden.