# Online Filtering over Expanding Graphs

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 27 references that are in the map.
- First posted on arXiv 17 Jan 2023.

## Builds on (most cited first, 13 of 13)

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [Graphs, Convolutions, and Neural Networks: From Graph Filters to Graph Neural Networks](https://mlsanity.com/paper/2003.03777/) (2020)
- [Discrete Signal Processing on Graphs: Frequency Analysis](https://mlsanity.com/paper/1307.0468/) (2013)
- [Attributed Network Embedding for Learning in a Dynamic Environment](https://mlsanity.com/paper/1706.01860/) (2017)
- [A Class of Prediction-Correction Methods for Time-Varying Convex Optimization](https://mlsanity.com/paper/1509.05196/) (2015)
- [Advances in Distributed Graph Filtering](https://mlsanity.com/paper/1808.03004/) (2018)
- [Online Graph-Adaptive Learning with Scalability and Privacy](https://mlsanity.com/paper/1812.00974/) (2018)
- [Recursive Prediction of Graph Signals with Incoming Nodes](https://mlsanity.com/paper/1911.11542/) (2019)
- [Graph filtering over expanding graphs](https://mlsanity.com/paper/2203.08058/) (2022)
- [Localized Iterative Methods for Interpolation in Graph Structured Data](https://mlsanity.com/paper/1310.2646/) (2013)
- [Learning Expanding Graphs for Signal Interpolation](https://mlsanity.com/paper/2203.07966/) (2022)

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

- [Online Learning Of Expanding Graphs](https://mlsanity.com/paper/2409.08660/) (2024)
- [Online Graph Filtering Over Expanding Graphs](https://mlsanity.com/paper/2409.07204/) (2024)

## Abstract (arXiv)

Data processing tasks over graphs couple the data residing over the nodes with the topology through graph signal processing tools. Graph filters are one such prominent tool, having been used in applications such as denoising, interpolation, and classification. However, they are mainly used on fixed graphs although many networks grow in practice, with nodes continually attaching to the topology. Re-training the filter every time a new node attaches is computationally demanding; hence an online learning solution that adapts to the evolving graph is needed. We propose an online update of the filter, based on the principles of online machine learning. To update the filter, we perform online gradient descent, which has a provable regret bound with respect to the filter computed offline. We show the performance of our method for signal interpolation at the incoming nodes. Numerical results on synthetic and graph-based recommender systems show that the proposed approach compares well to the offline baseline filter while outperforming competitive approaches. These findings lay the foundation for efficient filtering over expanding graphs.