Noda Atsushi, Hino Hideitsu, Tatsuno Masami, Akaho Shotaro, Murata Noboru
School of Science and Engineering, Waseda University, Shinjuku, Tokyo 169-8555, Japan
Neural Comput. 2014 Jul;26(7):1455-83. doi: 10.1162/NECO_a_00603. Epub 2014 Apr 7.
A graph is a mathematical representation of a set of variables where some pairs of the variables are connected by edges. Common examples of graphs are railroads, the Internet, and neural networks. It is both theoretically and practically important to estimate the intensity of direct connections between variables. In this study, a problem of estimating the intrinsic graph structure from observed data is considered. The observed data in this study are a matrix with elements representing dependency between nodes in the graph. The dependency represents more than direct connections because it includes influences of various paths. For example, each element of the observed matrix represents a co-occurrence of events at two nodes or a correlation of variables corresponding to two nodes. In this setting, spurious correlations make the estimation of direct connection difficult. To alleviate this difficulty, a digraph Laplacian is used for characterizing a graph. A generative model of this observed matrix is proposed, and a parameter estimation algorithm for the model is also introduced. The notable advantage of the proposed method is its ability to deal with directed graphs, while conventional graph structure estimation methods such as covariance selections are applicable only to undirected graphs. The algorithm is experimentally shown to be able to identify the intrinsic graph structure.
图是一组变量的数学表示形式，其中一些变量对由边连接。图的常见示例包括铁路、互联网和神经网络。估计变量之间直接连接的强度在理论和实践上都很重要。在本研究中，考虑了从观测数据估计内在图结构的问题。本研究中的观测数据是一个矩阵，其元素表示图中节点之间的相关性。这种相关性所代表的不仅仅是直接连接，因为它包括各种路径的影响。例如，观测矩阵的每个元素表示两个节点处事件的共现或对应于两个节点的变量的相关性。在这种情况下，虚假相关性使得直接连接的估计变得困难。为了缓解这一困难，使用有向图拉普拉斯算子来表征图。提出了这种观测矩阵的生成模型，并介绍了该模型的参数估计算法。所提方法的显著优点是能够处理有向图，而诸如协方差选择等传统图结构估计方法仅适用于无向图。实验表明该算法能够识别内在图结构。
