More Like this

1. Online Topology Inference from Streaming Stationary Graph Signals with Partial Connectivity Information

   https://doi.org/10.3390/a13090228  

   Shafipour, Rasoul; Mateos, Gonzalo (September 2020, Algorithms)

   null (Ed.)

   We develop online graph learning algorithms from streaming network data. Our goal is to track the (possibly) time-varying network topology, and affect 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 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. 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 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
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 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
5. Delay Embedding for Matrix Graphical Model Learning from Dependent Data

   https://doi.org/10.1109/ICASSP48485.2024.10447097  

   Tugnait, Jitendra K (April 2024, IEEE)

   We consider the problem of inferring the conditional independence graph (CIG) of a sparse, high-dimensional, stationary matrix-variate Gaussian time series. The correlation function of the matrix series is Kronecker-decomposable. Unlike most past work on matrix graphical models, where independent and identically distributed (i.i.d.) observations of matrix-variate are assumed to be available, we allow time-dependent observations. We follow a time-delay embedding approach where with each matrix node, we associate a random vector consisting of a scalar series component and its time-delayed copies. A group-lasso penalized negative pseudo log-likelihood (NPLL) objective function is formulated to estimate a Kronecker-decomposable covariance matrix which allows for inference of the underlying CIG. The NPLL function is bi-convex and the Kronecker-decomposable covariance matrix is estimated via flip-flop optimization of the NPLL function. Each iteration of flip-flop optimization is solved via an alternating direction method of multipliers (ADMM) approach. Numerical results illustrate the proposed approach which outperforms an existing i.i.d. modeling based approach as well as an existing frequency-domain approach for dependent data, in correctly detecting the graph edges. 

   more » « less