PaperlayerView exact revision on arXiv

Source-linked AI summary

Perfect Reconstruction Two-Channel Wavelet Filter-Banks for Graph Structured Data

Sunil K. Narang, Antonio Ortega

arXiv:1106.3693v3cs.DCcs.SI

TL;DR

Large graphs present computational and technical challenges for efficient local analysis. The paper constructs critically sampled two-channel wavelet filterbanks for graph-signals and provides graph-QMF designs with aliasing cancellation, perfect reconstruction, and orthogonality conditions.

  • Problem

    Large graphs present computational and technical challenges for applying efficient local analysis.

  • Method

    The paper constructs critically sampled two-channel wavelet filterbanks on bipartite graphs and proposes graph-QMF designs.

  • Results

    The proposed graph-QMF solution cancels aliasing, while the filterbanks have stated conditions for aliasing cancellation, perfect reconstruction, and orthogonality.

  • Takeaways & Limitations

    The construction provides critically sampled wavelet filterbanks for analyzing graph-signals on graphs.

Abstract

from arXiv · show

In this work we propose the construction of two-channel wavelet filterbanks for analyzing functions defined on the vertices of any arbitrary finite weighted undirected graph. These graph based functions are referred to as graph-signals as we build a framework in which many concepts from the classical signal processing domain, such as Fourier decomposition, signal filtering and downsampling can be extended to graph domain. Especially, we observe a spectral folding phenomenon in bipartite graphs which occurs during downsampling of these graphs and produces aliasing in graph signals. This property of bipartite graphs, allows us to design critically sampled two-channel filterbanks, and we propose quadrature mirror filters (referred to as graph-QMF) for bipartite graph which cancel aliasing and lead to perfect reconstruction. For arbitrary graphs we present a bipartite subgraph decomposition which produces an edge-disjoint collection of bipartite subgraphs. Graph-QMFs are then constructed on each bipartite subgraph leading to "multi-dimensional" separable wavelet filterbanks on graphs. Our proposed filterbanks are critically sampled and we state necessary and sufficient conditions for orthogonality, aliasing cancellation and perfect reconstruction. The filterbanks are realized by Chebychev polynomial approximations.

EDICS Category: DSP-WAVL, DSP-BANK, DSP-MULT, DSP-APPL, MLT

The paper extends wavelet-filterbank concepts to irregular graph-signals, addressing the lack of regular dimensions and downsampling operations on graphs. It develops critically sampled, invertible two-channel designs using bipartite structure and graph-QMFs.

  • Motivation: Graphs model diverse networked data, but their irregular structure prevents directly applying traditional filtering and downsampling notions.Graph neighborhoods can vary in size, and regular dimensions along which to filter are unavailable.
  • Limitations of Existing Designs: Existing graph filterbanks commonly oversample because their outputs are not downsampled, while lifting-based designs may ignore links within the same vertex partition.Lifting transforms are critically sampled and invertible, but their construction uses only links between the two disjoint vertex sets.
  • Graph Sampling: The paper introduces graph downsample-then-upsample operations and shows that bipartite graphs exhibit spectrum folding at mirror graph-frequencies around a central frequency.The folding phenomenon is analogous to aliasing in regular one-dimensional signals.
  • Graph-QMF Filterbanks: Using spectrum folding, the authors propose critically sampled two-channel filterbanks on bipartite graphs with necessary and sufficient conditions for aliasing cancellation, perfect reconstruction, and orthogonality.The practical graph-QMF design has these stated properties for bipartite graphs.
  • Implementation Trade-off: Polynomial approximations make graph-QMF filters locally supported around each node, but introduce small reconstruction error and loss of orthogonality.The exact graph-QMF realizations do not have well-localized support.
  • Arbitrary Graphs: For arbitrary graphs, an edge-disjoint bipartite subgraph decomposition yields a K-dimensional separable wavelet filterbank by treating each subgraph as a filtering dimension.The subgraphs share the original vertex set and their union is the original graph.

II. PRELIMINARIES

The paper represents graph signals as functions on vertices and analyzes them using graph transforms, Laplacian eigenvectors, and graph-frequency concepts.

  • Graph signals: A graph signal is a real-valued function f:V→R, equivalently a vector whose sample ordering is separate from neighborhood information.Applications include sensor measurements, traffic samples, and social-network information.
  • Graph transforms: Graph transforms are linear maps whose outputs combine a node’s signal value with values from nearby nodes.Strict j-hop localization requires filter coefficients to vanish beyond each node’s j-hop neighborhood.
  • Spectral representation: Because graph Laplacians are symmetric, their orthonormal eigenvectors provide graph-frequency modes and their eigenvalues form the graph spectrum.Every graph signal decomposes into a linear combination of these eigenvectors, while eigenspace projections are orthogonal for distinct eigenvalues.
  • Spectral representation: The graph Fourier transform projects a signal onto Laplacian eigenvectors, preserving energy and distinguishing low-pass from high-pass content by spectral concentration.Small eigenvalues correspond to low-pass modes, while large eigenvalues correspond to high-pass modes.

C. Downsampling in Graphs

Graph downsampling discards samples and reinserts zeros, producing deformed spectral coefficients; bipartite spectral folding provides the aliasing structure needed for critically sampled filterbanks.

  • Graph downsampling: Downsampling selects a vertex subset H and discards signal samples outside H before upsampling reinserts zeros at discarded vertices.The resulting downsample-then-upsample operation is represented by a diagonal matrix JβH.
  • Spectral effect: The GFT of a downsampled-then-upsampled signal combines the original spectral coefficient with a projection onto a deformed eigenvector.This second term is called the deformed spectral coefficient.
  • Bipartite downsampling: In bipartite graphs, the spectrum is symmetric and deformed eigenvectors remain eigenvectors, producing spectral folding at mirror graph-frequencies.This phenomenon forms the basis of the proposed two-channel framework.
  • Two-channel filterbanks: A two-channel graph filterbank separates graph signals into lowpass and highpass components, with filters H_i, G_i and downsampling functions βH and βL.The lowpass filter attenuates high graph-frequencies, while the highpass filter attenuates low graph-frequencies.
  • Critical sampling: Critically sampled outputs assign lowpass and highpass coefficients across complementary vertex sets, so the total number of stored coefficients equals the input size.The condition is |H|+|L|=N.
  • Perfect reconstruction: Perfect reconstruction requires the equivalent transfer function to be a scalar multiple of identity and the aliasing transfer function to vanish.Under these conditions, the two-channel filterbank provides distortion-free reconstruction.

E. Existing Designs

Existing graph wavelet designs are broadly spatial or spectral, but the reviewed approaches have limitations involving oversampling, invertibility, locality guarantees, or graph-edge usage.

  • Design categories: Existing graph wavelet-like filterbanks can be divided into spatial and spectral designs.The paper introduces this division to compare prior constructions and properties.
  • Spatial designs: Spatially localized transforms may be oversampled, producing twice as many outputs as input samples.Some also use binary-link sensor-network graphs or restrict interactions through graph simplification.
  • Spatial designs: Some spatial transforms are not wavelet filters because both transforms have non-zero DC response.This limitation is stated for the transforms discussed in the cited prior work.
  • Spatial designs: Crovella and Kolaczyk’s localized transforms provide multiscale summaries and zero DC response but lack approximation filters and are not generally invertible.Their wavelet functions are localized over scale/location indices and hop rings.
  • Lifting designs: Lifting-based transforms construct critically sampled local two-channel filterbanks by partitioning vertices into even and odd sets with prediction and update steps.A limitation is that simplifying arbitrary graphs to bipartite structure can exclude same-parity edges, resulting in edge losses.

2) Spectral Designs:

Spectral graph wavelet methods use Laplacian-based kernels and can achieve perfect reconstruction, but common constructions are overcomplete; the proposed solution targets critically sampled reconstruction through bipartite structure.

  • Diffusion wavelets: Diffusion wavelets use repeated applications of a diffusion operator to construct localized multiresolution basis functions.Localized basis functions are orthogonalized and downsampled through a local Gram-Schmidt scheme.
  • Diffusion wavelets: The local Gram-Schmidt method produces localized bump-functions but does not guarantee their support size.The resulting diffusion-wavelet basis is overcomplete and lacks a simple representation in the cited discussion.
  • Spectral implementation: Polynomial approximations replace spectral kernels with smooth degree-k polynomials, enabling an approximate transform based on the Laplacian.The paper states that these filters are approximated by polynomial functions.
  • Spectral reconstruction: A multi-channel spectral transform can perfectly reconstruct when the summed squared kernel responses remain positive across the Laplacian spectrum.However, a J-scale decomposition produces (J+1)N coefficients and requires least-square projection for inversion.
  • Proposed direction: The proposed graph-QMF design uses bipartite spectral folding to cancel aliasing and support perfect reconstruction and orthogonal decomposition.For arbitrary graphs, edge-disjoint bipartite subgraphs yield multidimensional separable filterbanks, with a recursive multiresolution implementation.
  • Proposed direction: For arbitrary graphs, bipartite subgraph decomposition produces a disjoint collection whose union is G, allowing a filterbank on each subgraph.The paper notes a trade-off: perfect reconstruction and orthogonality need not be local, while local designs may have approximate reconstruction.

A. Downsampling in bipartite graphs

In bipartite graphs, downsampling pairs each Laplacian eigenvalue λ with a mirror eigenvalue 2−λ, producing spectral folding and aliasing. This property supports perfect-reconstruction filterbank design.

  • A bipartite graph partitions vertices into disjoint sets L and H, with every edge connecting the two sets.
  • The normalized Laplacian spectrum of a bipartite graph is symmetric about 1, with minimum and maximum eigenvalues 0 and 2.
  • This spectral folding phenomenon provides the basis for designing perfect-reconstruction filterbanks on bipartite graphs.
  • Downsampling with βH or βL deforms an eigenvector at λ into an eigenvector at the mirror eigenvalue 2−λ.
  • The output signal contains the average of the original signal and a shifted, aliased version caused by downsampling.

B. Two-Channel Filterbank Conditions for Bipartite Graphs

For bipartite graphs, graph-QMF filters exploit spectral folding to cancel aliasing and characterize perfect reconstruction and orthogonality. Smooth polynomial approximations trade exactness for spatial localization.

  • Filterbank construction: The analysis assigns highpass outputs to H and lowpass outputs to L using complementary signed downsampling functions.
  • Orthogonality: Orthogonality requires the aliasing coefficient Dλ to vanish and the equivalent coefficient Cλ to equal c^2 for every spectral value.
  • Aliasing cancellation: Aliasing is canceled for any choice of h0(λ) by the proposed graph-QMF solution.
  • Perfect reconstruction: Perfect reconstruction and orthogonal decomposition hold when h0(λ)^2 + h0(2−λ)^2 = c^2 for all λ in σ(G), with c ≠ 0.
  • Localization and approximation: Polynomial kernels of degree k are exactly k-hop localized, enabling spatially localized filters at the cost of reconstruction error.
  • Localization and approximation: Meyer wavelet polynomial approximations yield smaller reconstruction errors than ideal-filter approximations, supporting near-perfect localized graph-QMF filters.

D. Multi-dimensional separable wavelet filterbanks for arbitrary graphs

Arbitrary graphs are handled by decomposing their edges into bipartite subgraphs and cascading two-channel graph-QMF stages. Each stage acts on separate vertex subsets, producing multidimensional separable coefficients.

  • Graph decomposition: Because arbitrary graphs need not be bipartite, the method decomposes them into a series of bipartite subgraphs covering the same vertices.
  • Cascaded transform: Filtering proceeds in cascade: each stage uses only the edges of its corresponding bipartite subgraph and stores intermediate results on vertices.
  • Graph decomposition: The decomposition is edge-disjoint, with every graph edge assigned to exactly one bipartite subgraph.
  • Cascaded transform: For two subgraphs, the second-stage filters act independently on B2(L1) and B2(H1), represented by block-diagonal matrices.
  • Separable transform: The two-dimensional analysis transform is the product of the analysis transforms associated with the two bipartite dimensions.
  • Separable transform: With exact graph-QMF filters such as Meyer kernels, each stage is invertible, making the combined transform invertible.

5. The transform function Ta

The transform Ta organizes cascaded channel outputs across disjoint node sets, yielding critical sampling and invertible decompositions under suitable graph partitioning. The decomposition itself is not unique and may be application dependent.

  • Transform structure: The multidimensional transform expands into channel transforms such as THH, THL, TLH, and TLL, each associated with a sequence of bipartite-stage filters.
  • Transform structure: Each channel combines multidimensional filtering with cascaded downsampling functions β2(n) and β1(n).
  • Critical sampling: Each channel output is stored on a mutually disjoint node set, so every node stores exactly one channel output and the filterbank is critically sampled.
  • Generalization: The construction extends recursively to K-dimensional decompositions because later-stage filter matrices commute with earlier downsampling matrices.
  • Approximation: Polynomial approximations of Meyer kernels introduce reconstruction errors in each dimension.
  • Scope: A good bipartite decomposition for an arbitrary graph remains future work and may depend on the application.
  • Scope: Harary’s decomposition produces ⌈log2k⌉ bipartite subgraphs from a k-coloring, but the result depends on color-ordering choices.
  • Scope: Arbitrary edge selections can preserve invertibility, but the resulting transforms are not necessarily critically sampled.

E. Multiresolution decomposition using two-channel filterbanks

The two-channel bipartite filterbank produces lowpass and highpass graph-signal versions that can be recursively decomposed on downsampled graphs. Extending this across multiple bipartite approximations yields multidimensional and K-dimensional separable filterbanks for arbitrary graphs.

  • The lowpass output f̂L is a coarse-resolution signal on L, while the highpass output f̂H stores detail information on H.
  • The decomposition can be recursively applied to lowpass or highpass signals by constructing an appropriate downsampled graph.
  • For bipartite graphs, downsampled graphs GL and GH may differ and need not remain bipartite, requiring either single or multiple bipartite approximations.
  • A single bipartite approximation produces a one-dimensional two-channel filterbank, whereas multiple approximations produce a multidimensional implementation.
  • K-dimensional two-channel filterbanks for arbitrary graphs decompose the signal into 2^K lower-resolution versions.

IV. EXPERIMENTS

The experiments construct graph filterbanks from edge-disjoint bipartite subgraphs and evaluate them on image graphs and irregular graphs. Results show directional filtering, critically sampled decomposition, and localized wavelet details.

  • Graph filterbank construction: Arbitrary graphs are perfectly colored, decomposed into K = ⌈log2(χ)⌉ bipartite subgraphs, and assigned graph-QMF filters using normalized Laplacians.
  • Graph filterbank construction: Chebychev polynomial approximations implement the spectral transforms without explicit eigenspace decompositions.
  • Graph filterbank construction: The approximation order m controls spatial localization and the reconstruction error that can be tolerated.
  • Image-graph experiments: On image graphs, rectangular, vertical, and horizontal bipartite subgraphs produce lowpass responses matching quincunx or factor-of-2 anti-aliasing filters.
  • Image-graph experiments: Diagonal connectivity produces a wider diagonal-direction passband, demonstrating additional directional choices for filtering and downsampling.
  • Image-graph experiments: In the four-channel image transform, LH coefficients concentrate around rectangular edges, while HL coefficients concentrate around diagonal edges.
  • Image-graph experiments: Connectivity-specific filterbanks are better suited to edges aligned with their corresponding rectangular or diagonal links.

C. Graph Filter-banks on Irregular Graphs

For irregular graphs, the method decomposes arbitrary graphs into bipartite subgraphs and applies graph-QMF filterbanks. Experiments on the Minnesota graph show critically sampled approximation and detail channels supporting reconstruction.

  • Minnesota graph: The Minnesota graph is 3-colorable and decomposed into ⌈log2(3)⌉ = 2 bipartite subgraphs.
  • Minnesota graph: A separable two-dimensional graph-QMF filterbank with m = 6 is applied to the decomposed Minnesota graph.
  • Minnesota graph: Because the graph has three colors, the HL channel is empty and only three channels are non-empty: LL, LH, and HH.
  • Minnesota graph: The transform is critically sampled because downsampling makes the total number of output coefficients equal the number of input samples.
  • Minnesota graph: The LL channel provides a smooth approximation with blurred sharp boundaries, while the remaining channels contain detail needed for perfect reconstruction.
  • General construction: The construction targets graph-signals on arbitrary finite weighted graphs using an edge-disjoint collection of bipartite subgraphs.
  • General construction: The graph-QMF design provides conditions for aliasing cancellation, perfect reconstruction, and orthogonality, with filters realized by Chebychev approximations.
  • Limitations: The authors identify small reconstruction error and loss of orthogonality as limitations motivating alternatives to the proposed graph-QMF design.
Loading 1106.3693v3…