A Multiscale Pyramid Transform for Graph Signals

David I Shuman; Mohammad Javad Faraji; Pierre Vandergheynst

Source-linked AI summary

A Multiscale Pyramid Transform for Graph Signals

David I Shuman, Mohammad Javad Faraji, Pierre Vandergheynst

arXiv:1308.4942v3Aug 22, 2013cs.ITcs.SImath.FA

TL;DR

Euclidean multiscale transforms do not directly capture the geometry of weighted graph domains. The paper adapts the Laplacian pyramid through graph downsampling, reduction, filtering, and interpolation, producing graph and signal multiresolutions while leaving the interplay of these operations for further study.

Problem
Multiscale transforms for signals and images cannot be directly applied to high-dimensional signals on weighted graphs because they do not capture the graph domain’s intrinsic topology.
Method
The paper builds a modular graph Laplacian-pyramid framework around graph downsampling, graph reduction, spectral filtering, and signal interpolation.
Results
The resulting transform yields both a multiresolution of the graph and a multiscale analysis of a signal on the associated sequence of graphs.
Takeaways & Limitations
The modular framework allows different choices of the four fundamental operations to be substituted when constructing graph multiscale transforms.
Takeaways & Limitations
The interplay among the four operations and its effects on dictionary localization and coefficient sparsity remain insufficiently understood.

Abstract

from arXiv · show

Multiscale transforms designed to process analog and discrete-time signals and images cannot be directly applied to analyze high-dimensional data residing on the vertices of a weighted graph, as they do not capture the intrinsic geometric structure of the underlying graph data domain. In this paper, we adapt the Laplacian pyramid transform for signals on Euclidean domains so that it can be used to analyze high-dimensional data residing on the vertices of a weighted graph. Our approach is to study existing methods and develop new methods for the four fundamental operations of graph downsampling, graph reduction, and filtering and interpolation of signals on graphs. Equipped with appropriate notions of these operations, we leverage the basic multiscale constructs and intuitions from classical signal processing to generate a transform that yields both a multiresolution of graphs and an associated multiresolution of a graph signal on the underlying sequence of graphs.

I. INTRODUCTION

Classical multiscale transforms do not directly capture the topology of weighted graph domains, motivating graph-specific operations and a Laplacian-pyramid framework. The paper develops vertex selection by the largest Laplacian eigenvector and combines graph downsampling, reduction, filtering, and interpolation for graph signals.

Multiscale transforms reveal signal structure across resolutions and can reduce processing complexity, but Euclidean-domain methods do not capture weighted-graph topology.
The paper presents a modular framework adapting Burt and Adelson’s Laplacian pyramid to graph signals.
Its four fundamental graph operations are downsampling, reduction, spectral filtering, and interpolation.
The downsampling operator aims to remove approximately half the vertices, avoid high-weight edges within either partition, and remain computationally efficient.
The proposed downsampling keeps vertices according to the polarity of the graph Laplacian’s largest eigenvector.

B. Special Case: Bipartite Graphs

For connected bipartite graphs, the largest Laplacian eigenvector separates the two bipartition sets, giving a principled graph analogue of removing every other sample. This reproduces familiar patterns on paths, rings, grids, and trees.

Bipartite graphs naturally split into two vertex sets with every edge crossing between them, making one-set retention a graph analogue of downsampling.
For connected bipartite graphs, the largest Laplacian eigenvector is simple, and its polarity separates the graph into the two bipartition sets.
For k-regular bipartite graphs, the largest Laplacian eigenvalue equals 2k.
The method removes every other vertex on paths and even rings and produces quincunx sampling on finite grids, with or without boundary connections.
On trees, largest-eigenvector polarity groups vertices by the parity of their depth from a chosen root, generalizing downsampling by alternating tree levels.

D. Connections with Nodal Domain Theory

The downsampling objective connects sign-based partitioning to nodal-domain maximization, approximate coloring, and spectral structure. The paper also frames graph reduction through multiple desired properties, including connectivity, spectral, structural, invertibility, and sparsity considerations.

D. Connections with Nodal Domain Theory: Assigning positive signs to kept vertices and negative signs to eliminated vertices links downsampling to maximizing nodal domains and reducing within-set edges.
D. Connections with Nodal Domain Theory: The largest Laplacian eigenvector has the maximum possible number of nodal domains exactly when the graph is bipartite.
D. Connections with Nodal Domain Theory: For arbitrary graphs, the largest eigenvector is not guaranteed to have more nodal domains than other eigenvectors.
D. Connections with Nodal Domain Theory: Approximate coloring seeks a partition with few same-set edges, and the paper relates this objective to spectral clustering and alternative downsampling methods.
Graph reduction is expected to preserve Laplacian structure and connectivity while representing spectra, structural properties, correspondences, invertibility, computational efficiency, and sparsity to varying degrees.

A. Kron Reduction

Kron reduction forms a graph on selected vertices by taking the Schur complement of the original Laplacian. For undirected weighted graphs, it preserves key Laplacian and connectivity properties while modifying the retained graph’s edge structure and weights.

A. Kron Reduction: Kron reduction starts with a weighted graph Laplacian and a selected vertex subset, then forms a reduced graph on that subset using a Schur complement.
B. Properties of Kron Reduction: The reduced matrix is well-defined and remains a graph Laplacian.
B. Properties of Kron Reduction: If the original graph is connected, its Kron-reduced graph is also connected.
B. Properties of Kron Reduction: Two retained vertices are adjacent after reduction exactly when a path between them exists through the eliminated vertices and the two retained endpoints.
B. Properties of Kron Reduction: Kron reduction can increase connectivity among retained vertices; for a tree, siblings become connected and the reduced graph becomes a union of complete subgraphs.

C. Special Cases

The paper examines how Kron reduction behaves on structured graph families, showing useful closure and connectivity patterns alongside losses of regularity and sparsity.

Path graphs: Kron reduction preserves the path-graph class under largest-eigenvector vertex selection, and unit edge weights remain unit weights.The sequential selection and reduction operations map a path graph to another path graph.
Ring graphs: Kron reduction maps a ring graph to a ring with half as many vertices, while halving its edge weights.This behavior is illustrated by the reduction of the ring in Figure 3(b).
Finite grids: For finite grids, reduction can produce an 8-connected-grid subgraph from a 4-connected grid.The stated mapping applies to the combined largest-eigenvector selection and Kron reduction operations.
Trees: For trees, Kron reduction is generally not a tree; it forms a union of complete subgraphs with weights determined by their sizes.With unit original weights, each complete subgraph has edge weights equal to one divided by its number of vertices.
Limitations: Kron reduction may fail to preserve regular structure and graph sparsity, motivating a sparsity-enhancing modification.The paper identifies both properties as weaknesses of Kron reduction for these graph classes.

5) k-Regular Bipartite Graphs:

For regular bipartite graphs, the paper relates Kron reduction to an existing common-neighbor reduction, while noting that repeated reductions can densify graphs and require sparsification.

Prior reduction: The prior method constructs reduced edges between retained vertices using the number of their common neighbors in the original graph.Its setting is connected, unweighted k-regular bipartite graphs, with an extension noted for weighted graphs.
k-regular bipartite graphs: Kron reduction generalizes the graph reduction method of Narang and Ortega for regular bipartite graphs up to a constant factor.The comparison is made between the Kron-reduced Laplacian and the reduced Laplacian from the prior method.
Sparsity: Repeated Kron reduction often produces progressively denser graphs, which can increase computational cost and weaken local-connectivity representation.The paper therefore recommends sparsification immediately after Kron reduction in many situations.
Sparsification: Spectral sparsification approximately preserves graph-Laplacian spectra and resistance distances with high probability for large graphs and suitable sample counts.The paper uses the Spielman–Srivastava algorithm and illustrates repeated reduction followed by sparsification.

E. Alternative Graph Reduction Methods

The paper surveys alternative graph reduction and coarsening approaches, then selects largest-eigenvector downsampling with sparsified Kron reduction for signal-independent graph multiresolutions.

Alternative methods: Alternative reduction methods include weighted-adjacency constructions, assignment-based aggregation, diffusion-based clustering, algebraic multigrid, and multilevel coarsening.These methods differ in whether they retain vertices directly or aggregate them into coarse nodes.
Alternative methods: One weighted-adjacency reduction may fail to preserve connectivity, introduce self-loops, omit original selected edges, and alter Laplacian spectral containment.These are listed as undesirable properties of the method discussed in the paper.
Graph coarsening: Graph coarsening methods partition vertices into clusters, represent each cluster by one coarse vertex, and derive coarse edges from the original graph.The paper distinguishes this aggregate-node strategy from reductions that retain a strict subset of vertices.
Chosen framework: The paper’s graph multiresolution uses largest-eigenvector downsampling, Kron reduction, and an additional sparsification step.The resulting graph multiresolutions are independent of signals residing on the graph.
Graph filtering: Graph filtering represents graph signals using Laplacian eigenvectors and applies spectral kernels by multiplying frequency components.The filtered signal can equivalently be written using a matrix function of the graph Laplacian.

B. Alternative Filtering Methods for Graph Signals

The paper presents graph-signal interpolation alternatives centered on smoothness, using Green’s functions of a regularized Laplacian to reconstruct values missing after downsampling.

Interpolation assumptions: The interpolation model assumes the signal is smooth, which holds here because the signals have first been smoothed by a lowpass graph spectral filter.This assumption distinguishes the construction from settings with much sparser known samples.
Green’s-function interpolation: The method represents missing signal values as a linear combination of Green’s functions centered at vertices with known values.The Green’s functions are generated from the regularized graph Laplacian L̄ = L + ϵI.
Green’s functions: The parameter ϵ controls Green’s-function spread, with smaller values producing broader localization around center vertices.Figure 5 displays three translated Green’s functions centered at different Minnesota-graph vertices.
Coefficient fitting: The interpolation coefficients are chosen so the Green’s-function combination matches the signal values on the known vertex subset.The coefficients solve the corresponding system involving the restricted Green’s-function matrix.
Computation: The interpolation computation is dominated by solving a sparse diagonally dominant system, followed by reconstruction using the fitted coefficients.The resulting interpolant agrees with the known signal values on the retained vertices.

VI. A PYRAMID TRANSFORM FOR SIGNALS ON GRAPHS

The paper builds a graph-specific Laplacian pyramid by combining graph downsampling and reduction with graph filtering and interpolation. The resulting single-level transform preserves perfect reconstruction while allowing modular choices of graph-processing operations.

Single-level construction: The graph pyramid combines downsampling, graph reduction, filtering, and interpolation to extend the classical Laplacian pyramid to graph signals.Its single-level inputs are a coarse signal approximation and the current graph Laplacian.
Single-level construction: Vertex selection uses the polarity of the largest eigenvector of the current graph Laplacian, while graph reduction applies Kron reduction followed by spectral sparsification.The selection vector also defines the graph downsampling and interpolation operators.
Single-level outputs: The transform outputs the reduced graph and selection vector alongside a coarse approximation and a prediction-error vector.The graph and selection data must be retained for reconstruction.
Single-level prediction: Spline interpolation replaces classical upsampling and lowpass filtering, improving predictions and thereby increasing transform-coefficient sparsity in the authors’ experiments.The change adds computational cost but is used to form the prediction error.
Single-level filtering: Graph filtering uses the graph Laplacian eigenbasis, with H^(j) = U^(j)[ĥ(Λ^(j))]U^(j)*.This replaces classical filtering with a graph spectral filtering operator.
Modularity: The graph scheme remains modular: alternative vertex selection, reduction, filtering, and interpolation methods can replace the proposed blocks without affecting perfect reconstruction.The figure separates graph-specific processing from signal-specific processing.

C. The Multilevel Pyramid

The multilevel transform iterates the single-level analysis on successive coarse graphs, using stored graph and selection information for synthesis. It supports exact reconstruction without coefficient noise, while spectral-sparsification choices require care when controlling the reduced spectra.

Multilevel analysis: The multilevel pyramid repeatedly applies single-level analysis to the lowpass output, with filtering operators changing by resolution through the graph Laplacians.A fixed scalar filter may be reused across levels when the reduced spectra remain within the initial spectral range.
Synthesis and reconstruction: Perfect reconstruction is possible for any filter ĥ(·) from the coarse approximation and prediction error using the single-level synthesis operator.Synthesis requires access to both the graph Laplacian and vertex-selection vector at each level.
Spectral scope: Including spectral sparsification means the reduced Laplacian spectrum is not guaranteed to stay within the initial maximum eigenvalue range.For large graphs, cited results limit how far the maximum eigenvalue can increase; filters defined on the positive real line avoid a practical issue.
Examples: Three-level examples reduce Minnesota road-network vertices from 2642 to 1329 to 676 to 334, with an overall redundancy factor of 1.89.The corresponding Stanford Bunny example reduces 8170 vertices to 4108 to 2050 to 1018, with redundancy factor 1.88.
Noisy reconstruction: With noisy coarse and error coefficients, the pseudoinverse-based synthesis operator minimizes reconstruction error.Landweber iteration can approximate the required computation for large graphs.
Synthesis and reconstruction: Without noise in the transform coefficients, repeated synthesis recovers the original signal exactly.The reconstruction process starts from the coarsest approximation and applies synthesis operators level by level.

E. Illustrative Examples

The illustrative experiments apply the pyramid transform to graph signals for denoising and compression, including piecewise-constant, piecewise-smooth, and graph-data signals. The transform produces sparse prediction errors and supports reconstruction from substantially fewer coefficients.

Compression: The Stanford bunny experiment reconstructs a piecewise-smooth signal from 2724 of 15346 pyramid coefficients using least squares synthesis.The retained coefficients are approximately one-third of the original signal size.
Denoising: On the Minnesota road network, prediction-error coefficients are extremely sparse and nonzero values concentrate around the signal discontinuity.The experiment uses a piecewise-constant signal based on the sign of the Fiedler vector.
Compression: The least squares synthesis yields reconstruction error 0.086 ||f||2, compared with 0.145 ||f||2 for direct synthesis.Both errors result from hard thresholding the largest-magnitude coefficients.
Transform outputs: The framework outputs both a graph multiresolution and a signal multiresolution residing on the corresponding sequence of graphs.This feature is particularly useful for multiscale visualization of graph signals.

1) Denoising:

The experiments evaluate denoising and compression with the pyramid transform and compare compression behavior across several graph-signal models and alternative transforms. The reported compression results indicate reasonable performance across all three signal classes, while the section also describes computational constraints and approximations.

Denoising: The denoising experiment adds white Gaussian noise with varying standard deviations and reconstructs signals after thresholding prediction errors at 3σ.The reconstruction combines coarse approximation coefficients with thresholded prediction-error coefficients.
Compression: Compression is evaluated on piecewise-smooth, spatially localized bandpass, and Flickr graph signals using a three-level pyramid transform.The Flickr signals represent daily photo-user counts in 10 x 10 meter regions around Trafalgar Square.
Compression: The comparison includes the graph Fourier transform, Kronecker deltas, spectral graph wavelets, graph-QMF, spatial graph wavelets, diffusion wavelets, and the pyramid transform.For each transform, the largest-magnitude coefficients are retained and the signal is reconstructed from them.
Results: The proposed pyramid transform works reasonably well for compression across all three signal models.The Flickr reconstruction errors are averaged over 500 signals, and more sophisticated reconstruction methods are identified as possible extensions.
Computational considerations: Full graph-Laplacian eigendecompositions have O(N^3) complexity, motivating methods that avoid them and preserve Laplacian sparsity.Chebyshev filtering can reduce filtering cost to O(K|E|) for sparse graphs.

A. Power Method for Computing the Largest Eigenvector

The implementation discussion develops efficient procedures for eigenvector computation, Kron reduction, filtering, and storage in the pyramid transform. It identifies repeated eigendecompositions and interpolation-related linear systems as important computational considerations, while presenting the framework as modular and extensible.

Power method: The power method computes the largest Laplacian eigenvector using repeated matrix-vector multiplication, with per-iteration cost dominated by O(|E|) for sparse graphs.Convergence requires λmax > λN−2 and a nonzero initial projection onto the largest-eigenvector direction.
Power method: Power-method convergence is faster when the ratio λN−2/λmax is smaller and can be accelerated by shifting the spectrum.A random initial vector satisfies the required nonzero projection condition with high likelihood.
Kron reduction: Naive full computation of the Kron-reduced Laplacian can cost O(N^3), whereas operator-based multiplication avoids explicitly forming the entire reduced graph.The operator approach supports coefficient computation but does not provide reduced graphs or coarse approximations for plotting.
Graph storage: Because Kron reduction can produce dense Laplacians, spectral sparsification reduces storage requirements and the complexity of subsequent computations.This is especially relevant when graph Laplacians are stored across multiple pyramid levels.
Interpolation: The interpolation step is the bottleneck in the signal-analysis portion of the proposed transform.Recent sparse-system solvers can reduce its cost from O(|E|N) to O(|E| log2 N), or faster.
Conclusion: The framework is modular, allowing different choices for graph downsampling, graph reduction, filtering, and interpolation.The authors identify the joint effects of these choices on dictionary localization and coefficient sparsity as future work.