## 2 Materials and Methods
### Identifying Graph Topologies from Observations of Stationary Graph Signals
#### 2.1.1 Revisiting Stationarity for Graph Learning  
As a different take on the shared eigenspace property, observe that stationarity of \(\mathbf{y}\) also implies \(\mathbf{C}_{\mathbf{y}}\mathbf{S}=\mathbf{SC}_{\mathbf{y}}\), thus forcing the covariance \(\mathbf{C}_{\mathbf{y}}\) to be a polynomial in \(\mathbf{S}\) [cf. (3)]. This commutation identity holds under the pragmatic assumption that all the eigenvalues of \(\mathbf{S}\) are simple and \(\sum_{l=0}^{L-1}h_{l}\lambda_{l}^{l}\
eq 0\), for \(i=1,\ldots,N\). It is also a natural characterization of (second-order) graph stationarity, requiring that second-order statistical information is shift invariant [7]. Since one can only estimate \(\hat{\mathbf{C}}_{\mathbf{y}}\) from data \(\{\mathbf{y}_{t}\}_{t=1}^{T}\), our idea to recover a sparse GSO is to solve (cf. (5))  
\[\mathbf{S}^{*}:=\operatorname*{argmin}_{\mathbf{S}\in\mathcal{S}}\,\|\,\mathbf{ S}\|_{1},\quad\text{subject to }\,\|\mathbf{S}\hat{\mathbf{C}}_{\mathbf{y}}-\hat{\mathbf{C}}_{\mathbf{y}} \mathbf{S}\|_{F}^{2}\leq\epsilon. \tag{6}\]  
The inverse problem (6) is intuitive. The constraints are such that one searches for an admissible \(\mathbf{S}\in\mathcal{S}\) that approximately commutes with the observations' empirical covariance matrix \(\hat{\mathbf{C}}_{\mathbf{y}}\). To recover a sparse graph we minimize the \(\ell_{1}\)-norm of \(\mathbf{S}\), the workhorse convex proxy to the intractable cardinality function \(\|\mathbf{S}\|_{0}\) counting the number of non-zero entries (edges) in the GSO. The sparsity prior is well justified to recover various real-world networks, or, to learn parsimonious and interpretable models of pairwise relationships among signal elements [4; 5]. Moreover, it follows from the arguments in Section 2.1 that if a signal is stationary with respect to \(\mathbf{S}\), it will also be stationary with respect to \(\mathbf{S}^{2}\) and all other higher powers of the GSO. Since \(\mathbf{S}^{l}\), \(l=2,3,\ldots\) are likely to be dense matrices, exploiting the sparsity in \(\mathbf{S}\) is particularly important towards lifting this under-determinacy. Different from (5) in [6], the formulation (6) circumvents computation of eigenvectors (an additional source of errors beyond covariance estimation), and reduces the number of optimization variables. More importantly, as we show in Section 2.1.3 that it offers favorable structure to invoke a proximal gradient solver with convergence guarantees, even in an online setting where the signals \(\mathbf{y}_{t}\) arrive in a streaming fashion. In closing, we elaborate on \(\mathcal{S}\) as the means to enforce the GSO is structurally admissible as well as to incorporate a priori knowledge about \(\mathbf{S}\). Henceforth we let \(\mathbf{S}=\mathbf{A}\) represent the adjacency matrix of an undirected graph with non-negative weights (\(S_{ij}=S_{ji}\geq 0\)) and no self-loops (\(S_{ii}=0\)). Unlike [6; 10], we investigate the effect of having additional prior information about the presence (or absence) of a few edges, or even their corresponding weights. This is well-motivated in studies where one can afford to explicitly measure a few of the pairwise relationships among the objects in \(\mathcal{N}\). Examples include social network studies involving questionnaire-based random sampling designs ([1], Ch. 5.3), or experimental testing of suspected regulatory interactions among selected pairs of genes ([1], Ch. 7.3.4). Since (6) is a sparse linear regression problem, one could resort to so-termed variable screening techniques to drop edges prior to solving the optimization; see e.g., [15]. Either way, one ends up with extra constraints \(S_{ij}=s_{ij}\), for a few vertex pairs \((i,j)\) in the set \(\Omega\subset\mathcal{N}\times\mathcal{N}\) of observed edge weights \(s_{ij}\).