GraphQmf Wavelet Filterbank

We introduce the usage of graphQmf wavelet filterbank in thgsp here.

Note

For a thorough understanding of this note. You are supposed to have already understand GraphQmf and GraphBiorth wavelet filterbanks. However, if you care about how to use it, that’s not necessary and remember that they are just filterbanks which define critically-sampling wavelet transform. Besides, code blocks in this note are all pieces of one whole.

Read and Plot Minnesota

The minnesota traffic network is a classic network pervasive in graph signal processing community. It has 2642 nodes and 3304 undirected edges, with a chromatic number of 3, meaning that it can be colored with 3 colors such that no same color are assigned to adjacent nodes. You can easily access to the minnesota graph from thgsp.

from thgsp.datasets import Minnesota
from thgsp.filters import ColorQmf
from thgsp.alg import dsatur
from thgsp.visual import draw_signal, draw_cn, draw
import matplotlib.pyplot as plt
data=Minnesota(download=True,connected=True)
minne=data[0]
print(minne)

GraphQmf 1 and GraphBiorth 2 filter bank require bipartite decomposition of the original graph into edge-disjoint bipartite subgraphs on each of which one GraphQmf filterbank is constructed. All contructed GraphQmfs are then stacked as a whole to perform multi-dimensional separable wavelet analysis. The vanilla GraphQmf and GraphBiorth get the bipartite subgraphs in terms of the graph coloring result. Though in those papers a \(O(n^3)\) exact coloring is employed, many experiments show that inaccurate greedy coloring is not likely to decrease the performance, i.e., the reconstruction SNR. Therefore, we color the minnesota graph with the classic dsatur algorithm.

Note

thgsp.filters.ColorQmf and thgsp.filters.ColorBiorth have already been integrated with dsatur algorithm, meaning that a graph coloring is invoked silently during the initialization of them. However, you can also initialize them with pre-computed coloring result to skip it. Here we firstly color the graph explicitly for a convenient visualization of coloring result.

# ==> continue the last code block
colors = dsatur(minne)
fig,axes= plt.subplots(1,2, figsize=(2 * 7, 6))
draw(minne, minne.coords, ax=axes[0],node_size=30,with_labels=False)
axes[0].set_title("the traffic network",fontsize='large', fontweight='bold')
draw_cn(minne, minne.coords ,colors, ax=axes[1], node_size=30,with_labels=False)
axes[1].set_title("coloring of Minnesota(chromatic={})".format(str(colors.max()+1)), fontsize='large', fontweight='bold')
plt.show()

You can see the figure below.

Wavelet Transform via GraphQmf

This section we initialize a : thgsp.filters.ColorQmf and evaluate the wavelet transform determined by it on a signal used in the original paper.

# ===> continue the last code block
K=30              # the order of Chebyshev approximation
qmf = ColorQmf(minne, order=K, vtx_color=colors)
f = data.f                                     # (2642,) The signal
wc= qmf.analyze(f)                             # analyze,            i.e., wavelet transform
f4_hat= qmf.synthesize(wc)                     # synthesize,         i.e., inverse transform
f_hat=f4_hat.sum(0).squeeze()                  # (4,2642,1)--> (2642,1) --> (2642)

Note

Though GraphQmf wavelet filterbank determines a critically graph wavelet transform, 4x2642 floats is needed to store these coefficients other than 2642 floats. Such memory waste arises from the computation scheme adopted by the authors 1 and us.

Evaluation

To evaluate the construction performance, SNR and MSE are taken into account. The next block will print them.

# ===> continue the last code block
from thgsp.utils import snr, mse
MSE = mse(f_hat, f).item()
SNR = snr(f_hat, f).item()
print("==============================> SUMMARY <=========================================")
print(f"|Mean Square Error :  {MSE:.3e}")
print(f"|Reconstruction SNR: {SNR: .3f}")

dis = (f_hat - f).abs()
print(f"|Max distortion    :  {dis.max().item():.3e} at {dis.argmax():4d}-th node")
print(f"|Min distortion    :  {dis.min().item():.3e} at {dis.argmin():4d}-th node")
print("==============================> SUMMARY <=========================================")

Let’s draw the input and reconstructed signal and check the difference between them.

# ===> continue the last code block
max_val = max(f.max(), f_hat.max())
min_val = min(f.min(), f_hat.min())
plt.figure(figsize=(2*7, 6))
plt.suptitle("Order: {}, SNR: {:3f}dB, MSE: {:3e}".format(K, SNR, MSE), fontsize='x-large', fontweight='bold')

ax1 = plt.subplot(121)
plt.title("input signal", fontsize='large', fontweight='bold')
draw_signal(minne, minne.coords, f, ax= ax1, cmap='jet', vmin=min_val, vmax=max_val,node_size=30, )

ax2 = plt.subplot(122)
plt.title("reconstructed signal", fontsize='large', fontweight='bold')
draw_signal(minne, minne.coords, f_hat, ax2, 'jet', vmin=min_val, vmax=max_val, node_size=30)
plt.show()

In addition to the default coloring-based bipartite approximation strategy 1, there are OSGLM 3, MFS 4, and ADMM-BGA 5 strategies to transform the original arbitrary undirected graph into bipartite one(s). You can use them by passing corresponding strategy str to thgsp.filters.ColorQmf and thgsp.filters.NumQmf.

1(1,2,3)

Sunil K. Narang, et al, Perfect Reconstruction Two-Channel Wavelet Filter Banks for Graph Structured Data, 2012.

2

Sunil K. Narang, et al, Compact Support Biorthogonal Wavelet Filterbanks for Arbitrary Undirected Graphs, 2013.

3

Akie Sakiyama, et al, Oversampled Graph Laplacian Matrix for Graph Filter Banks, 2014.

4

Jin Zeng, et al, Bipartite subgraph decomposition for critically sampled wavelet filterbanks on arbitrary graphs, 2016.

5

Aimin Jiang, et al, ADMM-BASED BIPARTITE GRAPH APPROXIMATION, 2019.