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.
翻译:上下文无关图形语法展示了在现实关系数据中模拟结构的非凡能力。然而,图形语法缺乏捕捉时间变化现象的能力,因为产生规则的从左到右的转换不代表时间变化。在本研究中,我们描述了动态顶点替换语法(DyVeRG),它在时间域中推广了顶点替换语法,通过提供一个正式的框架来更新与其基础数据的修改相符的学习的图形语法。我们展示了DyVeRG语法可以从真实世界动态图表中被学习和使用来生成忠实的图形,同时仍然具有人类可解释性。我们也展示了它们的预测能力,通过计算存在于这个框架中的新颖的图形相似度量——dyvergence分数。