Automated Inference of Graph Transformation Rules
<|reference_start|>Automated Inference of Graph Transformation Rules: The explosion of data available in life sciences is fueling an increasing demand for expressive models and computational methods. Graph transformation is a model for dynamic systems with a large variety of applications. We introduce a novel method of the graph transformation model construction, combining generative and dynamical viewpoints to give a fully automated data-driven model inference method.   The method takes the input dynamical properties, given as a "snapshot" of the dynamics encoded by explicit transitions, and constructs a compatible model. The obtained model is guaranteed to be minimal, thus framing the approach as model compression (from a set of transitions into a set of rules). The compression is permissive to a lossy case, where the constructed model is allowed to exhibit behavior outside of the input transitions, thus suggesting a completion of the input dynamics.   The task of graph transformation model inference is naturally highly challenging due to the combinatorics involved. We tackle the exponential explosion by proposing a heuristically minimal translation of the task into a well-established problem, set cover, for which highly optimized solutions exist. We further showcase how our results relate to Kolmogorov complexity expressed in terms of graph transformation.<|reference_end|>
@article{andersen2024automated,
    title={Automated Inference of Graph Transformation Rules},
    author={Jakob L. Andersen, Akbar Davoodi, Rolf Fagerberg, Christoph Flamm,
  Walter Fontana, Juri Kolv{c}'ak, Christophe V.F.P. Laurent, Daniel Merkle,
  Nikolai N{o}jgaard},
    journal={arXiv preprint arXiv:2404.02692},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.02692},
    primaryClass={cs.DM cs.LG q-bio.MN}
}