CAREER: Inferring Graph Structure via Spectral Representations of Network Processes

University Of Rochester, Rochester NY

Investigators

Abstract

Coping with the challenges found at the intersection of Network Science and Big Data necessitates fundamental breakthroughs in modeling, identification, and controllability of distributed network processes -- often conceptualized as signals defined on graphs. There is an evident mismatch between the scientific understanding of signals defined over regular domains (time or space) and graph-valued signals. Knowledge about time series was developed over the course of decades and boosted by real needs in areas such as communications, speech, or control. On the contrary, the prevalence of network-related signal processing problems and the access to quality network data are recent events. In this context, research in this project aims to push the frontiers of knowledge in network-analytic information processing, and thus make progress towards understanding the inherent complexities of strongly coupled systems such as the brain. Students will also be trained to tackle the problems at the intersection of Big Data and Network Science, thereby contributing to workforce development as well. Under the assumption that the signals are related to the topology of the graph where they are supported, the goal of graph signal processing is to develop algorithms that fruitfully leverage this relational structure, and can make inferences about these relationships when they are only partially observed. Most graph signal processing 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 assumption is often untenable in practice and arguably most graph construction schemes are largely informal, distinctly lacking an element of validation. The intellectual merit of this research project is to investigate how to use information available from graph signals to learn the underlying graph topology, through innovative approaches that operate in the graph spectral domain. The idea is to consider the graph Fourier transform of the snapshot signals associated with an arbitrary graph and, among all the feasible networks, search for one that endows the resulting transforms with target spectral properties and the sought graph with appealing physical characteristics. Aligned with current trends in data-driven scientific inquiry into complex networked systems, the aim is to shift from: (i) descriptive accounts to inferential graph signal processing techniques that can explain as well as predict network behavior; and from (ii) ad hoc graph constructions to rigorous formulations rooted in well-defined models and principles. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.