The logic of color refinement as an analytical framework for graph dynamical systems

An overarching goal of this project is to develop a general logical framework for specifying and analyzing graph dynamical systems, including Boolean networks, synchronous Hopfield networks, and distributed systems performing local algorithms. The update rules of such systems can often be expressed using logical operators in certain variants of first-order logic with counting and their extensions to weighted structures. Additionally, graph dynamical systems with continuous time and continuous states, known as coupled cell networks, can also be studied from a logical perspective. In particular, their synchronization patterns can be characterized by properties of their interaction graphs which are formalizable in two-variable logic with counting quantifiers.

Many dynamical behaviors of logically specified systems can be well understood combinatorially in terms of the Color Refinement procedure (also known as 1-dimensional Weisfeiler-Leman algorithm) and related concepts such as covering maps and equitable partitions. These combinatorial techniques have been extensively used in research on the graph isomorphism problem.

One of our key objectives is to transfer and extend the methods developed in this context to the study of dynamical systems on graphs.
Within this framework, we aim to investigate how the dynamical properties of a system depend on the syntactic complexity of its logical specification.
Additionally, we seek to explore the average-case dynamics of logically specified networks and estimate the performance of local distributed algorithms using logical methods.
Inspired by recent applications of Color Refinement in solving the alignment problem for correlated random graphs, we will also explore its potential in addressing the data reconciliation problem for relational structures.