# GraphDoc: Graph-Based Document Structure Analysis with Relation Annotations > GraphDoc introduces a graph-based Document Structure Analysis (gDSA) task, an 80K-image dataset with 4.13M relation annotations covering reading order, hierarchy, and cross-element references, and a plug-and-play relation prediction head (DRGG) that achieves 57.6% mAPg@0.5 as a first baseline. - Authors: Hunter Heidenreich - Published: 2025-02-04 - Updated: 2026-04-02 - Paper: Preprint (arXiv) - Paper: Published (ICLR 2025) - Project: GraphDoc (Project Page) - Code: GraphDoc (GitHub) - Dataset: GraphDoc Dataset - Source: Bevaya Labs, --- ## TL;DR GraphDoc introduces the graph-based Document Structure Analysis (gDSA) task and provides a dataset of 80K document images with 4.13M relation annotations (spatial and logical) built on top of DocLayNet. The accompanying model, DRGG, is a plug-and-play relation prediction head that achieves 57.6% $mAP\_g@0.5$. Prior layout datasets provide bounding boxes but not the relational graph structure needed for reading order, hierarchy, and cross-element references. GraphDoc adds this layer. ## What kind of paper is this? **Dominant:** $\Psi\_{\text{Resource}}$: The headline contribution is the GraphDoc dataset: 80K images, 11 object categories, 8 relation types, and 4.13M annotated relation pairs. This is the first large-scale dataset to combine spatial and logical document relations in a unified graph structure at paragraph level, including non-textual elements. **Secondary:** $\Psi\_{\text{Method}}$: DRGG is a plug-and-play relation prediction head demonstrating how to tackle gDSA, positioned as a baseline rather than a headline contribution. $\Psi\_{\text{Evaluation}}$: The paper introduces two new metrics ($mR\_g$ and $mAP\_g$) tailored to the multi-relation, class-imbalanced structure of the gDSA task. ## What is the motivation? Traditional Document Layout Analysis (DLA) focuses on detecting and classifying bounding boxes (text, table, figure, etc.) but stops there. It does not capture the relations between elements: which paragraph follows which, what section a figure belongs to, or how elements are spatially arranged relative to each other. Existing relational datasets are limited in scope: - FUNSD / XFUND: form key-value pairs only, text-only elements - ReadingBank: reading order only, text-only - HRDoc / Comp-HRDoc: hierarchical structure with non-textual elements, but no spatial relations and no unified graph modality No prior dataset captures the full relational graph of a document page, including both textual and non-textual elements, with both spatial and logical edge types. GraphDoc fills this gap. ## What is the novelty? ### The gDSA Task Graph-based Document Structure Analysis requires a model to produce a directed graph $G = (V, E)$ where nodes $V$ correspond to detected layout elements and edges $E$ carry relation labels from one of 8 types. The combined training objective is: $$ L\_{\text{gDSA}} = \sum\_{(v\_i, v\_j) \in E} \left( L\_{\text{cls}}(v\_i, \hat{v}\_i) + L\_{\text{rel}}(r\_{ij}, \hat{r}\_{ij}) \right) $$ This subsumes Reading Order Prediction (Sequence edges) and Hierarchical Structure Analysis (Parent/Child edges). For reading order, the Sequence edge type makes explicit the directed "next element" relation between consecutive layout elements, including across multi-column regions and non-text elements -- a relation prior datasets left implicit or handled only through post-processing heuristics. ### The GraphDoc Dataset GraphDoc extends DocLayNet's 80K document images (see [DocLayNet notes](2022-08-doclaynet.md) for the full class-level mapping) with eight relation categories. The eight categories split into two groups: - **Spatial relations (64.1% of pairs):** *Up*, *Down*, *Left*, *Right* -- nearest-neighbor spatial adjacency in each cardinal direction. - **Logical relations (36.9% of pairs):** *Parent*, *Child*, *Sequence*, *Reference* -- Sequence captures reading order; Parent/Child captures hierarchy; Reference links text to tables or figures it cites. Annotations were produced via a rule-based pipeline: Tesseract OCR and pdfplumber extraction, Recursive X-Y Cut for basic reading order, heuristic hierarchical grouping, and reference matching via text marker scanning. Approximately 58.5% of pages received human verification and refinement, including 12,000 financial report pages and 6,469 patent pages. Refinement rates during human verification varied by domain: ~23% for Financial Reports, ~8% for Scientific Articles, ~26% for Government Tenders, ~17% for Patents. **11 Object Categories:** Caption, Footnote, Formula, List-item, Page-footer, Page-header, Picture, Section-header, Table, Text, Title (same as DocLayNet). **8 Relation Types:** | Type | Category | Description | | :--- | :--- | :--- | | Up | Spatial | Nearest element above | | Down | Spatial | Nearest element below | | Left | Spatial | Nearest element to the left | | Right | Spatial | Nearest element to the right | | Parent | Logical | Hierarchical parent (e.g., section header over body text) | | Child | Logical | Hierarchical child | | Sequence | Logical | Reading order successor | | Reference | Logical | Cross-reference (e.g., figure cited in text) | ### The DRGG Model The Document Relation Graph Generator is a plug-and-play module that attaches to any DETR-style detector. After the decoder produces object queries $X^0$ and per-layer representations $X^l$, DRGG applies two independent pooling-MLP branches: $$ D\_1^l = \text{MLP}\_p^1(P\_1(X^l)), \quad D\_2^l = \text{MLP}\_p^2(P\_2(X^l)) $$ These are up-sampled, residually merged with the object features, expanded along orthogonal axes, and concatenated to produce pairwise relational features $F^l \in \mathbb{R}^{N \times N \times 2d\_{\text{embed}}}$. Features from all $L$ decoder layers are combined with learnable weights: $$ G = \text{MLP}\_g\!\left(\sum\_{l=1}^{L} \alpha^{(l)} F^l\right) $$ where $G \in \mathbb{R}^{N \times N \times k}$ and $k = 8$ relation categories. An auxiliary binary relation head stabilizes training; at inference, final scores are the element-wise product of the main predictor and the expanded auxiliary output. The total loss is: $$ \mathcal{L}\_{\text{total}} = \mathcal{L}\_{\text{cls}} + \mathcal{L}\_{\text{bbox}} + \lambda \mathcal{L}\_{\text{rel}} + \sigma \mathcal{L}\_{\text{rel\_aux}} $$ where both relation losses are binary cross-entropy and $\lambda$, $\sigma$ are hyperparameters not specified in the main paper. ### New Evaluation Metrics Standard Scene Graph Generation metrics (Recall@k) are poorly suited to gDSA because document element counts vary and top-$k$ filtering discards rare but critical relations. The paper introduces threshold-based metrics that first perform IoU-based instance matching then evaluate all relation predictions above a confidence threshold $T\_R$: $$ mR\_g@T\_R = \frac{1}{R} \sum\_{r=1}^{R} \text{Recall}\_r, \quad mAP\_g@T\_R = \frac{1}{R} \sum\_{r=1}^{R} \text{AP}\_r $$ Results are reported at $T\_R \in \\{0.5, 0.75, 0.95\\}$. ## What experiments were performed? All experiments use MMDetection and are trained and evaluated on GraphDoc. The study varies two dimensions independently: backbone (InternImage, ResNet, ResNeXt, Swin) and detector head (DETR, Deformable DETR, DINO, RoDLA). DRGG is added as a relation head on top of each. DLA performance: COCO $mAP@[50:5:95]$. gDSA performance: $mR\_g@0.5$ and $mAP\_g$ at thresholds 0.5, 0.75, and 0.95. Additional analyses include per-category AP breakdowns, domain-specific evaluation across six document types, an ablation comparing spatial-only vs. spatial-plus-logical relations, and an ablation replacing the relation feature extractor with a single linear layer. ## What are the outcomes/conclusions? The best configuration (InternImage + RoDLA + DRGG) achieves: - **DLA:** 81.5% $mAP@50:5:95$, up from 80.5% without DRGG -- joint relation prediction provides a small but consistent benefit to detection. - **gDSA:** $mR\_g@0.5 = 30.7\%$, $mAP\_g@0.5 = 57.6\%$, $mAP\_g@0.75 = 56.3\%$, $mAP\_g@0.95 = 46.5\%$. **Per-category AP@0.5** reveals a wide performance spread: | Relation | AP\_g@0.5 | | :--- | :--- | | Left | 99.0 | | Right | 99.0 | | Up | 49.0 | | Down | 49.0 | | Parent | 45.5 | | Child | 45.5 | | Sequence | 56.4 | | Reference | 16.8 | Spatial left/right relations are nearly solved; they encode purely geometric proximity that can be read off bounding box coordinates. Sequence (reading order), by contrast, reaches only 56.4% AP because correct ordering across multi-column layouts, footnotes, captions, and mixed-content regions depends on layout conventions that vary by domain and cannot be inferred from geometry alone. The 56.4% figure should be read as a lower bound on the difficulty of reading order prediction for documents at this scale of layout diversity. Reference prediction at 16.8% likely requires textual understanding that the vision-only DRGG lacks. **Domain-specific results** (mAP\_g@0.5): Laws and Regulations (63.2) performs best; Patents (31.8) performs worst. Financial Reports show low $mR\_g$ despite moderate $mAP\_g$, suggesting recall is constrained by complex, irregular layouts. **Key ablation findings:** - Adding DRGG improves DLA mAP (80.5 to 81.5), suggesting relational reasoning provides a useful auxiliary learning signal. - The full Relation Feature Extractor outperforms a simple linear layer (57.6 vs. 52.9 $mAP\_g@0.5$). - Including logical relations alongside spatial ones improves overall $mAP\_g$ (57.5 vs. 49.5 spatial-only), though mean recall drops slightly (26.7 vs. 32.1). **Limitations acknowledged:** visual-only input (hurts Reference and complex logical relations), single-page scope (cross-page structure unaddressed), rule-based annotation with heuristics that may not generalize, DLA errors propagate to relation prediction. **Limitations not acknowledged:** ~41.5% of pages rely entirely on rule-based annotations without human review, which may introduce systematic errors in logical relations. The dataset license is undeclared (see Reproducibility). ## Mapping to Matter vs. Meaning Framework GraphDoc inherits DocLayNet's 11-class label set (see [DocLayNet notes](2022-08-doclaynet.md) for the full class-level mapping). The novel contribution is the 8 relation types, which map to the [Matter vs. Meaning framework](../matter-vs-meaning/) as follows: ### Relation Types | GraphDoc Relation | Category | M-vs-M Mapping | Notes | | :--- | :--- | :--- | :--- | | **Up** | Spatial | *(no direct equivalent)* | Nearest element above. Spatial adjacency, not a semantic relation. | | **Down** | Spatial | *(no direct equivalent)* | Nearest element below. | | **Left** | Spatial | *(no direct equivalent)* | Nearest element to the left. | | **Right** | Spatial | *(no direct equivalent)* | Nearest element to the right. | | **Parent** | Logical | `header_of` | Hierarchical parent (e.g., section header over text body). | | **Child** | Logical | Inverse of `header_of` | Hierarchical child. | | **Sequence** | Logical | Reading order | Reading order successor. | | **Reference** | Logical | `group_with` | Cross-reference (e.g., figure cited in text, caption linked to figure). The hardest relation at 16.8% AP. | **Coverage gaps:** The M-vs-M framework defines `label_for` and `value_of` (form-specific relations) which GraphDoc does not cover, since DocLayNet contains no form annotations. The spatial relations (Up/Down/Left/Right) have no direct M-vs-M equivalent; they encode physical adjacency rather than semantic structure. ## Reproducibility ### Models DRGG is a plug-and-play relation head compatible with DETR-family detectors. The best configuration uses InternImage-XL + RoDLA + DRGG. Architecture details are in the paper's appendices C and F. The project repository is at `github.com/yufanchen96/GraphDoc` under MIT license, but as of April 2026 it remains a placeholder -- dataset, model checkpoints, training code, and evaluation code are all listed as "coming soon." ### Algorithms - Framework: PyTorch v1.10, MMDetection. - Optimizer: AdamW; lr $1 \times 10^{-4}$; weight decay $5 \times 10^{-3}$; betas $(0.9, 0.999)$; epsilon $1 \times 10^{-8}$. - Batch size: 4. - Multi-scale training: shorter side randomly sampled from $\\{480, 512, 544, 576, 608, 640, 672, 704, 736, 768, 800\\}$; longer side capped at 1333 pixels. - Loss: $L\_{\text{total}} = L\_{\text{cls}} + L\_{\text{bbox}} + \lambda L\_{\text{rel}} + \sigma L\_{\text{rel\_aux}}$; exact $\lambda$ and $\sigma$ values are in Appendix F. - Epochs and LR schedule: not reported in the paper. ### Data GraphDoc extends DocLayNet's 80K images with 4.13M relation pairs across 8 categories. Spatial relations were generated fully automatically; logical relations were generated by the rule-based pipeline then manually verified for approximately 58.5% of pages. The repository LICENSE file covers only the code (MIT). The GraphDoc authors have not declared an explicit dataset license in the repository README, paper, or project page. CDLA-Permissive-1.0 inheritance from DocLayNet cannot be confirmed without an explicit statement; treat the dataset license as Unknown. ### Evaluation - DLA task: standard COCO $mAP@[50:5:95]$. - gDSA task: $mR\_g$ and $mAP\_g$ at confidence thresholds 0.5, 0.75, 0.95 with IoU threshold fixed at 0.5 for instance matching. Metric formulation in Section 3.3 and Appendix B. - No error bars, significance tests, or multi-seed ablations reported. ### Hardware - 4 $\times$ Nvidia A100 GPUs (40 GB each), 300 GB CPU memory. - Infrastructure: HoreKa supercomputer / HAICORE@KIT / bwForCluster Helix. - GPU-hours and inference latency not reported. ## BibTeX ```bibtex @inproceedings{chen2025graphdoc, title = {Graph-based Document Structure Analysis}, author = {Yufan Chen and Ruiping Liu and Junwei Zheng and Di Wen and Kunyu Peng and Jiaming Zhang and Rainer Stiefelhagen}, booktitle = {The Thirteenth International Conference on Learning Representations}, year = {2025}, url = {https://arxiv.org/abs/2502.02501} } ```