Polynomial Graph Parsing with Non-Structural Reentrancies
- URL: http://arxiv.org/abs/2105.02033v3
- Date: Fri, 7 May 2021 08:11:22 GMT
- Title: Polynomial Graph Parsing with Non-Structural Reentrancies
- Authors: Johanna Bj\"orklund, Frank Drewes, and Anna Jonsson
- Abstract summary: Graph-based semantic representations are valuable in natural language processing.
We introduce graph extension grammar, which generates graphs with non-structural reentrancies.
We provide a parsing algorithm for graph extension grammars, which is proved to be correct and run in time.
- Score: 0.2867517731896504
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Graph-based semantic representations are valuable in natural language
processing, where it is often simple and effective to represent linguistic
concepts as nodes, and relations as edges between them. Several attempts has
been made to find a generative device that is sufficiently powerful to
represent languages of semantic graphs, while at the same allowing efficient
parsing. We add to this line of work by introducing graph extension grammar,
which consists of an algebra over graphs together with a regular tree grammar
that generates expressions over the operations of the algebra. Due to the
design of the operations, these grammars can generate graphs with
non-structural reentrancies; a type of node-sharing that is excessively common
in formalisms such as abstract meaning representation, but for which existing
devices offer little support. We provide a parsing algorithm for graph
extension grammars, which is proved to be correct and run in polynomial time.
Related papers
- SAT-Based Algorithms for Regular Graph Pattern Matching [40.86962847131912]
We propose a generalization of graph isomorphism that allows one to check complex structural properties.
This specification is given in the form of a Regular Graph Pattern (ReGaP), a special type of graph inspired by regular expressions.
We propose a SAT-based algorithm for checking if a target graph matches a given ReGaP.
arXiv Detail & Related papers (2023-12-15T18:12:44Z) - Generating Semantic Graph Corpora with Graph Expansion Grammar [0.0]
Lovelace is a tool for creating corpora of semantic graphs.
The system uses graph expansion grammar as a representational language.
Central use cases are the creation of synthetic data to augment existing corpora, and as a pedagogical tool for teaching formal language theory.
arXiv Detail & Related papers (2023-09-15T19:10:19Z) - Conversational Semantic Parsing using Dynamic Context Graphs [68.72121830563906]
We consider the task of conversational semantic parsing over general purpose knowledge graphs (KGs) with millions of entities, and thousands of relation-types.
We focus on models which are capable of interactively mapping user utterances into executable logical forms.
arXiv Detail & Related papers (2023-05-04T16:04:41Z) - Dynamic Vertex Replacement Grammars [6.3872634680339635]
We show that DyVeRG grammars can be learned from, and used to generate, real-world dynamic graphs faithfully.
We also demonstrate their ability to forecast by computing dyvergence scores, a novel graph similarity measurement.
arXiv Detail & Related papers (2023-03-21T02:44:15Z) - Tree-Based Representation and Generation of Natural and Mathematical
Language [77.34726150561087]
Mathematical language in scientific communications and educational scenarios is important yet relatively understudied.
Recent works on mathematical language focus either on representing stand-alone mathematical expressions, or mathematical reasoning in pre-trained natural language models.
We propose a series of modifications to existing language models to jointly represent and generate text and math.
arXiv Detail & Related papers (2023-02-15T22:38:34Z) - GraphQ IR: Unifying Semantic Parsing of Graph Query Language with
Intermediate Representation [91.27083732371453]
We propose a unified intermediate representation (IR) for graph query languages, namely GraphQ IR.
With the IR's natural-language-like representation that bridges the semantic gap and its formally defined syntax that maintains the graph structure, neural semantic parsing can more effectively convert user queries into GraphQ IR.
Our approach can consistently achieve state-of-the-art performance on KQA Pro, Overnight and MetaQA.
arXiv Detail & Related papers (2022-05-24T13:59:53Z) - Explanation Graph Generation via Pre-trained Language Models: An
Empirical Study with Contrastive Learning [84.35102534158621]
We study pre-trained language models that generate explanation graphs in an end-to-end manner.
We propose simple yet effective ways of graph perturbations via node and edge edit operations.
Our methods lead to significant improvements in both structural and semantic accuracy of explanation graphs.
arXiv Detail & Related papers (2022-04-11T00:58:27Z) - Plurality and Quantification in Graph Representation of Meaning [4.82512586077023]
Our graph language covers the essentials of natural language semantics using only monadic second-order variables.
We present a unification-based mechanism for constructing semantic graphs at a simple syntax-semantics interface.
The present graph formalism is applied to linguistic issues in distributive predication, cross-categorial conjunction, and scope permutation of quantificational expressions.
arXiv Detail & Related papers (2021-12-13T07:04:41Z) - Learning the Implicit Semantic Representation on Graph-Structured Data [57.670106959061634]
Existing representation learning methods in graph convolutional networks are mainly designed by describing the neighborhood of each node as a perceptual whole.
We propose a Semantic Graph Convolutional Networks (SGCN) that explores the implicit semantics by learning latent semantic-paths in graphs.
arXiv Detail & Related papers (2021-01-16T16:18:43Z) - Graph-Structured Referring Expression Reasoning in The Wild [105.95488002374158]
Grounding referring expressions aims to locate in an image an object referred to by a natural language expression.
We propose a scene graph guided modular network (SGMN) to perform reasoning over a semantic graph and a scene graph.
We also propose Ref-Reasoning, a large-scale real-world dataset for structured referring expression reasoning.
arXiv Detail & Related papers (2020-04-19T11:00:30Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.