Robust Textual Inference via Graph Matching

We present a system for deciding whether a given sentence can be inferred from text. Each sentence is represented as a directed graph (extracted from a dependency parser) in which the nodes represent words or phrases, and the links represent syntactic and semantic relationships. We develop a learned graph matching approach to approximate entailment using the amount of the sentence's semantic content which is contained in the text. We present results on the Recognizing Textual Entailment dataset (Dagan et al., 2005), and show that our approach outperforms Bag-Of-Words and TF-IDF models. In addition, we explore common sources of errors in our approach and how to remedy them.

• Publication year

  2005

• Venue

  Human Language Technology - The Baltic Perspectiv

• Publication date

  2005-10-06

• Fields of study

  Computer Science

• Identifiers
  DOI 10.3115/1220575.1220624
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Robust Textual Inference using Diverse Knowledge Sources

  2005cited by this paper
• The PASCAL Recognising Textual Entailment Challenge

  2005cited by this paper
• Joint Learning Improves Semantic Role Labeling

  2005cited by this paper
• Robust Textual Inference Via Learning and Abductive Reasoning

  2005cited by this paper
• WordNet::Similarity - Measuring the Relatedness of Concepts

  2004cited by this paper
• Learning Syntactic Patterns for Automatic Hypernym Discovery

  2004cited by this paper
• Natural Language Inference via Dependency Tree Mapping: An Application to Question Answering

  2004cited by this paper
• VerbOcean: Mining the Web for Fine-Grained Semantic Verb Relations

  2004cited by this paper
• COGEX: A Logic Prover for Question Answering

  2003influential reference
• Head-Driven Statistical Models for Natural Language Parsing

  2003cited by this paper
• Accurate Unlexicalized Parsing

  2003cited by this paper
• Bleu: a Method for Automatic Evaluation of Machine Translation

  2002cited by this paper
• DIRT – Discovery of Inference Rules from Text

  2001influential reference
• DIRT @SBT@discovery of inference rules from text

  2001influential reference
• Experiments with Open-Domain Textual Question Answering

  2000cited by this paper
• Book Reviews: WordNet: An Electronic Lexical Database

  1999cited by this paper
• An Electronic Lexical Database

  1998influential reference
• Using Information Content to Evaluate Semantic Similarity in a Taxonomy

  1995cited by this paper

• Information-Theoretic Limits on Exact Subgraph Alignment Problem

  2026cites this paper
• Strong Detection Threshold for Correlated Erd\H{o}s-R\'enyi Graphs with Constant Average Degree

  2025cites this paper
• On the Information-Theoretic Limit of Subgraph Alignment

  2025cites this paper
• Testing Correlation in Graphs by Counting Bounded Degree Motifs

  2025cites this paper
• Statistical-computational gap in multiple Gaussian graph alignment

  2025cites this paper
• A Polynomial-Time Iterative Algorithm for Random Graph Matching with Nonvanishing Correlation

  2025cites this paper
• Detecting Correlation Between Multiple Unlabeled Gaussian Networks

  2025cites this paper
• Sample Complexity of Correlation Detection in the Gaussian Wigner Model

  2025cites this paper
• Exact Random Graph Matching with Multiple Graphs

  2025cites this paper
• Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphs

  2024cites this paper
• Aligning Multiple Inhomogeneous Random Graphs: Fundamental Limits of Exact Recovery

  2024cites this paper
• Extraction of Event Structures from Text

  2024influential citation
• Robust random graph matching in Gaussian models via vector approximate message passing

  2024cites this paper
• Bridge to better understanding: Syntax extension with virtual linking-phrase for natural language inference

  2024cites this paper
• A computational transition for detecting correlated stochastic block models by low-degree polynomials

  2024cites this paper
• Linguistically Informed Language Generation: A Multi-faceted Approach

  2024cites this paper
• The Umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regime

  2024cites this paper
• Efficiently matching random inhomogeneous graphs via degree profiles

  2023cites this paper
• Graph-Based Interactive Matching for Pairs of News Articles

  2023cites this paper
• Low-Degree Hardness of Detection for Correlated Erdős-Rényi Graphs

  2023cites this paper
• A Comprehensive Survey of Graph-level Learning

  2023cites this paper
• Robust Graph Matching when Nodes are Corrupt

  2023cites this paper
• Efficient Algorithms for Attributed Graph Alignment With Vanishing Edge Correlation

  2023cites this paper
• Independence testing for inhomogeneous random graphs

  2023cites this paper
• The algorithmic phase transition of random graph alignment problem

  2023cites this paper
• A polynomial-time iterative algorithm for random graph matching with non-vanishing correlation

  2023cites this paper
• Efficient Algorithms for Exact Graph Matching on Correlated Stochastic Block Models with Constant Correlation

  2023cites this paper
• State of the Art and Potentialities of Graph-level Learning

  2023cites this paper
• SeedGNN: Graph Neural Networks for Supervised Seeded Graph Matching

  2022cites this paper
• Matching recovery threshold for correlated random graphs

  2022cites this paper
• A Polynomial Time Iterative Algorithm for Matching Gaussian Matrices with Non-vanishing Correlation

  2022cites this paper
• A polynomial‐time approximation scheme for the maximal overlap of two independent Erdős–Rényi graphs

  2022cites this paper
• The Power of D-hops in Matching Power-Law Graphs

  2021cites this paper
• Attributed Graph Alignment

  2021cites this paper
• Testing network correlation efficiently via counting trees

  2021cites this paper
• Similarity Is Not Entailment - Jointly Learning Similarity Transformation for Textual Entailment

  2021cites this paper
• Attributed Graph Alignment

  2021cites this paper
• Graph matching beyond perfectly-overlapping Erdős–Rényi random graphs

  2020cites this paper
• Sharp threshold for alignment of graph databases with Gaussian weights

  2020cites this paper
• A Lexico-Syntactic-Semantic Approach to Recognizing Textual Entailment

  2020cites this paper
• Graph Matching with Partially-Correct Seeds

  2020cites this paper
• Probing the Probing Paradigm: Does Probing Accuracy Entail Task Relevance?

  2020cites this paper
• Testing correlation of unlabeled random graphs

  2020cites this paper
• Network Sampling through Crawling

  2019cites this paper
• Spectral alignment of correlated Gaussian random matrices

  2019cites this paper
• Extracting Code-relevant Description Sentences Based on Structural Similarity

  2019cites this paper
• Graph Convolutional Networks with Structural Attention Model for Aspect Based Sentiment Analysis

  2019cites this paper
• EQUATE: A Benchmark Evaluation Framework for Quantitative Reasoning in Natural Language Inference

  2019cites this paper
• Spectral alignment of correlated Gaussian matrices

  2019cites this paper
• Knowledge Enhanced Attention for Robust Natural Language Inference

  2019cites this paper
• Unraveling Antonym’s Word Vectors through a Siamese-like Network

  2019cites this paper
• Detecting Subevents using Discourse and Narrative Features

  2019cites this paper
• Sentiment Classification for Hotel Booking Review Based on Sentence Dependency Structure and Sub-Opinion Analysis

  2018cites this paper
• AdvEntuRe: Adversarial Training for Textual Entailment with Knowledge-Guided Examples

  2018cites this paper
• Seeded graph matching via large neighborhood statistics

  2018cites this paper
• Efficient random graph matching via degree profiles

  2018cites this paper
• Stress Test Evaluation for Natural Language Inference

  2018cites this paper
• Análise de Medidas de Similaridade Semântica na Tarefa de Reconhecimento de Implicação Textual (Analysis of Semantic Similarity Measures in the Recognition of Textual Entailment Task)[In Portuguese]

  2017influential citation
• Natural language inference using LSTM model with sentence fusion

  2017cites this paper
• Automated Assessment of the Quality of Peer Reviews using Natural Language Processing Techniques

  2017cites this paper
• VIETNAMESE SENTIMENT ANALYSIS FOR ONLINE BOOKING HOTEL REVIEW BASED ON TERM FEATURE SELECTION AND DEPENDENCY TREE BY TRAN

  2017cites this paper
• Recognition of Textual Entailment using Composition of Semantic Relation

  2017cites this paper
• Investigating Citation Linkage Between Research Articles

  2017cites this paper
• Compositional Lexical Semantics in Natural Language Inference

  2017cites this paper
• The Detection of Contradictory Claims in Biomedical Abstracts

  2016cites this paper
• A Decomposable Attention Model for Natural Language Inference

  2016cites this paper
• On Automatic Question Answering Using Efficient Primal-Dual Models

  2016cites this paper
• Annotating Entailment Relations for Shortanswer Questions

  2015cites this paper
• Recognizing Textual Entailment by Soft Dependency Tree Matching

  2015cites this paper
• Posterior Regularization for Structured Latent Varaible Models

  2015cites this paper
• Knowledge-Based Textual Inference via Parse-Tree Transformations

  2015cites this paper
• A survey on how to cross-reference web information sources

  2015cites this paper
• A survey of graphs in natural language processing*

  2015cites this paper
• How free is ‘free’ word order in Sanskrit?

  2015cites this paper
• Proceedings of the 2nd Workshop on Natural Language Processing Techniques for Educational Applications

  2015cites this paper
• Recognizing Textual Entailment Using Probabilistic Inference

  2015cites this paper
• Towards an automated system for short-answer assessment using ontology mapping

  2015influential citation
• Author verification using a Graph-based Representation

  2015cites this paper
• The Question Answering System of DCUMT in NTCIR-11 QALab

  2014cites this paper
• Is the Stanford Dependency Representation Semantic?

  2014cites this paper
• Semantic Parsing via Paraphrasing

  2014cites this paper
• Converting Phrase Structures to Dependency Structures in Sanskrit

  2014cites this paper
• Causation in the Wild

  2014cites this paper
• Text Entailment and Machine Translation Evaluation

  2014cites this paper
• Unsupervised Event Coreference Resolution

  2014cites this paper
• Un modelo simple para la detección del juicio de implicación textual entre sentencias

  2014cites this paper
• Logical Inference on Dependency-based Compositional Semantics

  2014cites this paper
• Minimally supervised dependency-based methods for natural language processing

  2013cites this paper
• Determining is-a relationships for Textual Entailment

  2013cites this paper
• Mildly Non-Projective Dependency Grammar

  2013cites this paper
• Graph-Structures Matching for Review Relevance Identification

  2013cites this paper
• The semantics of role labeling

  2013cites this paper
• EXPLOITING STRUCTURED DATA FOR MACHINE LEARNING: ENHANCEMENTS IN EXPRESSIVE POWER AND COMPUTATIONAL COMPLEXITY

  2013cites this paper
• Local Graph Matching with Active Learning for Recognizing Inference in Text at NTCIR-10

  2013influential citation
• Entailment in Semantic Web World

  2013cites this paper
• Approximate Subgraph Matching-Based Literature Mining for Biomedical Events and Relations

  2013cites this paper
• Recognizing Textual Entailment II : An Extension of a Deep Semantic Approach via Dependency Parsing

  2013cites this paper
• テキスト含意認識に有効な意味類似度変換及びその獲得法;テキスト含意認識に有効な意味類似度変換及びその獲得法;Jointly Learning Similarity Transformations for Textual Entailment

  2013cites this paper
• Workshop on Events: Definition, Detection, Coreference, and Representation, EVENTS@NAACL-HLT 2013, Atlanta, Georgia, USA, June 14, 2013

  2013cites this paper
• A framework for ontology-based question answering with application to parasite data

  2013cites this paper