Graph Sequential Network for Reasoning over Sequences

Ming Tu, Jing Huang, Xiaodong He, Bowen ZhouarXiv 2020 · arXiv

Abstract

Standard Graph Neural Networks (GNNs) often "squash" sequences of text into single vectors before reasoning, leading to significant information loss. We introduce the Graph Sequential Network (GSN), which performs message passing directly over sequences using a co-attention mechanism. This architecture enables powerful multi-hop reasoning while preserving word-level details, allowing for fine-grained tasks like sequence labeling. GSN consistently outperforms standard GNN baselines on complex reasoning benchmarks like HotpotQA and FEVER.

Introduction

In many Natural Language Processing (NLP) tasks, such as multi-hop question answering or fact verification, models must reason across multiple pieces of information. Researchers frequently employ Graph Neural Networks (GNNs) for this purpose, representing sentences or documents as nodes. However, standard GNNs typically require each node to be a single, fixed-size vector. This necessitates "early summarization"—compressing a sentence into one vector via pooling or LSTMs before graph reasoning begins.

This compression creates an information bottleneck. Word-level nuances required for complex reasoning are lost, and the model becomes unable to perform sequence labeling tasks (e.g., predicting answer spans) directly from the graph-enhanced representations.

Methods: Reasoning Without Losing Detail

The Graph Sequential Network (GSN) addresses this bottleneck by treating each node as a sequence of feature vectors. Instead of static vector aggregation, GSN employs a novel message-passing algorithm:

  • Co-attention Aggregation: GSN uses a "Bidirectional Attention Flow" (BiDAF) style co-attention. When a node receives information from a neighbor, it compares its own sequence to the neighbor's sequence. This allows the model to dynamically highlight specific words in neighboring sentences that are relevant to the current context.
  • Sequential Output: Because message passing occurs at the sequence level, the output for each node remains a sequence, preserving fine-grained information throughout the reasoning process.
  • Flexible Information Fusion: The model supports multi-relational graphs and can use various pooling methods (e.g., max-pooling) to fuse information from multiple neighbors.
Comparison of traditional GNNs vs. GSN architecture.

Experimental Evaluation

The researchers evaluated GSN on two challenging benchmarks: HotpotQA (multi-hop QA) and FEVER (fact extraction and verification).

Key Results

GSN consistently outperformed standard GNN baselines. On the HotpotQA "Joint" metric, which requires correctly identifying both the answer and supporting facts, GSN achieved a score of 70.43 $F_1$, compared to the baseline's 69.64. The model showed a particularly strong improvement in identifying supporting sentences, with a +1.91 EM gain.

Main results on the HotpotQA dataset comparing GSN to the baseline.

On the FEVER dataset, GSN improved the official score to 70.51%, a significant increase over the 68.69% baseline. Ablation studies further revealed that max-pooling is generally more effective than mean-pooling for combining neighbor information in this sequential context.

Insights on Reasoning Depth

The authors found that reasoning depth is task-dependent. Token-level tasks like answer span prediction benefited most from a 1-layer GSN, while sentence-level reasoning (identifying supporting facts) was more effective with deeper networks (2-3 layers). Visualization of attention weights confirmed that the model successfully learns to attend to "bridging entities" that link disparate sentences.

Conclusion

The Graph Sequential Network provides a powerful framework for reasoning over sequences without the information loss inherent in early summarization. By maintaining sequence-level representations throughout the graph, GSN enables more accurate multi-hop reasoning and supports a wider range of fine-grained NLP tasks. Future work will focus on scaling the computational efficiency of co-attention for larger graphs and exploring automated graph construction methods.

Summary updated

Abstract

Recently Graph Neural Network (GNN) has been applied successfully to various NLP tasks that require reasoning, such as multi-hop machine reading comprehension. In this paper, we consider a novel case where reasoning is needed over graphs built from sequences, i.e. graph nodes with sequence data. Existing GNN models fulfill this goal by first summarizing the node sequences into fixed-dimensional vectors, then applying GNN on these vectors. To avoid information loss inherent in the early summarization and make sequential labeling tasks on GNN output feasible, we propose a new type of GNN called Graph Sequential Network (GSN), which features a new message passing algorithm based on co-attention between a node and each of its neighbors. We validate the proposed GSN on two NLP tasks: interpretable multi-hop reading comprehension on HotpotQA and graph based fact verification on FEVER. Both tasks require reasoning over multiple documents or sentences. Our experimental results show that the proposed GSN attains better performance than the standard GNN based methods.
BibTeX
@misc{tu2020graph,
  author = {Ming Tu and Jing Huang and Xiaodong He and Bowen Zhou},
  title = {{Graph Sequential Network for Reasoning over Sequences}},
  year = {2020},
  eprint = {2004.02001},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2004.02001},
}
Figure