CIF: Medium: Discovering Changes in Networks: Fundamental Limits, Efficient Algorithms, and Large-Scale Neuroscience

Sponsor: National Science Foundation

Award Number: 1955981

PI: Bobak Nazer

Co-Is/Co-PIs: Venkatesh Saligrama, Xue Han

Modern technological advances have made it possible to collect extremely large datasets across a wide range of disciplines, spanning from social science to neuroscience. These datasets often consist of the activity patterns of many nodes that together form a network. For instance, in a social network, each node can represent a person while a connection between two nodes can represent a friendship. In the brain, each node can represent a neuron and a connection between two nodes can represent a link between the neurons. An emerging challenge is to design algorithms that can reliably and efficiently infer the hidden structure of these networks (namely the set of connections between nodes), given only recordings of the nodes’ activity patterns. A related problem seeks to identify hidden clusters or communities in a network based only on the knowledge of some of the nodes’ connections. This project seeks to examine these problems from the perspective of network change discovery: Rather than attempt to recover the full network structure, the goal is to determine whether a network structure has changed significantly over a certain time scale, and where these structural changes have occurred. Preliminary findings show that, in some settings, change discovery can be substantially easier than structure recovery. This cross-disciplinary project will examine network change discovery problems from theoretical and algorithmic perspectives; the resulting tools will be applied to large neural datasets, on the way to understand how learning a task changes the connectivity of neurons in a particular region of the brain. In addition, this project will also attempt to forge new connections between the information sciences and neuroscience through a combination of focused workshops, course development, and co-supervision of undergraduate and graduate research.

From a technical perspective, the goals of the project are grouped into three thrusts. The first thrust employs modern tools from information theory and high-dimensional statistics to determine the fundamental limits for testing and recovering network changes. This effort will begin with simple canonical models, such as stochastic block models and Markov random fields, where direct comparisons are possible with prior work on structure learning. It will then move towards richer models that include dynamics, partial observations, and overlapping communities. The second thrust examines these problems from an algorithmic perspective, and seeks to design computationally-efficient algorithms that can provably approach the fundamental limits established in the first thrust. These algorithms will be validated on synthetic datasets, and then adapted to handle the complexities present in real datasets. The third thrust will apply these algorithms to large-scale calcium imaging neural datasets collected from the hippocampus of mice during association and extinction learning experiments. The goal is to determine how the connectivity between neurons changes as mice learn the task.

For more information: click here