图变换规则的自动推断 Automated Inference of Graph Transformation Rules

https://arxiv.org/abs/2404.02692v3

Automated Inference of Graph Transformation Rules

图变换规则的自动推断

摘要

生命科学中可用数据的爆炸式增长正在推动对表达性模型和计算方法日益增长的需求。图变换是一种动态系统模型，具有广泛的应用。我们引入了一种图变换模型构建的新方法，将生成性和动态性视角相结合，以给出一种完全自动化的数据驱动模型推断方法。

该方法以动态性质作为输入，这些性质由显式转换编码为动态的“快照”，并构建一个兼容的模型。所获得的模型被保证是最小的，从而将该方法框定为模型压缩（从一组转换到一组规则）。该压缩允许有损情形，即所构建的模型被允许表现出输入转换之外的行为，从而暗示了对输入动态的补全。

图变换模型推断的任务由于其涉及的组合性而自然具有高度挑战性。我们通过提出将该任务启发式地最小化翻译为一个成熟问题——集合覆盖——来应对指数爆炸，对于该问题存在高度优化的解。我们进一步展示我们的结果如何与以图变换表达的柯尔莫哥洛夫复杂度相关联。

关键词：图变换，模型压缩，柯尔莫哥洛夫复杂度

1. 引言

图是对象通过关系连接的一种非常直观的数学模型。由于兼具可视性和表达性，图的 versatility（多功能性）因其广泛的使用和适应性而得到强调。图变换是一种用于指定如何将一个图重写为另一个图的技术，从而为图的静态建模增加了动态性。图变换是一种强大的形式体系，在理论上有充分的基础 [21, 22, 20]。图变换不仅是计算的通用模型，而且在众多领域和区域享有多样且不断增长的应用，例如软件工程 [23, 12]、生物学 [26, 28, 9, 8] 或化学 [2, 3, 4, 6]。

在图变换中，将一个图重写为另一个图是通过图变换规则（或简称规则）来指定的。一条规则由两个图模式组成，一个用于匹配输入，另一个用于指定输出。将一条规则应用于一个包含输入模式匹配的图，会用输出模式替换匹配的部分。这样一组规则的集合则定义了一个图变换模型。这样的模型以转换系统的通常形式编码行为，其中状态是图，转换是所有可能的规则应用。这种编码行为的显式表示可能任意地大于规则集本身，甚至可能是无限的。

众多新兴的图变换应用，特别是在生命科学领域，挑战了传统的先构建模型（这里，一组规则）再分析涌现行为的方法。相反，我们发现自己处于这样一种情况：一些，可能全部，转换通过经验数据已知，而产生这些转换的模型仍然未知。我们因此面临从它们的应用逆向工程一组规则的问题。我们通过引入一种从（不完整的）转换系统构建图变换模型的完全自动化方法来解决这个问题。

逆向工程方法在化学反应网络的研究中尤其相关。分子传统上表示为无向标记图，化学反应可以自然地由规则，或更准确地说它们的应用来捕获。一个经验推断的化学反应网络（例如，一个细胞的代谢网络）可以被认为是所讨论化学的未知底层模型的可测量表达。识别这个底层模型是网络分析中的一个关键问题。解释经验数据的模型越简单越好，这是一个好的经验法则。

应该注意，定义规则的图模式可能任意大，包括完全指定的图。因此，每个转换本身也是一条规则。推断一个具有相同语义的较小规则集可以被视为图变换模型压缩的一个实例。压缩一个化学反应网络，就像任何其他转换系统一样，在于识别可以通过应用相同规则来再现或解释的反应。从化学上讲，这样的反应很可能在物理化学层面上以相同，或至少高度相似的底层机制发生。因此，通过压缩已知反应来暗示一种化学模型从根本上具有很大的意义。

当已知的化学反应网络可能不完整时，图变换模型压缩有进一步的应用。化学反应网络通常基于部分经验知识，特别是在生物环境中，其中反应本身必须从选定的测量中逆向工程。代谢网络在这方面提出了挑战，由于底层化学的固有复杂性。通常，一个特定的反应仅对单一底物已知，但一些相似的分子很可能能够以相同的方式经历该反应。这样的分子被称为混杂底物，并且在许多研究领域中受到关注，例如酶进化、药物开发或生命起源 [1, 10, 16, 24]。

我们证明，通过执行图变换模型的有损压缩，人们可以获得对混杂底物的建议。特别地，而不是要求规则集精确地再现输入转换，人们可以通过允许以受控方式出现新的规则应用，从而新的转换，来获得一个过度近似。因此，化学反应网络的有损压缩导致一个规则集，它不仅再现所有原始反应，而且还建议新的反应，这些反应在相同的底层机制（规则）上操作，如同现有反应一样，有效地执行网络补全。从纯粹的数学 standpoint（立场），人们也可以认为有损压缩指的是一个不引入任何新变换，而是丢失一些原始变换（欠近似）的规则集，或两者的组合。然而，由于欠近似情况缺乏直接应用，我们将自己限制于通过过度近似进行的有损压缩。

最后但并非最不重要的是，我们可以转向图变换模型压缩本身的性质。特别地，通过最大化压缩比（最小化规则集的大小），我们获得了一种以表达所需行为所需的最小规则数量来衡量的图变换模型复杂性的度量。自然地，这样的复杂性度量可以用于比较各种经验模型，例如化学反应网络。从计算的角度来看，所引入的复杂性度量 closely resembles（密切类似于）柯尔莫哥洛夫复杂度。确实，我们最终得到了一个为图变换问题重述的柯尔莫哥洛夫复杂度的近似。一个精确的表述 additionally（另外）需要考虑规则本身的大小，而不仅仅是它们的数量。

简而言之，我们的贡献是一种形式化方法，用于将图变换模型的已知转换（显式表示的语义）压缩为一组规则（隐式语义）。该方法有两种主要工作模式，一种无损和一种有损压缩，后者产生输入的过度近似。我们讨论了该方法的各种用例，包括逆向工程、复杂性分析和模型补全，并展示了跨各种图变换模型的应用示例。

文章其余部分组织如下。在第2节中，我们回顾必要的图变换定义，并将转换系统的概念形式化为图变换模型行为的显式说明。第3节详细描述了作为生成规则集构建的图变换模型压缩方法。一些说明性应用示例在第4节中提供。最后，第5节提供了我们贡献的总结和一些结束语。

符号说明

该论文包含若干用于说明目的的交换图。不同类型的图函数由不同的箭头类型表示。特别地：

2. 预备知识

在本节中，我们建立必要的形式化基础。首先，我们重申图变换的双推送（DPO）框架的相关部分。其次，我们在图变换框架内引入第3节所介绍方法所需的概念，例如转换系统。

定义 2.1.（图）

已经考虑了在表达性上有所不同的若干版本的DPO图变换 [22]，其特征在于对右态射和匹配的单射性要求。我们对规则和应用的定義代表了最一般的情况，当对所讨论的两个态射都没有单射性要求时。然而，为便于展示，我们将示例限制在匹配和右态射都是单态射的情况。

3. 方法

在本节中，我们引入一种形式化方法，它接受一个输入转换系统 S 并产生一个图变换模型——一组规则 R ，其可以再现 S 内捕获的行为。为了形式化地定义这种关系，我们引入生成规则集的概念。我们从单个转换开始。

仅仅基于规则集的大小来确定最小性，每个输入转换系统可能有多个不同的最小（精确）生成规则集。人们可以进一步通过考虑规则本身的大小来细化标准，然而，这样的细化超出了本出版物的范围。

示例 3.1.（生成规则集）
考虑来自示例2.6的输入转换系统 S 。尽管只有三个转换，但存在多个（精确的）生成 S 的规则集。我们在图5中展示了其中一些。

3.1. 最大规则

3.2. 候选规则

注意，虽然该示例类似于简化为一维的元胞自动机，但该行为不能以标准元胞自动机的方式表达，其中每个代理的值仅取决于其直接邻居。相反，精确最小生成规则集由两条规则组成，这两条规则在单个方向上考虑两个最近的邻居。

3.3. 图变换模型的柯尔莫哥洛夫复杂度

4. 实验

在本节中，我们介绍几个大多为人工的应用示例，其显著地比示例3.3中使用的输入转换系统更复杂。所有实验都是使用一个原型实现（https://github.com/JuriKolcak/rule_inference）进行的，该实现被定制用于与图变换框架MØD协同使用。MØD是一个专门用于化学反应网络的图变换框架，并以相应受约束的方式实现DPO。特别地，仅考虑简单图，并且所有规则的右态射 r r和匹配 m m都要求是单射的（单态射）[3]。应该注意，当前的实现纯粹是概念验证，以说明该方法的可能应用，并不是本出版物的重点，也完全没有针对性能进行优化。许多子问题（例如寻找最大公共子规则）的实现严格来说是朴素的。由于这个原因，我们不将计算性能评估视为实验的一部分。

4.1. 正则语言

4.2. 井字棋

4.3. 有机化学——福尔摩斯反应

最后但同样重要的是，我们考虑一个来自化学的例子。特别地，我们研究从甲醛合成单糖的充分研究的机制，通常称为福尔摩斯反应 [13, 11, 15, 5, 19]。福尔摩斯反应是一个合适且简洁的例子，但最重要的是在化学中高度相关，特别是在自催化研究 [32] 和生命起源研究 [30, 7, 29] 中。

伪转换由检索到的两条规则生成。两条由执行醛糖-酮糖异构化的规则生成，九条由醛醇反应规则生成。醛糖-酮糖异构化的伪转换是“自异构化”，即乙醇醛或酮四糖经历醛糖-酮糖异构化为它们自身，即规则应用的结果图与输入图同构。这种类型的异构化对于追踪反应中的单个原子或立体化学可能很重要，然而，在我们在此示例中采用的抽象层次上，是多余的，尽管并非不正确。

5. 讨论

图变换模型——或图变换规则——的设计由手动方法主导。我们提出一种形式化方法，可用于至少部分地自动化规则设计过程。该方法是通用的，可以应用于建模过程的不同阶段，以执行或协助各种任务，包括构建初始设计、验证、补全、评估或优化图变换模型。

该方法是在图上提出的，但唯一需要的形式体系，即子规则的概念和表达真转换（余积）的能力，允许它扩展到任何DPO应用，特别是广义上的广泛黏性范畴，模去元素映射的表示。因此，该方法高度适应确切的應用设置，为各种优化开辟了可能性。这种适应性通过自由增强构成该过程最后一步的ILP实例的目标函数的可能性而进一步增强。

该方法的通用性通过在有多个高度多样化模型上演示规则推断方法而得到强调。实验不仅用于突出该方法本身，用于精确生成规则集的推断和模型补全，而且还用于例证突出的挑战。特别地，该方法依赖于输入转换系统的精确指定，这在使用经验数据时并不总是如此。

因此，我们的贡献主要在于框架的形式化，该框架允许我们从现有、经验或期望行为的角度探索图变换模型。精确的实现，仅仅是众多可能性之一，退居次要角色。即使作为一个形式化框架，我们也仅剖析了问题的一部分——过度近似——省略了欠近似情况，即允许输入转换系统的一些转换不被生成，以利于更仔细的处理。

我们的形式体系试图阐明一种图变换以及其他基于规则和生成模型整体的形式化分析的新方法。我们相信，新的视角与方法的灵活性相结合，为进一步研究提供了肥沃的土壤。无论是可以从丰富的可用经验数据中受益的数据驱动应用和案例研究。或者也许是一种针对该方法本身的形式化方法，它可能受益于与现有经过充分研究的形式体系（如抽象解释 [17]）的联系。确实，生成规则集的构建可以被视为一个抽象函数，而将规则集应用于输入图则是具体化函数，两者共同构成一个伽罗瓦连接 [18]。

原文链接：https://arxiv.org/pdf/2404.02692v3