Graph Transformation

Discovering the underlying structures present in large real world graphs is a fundamental scientific problem. Recent work at the intersection of formal language theory and graph theory has found that a Probabilistic Hyperedge Replacement Grammar (PHRG) can be extracted from a tree decomposition of any graph. However, because the extracted PHRG is directly dependent on the shape and contents of the tree decomposition, rather than from the dynamics of the graph, it is unlikely that informative graph-processes are actually being captured with the PHRG extraction algorithm. To address this problem, the current work adapts a related formalism called Probabilistic Synchronous HRG (PSHRG) that learns synchronous graph production rules from temporal graphs. We introduce the PSHRG model and describe a method to extract growth rules from the graph. We find that SHRG rules capture growth patterns found in temporal graphs and can be used to predict the future evolution of a temporal graph. We perform a brief evaluation on small synthetic networks that demonstrate the prediction accuracy of PSHRG versus baseline and state of the art models. Ultimately, we find that PSHRGs seem to be very good at modelling dynamics of a temporal graph; however, our prediction algorithm, which is based on string parsing and generation algorithms, does not scale to practically useful graph sizes.

When specifying graph languages via type graphs, cores are a convenient way to minimize the type graph without changing the graph language, i.e. the set of graphs typed over the type graph. However, given a type graph, the problem of finding its core is NP-hard. Using the Tool CoReS, we automatically encode all required properties into SAT- and SMT-formulas to iteratively compute cores by employing the corresponding solvers. We obtain runtime results to evaluate and compare the two encoding approaches.

AGREE is a new approach to algebraic graph transformation. It provides sophisticated mechanisms for object cloning and non-local manipulations. It is for example possible to delete all edges in a graph by a single rule application. Due to these far-reaching effects of rule application, Church-Rosser results are difficult to obtain. Currently, there are only sufficient conditions for parallel independence, i.e. there are independent situations which are not classified independent by the existing conditions. In this paper, we characterise all independent situations.