Neural Graph Matching for Modification Similarity Applied to Electronic Document Comparison

Document comparison[7, 8], also known as redlining or blacklining, is a process of cross checking new versions of a document against previous copies in order to identify changes.

The recent work by Manandhar et al. [5] is the first to leverage GNNs to learn structural similarity of 2D graphical layouts, focusing on UI layouts with rectangular boundaries. The work employed a GCN-CNN architecture on a graph of UI layout images, also under an IoU-trained triplet network [20]. In addition, [10] learns the graph embeddings in a dependent manner. Through cross-graph information exchange, the embeddings are learned in the context of the anchor-positive (respectively, the anchor-negative) pair.

Previous general approaches have need of the image examples for extracting and aligning the visual information. Indeed, image is a significant important feature in document representations. However, for the time being, it is a huge surge in document electronically, almost formats of electronic document render with the same encoding. As PDF, displaying the exact same content and layout no matter which operating system, device or software application it is viewed on. For PDF 1.4, the visual features are embedded as shown in Fig. 3; font style is shown in (Green), font size is shown in (Blue), color is shown in (Tan), position is shown in (Red) and text encode is shown in (Bold).

A variety of visual and content-based features can be incorporated as the initial node features, such as the text, font, size, and type of a layout element or the image features in a document page. For modified learning in decodable electronic document tasks such as ours, we can only focus on content-based features. However, our work is not similar to [9, 10], the initial node features only contain semantic and geometric information of the layout elements. Since text and related features need to be considered, we simply apply Sentence-BERT[11] here to embed all of the text in the element. As shown in Fig. 4(a), which describes a document layout with height $h$ and width $w$ as a spatial graph $G=(V,E)$ where $V=\{c_{1},\cdots,c_{i},\cdots,c_{k}\}$ is set of nodes representing its k components and $E=\{e_{1},\cdots,e_{i},\cdots,e_{k}\}$ is the set of edges that denotes a relationship between them. Each node carries three or four types of information:

• •

  (Optional) Semantic property $s_{i}$: A one-hot vector denoting the component class.

• •

  Text property $t_{i}$: All the embedded text inside the component.

• •

  Geometric property $g_{i}$: Captures the spatial location of the component in layout are encoded.

• •

  Visual property $v_{i}$: Extracts the visual features from PDF code.

Let $(x_{i},y_{i})$ and $(w_{i},h_{i})$ be the geometrical centroid, width and height of the component $c_{1}$, and $A_{i}=\sqrt{w_{i}h_{i}}$, then the geometric feature $g_{i}$ is $[\frac{x_{i}}{w},\frac{y_{i}}{h},\frac{w_{i}}{w},\frac{h_{i}}{h},\frac{A_{i}}{wh}]$.

Define the edges features $r_{ij}$ associated with edge $e_{ij}$ using the pairwise geometric features between components $c_{i}$ and $c_{j}$ given below.

Where $\Delta x=x_{j}+x_{i}$ and $\Delta y=y_{j}+y_{i}$ are the shifts between the components and constant $D=\sqrt{w^{2}+h^{2}}$ normalises against the diagonal. In addition, the feature $r_{ij}$ incorporates various geometric relations such as relative distance, aspect ratios and orientation $\theta=\arctan 2(\frac{\Delta y}{\Delta x})\in[-\pi,\pi]$. We explicitly include a containment feature $\psi_{ij}$ taking into account the Intersection over Union (IoU) between components capturing the nesting of the layout components:

The visual feature $v_{i}$ is a 3xN matrix of which N is the same as the length of the text of component, and the 3 types of features (Font-style, Size, and Color) are obtained from PDF code:

• •

  Font-style encodes typeface and font. For example, LiberationSans-Bold is encoded as below.

  LiberationSans	$\cdots\cdots$	Bold
  1	0	1

• •

  Size is the size of text.

• •

  Color is obtained by transforming color space to YCbCr with 4:2:0 chroma subsampling.

As show in Fig. 4(c), the node features $n_{i}$ in the graph hold both the semantic class label $s_{i}$ as well as the geometric property $g_{i}$, text property $v_{i}$ and visual presentation $v_{i}$ of the layout component $c_{i}$. $n_{0}={E_{n}([E_{c}(E_{s}(s_{0}),E_{t}(t_{0}),E_{v}(v_{0}))g_{0}])}$ where $E$ is the embedding layer that learns the several kinds of features and then projects the features into node feature $n_{i}$. Similarly, the edge features $r_{ij}$ are projected by $E_{r}(r_{ij})$. Next, the node features and the edge (relation) features are operated by graph convolutional networks $g_{n}(\cdot)$ and $g_{r}(\cdot)$. The node and relational feature outputs of the GCN network are computed by $x_{n_{i}}=g_{n}(n_{i})$ , $x_{r_{ij}}=g_{r}([n_{i}E_{r}(r_{ij})n_{j}])$. The relation graph network $g_{r}$ operates on tuples $\langle n_{i},E_{r}(r_{ij})$, $n_{j}\rangle$ passing the information through the graph to learn the overall layout. Then obtain two set of features $X_{n}=\{x_{n_{1}},x_{n_{2}},\cdots,x_{n_{n}}\},X_{r}=\{x_{r_{1}},x_{r_{2}},\cdots,x_{r_{n}}\}$. Where $k$ and $k^{{}^{\prime}}$ are the number of components (node features) and the total number of the relationship features which vary for different layout layouts. Next, the sets of features are passed through self-attention modules which learn to pool the node features and relational features given by

where, $a_{n_{i}}$ and $a_{r_{i}}$ are attention weights learned with $w_{n}^{\intercal}$ and $w_{r}^{\intercal}$ parameters.

Finally, obtain a d-dimensional latent embedding that encodes the layout:

We modify previous works [12, 13, 14] to implement our approach. The learning process of our matching neural network is shown in Alg. 1.