Rey, SamuelDas, BishwadeepIsufi, Elvin2025-02-172025-02-172025-01-27S. Rey, B. Das and E. Isufi, "Online Learning Of Expanding Graphs," in IEEE Open Journal of Signal Processing, doi: 10.1109/OJSP.2025.35346922644-1322https://hdl.handle.net/10115/76737This work was partially supported by the the Spanish AEI Grants PID2022-136887NB-I00, TED2021-130347B-I00, PID2023-149457OB-I00, the EU H2020 Grant Tailor (No 952215, agreement 99), the Community of Madrid (Madrid ELLIS Unit). TU Delft AI Labs programme, the NWO OTP GraSPA proposal #19497, and the NWO VENI proposal 222.032This 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 delaysensitive 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.en-USAttribution 4.0 Internationalhttp://creativecommons.org/licenses/by/4.0/Topology inferenceDynamic graph learningOnline graph learningExpanding graphsgraph signal processingArticle10.1109/OJSP.2025.3534692info:eu-repo/semantics/openAccess