## 2 Materials and Methods
### Online Network Topology Inference
#### 2.2.1 Algorithm Construction
For Algorithm 2, these types of results are established in the ensuing section. #### 2.2.2 Convergence and Regret Analysis

The key difference between the batch algorithm (11) and its online counterpart (15) is the variability of \(g_{t}\) per iteration in the latter. Ideally, we would like Algorithm 2 to closely track the sequence of minimizers \(\{\mathbf{S}_{t}^{*}\}\) for large enough \(t\), something we corroborate numerically in Section 3. Following closely the analysis in [16], we derive recovery (i.e., tracking error) bounds \(\left\|\mathbf{S}_{t}-\mathbf{S}_{t}^{*}\right\|_{F}\) under the pragmatic assumption that \(g_{t}\) is strongly convex and \(\mathbf{S}_{t}^{*}\) is the unique minimizer of (13), for each \(t\). Before stating the main result in Theorem 1, the following proposition (proved in Appendix A) offers a condition for strong convexity of \(g_{t}\). **Proposition 2**. : _Let set \(\mathcal{D}\) contain the indices of \(\text{vec}(\mathbf{S})\) corresponding to the diagonal entries of \(\mathbf{S}\); i.e., \(\mathcal{D}:=\left\{N(i-1)+i\mid i\in\{1,\ldots,N\}\right\}\), and let \(\mathcal{D}^{c}\) be the complement of \(\mathcal{D}\). Define \(\boldsymbol{\
abla}_{t}=\hat{\mathbf{C}}_{\mathbf{y},t}\otimes\mathbf{I}_{N} -\mathbf{I}_{N}\otimes\hat{\mathbf{C}}_{\mathbf{y},t}\in\mathbb{R}^{N^{2}\times N ^{2}}\). If \(\boldsymbol{\
abla}_{t,\mathcal{D}^{c}}\in\mathbb{R}^{N^{2}\times N(N-1)}\) (the submatrix of \(\boldsymbol{\
abla}_{t}\) that contains columns indexed by the set \(\mathcal{D}^{c}\)) is full column rank, then \(g_{t}(\mathbf{S})\) in (13) is strongly convex with constant \(m_{t}>0\) being the smallest (nonzero) singular value of \(\boldsymbol{\
abla}_{t,\mathcal{D}^{c}}\)._

Consider the eigendecomposition \(\hat{\mathbf{C}}_{\mathbf{y},t}=\hat{\mathbf{V}}_{t}\hat{\mathbf{A}}_{t}\hat {\mathbf{V}}_{t}^{T}\) of the sample covariance matrix at time \(t\), with \(\hat{\mathbf{V}}_{t}\) denoting the matrix of orthogonal eigenvectors and \(\hat{\mathbf{A}}_{t}\) the diagonal matrix of non-negative eigenvalues. Exploiting the structure of \(\boldsymbol{\
abla}_{t}\) it follows that the strong convexity condition stated in Proposition 2 will be satisfied if (i) all eigenvalues of \(\hat{\mathbf{C}}_{\mathbf{y},t}\) are distinct; and (ii) the matrix \(\hat{\mathbf{V}}_{t}\circ\hat{\mathbf{V}}_{t}\) is non-singular. Recalling the covariance expression in (4), the aforementioned conditions (i)-(ii) immediately translate to properties of the diffusion filter's (squared) frequency response and the GSO eigenvectors. In extensive simulations involving several synthetic and real-world graphs, we have indeed observed that \(\boldsymbol{\
abla}_{t,\mathcal{D}^{c}}\) is typically full column rank and thus \(g_{t}\) is strongly convex. Under the strong convexity assumption, we have the following (non-asymptotic) performance guarantee for Algorithm 2. The result is adapted from ([16], Theorem 1) ; see Appendix B for a proof. **Theorem 1**. : _Let \(\
u_{t}:=\left\|\mathbf{S}_{t+1}^{*}-\mathbf{S}_{t}^{*}\right\|_{F}\) capture the variability of the optimal solution of (13). If \(g_{t}\) in (13) is strongly convex with constant \(m_{t}\), then for all \(t\geq 1\) the iterates \(\mathbf{S}_{t}\) generated by Algorithm 2 satisfy_

\[\left\|\mathbf{S}_{t}-\mathbf{S}_{t}^{*}\right\|_{F}\leq\tilde{L}_{t-1}\left( \left|\mathbf{S}_{0}-\mathbf{S}_{0}^{*}\right|_{F}+\sum_{\tau=0}^{t-1}\frac{ \
u_{\tau}}{\tilde{L}_{\tau}}\right), \tag{17}\]

_where \(L_{t}=\max\left\{\left|1-\gamma_{t}m_{t}\right|,\left|1-\gamma_{t}M_{t} \right|\right\},\tilde{L}_{t}=\prod_{\tau=0}^{t}L_{\tau}\). In terms of the objective values, it can be shown that \(F_{t}\left(\mathbf{S}_{t}\right)-F_{t}\left(\mathbf{S}_{t}^{*}\right)\leq \frac{M_{t}}{2}\left|\mathbf{S}_{t}-\mathbf{S}_{t}^{*}\right|_{F}^{2}\); see ([45], Theorem 10.29)._

As expected, Theorem 1 asserts that the higher the variability in the underlying graph, the higher the recovery performance penalty.