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

现代技术的进步使得收集从社会科学到神经科学等广泛学科的超大型数据集成为可能。这些数据集通常由许多节点的活动模式组成，这些节点共同形成一个网络。例如，在社交网络中，每个节点可以表示一个人，而两个节点之间的连接可以表示友谊。在大脑中，每个节点可以代表一个神经元，两个节点之间的连接可以代表神经元之间的链接。一个新出现的挑战是设计算法，可以可靠和有效地推断这些网络的隐藏结构（即节点之间的连接集），只需记录节点的活动模式。一个相关的问题是试图仅基于对一些节点连接的了解来识别网络中的隐藏集群或社区。该项目试图从网络变化发现的角度来研究这些问题：而不是试图恢复完整的网络结构，目标是确定网络结构是否在一定的时间尺度上发生了显着变化，以及这些结构变化发生在哪里。初步研究结果表明，在某些情况下，发现变化可能比结构恢复容易得多。这个跨学科项目将从理论和算法的角度研究网络变化发现问题;由此产生的工具将应用于大型神经数据集，以了解学习任务如何改变大脑特定区域神经元的连接。此外，本项目还将通过专题研讨会、课程开发、本科生和研究生研究的共同监督，尝试在信息科学和神经科学之间建立新的联系。从技术角度来看，本项目的目标分为三个方面。第一个推力采用信息论和高维统计的现代工具来确定测试和恢复网络变化的基本限制。这项工作将开始与简单的规范模型，如随机块模型和马尔可夫随机场，直接比较是可能的结构学习的工作。然后，它将转向更丰富的模型，包括动态，部分观测和重叠社区。第二个推力检查这些问题从算法的角度来看，并寻求设计计算效率高的算法，可以证明接近的基本限制建立在第一个推力。这些算法将在合成数据集上进行验证，然后进行调整以处理真实的数据集中存在的复杂性。第三个目标是将这些算法应用于在关联和消退学习实验期间从小鼠海马体收集的大规模钙成像神经数据集。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.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.