论文标题
网络重建中的granger-faithful和链接方向
Granger-faithfulness and link orientation in network reconstruction
论文作者
论文摘要
网络动态系统通常被抽象成有向图，其中观察到的系统过程形成顶点集和有向边缘来表示非零传输函数。仅给定观察数据，恢复这种网络动态系统的确切基础图结构是一项具有挑战性的任务。在相对温和的网络动力学假设下，有一些最新的方法可以保证没有假阳性。但是，在本文中，我们证明，在相同的适当性假设下，在某些网络实例中，任何方法都易于推断假阴性边缘或假阳性边缘。从图形模型理论中借用术语，我们说这些系统对其网络不忠。我们为动态系统（称为Granger-Faithfulness，以及大量的动态网络）形式化了一种忠实的变体，我们表明Granger-Unfaithful Systems构成了Lebesgue Zero Zero Zero-Measure集合。对于同一类的网络，在Granger-Faithfulness的假设下，我们提供了一种算法，该算法可重建网络拓扑，并保证其输出中没有假阳性和没有错误的负面边缘。我们通过针对某些推断的边缘的方向规则扩展了拓扑重建算法，我们证明规则在Granger-Faithfulness假设下是一致的。
Networked dynamic systems are often abstracted as directed graphs, where the observed system processes form the vertex set and directed edges are used to represent non-zero transfer functions. Recovering the exact underlying graph structure of such a networked dynamic system, given only observational data, is a challenging task. Under relatively mild well-posedness assumptions on the network dynamics, there are state-of-the-art methods which can guarantee the absence of false positives. However, in this article we prove that under the same well-posedness assumptions, there are instances of networks for which any method is susceptible to inferring false negative edges or false positive edges. Borrowing a terminology from the theory of graphical models, we say those systems are unfaithful to their networks. We formalize a variant of faithfulness for dynamic systems, called Granger-faithfulness, and for a large class of dynamic networks, we show that Granger-unfaithful systems constitute a Lebesgue zero-measure set. For the same class of networks, under the Granger-faithfulness assumption, we provide an algorithm that reconstructs the network topology with guarantees for no false positive and no false negative edges in its output. We augment the topology reconstruction algorithm with orientation rules for some of the inferred edges, and we prove the rules are consistent under the Granger-faithfulness assumption.
