PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph Filters for Signal Processing and Machine Learning on Graphs

Elvin Isufi, Fernando Gama, David I. Shuman, Santiago Segarra

arXiv:2211.08854v2eess.SPcs.LG

TL;DR

Graph filtering addresses the challenge of processing signals and learning patterns on irregular domains whose structure is not captured by conventional Euclidean filters. The article provides a unified overview of graph-filter categories, design strategies, trade-offs, filter banks, neural networks, and applications, while identifying higher-order convolutional instability and spectral approximation limits.

  • Problem

    Conventional filters cannot be directly applied to irregular data structures, while existing graph-filter references do not comprehensively unify forms, design choices, trade-offs, and applications across signal processing and machine learning.

  • Method

    The article synthesizes graph-filter forms, properties, design and learning strategies, applications, and extensions into filter banks and graph neural networks.

  • Results

    The article presents graph filters as a unifying framework spanning signal processing and machine learning, including their use in filter banks, neural networks, reconstruction, topology inference, and learning tasks.

  • Takeaways & Limitations

    Graph filters provide a common perspective for modeling graph-structured signals, data patterns, and relationships across signal-processing and machine-learning applications.

Abstract

from arXiv · show

Filters are fundamental in extracting information from data. For time series and image data that reside on Euclidean domains, filters are the crux of many signal processing and machine learning techniques, including convolutional neural networks. Increasingly, modern data also reside on networks and other irregular domains whose structure is better captured by a graph. To process and learn from such data, graph filters account for the structure of the underlying data domain. In this article, we provide a comprehensive overview of graph filters, including the different filtering categories, design strategies for each type, and trade-offs between different types of graph filters. We discuss how to extend graph filters into filter banks and graph neural networks to enhance the representational power; that is, to model a broader variety of signal classes, data patterns, and relationships. We also showcase the fundamental role of graph filters in signal processing and machine learning applications. Our aim is that this article provides a unifying framework for both beginner and experienced researchers, as well as a common understanding that promotes collaborations at the intersections of signal processing, machine learning, and application domains.

I. INTRODUCTION

Graph filters extend conventional filtering to irregular, graph-structured data while preserving useful filtering principles and adding graph-specific properties. This article addresses the lack of a comprehensive reference by unifying filter forms, design strategies, trade-offs, extensions, and applications across signal processing and machine learning.

  • Motivation: Graph filters adapt information processing to irregular biological, financial, social, economic, power, water, sensor, and multi-agent networks.They generalize conventional Euclidean filters to graph-structured data.
  • Motivation: Unlike conventional filters, graph filters can be permutation equivariant, distributively implemented, and generalized to node-varying or edge-varying forms.They retain linearity, shift invariance, parametric structure, and spectral interpretations while adding graph-specific flexibility.
  • Contribution: Existing work covers particular graph-filter forms, properties, or applications, but lacks a comprehensive and unifying treatment spanning signal processing and machine learning.The article is designed as a point-of-entry reference for fundamental research and applications.
  • Contribution: The article surveys graph-filter forms, properties, design and learning strategies, and extensions into filter banks and neural networks.These extensions are presented as ways to build more expressive solutions.
  • Applications: Graph-filter applications discussed include signal processing and machine learning tasks across physical and abstract networks.Examples include sensor, power, water, telecommunication, road, and other network settings, but the application roadmap is not comprehensive.

1) Signal reconstruction, including interpolation and denoising:

Graph convolutions process graph signals through repeated local shifts and shared weighted combinations, making them local, transferable, permutation-equivariant, and scalable architectures. These properties support signal reconstruction and broader graph-signal learning tasks.

  • Signal reconstruction: Graph signal reconstruction uses noisy or partial observations to denoise signals or interpolate missing values by leveraging neighboring values and graph structure.Approaches include regularization, fitting graph filters, and sparse graph-based dictionaries.
  • Graph convolutional filters: Graph shifts are local linear combinations of neighboring-node values, with adjacency shifts representing propagation and Laplacian shifts representing weighted differences.Repeated shifts provide the local information used by convolutional filtering.
  • Graph convolutional filters: A graph convolutional filter combines K shifted signals as a polynomial in the graph shift operator.Its output at a node depends on signal values up to K hops away.
  • Properties: Graph convolutions are permutation equivariant, so reordering node indices reorders the output without changing the underlying graph computation.This makes the filter independent of arbitrary node ordering while exploiting graph-relative signal patterns.
  • Properties: Graph convolutions can transfer from one graph to another, possibly with a different number of nodes, without redesigning or retraining.This is useful when the physical communication graph changes in distributed signal-processing tasks.
  • Properties: Graph convolutions have computational complexity O(K|E|+KN), linear in the number of edges and filter order.Local computation allows distributed implementation, while shared parameters use O(K) filter parameters.

IV. SPECTRAL ANALYSIS

Graph spectral analysis interprets graph-filter behavior through eigenvectors and eigenvalues of a graph shift operator, generalizing Fourier analysis from periodic signals. Graph frequencies are tied to signal variability, with distinct criteria for undirected and directed graphs.

  • Frequency response: The spectral frequency-response view is used to interpret graph-filter behavior and facilitate filter design for desired responses.The exposition assumes diagonalizable shift operators and additionally assumes Hermitian operators in some spectral examples.
  • Graph Fourier transform: The graph Fourier transform projects a signal onto the eigenvectors of a diagonalizable graph shift operator, and the inverse transform reconstructs it from those coefficients.The eigenvalues provide the associated graph-frequency coordinates.
  • Graph Fourier transform: For a directed cycle graph, the adjacency shift acts as a temporal delay, and the graph Fourier transform coincides with the discrete Fourier transform.This establishes the periodic time-signal case as a graph-signal special case.
  • Undirected graphs: For undirected graphs, Laplacian eigenvalues order eigenvectors by quadratic variation, with small eigenvalues representing low frequencies and large eigenvalues representing high frequencies.The lowest frequency is λ1 = 0 for a connected graph and corresponds to a constant eigenvector.
  • Directed graphs: For directed graphs, total variation measures how much a shifted signal differs from the original, and constant signals may have non-zero variation.Under the normalized adjacency shift, eigenvector variability is ordered by distance from the maximum-amplitude eigenvalue in the complex plane.
  • Bandlimited signals: A graph signal is N′-bandlimited when its variability can be represented using only N′ ≪ N graph Fourier basis vectors.The signal then expands over the corresponding subset of eigenvectors.

B. Frequency Response

Graph convolutional filters act as polynomial frequency responses: graph-domain filtering becomes pointwise multiplication in the graph frequency domain, with the graph determining the eigenvalue locations where the response is evaluated. Filter design ranges from exact operator matching under spectral conditions to approximate fitting when those conditions fail.

  • Frequency-domain interpretation: Graph convolutional filtering multiplies each input GFT coefficient by the filter frequency response at the corresponding graph eigenvalue.The response is an analytic polynomial in the eigenvalue, while the input GFT depends on the graph-shift eigenvectors.
  • Frequency-domain interpretation: A graph convolutional filter assigns the same frequency response to frequencies sharing an eigenvalue.Repeated eigenvalues therefore constrain the response of polynomial graph convolutional filters.
  • Frequency-domain interpretation: The filter frequency response is determined by its parameters and is instantiated on a graph’s specific eigenvalues, determining its effect on the input.Figure 4 illustrates this graph-specific sampling of the response.
  • Operator matching: Operator matching can reduce computational cost for dense matrices or enable distributed implementation over sensor networks.The distributed relevance follows from graph-filter locality, even though eigendecomposition costs O(N^3).
  • Operator matching: Exact operator matching requires simultaneous diagonalization, equal desired responses on repeated eigenvalues, and filter order K ≥ D.Under these conditions, h* = Ψ†β yields B = H(h*, S).
  • Operator matching: When exact matching conditions are too stringent, spectral or vertex-domain approximation fits a lower-order polynomial to the desired operator.Universal polynomial design fits over a spectral interval, whereas non-spectral design uses h* = Θ†vec(B).

B. Data-driven

Data-driven graph-filter design identifies filter parameters from input-output observations, including settings with partial observations and unknown inputs. Polynomial bases provide recursive and distributable implementations, while regularization promotes simpler filters and lifting supports blind deconvolution.

  • System identification: Data-driven filter identification estimates graph-filter parameters from input-output realizations of graph-based systems.Examples include opinion formation, source identification, biological signals, and diffusion processes.
  • Polynomial approximation: Chebyshev approximation represents a desired response with a truncated low-order polynomial graph convolutional filter.The coefficients have a closed-form integral expression, and truncation to finite K controls computational complexity.
  • Polynomial approximation: Recursive evaluation of Chebyshev terms enables graph filters whose parameters are computed offline and whose operation can be implemented distributively.The recursion starts from T0(S)x = x and T1(S)x = γSx − x.
  • System identification: With only M ≤ N observed nodes, identification uses a sampling matrix that selects the observed outputs.The formulation can include a fitting loss and a sparsity-promoting regularizer on the filter parameters.
  • System identification: Increasing penalties for higher powers of S promotes lower-complexity and numerically stable filters when the degree is overestimated.The weighting vector controls the relative penalties, while γ controls regularization strength relative to fitting loss.
  • Blind deconvolution: Blind deconvolution jointly estimates the unknown input and filter parameters by lifting their bilinear relation into a rank-one matrix variable.Convex relaxations use nuclear-norm and mixed-norm penalties to promote low rank and row sparsity.

VI. OTHER GRAPH FILTERS

Alternative graph filters address limitations of polynomial convolutional filters through rational responses and other filtering forms. Rational filters can achieve comparable responses with lower order, but introduce stability, design, and output-computation challenges.

  • Motivation: Polynomial graph convolutional filters become more expressive as order K grows, but higher matrix powers can cause numerical instability and poor interpolation or extrapolation.Their spectral form also may not approximate a general operator sufficiently well.
  • Rational graph filters: Rational filters use a ratio of polynomials whose orders control zeros and poles, often achieving similar responses with fewer parameters and lower order.Their improved interpolatory and extrapolatory properties motivate them as alternatives to polynomial filters.
  • Rational graph filters: Rational filters face stability issues because their denominator roots must satisfy stability constraints.Universal stability can be imposed over an interval when the specific graph eigenvalues are unavailable.
  • Rational graph filters: Rational filtering requires solving a linear system in the vertex domain, with cubic-order complexity O(N^3) before iterative methods are applied.Conjugate-gradient implementations can reduce the cost to O((PT + Q)|E|) after T iterations.
  • Rational graph filters: Designing rational filters is harder than fitting polynomial filters because the optimization is nonlinear and must address stability.Optimization-based methods enforce stability, while change-of-variable approaches can yield closed-form stable filters but are often limited to ideal step responses.
  • Rational graph filters: Distributed rational filtering relies on local first-order methods such as ARMA-like recursions or gradient descent.For small-diameter graphs, quasi-Newton or preconditioned gradient methods are also described as local options.

B. Node Domain Filtering

Node- and edge-varying graph filters increase expressivity by assigning parameters across nodes or edges while retaining local implementation. This flexibility supports more general operator matching, but sacrifices permutation equivariance and transferability across graphs.

  • Node-varying filtering: Node-varying filters assign node-specific parameters to shifted signals, extending convolutional filtering while preserving locality.The filter applies different parameters to each node and shift order.
  • Node-varying filtering: Node-varying filters can implement more general operators than convolutional filters while maintaining local computation.Their operator-matching conditions are less stringent than simultaneous diagonalization required for conventional filters.
  • Edge-varying filtering: Edge-varying filters let each node weight each neighbor differently, increasing flexibility while preserving local implementation.They use edge-specific parameters at each shift, with the zeroth-order matrix reducing to self-node weights.
  • Complexity and trade-offs: Node- and edge-varying filters have O(K|E|) complexity despite substantially larger parameter counts than convolutional filters.The node-varying filter has N(K+1) parameters, while the edge-varying filter has N +(N +|E|)K parameters.
  • Complexity and trade-offs: These filters are neither shift invariant nor permutation equivariant, so cascade order and node labeling matter and transfer across graphs is unavailable.Their many degrees of freedom can also be difficult to estimate from limited data, motivating regularization or hybrid designs.
  • Nonlinear extensions: Nonlinear graph filters address the limitations of node-domain filters by modeling more complex input-output relationships with shared nonlinear functions.The surveyed examples include Volterra and median graph filters, although polynomial models may overfit or become ill-conditioned.

D. Filtering by Regularization

Regularization-based graph filters recover signals by combining data fidelity with graph-based priors such as smoothness, sparsity, or statistical structure. These choices yield filters with distinct spectral behavior and assumptions, while regularizer selection remains challenging.

  • Framework: Regularization filtering recovers graph signals from noisy or incomplete observations by combining a fitting term with a graph-based prior.The paper organizes these methods into smooth, sparsity, and Wiener filtering.
  • Smooth filtering: Increasing the Tikhonov parameter γ prioritizes smoothness and produces a more low-pass rational graph filter.Its frequency response is ˜h(λ) = (1 + γλ)^-1.
  • Sparsity filtering: Graph trend filtering estimates signals whose differences are sparse on edges, with higher-order variants imposing sparsity on diffused or shifted differences.These constraints capture discontinuities and recover piecewise-constant signals better than smooth filtering methods.
  • Sparsity filtering: Odd- and even-order graph trend filters impose different sparsity structures on diffused signals or shifted versions, respectively.The formulation can require iterative algorithms, and its ℓ1 penalty may shrink large signal components toward zero.
  • Wiener filtering: Wiener filtering uses a frequency-adaptive inverse-SNR regularizer rather than a constant regularization weight.Under shared eigenvectors between signal and noise covariance matrices and the graph shift operator, it reduces to a rational graph filter.
  • Design trade-offs: The main challenge is identifying a regularizer or combination that accurately represents the data, often requiring domain expertise.This motivates using more general graph filters as input-output mappings when prior specification is difficult.

E. Multi-GSO Filters

Multi-GSO filters use several graph shift operators as inductive biases about the graph or data. This approach reduces parameter and computational costs relative to learning the shift operators directly while retaining linear parameter design.

  • Multi-GSO formulation: Multi-GSO filters combine signal shifts from several graph shift operators to encode multiple graph or data inductive biases.The filter applies parameters h_qk to the kth shift associated with the qth graph shift operator.
  • Complexity and design: Using Q graph shift operators reduces the parameters to Q(K + 1) and the computational cost to O(QK|E|).Because the filters remain linear in their parameters, data-driven design reduces to least squares.

VII. GRAPH FILTER BANKS AND WAVELETS

Graph filter banks combine multiple graph filters to produce richer representations, with undecimated designs emphasizing flexible analysis and critically sampled designs reducing storage while preserving reconstruction under suitable conditions.

  • Multiple filter outputs can form feature vectors for machine learning or support regularization when coefficients have known structures such as sparsity.
  • Undecimated Single-Level M-Channel Graph Filter Banks: An undecimated M-channel bank applies M filters and concatenates their outputs, producing a redundant transform whose coefficients can be interpreted through localized dictionary atoms.
  • Undecimated Single-Level M-Channel Graph Filter Banks: Tight Parseval frames equalize the summed squared filter responses across eigenvalues, preserving signal energy and enabling perfect reconstruction when analysis and synthesis filters coincide.
  • Undecimated Single-Level M-Channel Graph Filter Banks: Spectral graph wavelets use dilated filters whose atoms become increasingly vertex-localized, yielding sparse coefficients for smooth or piecewise-smooth graph signals.
  • Downsampling and Critically-Sampled Graph Filter Banks: Critically sampled banks downsample channel outputs to reduce storage, while bipartite and generalized arbitrary-graph designs can achieve perfect reconstruction through spectral folding or biorthogonal conditions.

C. Alternative Structures for Arbitrary Graphs

Perfect reconstruction on arbitrary graphs can be pursued through several alternatives beyond standard critically sampled designs, including multiresolution, subgraph, interpolation, and oversampled constructions.

  • Alternative structures include graph lifting and pyramid transforms, oversampled filter banks, subgraph-based banks, and designs replacing synthesis with interpolation operators.

D. Multi-Level Graph Filter Banks

Multi-level graph filter banks face a central challenge: defining coarser graphs that preserve the spectral relationships needed for meaningful filtering across levels. Learned filter banks and nonlinear graph architectures extend representational capacity in response.

  • D. Multi-Level Graph Filter Banks: Classical multi-level banks repeatedly filter and downsample lowpass outputs, but irregular graphs lack an obvious coarsening that preserves correspondence between successive shift-operator eigenvectors.
  • D. Multi-Level Graph Filter Banks: Graph filter banks can be learned from representative signals to produce sparse representations or tight frames with balanced average subband energy.
  • Graph Neural Networks: GNNs stack graph filters with pointwise nonlinear activations, enabling sequential feature extraction and more complex relationships than linear graph filters.
  • Graph Neural Networks: Multiple filters per layer increase GNN representation power by transforming several input features into several output features and aggregating them to avoid exponential growth.
  • Graph Neural Networks: Learned layer filter banks can be viewed as undecimated analysis banks, with width and depth serving as hyperparameters associated with representational capability.

A. Graph Convolutional Neural Networks

Graph convolutional neural networks use graph filters, nonlinear activations, and learned feature mixing to form local architectures that respect graph structure. Alternative filter choices yield different GNN properties, including sharper transitions, non-convolutional behavior, interpretability, and higher expressive power.

  • Graph Convolutional Neural Networks: GCNN layers shift graph features locally across up to K hops and combine features at each node through learned filter-bank coefficients.
  • Graph Convolutional Neural Networks: Pointwise activation combined with local graph filtering makes GCNNs local and preserves key graph-filter properties, while remaining Lipschitz continuous to graph-support changes.
  • Graph Convolutional Neural Networks: GCNNs can stably process information at large graph-shift eigenvalues, unlike linear graph convolutions, making them suitable when such information matters.
  • Implementations: Different parameter choices recover architectures such as GCN, SGC, GIN, and GraphSAGE, with some low-pass designs associated with oversmoothing.
  • Alternative GNN Filters: Replacing convolutional filters changes GNN behavior: rational filters sharpen frequency transitions, node- and edge-varying filters produce non-convolutional models, and wavelet filters support interpretable training-free scattering.
  • Alternative GNN Filters: Nonlinear graph filters such as max and median filters can serve as learnable local activations while preserving permutation equivariance and increasing expressive power.

A. Signal Reconstruction

Graph filters support reconstruction, anomaly detection, topology inference, image processing, and distributed signal processing by exploiting graph structure and localized operations. Their applications range from recovering noisy or missing signals to consensus and graph-based image enhancement.

  • Signal reconstruction: Graph-filter-based reconstruction estimates missing or noisy graph-signal values using regularization, fitted filters, or sparse graph-filter dictionaries.Dictionary atoms are formed from graph convolutional filters, whose order controls vertex locality and the number of trainable parameters.
  • Anomaly detection: Bandlimited or low-pass graph signals can expose anomalies through unexpected high-pass components.Detection methods include high-pass filtering, nonlinear reconstruction, and band-pass filters followed by energy-based testing.
  • Network topology inference: Topology inference formulates graph recovery as fitting observed signals with a filter while regularizing the graph shift operator.Low-pass assumptions encourage smooth signals, whereas stationarity-based approaches impose covariance–shift commutativity.
  • Graph-based image processing: Graph-based image processing represents pixels as graph signals and uses weighted graphs and low-pass filters for denoising, smoothing, and edge enhancement.Weights combine pixel-location and intensity distances; heat kernels and low-order filters provide examples.
  • Distributed processing: Local graph-filter implementations support distributed denoising and consensus over networks where nodes exchange information with neighbors.Exact finite-time average consensus is possible with an appropriate filter when the graph is connected, while higher-order filters improve approximate consensus but may introduce design instability.

2) General operator:

Graph filters can match desired operators and support distributed implementation, adaptation, and robust processing under communication imperfections. Their behavior depends on filter design, link reliability, quantization, synchronization, and algorithmic assumptions.

  • General operator: Graph convolutional, rational, node-varying, and edge-varying filters can approximate a desired operator and implement it distributively by exploiting locality.The same operator-matching perspective extends across several graph-filter classes.
  • Interference: Link losses perturb distributed filter outputs, and Lipschitz analyses bound the expected squared deviation when edges are independently preserved.The bound depends on the preservation probability, Lipschitz constant, and a shift-operator-dependent factor.
  • Asynchronous implementation: Asynchronous communication improves scalability but can compromise convergence guarantees, although sufficient conditions ensure mean-squared-error convergence to the designed output.The same line of analysis extends to filter banks and edge-varying filters.
  • Interference: Robust filter design accounts for quantization errors because quantizing exchanged signal shifts distorts the filter output.The distortion-control parameter is set according to the quantization step size, with extensions addressing link losses and graph-filter dictionaries.
  • Adaptive distributed filtering: Distributed least-mean-squares adaptation decomposes filter-parameter learning across nodes using local updates and neighbor-weighted combinations.Each node uses a local step size and combination weights restricted to its neighborhood.
  • Adaptive distributed filtering: Under the stated white-temporal-process assumptions, the diffusion algorithm converges asymptotically in mean to the optimal filter when step sizes are sufficiently small.The expected error tends to zero for any initial condition.

X. APPLICATIONS IN MACHINE LEARNING

In machine learning, graph filters use graph structure as an inductive bias for semi-supervised and unsupervised learning, matrix completion, and recommender systems. They propagate or reconstruct information while offering parameter-efficient, permutation-equivariant, and computationally efficient mappings.

  • Overview: Graph filters provide parameterized input-output mappings with limited parameters, permutation equivariance, and linear computation cost.These properties motivate applications across semi-supervised learning, clustering, matrix completion, and Gaussian processes.
  • Semi-Supervised Learning: In semi-supervised learning, graph filters propagate labeled-node information from multi-hop neighbors to unlabeled nodes.Filter banks can use multiple similarity graphs or class-specific filters, while regression-like objectives may limit classification performance despite convex implementation.
  • Unsupervised Learning: Spectral clustering uses smooth Laplacian eigenvectors as node features before normalization and k-means clustering.Graph filtering can improve scalability by approximating ideal filters, sampling nodes for k-means, and assigning remaining labels through smooth regularization.
  • Matrix completion: Graph filters support matrix completion by treating matrix entries as signals over graphs that encode row and column side information.This extends signal reconstruction to partially observed interaction matrices and addresses settings where low-rank structure or complete rows and columns are unavailable.
  • Matrix completion: A learned graph convolutional filter for recommender systems can behave as a bandstop filter, combining low-pass smoothing with high-pass diversity improvement.The vanilla nearest-neighbor collaborative filter is a special case of an order-one graph convolutional filter.

D. Supervised Learning with Gaussian Processes

The section models graph-signal outputs with Gaussian processes whose covariance incorporates graph filters. These filters impose signal behavior such as smoothness and use multi-hop neighborhood information through graph convolutions.

  • Graph Gaussian-process model: Graph-signal outputs provide an alternative Gaussian-process regression model in which output covariance includes the graph-filter factors H(S)H(S)⊤.The covariance between outputs is K(x_n, x_m)H(S)H(S)⊤.
  • Filter-induced behavior: A first use of H(S) is a low-pass rational filter that produces graph signals smooth with respect to the underlying graph.
  • Filter-induced behavior: Graph-filtered regression can also generalize the Matérn kernel to the graph setting.
  • Learned graph convolutions: A graph convolutional filter can have parameters estimated from data while preserving kernel validity and weighting information from multi-hop neighbors.The cited approach is reported to outperform regularized-filtering kernels.
  • Applications and extensions: The surrounding overview situates graph filters across signal-processing and machine-learning applications, including point-cloud processing, tracking, and future higher-order network structures.
Loading 2211.08854v2…