PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Shift Operator, Graph Frequency and Optimal Filtering in Graph Signal Processing

Adnan Gavili, Xiao-Ping Zhang

arXiv:1511.03512v6math.SPcs.IT

TL;DR

Graph signal processing needs a shift operator that supports classical signal-processing operations without changing signal energy. The paper constructs energy-preserving graph shifts, separates graph structure from spectral amplitude effects, and develops associated filtering and correlation tools. It derives LSI, Wiener, spectral-analysis, and prediction frameworks for graph signals, with efficient power-spectrum solutions under stated graph and shift-operator conditions.

  • Problem

    Graph shift operators are central to graph filtering, transformation, and prediction, but commonly used adjacency- and Laplacian-based operators can modify signal energy and hinder classical-style frequency analysis.

  • Method

    The paper constructs energy-preserving shift operators by representing graph structure with eigengraphs and assigning phase-shift eigenvalues, then develops LSI filters, graph correlations, and Wiener filtering.

  • Results

    The framework shows that adjacency matrices are LSI graph filters and provides explicit GFIR/GIIR forms, optimal Wiener filters, power-spectrum analysis, and linear predictors on graphs.

  • Takeaways & Limitations

    The framework analyzes graph signals along correlation structures defined by a graph shift manifold, paralleling classical time-shift-based signal processing.

Abstract

from arXiv · show

Defining a sound shift operator for signals existing on a certain graph structure, similar to the well-defined shift operator in classical signal processing, is a crucial problem in graph signal processing, since almost all operations, such as filtering, transformation, prediction, are directly related to the graph shift operator. We define a set of energy-preserving shift operators that satisfy many properties similar to their counterparts in classical signal processing. Our definition of the graph shift operator negates the shift operators defined in the literature, such as the graph adjacency matrix and Laplacian matrix based shift operators, which modify the energy of a graph signal. We decouple the graph structure represented by eigengraphs and the eigenvalues of the adjacency matrix or the Laplacian matrix. We show that the adjacency matrix of a graph is indeed a linear shift invariant (LSI) graph filter with respect to the defined shift operator. We introduce graph finite impulse response (GFIR) and graph infinite impulse response (GIIR) filters and obtain explicit forms for such filters. We further define autocorrelation and cross-correlation functions of signals on the graph, enabling us to obtain the solution to the optimal filtering on graphs, i.e., the corresponding Wiener filtering on graphs and the efficient spectra analysis and frequency domain filtering in parallel with those in classical signal processing. This new shift operator based GSP framework enables the signal analysis along a correlation structure defined by a graph shift manifold as opposed to classical signal processing operating on the assumption of the correlation structure with a linear time shift manifold. We further provide the solution to the optimal linear predictor problem over general graphs. Several illustrative simulations are presented to validate the performance of the optimal LSI filters.

I. INTRODUCTION

Graph signal processing represents signals on graph structures, but existing graph shift operators can alter signal energy and complicate classical-style filtering. The paper introduces energy-preserving shift operators, develops graph filtering and correlation tools, and derives optimal filtering frameworks for arbitrary graphs.

  • Motivation: Graph signal processing represents measurements from networked sources as signals whose graph structure captures relationships among nodes.Examples include sensor, transportation, weather, and body-area networks.
  • Motivation: Existing Laplacian- and adjacency-based shift operators can change signal energy through repeated application, complicating frequency-response design.An earlier isometric alternative preserves energy but has structure-dependent phase shifts and lacks some desired computational properties.
  • New graph shift operators: The paper introduces graph shift operators that preserve frequency-domain energy by separating graph structure, represented by eigengraphs, from amplitude-changing adjacency or Laplacian eigenvalues.A specific construction also provides a periodicity property analogous to classical signal processing.
  • Graph filtering: The proposed framework establishes linear shift-invariant graph filtering and shows that the adjacency matrix is an LSI graph filter under the new shift operator.The paper also develops GFIR and GIIR filters with explicit forms.
  • Optimal filtering: Using graph autocorrelation and cross-correlation, the paper derives Wiener filtering, efficient power-spectrum analysis for certain graphs, and optimal linear prediction.The resulting analysis follows a graph shift manifold rather than the linear time-shift manifold assumed in classical signal processing.

1) Graph shift:

The paper defines graph shift operators as linear operators that advance graph-signal states while preserving frequency-domain energy. The proposed operators retain graph eigenvectors but replace adjacency eigenvalues with unit-magnitude phase shifts, separating graph structure from filtering.

  • A graph shift operator maps a graph signal to a new state, analogous to a one-unit shift in classical signal processing.
  • The proposed operator Aφ is constructed from the adjacency eigenvectors and arbitrary distinct phase shifts λφk = e^jφk.
  • Aφ preserves the adjacency eigenvectors while replacing adjacency eigenvalues with pure phase shifts.
  • The shift preserves graph-signal energy in the frequency domain and changes only the phases of frequency components.
  • The special operator Ae may be nonsparse or complex-valued, increasing shift-domain storage and computation, although polynomial sparse implementations are available.
  • Unlike many existing adjacency- and Laplacian-based shifts, the proposed operator avoids repeated-shift energy growth or decay by using unit-modulus eigenvalues.

D. Frequency Content of Graphs, Eigengraphs and Graph Fourier Basis

The paper represents graph frequency through the adjacency matrix's eigendecomposition and interprets each eigencomponent as an eigengraph. Eigengraphs encode frequency-specific transition structures whose combinations recover the original graph.

  • The adjacency matrix is assumed diagonalizable, with its eigenvalues forming the graph spectrum and its eigenvectors defining graph-frequency components.
  • Each eigengraph is an eigenoperator of the adjacency matrix, while a linear combination of eigengraphs reconstructs the original graph structure.
  • The i-th eigengraph is a rank-one matrix formed from the paired right and left eigenvectors associated with the i-th frequency component.
  • An eigengraph can be viewed as a signal-transition matrix whose weights describe transitions between graph nodes.

3) Graph Fourier basis and Graph Fourier transform (GFT):

The graph Fourier transform uses the inverse eigenvector matrix to represent graph signals in a generally biorthogonal frequency basis. The resulting framework connects eigengraph projections, frequency preservation, and energy-preserving shifts.

  • The graph Fourier transform is F = V^-1, while V is the inverse graph Fourier transform mapping frequency coefficients back to graph signals.
  • For general graphs, the Fourier basis is biorthogonal rather than necessarily orthogonal, pairing columns of V with columns of (V^-1)^T.
  • For undirected graphs, the unitary Fourier transform makes the proposed shift operator unitary and preserves signal energy.
  • Applying an eigengraph operator selects the corresponding graph-frequency component, and the adjacency matrix decomposes into eigengraphs weighted by eigenvalues.
  • A graph shift should combine eigengraphs with equal magnitudes and phase-only coefficients, requiring |αi| = 1.
  • The three-node cyclic graph uses the discrete Fourier transform structure, with its adjacency matrix matching the special Ae operator.

III. GRAPH FILTERS BASED ON THE NEW SHIFT OPERATOR

The paper defines graph linear shift-invariant filters as operators commuting with the new shift and characterizes them through polynomial representations. This yields graph FIR/IIR analogues and connects graph filtering with classical convolution, including zero-padded aperiodic filtering.

  • A graph filter is a matrix H that maps an input graph signal x to an output Hx, and LSI filtering requires H Aφx = Aφ Hx.
  • Every polynomial of Aφ is a graph LSI filter, and every graph LSI filter is a polynomial of Aφ.
  • Any adjacency matrix is an LSI filter under Aφ because it commutes with the proposed shift operator.
  • For cyclic graphs, classical circular convolution is equivalent to LSI graph filtering using the circulant adjacency matrix.
  • Aperiodic convolution equals graph filtering of zero-padded signals with a circulant graph filter.
  • When the minimal-polynomial degree condition holds, an LSI filter has an equivalent polynomial representation of degree at most LAφ − 1.
  • GFIR and GIIR filters extend finite- and infinite-impulse-response concepts to graph filters through polynomial tap representations.

B. Frequency domain interpretation of filtering

The paper represents graph filtering in the Fourier domain as point-wise multiplication and shows that energy-preserving shift operators enable DTFT-based computation of LSI graph-filter coefficients.

  • The time/shift-domain operation y = Hx becomes yF = HFxF after applying the Fourier transform.
  • Fourier-domain filtering is point-wise: yF(m) = HF(m, m) × xF(m).
  • With energy-preserving shift operators Ae, an LSI filter's GFT coefficients can be computed using L-tap discrete-time Fourier transforms.
  • Because the shift eigenvalues have unit magnitude, filter coefficients control the magnitude of each frequency component.The paper contrasts this with arbitrary graph shifts whose eigenvalue magnitudes need not equal one.

IV. CORRELATION FUNCTIONS OF GRAPH SIGNALS AND OPTIMAL LSI GRAPH FILTERS

For graph representations of time-series data, the paper formulates optimal LSI denoising through autocorrelation and cross-correlation, recovering Wiener filtering and more efficient spectral computations.

  • The denoising problem designs an LSI filter to minimize the residual error ∥Hy − x∥2 for noisy observations y = x + n.
  • Shift invariance expresses the filter as H = Σ_{k=0}^{L−1} h_k C^k, with filtered output represented through a matrix of shifted observations.
  • When the polynomial degree equals the signal dimension, the shift-based matrix is full rank and the optimal coefficients can be obtained by matrix inversion.
  • The resulting linear system is the Wiener-Hopf equation, whose correlation matrix is Toeplitz for the time-series case.
  • The LSI property yields classical Wiener filtering, while Fourier-domain autocorrelation and cross-correlation calculations reduce computational complexity.

F Wrxy. (39)

The paper connects its graph-spectrum formulation to classical power-spectrum analysis, with the eigenvalue structure of the proposed shift operator supporting the representation.

  • The power-spectrum interpretation is consistent with classical signal processing, and the property of Λe is essential for the spectrum representation.
  • The paper indicates that a similar LSI-filter structure can be obtained for graphs with special structures.

B. Correlation Functions and Optimal (Wiener) Filtering for Arbitrary Graph Signals

For arbitrary graphs, the paper defines correlations through graph shifts and formulates optimal Wiener filtering as a graph Wiener-Hopf problem, with a simple power-spectrum solution only under specific conditions.

  • General LSI graph filters are polynomials of the defined shift matrix, H = h(Aφ).
  • Graph autocorrelation and cross-correlation measure relationships between signals and their graph-shifted versions.
  • These correlations produce a graph Wiener-Hopf equation for optimal filtering.
  • For efficient spectral computation, the paper considers eigendecomposition of Aφ and unitary eigenvectors, a condition satisfied by undirected graphs and some directed graphs.
  • The simple closed-form power-spectrum solution requires both unitary adjacency eigenvectors and the proposed shift operator Ae.
  • For general directed graphs, optimal filtering requires solving the general graph Wiener-Hopf equation rather than using the simple closed form.
  • The framework aims to extend autocorrelation, cross-correlation, and Wiener filtering from linear time-shift structures to graph correlation structures.

V. SIMULATIONS

Simulations compare the proposed energy-preserving shift operator with adjacency-based operators on undirected and directed sensor networks and in Wiener filtering. The proposed operator keeps Fourier-domain energy constant and achieves lower, less noise-dependent reconstruction error, while adjacency-based filtering saturates as coefficients increase.

  • Energy preservation: Adjacency-based shifts change signal energy because eigenvalues with magnitude above one grow across repeated shifts and dominate the frequency components.The proposed operator preserves shift-domain energy for integer multiples of N through its cyclic property, A_e^N = I.
  • Energy preservation: The proposed shift operator keeps the Fourier-domain energy constant for a 10-sparse signal under different shift amounts.For the directed example, the Fourier-domain energy is fixed at 8.32, although shift-domain energy varies.
  • Wiener filtering: Wiener filtering with the proposed shift operator produces much lower reconstruction error than traditional adjacency-based operators across three graph-construction approaches.The comparison includes k-nearest neighbors with k = 9, exponentially distance-weighted adjacency, and empirical covariance-based graph construction.
  • Wiener filtering: Adjacency-based Wiener filtering saturates after nearly 15 taps at noise variance σ2_n = 1 and earlier at σ2_n = 100, whereas the proposed operator continues improving with more coefficients.The saturation depends on the adjacency eigenvalue magnitudes; the proposed cyclic shift requires at most N taps for best LSI-filter performance.

VI. CONCLUSIONS

The paper introduces energy-preserving graph shift operators and develops an associated framework for graph filtering, correlation, spectral analysis, and prediction. It concludes that this framework supports graph signal analysis along a graph shift manifold and validates optimal filters through simulations.

  • The proposed shift operators preserve graph-signal energy in both shift and frequency domains by flexibly resetting adjacency- or Laplacian-matrix eigenvalues.
  • Any linear shift-invariant graph filter can be represented as a polynomial of the graph shift operator.
  • The framework defines GFIR and GIIR filters, autocorrelation and cross-correlation functions, and Wiener filtering through a graph Wiener–Hopf equation.
  • Illustrative simulations validate the performance of the designed optimal LSI filters.
  • The graph shift framework enables signal analysis along a correlation structure defined by a graph shift manifold rather than a linear time-shift manifold.

APPENDIX

The appendix derives polynomial representations for the proposed graph shift operator using the shared Fourier basis of the relevant operators. It reduces the coefficient determination to a Vandermonde linear system with a unique solution when the eigenvalues are distinct.

  • The proposed operator is assumed to be representable as a polynomial of the original graph operator.
  • Because the two operators share the same Fourier basis, both can be diagonalized using the same eigenvector matrix and its inverse.
  • The polynomial coefficients are organized into a linear matrix equation involving the operator’s eigenvalues.
  • The coefficient system uses a Vandermonde matrix, which has full rank when the eigenvalues are pairwise distinct.
  • When the Vandermonde matrix is full rank, the polynomial coefficients have the unique solution g = Z^-1λ.

B. Proof of Theorem 4

The proof constructs polynomial representations for graph shift operators and LSI filters, using diagonalized eigenvalue relations and Vandermonde systems. It also identifies finite filter lengths and a special eigenvalue choice for a particular operator.

  • B. Proof of Theorem 4: The minimal polynomial provides the algebraic basis for representing the proposed operator with a finite-degree polynomial.
  • B. Proof of Theorem 4: For the degenerate non-full-rank case, the proof treats the reduced minimal-polynomial degree separately and assumes α_LAφ = 1.
  • B. Proof of Theorem 4: The proof converts the operator relation into a diagonalized eigenvalue equation and then into a matrix-form linear system.
  • B. Proof of Theorem 4: The polynomial coefficients are obtained by solving the transformed system as α = ˜Z^-1˜λφ.
  • B. Proof of Theorem 4: A special operator is constructed by selecting eigenvalues λ_ek = e^-j 2π(k−1) for the corresponding frequency components.
  • B. Proof of Theorem 4: The resulting LSI filters can be expressed using the graph shift operator, with filter length reduced to the relevant minimal-polynomial degree plus one.
Loading 1511.03512v6…