The Graph Signal Processing Toolbox

You thought signal processing on graphs was hard?

View the code

Go to function

GSP_DEMO - Tutorial on the GSPBox

Description

In this demo, we are going to show the basic operations of the GSPBox. To lauch the toolbox, just go into the repository where the GSPBox was extracted and type:

gsp_start;

A banner will popup telling you that everything happens correctly. To speedup some processing, you might want to compile some mexfile. Refer to gsp_make for more informations. However, if the compilation is not working on your computer, keep quiet, everything should still work and most of the routine are implemented only in matlab.

Most likely, the first thing you would like to do is to create a graph. To do so, you only need the adjacendy or the weight matrix \(W\). Once you have it, you can construct a graph using:

G = gsp_graph(W);

This function will create a full structure ready to be used with the toolbox. To know a bit more about what is in this structure, you can refer to the help of the function gsp_graph_default_parameters.

The GSPBox contains also a list of graph generators. To see a full list of these graphs, type:

help graphs

This code produces the following output:

GSPBOX - Graphs

   Specific graphs
     gsp_swiss_roll              -  Create swiss roll graph
     gsp_david_sensor_network    -  Create the sensor newtwork from david
     gsp_ring                    -  Create the ring graph
     gsp_path                    -  Create the path graph
     gsp_airfoil                 -  Create the airfoil graph
     gsp_comet                   -  Create the comet graph
     gsp_erdos_renyi             -  Create a erdos renyi graph
     gsp_minnesota               -  Create Minnesota road graph
     gsp_low_stretch_tree        -  Create a low stretch tree graph
     gsp_sensor                  -  Create a random sensor graph
     gsp_random_regular          -  Create a random regular graph
     gsp_random_ring             -  Create a random ring graph
     gsp_full_connected          -  Create a fully connected graph
     gsp_nn_graph                -  Create a nearest neighbors graph
     gsp_rmse_mv_graph           -  Create a nearest neighbors graph with missing values
     gsp_sphere                  -  Create a spherical-shaped graph
     gsp_cube                    -  Create a cubical-shaped graph
     gsp_2dgrid                  -  Create a 2d-grid graph
     gsp_torus                   -  Create a torus graph
     gsp_logo                    -  Create a GSP logo graph
     gsp_community               -  Create a community graph
     gsp_bunny                   -  Create a bunny graph
     gsp_spiral                  -  Create a spiral graph
     gsp_stochastic_block_graph  -  Create a graph with the stochastic block model

   Hypergraphs
     gsp_nn_hypergraph           -  Create an hyper nearest neighbor graph
     gsp_hypergraph              -  Create an hypergraph

   Utils
     gsp_graph_default_parameters-  Initialise all parameters for a graph
     gsp_graph_default_plotting_parameters-  Initialise all plotting parameters for a graph
     gsp_graph                   -  Create a graph from a weight matrix
     gsp_update_weights          -  Update the weights of a graph
     gsp_update_coordinates      -  Update the coordinate of a graph
     gsp_components              -  Cuts non connected graph into several connected ones
     gsp_subgraph                -  Create a subgraph
     gsp_graph_product           -  Compute graph product between two graphs
     gsp_line_graph              -  Create the Line Graph (or edge-to-vertex dual graph) of a graph
     gsp_jtv_graph               -  Add time information to the graph structure


   For help, bug reports, suggestions etc. please send email to
   gspbox 'dash' support 'at' groupes 'dot' epfl 'dot' ch

For this demo, we will use the graph gsp_logo. You can load it using:

G = gsp_logo

This code produces the following output:

G =

             W: [1130x1130 double]
        coords: [1130x2 double]
          info: [1x1 struct]
      plotting: [1x1 struct]
        limits: [0 640 -400 0]
             A: [1130x1130 logical]
             N: 1130
          type: 'unknown'
      directed: 0
    hypergraph: 0
      lap_type: 'combinatorial'
             L: [1130x1130 double]
             d: [1130x1 double]
            Ne: 3131

Here observe the attribute of the structure G.

  • G.W: Weight matrix
  • G.A: Adacency matrix
  • G.N: Number of nodes
  • G.type: Type of graph
  • G.directed: 1 if the graph is directed, 0 if not
  • G.lap_type: Laplacian type
  • G.d: Degree vector
  • G.Ne: Number of edges
  • G.coords: Coordinates of the vertices
  • G.plotting: Plotting parameters

In the folder 'plotting', the GSPBox contains some plotting routine. For instance, we can plot a graph using:

gsp_plot_graph(G);
gsp_demo_1.png

GSP graph

This figure shows the result of the command 'gsp_plot_graph(G)'

Wonderful! Isn't it? Now, let us start to analyse this graph. To compute graph Fourier transform or exact graph filtering, you need to precompute the Fourier basis of the graph. This operation could be relatively long since it involves a full diagonalization of the Laplacian. Don't worry, you do not need to perform this operation to filter signals on graph. The fourier basis is computed by:

G = gsp_compute_fourier_basis(G);

The function gsp_compute_fourier_basis add two new fields to the structure G:

  • G.U: The eigenvectors of the Fourier basis
  • G.e: The eigenvalues

The fourier eigenvectors does look like a sinusoide on the graph. Let's plot the second and the third ones. (The first one is constant!):

gsp_plot_signal(G,G.U(:,2));
title('Second eigenvector')
subplot(212)
gsp_plot_signal(G,G.U(:,3));
title('Third eigenvector')
gsp_demo_2.png

Eigenvectors

Now, we are going to show a basic filtering operation. Filters are usually defined in the spectral domain. To define the following filter

\begin{equation*} h(x) =\frac{1}{1+\tau x}, \end{equation*}

just write in Matlab:

tau = 1;
h = @(x) 1./(1+tau*x);

Hint: You can define filterbank using cell array!

Let's display this filter:

gsp_plot_filter(G,h);
gsp_demo_3.png

Low pass filter \(h\)

The filter \(h\) is plotted along all the spectrum of the graph. The black cross are the eigenvalues of the Laplacian. They are the points where the continuous filter will be evaluated to create a discrete filter.

To apply the filter to a given signal, you only need to run a single function:

% Create a signal
f = zeros(G.N,1);
f(G.info.idx_g) = -1;
f(G.info.idx_s) = 1;
f(G.info.idx_p) = -0.5;
f = f + 0.3*randn(G.N,1);
% Remove the noise
f2 = gsp_filter(G,h,f);

gsp_filter is actually a shortcut to gsp_filter_analysis. gsp_filter_analysis performs the analysis operator associated to a filterbank. See the gsp_demo_wavelet for more information.

Finnaly, we display the result of this low pass filtering on the graph:

figure;
subplot(211)
gsp_plot_signal(G,f);
title('Signal with noise')
subplot(212)
gsp_plot_signal(G,f2);
title('Signal denoised');
gsp_demo_4.png

Result of filtering

The noise is largely removed thanks to the filter. However, some energy is diffused between the letters. This is the typical behaviour of a low pass filter.

Enjoy the GSPBOX !