Learning Representations for Signal And Data Processing on Directed Graphs

Rasoul Shafipour

Supervised by Professor Gonzalo Mateos

Computer Studies Building 601

Network processes are becoming increasingly ubiquitous, with examples ranging from the measurements of neural activities at different regions of the brain to infectious states of individuals in a population affected by an epidemic. Such network data can be conceptualized as graph signals supported on the vertices of the adopted graph abstraction to the network. Under the natural assumption that the signal properties relate to the underlying graph topology, the goal of graph signal processing (GSP) is to develop algorithms that fruitfully exploit this relational structure. This dissertation contributes to this effort by advancing signal representations for information processing on (possibly directed) networks.

An instrumental GSP tool is the graph Fourier transform (GFT), which decom- poses a graph signal into orthonormal components describing different modes of variation with respect to the graph topology. In the first part of this dissertation, we study the problem of constructing a graph Fourier transform (GFT) for directed graphs (digraphs). Unlike existing approaches, to capture low, medium, and high frequencies, we seek a digraph (D)GFT such that the orthonormal frequency components are as spread as possible in the graph spectral domain. To that end, we advocate a two-step design whereby we: (i) find the maximum directed variation (i.e., a novel notion of frequency on a digraph) a candidate basis vector can attain; and (ii) minimize a smooth spectral dispersion function over the achievable frequency range to obtain a spread DGFT basis. Both steps involve non-convex, orthonormality-constrained optimization problems, which are tack- led via a provably-convergent feasible optimization method on the Stiefel manifold. We discuss a data-adaptive variant whereby a sparsifying orthonormal trans- form is learnt to encourage parsimonious representations of bandlimited signals. Distributed graph filtering based on the learnt transform is investigated as well.

Graph frequency analyses require a specification of the underlying digraph which might not be readily available. In the second part of this thesis, we con- sider inferring a network given observations of graph signals generated by linear diffusion dynamics on the sought graph. Observations are modeled as the out- puts of a linear graph filter (i.e., a polynomial on a diffusion graph-shift operator encoding the unknown graph topology), excited with input graph signals with arbitrarily-correlated nodal components. In this context, we first rely on observations of the output signals along with prior statistical information on the inputs to identify the diffusion filter. Such problem entails solving a system of quadratic matrix equations which we recast as standard optimization problems with provable performance guarantees. Subsequent identification of the network topology boils down to finding a sparse graph-shift operator that is simultaneously diagonalizable with the given filter estimate. We further develop an (online) adaptive scheme to track the (possibly) time-varying network structure, and affect memory and computational savings by processing the data on-the-fly as they are acquired. We illustrate the effectiveness of the novel DGFT and topology inference algorithms through numerical tests on synthetic and real-world networks.