Identifying the Topology of Undirected Networks from Diffused Non-stationary Graph Signals

Understand

We address the problem of inferring an undirected graph from nodal observations, which are modeled as non-stationary graph signals generated by local diffusion dynamics that depend on the structure of the unknown network.

• Using the so-called graph-shift operator (GSO), which is a matrix representation of the graph, we first identify the eigenvectors of the shift matrix from realizations of the diffused signals, and then estimate the eigenvalues by imposing desirable properties on the graph to be recovered.
• Different from the stationary setting where the eigenvectors can be obtained directly from the covariance matrix of the observations, here we need to estimate first the unknown diffusion (graph) filter -- a polynomial in the GSO that preserves the sought eigenbasis.
• To carry out this initial system identification step, we exploit different sources of information on the arbitrarily-correlated input signal driving the diffusion on the graph.