{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T19:20:05Z","timestamp":1776885605641,"version":"3.51.2"},"reference-count":52,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2020,9,9]],"date-time":"2020-09-09T00:00:00Z","timestamp":1599609600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1750428"],"award-info":[{"award-number":["CCF-1750428"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["ECCS-1809356"],"award-info":[{"award-number":["ECCS-1809356"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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\u2019 covariance matrix and the so-called graph shift operator (GSO\u2014a 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\u2019 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.<\/jats:p>","DOI":"10.3390\/a13090228","type":"journal-article","created":{"date-parts":[[2020,9,9]],"date-time":"2020-09-09T09:01:09Z","timestamp":1599642069000},"page":"228","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":30,"title":["Online Topology Inference from Streaming Stationary Graph Signals with Partial Connectivity Information"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2996-2671","authenticated-orcid":false,"given":"Rasoul","family":"Shafipour","sequence":"first","affiliation":[{"name":"Microsoft, Redmond, WA 98052, USA"},{"name":"Department of Electrical and Computer Engineering, University of Rochester, Rochester, NY 14627, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9847-6298","authenticated-orcid":false,"given":"Gonzalo","family":"Mateos","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, University of Rochester, Rochester, NY 14627, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,9,9]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Kolaczyk, E.D. (2009). Statistical Analysis of Network Data: Methods and Models, Springer.","DOI":"10.1007\/978-0-387-88146-1"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1109\/MSP.2014.2327238","article-title":"Modeling and optimization for big data analytics: (Statistical) learning tools for our era of data deluge","volume":"31","author":"Slavakis","year":"2014","journal-title":"IEEE Signal Process. Mag."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"808","DOI":"10.1109\/JPROC.2018.2820126","article-title":"Graph signal processing: Overview, challenges and applications","volume":"106","author":"Ortega","year":"2018","journal-title":"Proc. IEEE"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1109\/MSP.2018.2890143","article-title":"Connecting the dots: Identifying network structure via graph signal processing","volume":"36","author":"Mateos","year":"2019","journal-title":"IEEE Signal Process. Mag."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1109\/MSP.2018.2887284","article-title":"Learning graphs from data: A signal representation perspective","volume":"36","author":"Dong","year":"2019","journal-title":"IEEE Signal Process. Mag."},{"key":"ref_6","first-page":"467","article-title":"Network topology inference from spectral templates","volume":"3","author":"Segarra","year":"2017","journal-title":"IEEE Trans. Signal Inf. Process. Netw."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"5911","DOI":"10.1109\/TSP.2017.2739099","article-title":"Stationary graph processes and spectral estimation","volume":"65","author":"Marques","year":"2017","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"3462","DOI":"10.1109\/TSP.2017.2690388","article-title":"Stationary signal processing on graphs","volume":"65","author":"Perraudin","year":"2017","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Girault, B. (September, January 31). Stationary graph signals using an isometric graph translation. Proceedings of the 2015 23rd European Signal Processing Conference (EUSIPCO), Nice, France.","DOI":"10.1109\/EUSIPCO.2015.7362637"},{"key":"ref_10","first-page":"481","article-title":"Characterization and inference of graph diffusion processes from observations of stationary signals","volume":"4","author":"Pasdeloup","year":"2018","journal-title":"IEEE Trans. Signal Inf. Process. Netw."},{"key":"ref_11","first-page":"123","article-title":"Proximal algorithms","volume":"1","author":"Parikh","year":"2014","journal-title":"Found. Trends Optim."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1137\/080716542","article-title":"A fast iterative shrinkage-thresholding algorithm for linear inverse problems","volume":"2","author":"Beck","year":"2009","journal-title":"SIAM J. Imag. Sci."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Shafipour, R., Hashemi, A., Mateos, G., and Vikalo, H. (2019, January 2\u20135). Online topology inference from streaming stationary graph signals. Proceedings of the 2019 IEEE Data Science Workshop (DSW), Minneapolis, MN, USA.","DOI":"10.1109\/DSW.2019.8755560"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Shafipour, R., and Mateos, G. (2019, January 15\u201318). Online network topology inference with partial connectivity information. Proceedings of the 2019 IEEE 8th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP), Le gosier, Guadeloupe.","DOI":"10.1109\/CAMSAP45676.2019.9022677"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Ahmed, T., and Bajwa, W.U. (2017, January 10\u201313). Correlation-based ultra high-dimensional variable screening. Proceedings of the 2017 IEEE 7th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP), Curacao, Netherlands Antilles.","DOI":"10.1109\/CAMSAP.2017.8313129"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Madden, L., Becker, S., and Dall\u2019Anese, E. (2019, January 2\u20135). Online sparse subspace clustering. Proceedings of the 2019 IEEE Data Science Workshop (DSW), Minneapolis, MN, USA.","DOI":"10.1109\/DSW.2019.8755556"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"157","DOI":"10.2307\/2528966","article-title":"Covariance selection","volume":"28","author":"Dempster","year":"1972","journal-title":"Biometrics"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"432","DOI":"10.1093\/biostatistics\/kxm045","article-title":"Sparse inverse covariance estimation with the graphical lasso","volume":"9","author":"Friedman","year":"2008","journal-title":"Biostatistics"},{"key":"ref_19","unstructured":"Lake, B.M., and Tenenbaum, J.B. (2010, January 11\u201314). Discovering structure by learning sparse graphs. Proceedings of the 32nd Annual Meeting of the Cognitive Science Society (CogSci 2010), Portland, OR, USA."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"825","DOI":"10.1109\/JSTSP.2017.2726975","article-title":"Graph learning from data under Laplacian and structural constraints","volume":"11","author":"Egilmez","year":"2017","journal-title":"IEEE J. Sel. Top. Signal Process."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"1436","DOI":"10.1214\/009053606000000281","article-title":"High-dimensional graphs and variable selection with the lasso","volume":"34","author":"Meinshausen","year":"2006","journal-title":"Ann. Stat."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"6160","DOI":"10.1109\/TSP.2016.2602809","article-title":"Learning Laplacian matrix in smooth graph signal representations","volume":"64","author":"Dong","year":"2016","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"2077","DOI":"10.1109\/TSP.2016.2634543","article-title":"Signal processing on graphs: Causal modeling of unstructured data","volume":"65","author":"Mei","year":"2017","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_24","unstructured":"Kalofolias, V. (2016, January 9\u201311). How to learn a graph from smooth signals. Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), Cadiz, Spain."},{"key":"ref_25","first-page":"484","article-title":"Learning heat diffusion graphs","volume":"3","author":"Thanou","year":"2017","journal-title":"IEEE Trans. Signal Inf. Process. Netw."},{"key":"ref_26","unstructured":"Kalofolias, V., and Perraudin, N. (2019, January 6\u20139). Large scale graph learning from smooth signals. Proceedings of the 7th International Conference on Learning Representations (ICLR), New Orleans, LA, USA."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Chepuri, S.P., Liu, S., Leus, G., and Hero, A.O. (2017, January 5\u20139). Learning sparse graphs under smoothness prior. Proceedings of the 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), New Orleans, LA, USA.","DOI":"10.1109\/ICASSP.2017.7953410"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Rabbat, M.G. (2017, January 5\u20139). Inferring sparse graphs from smooth signals with theoretical guarantees. Proceedings of the 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), New Orleans, LA, USA.","DOI":"10.1109\/ICASSP.2017.7953415"},{"key":"ref_29","first-page":"105","article-title":"Efficient graph learning from noisy and incomplete data","volume":"6","author":"Berger","year":"2020","journal-title":"IEEE Trans. Signal Inf. Process. Netw."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Shafipour, R., Segarra, S., Marques, A.G., and Mateos, G. (2020). Identifying the topology of undirected networks from diffused non-stationary graph signals. IEEE Open J. Signal Process., (submitted; see also arXiv:1801.03862 [eess.SP]).","DOI":"10.1109\/OJSP.2021.3063926"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Shafipour, R., Segarra, S., Marques, A.G., and Mateos, G. (2017, January 5\u20139). Network topology inference from non-stationary graph signals. Proceedings of the 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), New Orleans, LA, USA.","DOI":"10.1109\/ICASSP.2017.7953282"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Cardoso, J., and Palomar, D. (2020). Learning undirected graphs in financial markets. arXiv.","DOI":"10.1109\/IEEECONF51394.2020.9443573"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Kalofolias, V., Loukas, A., Thanou, D., and Frossard, P. (2017, January 5\u20139). Learning time varying graphs. Proceedings of the 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), New Orleans, LA, USA.","DOI":"10.1109\/ICASSP.2017.7952672"},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Vlaski, S., Mareti\u0107, H.P., Nassif, R., Frossard, P., and Sayed, A.H. (2018, January 4\u20136). Online graph learning from sequential data. Proceedings of the 2018 IEEE Data Science Workshop (DSW), Lausanne, Switzerland.","DOI":"10.1109\/DSW.2018.8439913"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"3675","DOI":"10.1109\/TSP.2017.2698369","article-title":"Tensor decompositions for identifying directed graph topologies and tracking dynamic networks","volume":"65","author":"Shen","year":"2017","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1109\/TSP.2016.2614793","article-title":"Autoregressive moving average graph filtering","volume":"65","author":"Isufi","year":"2017","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1109\/JSTSP.2014.2317284","article-title":"Proximal-gradient algorithms for tracking cascades over social networks","volume":"8","author":"Baingana","year":"2014","journal-title":"IEEE J. Sel. Top. Signal Process."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"787","DOI":"10.1109\/JPROC.2018.2804318","article-title":"Topology identification and learning over graphs: Accounting for nonlinearities and dynamics","volume":"106","author":"Giannakis","year":"2018","journal-title":"Proc. IEEE"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1109\/MSP.2020.2968813","article-title":"Optimization and learning with information streams: Time-varying algorithms and applications","volume":"37","author":"Simonetto","year":"2020","journal-title":"IEEE Signal Process. Mag."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"4193","DOI":"10.1109\/TSP.2017.2708035","article-title":"Distributed adaptive learning of graph signals","volume":"65","author":"Banelli","year":"2017","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"3584","DOI":"10.1109\/TSP.2018.2835384","article-title":"Adaptive graph signal processing: Algorithms and optimal sampling strategies","volume":"66","author":"Banelli","year":"2018","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"2263","DOI":"10.1109\/TSP.2019.2903025","article-title":"Semi-blind inference of topologies and dynamical processes over dynamic graphs","volume":"67","author":"Ioannidis","year":"2019","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"1413","DOI":"10.1002\/cpa.20042","article-title":"An iterative thresholding algorithm for linear inverse problems with a sparsity constraint","volume":"57","author":"Daubechies","year":"2004","journal-title":"Commun. Pure Appl. Math."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"2479","DOI":"10.1109\/TSP.2009.2016892","article-title":"Sparse reconstruction by separable approximation","volume":"57","author":"Wright","year":"2009","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_45","doi-asserted-by":"crossref","unstructured":"Beck, A. (2018). First-Order Methods in Optimization, Society for Industrial and Applied Mathematics.","DOI":"10.1137\/1.9781611974997"},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Bauschke, H.H., and Combettes, P.L. (2011). Convex Analysis and Monotone Operator Theory in Hilbert Spaces, Springer.","DOI":"10.1007\/978-1-4419-9467-7"},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/s10107-004-0552-5","article-title":"Smooth minimization of nonsmooth functions","volume":"103","author":"Nesterov","year":"2005","journal-title":"Math. Prog."},{"key":"ref_48","unstructured":"Chen, Y., and Ye, X. (2011). Projection onto a simplex. arXiv."},{"key":"ref_49","unstructured":"Solo, V., and Kong, X. (1995). Adaptive Signal Processing Algorithms: Stability and Performance, Prentice Hall."},{"key":"ref_50","doi-asserted-by":"crossref","unstructured":"Kunegis, J. (2013, January 13\u201317). KONECT\u2014The Koblenz Network Collection. Proceedings of the 22nd International Conference on World Wide Web (WWW\u201913 Companion), Rio de Janeiro, Brazil.","DOI":"10.1145\/2487788.2488173"},{"key":"ref_51","unstructured":"Leskovec, J., and Mcauley, J. (2012, January 3\u20136). Learning to discover social circles in ego networks. Proceedings of the Advances in Neural Information Processing Systems (NIPS), Lake Tahoe, Nevada."},{"key":"ref_52","doi-asserted-by":"crossref","unstructured":"Li, Y., and Mateos, G. (2019, January 12\u201317). Identifying Structural Brain Networks from Functional Connectivity: A Network Deconvolution Approach. Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Brighton, UK.","DOI":"10.1109\/ICASSP.2019.8682716"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/9\/228\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:08:20Z","timestamp":1760177300000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/9\/228"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,9]]},"references-count":52,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2020,9]]}},"alternative-id":["a13090228"],"URL":"https:\/\/doi.org\/10.3390\/a13090228","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9,9]]}}}