Python functionality for recovering graph signals from subsampled measurements.
Currently maintained by Rodrigo C. G. Pena.
The installation guide below contains instructions for setting up your environment to use the tools in the repository.
A graph is a collection of vertices and edges. The latter can be weighted, often indicating the degree of similarity between the connected vertices.
Any numerical quantities attached to the vertices of a graph can be considered as a graph signal. For example, in a social network with
Querying each vertex for its signal value can be expensive in large networks, meaning one can usually afford to measure these values only at a few selected locations. This is called subsampling and is, mathematically, a linear operation. Let
To recover
This repository contains utilities to conveniently load graphs and signals, and implement sampling designs and decoders.
graphs_signals.py
: Functions related to loading and representing graphs and their signals. See thedata/
folder in this repository for information on the relevant datasets. You need to follow the instructions therein to download the required files for working with each dataset.sampling.py
: Functions related to vertex sampling designs.recovery.py
: Functions related to recovery programs (decoders).phase_transition.py
: Functions related to the phase transition experiments commonly done in Compressed Sensing. They allow one to observe how the recovery error varies with a set of parameters (normally the number of measurements).plotting.py
: Functions related to plotting of graphs and signals.utils.py
: A miscellaneous collection of helper functions.
Remark: You can also click the binder badge below to run the included notebooks from your browser without installing anything.
For a local installation, you will need git, python >= 3.6, jupyter, and packages from the python scientific stack. I recommend using conda for creating and managing a separate environment for this repository. If unfamiliar with this process, you can follow the instructions below.
- Download the Python 3.x Miniconda installer and run it using default settings (another option is to download the bulkier Anaconda installer).
- Open a terminal window and install git with
conda install git
. - Within the terminal, navigate to the directory where you want to keep the contents from this repository (e.g., run
cd ~/Documents/github/
). - Download this repository to the current directory by typing
git clone https://github.com/rodrigo-pena/gssr
on the terminal. - Create a new environment by typing
conda create --name gssr
on the terminal. - Activate the environment with
conda activate gssr
(oractivate gssr
, orsource activate gssr
). - You should notice
gssr
typed somewhere on the newest terminal line, indicating that you are within the environment. Install the required packages by runningconda install -c conda-forge python=3.6 jupyterlab
and thenpip install -r requirements.txt
. - Run
python test_install.py
to check if all the requirements have been correctly installed.
After the (one-time) creation of the environment, you can do the following every time you want to work with this repository:
- Open a terminal and navigate to the directory where the repository has been downloaded.
- Activate the environment with
conda activate gssr
(oractivate gssr
, orsource activate gssr
). - Start Jupyter with
jupyter lab
. The command should open a new tab in your web browser. - Edit and run the scripts and notebooks from your browser.
You can check standard_pipeline.ipynb
for a basic idea of how to use the function modules in the repository.
The contents of this repository benefitted from the following resources:
- PyGSP.
- PyUNLocBoX.
- Voting patterns in the Swiss National Council.
- Finding Continents from a Flight Routes Network.
The content is released under the terms of the MIT License.
If you are using this software for your research, for the sake of reproducibility, please cite the version you used as indexed by its Zenodo record. Alternatively, you may cite it generically as
@software{gssr,
author = {Rodrigo C. G. Pena},
title = {Graph Signal Sampling and Recovery (GSSR)},
publisher = {Zenodo},
doi = {10.5281/zenodo.6566207},
url = {https://github.com/rodrigo-pena/gssr}
}