Semgrex and Ssurgeon, Searching and Manipulating Dependency Graphs
John Bauer Chloe Kiddon Eric Yeh Alex Shan Christopher D. Manning

Mitigating Automotive Radar Interference using Onboard Intelligent Reflective Surface

    Shree Prasad Maruthi^*, Karrthik G. K.^**, Vijaya Krishna A.^†, Mahbub Hassan^, Jinhong Yuan^
		^*Dept. of Electrical and Electronics Engineering, WILP Division, BITS Pilani, India 

			^**Charcoal Technologies, Bengaluru, India, ^†Bosch Global Software Ltd., Bengaluru, India 

			^ School of Computer Science and Engineering, University of New South Wales, Sydney, Australia

			^ School of Electrical Engineering and Telecommunications, University of New South Wales, Sydney, Australia

			Email: shreeprasadm@gmail.com, karrthik.gk23@gmail.com, A.VijayaKrishna@in.bosch.com, mahbub.hassan@unsw.edu.au,
 j.yuan@unsw.edu.au
		

    
=========================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================


Searching dependency graphs and manipulating them can be a time consuming and challenging task to get right.  We document Semgrex, a system for searching dependency graphs, and introduce Ssurgeon, a system for manipulating the output of Semgrex.  The compact language used by these systems allows for easy command line or API processing of dependencies.  Additionally, integration with publicly released toolkits in Java and Python allows for searching text relations and attributes over natural text.




§ INTRODUCTION


With the rapid growth in languages supported by Universal
Dependencies <cit.>, being able to easily
and quickly search over dependency graphs greatly simplifies
processing of UD datasets.  Tools which allow for searching of
specific relation structures greatly simplify the work of linguists
interested in specific syntactic constructions and researchers
extracting relations as features for downstream tasks.  Furthermore,
converting existing dependency treebanks from non-UD sources to match
the UD format is valuable for adding additional data to Universal
Dependencies, and doing this conversion automatically greatly reduces
the time needed to add more datasets to UD.  Accordingly, several
tools have been developed for searching, displaying, and converting
existing datasets.

In this paper, we describe Semgrex, a tool which searches for
regex-like patterns in dependency graphs, and Ssurgeon, a tool to
rewrite dependency graphs using the output of Semgrex.  Both
systems are written in Java, with Java API and command line tools
available.  In addition, there is a Python interface, including using
displaCy <cit.> as a
library to visualize the results of searches and transformation
operations.  The tools can be used programmatically to enable further
processing of the results or used via the included command line tools.
Furthermore, a web interface[<https://corenlp.run/>] shows the
results of applying patterns to raw text.

Semgrex was released as part of CoreNLP
<cit.>.  As such, it has been
used in several projects (section <ref>).  Several existing
uses of Semgrex make use of it via the API, one of the strengths of
the system, such as the OpenIE relation extraction
of <cit.>.

More recently,
we have added new pattern matching capabilities such as exact edge
matching, a new python interface, and performance improvements.  The
previously unpublished Ssurgeon adds useful new capabilities
for transforming dependency graphs.

Many of the features described here are similar to those in
Grew-Match <cit.> and
Semgrex-Plus <cit.>.  Similar to Ssurgeon,
Semgrex-Plus uses Semgrex to find matches for editing, but Ssurgeon
supports a wider range of operations.  Compared with Grew-Match,
Semgrex and Ssurgeon have the ability to start with raw text and
search for dependency relations directly.





§ SEMGREX


Semgrex and Ssurgeon are publicly released as part of the CoreNLP software package <cit.>[<https://stanfordnlp.github.io/CoreNLP/>].  Semgrex reads dependency trees from CoNLL-U files or parses dependencies from raw text using the associated CoreNLP parser.

Search patterns are composed of two pieces: node descriptions and
relations between nodes.  A search is executed by iterating over
nodes, comparing each word to the node search pattern and checking its
relationships with its neighbors using the relation search patterns.



 §.§ Node Patterns


Dependency graphs of words and their dependency relations are
represented internally using a directed graph, with nodes representing
the words and labeled edges representing the dependencies.

When searching over nodes, the most generic node description is
empty curly brackets.  This search matches every node in the graph:



Within the brackets, any attributes of the words available to Semgrex can be queried.  For example, to query a person's name:



It is possible to use standard string regular expressions, using the match semantics, within the attributes:



A node description can be negated.  For example, this will match any
word, as long as it does not start with Jen, Jenny, Jennifer, etc.



Node descriptions can also be combined:



See Table <ref> for a list of commonly used word
attributes.  Note that  may require a tool which provides
NER annotations, such as <cit.> (Java) or <cit.> (Python),
as those are typically not part of UD treebanks.





 §.§ Relation Patterns




Adding relations between nodes allows for searching over graph
structures, making Semgrex a powerful search tool over
dependency graphs.  The relations used can be from any dependency
formalism, although CoreNLP and Stanza both use Universal Dependencies
by default.

The simplest relations are parent and child:



Many relations consider word order as well, such as the sister
relations: + indicates the word on the left of the relation comes
first, and - indicates the word on the right comes first:



See Table <ref> for a list of supported relations.

Relations can have labels, in which case the types on the edge between nodes must match:




   [column sep=0.6cm]
      Jen & rescued & Beckett 

   
   [edge style=blue!60!black,ultra thick,
            label style=fill=green!60,font=,text=black]21nsubj
   23obj





A special token matches exactly at root, such as in this example from the UD conversion of EWT <cit.>:





   [column sep=0.3cm]
      guerrillas & kidnapped & a & cosmetic & surgeon 

   
   [edge style=blue!60!black,ultra thick,
            label style=fill=green!60,font=,text=black]21nsubj
   [edge style=blue!60!black,ultra thick,
            label style=fill=green!60,font=,text=black]25obj
   53det
   54amod




Relations can be chained.  Without parentheses, subsequent relations
all apply to the same node; brackets denote that the later relations
apply between the nodes in brackets as opposed to the head of the
expression.





   [column sep=0.3cm]
      guerrillas & kidnapped & a & cosmetic & surgeon 

   
   [edge style=blue!60!black,ultra thick,
            label style=fill=green!60,font=,text=black]21nsubj
   [edge style=blue!60!black,ultra thick,
            label style=fill=green!60,font=,text=black]25obj
   53det
   54amod








   [column sep=0.3cm]
      guerrillas & kidnapped & a & cosmetic & surgeon 

   
   21nsubj
   [edge style=blue!60!black,ultra thick,
            label style=fill=green!60,font=,text=black]25obj
   53det
   [edge style=blue!60!black,ultra thick,
            label style=fill=green!60,font=,text=black]54amod




More advanced conjunction and disjunction operations are also possible.  The JavaDoc[<https://nlp.stanford.edu/nlp/javadoc/javanlp/edu/stanford/nlp/semgraph/semgrex/SemgrexPattern.html>] reference describes the complete syntax.



 §.§ Named Nodes and Relations


It is possible to name one or more nodes as part of a Semgrex pattern.
This allows for relations between three or more nodes using
backreferences.  When a node is named in a backreference, it must be
the exact same node as the first instance for the pattern to match.





   [column sep=0.3cm]
      Paul & and & Mary & are & running 

   
   32cc
   [edge style=blue!60!black,ultra thick,
            label style=fill=green!60,font=,text=black]53nsubj
   54aux
   [edge style=blue!60!black,ultra thick,
            label style=fill=green!60,font=,text=black]51nsubj
   [edge style=blue!60!black,ultra thick,
            label style=fill=green!60,font=,text=black]13conj




It is also possible to name the edges.  This is useful when combined
with Ssurgeon, which can manipulate an edge based on its name.





   [column sep=0.3cm]
      Paul & and & Mary & are & running 

   
   32cc
   [edge style=blue!60!black,ultra thick,
            label style=fill=green!60,font=,text=black]53nsubj
   54aux
   [edge style=blue!60!black,ultra thick,
            label style=fill=green!60,font=,text=black]51nsubj
   [edge style=blue!60!black,ultra thick,
            label style=fill=red!60,font=,text=black]13conj






 §.§ Concrete Example



Here are a couple examples from a slot filling task using Semgrex.
Both examples search for “son” or “daughter” in relation to possible
family members.  <cit.>

This matches “John's daughter, Logan, …”



This matches “Tommy, son of John, …”





 §.§ Implementation Notes


Under the hood, the tool is built using JavaCC[<https://javacc.github.io/javacc/documentation/grammar.html>] to process input patterns.

The graphs are implemented as a collection of edges as relations, with nodes storing indices and the text information such as word, lemma, and POS.  To represent edges to hidden copy nodes, nodes can be pointers to the same underlying data with a copy index on them.  An example where this happens is I went over the river and through the woods, where the unstated went before through the woods is represented as a copy node.

Nodes are searched in topographical order if possible, and in index order if not, with the intention of making a canonical ordering on the search results.



§ SSURGEON


Ssurgeon is an extension of Semgrex which includes rules to rewrite dependency graphs.

A pattern in Ssurgeon is a pattern for Semgrex with required
named nodes and/or edges, depending on the edit type, along with a
edit definition.



 §.§ Edge Editing


To add a new edge, the edit pattern must specify the governor, the
dependent, and the edge type.  The Ssurgeon pattern will add an
edge to each match of the Semgrex pattern.

For example, in the previous “Paul and Mary are running” graph, the
following would add the second nsubj if it did not already exist.
This would be useful for making enhanced dependencies, as basic UD has
conj(Paul, Mary) but not nsubj(running, Mary).)
If the edge already exists, this rule does not add a duplicate edge.





   [column sep=0.3cm]
      Paul & and & Mary & are & running 

   
   32cc
   [edge style=blue!60!black,ultra thick,
            label style=fill=red!60,font=,text=black]53nsubj
   54aux
   [edge style=blue!60!black,ultra thick,
            label style=fill=green!60,font=,text=black]51nsubj
   [edge style=blue!60!black,ultra thick,
            label style=fill=green!60,font=,text=black]13conj




There are two mechanisms for deleting an edge.  The first deletes an edge between two named nodes, and the second deletes a named edge.  All edges which match the Semgrex pattern will be deleted.





   [column sep=0.3cm]
      Paul & and & Mary & are & running 

   
   32cc
   [edge style=blue!60!black,ultra thick,
            label style=fill=green!60,font=,text=black]53nsubj
   54aux
   [edge style=blue!60!black,ultra thick,
            label style=fill=green!60,font=,text=black]51nsubj
   [edge style=blue!60!black,ultra thick,
            label style=fill=red!60,font=,text=black]13conj







   [column sep=0.3cm]
      Paul & and & Mary & are & running 

   
   32cc
   [edge style=blue!60!black,ultra thick,
            label style=fill=green!60,font=,text=black]53nsubj
   54aux
   [edge style=blue!60!black,ultra thick,
            label style=fill=green!60,font=,text=black]51nsubj




Alternatively, removeNamedEdge removes a labeled edge:



There is also a mechanism for relabeling an edge, such as might be handy when mapping dependency graphs from one formalism to another:






 §.§ Node Editing


There are mechanisms to add a node, remove a subgraph starting from a node, and alter the content of a node.

To add a node, specify a position, a node to attach it to, and a
relation.  The position can be at the start or end of a sentence or relative
to an existing node.  For this modification, it is necessary to add a
guard to the Semgrex expression, or it will enter an infinite loop of
adding unlimited new nodes to the graph.

Note that in the following example, searching for a word with no det
and adding a det to the node is already sufficient to prevent runaway nodes.




   [column sep=0.3cm]
      I & bought & hamburger 

   
   21nsubj
   23obj









   [column sep=0.3cm]
      I & bought & a & hamburger 

   
   21nsubj
   24obj
   [edge style=blue!60!black,ultra thick,
            label style=fill=green!60,font=,text=black]43det






§ USAGE



Semgrex has been used for task-specific processing of academic work <cit.>, news summarization <cit.>, text-to-scene generations <cit.>, relation extraction <cit.>, and processing medical documents <cit.>.

Ssurgeon was used internally to simplify sentences using their dependencies as an extension to the textual entailment system in <cit.>.

The Java API and command line interfaces are part of the Java package CoreNLP <cit.>[<https://stanfordnlp.github.io/CoreNLP/>].  The python client is available via Stanza <cit.>[<https://stanfordnlp.github.io/stanza/>]
The code is actively maintained as of 2023, and suggestions for additional Semgrex relations, Ssurgeon operations, or other improvements are welcome at our github repo[<https://github.com/stanfordnlp/CoreNLP>].



 §.§ Python Integration



Both Semgrex and Ssurgeon have Python APIs.  This allows for
operations on the results of Stanza <cit.> on natural language or using
the API in Stanza to read and process existing UD datasets.

Here is an example of using Semgrex on the results of parsing an
article on disease transmission with Stanza to find out what
insect vectors transmit a disease.  The search patterns here are
abridged for readability.






Also included is a mechanism to display graphs as search results,
thanks to an API call to displaCy <cit.>.



§ RELATED WORK




The analysis of dependency treebanks, especially Universal
Dependencies, has a long history of using dependency searching and
rewriting tools.



Constituency treebanks such as the Penn Treebank <cit.>
predate Universal Dependencies.  To analyze such constituency datasets,
Tgrep <cit.> and its successor Tgrep2 <cit.> set the
initial standard for searching tree structured data.  Tregex and
Tsurgeon <cit.> extended the language and
added functionality to rewrite constituency trees.

Semgrex was one of the earliest tools to address the problem
of searching in dependency graphs.  It was previous briefly described
in a paper on entailment that was the first to use Semgrex,
<cit.>, although that paper did not
include Ssurgeon or fully explain the usage of Semgrex.
Semgrex has been used by other research several times in the following years.



The authors of the UD_Italian-VIT
<cit.> dataset used an extension of Semgrex,
Semgrex-Plus <cit.>, to convert the dependency
form of VIT to Universal Dependencies.  Semgrex-Plus adds
edge creation, edge deletion, and word relabeling to a Semgrex result.




Also connected with UniversalDependencies are multiple search engines
which allow for easier viewing of the treebanks.
Tündra <cit.> allows for searching of a variety of
treebanks using the TIGERSearch
format <cit.>.[<https://www.ims.uni-stuttgart.de/documents/ressourcen/werkzeuge/tigersearch/doc/html/QueryLanguage.html>]
Additional treebanks not part of UD are
included <cit.>, although recent UD
updates have not been incorporated.



Grew-Match <cit.>[<http://universal.grew.fr/>]
hosts a website which allows for searching of existing UD and other dependency datasets.
The interface is frequently updated, hosting the latest 2.11 treebanks
as of January 2023.



<cit.> provides a web interface to
backend parsers such as <cit.> and provides
search, visual editing, and automatic pattern matching and
replacement.  However, it does not include a command line tool.



Other tools include UDeasy <cit.>, which provides a graphical interface
which allows for searching of UD treebanks or any other dependency
formalism.  spaCy reimplemented Semgrex as part of the 3.0 release, adding the
DependencyMatcher tool
<cit.>.[<https://spacy.io/api/dependencymatcher>]
UDapi <cit.> provides mechanisms for searching
dependency graphs, parsing text, visualizing the graphs, and
manipulating the graphs themselves.
Odin is a rule-based event extraction framework over dependency structures <cit.>.








§ CONCLUSION


We have introduced Semgrex and Ssurgeon, flexible, simple systems for dependency
matching and dependency tree manipulation.



§ ACKNOWLEDGEMENTS


We would like to thank the reviewers for their helpful feedback on this work.




