Source-linked AI summary
N-ary Relation Extraction using Graph State LSTM
Linfeng Song, Yue Zhang, Zhiguo Wang, Daniel Gildea
TL;DR
Cross-sentence n-ary relation extraction requires modeling relations among entities distributed across multiple sentences, but splitting document graphs into two DAGs can discard useful structure. The paper introduces graph-state LSTM, which performs parallel recurrent message passing on the original graph and achieves the best reported benchmark performance, including a 5.9% accuracy gain over its DAG LSTM baseline. Its scope also leaves coreference and word-sense information as future directions.
Problem
Splitting document graphs into two DAGs can lose dependency structure and exclude sibling information needed for cross-sentence n-ary relation extraction.
Method
Graph-state LSTM directly models the original graph through parallel recurrent state transitions that exchange information among neighboring words.
Results
5.9% higher accuracy than the bidirectional DAG LSTM baseline, while also surpassing Peng et al. (2017) by 1.2%.
Takeaways & Limitations
Graph-state LSTM provides a more effective graph-based model for encoding rich linguistic knowledge in ternary and binary relation extraction.
Takeaways & Limitations
Future work identifies missing coreference and word-sense information as unresolved directions for the model.
Abstract
from arXiv · showhide
Cross-sentence $n$-ary relation extraction detects relations among $n$ entities across multiple sentences. Typical methods formulate an input as a \textit{document graph}, integrating various intra-sentential and inter-sentential dependencies. The current state-of-the-art method splits the input graph into two DAGs, adopting a DAG-structured LSTM for each. Though being able to model rich linguistic knowledge by leveraging graph edges, important information can be lost in the splitting procedure. We propose a graph-state LSTM model, which uses a parallel state to model each word, recurrently enriching state values via message passing. Compared with DAG LSTMs, our graph LSTM keeps the original graph structure, and speeds up computation by allowing more parallelization. On a standard benchmark, our model shows the best result in the literature.
1 Introduction
Cross-sentence n-ary relation extraction must connect entity mentions across sentences using syntactic and discourse structure. This paper proposes graph-state LSTM to preserve the full graph, incorporate broader context, and improve accuracy over DAG LSTM baselines.
- Motivation: Cross-sentence n-ary extraction identifies relations among several entity mentions appearing in distinct sentences, such as drug, gene, and mutation relations.The example concerns cancers associated with an EGFR mutation and response to gefitinib.
- Prior approach: Prior graph-structured LSTM methods construct document graphs from dependency edges, adjacent-word links, and inter-sentence relations, then split each graph into two DAGs.The split separates left-to-right from right-to-left edges before applying separate recurrent networks.
- Limitations: Splitting graphs can lose important structure, including the dependency relation between “exon-19” and “EGFR”, while DAG LSTMs omit sibling information.The baseline primarily incorporates ancestor and descendant information for each word.
- Proposed model: The proposed graph-state LSTM models the original cyclic graph through recurrent message passing, with every node exchanging information with directly connected nodes at each transition step.Increasing recurrent steps exposes each word to a larger context while nodes operate simultaneously within each step.
- Advantages: Compared with bidirectional DAG LSTM, graph-state LSTM preserves graph structure, incorporates sibling information, and permits greater computational parallelization.These design advantages address information loss and restricted context flow in the DAG formulation.
- Results: 5.9% accuracy improvement over the bidirectional DAG LSTM baseline and 1.2% over Peng et al. (2017) establish the model as the strongest reported result.The paper also reports that graph LSTM empirically uses structural information more effectively than DAG LSTM.
2 Task Definition
Cross-sentence n-ary relation extraction determines whether multiple entity mentions form a relation and, when applicable, identifies which relation holds among them.
- Input: The task represents entity mentions E together with multi-sentence text T, where each entity mention belongs to one sentence.The relation inventory includes a None class for cases where no relation holds.
- Prediction: Binary classification asks whether the entity mentions jointly form a relation, whereas multi-class classification identifies the specific relation type.The example distinguishes whether gefitinib affects the cancer from whether the effect is response, resistance, sensitivity, or another class.
3 Baseline: Bi-directional DAG LSTM
The baseline represents each input graph with two DAG LSTMs after separating left-to-right and right-to-left edges. It incorporates word and edge-label representations, then classifies using entity-mention states.
- Input graphs connect words with dependency, adjacency, and inter-sentence edges carrying syntactic and discourse information.
- The baseline splits each graph into separate forward and backward DAGs and encodes them with two DAG LSTMs.The split separates left-to-right from right-to-left edges.
- The entity mentions’ hidden states from both DAG LSTMs are passed to a logistic regression classifier for prediction.
- Each edge representation combines the source-word embedding with the embedding of its edge label.Edge labels are concatenated with node representations rather than assigned separate gated-network parameters.
- For each word, incoming edge representations and incoming node states are summed before gated state transitions.The transitions use input, output, and forget gates to compute word hidden states.
4 Graph State LSTM
The graph state LSTM models the original graph directly instead of splitting it into two DAGs. It recurrently exchanges information between connected words through parallel gated state updates.
- The model directly applies a graph-structured LSTM to the original input graph without splitting it into two DAGs.It retains the baseline’s input-representation and classification procedures.
- A graph state consists of one hidden state for every word, initialized as zero vectors and updated through recurrent graph states.
- Repeated transitions propagate information from neighboring to non-neighboring words, enabling broader graph context over multiple steps.
- At each transition step, every word exchanges information with all directly connected incoming and outgoing words.Incoming and outgoing states are summed separately before the gated update.
- Gated LSTM cells control information flow from edge inputs and neighboring word states through input, output, and forget gates.
- Unlike the sequential DAG baseline, graph-state node updates can be parallelized and efficiently executed on a GPU.
5 Training
The models are trained on gold-standard graph examples with cross-entropy loss and evaluated using the best development-set model. The dataset statistics describe token and sentence distributions.
- Training minimizes cross-entropy loss over input graphs, gold class labels, and model parameters.
- Table 2 reports average tokens, average sentences, and the percentage of multi-sentence instances in the dataset.
- The model with the best development-set performance is selected for test-set evaluation.
6 Experiments
Experiments evaluate graph state LSTM on ternary, binary, and multi-class relation extraction, comparing it with bidirectional DAG LSTM and prior systems. The model achieves higher accuracy and substantially faster computation while benefiting from direct graph message passing and parallel transitions.
- Settings: Experiments cover binary relation detection, multi-class relation extraction, and biomedical drug-gene-mutation ternary relations.The dataset contains 6987 ternary and 6087 binary instances, evaluated with five-fold cross-validation.
- Model analysis: More transition steps improve graph-state accuracy until performance converges after 4–5 transitions.Using both forward and backward relations performs better than either direction alone, while applying the model to the original graph outperforms concatenating directional states.
- Final results: 5.9% higher test accuracy than the bidirectional DAG baseline is achieved on all ternary instances, with the highest accuracy among compared methods.The graph state LSTM also surpasses Peng et al. (2017) despite not using multi-task learning.
- Final results: Single-sentence evaluation causes performance drops for all systems, while the baseline drops 1.7 points compared with up to 4.1 points for other neural systems.The authors suggest insufficient context and possible overfitting as reasons single-sentence relations are more challenging.
- Efficiency: The graph state LSTM is 8 to 10 times faster than the baseline in training and decoding, respectively.The baseline requires 74 recurrent transition steps per input word, whereas the proposed model uses 5 parallelizable state transitions.
- Analysis: Graph-state LSTM accuracy remains higher on varying sentence lengths and maximal neighborhood sizes, with a larger advantage on shorter instances.The case study reports correct predictions for both examples where bidirectional DAG LSTM fails, including contexts involving sibling indicators.
- Binary and multi-class results: On binary drug-mutation relations, graph-state LSTM outperforms other systems by a large margin, and its advantage increases for more ambiguous multi-class extraction.The results are described as evidence that message passing better encodes rich linguistic knowledge in input graphs.
7 Related Work
Related work covers n-ary relation extraction, graph encoders, and graph recurrent networks. The paper focuses on ternary cross-sentence relations while extending graph-based modeling to preserve richer contextual structure.
- N-ary relation extraction: Earlier n-ary relation extraction often considered single-sentence instances, while cross-sentence approaches simplified context through coreference annotation or coherent-event assumptions.Quirk and Poon (2017) used diverse contextual evidence for binary relations; this paper follows Peng et al. (2017) in studying ternary cross-sentence relations.
- Graph encoders: Graph encoders have been applied to semantic object parsing, semantic role labeling, machine translation, text generation, text representation, and semantic parsing.The cited approaches include graph LSTMs, graph convolutional networks, and graph recurrent networks.
8 Conclusion
The graph-state LSTM preserves the original graph structure while refining graph-context representations, and experiments report significant improvements over prior results. Future work targets coreference and word-sense information.
- The graph-state LSTM recurrently refines a neural graph-state representation for cross-sentence n-ary relation extraction.
- It preserves the input graph structure, avoiding information loss and incorporating sibling information when computing node context.
- It is better parallelizable than the bidirectional DAG LSTM baseline.
- Experiments show significant improvements over previously reported results, including the bidirectional graph LSTM model.
- Future work considers adding coreference and word-sense information.