CIF: Small: Graph Structure Discovery of Networked Dynamical Systems

在重要的应用领域中出现的许多系统都是许多组件的复杂互联。这些系统通常被称为代理网络，一个代理的观察到的行为取决于网络中许多其他代理的行为，无论是否观察到。这类系统的例子不仅包括生物或大脑网络、基因调控网络和在人群中传播的流行病，还包括大型关键物理基础设施，如电网。例如，对于大脑网络，重要的是从脑电(EEG)记录中推断出哪些神经网络形成，以便更好地了解神经活动，从而提供更好地诊断一些大脑损伤或疾病的方法。该项目将开发确定系统各部分(代理)之间的未知和隐藏联系的方法，这通常是了解整个系统的全局行为的必要的第一步。在复杂的系统中，如脑电阵列，与未观察到但相互关联的组件的数量要多得多相比，测量探头的数量很少。待开发的方法将可靠地推断被观察或测量的试剂之间的联系，即使在系统中存在许多潜在的、未被观察到的部分。这些方法将在许多不同的实用领域具有广泛的适用性。该项目将支持至少两名博士生，并将吸引卡内基梅隆大学广泛而多样的硕士和本科生群体。揭示网络动力系统(NDS)各部分之间的相互联系，即结构识别，在研究界受到了极大的关注。但当前方法的成功受到各种因素的限制。例如，一些方法要求完全可观察性，即观察NDS中所有相互关联的代理的活动。然而，这通常是不现实的，因为许多NDS的规模很大，或者因为跟踪所有代理的行为(例如，大脑网络中的神经元活动)是不切实际的或不可能的。第二个限制涉及假设不同代理人观察到的行为样本是独立的和相同分布的。同样，这样的假设是非常有限的，因为在许多场景中，跨时间和跨代理的观察到的行为有很大的相关性。所进行的研究将考虑可能具有时间和空间(跨代理)依赖的全部和部分可观察性背景。对于每对代理，该方法设计一个高维特征向量，然后将其输入到分类器，该分类器对特征进行聚类，并使用高维流形将连接的对与未连接的对分开。这项工作将为特征的可分离性以及分离流形对影响代理行为的连通性、可观性和扰动的各种方案的稳定性提供理论保证。还将研究该方法的普适性，例如，用低维NDS进行训练，然后推断更大规模系统的结构。该项目将使用来自一些实际相关应用的合成和真实数据集来测试这些方法。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Many systems arising in important application domains are complicated interconnections of many components. These systems are commonly referred to as networks of agents, and the observed behavior of one agent depends on the behavior of the many other agents, observed or not, in the network. Examples of such systems include not only biological or brain networks, gene regulatory networks, and pandemics spreading over populations, but also large critical physical infrastructures like the electric-power grid. For example, with brain networks, it is important to infer from electroencephalography (EEG) recordings which neural networks form in order to better understand the neural activity and thereby provide a means to better diagnose a number of brain injuries or diseases. The project will develop methods to determine the unknown and hidden connections among the parts (agents) of a system, often a necessary first step to understand the global behavior of the overall system. In complex systems, like EEG arrays, the number of measuring probes is small compared to the much larger number of unobserved but interconnected components. The methods to be developed will reliably infer the connections among the agents that are observed or measured, even in the presence of many latent, unobserved parts of the system. These methods will have broad applicability across many different practical domains. The project will support at least two PhD students and will engage a broad, diverse group of Master and undergraduate students at Carnegie Mellon University.The problem of uncovering the interconnections among parts of a network dynamical system (NDS), known as structure identification, has received significant attention in the research community. But the success of current approaches is limited by various factors. For example, some methods require total observability, i.e., observing the activity of all the interconnected agents in the NDS. However, this is often unrealistic due to the large scale of many NDS or because it is impractical or impossible to track the behavior of all the agents (e.g., neuron activity in a brain network). A second limitation relates to assuming that the samples of the observed behavior of different agents are independent and identically distributed. Again, such an assumption is very limiting since, in many scenarios, there are significant dependencies in the observed behaviors across time and across agents. The research pursued will consider the total- and partial-observability contexts with possibly temporal and spatial (across-agent) dependencies. For every pair of agents, the approach engineers a high-dimensional feature vector that is then input to a classifier that clusters the features, with a high-dimensional manifold separating the connected pairs from the unconnected pairs. The work will provide theoretical guarantees regarding the separability of the features as well as the stability of the separating manifold to various regimens of connectivity, observability, and disturbances affecting the behaviors of the agents. The generalizability of the approach will also be studied, e.g., training with a lower-dimensional NDS and then inferring the structure of much larger-scale systems. The project will test the methods with synthetic and real-word datasets drawn from a number of practically relevant applications.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.