## 1 Introduction
### Identifying the Structure of Network Diffusion Processes  
Consider a weighted, undirected graph \(\mathcal{G}\) consisting of a node set \(\mathcal{N}\) of cardinality \(N\), and symmetric adjacency matrix \(\mathbf{A}\in\mathbb{R}_{+}^{N\times N}\) with entry \(A_{ij}=A_{ji}+0\) denoting the edge weight between node \(i\) and node \(j\). We assume that \(\mathcal{G}\) contains no self-loops; i.e., \(A_{ii}=0\). The adjacency matrix encodes the topology of \(\mathcal{G}\). One could generically define a _graph-shift operator_ (GSO) \(\mathbf{S}\in\mathbb{R}^{N\times N}\) as any matrix capturing the same sparsity pattern as \(\mathbf{A}\) on its off-diagonal entries. Beyond \(\mathbf{A}\), common choices for \(\mathbf{S}\) are the combinatorial Laplacian \(\mathbf{L}\coloneqq\mathrm{diag}(\mathbf{A}\mathbf{1})-\mathbf{A}\) as well as their normalized counterparts [3]. Henceforth we focus on \(\mathbf{S}=\mathbf{A}\) and aim to recover the _sparse_ adjacency matrix of the unknown graph \(\mathcal{G}\). Other GSOs can be accommodated in a similar fashion. The graph can be dynamic with a slowly time-varying GSO \(\mathbf{S}_{t}\), \(t=1,2,\ldots\) (see also Section 2.2), but for now we omit any form of temporal dependency to simplify exposition. Our goal is to develop an online framework to estimate sparse graphs that explain the structure of a class of streaming random signals. At some time instant, let \(\mathbf{y}=[y_{1},\ldots,y_{N}]^{T}\in\mathbb{R}^{N}\) be a zero-mean graph signal in which the \(i\)-th element \(y_{i}\) denotes the signal value at node \(i\) of the unknown graph \(\mathcal{G}\) with shift operator \(\mathbf{S}\). Further, consider a zero-mean white signal \(\mathbf{x}\). We state that the graph \(\mathbf{S}\) represents the structure of the signal \(\mathbf{y}\in\mathbb{R}^{N}\) if there exists a diffusion process in the GSO \(\mathbf{S}\) that produces the signal \(\mathbf{y}\) from the input signal \(\mathbf{x}\)[6], that is  
\[\mathbf{y}=\alpha_{0}\prod_{l=1}^{\infty}(\mathbf{I}_{N}-\alpha_{l}\mathbf{S })\mathbf{x}=\sum_{l=0}^{\infty}\beta_{l}\mathbf{S}^{l}\mathbf{x}. \tag{1}\]  
Under the assumption that \(\mathbf{C}_{\mathbf{x}}=\mathbb{E}\left[\mathbf{x}\mathbf{x}^{T}\right]= \mathbf{I}_{N}\) (identity matrix), (1) is equivalent to the _stationarity_ of \(\mathbf{y}\) in \(\mathbf{S}\); see e.g., ([7], Def. 1), [8; 9]. The product and sum representations in (1) are common (and equivalent) models for the generation of random network processes. Indeed, any process that can be understood as the linear propagation of a white input through \(\mathcal{G}\) can be written in the form in (1), and subsumes heat diffusion, consensus and the classic DeGroot model of opinion dynamics as special cases. The justification to say that \(\mathbf{S}\) represents the structure of \(\mathbf{y}\) is that we can think of the edges of \(\mathcal{G}\), i.e., those few non-zero entries in \(\mathbf{S}\), as direct (one-hop) relations between the elements of the signal. The diffusion in (1) modifies the original correlation by inducing indirect (multi-hop) relations in \(\mathbf{C}_{\mathbf{y}}=\mathbb{E}\left[\mathbf{y}\mathbf{y}^{T}\right]\). At a high level, the problem studied in this paper is the following [6; 10]. **Problem. ** Recover the direct relations described by a sparse GSO \(\mathbf{S}\) from a set \(\{\mathbf{y}_{t}\}_{t=1}^{T}\) of \(T\) independent samples of the random signal \(\mathbf{y}\) adhering to (1). We consider the challenging setup when we have no knowledge of the diffusion coefficients \(\{\alpha_{l}\}\) (or \(\{\beta_{l}\}\)), nor do we get to observe the specific realizations of the driving inputs \(\{\mathbf{x}_{t}\}_{t=1}^{T}\). The stated inverse problem is severely underdetermined and nonconvex. It is underdetermined because for every observation \(\mathbf{y}\) we have the same number of unknowns in the input \(\mathbf{x}\) on top of the unknown diffusion coefficients and the shift \(\mathbf{S}\), the latter being the quantity of interest.