Generative Graph Prototypes from Information Theory
Generative Graph Prototypes from Information Theory
复制标题
DOI：
10.1109/tpami.2015.2400451
复制
发表时间：
2015-10
影响因子：
23.6
通讯作者：
Lin Han;Richard C. Wilson;E. Hancock
中科院分区：
文献类型：
--
作者：
Lin Han;Richard C. Wilson;E. Hancock
在本文中，我们提出了一种方法，通过采用最小描述长度的方法来构造一组图的生成原型。该方法提出了在学习的生成超图模型，新的样本可以通过一个适当的采样机制。我们开始通过构建一个概率分布的节点和边的超图的出现。我们使用近似的冯诺依曼熵编码的超图的复杂性。EM算法的一个变种的开发，以尽量减少描述长度的标准，其中的结构的超图和样本图和超图之间的节点对应关系被视为丢失的数据。为了生成新的图，我们假设图的节点和边在独立的伯努利分布下出现，并根据它们的节点和边的出现概率对新的图进行采样。对真实数据库的实证评估表明，该算法的实用性，并显示生成模型的有效性，图分类，图聚类和生成新的样本图的任务。
In this paper we present a method for constructing a generative prototype for a set of graphs by adopting a minimum description length approach. The method is posed in terms of learning a generative supergraph model from which the new samples can be obtained by an appropriate sampling mechanism. We commence by constructing a probability distribution for the occurrence of nodes and edges over the supergraph. We encode the complexity of the supergraph using an approximate Von Neumann entropy. A variant of the EM algorithm is developed to minimize the description length criterion in which the structure of the supergraph and the node correspondences between the sample graphs and the supergraph are treated as missing data. To generate new graphs, we assume that the nodes and edges of graphs arise under independent Bernoulli distributions and sample new graphs according to their node and edge occurrence probabilities. Empirical evaluations on real-world databases demonstrate the practical utility of the proposed algorithm and show the effectiveness of the generative model for the tasks of graph classification, graph clustering and generating new sample graphs.