Aguinaga Salvador, Chiang David, Weninger Tim
IEEE Trans Pattern Anal Mach Intell. 2019 Mar;41(3):625-638. doi: 10.1109/TPAMI.2018.2810877. Epub 2018 Mar 1.
The discovery and analysis of network patterns are central to the scientific enterprise. In the present work, we developed and evaluated a new approach that learns the building blocks of graphs that can be used to understand and generate new realistic graphs. Our key insight is that a graph's clique tree encodes robust and precise information. We show that a Hyperedge Replacement Grammar (HRG) can be extracted from the clique tree, and we develop a fixed-size graph generation algorithm that can be used to produce new graphs of a specified size. In experiments on large real-world graphs, we show that graphs generated from the HRG approach exhibit a diverse range of properties that are similar to those found in the original networks. In addition to graph properties like degree or eigenvector centrality, what a graph "looks like" ultimately depends on small details in local graph substructures that are difficult to define at a global level. We show that the HRG model can also preserve these local substructures when generating new graphs.
网络模式的发现与分析是科学事业的核心。在当前的工作中，我们开发并评估了一种新方法，该方法能够学习图的构建模块，这些构建模块可用于理解和生成新的现实图。我们的关键见解是，图的团树编码了强大而精确的信息。我们表明，可以从团树中提取超边替换文法（HRG），并且我们开发了一种固定大小的图生成算法，可用于生成指定大小的新图。在对大型真实世界图的实验中，我们表明，通过HRG方法生成的图展现出了与原始网络中发现的性质多样的属性。除了诸如度或特征向量中心性等图属性外，图的“外观”最终取决于局部图子结构中的小细节，而这些细节在全局层面上难以定义。我们表明，HRG模型在生成新图时也能够保留这些局部子结构。
