  We propose novel two-channel filter banks for signals on graphs. Our designs
can be applied to arbitrary graphs, given a positive semi definite variation
operator, while using arbitrary vertex partitions for downsampling. The
proposed generalized filter banks (GFBs) also satisfy several desirable
properties including perfect reconstruction and critical sampling, while having
efficient implementations. Our results generalize previous approaches that were
only valid for the normalized Laplacian of bipartite graphs. Our approach is
based on novel graph Fourier transforms (GFTs) given by the generalized
eigenvectors of the variation operator. These GFTs are orthogonal in an
alternative inner product space which depends on the downsampling and variation
operators. Our key theoretical contribution is showing that the spectral
folding property of the normalized Laplacian of bipartite graphs, at the core
of bipartite filter bank theory, can be generalized for the proposed GFT if the
inner product matrix is chosen properly. In addition, we study vertex domain
and spectral domain properties of GFBs and illustrate their probabilistic
interpretation using Gaussian graphical models. While GFBs can be defined given
any choice of a vertex partition for downsampling, we propose an algorithm to
optimize these partitions with a criterion that favors balanced partitions with
large graph cuts, which are shown to lead to efficient and stable GFB
implementations. Our numerical experiments show that partition-optimized GFBs
can be implemented efficiently on 3D point clouds with hundreds of thousands of
points (nodes), while also improving the color signal representation quality
over competing state-of-the-art approaches.
