PaperlayerView exact revision on arXiv

Source-linked AI summary

Stationary Graph Processes and Spectral Estimation

Antonio G. Marques, Santiago Segarra, Geert Leus, Alejandro Ribeiro

arXiv:1603.04667v2eess.SYcs.IT

TL;DR

Graph structure complicates extending time-domain stationarity and spectral analysis to graph signals. The paper defines weak graph stationarity for normal shifts, establishes equivalent formulations, and develops PSD estimation methods spanning nonparametric and parametric models. It also analyzes these methods and illustrates PSD estimation on synthetic and real-world graphs.

  • Problem

    Irregular graph domains make it difficult to generalize classical time-domain stationarity and spectral analysis to graph signals.

  • Method

    The paper models stationary graph processes using normal graph shifts, graph filters, covariance characterizations, and graph PSD estimators including periodograms, windowing, filter banks, MA, AR, and ARMA models.

  • Results

    The proposed stationarity formulations are equivalent under mild conditions, and the paper analyzes nonparametric and parametric methods for estimating graph power spectral densities.

  • Takeaways & Limitations

    Graph stationarity can be studied through graph Fourier-domain PSDs, enabling spectral estimation methods adapted from time-domain analysis to graph processes.

Abstract

from arXiv · show

Stationarity is a cornerstone property that facilitates the analysis and processing of random signals in the time domain. Although time-varying signals are abundant in nature, in many practical scenarios the information of interest resides in more irregular graph domains. This lack of regularity hampers the generalization of the classical notion of stationarity to graph signals. The contribution in this paper is twofold. Firstly, we propose a definition of weak stationarity for random graph signals that takes into account the structure of the graph where the random process takes place, while inheriting many of the meaningful properties of the classical definition in the time domain. Our definition requires that stationary graph processes can be modeled as the output of a linear graph filter applied to a white input. We will show that this is equivalent to requiring the correlation matrix to be diagonalized by the graph Fourier transform. Secondly, we analyze the properties of the power spectral density and propose a number of methods to estimate it. We start with nonparametric approaches, including periodograms, window-based average periodograms, and filter banks. We then shift the focus to parametric approaches, discussing the estimation of moving-average (MA), autoregressive (AR) and ARMA processes. Finally, we illustrate the power spectral density estimation in synthetic and real-world graphs.

I. INTRODUCTION

The paper generalizes stationarity and spectral analysis from time signals to graph signals using normal graph shift operators. It defines equivalent stationarity conditions and develops nonparametric and parametric methods for graph power spectral density estimation.

  • Graph signal processing: Graph signal processing represents signals on graph vertices, using a graph shift operator and graph Fourier transform to exploit graph structure.The graph Fourier transform projects signals into the eigenvector space of the graph shift operator.
  • Weak stationarity: The paper defines weak graph stationarity through linear filtering of white input, shift-related covariance invariance, or covariance diagonalization by the shift eigenvectors.These three definitions are equivalent under mild conditions and preserve the locality associated with the graph shift.
  • Scope: The graph-domain framework applies to arbitrary normal graph shift operators, extending beyond Laplacian shifts to all symmetric shifts and some nonsymmetric shifts.The directed cycle is included among the nonsymmetric normal shifts covered.
  • Spectral estimation: The paper studies graph PSD estimation with periodograms, correlograms, window-based average periodograms, filter banks, and parametric MA, AR, and ARMA models.ARMA parameter estimation is generally non-convex, though certain cases including positive semidefinite shifts are tractable.
  • Weak stationarity: For normal shifts with distinct eigenvalues, filter-based and covariance-based stationarity definitions are equivalent because the associated Vandermonde system has a solution.The distinct-eigenvalue condition guarantees the required filter coefficients.

A. Properties of Graph Stationary Processes

The paper characterizes graph stationarity through graph-filter generation, covariance structure, and graph Fourier analysis. These properties extend classical stationary-process ideas while incorporating graph locality and structure.

  • Definition and spectral representation: Stationary graph processes can be modeled as graph-filter outputs of white inputs, with covariance diagonalized by the graph Fourier transform.The graph Fourier transform yields an uncorrelated process representation and supports frequency-domain analysis.
  • Filter properties: Graph filtering preserves stationarity, transforming covariance as Cy = HCxHᴴ and PSD as py = |h̃|² ◦ px.This is the graph-domain analogue of spectral convolution for stationary signals.
  • Locality of correlations: A degree-L−1 graph filter limits correlations to nodes within the 2(L−1)-hop neighborhood.The bound follows from filter locality and motivates graph windows for spectral estimation.
  • First-order moments: The proposed mean may be a scaled eigenvector of the shift, incorporating graph structure while recovering the classical constant-mean case in specified shifts.This differs from prior definitions that require zero mean or a scaled all-ones vector.

B. Examples of Stationary Graph Processes

The paper gives examples showing that graph stationarity arises naturally from covariance, precision, white-noise, and diffusion constructions. Graph filtering also preserves stationarity for diffusion-type processes.

  • White noise: Zero-mean white noise is stationary for any graph shift and has a flat PSD proportional to the identity vector.Its covariance is σ²I.
  • Covariance matrix graph: Using the covariance matrix as the graph shift makes any random process stationary, with PSD equal to the shift’s eigenvalue vector.This construction connects graph stationarity with correlation-based network topology inference.
  • Precision matrix graph: A process is stationary with respect to its precision matrix, whose sparse structure captures conditional independence for Gaussian Markov random fields.For a GMRF, nonzero precision entries correspond to graph links or diagonal terms.
  • Network diffusion processes: Diffusion dynamics can be expressed through local graph recursions, and a stationary initial process remains stationary after the resulting graph filtering.The Cayley-Hamilton theorem represents the matrix polynomial as a graph filter of degree less than N.

IV. NONPARAMETRIC PSD ESTIMATION

The paper develops nonparametric PSD estimators for graph-stationary processes from one or a few realizations, extending periodograms, correlograms, windowing, and filter banks to graph signals. It analyzes estimator bias, variance, and the bias–variance tradeoff of smoothing methods.

  • Nonparametric methods: Nonparametric graph PSD estimation generalizes periodograms, correlograms, windowing, and filter banks without assuming a particular process model.Parametric methods are treated separately.
  • Periodogram and correlogram: The graph periodogram estimates PSD by averaging squared magnitudes of graph Fourier transforms across observed realizations.The procedure computes the GFT of each sample before averaging spectral magnitudes.
  • Periodogram and correlogram: The correlogram retains the diagonal of the graph-Fourier-transformed empirical covariance, and it is identical to the periodogram estimator.The equivalence follows because both use the same squared GFT magnitudes from each realization.
  • Estimator properties: The periodogram is unbiased, while its covariance formula requires Gaussian processes; for symmetric shifts, different frequency estimates are uncorrelated.The Gaussian restriction arises because covariance evaluation uses fourth-order moments.
  • Estimator properties: Periodogram variance scales with the squared PSD, producing errors on the order of the frequency component magnitude.Windows and filter banks reduce MSE by trading bias for variance.

B. Windowed Average Periodogram

Windowing creates multiple graph-signal realizations from one observation, enabling averaged PSD estimates while introducing spectral distortion and dependence. Nonoverlapping local windows can reduce cross-term effects when correlations are sufficiently local.

  • Windowing in the graph domain: Graph windows are vertex-domain multiplications whose frequency-domain dual is ˜W = V^Hdiag(w)V, generally mixing spectral components.The identity dual operator would avoid spectral distortion, but is typically impractical beyond the all-ones window.
  • Bias and averaging: The windowed periodogram is biased because its expectation is transformed by the frequency-domain window operator.Its bias is determined by the dual windowing operator ˜W.
  • Bias and averaging: Averaging multiple windowed periodograms can reduce estimation variance, but the gain is smaller than with independent samples because all windows derive from one realization.The same construction also introduces distortion because windowed signals replace the original process.
  • Window design: Window-bank bias depends on the weighted sum of spectrum-mixing matrices, so suitable designs can produce small bias even when individual matrices differ from identity.The mixing matrices depend on both the window-bank design and graph topology.
  • Window design: Optimal windows minimize squared bias plus covariance trace, but the optimization is computationally challenging because the bias depends on the unknown PSD.Assuming a white PSD or using other prior PSD knowledge can circumvent the unknown-PSD issue in the objective.
  • Local windows: Nonoverlapping windows separated by more than 2L hops eliminate cross terms for processes generated by an L-degree graph filter.Under this condition, the covariance of the PSD estimator behaves as if the windowed samples were independent, though the bound reflects a stringent correlation model.

C. Filter Banks

Filter banks estimate graph PSD components by filtering one realization through normalized linear shift-invariant filters and averaging the resulting output energies. Their variance benefits from averaging, but useful MSE reduction requires controlling bias through graph-frequency structure.

  • Filter-bank construction: A filter bank uses N normalized linear shift-invariant filters, with each filter intended to estimate one component of the graph PSD.The kth estimate is obtained from the energy of the filtered output signal x_k = Q_kx.
  • Filter-bank construction: Filter-bank estimates act as virtual realizations generated by different filtered versions of a single observed graph signal.This contrasts with windowing, where virtual realizations come from different pieces of the same signal.
  • Bias and variance: Averaging provides a variance advantage, but overall MSE decreases only when the associated bias is sufficiently small.The MSE combines the estimator variance with squared bias.
  • Filter design: Graph-frequency components with similar PSD values can be averaged when additional structure, such as similar shift eigenvalues in diffusion processes, identifies them.For ordered Laplacian eigenvalues, averaging nearby PSD estimates corresponds to bandpass filtering.
  • Filter design: FIR filter-bank design can target low MSE but may require prior PSD knowledge and optimization involving fourth-order polynomials.FIR filters are attractive because they can be implemented distributively.

V. PARAMETRIC PSD ESTIMATION

The parametric approach models a graph process as the response of a graph filter to white input and estimates compact MA, AR, or ARMA representations.

  • Parametric PSD estimation: Parametric PSD estimation assumes the graph process is well approximated by a graph filter H applied to white input.The paper focuses on modeling graph processes and estimating the generating filters, not on filter design.
  • Parametric PSD estimation: The target is a filter representation with order much smaller than the number of signal elements N.The paper develops moving-average, autoregressive, and ARMA models by analogy with time processes.

A. Moving Average Graph Processes

Moving-average graph processes model signals as finite-order graph-filter responses to white input, linking covariance and PSD estimation to the filter coefficients. The resulting coefficient-fitting problems are generally nonconvex, with tractable relaxations under additional shift or coefficient restrictions.

  • Moving-average model: An MA graph process uses an FIR graph filter H(β) = Σ_{l=0}^{L−1} β_lS^l applied to white input, with practical order L much smaller than N.The filter degree is less than N−1, while the intended regime is L ≪ N.
  • Covariance and PSD: For an FIR-generated process, the covariance is determined by the filter, and the PSD equals the magnitude squared of its graph-frequency response.These expressions are graph counterparts of MA time processes.
  • Coefficient estimation: Filter coefficients can be estimated by minimizing covariance-domain distortion or by comparing the observed periodogram with the model PSD.Both approaches select coefficients that best match empirical second-order or spectral estimates.
  • Optimization challenges: The covariance-based and periodogram-based optimization problems are generally nonconvex because their quadratic forms in β are indefinite.The same nonconvexity appears in the quadratic spectral model used for frequency-domain fitting.
  • Tractable restrictions: For symmetric shifts, reparameterizing covariance through coefficient crossproducts yields a convex relaxation when the distortion metric is convex.Dropping the crossproduct constraints makes the relaxation tractable, while retaining them recovers equivalence to the original problem.
  • Tractable restrictions: For positive semidefinite shifts with nonnegative filter coefficients, replacing the squared-magnitude comparison by a linear-response comparison produces a convex optimization.This restriction changes the objective and requires both positive semidefinite shifts and β ≥ 0.

B. Autoregressive Graph Processes

The paper models autoregressive graph processes through infinite-impulse-response graph filters and derives corresponding PSD estimation formulations. First-order models require only two parameters, while higher-order models extend this construction through multiple poles.

  • Autoregressive Graph Processes: A diffusion filter H = α0(I −αS)^−1 acts as a single-pole autoregressive graph filter.Its frequency response and PSD provide the basis for AR parametric estimation.
  • Autoregressive Graph Processes: AR PSD estimation substitutes the model covariance and PSD into graph-domain and graph-frequency-domain optimization problems.For the single-pole model, only two parameters must be estimated, making the optimization problems tractable.
  • Autoregressive Graph Processes: An order-M AR process is formed by sequentially applying M single-pole filters with distinct diffusion rates.This construction extends the single-pole model to higher-order autoregressive dynamics.
  • Autoregressive Graph Processes: A Gaussian first-order AR process has a sparse precision matrix, so each node’s Markov blanket is its two-hop neighborhood.The process is stationary with respect to both the graph shift and its precision matrix.

C. Autoregressive Moving Average Graph Processes

ARMA graph processes combine finite- and infinite-response graph filters and estimate PSDs through frequency-domain rational models. The methods support covariance estimation, though the general coefficient-fitting problems can be computationally difficult.

  • Autoregressive Moving Average Graph Processes: ARMA graph filters are formulated as ratios of polynomials in graph eigenvalues, combining autoregressive and moving-average components.The resulting filter can be interpreted as sequential finite- and infinite-response filtering.
  • Autoregressive Moving Average Graph Processes: The covariance of an ARMA-generated process is diagonalized by the graph Fourier basis, yielding a corresponding stationary PSD.This establishes the ARMA model within the paper’s graph-stationarity framework.
  • Autoregressive Moving Average Graph Processes: ARMA coefficients can be identified by minimizing covariance or PSD distortion, but these optimization problems may be computationally difficult.Relaxations for symmetric shifts and restrictions to nonnegative coefficients for positive semidefinite shifts provide tractable alternatives.
  • Autoregressive Moving Average Graph Processes: Model choice depends on diffusion structure: MA models suit finite-order dynamics, whereas AR models suit single-pole or sequential diffusion processes.The paper recommends MA estimation when the diffusion length is small relative to graph size.
  • Autoregressive Moving Average Graph Processes: Parametric PSD estimators can also produce covariance estimates directly or by reconstructing the covariance from the estimated PSD.The reconstruction uses the graph Fourier basis and the estimated graph PSD.
  • Autoregressive Moving Average Graph Processes: Figure 1 compares NMSE across periodograms, window strategies, filter banks, MA estimators, and ARMA estimators using different realization counts.The panels vary input distribution, window number, generating-filter degree, and R = 1 versus R = 2 realizations.

VI. NUMERICAL EXPERIMENTS

Numerical experiments evaluate nonparametric and parametric PSD estimators on synthetic graphs, then apply graph-stationarity tools to opinion, image, brain, and protein-network examples. The results show estimator behavior and practical stationarity-related applications.

  • TC1. Nonparametric methods: For the baseline Gaussian experiment, the average periodogram has NMSE = 2/R and remains insensitive to graph size, topology variation, and filter degree.The tested variations include smaller Erdős–Rényi and small-world graphs and a degree-6 filter.
  • TC1. Nonparametric methods: Local and random windows are compared as the number of windows increases for short-range and graph-diameter-exceeding correlations.The experiments use stochastic block-model graphs with community-based local windows and equal-size random windows.
  • TC1. Nonparametric methods: The experiments compare filter-bank estimators using ideal bandpass filters and filters based on nearby graph frequencies.The filter-bank study evaluates how spectral grouping choices affect PSD estimation.
  • TC1. Nonparametric methods: Model mismatch degrades MA estimation, but the parametric estimates remain superior to the periodogram.The mismatch uses an assumed process order of L + 2 instead of L.
  • TC3. Real-world graphs with synthetic signals: Source-identification error decreases as more opinion observations are available, while higher noise worsens recovery; σ = 0.1 can remain comparable to the noiseless case.The experiment uses a 34-node karate-club graph and sparse rumor-source signals.
  • TC3. Real-world graphs with synthetic signals: The Wiener graph filter outperforms a regular low-pass graph filter, and both outperform the classical 2D Gaussian filter for face-image denoising.The Wiener filter exploits both the graph Fourier basis and PSD, whereas the low-pass filter exploits only the basis.
  • TC3. Real-world graphs with synthetic signals: Using the shift associated with faces with glasses recovers the glasses, whereas the shift associated with faces without glasses produces poorer recovery.The difference is interpreted through the image’s relative stationarity in the two shifts.
  • TC3. Real-world graphs with synthetic signals: Functional brain signals are approximately stationary in both functional and structural network bases, with θ = 99% and θ = 67%, respectively.The structural network basis was constructed independently of the observed functional signals.

VII. CONCLUSION

The paper develops equivalent graph-stationarity definitions, introduces PSD estimation methods, and studies nonparametric and parametric models. It also identifies diffusion settings where parametric estimation is tractable and illustrates the framework on synthetic and real-world signals.

  • VII. CONCLUSION: Graph stationary processes associated with normal shift operators admit several equivalent formulations and are diagonalized by the graph Fourier basis.The diagonalization supports defining a graph-domain power spectral density.
  • VII. CONCLUSION: The paper generalizes periodograms, window-based average periodograms, and filter banks to estimate graph power spectral densities.It also compares these methods with traditional time-domain schemes and identifies open issues in grouping graph nodes and frequencies.
  • VII. CONCLUSION: MA, AR, and ARMA models are studied as parametric estimators and as models for linear diffusion dynamics.Particular diffusion scenarios yield tractable optimal parameter-estimation problems.
  • VII. CONCLUSION: The periodogram estimator is unbiased under the stated realization and graph-Fourier assumptions.The conclusion follows from E[ˆppg] = p.

B. Proof of Prop. 4

The proof derives expressions (22) and (23) for the window-based estimator by expanding it across windows and evaluating Gaussian quadratic and quartic forms. Symmetry of S simplifies the final substitution.

  • B. Proof of Prop. 4: The derivation of expression (22) uses the diagonal covariance diag(p) and the elementwise product identity for ˜Wmm.The proof explicitly invokes E[·] covariance structure and the relation ˜Wmm = ˜Wm ◦ ˜W∗m.
  • B. Proof of Prop. 4: The diagonal entries of ΣW are sufficient to establish expression (23).The proof obtains these entries from the row-wise representation and concludes the derivation of (23).
  • B. Proof of Prop. 4: The estimator ˆpW is rewritten as a sum across the M windows.This expansion supports the subsequent row-wise and window-wise calculations.
  • B. Proof of Prop. 4: Each kth component is expressed using the kth row of ˜Wm and the corresponding quadratic form.The proof identifies [|ˆWm˜x|^2]k with a row-based expression before computing expectations.
  • B. Proof of Prop. 4: A Gaussian quartic-form calculation supplies the remaining expectation terms in the covariance derivation.The proof cites the fourth moment of a Gaussian with covariance diag(p).
  • B. Proof of Prop. 4: When S is symmetric, V is real and the second and third summands coincide before the final substitutions.This symmetry reduces the expression used to complete the proof.

C. Proof of Prop. 6

The proof obtains the expectation and variance formulas for a component of the estimator by rewriting its norm as a trace and evaluating the resulting Gaussian quartic form. For symmetric S, the trace term simplifies because V is real.

  • C. Proof of Prop. 6: The norm in (27) is rewritten as the trace of an outer product.This converts the estimator component into a trace expression suitable for moment calculations.
  • C. Proof of Prop. 6: The expectation in (28) follows from the diagonal covariance diag(p) and the trace identity for diagonal matrices.The trace of a product of diagonal matrices becomes the sum of entrywise products of their diagonals.
  • C. Proof of Prop. 6: The component ˆp˜qk is represented as tr[˜xHdiag(|˜qk|2)˜x] before computing its second moment.The proof then forms E[ˆp˜qk ˆp˜qk] using this scalar trace representation.
  • C. Proof of Prop. 6: The second-moment calculation reduces to a Gaussian quartic form and yields the terms shown in (65).The displayed result includes a squared weighted-power term and an additional trace term.
  • C. Proof of Prop. 6: For symmetric S, V is real and the trace term in (65) is equal to another term in the expression.This equality is used in simplifying the variance derivation.
Loading 1603.04667v2…