PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph Signal Processing: History, Development, Impact, and Outlook

Geert Leus, Antonio G. Marques, José M. F. Moura, Antonio Ortega, David I Shuman

arXiv:2303.12211v1eess.SP

TL;DR

GSP develops spectral and algebraic approaches for signals and graphs, including a joint framework with sampling-based reconstruction. Its scope includes graph learning and neuroscience applications, while higher-order GSP and uncertainty remain open issues.

  • Problem

    Many applications require inferring an implicit graph from data to represent relations, similarities, or dependencies among data locations.

  • Method

    The paper reviews spectral and algebraic approaches to GSP and develops a joint framework connecting graph filters, signals, and sampling.

  • Results

    For bandlimited signals, when M ≥ K and (Φ_MV_K) is full rank, x can be identified from samples x_M via x = V_K(Φ_MV_K)†x_M.

  • Takeaways & Limitations

    The framework supports graph-signal analysis and learning across applications including graph learning and functional brain graphs.

  • Takeaways & Limitations

    Open issues include extending GSP to higher-order settings and incorporating uncertainty in signals and graphs.

Abstract

from arXiv · show

Graph signal processing (GSP) generalizes signal processing (SP) tasks to signals living on non-Euclidean domains whose structure can be captured by a weighted graph. Graphs are versatile, able to model irregular interactions, easy to interpret, and endowed with a corpus of mathematical results, rendering them natural candidates to serve as the basis for a theory of processing signals in more irregular domains. In this article, we provide an overview of the evolution of GSP, from its origins to the challenges ahead. The first half is devoted to reviewing the history of GSP and explaining how it gave rise to an encompassing framework that shares multiple similarities with SP. A key message is that GSP has been critical to develop novel and technically sound tools, theory, and algorithms that, by leveraging analogies with and the insights of digital SP, provide new ways to analyze, process, and learn from graph signals. In the second half, we shift focus to review the impact of GSP on other disciplines. First, we look at the use of GSP in data science problems, including graph learning and graph-based deep learning. Second, we discuss the impact of GSP on applications, including neuroscience and image and video processing. We conclude with a brief discussion of the emerging and future directions of GSP.

I. The Early Roots

GSP emerged from algebraic and spectral graph theory, harmonic analysis, and diverse graph-based methods for analyzing data. These strands converged into a common framework for processing signals on graphs.

  • GSP drew on algebraic and spectral graph theory, harmonic analysis, numerical linear algebra, and applications including machine learning and neuroscience.
  • Graph-based methods spread across computer graphics, image processing, Bayesian graphical models, dimensionality reduction, semi-supervised learning, and neuroscience.
  • Graph Laplacian eigenvectors supported surface smoothing and mesh compression, while weighted image graphs enabled denoising, smoothing, and segmentation.
  • Network science modeled small-world and scale-free systems and studied processes such as percolation, traffic flows, synchronization, and epidemic spread.
  • Early graph wavelet methods combined vertex-domain constructions, diffusion-based multiresolution spaces, orthogonal detail bases, and spectral localization.
  • GSP coalesced these perspectives into a common framework that developed into a full-fledged theory and set of ideas.

II. The Theoretical Underpinnings

Theoretical foundations of GSP extend classical signal-processing ideas to weighted graphs through graph-aware operators and topology-encoding matrices. Graphs represent relationships among data locations, while signals assign values to vertices.

  • Two foundational approaches used the graph Laplacian to generalize frequencies and filter banks, and the adjacency matrix to define the basic graph-signal shift.
  • The integrated framework connected these approaches with classical signal processing and helped propel GSP’s growth.
  • A. Basic definitions and notational conventions: A graph signal assigns data to vertices and may be scalar, discrete, complex, or vector-valued; here the discussion focuses on scalar real-valued signals.
  • A. Basic definitions and notational conventions: A weighted graph G = (V, E, ω) assigns vertices, edges, and real-valued edge weights, with larger weights representing stronger similarity or dependency.
  • A. Basic definitions and notational conventions: Time-series and image signals can be represented as graph signals using directed cycles and undirected two-dimensional lattices, respectively.
  • A. Basic definitions and notational conventions: Adjacency and Laplacian matrices encode graph topology, with the Laplacian defined as L := D − A and D containing vertex degrees.

B. The spectral approach for GSP

The spectral approach generalizes Fourier analysis by representing graph signals in bases ordered by graph smoothness or oscillation. Laplacian eigenvectors provide graph frequencies, enabling graph Fourier transforms and frequency-selective filters.

  • The spectral approach generalizes classical Fourier analysis by expanding graph signals in basis vectors ordered by their oscillation rate or smoothness.
  • The graph Laplacian extends the time-domain Laplacian, with eigenvectors acting as graph frequency vectors and eigenvalues measuring oscillation rate.
  • Laplacian eigenvectors are ordered by increasing variability: larger eigenvalues correspond to less-smooth, more variable eigenvectors.
  • The graph Fourier transform maps a signal x to frequency components through ˆx = V⊤x.
  • Graph filters modify frequency components individually through [ˆy]ℓ = H(λℓ)[ˆx]ℓ, with kernels that can promote smoothness and remove noise.
  • Graph filters also support missing-value interpolation and dictionaries localized around selected frequencies or vertices.

C. The algebraic approach for GSP

The algebraic approach defines graph signal processing from a graph-aware shift, choosing adjacency-matrix multiplication as the basic operation. Polynomial filters and their eigendecompositions extend classical filtering and Fourier representations to graphs.

  • The algebraic approach identifies a graph-aware operator and sets the basic graph-signal operation to Ax, multiplication by the adjacency matrix.
  • Adjacency multiplication combines neighboring signal values, while polynomial filters mix information from neighborhoods up to their polynomial order in hops.
  • When the adjacency matrix represents a directed cycle, graph polynomial filters reduce to classical linear time-invariant filters.
  • Graph filters are adjacency-polynomial operators p(A) that commute with A, generalizing shift-invariant polynomial filters.
  • The algebraic graph Fourier transform diagonalizes adjacency-polynomial filters through the eigendecomposition A = Vdiag(λ)V−1.
  • The framework generalized graph frequencies and low- or high-pass filters, supporting prediction, compression, classification, customer-behavior prediction, filter design, and sensor-network malfunction detection.

D. The benefits of a joint framework

A common GSP framework unified complementary approaches and connected graph-domain processing to classical signal processing. It enabled shared theory, technically grounded algorithms, and advances across sampling, filtering, signal modeling, and statistical analysis.

  • Graph shift operators generalized graph structure beyond individual adjacency or Laplacian choices, supporting broader processing setups.The operator can represent adjacency matrices, graph Laplacians, Gaussian Markov random-field precision matrices, or combinations.
  • Polynomial graph filters provided frequency- and vertex-domain views while representing successive applications of the graph shift operator.The filter can be parameterized by frequency responses or vertex-domain taps, with polynomial representations extending to arbitrary degree through the Cayley–Hamilton theorem.
  • The framework extended classical signal-processing tasks to graphs, including prediction, classification, compression, sampling, interpolation, denoising, and filter identification.Solutions depend on the chosen graph shift operator and assumptions about the graph filter or signal structure.
  • The generative model x = H(S)z unified structural assumptions such as bandlimitedness, smoothness, stationarity, and sparsity for graph-signal learning.This combination supported estimation and learning tasks and enabled statistical descriptions linking graph structure with graph-signal properties.
  • For K-bandlimited signals, M ≥ K samples identify the signal when Φ_MV_K is full rank, whereas regular sampling and ideal low-pass optimality do not generally transfer from time signals.The graph domain lacks the regularity that supports those classical sampling conclusions.
  • The joint framework connected previously separate approaches and clarified their relationships, differences, and complementary perspectives.

III. The Impact of GSP on Data Science

GSP has expanded beyond signal processing into data science, where graph-based approaches have made significant contributions. The reviewed problems include graph learning and graph-based deep learning.

  • GSP has significantly affected data-science disciplines beyond signal processing.
  • The identified data-science areas include graph learning and graph-based deep learning.
  • The paper reviews data-science problems in which GSP-based approaches have made significant contributions.

A. Graph learning

Graph learning uses graph-signal assumptions to infer network structure from observed data, addressing an otherwise severely ill-posed problem. GSP-based methods leverage smoothness, diffusion, and spectral or polynomial relations, with extensions to richer graph and interaction models.

  • Graph learning: Graph learning infers relationships among variables when the graph is implicit and must be recovered from data.The task is formulated as finding a sparse graph matrix S from graph signals X, but the problem is severely ill posed.
  • Graph learning: Graph construction can combine domain knowledge with data-derived relations, including pixel similarity, feature-based kNN edges, and brain-network correlations.Applications span transportation, communication, social, and structural brain networks.
  • Graph learning: Early GSP approaches learned graphs that make observed signals smooth with respect to the inferred topology.Laplacian-based smoothness leads to a kernel-ridge formulation and establishes links with graphical lasso.
  • Graph learning: Another class models observations as graph-filtered diffusion processes, with assumptions on the filter and latent input signals shaping topology inference.The model x_m = H(S)z_m connects observations to a sought graph through a graph filter; white inputs imply stationarity in S.
  • Graph learning: GSP provides a common spectral and polynomial framework that unifies existing graph-estimation methods and supports new estimation approaches.This framework has motivated generalizations to directed graphs, causal identification, hidden nodes, dynamic networks, multilayer graphs, and nonlinear interactions.

B. Network science

GSP tools have been applied to network-science problems such as clustering, community mining, structural embedding, and centrality measurement. These methods provide multiscale, spectral, and sampling-based alternatives for analyzing network structure.

  • Network science: GSP techniques address network-science problems including clustering and community mining.The reviewed examples include spectral wavelets, filtered random signals, and sampling or interpolation methods.
  • Network science: Spectral graph wavelets support a fast, multiscale protocol for community mining.The wavelet construction is presented as one example of GSP methods applied to network analysis.
  • Network science: Filtering random graph signals constructs vertex features whose pairwise distances resemble those from standard spectral-clustering features.This provides an efficient feature-construction approach for network analysis.
  • Network science: GSP sampling and interpolation methods can accelerate spectral clustering by avoiding k-means.The cited approach combines these methods with a clustering workflow that does not require k-means.
  • Network science: Graph wavelets can learn structural embeddings that identify vertices with similar network roles even when they are graph-distant.GSP also supplies a graph-Fourier-transform-based centrality measure.

C. Semi-supervised learning

GSP frames semi-supervised learning as graph-based signal estimation: known labels constrain the solution while graph structure supplies smoothness or sparsity priors. This connects label propagation, graph interpolation, and graph-wavelet methods.

  • Semi-supervised learning: Semi-supervised learning combines labeled and unlabeled data to predict labels for unlabeled points.Labels may be discrete for classification or continuous for regression.
  • Semi-supervised learning: Early graph-based methods build weighted similarity graphs over data points and diffuse known labels to unlabeled vertices.The resulting optimization includes a fitting term that matches known labels and a regularizer enforcing graph smoothness.
  • Semi-supervised learning: A low-pass graph-filter regularizer x⊤H(S)x enforces global smoothness of the label signal.This is combined with a fitting term for the known labels.
  • Semi-supervised learning: Graph-wavelet SSL instead encourages piecewise-smooth labels through a sparse linear combination of wavelet atoms.Its objective uses the norm or mixed norm of synthesis coefficients to impose a sparsity prior.
  • Semi-supervised learning: GSP relates SSL to graph signal interpolation, allowing sampling and reconstruction results for bandlimited signals to inform label prediction.This connection is stated as a graph-signal-processing interpretation of SSL.
  • Semi-supervised learning: GSP provides a principled framework for incorporating graphs into neural-network architectures and parameterizing graph filters.Examples include polynomial, rational, and diffusion filters, along with pooling, recurrent, product-graph, and graphon-filter architectures.
  • Semi-supervised learning: The GSP framework has clarified links among graph-neural-network works and enabled contributions on transferability, robustness, and graph sensitivity.These issues concern how architectures behave across or with respect to the underlying graph.

E. Graph-time processing

Graph-time processing represents signals observed across graph nodes and time using product graphs, joint transforms, and graph-aware temporal models. These tools support denoising, interpolation, and autoregressive modeling with richer graph-time interactions.

  • Graph-time processing: A time-varying graph signal can be represented as node time series, a collection of graph signals, or one signal varying across nodes and time.For X ∈ R^N×T, vec(X) lies in R^NT and jointly indexes graph location and time.
  • Graph-time processing: Product graphs combine the vertex graph with a time graph to create a larger graph with NT nodes.This enables standard GSP tools such as graph Fourier transforms and graph filters.
  • Graph-time processing: Joint graph-time filters analyze the joint spectrum and can be used for denoising or interpolation.In their most general form, these filters need not be separable across graph and time domains, increasing modeling and processing potential.
  • Graph-time processing: Graph-time vector autoregressive models replace or augment matrix weights with graph filters and graph-structured interactions.Graph VAR processes use filters H_p(S), while structural VAR processes model links among current and past node data with sparse matrix weights.
  • Graph-time processing: Causal graph-time models constrain graph-filter polynomial order by the temporal delay on which the filter operates.Graph-filter implementations can use the graph-frequency domain or polynomials of the graph shift operator.
  • Applications: GSP methods have been applied to engineering networks and to domains where graphs are inferred, including neuroscience and image and video processing.Examples include communication, smart-grid, power, water, transportation, social, meteorological, genetic, and financial networks.

A. Applications to neuroscience

GSP connects brain signals with anatomical or functional brain graphs, supporting graph learning and analyses of cognition, task state, disease, and behavior. Applications include graph transforms, localized frequency analysis, filtering, and diffusion modeling, although this pairing remains in its infancy.

  • Brain graph representations: Brain graphs represent structural connections or functional interdependencies between brain regions, often using diffusion MRI or fMRI data.Anatomical graphs capture structural connections, whereas functional graphs capture pairwise dependencies between measured regional activity.
  • Dynamic functional graphs: Task and rest functional brain graphs differ substantially, while resting-state graph dynamics correlate with EEG, demographic, and behavioral data.These findings illustrate that functional brain graphs can vary with cognitive state and exhibit meaningful resting-state dynamics.
  • GSP for brain signals: GSP merges brain signals with brain graphs to analyze how measured activity relates to anatomical or functional network structure.GSP tools can also support learning brain graphs, but their distinctive use is analyzing signal behavior relative to a graph.
  • GSP tools: GFTs, graph wavelets, Slepians, graph filters, and diffusion operators support localized frequency analysis and disease-progression modeling in neuroscience.These methods have been used to reveal localized brain frequency content and model dementia progression.
  • Cognitive and clinical analyses: Graph-frequency analyses link fMRI activity to attention switching, task-learning rate, exposure time, and differences associated with multiple concussions.Reported studies examine high- and low-frequency graph-signal energy across cognitive behavior, learning, and concussion-related comparisons.
  • Open scope: The application of GSP to neuroscience remains in its infancy, leaving substantial room for exploration.The review characterizes existing results as demonstrating potential rather than a mature pairing.

V. The Future Ahead

The future of GSP centers on extending graph models and processing methods to dynamic, higher-order, uncertain, categorical, geometric, and control settings. The field is expected to place greater emphasis on applications, learning, and statistical schemes while many technical challenges remain open.

  • Dynamic graphs: Dynamic graphs require methods for estimating changing graph topologies and processing time-varying graph signals.Graphs can change through new users, evolving connections, or task-dependent functional brain networks, so existing tools require extension.
  • Dynamic graphs: Dynamic graph-topology methods can be computationally challenging, and adaptive approaches still have low tracking rates.Many methods link consecutive graphs in the cost function; correction-only and prediction-correction methods address this issue but do not yet track reliably.
  • Higher-order GSP: Higher-order GSP extends processing beyond pairwise node interactions to edges, triangles, polygons, and other higher-order structures.Simplicial and cell complexes support hierarchical processing through higher-order Laplacians, while hypergraphs allow hyperedges connecting more than two vertices.
  • Higher-order GSP: Open issues in higher-order GSP include connections to topological data analysis and computational geometry.The review identifies these connections as unresolved directions for higher-order graph processing.
  • Broader directions: Future work also includes uncertainty-aware GSP, Bayesian recursive estimators, categorical data, continuous manifolds, reinforcement learning, and spatio-temporal control.These directions are presented as open problems expected to shape the discipline's future.
  • Field outlook: The coming years are expected to emphasize applications, learning, and statistical schemes more strongly than the field's early years.The review contrasts early theoretical emphasis with an anticipated increase in application-oriented work.
Loading 2303.12211v1…