  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.
