CIF: Small: Graph Structure Discovery of Networked Dynamical Systems

在重要的应用领域中出现的许多系统是许多组件的复杂互连。这些系统通常被称为代理网络，一个代理的观察行为取决于网络中许多其他代理的行为，无论是否被观察到。这类系统的例子不仅包括生物或大脑网络、基因调控网络和在人群中传播的流行病，还包括像电网这样的大型关键物理基础设施。例如，对于大脑网络，重要的是从脑电图（EEG）记录推断出哪些神经网络形成，以便更好地理解神经活动，从而提供更好地诊断许多脑损伤或疾病的手段。该项目将开发方法来确定系统各部分（代理）之间的未知和隐藏连接，这通常是理解整个系统的全局行为的必要的第一步。在复杂的系统中，如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.