bwdeng20 / thgsp Goto Github PK

A graph signal processing toolbox built on pytorch. The repository now mainly consists of the following stuffs:

1. GFT-based filter(banks) processing multi-dimensional signals in a Multiple Input Multiple Output(MIMO) manner.
2. GraphQmf and GraphBiorth wavelet filter bank.
3. Many strategies to decompose an arbitrary graph into many(usually <10) bipartite graphs.
4. Many graph signal sampling(which differs slightly with general graph sampling) and reconstruction algorithms.

As this package is built on PyTorch and pytorch_sparse, you can easily integrate functionalities from thgsp into a PyTorch pipeline. Check the document for installation and introduction.

• Example
• Reference
• Citation

The Minnesota traffic network is 3-colorable(exactly) or 4-colorable(roughly). Hence 4-channel GraphQmf filterbank is constructed, requiring a ceil(log2(4))=2 level bipartite decomposition. The bipartite graphs are below.

The comparision between the eventual reconstructed signal and the input one.

See the full program here.

[David K Hammond, et al.] Wavelets on Graphs via Spectral Graph Theory
[Sunil K. Narang, et al.] Compact Support Biorthogonal Wavelet Filterbanks for Arbitrary Undirected Graphs
[Sunil K. Narang, et al.] Perfect Reconstruction Two-Channel Wavelet Filter Banks for Graph Structured Data
[Akie Sakiyama, et al.] Oversampled Graph Laplacian Matrix for Graph Filter Banks
[Jing Zen, et al.] Bipartite Subgraph Decomposition for Critically Sampledwavelet Filterbanks on Arbitrary Graphs
[Aamir Anis, et al.] Towards a Sampling Theorem for Signals on Arbitrary Graphs
[Aimin Jiang, et al.] Admm-based Bipartite Graph Approximation
[Yuanchao Bai, et al.] Fast graph sampling set selection using Gershgorin disc alignment, IEEE TSP, 2020
[G. Puy, et al.] Random sampling of bandlimited signals on graphs, ACHA, 2018.
[A. Sakiyama, et al.] Eigendecomposition-free sampling set selection for graph signals，IEEE TSP, 2020.
[Aamir Anis et al.] Efficient sampling set selection for bandlimited graph signals using graph spectral proxies, IEEE TSP, 2016.

@misc{thgsp,
  author = {Bowen Deng},
  title = {ThGSP: A PyTorch-based Graph Signal Processing Library},
  year = {2021},
  publisher = {GitHub},
  journal = {GitHub repository},
  howpublished = {\url{https://github.com/bwdeng20/thgsp}},
}