## 2 Materials and Methods
### Online Network Topology Inference
#### 2.2.1 Algorithm Construction
1.2.2) represented by a graph \(\mathcal{G}\) consisting of \(N=34\) nodes or members of the club and 78 undirected edges symbolizing friendships among them. We seek to infer this graph from the observation of diffusion processes that are synthetically generated via graph filtering as in (2). The rank of \(\mathbf{W}_{\mathcal{D}}\) (cf. Proposition 1) for this graph is 32. This implies that the knowledge of the perfect output covariance \(\mathbf{C}_{\mathbf{y}}\) leaves the GSO \(\mathbf{S}\) in a 2-dimensional subspace which can lead to singleton feasibility set by observing only two different edges. However, here we work with a noisy sample covariance \(\hat{\mathbf{C}}_{\mathbf{y}}\). We observe one of the 78 edges (chosen uniformly at random) and aim to infer the rest of the edges. At each time step, 10 synthetic signals \(\{\mathbf{y}_{p}\}\) are generated through a diffusion process \(\mathbf{H}\) where the entries of the inputs \(\{\mathbf{x}_{p}\}\) are drawn independently from the standard Gaussian distribution. In the online case, upon sensing 10 signals at each time step, we first update the sample covariance \(\hat{\mathbf{C}}_{\mathbf{y},t}\) and then carry out \(i_{t}=10\) PG iterations as Algorithm 2. To examine the tracking capability of the online estimator, after 5000 time steps, we remove 10% of the existing edges and add the same number of edges elsewhere. This would affect the graph filter \(\mathbf{H}\) accordingly. To corroborate the assumption in Theorem 1, it is worth mentioning that throughout the process we observed that \(\mathbf{\
abla}_{t,\mathcal{D}^{c}}\) was full column rank and thus the cost in (13) was strongly convex; see Proposition 2. Figure 2a depicts the running objective value \(F_{t}(\mathbf{S}_{t})\) [cf. (13)] averaged over 10 experiments as a function of the time steps and the available a priori knowledge--two randomly chosen edges as well as the case where we have no a priori information on the edges (\(\Omega=\varnothing\)). For the latter case, we modify the feasible set \(\mathcal{S}\) as suggested in Remark 2 as well as Algorithm 2 by implementing the proximal operator in (16). We also superimpose Figure 2a with the optimal objective value \(F_{t}(\mathbf{S}_{t}^{*})\) at each time step. First, we notice that the objective value trajectory converges to a region above the optimal trajectory. We observe that after 5000 iterations, the performance deteriorates at first due to the sudden change of the network structure, but after observing enough new samples Algorithm 2 can adapt and track the batch estimator as well. This demonstrates the effectiveness of the developed online algorithm when it comes to adapting to network perturbations. Finally, we study the quality of the graph \(\mathbf{S}_{t}\) learned in an online fashion at iteration 5000 (just before the perturbation). Figure 2b depicts the heat maps of the ground-truth and inferred

Figure 2: Recovery of [PERSON]’s karate club graph with \(N=34\) nodes. (**a**) Evolution of the objective values for the online and batch estimators in inferring a karate club. (**b**) Ground-truth adjacency matrix and corresponding estimates after 5000 time steps, for different prior connectivity information settings. Knowledge of at least one edge in the graph can markedly improve support recovery performance as indicated by the obtained F-measure values. adjacency matrices for different a priori information. Although the procedure results in a slight gap between \(F_{t}(\mathbf{S}_{t}^{*})\) and \(F_{t}(\mathbf{S}_{t})\), it still reveals the underlying support of \(\mathbf{A}\) with reasonable accuracy. Inspection of the F-measures in Figure 2b calculated on the thresholded adjacency matrices reveals that, as expected, having a priori information on the edges aids graph recovery performance. ## 4 Discussion

Here we include a brief but general discussion about the approach followed (and the assumptions made), its limitations as well as the impact this work can have to applications.