  Network processes are often represented as signals defined on the vertices of
a graph. To untangle the latent structure of such signals, one can view them as
outputs of linear graph filters modeling underlying network dynamics. This
paper deals with the problem of joint identification of a graph filter and its
input signal, thus broadening the scope of classical blind deconvolution of
temporal and spatial signals to the less-structured graph domain. Given a graph
signal $\mathbf{y}$ modeled as the output of a graph filter, the goal is to
recover the vector of filter coefficients $\mathbf{h}$, and the input signal
$\mathbf{x}$ which is assumed to be sparse. While $\mathbf{y}$ is a bilinear
function of $\mathbf{x}$ and $\mathbf{h}$, the filtered graph signal is also a
linear combination of the entries of the lifted rank-one, row-sparse matrix
$\mathbf{x} \mathbf{h}^T$. The blind graph-filter identification problem can
thus be tackled via rank and sparsity minimization subject to linear
constraints, an inverse problem amenable to convex relaxations offering
provable recovery guarantees under simplifying assumptions. Numerical tests
using both synthetic and real-world networks illustrate the merits of the
proposed algorithms, as well as the benefits of leveraging multiple signals to
aid the blind identification task.
