# Learning Hyperedge Replacement Grammars for Graph Generation

arXiv: https://arxiv.org/abs/1802.08068 · HTML: https://mlsanity.com/paper/1802.08068/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Feb 2018.

## Built on by (most cited first, 2 of 2)

- [Data-Efficient Graph Grammar Learning for Molecular Generation](https://mlsanity.com/paper/2203.08031/) (2022)
- [Dynamic Vertex Replacement Grammars](https://mlsanity.com/paper/2303.11553/) (2023)

## Abstract (arXiv)

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.