GSPBOX: A toolbox for signal processing on graphs

Toolbox organization

In this document, we briefly describe the different modules available in the toolbox. For each of them, the main functions are briefly described. This chapter should help making the connection between the theoretical concepts introduced in [shuman2013emerging, shuman2013vertex, shuman2013multiscale] and the technical documentation provided with the toolbox. We highly recommend to read this document and the tutorial before using the toolbox. The documentation, the tutorials and other resources are available on-line See https://lts2.epfl.ch/gsp/doc/ for MATLAB and https://lts2.epfl.ch/pygsp for Python. The full documentation is also available in a single document: https://lts2.epfl.ch/gsp/gspbox.pdf.

The toolbox has first been implemented in MATLAB but a port to Python, called the PyGSP, has been made recently. As of the time of writing of this document, not all the functionalities have been ported to Python, but the main modules are already available. In the following, functions prefixed by [M]: refer to the MATLAB implementation and the ones prefixed with [P]: refer to the Python implementation.

The general design of the GSPBox focuses around the graph object [shuman2013emerging], a MATLAB structure containing the necessary informations to use most of the algorithms. By default, only a few attributes are available (see section 2), allowing only the use of a subset of functions. In order to enable the use of more algorithms, additional fields can be added to the graph structure. For example, the following line will compute the graph Fourier basis enabling exact filtering operations.

Ideally, this operation should be done on the fly when exact filtering is required. Unfortunately, the lack of well defined class paradigm in MATLAB makes it too complicated to be implemented. Luckily, the above formulation prevents any unnecessary data copy of the data contained in the structure G. In order to avoid name conflicts, all functions in the GSPBox start with [M]: gsp_. A second important convention is that all functions applying a graph algorithm on a graph signal takes the graph as first argument. For example, the graph Fourier transform of the vector f is computed by

The graph operators are described in section . Filtering a signal on a graph is also a linear operation. However, since the design of special filters (kernels) is important, they are regrouped in a dedicated module (see section ).

The toolbox contains two additional important modules. The optimization module contains proximal operators, projections and solvers compatible with the UNLocBoX [perraudin2014unlocbox] (see section ). These functions facilitate the definition of convex optimization problems using graphs. Finally, section is composed of well known graph machine learning algorithms.

2 General structure of the toolbox (Python)

The structure of the Python toolbox follows closely the MATLAB one. The major difference comes from the fact that the Python implementation is object-oriented and thus allows for a natural use of instances of the graph object.

For example the equivalent of the MATLAB call:

can be achieved using a simple method call on the graph object:

Moreover, the use of class for the "graph object" allows to compute additional graph attributes on the fly, making the code clearer as its MATLAB equivalent. Note though that functionalities are grouped into different modules (one per section below) and that several functions that work on graphs have to be called directly from the modules. For example, one should write:

This is the case as soon as the graph is the structure on which the action has to be performed and not our principal focus.

In a similar way to the MATLAB implementation using the UNLocBoX for the convex optimization routines, the Python implementation uses the PyUNLocBoX, which is the Python port of the UNLocBoX.

Graphs

The GSPBox is constructed around one main object: the graph. It is implemented as a structure in Matlab and as a class in Python. It stores the nodes, the edges and other attributes related to the graph. In the implementation, a graph is fully defined by the weight matrix $\mathbf{W}$, which is the main and only required attribute. Since most graph structures are far from fully connected, $\mathbf{W}$ is implemented as a sparse matrix. From the weight matrix a Laplacian matrix $\mathcal{L}$ is computed and stored as an attribute of the graph object. Different other attributes are available such as plotting attributes, vertex coordinates, the degree matrix, the number of vertices and edges. The list of all attributes is given in table .