## 2 Materials and Methods
### Online Network Topology Inference
#### 2.2.1 Algorithm Construction
## 5 Conclusions

We studied the problem of identifying the topology of an undirected network from streaming observations of stationary signals diffused on the unknown graph. This is an important problem, because as a general principle network structural information can be used to understand, predict, and control the behavior of complex systems. The stationarity assumption implies that the observations' covariance matrix and the GSO 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 recovery guarantees. Ongoing work includes extensions of the online graph learning framework to observations of streaming signals that are smooth on the sought network. [PERSON] and [PERSON] were responsible for conceptualizing this work (including the formal analysis and methodology), they also drafted and revised the manuscript. [PERSON] carried out the numerical tests. [PERSON] supervised this work and was responsible for funding acquisition. Both authors have read and agreed to the published version of the manuscript. Work in this paper was supported by the National Science Foundation awards CCF-1750428 and ECCS-1809356. The authors declare no conflict of interest. ## Appendix A Proof of Proposition 2

Strong convexity of \(g_{t}(\mathbf{S})\) in (13) is equivalent to finding \(m_{t}>0\) such that

\[(\mathbf{S}_{1}-\mathbf{S}_{2},\
abla g_{t}(\mathbf{S}_{1})-\
abla g_{t}( \mathbf{S}_{2}))\geq m_{t}|\mathbf{S}_{1}-\mathbf{S}_{2}|_{F}^{2}, \tag{10}\]

for \(\mathbf{S}_{1}\), \(\mathbf{S}_{2}\in\mathcal{S}\). Note that the Frobenius inner product of two real square matrices is defined as \((\mathbf{A},\mathbf{B})=\sum_{i,j}A_{ij}B_{ij}=\text{trace}(\mathbf{A}^{T} \mathbf{B})\). Substituting the time-varying counterpart of (9) in (10) and using properties of the Khatri-Rao product, one can write the left hand side (LHS) of (10) as

\[\|(\mathbf{S}_{1}-\mathbf{S}_{2})\hat{\mathbf{C}}_{\mathbf{y},t}-\hat{\mathbf{ C}}_{\mathbf{y},t}(\mathbf{S}_{1}-\mathbf{S}_{2})\|_{F}^{2}=\|\mathbf{\Psi}_{t} \text{vec}(\mathbf{S}_{1}-\mathbf{S}_{2})\|_{2}^{2},\]

where \(\text{vec}(\cdot)\) stands for matrix vectorization and \(\|\cdot\|\) denotes the Euclidean distance. Since GSOs are devoid of self-loops, we can discard the zero entries of \(\text{vec}(\mathbf{S}_{1}-\mathbf{S}_{2})\) corresponding to the diagonal entries of \(\mathbf{S}\) as well as the related columns in \(\mathbf{\Psi}_{t}\). This would further simplify the LHS of (10) leading immediately to the result in Proposition 2. Notice that \(\|\text{vec}(\mathbf{S}_{1}-\mathbf{S}_{2})\|_{2}^{2}=\|\mathbf{S}_{1}- \mathbf{S}_{2}\|_{F}^{2}\). where the first inequality is due to the nonexpansiveness of the proximal operator and the second one follows from (A2). Leveraging the triangle inequality and the definition \(v_{t}=\left\|\mathbf{S}_{t+1}^{*}-\mathbf{S}_{t}^{*}\right\|_{F}\) results in

\[\left\|\mathbf{S}_{t+1}-\mathbf{S}_{t+1}^{*}\right\|_{F} \leq\left\|\mathbf{S}_{t+1}-\mathbf{S}_{t}^{*}\right\|_{F}+\left\| \mathbf{S}_{t+1}^{*}-\mathbf{S}_{t}^{*}\right\|_{F}\] \[\leq L_{t}\left\|\mathbf{S}_{t}-\mathbf{S}_{t}^{*}\right\|_{F}+v _{t},\]

which can be applied recursively to obtain (17). ## References

* [PERSON] (2009) [PERSON] _Statistical Analysis of Network Data: Methods and Models_; Springer: New York, NY, USA, 2009. * [PERSON] et al. (2014) [PERSON]; [PERSON]; [PERSON] Modeling and optimization for big data analytics: (Statistical) learning tools for our era of data deluge. _IEEE Signal Process. Mag._**2014**, _31_, 18-31. [CrossRef]
* [PERSON] et al.