Network topology identification from imperfect spectral templates

This paper studies network topology inference, which is a cornerstone problem in statistical analysis of complex systems. The fresh look advocated here builds on recent advances in convex optimization and graph signal processing to identify the so-termed graph-shift operator (encoding the network topology) given only the eigenvectors of the shift. These spectral templates can be obtained, for example, from the covariance of a set of graph signals defined on the particular network. The novel idea is to find a graph shift that, while being consistent with the provided spectral information, endows the network structure with certain desired properties such as sparsity. To that end we develop efficient inference algorithms stemming from provably-tight convex relaxations of natural non-convex criteria. We initially propose algorithms along with theoretical performance guarantees for the case when the eigenbasis is perfectly known. We then investigate setups where an imperfect (noisy) eigenbasis is available as well as others when only a subset of the eigenvectors is known. Numerical tests showcase the effectiveness of the proposed algorithms in recovering real-world social networks.

I. Introduction

Advancing a holistic theory of networks necessitates breakthroughs in modeling, identification, and controllability of distributed network processes - often conceptualized as signals defined on the vertices of a graph [1], [2]. Under the assumption that the signal properties are related to the topology of the graph where they are supported, the goal of graph signal processing (GSP) is to develop algorithms that fruitfully leverage this relational structure [3], [4]. Instrumental to that end is the so-termed graph-shift operator (GSO) [4], a matrix capturing the graph's local topology and whose eigendecomposition defines the graph Fourier transform [4]. Most GSP works assume that the GSO (hence the graph) is known, and then analyze how the algebraic and spectral characteristics of the GSO affect the properties of the signals and filters defined on such a graph. We take here the reverse path and investigate how to use information available from graph signals and filters to infer the underlying graph topology; see also [5], [6]. By advocating a two-step approach, we first leverage results from GSP theory to estimate the GSO's eigenbasis, and then rely on these (possibly imperfect and incomplete) spectral templates to recover the GSO itself.