Connecting the Dots: Learning Graphs from Data, Part 1 of 2

Under the assumption that network data 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 and can make inferences about these relationships, even when they are only partially observed. Many GSP efforts to date assume that the underlying network is known, and then analyze how the graph?s algebraic and spectral characteristics impact the properties of the graph signals of interest. However, such an assumption is often untenable in practice and arguably most graph construction schemes are largely informal, distinctly lacking an element of validation. In this lecture, we offer an overview of network topology inference methods developed to bridge the aforementioned gap, by using information available from graph signals along with innovative GSP tools and models to infer the underlying graph structure. It will also introduce the attendees to challenges and opportunities for SP research in emerging topic areas at the crossroads of modeling, prediction, and control of complex behavior arising with large-scale networked systems that evolve over time. Accordingly, this lecture stretches all the way from (nowadays rather mature) statistical approaches including correlation analyses to recent GSP advances in a comprehensive and unifying manner. Through rigorous problem formulations and intuitive reasoning, concepts are made accessible to SP researchers not well-versed in network-analytic issues. A diverse gamut of network inference challenges and application domains will be selectively covered, based on importance and relevance to SP expertise, as well as the instructor's own experience and contributions.