Source-linked AI summary
Compact Support Biorthogonal Wavelet Filterbanks for Arbitrary Undirected Graphs
Sunil K. Narang, Antonio Ortega
TL;DR
The paper addresses wavelet transforms that are invertible and compactly supported, extending graph-wavelet filterbanks to critically sampled representations with compactly supported basis functions. The resulting filterbanks are reported as useful for arbitrary graphs and standard signal-processing applications.
Problem
The paper focuses on designing wavelet transforms that are invertible and compactly supported.
Method
The paper extends a filterbank approach to design graph wavelets with compactly supported basis functions and two filterbank flavors: nonzeroDC and another unspecified flavor.
Results
The filterbanks provide a critically sampled representation, with the total number of outputs across channels equal to the total number of input samples.
Takeaways & Limitations
Preliminary results indicate that the filterbanks are useful for arbitrary graphs and standard signal-processing applications.
Abstract
from arXiv · showhide
In our recent work, we proposed the design of perfect reconstruction orthogonal wavelet filterbanks, called graph- QMF, for arbitrary undirected weighted graphs. In that formulation we first designed "one-dimensional" two-channel filterbanks on bipartite graphs, and then extended them to "multi-dimensional" separable two-channel filterbanks for arbitrary graphs via a bipartite subgraph decomposition. We specifically designed wavelet filters based on the spectral decomposition of the graph, and stated necessary and sufficient conditions for a two-channel graph filter-bank on bipartite graphs to provide aliasing-cancellation, perfect reconstruction and orthogonal set of basis (orthogonality). While, the exact graph-QMF designs satisfy all the above conditions, they are not exactly k-hop localized on the graph. In this paper, we relax the condition of orthogonality to design a biorthogonal pair of graph-wavelets that can have compact spatial spread and still satisfy the perfect reconstruction conditions. The design is analogous to the standard Cohen-Daubechies-Feauveau's (CDF) construction of factorizing a maximally-flat Daubechies half-band filter. Preliminary results demonstrate that the proposed filterbanks can be useful for both standard signal processing applications as well as for signals defined on arbitrary graphs. Note: Code examples from this paper are available at http://biron.usc.edu/wiki/index.php/Graph Filterbanks
EDICS Category: DSP-WAVL, DSP-BANK, DSP-MULT, DSP-APPL, MLT
The paper designs graph-wavelet filterbanks that combine critical sampling, perfect reconstruction, and compact vertex-domain support for signals on arbitrary graphs. By relaxing orthogonality, the graphBior construction controls the trade-off between vertex and spectral localization while retaining perfect reconstruction.
- Motivation: Graph-wavelet methods address multiresolution analysis of signals attached to nodes in large, high-dimensional datasets and networks.Graph representations support local processing around nodes and can produce smaller graphs with smooth approximations of the original signals.
- Motivation: The paper targets wavelet transforms that are invertible, compactly supported on the graph, and critically sampled.Critical sampling keeps the number of generated coefficients equal to the number of graph vertices, supporting compact representations and graph reduction.
- Motivation: Filters are designed spectrally while guaranteeing compact vertex-domain support, allowing explicit control of the vertex–spectral localization trade-off.The framework extends bipartite two-channel filterbanks to arbitrary graphs through bipartite approximations or link-disjoint bipartite subgraph decompositions.
- Motivation: Earlier graph-QMF filters achieved aliasing cancellation, perfect reconstruction, and orthogonality, but lacked compact graph support.Polynomial approximation could improve localization, but introduced reconstruction error and loss of orthogonality.
- Motivation: The proposed graphBior filters relax orthogonality to obtain exactly k-hop-localized graph wavelets that still satisfy perfect reconstruction.The construction is analogous to the CDF factorization of maximally-flat half-band filters.
- Motivation: The designs include nonzeroDC and zeroDC graphBior variants, and the biorthogonal filterbanks can be designed to nearly preserve energy using Riesz bounds.The zeroDC variant has zero highpass response for constant graph-signals, while nonzeroDC associates DC with degree-dependent signals.
II. PRELIMINARIES
The preliminaries define graph structure, graph signals, localization, and graph filters. They characterize spatial spread through impulse responses and relate polynomial spectral responses to exact k-hop localization.
- Graph definitions: The paper considers undirected graphs without self-loops or multiple links, with positive link weights and geodesic distance based on shortest-path weight sums.The graph size is N = |V|, and disconnected node pairs have infinite distance.
- Graph signals and transforms: A graph-signal assigns scalar values to graph vertices, while a graph-based transform is a linear map applied in the vertex domain.The transform output at a node combines the signal there with values from nearby nodes.
- Graph signals and transforms: Because graph links are irregular, a graph filter’s impulse response can vary across vertices.Each row of the transform is treated as the impulse response at one node.
- Localization: Spatial localization means concentrating each impulse response’s energy in a local region around its associated node.The paper measures transform spatial spread by averaging the spatial spread of impulse responses over graph nodes.
- Localization: A signal’s spatial spread is defined from a probability-mass interpretation of squared signal coefficients and the variance of geodesic distance.Small spread values for all impulse responses indicate good spatial localization.
B. Graph spectral domain
The paper represents graph signals and filters in a Laplacian spectral domain, using eigenvalues, eigenvectors, and eigenspace projections. Polynomial spectral responses provide controllable K-hop localization and reduce filtering complexity.
- Laplacian spectral representation: The symmetric normalized Laplacian is used to define the graph spectral domain and its eigenstructure.Its eigenvectors form an orthonormal basis, with nonnegative eigenvalues ordered from λ0 through λN−1; the graph is assumed connected.
- Laplacian spectral representation: A graph signal is represented by projections onto Laplacian eigenvectors, while eigenspaces collect eigenvectors associated with each eigenvalue.Eigenspace projection matrices are idempotent, mutually orthogonal for distinct eigenvalues, and sum to the identity.
- Laplacian spectral representation: The random-walk Laplacian Lr is used to design zeroDC filterbanks and has the same eigenvalues as the symmetric Laplacian L.If ul is an eigenvector of L for λl, then D−1ul is an eigenvector of Lr for the same eigenvalue.
- Localization and complexity: The paper uses heuristic spectral spread measures to illustrate a trade-off between spatial and spectral localization.For nonregular graphs, the chosen Laplacian can affect spectral-spread results, and disconnected components are analyzed separately.
- Localization and complexity: Polynomial spectral responses of degree K yield exactly K-hop-localized graph filters with O(K|E|) filtering complexity.They can be computed iteratively using K one-hop operations per node without diagonalizing the Laplacian; K also represents the spectral-filter length.
- Spectral graph filters: Spectral graph filters apply eigenvalue-dependent kernels to the corresponding eigenspace components of an input signal.The filtered output expands as a sum of kernel-weighted projections, so the spectral response determines which harmonic components are attenuated or enhanced.
D. Spectral wavelet filterbanks
The two-channel graph filterbank operates on bipartite graphs through spectral filtering and critically sampled downsampling/upsampling. Bipartite spectral folding enables analysis of aliasing, while biorthogonal designs target perfect reconstruction with compact support.
- Bipartite graph filterbanks: A bipartite graph partitions vertices into disjoint sets L and H, with every link connecting the two sets.This partition supports the two-channel lowpass and highpass graph-signal flows.
- Bipartite graph filterbanks: The analysis bank filters the input with H0 in the lowpass channel and H1 in the highpass channel before DU operations.The synthesis side uses corresponding graph transforms Gi, while the channels represent approximation and detail components.
- Downsampling and upsampling: DU operations retain lowpass coefficients on L and highpass coefficients on H, producing critical sampling because the sets are complementary.The operation is represented by 1/2(I + Jβ) for lowpass and 1/2(I − Jβ) for highpass, with Jβ = diag{β}.
- Spectral folding: Multiplication by Jβ maps the eigenspace at λ to the eigenspace at 2 − λ, folding the spectrum across λ = 1.This spectral folding phenomenon underlies the aliasing behavior of bipartite graph filterbanks.
- Perfect reconstruction: Perfect reconstruction is characterized by necessary and sufficient spectral conditions on the analysis and synthesis filters.These conditions can be designed as continuous spectral kernels over λ ∈ [0,2], making the design independent of graph structure.
- Compact biorthogonal designs: Exact graph-QMF solutions are perfect-reconstruction and orthogonal but lack compact support, motivating biorthogonal PR solutions with compact support.Polynomial approximation can localize exact filters, but introduces reconstruction error and loss of orthogonality that decrease with approximation degree.
III. NONZERODC GRAPHBIOR FILTERBANKS
The section constructs compactly supported nonzeroDC graphBior filterbanks by designing a maximally flat polynomial half-band kernel and factorizing it into complementary analysis and synthesis kernels.
- Filterbank construction: The design targets k-hop localized filters satisfying perfect reconstruction conditions through polynomial spectral kernels and spectral factorization.The half-band kernel is designed first, followed by analysis and synthesis kernel construction.
- Filterbank construction: The four polynomial kernels comprise lowpass and highpass analysis and synthesis filters, with highpass kernels derived from the lowpass pair.The highpass kernels are obtained using the specified relation after designing the lowpass analysis and synthesis kernels.
- Half-band design: Perfect reconstruction requires the half-band polynomial to satisfy the stated complementary relation over λ ∈ [0,2].Equivalently, the transformed kernel must satisfy the corresponding relation for l ∈ [−1,1].
- Half-band design: The maximally flat construction assigns K roots at λ = 0 and chooses the shortest polynomial satisfying the half-band condition.The resulting transformed polynomial has K roots at l = −1 and includes a residual polynomial factor.
- Polynomial constraints: Increasing K produces a spectral response that better approximates the ideal half-band filter.The construction therefore trades polynomial degree against approximation quality.
B. Spectral factorization of half-band kernel ˆp(λ)
The half-band kernel is factored into real polynomial analysis and synthesis kernels, with root assignments selected to preserve perfect reconstruction while approaching orthogonality.
- Root factorization: Complex roots of the real polynomial kernel are assigned in conjugate pairs to either the analysis or synthesis lowpass kernel.This preserves real coefficients for both factors.
- Root factorization: Any such factorization yields a perfect-reconstruction biorthogonal filterbank, but the design favors factorizations that are as close to orthogonal as possible.Near-orthogonality is treated as a separate optimization criterion after perfect reconstruction is ensured.
- Orthogonality criterion: Near-orthogonality is measured using the Riesz bounds of the overall analysis transform, requiring lower and upper bounds A and B close to 1.The bounds are computed from the minimum and maximum singular values of the analysis transform.
- Orthogonality criterion: The orthogonality measure Θ equals 1 for orthogonal filterbanks, and the selected factorization maximizes Θ among candidates with least dissimilar filter lengths.The criterion depends on the graph’s eigenvalue distribution.
- Graph-independent design: For graph-independent designs, the relevant spectral quantities are approximated using extrema and 100 uniformly sampled points over [0,2].These approximations are then used to compute Θ.
C. Unity gain compensation
Unity-gain compensation normalizes graphBior filters because biorthogonal designs do not inherit the automatic unity gain of orthogonal graph-QMF filters.
- Implementation: A gain-compensation block is applied after filtering and downsampling, with its inverse applied before filtering and upsampling.This placement preserves perfect reconstruction.
- Gain normalization: GraphBior filters may not have unity gain, unlike graph-QMF filters whose orthogonality condition ensures unity gain.The normalization follows specifications analogous to those used in JPEG2000.
- Gain normalization: The lowpass filter is normalized at λ = 0 and the highpass filter at λ = 2, corresponding to DC and Nyquist frequencies on bipartite graphs.The gain factor is based on the reciprocal magnitude of the kernel response at the relevant endpoint.
D. Nomenclature and design of graphBior filterbanks
The paper defines graphBior filterbanks through root and degree parameters, extends them to zeroDC designs using the random-walk Laplacian, and characterizes their reconstruction and basis properties.
- Nomenclature and design: graphBior(k0, k1) uses k0 and k1 to specify lowpass analysis and synthesis roots at λ = 0, while l0 and l1 specify their degrees.The highpass kernels are computed from the lowpass kernels.
- Nomenclature and design: The product p̂(λ)=ĥ0(λ)ĝ0(λ) has K=k0+k1 roots at λ=0 and degree 2K−1, then is factorized with l0=K and l1=K−1.Θ selects among possible factorizations, yielding a unique biorthogonal design.
- Nomenclature and design: Designs with k0=k1 are close to orthogonal and have near-flat pass-band responses.Their lowpass and highpass analysis kernels are illustrated in Figure 4 and tabulated in Table II.
- ZeroDC extension: ZeroDC graphBior filters use the random-walk Laplacian instead of the normalized Laplacian, while retaining the spectral-kernel design.The two Laplacians are similar and have identical eigenvalues.
- ZeroDC extension: For connected graphs, a kernel with ĥ(0)=0 produces a transform with zero DC response.The corresponding random-walk-Laplacian transform annihilates the constant signal.
- ZeroDC properties: ZeroDC graphBior filterbanks retain perfect reconstruction and form a Riesz basis with bounds related to those of the corresponding nonzeroDC bank.For irregular graphs, their orthogonality measure is reduced by the factor dmin/dmax.
- Choice of DC formulation: For physical-domain graphs, zeroDC filterbanks preserve nearly constant signals and perform better than nonzeroDC filterbanks in the reported examples.Highly irregular graphs may instead favor degree-normalized nonzeroDC designs.
V. MULTI-DIMENSIONAL AND MULTI-RESOLUTION IMPLEMENTATIONS
The paper extends graphBior filterbanks from bipartite graphs to arbitrary graphs through bipartite subgraph decompositions, enabling separable multi-dimensional and multiresolution implementations.
- Arbitrary-graph extension: Arbitrary graphs are decomposed into link-disjoint bipartite subgraphs, with filtering and downsampling restricted to one bipartite graph per stage.The subgraphs’ union covers almost all graph links, and the number of stages follows the decomposition.
- Two-dimensional decomposition: A two-dimensional decomposition divides the graph into LL, LH, HL, and HH clusters and constructs successive bipartite subgraphs from their connecting links.Links used for the first bipartite graph are removed before constructing the second.
- Separable implementation: Each dimension consists of filtering and downsampling on a single bipartite subgraph, analogous to separable filtering across dimensions in regular multidimensional signals.The resulting two-dimensional graphBior filterbank is represented by the block diagram in Figure 6.
- Perfect reconstruction: Separable graphBior filterbanks provide perfect reconstruction for any arbitrary partitions LL, LH, HL, and HH induced on the graph.The choice of decomposition can prioritize preservation of structure in highly structured graphs or other criteria for arbitrary graphs.
- Decomposition criteria: For arbitrary graphs, decomposition criteria include minimizing the number of bipartite subgraphs or maximizing disjointness of node neighborhoods across subgraphs.Harary’s algorithm gives a ⌈log2K⌉-subgraph decomposition for a K-colorable graph.
- Multiresolution implementation: Multiresolution analysis repeatedly treats the L-set output as the next-resolution signal, reconnecting its vertices into a coarsened graph.Any of the described graph-coarsening schemes can be used to compute the graph at the next level while preserving selected graph properties.
VI. EXPERIMENTS
Experiments compare graphBior and graph-QMF filterbanks on random bipartite graphs, showing a trade-off between localization, compact support, reconstruction, and orthogonality.
- Localization trade-off: Graph-QMF filters based on ideal half-band kernels have very small spectral spread but very large spatial spread because of their brick-wall spectral response.Meyer-kernel graph-QMF filters reduce spatial spread while retaining higher spatial spread than other designs.
- Localization trade-off: Proposed graphBior filterbanks exploit the spatial/spectral trade-off better and have compact support.Shorter filters are more spatially localized but less spectrally localized than longer filters.
- Design comparison: ZeroDC graphBior filterbanks perform slightly worse than nonzeroDC designs because additional normalizations enforce zero DC response.The comparison concerns the localization experiment on random bipartite graphs.
- Comparison with graph-QMF: Exact graph-QMF filters provide perfect reconstruction but lack compact support, whereas polynomial approximations gain localization at the cost of reconstruction error.The approximation error can be reduced by increasing polynomial degree.
- Reconstruction and orthogonality: All graphBior designs provide perfect reconstruction with reconstruction SNR > 100dB on the tested random bipartite graphs.The graph-QMF filters are closer to orthogonal, with Θ almost 1, but have considerably lower reconstruction SNR.
B. Graph based image processing
Graph-based image filterbanks add directional and edge-aware processing to standard separable transforms, improving reconstruction quality while retaining comparable computational complexity.
- Graph image representation: Images are represented as graphs by treating pixels as nodes, intensities as signals, and neighboring pixels as connected vertices.An 8-connected image graph supplies horizontal, vertical, and diagonal relationships.
- Directional filtering: GraphBior filterbanks on decomposed 8-connected image graphs provide diagonal and rectangular filtering directions, unlike standard separable filters’ rectangular directions.The added directions are available at the same order of computational complexity.
- Edge-aware processing: Edge-aware graph representations remove links across strong intensity changes, preventing filtering across image edges.Canny edge detection is used to identify edges, with small connected components removed before graph construction.
- Compression implications: The paper notes that edge-aware compression requires sending an edge map to the decoder, although related work reports overall transmission reductions despite that overhead.The edge-map overhead is therefore a practical consideration for compression applications.
- Reconstruction quality: Edge-aware graphBior reconstruction gives the best reported image quality and preserves edge structure because filtering operations do not cross disconnected edges.The comparison uses all lowpass coefficients and 3% highpass coefficients after four decomposition levels.
- Limitations: NonzeroDC graphBior filterbanks produce significant ringing artifacts near boundaries and edges, while suitable graph signal extensions remain an open issue.The limitation parallels boundary artifacts encountered with standard image filterbanks.
- Reconstruction quality: ZeroDC graphBior filterbanks outperform standard CDF 9/7 filters by up to 2dB in PSNR as the fraction of detail coefficients varies.The comparison uses PSNR and SSIM for reconstructions of coins.png.
C. Compression and Learning on arbitrary graphs
The paper applies graphBior filterbanks to critically sampled analysis and compression of signals on arbitrary graphs, including the Minnesota traffic graph.
- Arbitrary-graph applications: The proposed filterbanks are intended for analyzing and compressing signals defined on arbitrary graphs.The Minnesota traffic graph serves as a proof-of-concept application.
- Minnesota traffic graph: Harary’s decomposition represents the perfectly 3-colorable Minnesota traffic graph using ⌈log2(3)⌉ = 2 bipartite subgraphs.A two-dimensional graphBior filterbank with filter length 10 is then implemented.
- Critically sampled representation: The LL channel provides a smooth approximation on a subset of nodes, while the remaining channels contain details required for perfect reconstruction.The four-channel output is critically sampled because the total output count equals the input sample count.
- Compression: For the piecewise-constant graph signal, zeroDC graphBior filterbanks provide a sparser approximation than nonzeroDC designs.Using all lowpass coefficients and 1% of highpass coefficients yields better SNR with zeroDC filters.
- Conclusions: The filterbanks provide critically sampled representations with compactly supported basis functions in two variants: nonzeroDC and zeroDC.NonzeroDC filters use polynomials of the normalized graph Laplacian, while zeroDC filters extend them to impose zero highpass response at DC.
- Conclusions: Preliminary results indicate usefulness in both arbitrary-graph and standard regular signal-processing domains.The paper identifies applications such as social-network and sensor-network analysis as future scenarios.