Lightweight Spatial Modeling for Combinatorial Information Extraction From Documents (2023)

Abstract: Documents that consist of diverse templates and exhibit complex spatial structures pose a challenge for document entity classification. We propose KNN-Former, which incorporates a new kind of spatial bias in attention calculation based on the K-nearest-neighbor (KNN) graph of document entities. We limit entities’ attention only to their local radius defined by the KNN graph. We also use combinatorial matching to address the one-to-one mapping property that exists in many documents, where one field has only one corresponding entity. Moreover, our method is highly parameter-efficient compared to existing approaches in terms of the number of trainable parameters. Despite this, experiments across various datasets show our method outperforms baselines in most entity types. Many real-world documents exhibit combinatorial properties which can be leveraged as inductive biases to improve extraction accuracy, but existing datasets do not cover these documents. To facilitate future research into these types of documents, we release a new ID document dataset that covers diverse templates and languages. We also release enhanced annotations for an existing dataset.

## introduction structured document information extraction (ie) attracts increasing research interest due to the surging demand for automatic document processing, with practical applications in receipt digitization, workflow automation, and identity verification etc. recent state-of-the-art methods for processing documents with complex layouts extensively exploit layout information, such as position, relative distance, and angle, with transformer-based models. spatial modelling is a key contributing factor to the success of these methods @xcite @xcite . however, absolute coordinates, pair-wise 1 https://github.com/miafei/knn-former relative euclidean distance, and angle are insufficient to capture the spatial relationship in complex layouts. two document entity pairs could carry different importance despite having the same position and distance, due to the presence or absence of other entities positioned between the pairs. we believe that spatial information can be better exploited for document entity classification. we propose knn-former, a parameter-efficient transformer-based model that extracts information from structured documents with combinatorial properties. in addition to relative euclidean distance and angle embeddings as inductive biases @xcite , we introduce a new form of spatial inductive bias based on the k-nearest neighbour (knn) graph which is constructed from the document entities and integrate it directly into the attention mechanism. specifically, we first construct a knn graph based on the relative euclidean distance of document entities. then we incorporate hop distance between entities, which is defined as the shortest path between two entities on the knn graph, in training their pair-wise attention weight. for entity pairs with the same euclidean distance but different hop distance, the difference in hop distance would still contribute to different attention weights. we limit an entity's attention calculation only to its local radius of neighborhood defined by the knn graph. this also strengthens the inductive bias as reflected by our experiment results. furthermore, many real-world document information extraction tasks come with combinatorial properties, such as one-to-one mapping between field categories and values. such combinatorial properties can be leveraged as inductive biases to improve the extraction accuracy, but are underexplored because existing datasets do not cover such documents. current methods that do not address the combinatorial constraints suffer suboptimal performance on these types of documents. we further leverage this inductive bias by treating the entity classification task as a set prediction problem and using combinatorial matching to post-process model predictions @xcite @xcite . in addition, knn-former is parameter-efficient. recent baseline models are initialized with parameters of pre-trained language models @xcite @xcite , making their model size larger or at least comparable to the language models. knn-former does not utilize initialized parameters of existing language models, therefore free from the parameter size floor restriction. it is designed to be 100x smaller in trainable parameters compared to prevailing baselines. knn-former's parameter efficiency makes it energy-efficient, contributes to faster training, fine-tuning and inference speed and makes mobile deployment feasible. to encourage the progress of ie research in complex structured documents with combinatorial mapping properties, we release an id document dataset (named poi). while the existing id document dataset has only 10 templates @xcite , poi exhibits better template and lingual diversity. it also has a special mapping constraint where one field category has only one corresponding entity. in compliance with privacy regulations, the documents in the poi dataset are specimens and do not contain information about real persons. we conduct extensive experiments to evaluate the effectiveness of our proposed method. knn-former outperforms baselines on most field categories across various datasets, despite having a significantly smaller model size. extensive ablation studies show the importance of the knn-based inductive bias and combinatorial matching. to summarize, our contributions include (1) a highly parameter-efficient transformer-based model that (2) incorporates knn-based graph information in sparsified local attention; (3) combinatorial matching to address the one-to-one mapping constraint; (4) a new id document dataset with good template diversity, complex layout, and a combinatorial mapping constraint. ## related work researchers have tried multiple approaches for document information extraction @xcite @xcite . however, these works do not have spatial cues, such as the position of the information in the origi-nal document. to address this shortcoming, a number of works introduce the modality of layout information as additional input features. majumder et al. (2020) adopts positional information as inputs to their method to extract information from receipt documents. layoutlm @xcite ) adds 1-d and 2-d absolute position encodings to text embeddings before passing them to the transformer. @xcite proposes to train a language model from unlabeled documents with area masking, encoding relative positions of texts. structurallm @xcite assigns the bounding box cell position as the position coordinates for each word contained in it. docformer @xcite encodes 2d spatial coordinates of bounding boxes for visual and language features. layoutlmv2 @xcite uses learnable pair-wise relative positional embeddings as attention bias. a few works propose to use graphs to represent spatial entity relationships in documents. spade @xcite uses a three steps graph decoder and formulates the information extraction task as a dependency parsing problem. formnet @xcite constructs a k-nearest neighbor graph and applies a 12-layer graph convolutional network (gcn) to get the entity embeddings before feeding them into a transformer network. however, there are some limitations in using gcn to obtain embeddings. it is well established that the message passing-based gcn are limited in their expressive power @xcite @xcite @xcite . in addition, formnet does not use the hop distance between nodes, which could serve as a strong inductive bias to capture the spatial relationships between document entities. datasets with positional information such as funsd @xcite , cord @xcite , sroie @xcite are released to facilitate research in document understanding. however, they do not contain documents with combinatorial properties which are common in real-world applications.midv500 @xcite and midv2020 @xcite are two synthetic id datasets with combinatorial properties, but are unsuitable for document information extraction tasks due to incomplete annotations. they also lack template diversity. ## methodology in this section, we discuss the methodology for our model. we formulate the problem in sec.3.1 and explain our overall model architecture and the details of each component in sec.3.2. ## datasets many real-world documents exhibit combinatorial properties, such as a one-to-one mapping between between its fields and entities. however, existing public datasets do not cover documents with such properties @xcite @xcite . to fill the gap, we release a new id document dataset poi, and enhanced annotations of midv2020. we also verify our method on a private dataset prv. all 3 datasets exhibit combinatorial properties. in addition, we design the poi dataset to be template-rich with diverse languages. we also design the enhanced midv2020 with a difficult split such that templates in testing are unseen during training. bert alone without spatial information can achieve above 90% f1 on some existing datasets @xcite @xcite , indicating relative sufficiency of leveraging text information alone. yet in many real-world use cases, using text alone is insufficient. this motivates us to work on more challenging datasets where the exploitation of spatial information is important. dataset statistics are summarized in 1 and tab. 2. more details are as follows. poi we collect and annotate 530 proof-of-identity documents from online sources. we will release this poi dataset which consists of 10 document types, 265 distinct templates, and 131 countries of origin. the template and language diversity of poi create a challenging task for document understanding. all images are specimens with dummy values. the document type distribution is shown in tab. 3 . there are 8 field categories in total: last name, first name, date of birth, date of issue, date of expiry, id number, key, and others. key represents entities that indicate the field names for the important entities (e.g. last name) that we are interested to extract. the first 6 field categories appear in each document image once and only once, creating a special mapping constraint unseen in other datasets. the last 2 field categories (key and others) are not subject to the constraint. in real-world applications, it is common to extract a set of entities from documents that have combinatorial properties between its field and entities. id document information extraction is one such use case, where we only expect to extract one entity for each field category of interest. this one-to-one correspondence can be leveraged to improve classification performance. despite being a common task setting, we notice the lack of method exploration and innovation in this direction, due to the unavailability of such property among existing popular document datasets. more details about the dataset can be found in the appendix. ## experiments in this section, we conduct extensive experiments to evaluate our proposed knn-former on aforementioned datasets. we first compare our results with several baselines in sec. 5.1. then in sec. 5.2, we evaluate the generalization ability of our method on unseen templates. we then conduct ablation studies in sec.5.3 and sec.5.4 to assess the effects of each component in knn-former and the impact of different k in the knn graph. ## conclusion we propose knn-former, a parameter-efficient transformer-based model for document entity classification. knn-former uses knn hop attention, a new attention mechanism that leverages knn graph-based inductive bias to capture structural information between document entities. knn-former utilizes combinatorial matching to perform set prediction. we also release poi, a templaterich id document dataset subject to combinatorial constraints. experiments show that knn-former outperforms baselines in entity classification across various datasets.