# Filtering Random Graph Processes Over Random Time-Varying Graphs

arXiv: https://arxiv.org/abs/1705.00442 · HTML: https://mlsanity.com/paper/1705.00442/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 May 2017.

## Built on by (most cited first, 8 of 8)

- [Graph Filters for Signal Processing and Machine Learning on Graphs](https://mlsanity.com/paper/2211.08854/) (2022)
- [Stability of Graph Convolutional Neural Networks to Stochastic Perturbations](https://mlsanity.com/paper/2106.10526/) (2021)
- [Synthesizing Decentralized Controllers with Graph Neural Networks and Imitation Learning](https://mlsanity.com/paper/2012.14906/) (2020)
- [Learning Stochastic Graph Neural Networks with Constrained Variance](https://mlsanity.com/paper/2201.12611/) (2022)
- [Framelet Message Passing](https://mlsanity.com/paper/2302.14806/) (2023)
- [Real-Time Risky Fault-Chain Search using Time-Varying Graph RNNs](https://mlsanity.com/paper/2503.09775/) (2025)
- [Quantitative Error Feedback for Quantization Noise Reduction of Filtering over Graphs](https://mlsanity.com/paper/2506.01404/) (2025)
- [Stochastic Sequential Decision Making over Expanding Networks with Graph Filtering](https://mlsanity.com/paper/2603.19501/) (2026)

## Abstract (arXiv)

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.