Bipartite subgraph decomposition for critically sampled wavelet filterbanks on arbitrary graphs

Abstract

The observation of frequency folding in graph spectrum during down-sampling for signals on bipartite graphs-analogous to the same phenomenon in Fourier domain for regularly sampled signals-has led to the development of critically sampled wavelet filterbanks such as GraphBior. However, typical graph-signals live on general graphs that are not necessarily bipartite. To decompose a non-bipartite graph into a series of bipartite subgraphs so that two-channel filterbanks can be applied iteratively, we propose a new algorithm based on two criteria easily computed in the vertex domain aiming at compact signal representation in the wavelet domain. Given that filterbanks have minimal frequency discrimination at 1, the first criterion aims to minimize the multiplicity of mid graph frequency 1. The second criterion aims to preserve the edge structure of the original graph, which may reflect correlations among signal samples, so that a signal projected on approximated bipartite subgraphs can nonetheless be well represented using low frequency components. Experimental results show that our proposed bipartite subgraph decomposition outperforms competing proposals in terms of energy compaction.