Graph Matching and Graph Rewriting: GREW tools for corpus exploration, maintenance and conversion (2021)

Abstract: This article presents a set of tools built around the Graph Rewriting computational framework which can be used to compute complex rule-based transformations on linguistic structures. Application of the graph matching mechanism for corpus exploration, error mining or quantitative typology are also given.

## introduction the motivation of grew is to have an effective tool to design rule-based transformations of linguistic structures. when designing grew, our goal was to be able to manipulate at least syntactic and semantic representations of natural language (one of the first application of grew was the modeling of a syntax-semantics interface). in a naive view, we can say that syntactic structures are trees and semantic ones are graphs. then, if we want to work with both kinds of structures in a common framework, we can use the fact that a tree can be considered as a graph and hence consider that all structures are graphs. 1 now, if we consider all structures as graphs, how to describe rule-based transformation on these structures? in practice, these transformations can of course be computed with some programs but when it becomes complex and implies many rules, it is difficult to maintain and to debug. to deal with this, we propose to use the graph rewriting formalism to describe these transformations. graph rewriting is a well-defined mathematical formalism and we know that any computable transformation can be expressed by a graph rewriting system. in this approach, a global transformation is decomposed in a successive application of small and local transformations which are described by 1 we may lose information if the order between the child nodes of a given node (see section 2). several graph rewriting tools already exist but some specificities of nlp made it useful to build a system dedicated to this domain. in grew tools, a built-in notion of feature structure is available and rules can be parametrised by lexical information. moreover, transformations on dependency structures often requires to change head of substructures and a dedicated command ease this kind of operation (see section 3.5). in section 2, we give a more precise definition of our graphs and graph rewriting framework and the next parts present examples about rewriting (section 3) and about matching (section 4). ## graphs and graph rewriting the book @xcite gives a complete description of the graphs and graph rewriting system used in grew. we give here a short description on the main aspects. in our framework, a graph is defined by a set of nodes labelled by non-recursive feature structure and a set of labelled edges (note that edges encode relations and hence, we do not consider multiple edges with the same label on the same pair of nodes). in addition to the usual graph mathematical definition of graphs, we also add a notion of order on nodes. for each graph, a sub-part of the nodes are ordered. the subset of ordered nodes can contains all the nodes (for instance in dependency structures like in figure 1 ); it can be empty (for instance in semantic graphs like amr structures shown in section 4.2); but we can also have structures where a strict subpart is ordered, for instance with phrase structure trees where lexical nodes are ordered following the tokens order in the input sentence whereas non-lexical nodes are unordered. global transformations of graphs are decomposed in small steps; each step is described as a rule. a rule encodes a local transformation and is composed in two parts: the left-hand side which expresses the conditions for the application of the rule and the right-hand part which describes the modifications to be done on the graph. formally, the conditions of application are described by a pattern which is itself a graph. graph matching is used to decide if a pattern can be found in a graph. the pattern can be refined by a set of nap (negative application patterns) which are used to filter out some occurrences given by the first pattern. the main pattern is introduced by the keyword pattern and naps are introduced with the keyword without (see examples in the next section). to avoid complex mathematical definitions and to propose an operational way to modify graph, grew describes the modifications of the graph through a sequence of atomic commands for edge deletion, edge creation, feature updating. . . when the number of rules increases, it may become tricky to control the order in which they should be applied; a dedicated notion of rewriting strategies was design to let the user control these applications. when using rewriting, confluence and termination are important aspects. these questions are discussed on examples in the next section. ## graph rewriting in practice the goal of this section is to present through examples the usage of the rewriting part of grew. some important concepts like confluence and termination will be also discussed. ## application of graph matching graph matching is a subpart of the system used to describe left part of rewriting rules, but it is also useful alone as a way to make requests on a graph or a set of graphs. in practice, it can be used for searching examples of a given construction, for checking consistencies of annotations or for error mining. this subpart of grew is now proposed as a separate tool, named grew-match and freely available as a web service foot_2 . this graph matching system is also available in the arboratorgrew tool @xcite 6 . a screenshot of the grew-match interface is shown in figure 3 . with the top bar and the list on the left, the user can chose a corpus (all 183 ud and sud 2.7 corpora and a few other freely available corpora can be requested). a request is entered and the user can visualise the occurrences found in the corpora with elements of the pattern highlighted in the sentence. ## conclusion grew was used in many tasks of corpus conversion. it is used for instance for conversion between ud and sud @xcite : all ud corpora are converted into sud with it. grew is implemented in ocaml and is quite efficient: for instance the conversion of ud 2.7 (1.48m sentences, 26.5m tokens) into sud uses 100 rules and takes 5,500 seconds on a labtop (around 267 graphs rewritten by second). grew is available as a command line program or through a python library. installation proce-dures and usage documentation are given on the grew website: https://grew.fr . a web-based interface for the usage of the rewriting part of the software will be provided soon. in this article, examples are given on dependency syntax and on semantic representations like amr. a more complete set of examples is given in @xcite . many other linguistic structures can be encoded as graphs and we plan to extend the experiments to other kind of semantic representations.