PaperlayerView exact revision on arXiv

Source-linked AI summary

Autoregressive Moving Average Graph Filtering

Elvin Isufi, Andreas Loukas, Andrea Simonetto, Geert Leus

arXiv:1602.04436v2cs.LGeess.SYstat.ML

TL;DR

Distributed graph filtering must handle broad frequency responses and changing graph signals or topologies without relying on graph-specific designs. The paper develops universal ARMA recursions with exact denoising and interpolation constructions, then extends them to joint graph-temporal filtering and time-varying graphs. The resulting filters approximate arbitrary desired responses, converge linearly under stability conditions, and support distributed operation in static and changing settings.

  • Problem

    Existing FIR graph filters are sensitive to time-varying signals and graphs, while prior ad-hoc autoregressive designs achieve only a limited subset of filtering objectives.

  • Method

    The paper designs universal parallel and periodic ARMA recursions whose coefficients are independent of the underlying graph and extends them to time-varying signals and graphs.

  • Results

    The ARMA filters approximate any desired graph frequency response, provide exact Tikhonov, Wiener, and interpolation solutions, and extend naturally to two-dimensional graph-time filtering.

  • Takeaways & Limitations

    ARMA graph filters provide distributed filtering applicable to unknown or changing graph structures while jointly processing graph-frequency and temporal-frequency content.

Abstract

from arXiv · show

One of the cornerstones of the field of signal processing on graphs are graph filters, direct analogues of classical filters, but intended for signals defined on graphs. This work brings forth new insights on the distributed graph filtering problem. We design a family of autoregressive moving average (ARMA) recursions, which (i) are able to approximate any desired graph frequency response, and (ii) give exact solutions for tasks such as graph signal denoising and interpolation. The design philosophy, which allows us to design the ARMA coefficients independently from the underlying graph, renders the ARMA graph filters suitable in static and, particularly, time-varying settings. The latter occur when the graph signal and/or graph are changing over time. We show that in case of a time-varying graph signal our approach extends naturally to a two-dimensional filter, operating concurrently in the graph and regular time domains. We also derive sufficient conditions for filter stability when the graph and signal are time-varying. The analytical and numerical results presented in this paper illustrate that ARMA graph filters are practically appealing for static and time-varying settings, as predicted by theoretical derivations.

I. INTRODUCTION

Distributed graph filtering addresses scalable processing of graph signals, but FIR methods are sensitive to changing signals and graph topologies. The paper develops universal ARMA filters that approximate prescribed responses independently of graph structure and extend to time-varying settings.

  • Motivation: FIR graph filters are sensitive to time-varying signals and graphs because their intermediate recursion steps cannot be computed exactly.FIR methods also require restarting a filter for each new input signal, increasing computation, message, and memory complexities.
  • Contributions: ARMA graph filters use graph-independent coefficients, making one design applicable across graph structures, including unknown or time-varying graphs.The coefficients are designed independently of the graph Laplacian eigenvalues.
  • Contributions: For time-varying graph signals, ARMA filters extend to two-dimensional filtering over graph-frequency and temporal-frequency domains.The paper also provides sufficient stability conditions when both graph topology and signal vary over time.
  • Contributions: The proposed distributed ARMA recursions approximate any desired graph frequency response and provide exact constructions for Tikhonov and Wiener denoising and smoothness-based interpolation.The filters use rational frequency responses and extend beyond the approximation-only solutions of earlier FIR approaches.
  • Preliminaries: Graph Fourier analysis represents graph signals using Laplacian eigenvectors, whose eigenvalues serve as graph frequencies for the filter response.The framework assumes a symmetric, local representation matrix with bounded spectral norm across the considered graph class.

III. ARMA GRAPH FILTERS

The paper constructs distributed ARMA graph filters from first-order recursions with rational frequency responses. These recursions converge linearly under stability conditions and can be implemented through local exchanges among neighboring nodes.

  • ARMA1: An ARMA1 recursion implements a first-order rational graph frequency response through local signal values and weighted neighbor exchanges.Each node updates its value using its local input and neighbors’ previous-iteration states.
  • ARMA1: H(λ) = c + r λ −p, subject to |p| > ϱ, with pole p = 1/ψ and residue r = −ϕ/ψ.The stability condition is tied to the spectral-radius bound of the graph representation matrix.
  • ARMA1: When |ψϱ| < 1, the ARMA1 recursion converges linearly to its frequency response regardless of initialization and graph Laplacian.The limiting response applies over the full bounded graph-frequency interval, not only one graph’s discrete spectrum.
  • Relation to FIR: ARMA1 outputs at finite time are equivalent to FIR filters with finite geometric coefficients, while ARMA implementations are more robust in time-varying scenarios.The equivalence connects recursive rational filtering with finite-time FIR behavior.

B. ARMAK graph filters

Higher-order ARMA graph filters are built either by running first-order filters in parallel or by varying coefficients periodically. The periodic design reduces memory requirements while retaining rational responses and linear convergence.

  • Parallel implementation: Parallel ARMAK combines K first-order ARMA filters to obtain a rational frequency response of order K.Its communication and memory costs scale by K relative to ARMA1.
  • Parallel implementation: Parallel ARMAK converges linearly regardless of its initial conditions and graph Laplacian, subject to its stability constraint.The response is expressed using residues and poles from the component ARMA1 filters.
  • Periodic implementation: Periodic ARMAK varies its coefficients with period K and produces a valid output every K iterations.This construction reuses state values rather than maintaining K parallel filter states.
  • Periodic implementation: Periodic ARMAK has rational frequency response of order K and converges linearly under its joint stability condition.Joint stability can hold even when some constituent ARMA1 filters are unstable, provided the relevant product condition is satisfied.
  • Complexity: Periodic implementation reduces memory complexity to O(M), compared with O(KM) for parallel ARMAK, while its communication complexity remains O(KM).The lower memory requirement suits resource-constrained devices.

IV. ARMA FILTER DESIGN

The paper designs ARMA graph filters by approximating target frequency responses with rational functions, then realizes them through parallel or periodic distributed recursions. The approach can approximate arbitrary responses while balancing accuracy, convergence, numerical stability, and communication complexity.

  • Filter approximation: Shanks’ method approximates a desired graph frequency response with rational numerator and denominator polynomials of order K.The coefficients are obtained through polynomial regression and coefficient-wise systems of equations.
  • Graph-specific design: ARMA filters use graph-frequency rational responses, so classical IIR design methods such as Butterworth and Chebyshev do not directly apply.Their stability constraint also differs from classical filter design because the rational variable is the graph frequency λ.
  • Stability: For a Butterworth-like response with K = 2, parallel filters are unstable whenever the cutoff frequency λc exceeds ϱ.The example has complex-conjugate poles at ±λc, showing that stability depends on the cutoff frequency.
  • Distributed realizations: Parallel and periodic implementations realize the rational response as distributed ARMA recursions with fast convergence and linear edge- and order-dependent message and memory requirements.The parallel design uses partial fractions, while the periodic design matches denominator roots and numerator coefficients.
  • Accuracy and complexity: Equal numerator and denominator orders provide the highest approximation accuracy for a given communication and memory complexity.Using a much higher approximation order ˆK can slightly improve accuracy but slows convergence and increases sensitivity to numerical errors; the paper sets ˆK = K + 1.
  • Empirical behavior: The proposed design method has no theoretical stability guarantees, although it consistently produced stable filters in the reported observations.Figure 1 compares ARMAK and corresponding-order FIR responses for step and window targets.

B. Exact and Universal Graph Filter Constructions

The paper constructs universal ARMA graph filters for denoising and interpolation without using a graph’s specific eigenvalues. These constructions provide exact or explicit solutions in selected problems, with stability and distributed-computability depending on the formulation.

  • Universal constructions: ARMA coefficients can be designed independently of graph Laplacian eigenvalues, making the resulting filters universal across graph structures.This independence is presented as particularly useful when the graph structure is unknown or changing.
  • Tikhonov-based denoising: Tikhonov denoising minimizes data disagreement plus a graph-smoothness penalty based on a quadratic form of L^K.The regularization weight w controls the trade-off between fidelity to the noisy signal and smoothness.
  • Tikhonov-based denoising: The denoising solution can be approximated by ARMAK filters, whose poles satisfy K√wϱ < 1 for the unshifted formulation.Shifted Laplacians provide a notable improvement in filter stability under the corresponding condition.
  • Tikhonov-based denoising: For the shifted normalized Laplacian, the stability condition is always met for K = 1 and K = 2 under the stated standard choices.These correspond to quadratic regularization and total variation, respectively.
  • Wiener-based denoising: When signal and noise covariance spectra are rational functions of λ of order K, the Wiener filter corresponds to an ARMAK graph filter.The resulting coefficients depend on the rational covariance functions, not on the graph’s specific Laplacian eigenvalues.
  • Wiener-based denoising: For a smooth-signal covariance model with white noise, the Wiener construction is identical to Tikhonov denoising for K = 1 and yields an always-stable ARMA1 implementation.The paper cautions that stability is not necessarily guaranteed for every covariance matrix and must be checked problem-specifically.
  • Graph signal interpolation: Graph interpolation with K = 1 is represented by an ARMA1 filter, whereas larger K cannot be computed distributively because the basis matrix lacks an appropriate local factorization.The interpolation problem assumes a signal smooth with respect to the discrete or normalized Laplacian.

V. TIME-VARIATIONS

The paper examines whether ARMA graph-filter properties persist when graph signals or graph topologies vary over time. It characterizes temporal behavior and addresses simultaneous variation in both signal and graph.

  • Scope: The time-variation analysis covers changing graph signals and changing graph topologies after characterizing filtering and convergence for static inputs.The paper treats these cases separately in the subsequent analysis.

A. Joint Graph and Temporal Filters

The ARMA recursions extend graph filtering into a joint graph–temporal frequency domain, while retaining distinct parallel and periodic implementations. Their temporal behavior depends on graph frequency, with parallel concatenation offering greater stability under temporal dynamics.

  • Joint graph and temporal characterization: ARMA graph filters operate simultaneously in graph and temporal frequency domains for time-varying graph signals.The graph dimension uses the graph Fourier transform, while the temporal dimension uses the Z-transform.
  • Joint graph and temporal characterization: The joint transfer function completely characterizes parallel and periodic ARMA_K implementations, which are ARMA_K filters in both domains.The higher-order results are subject to the respective static stability conditions.
  • Frequency-response interpretation: Temporal frequencies are normalized so that f = 0 recovers the standard graph frequency response.Figure 3 uses a third-order filter approximating an ideal low-pass response with λc = 0.5.
  • Frequency-response interpretation: Both implementations preserve nearly the static response for low temporal variations f ≤1/8, whereas graph frequencies near λ = 1 damp all temporal frequencies.The damping phenomenon is attributed to the shifted Laplacian design and multiplicative pole relationships.
  • Stability under temporal variation: Parallel concatenation is more stable than periodic implementation under temporal dynamics, whose output can blow up by an order of magnitude beyond f = 1/8.The comparison is reported for λ = 0 and λ = 2; periodic instability is linked to poles approaching the unit circle.

B. Time-Varying Graphs and Signals

The paper develops a joint representation for time-varying graph topologies and signals, enabling frequency analysis beyond any single Laplacian. Under boundedness conditions, ARMA outputs remain stable and approach time-varying solutions with exponentially decreasing error.

  • Universal design: The proposed coefficients can preserve a desired frequency response across different graph realizations because they are designed independently of the underlying graph.This universal design addresses changes in graph topology without redesigning coefficients.
  • Frequency characterization: A decomposition basis exists for time-varying graph filters and depends only on the sequence of graph realizations.In this basis, ARMA1 and parallel ARMAK filters retain the static-case frequency response.
  • Time-varying graph representation: A single Laplacian spectrum is insufficient because the filter output depends on the entire sequence of graph realizations.The paper therefore defines a joint Laplacian that encompasses the individual time-indexed Laplacians.
  • Time-varying graph representation: The constructed time-varying graph replicates each node across timesteps and connects neighbors across consecutive times, encoding topology and one-step information delays.This construction captures both changing graph structure and temporal relations between graph signals.
  • Stability and convergence: For shifted normalized Laplacians, sufficient stability conditions are |ψ| < 2 for the unnormalized case and |ψ| < 1 for the normalized case.The condition follows from bounding the Laplacian operators and their eigenvalues.
  • Stability and convergence: ARMA outputs do not diverge when graph Laplacians have uniformly bounded spectral norm, and the distance between outputs decreases exponentially.The result extends from ARMA1 to general ARMAK filters through parallel sums or periodic cycles.

VI. NUMERICAL RESULTS

The numerical section studies ARMA filters on fixed and time-varying graphs and signals, including comparison with universal FIR filters in the jointly time-varying case.

  • Numerical results: Two case studies evaluate ARMA performance: one with a fixed graph and time-varying signal, and another with both graph and signal varying.The latter compares ARMA with state-of-the-art FIR filters designed universally.
  • Numerical results: The first case study examines signals containing spectral content in both graph and temporal frequency domains.The second case study evaluates performance when graph topology and graph signals are time-varying.

A. Variations on the Graph Signal

The experiments test ARMA5 filtering of time-varying graph signals under correlated and uncorrelated interference plus noise. The results show temporal-frequency attenuation and decreasing output-spectrum error.

  • Experimental setup: The setup uses a 0.5-bandlimited signal oscillating at π/10, interference at 9π/10, and i.i.d. Gaussian noise with variance σ2 = 0.1.A parallel ARMA5 filter approximates a graph-domain low-pass response with cut-off λc = 0.5 while attenuating high temporal frequencies.
  • Correlated signal interference: Correlated interference shares the signal’s graph spectrum but oscillates at a higher temporal frequency, causing the corrupted input to lose its bandlimited appearance.The interference is self-induced and shares the graph spectrum of the signal at each instant.
  • Correlated signal interference: 13 dB: the output’s content at the interfering frequency 9π/10 is attenuated relative to its main temporal-frequency content at π/10.Figure 5 reports average time spectral content over all nodes, normalized to the maximum.
  • Uncorrelated signal interference: For uncorrelated interference, the study compares ARMA5 output against both the interference-free target and the output produced without interference.The first error includes noise and interference relative to the desired signal, while the second isolates interference effects.
  • Uncorrelated signal interference: After a few iterations, the error becomes relatively small, indicating that interference-affected and interference-free output spectra become similar.Figure 6 evaluates the ARMA recursion under a time-varying input affected by uncorrelated interference.
  • Interpretation: The two-dimensional ARMA behavior enables attenuation at a selected graph/temporal frequency and separation of signals that are orthogonal in temporal frequency.The recursion can preserve the graph response for low temporal oscillations while attenuating high temporal frequencies.

B. Variations on the Graph Topology

The experiments examine denoising and low-pass approximation under static and time-varying graph conditions. ARMA filters generally outperform analogous FIR filters, while higher order can worsen approximation under mobility because convergence slows.

  • Exact design (denoising): The study compares denoising performance under random edge failures and static topology, using ARMA1 alongside FIR graph filters.The denoising simulation uses edge-down probability p = 0.05 and combines a smooth signal with i.i.d. Gaussian noise.
  • Exact design (denoising): ARMA achieves lower denoising error than the optimization solution’s FIR approximations on both random time-varying and static graphs.It matches the analytical solution on static graphs and approximates it well when the graph is randomly generated.
  • Time-varying graph, constant graph signal: ARMA filters outperform analogous FIR filters as graph mobility increases, although approximation error rises with node speed.Higher-order ARMA filters improve static-graph approximation but can become rough under mobility because convergence slows and poles approach the unit circle.
  • Time-varying graph and graph signal: When both topology and graph signal vary, errors increase with speed and exceed those in the topology-only setting.ARMA remains better than analogous FIR filters except for K = 2 at zero speed, identified as an artifact of Shanks’ method.
  • Conclusions: The paper concludes that distributed ARMA filters approximate arbitrary graph responses and solve denoising and interpolation tasks in static and varying settings.The approach also extends to joint graph- and time-frequency filtering, with convergence guaranteed under characterized time-varying conditions.
  • Conclusions: Stable analytical design methods for one- and two-dimensional ARMA recursions remain future work.The authors also propose studying separable two-dimensional filters for disjoint design in graph and temporal domains.

APPENDIX Table I

The appendix presents coefficient tables and derivation material for parallel and periodic ARMA filters. These passages connect recursion stability and transform-based derivations to rational graph and joint transfer functions.

  • APPENDIX Table I: The time-invariant system uses Γt = θtI + ψtL and a backward product ΦΓ to represent accumulated time-varying recursion effects.The output at the end of each period can be rewritten as a time-invariant system.
  • APPENDIX Table I: If the maximum eigenvalue of A satisfies |λmax(A)| < 1, the recursion converges linearly to its steady state.The convergence rate is |λmax(A)|, and the stability condition follows from convergence of the state recursion.
  • APPENDIX Table I: Parallel ARMAK stacks K ARMA1 states, with Ψ, ϕ, and the graph Laplacian defining the state update and output.The recursion is expressed compactly with a Kronecker product.
  • APPENDIX Table I: Table I lists residues and poles for parallel ARMAK filters with K = 3, 5, and 7.Higher-order filters are omitted from the table due to space considerations.
  • APPENDIX Table I: Applying the Z-transform and graph Fourier transform yields the filter’s closed-form joint transfer function.The derivation uses Kronecker-product identities and geometric-series properties.

Proof of Theorem 5

The proof expands the periodic ARMA recursion for time-varying inputs, isolates graph-frequency components, and derives the joint transfer function. Stability permits transient terms to vanish in the long-run expression.

  • Proof of Theorem 5: Expanding the recursion gives the period-end output as a state term plus a scaled input term.The formulation uses Γt and the backward product ΦΓ to capture the periodic recursion across periods.
  • Proof of Theorem 5: Under the theorem’s stability condition, the transient state term approaches zero for sufficiently large periods.This allows the steady-state transfer behavior to be derived without the initial-state contribution.
  • Proof of Theorem 5: Restricting the input to a Laplacian eigenvector reduces the recursion to a scalar graph-frequency component.The input, state, and output share the eigenvector φ, with λ denoting its associated eigenvalue.
  • Proof of Theorem 5: Taking the Z-transform and exploiting coefficient periodicity groups repeated period terms into a closed-form frequency-domain expression.The resulting limit is assembled from the transformed periodic recursion.
  • Proof of Theorem 5: The derivation obtains the joint transfer function and, after normalization, establishes the claimed response formula.The proof first rearranges the numerator, then applies norm inequalities and eigenvalue bounds to derive the error bound.
  • Proof of Theorem 5: The approximation error bound follows by dividing the closed-form bound by xmax and adjusting the indices.The bound uses |ψϱ| < 1 and the uniform input constraint ∥xt∥ ≤ xmax.
Loading 1602.04436v2…