.GReTA-seminar

Multilevel modeling extends traditional modeling techniques with a potentially unlimited number of abstraction levels. Multilevel models can be formally represented by multilevel typed graphs whose manipulation and transformation are carried out by multilevel typed graph transformation rules. These rules are cospans of three graphs and two inclusion graph homomorphisms where the three graphs are multilevel typed over a common typing chain. In this paper, we show that typed graph transformations can be appropriately generalized to multilevel typed graph transformations improving preciseness, flexibility and reusability of transformation rules. We identify type compatibility conditions, for rules and their matches, formulated as equations and inequations, respectively, between composed partial typing morphisms. These conditions are crucial presuppositions for the application of a rule for a match—based on a pushout and a final pullback complement construction for the underlying graphs in the category —to always provide a well-defined canonical result in the multilevel typed setting. Moreover, to formalize and analyze multilevel typing as well as to prove the necessary results, in a systematic way, we introduce the category of typing chains and typing chain morphisms.

Tooling is essential for practical applications in any field. For Graph Transformation, one of the ways to quickly prototype your graph-like domain is by developing a model in GROOVE, a standalone tool that will give you isomorphism checking, state space exploration, and model checking based on a graph grammar consisting of a set of (optionally typed) rules and start graph, optionally complemented with a control program.

In this second part of the tutorials on GROOVE, the following advanced features will be covered: Nested rules, rule parameters, control (functions and recipes), and model checking.

In this talk I will present the state of the research on higher-arity algebras from the perspective of (labelled) hypergraph rewriting. Recent discoveries on ternary algebras enabled by the rewriting approach will be discussed and a proposal for computational foundations of formal objects generalizing diagrammatic calculi, such us the one in category theory, will be introduced. This presentation will be done using recently developed function paclets in Mathematica.

Tooling is essential for practical applications in any field. For Graph Transformation, one of the ways to quickly prototype your graph-like domain is by developing a model in GROOVE, a standalone tool that will give you isomorphism checking, state space exploration and model checking based on a graph grammar consisting of a set of (optionally typed) rules and start graph, optionally complemented with a control program.
In this talk I will show the capabilities of the tool, especially touching on the more advanced features such as nested rules, attribute manipulation, recipes (aka transactions) and various analysis techniques. Some of these are recent extensions. I am also very interested in any type of feedback regarding potential use cases and desirable features.

The laws of Physics are time-reversible, making no qualitative distinction between the past and the future—yet we can only go towards the future. This apparent contradiction is known as the “arrow of time problem”. Its current resolution states that the future is the direction of increasing entropy. But entropy can only increase towards the future if it was low in the past, and past low entropy is a very strong assumption to make, because low entropy states are rather improbable, non-generic. Recent works from the Physics literature suggest, however, we may do away with this so-called “past hypothesis”, in the presence of reversible dynamical laws featuring expansion. We prove that this is the case, for a synchronous graph rewriting-based toy model. It consists in graphs upon which particles circulate and interact according to local reversible rules. Some rules locally shrink or expand the graph. Generic states always expand; entropy always increases—thereby providing a local explanation for the arrow of time. This discrete setting allows us to deploy the full rigour of theoretical Computer Science proof techniques.

I will discuss how Message Passing Neural Networks (MPNNs) model mixing among features in a graph. I will show that MPNNs need as many layers as the commute time between nodes to model strong mixing. This allows to derive a measure for over-squashing and to clarify how the latter limits the expressivity of MPNNs to learn functions with long-range interactions. I will then discuss a novel paradigm for message-passing that determines “when” messages are being propagated based on the geometry of the data and introduces a delay mechanism to greatly enhance the power of MPNNs to capture long-range interactions achieving superior performance than Graph-Transformers even remaining sub-quadratic.

In this talk we describe functorial data migration from a re-writing perspective, by way of the open-source CQL tool from categoricaldata.net. We describe how co-presheaves and their lifting problems can be finitely presented, how solving word problems in categories enables computational category theory, and some techniques for performing functorial data migration using chase algorithms.

Applications of graph transformation (GT) systems often require control structures that can be used to direct GT processes. Most existing GT tools follow a stateful computational model, where a single graph is repeatedly modified “in-place” when GT rules are applied. The implementation of control structures in such tools is not trivial. Common challenges include dealing with the non-determinism inherent to rule application and transactional constraints when executing compositions of GTs, in particular atomicity and isolation. The complexity of associated transaction mechanisms and rule application search algorithms (e.g., backtracking) complicates the definition of a formal foundation for these control structures. Compared to these stateful approaches, functional graph rewriting presents a simpler (stateless) computational model, which simplifies the definition of a formal basis for (functional) GT control structures. In this talk, I will discuss the “Graph Transformation control Algebra” (GTA) as a foundation for functional graph rewriting and its application in the tool GrapeVine.