Abstract | ||
---|---|---|
The discovery and analysis of network patterns is 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 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. |
Year | DOI | Venue |
---|---|---|
2019 | 10.1109/TPAMI.2018.2810877 | IEEE transactions on pattern analysis and machine intelligence |
Keywords | DocType | Volume |
Grammar,Robustness,Aggregates,Task analysis,Diseases,Chemicals | Journal | abs/1802.08068 |
Issue | ISSN | Citations |
3 | 0162-8828 | 0 |
PageRank | References | Authors |
0.34 | 18 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Salvador Aguiñaga | 1 | 7 | 3.12 |
David Chiang | 2 | 2843 | 144.76 |
Tim Weninger | 3 | 576 | 46.14 |