# Dynamic Vertex Replacement Grammars

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 45 references that are in the map.
- First posted on arXiv 21 Mar 2023.

## Builds on (most cited first, 18 of 18)

- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models](https://mlsanity.com/paper/1802.08773/) (2018)
- [From Louvain to Leiden: guaranteeing well-connected communities](https://mlsanity.com/paper/1810.08473/) (2018)
- [Efficient Graph Generation with Graph Recurrent Attention Networks](https://mlsanity.com/paper/1910.00760/) (2019)
- [Simplicial Closure and higher-order link prediction](https://mlsanity.com/paper/1802.06916/) (2018)
- [Molecular Hypergraph Grammar with its Application to Molecular Optimization](https://mlsanity.com/paper/1809.02745/) (2018)
- [Statistical clustering of temporal networks through a dynamic stochastic block model](https://mlsanity.com/paper/1506.07464/) (2015)
- [Data-Efficient Graph Grammar Learning for Molecular Generation](https://mlsanity.com/paper/2203.08031/) (2022)
- [Curvature Filtrations for Graph Generative Model Evaluation](https://mlsanity.com/paper/2301.12906/) (2023)
- [Reinforced Molecular Optimization with Neighborhood-Controlled Grammars](https://mlsanity.com/paper/2011.07225/) (2020)
- [A smart local moving algorithm for large-scale modularity-based community detection](https://mlsanity.com/paper/1308.6604/) (2013)
- [An information-theoretic, all-scales approach to comparing networks](https://mlsanity.com/paper/1804.03665/) (2018)
- [Joint Subgraph-to-Subgraph Transitions -- Generalizing Triadic Closure for Powerful and Interpretable Graph Modeling](https://mlsanity.com/paper/2009.06770/) (2020)
- [Learning Hyperedge Replacement Grammars for Graph Generation](https://mlsanity.com/paper/1802.08068/) (2018)
- [Modeling Graphs with Vertex Replacement Grammars](https://mlsanity.com/paper/1908.03837/) (2019)
- [Towards Interpretable Graph Modeling with Vertex Replacement Grammars](https://mlsanity.com/paper/1910.08579/) (2019)
- [Growing Better Graphs With Latent-Variable Probabilistic Graph Grammars](https://mlsanity.com/paper/1806.07955/) (2018)
- [Attributed Graph Modeling with Vertex Replacement Grammars](https://mlsanity.com/paper/2110.06410/) (2021)

## Abstract (arXiv)

Context-free graph grammars have shown a remarkable ability to model structures in real-world relational data. However, graph grammars lack the ability to capture time-changing phenomena since the left-to-right transitions of a production rule do not represent temporal change. In the present work, we describe dynamic vertex-replacement grammars (DyVeRG), which generalize vertex replacement grammars in the time domain by providing a formal framework for updating a learned graph grammar in accordance with modifications to its underlying data. We show that DyVeRG grammars can be learned from, and used to generate, real-world dynamic graphs faithfully while remaining human-interpretable. We also demonstrate their ability to forecast by computing dyvergence scores, a novel graph similarity measurement exposed by this framework.