ROPE : Reading Order Equivariant Positional Encoding for Graph-based Document Information Extraction (2021)

Abstract: Natural reading orders of words are crucial for information extraction from form-like documents. Despite recent advances in Graph Convolutional Networks (GCNs) on modeling spatial layout patterns of documents, they have limited ability to capture reading orders of given word-level node representations in a graph. We propose Reading Order Equivariant Positional Encoding (ROPE), a new positional encoding technique designed to apprehend the sequential presentation of words in documents. ROPE generates unique reading order codes for neighboring words relative to the target word given a word-level graph connectivity. We study two fundamental document entity extraction tasks including word labeling and word grouping on the public FUNSD dataset and a large-scale payment dataset. We show that ROPE consistently improves existing GCNs with a margin up to 8.4% F1-score.

## introduction key information extraction from form-like documents is one of the fundamental tasks of document understanding that has many real-world applications. however, the major challenge of solving the task lies in modeling various template layouts and formats of documents. for example, a single document may contain multiple columns, tables, and non-aligned blocks of texts (e.g. figure 1 ). the task has been studied from rule-based models @xcite to learning-based approaches @xcite . inspired by the success of sequence tagging in nlp @xcite @xcite , a natural extension is applying these methods on linearly serialized 2d documents @xcite . top: a portion of a form document with the original word reading order. bottom: given a graph connectivity, rope generates equivariant reading order codes with respect to the target word (in this case the date "3/18/97"). nevertheless, scattered columns, tables, and text blocks in documents make the serialization extremely difficult, largely limiting the performance of sequence models. @xcite ; @xcite explore to directly work on 2d document space using grid-like convolutional models to better preserve spatial context during learning, but the performance is restrictive to the resolution of the grids. recently, @xcite ; @xcite ; @xcite propose to represent documents using graphs, where nodes define word tokens and edges describe the spatial patterns of words. @xcite show state-of-the-art performance of graph convolutional networks (gcns) @xcite on document understanding. although gcns capture the relative spatial relationships between words through edges, the specific word ordering information is lost during the graph aggregation operation, in the similar way to the average pooling in convolutional neural networks (cnns). however, we believe reading orders are strong prior to comprehending languages. in this work, we propose a simple yet effective reading order equivariant positional encoding (rope) that embeds the relative reading order context into graphs, bridging the gap between sequence and graph models for robust document understanding. specifically, for every word in a constructed graph, rope generates unique reading order codes for its neighboring words based on the graph connectivity. the codes are then fed into gcns with self-attention aggregation functions for effective relative reading order encoding. we study two fundamental entity extraction tasks including word labeling and word grouping on the public funsd dataset and a large-scale payment dataset. we observe that by explicitly encoding relative reading orders, rope brings the same or higher performance improvement compared to spatial relationship features in existing gcns in parallel. ## other related work attention models show state-of-the-art results in graph learning @xcite and nlp benchmarks @xcite . as attention models with positional encodings are proven to be universal approximators of sequence-to-sequence functions @xcite , encoding positions or ordering is an important research topic. for sequence, learned positional embeddings @xcite @xcite , sinusoidal functions and its extensions @xcite have been studied. beyond that, positional encodings are explored in graphs @xcite , 2d images @xcite and 3d structures (fuchs et al., 2020). lastly, graph modeling is also applied to other document understanding tasks, including document classification @xcite and summerization @xcite . ## method we follow recent advances in using gcns for document information extraction that relax any serialization assumptions by sequence modeling. gcns take inputs (word tokens in this case) of arbitrary numbers, sizes, shapes and locations, and encode the underlying spatial layout patterns of documents through direct message passing and gradient updates between input embedding in the 2d space. node definition. given a document d with n tokens denoted by @xmath0, t 2 , ..t n }, we refer t i to the i-th token in a linearly serialized text sequence returned by the optical character recognition (ocr) engine. the ocr engine generates the bounding box sizes and locations for all tokens, as well as the text within each box. we define node input representation for all tokens t as vertices @xmath1, v 2 , ..v n }, where v i concatenates quantifiable attributes available for t i . in our design, we use two common input modalities: (a) word embeddings from an off-the-shelf pre-trained bert model @xcite , and (b) spatial embeddings from normalized bounding box heights, widths, and cartesian coordinate values of four corners. edge definition. while the vertices v represent tokens in a document, the edges characterize the relationship between the vertices. precisely, we define directional edges for a set of edges e, where each edge e ij connects two vertices v i and v j , concatenating quantifiable edge attributes. in our design, we use two input modalities given an edge e ij connecting two vertices: (a) spatial embeddings from horizontal and vertical normalized relative distances between centers, top left corners and bottom right corners of the bounding boxes. it also contains height and width aspect ratios of v i , v j , and relative height and width aspect ratios between v i and v j . (b) visual embeddings that utilizes im-agenet pre-trained mobilenetv3 @xcite to extract visual representations of union bounding boxes containing v i and v j . the visual embedding in edge formation picks up visual cues such as colors, fonts, separating symbols or lines between two token bounding boxes (through their union bounding box). we refer to the spatial embedding in (a) as the edge geometric (edgegeo) feature used in the experimental section. graph construction. our implementation is based on the β-skeleton graph (kirkpatrick and radke, 1985) with β = 1 for graph construction. by using the "ball-of-sight" strategy, β-skeleton graph offers high connectivity between word vertices for necessary message passing while being much sparser than fully-connected graphs for efficient forward and backward computations @xcite . a β-skeleton graph example can be found in figure 2 , and more can be found in figure 5 in the appendix. ## experiments we evaluate how reading order impacts overall performance of graph-based information extraction from form-like documents. we adopt two form understanding tasks as @xcite , including word labeling and word grouping. word labeling is the task of assigning each word a label from a set of predefined entity categories, realized by node classification. word grouping is the task of aggregating words that belong to the same entity, realized by edge classification. these two fundamental entity extraction tasks do not rely on perfect entity word groupings provided by the dataset and therefore help decouple the modeling capability provided by the proposed rope in practice. these two tasks also effectively demonstrate the quality of the node embedding and edge embedding of the proposed graph architecture and decouple any performance gain from sophisticated conditional random field (crf) decoders often used on top of the model. ## conclusion we present a simple and intuitive reading order encoding method rope that is equivariant to relative reading order shifting. it embeds the effective positional encoding from sequence models while leveraging the existing spatial layout modeling capability of graphs. we foresee the proposed rope can be immediately applicable to other document understanding tasks. figure 6: sample output of the word grouping task on funsd with a few failure cases.