More Like this

1. Online proximal gradient for learning graphs from streaming signals

   https://doi.org/10.23919/Eusipco47968.2020.9287550  

   Shafipour, Rasoul ; Mateos, Gonzalo ( January 2021 , 2020 28th European Signal Processing Conference (EUSIPCO))

   null (Ed.)

   We leverage proximal gradient iterations to develop an online graph learning algorithm from streaming network data. Our goal is to track the (possibly) time-varying network topology, and effect memory and computational savings by processing the data on-the-fly as they are acquired. The setup entails observations modeled as stationary graph signals generated by local diffusion dynamics on the unknown network. Moreover, we may have a priori information on the presence or absence of a few edges as in the link prediction problem. The stationarity assumption implies that the observations' covariance matrix and the so-called graph shift operator (GSO - a matrix encoding the graph topology) commute under mild requirements. This motivates formulating the topology inference task as an inverse problem, whereby one searches for a (e.g., sparse) GSO that is structurally admissible and approximately commutes with the observations' empirical covariance matrix. For streaming data said covariance can be updated recursively, and we show online proximal gradient iterations can be brought to bear to efficiently track the time-varying solution of the inverse problem with quantifiable guarantees. Specifically, we derive conditions under which the GSO recovery cost is strongly convex and use this property to prove that the online algorithm converges to within a neighborhood of the optimal time-varying batch solution. Preliminary numerical tests illustrate the effectiveness of the proposed graph learning approach in adapting to streaming information and tracking changes in the sought dynamic network. 

   more » « less
2. Online Topology Inference from Streaming Stationary Graph Signals

   https://doi.org/10.1109/DSW.2019.8755560  

   Shafipour, Rasoul ; Hashemi, Abolfazl ; Mateos, Gonzalo ; Vikalo, Haris ( June 2019 , 2019 IEEE Data Science Workshop (DSW))

   We address the problem of online topology inference from streaming nodal observations of graph signals generated by linear diffusion dynamics on the sought graph. To that end, we leverage the stationarity of the signals and use the so-called graph-shift operator (GSO) as a matrix representation of the graph. Under this model, estimated covariance eigenvectors obtained from streaming independent graph signals diffused on the sought network are a valid estimator of the GSO's spectral templates. We develop an ADMM algorithm to find a sparse and structurally admissible GSO given the eigenvectors estimate. Then, we propose an online scheme that upon sensing new diffused observations, efficiently updates eigenvectors (thus makes more accurate on expectation) and performs only one or a few iterations of the mentioned ADMM until the new data is observed. Numerical tests illustrate the effectiveness of the proposed topology inference approach in recovering large scale graphs, adapting to streaming information, and accommodating changes in the sought network. 

   more » « less
3. Online Network Topology Inference with Partial Connectivity Information

   https://doi.org/10.1109/CAMSAP45676.2019.9022677  

   Shafipour, Rasoul ; Mateos, Gonzalo ( December 2019 , 2019 IEEE 8th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP))

   We develop algorithms for online topology inference from streaming nodal observations and partial connectivity information; i.e., a priori knowledge on the presence or absence of a few edges may be available as in the link prediction problem. The observations are modeled as stationary graph signals generated by local diffusion dynamics on the unknown network. Said stationarity assumption implies the simultaneous diagonalization of the observations' covariance matrix and the so-called graph shift operator (GSO), here the adjacency matrix of the sought graph. When the GSO eigenvectors are perfectly obtained from the ensemble covariance, we examine the structure of the feasible set of adjacency matrices and its dependency on the prior connectivity information available. In practice one can only form an empirical estimate of the covariance matrix, so we develop an alternating algorithm to find a sparse GSO given its imperfectly estimated eigenvectors. Upon sensing new diffused observations in the streaming setting, we efficiently update eigenvectors and perform only one (or a few) online iteration(s) of the proposed algorithm until a new datum is observed. Numerical tests showcase the effectiveness of the novel batch and online algorithms in recovering real-world graphs. 

   more » « less
4. Online Graph Learning under Smoothness Priors

   https://doi.org/10.23919/EUSIPCO54536.2021.9616123  

   Saboksayr, Seyed Saman ; Mateos, Gonzalo ; Cetin, Mujdat ( August 2021 , 2021 29th European Signal Processing Conference (EUSIPCO))

   The growing success of graph signal processing (GSP) approaches relies heavily on prior identification of a graph over which network data admit certain regularity. However, adaptation to increasingly dynamic environments as well as demands for real-time processing of streaming data pose major challenges to this end. In this context, we develop novel algorithms for online network topology inference given streaming observations assumed to be smooth on the sought graph. Unlike existing batch algorithms, our goal is to track the (possibly) time-varying network topology while maintaining the memory and computational costs in check by processing graph signals sequentially-in-time. To recover the graph in an online fashion, we leverage proximal gradient (PG) methods to solve a judicious smoothness-regularized, time-varying optimization problem. Under mild technical conditions, we establish that the online graph learning algorithm converges to within a neighborhood of (i.e., it tracks) the optimal time-varying batch solution. Computer simulations using both synthetic and real financial market data illustrate the effectiveness of the proposed algorithm in adapting to streaming signals to track slowly-varying network connectivity. 

   more » « less
5. Dual-Based Online Learning of Dynamic Network Topologies

   https://doi.org/10.1109/ICASSP49357.2023.10096392  

   Saboksayr, Seyed Saman ; Mateos, Gonzalo ( June 2023 , ICASSP 2023 - 2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP))

   We investigate online network topology identification from smooth nodal observations acquired in a streaming fashion. Different from non-adaptive batch solutions, our distinctive goal is to track the (possibly) dynamic adjacency matrix with affordable memory and computational costs by processing signal snapshots online. To this end, we leverage and truncate dual-based proximal gradient (DPG) iterations to solve a composite smoothness-regularized, time-varying inverse problem. Numerical tests with synthetic and real electrocorticography data showcase the effectiveness of the novel lightweight iterations when it comes to tracking slowly-varying network connectivity. We also show that the online DPG algorithm converges faster than a primal-based baseline of comparable complexity. Aligned with reproducible research practices, we share the code developed to produce all figures included in this paper. 

   more » « less