Multi-dimensional separable critically sampled wavelet filterbanks on arbitrary graphs

In our previous work, we observed an “aliasing” phenomenon for functions defined on bipartite graphs which is analogous to aliasing occurring in the downsampling of regular 1-dimensional signals. We exploited these concepts to design critically sampled two-channel wavelet filterbanks for any bipartite graph. For arbitrary graphs, we proposed a bipartite subgraph decomposition scheme to decompose the graph into edge-disjoint bipartite subgraphs and apply filtering and downsampling separately on each subgraph. This leads to the design of multi-dimensional separable filterbanks on graphs. In this paper, we study these bipartite decompositions in more detail. In particular, we describe the meaning of dimensionality in the subgraph decomposition of arbitrary graphs and define some graph based metrics based on this understanding. Subsequently, we propose a heuristics based algorithm for bipartite subgraph decomposition and compare it with other non-optimized algorithms. The results show both qualitative and quantitative improvements in the decomposed bipartite subgraphs with the proposed heuristics.