Filtering Random Graph Processes Over Random Time-Varying Graphs
arXiv:1705.00442 · doi:10.1109/TSP.2017.2706186
Abstract
Graph filters play a key role in processing the graph spectra of signals supported on the vertices of a graph. However, despite their widespread use, graph filters have been analyzed only in the deterministic setting, ignoring the impact of stochastic- ity in both the graph topology as well as the signal itself. To bridge this gap, we examine the statistical behavior of the two key filter types, finite impulse response (FIR) and autoregressive moving average (ARMA) graph filters, when operating on random time- varying graph signals (or random graph processes) over random time-varying graphs. Our analysis shows that (i) in expectation, the filters behave as the same deterministic filters operating on a deterministic graph, being the expected graph, having as input signal a deterministic signal, being the expected signal, and (ii) there are meaningful upper bounds for the variance of the filter output. We conclude the paper by proposing two novel ways of exploiting randomness to improve (joint graph-time) noise cancellation, as well as to reduce the computational complexity of graph filtering. As demonstrated by numerical results, these methods outperform the disjoint average and denoise algorithm, and yield a (up to) four times complexity redution, with very little difference from the optimal solution.
References in corpus (13)
- The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
- Discrete Signal Processing on Graphs
- Opinion fluctuations and disagreement in social networks
- Autoregressive Moving Average Graph Filtering
- Stationary signal processing on graphs
- Stationary Graph Processes and Spectral Estimation
- Graph Frequency Analysis of Brain Signals
- Kernel-based Reconstruction of Graph Signals
- Chebyshev Polynomial Approximation for Distributed Signal Processing
- Adaptive Least Mean Squares Estimation of Graph Signals
- Reconstruction of Graph Signals through Percolation from Seeding Nodes
- Distributed Autoregressive Moving Average Graph Filters
- Distributed Linear Network Operators using Graph Filters
Cited by in corpus (15)
- Graph signal processing for machine learning: A review and new perspectives
- Advances in Distributed Graph Filtering
- Grid-Graph Signal Processing (Grid-GSP): A Graph Signal Processing Framework for the Power Grid
- A Hilbert Space Theory of Generalized Graph Signal Processing
- Tensor Graph Convolutional Networks for Multi-relational and Robust Learning
- Stochastic Graph Neural Networks
- Controllability of Bandlimited Graph Processes Over Random Time Varying Graphs
- Observing and Tracking Bandlimited Graph Processes
- Learning Stochastic Graph Neural Networks with Constrained Variance
- Modelling Graph Errors: Towards Robust Graph Signal Processing
- Stability of Graph Convolutional Neural Networks to Stochastic Perturbations
- On the Stability of Graph Convolutional Neural Networks under Edge Rewiring
- Online Distributed Learning over Graphs with Multitask Graph-Filter Models
- Sampling Policy Design for Tracking Time-Varying Graph Signals with Adaptive Budget Allocation
- Fast Decentralized Linear Functions Over Edge Fluctuating Graphs