Online Topology Inference from Streaming Stationary Graph Signals with\n Partial Connectivity Information

We develop online graph learning algorithms from streaming network data. Our\ngoal is to track the (possibly) time-varying network topology, and effect\nmemory and computational savings by processing the data on-the-fly as they are\nacquired. The setup entails observations modeled as stationary graph signals\ngenerated by local diffusion dynamics on the unknown network. Moreover, we may\nhave a priori information on the presence or absence of a few edges as in the\nlink prediction problem. The stationarity assumption implies that the\nobservations' covariance matrix and the so-called graph shift operator (GSO --\na matrix encoding the graph topology) commute under mild requirements. This\nmotivates formulating the topology inference task as an inverse problem,\nwhereby one searches for a sparse GSO that is structurally admissible and\napproximately commutes with the observations' empirical covariance matrix. For\nstreaming data said covariance can be updated recursively, and we show online\nproximal gradient iterations can be brought to bear to efficiently track the\ntime-varying solution of the inverse problem with quantifiable guarantees.\nSpecifically, we derive conditions under which the GSO recovery cost is\nstrongly convex and use this property to prove that the online algorithm\nconverges to within a neighborhood of the optimal time-varying batch solution.\nNumerical tests illustrate the effectiveness of the proposed graph learning\napproach in adapting to streaming information and tracking changes in the\nsought dynamic network.\n