# Basic Graph Terminology

Semantic graphs (across different frameworks) can be be viewed as directed graphs (or digraphs).  A digraph is a triple 〈TNE〉 where N is a set of nodes and E ⊆N × N is a set of edges.  The in- and out-degree of a node count the number of edges arriving at or leaving from the node, respectively.  In contrast to the unique root node in trees, graphs can have multiple (structural) roots, which we define as nodes with in-degree zero.  The majority of semantic graphs are structurally multi-rooted.  Thus, we distinguish one or several nodes in each graph as top nodes, TN; the top(s) correspond(s) to the most central semantic entities in the graph, usually the main predication(s).

In a tree, every node except the root has in-degree one.  In semantic graphs, nodes can have in-degree two or higher (indicating shared arguments), which constitutes a reentrancy in the graph.  In contrast to trees, general digraphs may contain cycles, i.e. a directed path leading from a node to itself.  Another central property of trees is that they are connected, meaning that there exists an undirected path between any pair of nodes.  In contrast, semantic graphs are not generally connected.

Finally, in some semantic graph frameworks there is a (total) linear order on the nodes, typically induced by the surface order of corresponding tokens.  Such graphs are conventionally called bi-lexical dependency graphs and formally constitute ordered graphs.  A natural way to visualize a bi-lexical dependency graph is to draw its edges as semicircles in the halfplane above the sentence.  A graph is called noncrossing if in such a drawing, the semicircles intersect only at their endpoints (this property is a natural generalization of projectivity as it is known from dependency trees).

A natural generalization of the noncrossing property, where one is allowed to also use the halfplane below the sentence for drawing edges is a property called pagenumber two.  For additional definitions and a quantitative summary of various formal graph properties across frameworks, please see Kuhlmann & Oepen (2016).

# Flavors versus Frameworks

In the context of the shared task, we will distinguish different flavors of semantic graphs based on the nature of the relationship they assume between the linguistic surface signal (typically a written sentence, i.e. a string) and the nodes of the graph.  We refer to this relation as anchoring (of nodes on sub-strings), where other common terms include alignment, correspondence, or lexicalization.

Type (0)  The strongest form of anchoring is obtained in bi-lexical dependency graphs, where graph nodes injectively correspond to surface lexical units (tokens).  In such graphs, each node is directly linked to one specific token (conversely, there may be semantically empty tokens), and the nodes inherit the linear order of their corresponding tokens.

Type (1)  A more general form of anchored semantic graphs is characterized by relaxing the correspondence between nodes and tokens, allowing arbitrary parts of the sentence (e.g. sub-token or multi-token sequences) as node anchors, as well as multiple nodes anchored to overlapping sub-strings.  These graphs afford greater flexibility in the representation of meaning contributed by, for example, (derivational) affixes or phrasal constructions and facilitate lexical decomposition (e.g. of causatives or comparatives).

Type (2)  Finally, some semantic graphs do not consider the correspondence between nodes and the surface string an inherent part of the representation of meaning (thus backgrounding notions of derivation and compositionality).  Such semantic graphs are simply unanchored.  While different flavors refer to formally defined sub-classes of semantic graphs, we will use the term framework for specific linguistic approaches to graph-based meaning representation (typically encoded in a particular graph flavor, of course).

# Frameworks and Sample Graphs

A high-level overview of the meaning representation frameworks represented in the shared task and example semantic graphs are provided as a separate page

XHTML 1.0 | Last updated: 2019-04-26 (16:04)