PaperlayerView exact revision on arXiv

Source-linked AI summary

The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains

David I Shuman, Sunil K. Narang, Pascal Frossard, Antonio Ortega, Pierre Vandergheynst

arXiv:1211.0053v2cs.DMcs.LGcs.SI

TL;DR

Signals on graphs require methods that respect irregular data domains while retaining useful signal-processing intuition. This tutorial defines graph spectral domains, reviews generalized operators and localized multiscale transforms, and highlights both their extensions and unresolved challenges.

  • Problem

    Signal processing on graphs must determine suitable graph constructions, localized transforms, Euclidean intuitions, and efficient implementations for high-dimensional signals on irregular domains.

  • Method

    The paper surveys graph spectral domains, generalized signal operators, and localized multiscale transforms for graph signals.

  • Results

    Classical signal-processing intuition often extends to graphs, but irregular domains produce surprising transform properties and resolution trade-offs.

  • Takeaways & Limitations

    Graph signal analysis benefits from incorporating graph structure while recognizing that multiple spectral bases and transform designs remain viable.

  • Takeaways & Limitations

    The paper notes that explicitly computing Laplacian eigenvectors is impractical for extremely large graphs, leaving efficient approximation and numerical issues open.

Abstract

from arXiv · show

In applications such as social, energy, transportation, sensor, and neuronal networks, high-dimensional data naturally reside on the vertices of weighted graphs. The emerging field of signal processing on graphs merges algebraic and spectral graph theoretic concepts with computational harmonic analysis to process such signals on graphs. In this tutorial overview, we outline the main challenges of the area, discuss different ways to define graph spectral domains, which are the analogues to the classical frequency domain, and highlight the importance of incorporating the irregular structures of graph data domains when processing signals on graphs. We then review methods to generalize fundamental operations such as filtering, translation, modulation, dilation, and downsampling to the graph setting, and survey the localized, multiscale transforms that have been proposed to efficiently extract information from high-dimensional data on graphs. We conclude with a brief discussion of open issues and possible extensions.

I. INTRODUCTION … II. THE GRAPH SPECTRAL DOMAINS

The paper frames graph signal processing as an emerging field for analyzing high-dimensional data on weighted, irregular networks by combining graph theory with computational harmonic analysis. It introduces graph spectral domains as analogues of classical frequency domains and surveys generalized operators and localized multiscale methods for graph signals.

  • I. INTRODUCTION: Weighted graphs represent geometric structures in social, energy, transportation, sensor, neuronal, and learning-related data domains.Vertices represent data entities, while edge weights can encode similarities or inferred or physics-determined relationships.
  • I. INTRODUCTION: Graph signal processing addresses filtering, denoising, inpainting, and compression when data reside on irregular graph domains.The central questions concern how to process graph data and efficiently extract information for storage, communication, and analysis.
  • A. The Main Challenges of Signal Processing on Graphs: Classical signal processing cannot be directly transferred to graphs because treating graph signals like discrete-time signals ignores dependencies induced by irregular data domains.Graph signals and length-N discrete-time signals are both vectors in R^N, but their domain structures differ.
  • A. The Main Challenges of Signal Processing on Graphs: Fundamental graph operations remain nontrivial: translation lacks a natural coordinate shift, modulation must handle irregular discrete spectra, and downsampling lacks an obvious notion of every other vertex.Multiresolution methods must also generate coarser graphs that capture structural properties of the original graph and scale to large vertex counts.
  • A. The Main Challenges of Signal Processing on Graphs: The field’s overarching challenges are constructing informative weighted graphs, incorporating graph structure into localized transforms, leveraging Euclidean signal-processing intuition, and developing computationally efficient methods.These challenges arise alongside the irregularity and potentially large scale of graph data.
  • A. The Main Challenges of Signal Processing on Graphs: Signal processing on graphs combines algebraic and spectral graph theory with computational harmonic analysis to study signals rather than only their underlying graphs.The paper positions this combination as a response to the field’s central methodological challenges.
  • B. Outline of the Paper: The tutorial reviews graph structure encodings and graph spectral domains, then surveys generalized filtering, translation, modulation, and downsampling operators and localized multiscale transforms.These spectral domains serve as analogues to the classical frequency domain, while the operators support information extraction from graph data.
  • II. THE GRAPH SPECTRAL DOMAINS: Spectral graph theory provides frequency spectra and expansion bases for graph Fourier transforms, extending mathematical ideas and intuitions from classical Fourier analysis to graphs.Section II reviews the relevant spectral graph theory definitions and notation with this signal-processing focus.

A. Weighted Graphs and Graph Signals · B. The Non-Normalized Graph Laplacian · C. A Graph Fourier Transform and Notion of Frequency

The paper represents vertex-based data as signals on undirected, connected, weighted graphs, analyzes their variation with the non-normalized graph Laplacian, and defines graph frequency through Laplacian eigenvectors and eigenvalues. Low graph frequencies correspond to slowly varying eigenvectors, while larger eigenvalues indicate more rapidly oscillating behavior.

  • A. Weighted Graphs and Graph Signals: Edge weights may be constructed with a thresholded Gaussian kernel or by connecting each vertex to its k-nearest neighbors using physical or feature-space distances.Distances can represent physical separation or Euclidean distance between feature vectors.
  • A. Weighted Graphs and Graph Signals: Signals on a weighted graph are vectors in R^N whose ith component gives the function value at vertex i.The graph consists of vertices, edges, and a weighted adjacency matrix; disconnected graphs can be separated into pieces by connected component.
  • B. The Non-Normalized Graph Laplacian: The non-normalized graph Laplacian is Ł := D − W, with D containing weighted degrees, and it acts as a difference operator on graph signals.The degree at vertex i is the sum of weights of all edges incident to that vertex.
  • B. The Non-Normalized Graph Laplacian: Because Ł is real symmetric, it has orthonormal eigenvectors with real non-negative eigenvalues, and zero has multiplicity equal to the graph’s number of connected components.For connected graphs, the eigenvalues are ordered beginning with zero.
  • C. A Graph Fourier Transform and Notion of Frequency: The graph Fourier transform expands a signal on graph-Laplacian eigenvectors, with the inverse transform reconstructing the signal from those components.This parallels the classical Fourier expansion in eigenfunctions of the one-dimensional Laplace operator.
  • C. A Graph Fourier Transform and Notion of Frequency: Graph Laplacian eigenvalues and eigenvectors define frequency: low-frequency eigenvectors vary slowly across strongly weighted edges, whereas larger eigenvalues correspond to faster oscillations.Adjacent vertices connected by large-weight edges are likely to have similar values for low frequencies and dissimilar values for higher frequencies.
  • C. A Graph Fourier Transform and Notion of Frequency: Laplacian eigenvectors associated with larger eigenvalues cross zero more often, supporting their interpretation as higher graph frequencies.Zero crossings are edges connecting a positive-valued vertex to a negative-valued vertex; this pattern holds for both non-normalized and normalized Laplacians.

D. Graph Signal Representations in Two Domains · E. Discrete Calculus and Signal Smoothness with Respect to the Intrinsic Structure of the Graph

Graph signals can be represented equivalently in the vertex and graph spectral domains, while graph-based discrete calculus defines smoothness through the graph’s intrinsic connectivity. The graph Laplacian unifies these representations and smoothness measures by linking neighboring values, differential operators, and spectral frequencies.

  • D. Graph Signal Representations in Two Domains: Graph Fourier analysis represents a signal equivalently in the vertex domain and graph spectral domain, where kernels may be defined directly spectrally.A heat kernel illustrates equivalent representations across the two domains.
  • E. Discrete Calculus and Signal Smoothness with Respect to the Intrinsic Structure of the Graph: Smoothness must be assessed relative to the intrinsic structure of the weighted graph rather than independently of its domain.Discrete calculus adapts differential operators to finite, discrete spaces.
  • E. Discrete Calculus and Signal Smoothness with Respect to the Intrinsic Structure of the Graph: Edge derivatives and graph gradients provide discrete differential operators for describing how a signal changes across graph edges and vertices.These operators formalize smoothness with respect to the underlying graph.
  • E. Discrete Calculus and Signal Smoothness with Respect to the Intrinsic Structure of the Graph: Local variation measures smoothness around a vertex and is small when its value resembles those of all neighboring vertices.The measure captures local agreement between a signal and adjacent values.
  • E. Discrete Calculus and Signal Smoothness with Respect to the Intrinsic Structure of the Graph: The discrete p-Dirichlet form provides a global smoothness measure, with p = 1 yielding graph total variation and p = 2 yielding the Laplacian quadratic form.The p = 2 form also induces a graph-Laplacian seminorm.
  • E. Discrete Calculus and Signal Smoothness with Respect to the Intrinsic Structure of the Graph: The Laplacian quadratic form is zero exactly for signals constant across all vertices and is small when strongly weighted neighboring vertices have similar values.Thus, edge weights determine which neighboring differences contribute most to global smoothness.
  • E. Discrete Calculus and Signal Smoothness with Respect to the Intrinsic Structure of the Graph: Laplacian eigenvectors associated with lower eigenvalues are smoother, explaining why the graph Laplacian spectrum provides a notion of frequency.The Rayleigh-quotient characterization gives an iterative interpretation of these eigenvectors.
  • E. Discrete Calculus and Signal Smoothness with Respect to the Intrinsic Structure of the Graph: Graph connectivity is encoded in the Laplacian, which defines the graph Fourier transform and smoothness notions; both depend on the underlying graph.Changing the graph can change a signal’s smoothness and graph spectral content.

F. Other Graph Matrices

Graph Fourier analysis can use several graph matrices beyond the non-normalized Laplacian, including the normalized Laplacian, generalized Laplacians, and random-walk matrices. The choice of basis is context-dependent, while graph structure directly affects signal smoothness and spectral content.

  • Graph-dependent spectral behavior: Signal smoothness and spectral content depend on the underlying graph structure, with quadratic forms fTŁ1f = 0.14, fTŁ2f = 1.31, and fTŁ3f = 1.81.The signal is smoothest on G1 and least smooth on G3.
  • Normalized graph Laplacian: The normalized graph Laplacian provides an alternative spectral basis whose higher-eigenvalue eigenvectors generally have more zero crossings, while its zero-eigenvalue eigenvector is not constant.Its spectrum is contained in [0, 2], and its maximum eigenvalue equals 2 exactly for bipartite graphs.
  • Generalized graph Laplacians: Generalized graph Laplacians, also called discrete Schrödinger operators, are symmetric matrices with negative entries on edges, zero entries for nonadjacent distinct vertices, and unrestricted diagonal entries.Both normalized and non-normalized graph Laplacians are examples of this broader class.
  • Random walk matrix: The random walk matrix P := D−1W represents one-step transition probabilities, and for connected, aperiodic graphs, Pt rows converge to the walk’s stationary distribution.It is often used in dimensionality-reduction techniques for graph signals and is closely related to the asymmetric graph Laplacian.
  • Basis selection: There is no clear rule for choosing normalized or non-normalized Laplacian eigenvectors, or another basis, as graph-signal filtering bases.The normalized Laplacian nevertheless offers a spectrum bounded in [0, 2] and spectral folding for bipartite graphs.

III. GENERALIZED OPERATORS FOR SIGNALS ON GRAPHS · A. Filtering · 1) Frequency Filtering:

The paper frames graph filtering as a generalized operator built from a chosen graph spectral representation, extending frequency-domain filtering to irregular graph signals. These filters support classical smoothing and regularization methods, including applications to inverse problems such as denoising, inpainting, and super-resolution.

  • III. GENERALIZED OPERATORS FOR SIGNALS ON GRAPHS: Generalized graph operators—including filtering, translation, modulation, dilation, and downsampling—provide ingredients for localized, multiscale graph transforms.The paper reviews these operations as foundations for the transforms discussed later.
  • A. Filtering: Filtering is introduced first by extending frequency filtering to graphs, followed by localized filtering in the vertex domain.This establishes the organization of the filtering discussion.
  • 1) Frequency Filtering:: Classical frequency filtering represents a signal as complex exponentials and amplifies or attenuates selected components through a transfer function.The transfer function specifies how the filter modifies frequency components.
  • 1) Frequency Filtering:: After fixing a graph spectral representation, graph spectral filtering applies a transfer function to graph Fourier coefficients and is equivalently written as fout = ˆh(Ł)fin.The construction uses the eigenvectors of Ł, although ˜Ł can also define the graph Fourier transform.
  • 1) Frequency Filtering:: Graph spectral filtering implements discrete versions of Gaussian smoothing, bilateral filtering, total variation filtering, anisotropic diffusion, and non-local means filtering.These filters can arise as solutions to variational problems that regularize ill-posed inverse problems.
  • 1) Frequency Filtering:: Graph filtering and energy-minimization models connect discrete spectral filters with continuous partial differential equations and applications including image processing, mesh smoothing, and statistical learning.The cited models include p-Dirichlet-form-based formulations and applications such as denoising.

2) Filtering in the Vertex Domain:

Vertex-domain filtering is a localized linear transform that combines signal values within a K-hop neighborhood. Polynomial graph spectral filters admit the same localization, while graph-based low-pass filtering can denoise while better preserving image edges than classical Gaussian filtering.

  • Filtering in the Vertex Domain:: Vertex-domain filtering computes each output value as a linear combination of input values within a K-hop neighborhood.This is a localized linear transform over graph vertices.
  • Filtering in the Vertex Domain:: An order K polynomial frequency filter produces a vertex-domain output that depends only on vertices within K hops.This links spectral filtering to localized vertex-domain operations and relates kernel smoothness to signal localization.
  • Filtering in the Vertex Domain:: Tikhonov regularization reconstructs a graph-smooth signal through the low-pass filter ĥ(λ) = 1/(1+γλ).The method models noisy observations as a clean graph signal plus uncorrelated additive Gaussian noise and penalizes graph roughness.
  • Filtering in the Vertex Domain:: Graph spectral filtering smooths less across image edges than classical Gaussian filtering because the graph Laplacian encodes image geometry.The comparison uses a 512 x 512 cameraman image corrupted by Gaussian noise with standard deviation 0.1.

B. Convolution · C. Translation · D. Modulation and Dilation

The paper generalizes convolution, translation, modulation, and dilation to graph signals through graph Laplacian eigenvectors and spectral-domain operations. These generalizations preserve selected classical properties while reflecting graph-spectrum irregularity and vertex-domain localization.

  • B. Convolution: Graph convolution replaces complex exponentials with graph Laplacian eigenvectors, making vertex-domain convolution equivalent to multiplication in the graph spectral domain.This construction adapts the classical convolution theorem to signals defined on graph vertices.
  • C. Translation: Graph translation is defined as generalized convolution with a delta centered at vertex n.The operator acts on a spectral-domain kernel rather than directly translating a vertex-domain signal.
  • C. Translation: The translation normalization preserves a signal’s mean, while kernel smoothness controls localization around the center vertex.The translated kernel’s magnitude decays as vertex distance from n increases.
  • C. Translation: Unlike classical translation, generalized graph translation is not generally isometric, partly because graph Laplacian eigenvectors may have limited localization.This distinguishes graph translation from ordinary shifts in regular domains.
  • D. Modulation and Dilation: Generalized modulation multiplies by a graph Laplacian eigenvector instead of a complex exponential, but irregular discrete spectra prevent exact spectral translation.A kernel localized around zero remains localized around λ_k under this operation.
  • D. Modulation and Dilation: Graph dilation is derived in the Fourier domain because direct time-domain scaling can map vertices outside the graph domain.Unlike generalized modulation, it requires the kernel to be defined on the entire real line.
  • D. Modulation and Dilation: Powers of the heat diffusion operator implement dilation by filtering signals with a dilated heat kernel, with increasing powers spreading influence from local to more distant vertices.The heat kernel filter is ˆg(λ_l) = e^−λ_l, and dyadic diffusion powers underpin diffusion wavelets and diffusion wavelet packets.

E. Graph Coarsening, Downsampling, and Reduction

Graph coarsening transforms a fine graph into a smaller graph while seeking to preserve geometric, connectivity, spectral, and sparsity properties. It comprises vertex selection and edge-weight assignment, with downsampling selecting vertices and reduction or contraction defining their connections.

  • Graph Coarsening: Graph coarsening creates a graph with fewer vertices and edges while preserving intrinsic geometry, connectivity, graph spectral distribution, and sparsity.These properties are important for multiscale graph transforms.
  • Graph Coarsening: The process separates selecting the reduced vertex set from assigning its edges and weights; restricting selected vertices to the original set defines graph downsampling.The edge-and-weight assignment step is called graph reduction or graph contraction.
  • Graph Downsampling: Bipartite graphs admit natural factor-of-two downsampling because vertices can be divided into two subsets connected only across subsets.This provides an “every other vertex” interpretation.
  • Graph Coarsening: Non-bipartite graph coarsening is more complex and includes vertex-sampling, recursive spectral bisection, edge-based objectives, and Laplacian-eigenvector polarity methods.The cited methods use graph structure, Fiedler-vector signs, within-subset edges, or the eigenvector associated with λmax.
  • Related Connections: Graph coarsening connects to graph coloring, spectral clustering, and nodal domain theory, while bandlimited graph signals can be downsampled on particular subgraphs and stably reconstructed.Pesenson’s extension establishes sampling and reconstruction for certain graph-signal classes.

IV. LOCALIZED, MULTISCALE TRANSFORMS FOR SIGNALS ON GRAPHS

Graph signal processing has developed localized, multiscale transforms—including numerous wavelet constructions—to analyze graph data by localizing information across graph space and spectral domains. Existing graph wavelet designs broadly divide into vertex-domain and graph-spectral-domain approaches, with applications also valuing reconstruction, sampling, orthogonality, and multiresolution.

  • Transform designs: Recent graph-transform research includes wavelets, diffusion wavelets and packets, top-down constructions, graph-dependent bases, lifting-based wavelets, and multiscale wavelets.These methods target signals on graphs in applications including computer-network traffic and sensor networks.
  • Transform designs: Most graph-transform designs generalize classical wavelet filter banks, seeking simultaneous localization of graph-signal information in graph space and graph frequency.This localization supports a time-frequency resolution trade-off analogous to that of classical wavelets versus the Fourier transform.
  • Transform properties: Depending on the application, desirable graph-wavelet properties include perfect reconstruction, critical sampling, orthogonal expansion, and multiresolution decomposition.
  • Transform categories: Graph wavelet transform designs broadly divide into vertex-domain and graph-spectral-domain constructions.

A. Vertex Domain Designs · B. Graph Spectral Domain Designs

Graph wavelet transforms are designed either from vertex-domain structure, using connectivity and distances, or from graph spectral properties encoded by matrix eigenvalues and eigenvectors. Vertex-domain methods localize through neighborhoods or hierarchical constructions, while spectral-domain methods seek joint vertex and spectral localization through diffusion, bandpass, or filter-bank designs.

  • A. Vertex Domain Designs: Vertex-domain transforms use node connectivity and intervertex distances, with outputs computed from samples in a K-hop neighborhood.Most such localized transforms are instances of vertex-domain filtering, while their graph spectral properties are not explicitly designed.
  • A. Vertex Domain Designs: Random transforms compute weighted averages or differences over k-hop neighborhoods, using constant nonzero weights selected to guarantee invertibility.Weights are c within the neighborhood and zero outside.
  • A. Vertex Domain Designs: Lifting-based graph transforms partition vertices into even and odd sets, then combine odd-node prediction coefficients with even-node update coefficients.Odd nodes use their own data and even neighbors for prediction; even nodes use their own data and neighboring odd-node predictions for updates.
  • A. Vertex Domain Designs: Vertex- and spectral-localization designs involve a trade-off, and spectral-spread results depend on heuristic definitions and, for irregular graphs, the chosen Laplacian matrix.The cited spread definitions lack a well-understood theoretical background.
  • A. Vertex Domain Designs: Tree wavelets build a balanced hierarchical tree from graph data and generate orthonormal bases for its partitions using modified one-dimensional wavelet filtering and decimation.The construction is defined over partitions at each tree level.
  • B. Graph Spectral Domain Designs: Spectral-domain designs use eigenvalues and eigenvectors of graph matrices to construct bases localized in both the vertex and graph spectral domains.Examples include diffusion wavelets, spectral graph wavelets, and graph quadrature mirror filter banks.
  • B. Graph Spectral Domain Designs: Diffusion wavelets compress powers of a diffusion operator, then downsample and orthogonalize localized basis functions at each resolution level.Orthogonalization uses a variation of Gram-Schmidt.
  • B. Graph Spectral Domain Designs: Spectral graph wavelets use dilated and translated versions of a bandpass kernel designed in the non-normalized graph Laplacian spectral domain.The construction is explicitly graph-spectral rather than vertex-domain based.

C. Examples of Graph Wavelet Designs

The section illustrates graph wavelet design through a vertex-domain CKWT and a spectral-domain SGWT. Their comparison shows a graph-specific trade-off between spatial and spectral localization.

  • Vertex-domain design: The CKWT constructs wavelets from shortest-path distance, making them constant on vertices equally distant from a center vertex.Wavelet values depend on distance shells around the center vertex.
  • Vertex-domain design: CKWT wavelets are exactly supported within a k-hop neighborhood around their center vertex.The coefficients a_k,τ vanish for τ > k.
  • Spectral-domain design: The SGWT uses translated low-pass scaling functions and dilated band-pass wavelets centered at every vertex across multiple scales.Its band-pass kernel satisfies ĝ(0) = 0, tends to zero as λ → ∞, and obeys an admissibility condition.
  • Localization comparison: On d-regular random graphs, CKWT wavelets are more spatially localized but less spectrally localized than SGWT wavelets.The comparison uses average spatial and spectral spreads across wavelets at each scale.
  • Signal representation: The transforms are also evaluated for representing a piecewise smooth graph signal with a sharp discontinuity on the unweighted Minnesota road graph.The experiment uses CKWT scales k = 1, 2, . . . , 10 and SGWT with 5 wavelet scales plus a scaling kernel.

V. SUMMARY, OPEN ISSUES, AND EXTENSIONS · A. Open Issues • · B. Extensions

The paper summarizes a graph signal processing framework built around generalized operators and localized, multiscale transforms, while emphasizing that graph irregularity creates unexpected properties. It identifies open questions about graph construction, spectral and vertex-domain choices, scalability, and approximation theory, and proposes extensions to dynamic and directed settings.

  • V. SUMMARY, OPEN ISSUES, AND EXTENSIONS: The framework generalizes filtering, convolution, and translation to graphs, providing core operations for localized, multiscale graph transforms.These generalized operators underlie the graph signal processing algorithms reviewed in the paper.
  • V. SUMMARY, OPEN ISSUES, AND EXTENSIONS: Graph irregularity can produce surprising signal and transform properties even when classical Euclidean signal-processing intuition extends directly.The paper notes that graph frequency generalizes naturally, but irregular domains can lead to unexpected behavior.
  • A. Open Issues •: The graph’s construction is crucial because all described methods incorporate graph structure, yet its effects on localized, multiscale transforms remain poorly understood.This makes graph construction an important open issue for analyzing transform behavior.
  • A. Open Issues •: It remains unclear when to use normalized Laplacian eigenvectors, non-normalized Laplacian eigenvectors, or another basis for graph spectral filtering.The choice of spectral filtering basis is not resolved by the framework.
  • A. Open Issues •: Selecting among geodesic, resistance, diffusion, and algebraic distances remains an open question for constructing or analyzing graph transform methods.Each distance has useful properties, but the paper does not identify a universally best choice.
  • A. Open Issues •: Scalable graph transforms require efficient application and adjoints, but explicitly computing Laplacian eigenvectors is impractical for extremely large graphs.Approximate computational methods are therefore identified as an important research direction.
  • A. Open Issues •: A major open issue is linking structural properties of graph signals and graphs to transform-coefficient properties such as sparsity and localization.Such approximation theory could guide the design of graph transforms.
  • B. Extensions: The static, weighted, undirected framework could extend to directed graphs, vertex-wise time series, time-varying graphs, or combinations of these.Although analytic techniques have increased, their application to real science and engineering problems remains in its infancy despite vast potential applications.
Loading 1211.0053v2…