# Online Learning Of Expanding Graphs

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

## Key facts

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

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

- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [How to learn a graph from smooth signals](https://mlsanity.com/paper/1601.02513/) (2016)
- [Learning graphs from data: A signal representation perspective](https://mlsanity.com/paper/1806.00848/) (2018)
- [Connecting the Dots: Identifying Network Structure via Graph Signal Processing](https://mlsanity.com/paper/1810.13066/) (2018)
- [Network Topology Inference from Spectral Templates](https://mlsanity.com/paper/1608.03008/) (2016)
- [Network Inference via the Time-Varying Graphical Lasso](https://mlsanity.com/paper/1703.01958/) (2017)
- [Graph Filters for Signal Processing and Machine Learning on Graphs](https://mlsanity.com/paper/2211.08854/) (2022)
- [New Bounds for Matrix Multiplication: from Alpha to Omega](https://mlsanity.com/paper/2307.07970/) (2023)
- [Learning by Transference: Training Graph Neural Networks on Growing Graphs](https://mlsanity.com/paper/2106.03693/) (2021)
- [Learning Graphs from Smooth and Graph-Stationary Signals with Hidden Variables](https://mlsanity.com/paper/2111.05588/) (2021)
- [Online Topology Inference from Streaming Stationary Graph Signals with Partial Connectivity Information](https://mlsanity.com/paper/2007.03653/) (2020)
- [Robust Graph Filter Identification and Graph Denoising from Signal Observations](https://mlsanity.com/paper/2210.08488/) (2022)
- [Learning Undirected Graphs in Financial Markets](https://mlsanity.com/paper/2005.09958/) (2020)
- [Online Discriminative Graph Learning from Multi-Class Smooth Signals](https://mlsanity.com/paper/2101.00184/) (2021)
- [Joint Network Topology Inference in the Presence of Hidden Nodes](https://mlsanity.com/paper/2306.17364/) (2023)
- [Learning Time-Varying Graphs from Online Data](https://mlsanity.com/paper/2110.11017/) (2021)
- [Time-Varying Graph Learning with Constraints on Graph Temporal Variation](https://mlsanity.com/paper/2001.03346/) (2020)
- [Enhanced graph-learning schemes driven by similar distributions of motifs](https://mlsanity.com/paper/2207.04747/) (2022)
- [Fair GLASSO: Estimating Fair Graphical Models with Unbiased Statistical Behavior](https://mlsanity.com/paper/2406.09513/) (2024)
- [State-Space Network Topology Identification from Partial Observations](https://mlsanity.com/paper/1906.10471/) (2019)
- [Polynomial Graphical Lasso: Learning Edges from Gaussian Graph-Stationary Signals](https://mlsanity.com/paper/2404.02621/) (2024)
- [Recursive Prediction of Graph Signals with Incoming Nodes](https://mlsanity.com/paper/1911.11542/) (2019)
- [Joint inference of multiple graphs with hidden variables from stationary graph signals](https://mlsanity.com/paper/2110.03666/) (2021)
- [Online Joint Topology Identification and Signal Estimation from Streams with Missing Data](https://mlsanity.com/paper/2012.05957/) (2020)
- [Dual-based Online Learning of Dynamic Network Topologies](https://mlsanity.com/paper/2211.07449/) (2022)
- [Online Filtering over Expanding Graphs](https://mlsanity.com/paper/2301.06898/) (2023)
- [Online Graph Learning in Dynamic Environments](https://mlsanity.com/paper/2110.05023/) (2021)

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

- [Enhancing Graphical Lasso: A Robust Scheme for Non-Stationary Mean Data](https://mlsanity.com/paper/2503.19651/) (2025)
- [Non-negative DAG Learning from Time-Series Data](https://mlsanity.com/paper/2512.07267/) (2025)

## Abstract (arXiv)

This paper addresses the problem of online network topology inference for expanding graphs from a stream of spatiotemporal signals. Online algorithms for dynamic graph learning are crucial in delay-sensitive applications or when changes in topology occur rapidly. While existing works focus on inferring the connectivity within a fixed set of nodes, in practice, the graph can grow as new nodes join the network. This poses additional challenges like modeling temporal dynamics involving signals and graphs of different sizes. This growth also increases the computational complexity of the learning process, which may become prohibitive. To the best of our knowledge, this is the first work to tackle this setting. We propose a general online algorithm based on projected proximal gradient descent that accounts for the increasing graph size at each iteration. Recursively updating the sample covariance matrix is a key aspect of our approach. We introduce a strategy that enables different types of updates for nodes that just joined the network and for previously existing nodes. To provide further insights into the proposed method, we specialize it in Gaussian Markov random field settings, where we analyze the computational complexity and characterize the dynamic cumulative regret. Finally, we demonstrate the effectiveness of the proposed approach using both controlled experiments and real-world datasets from epidemic and financial networks.