Pointing Back into the Graph: Output-Sensitive Document Relation Extraction

Most systems that pull entities and relations out of a document compare candidates in pairs. They enumerate every text span that might be an entity, or every pair of entities that might be related, and score each one. The number of candidates grows with the square of the document length, or of the entity count, even though almost all of them are wrong. We propose a decoder that builds the relation graph one action at a time. At each step it can do one of three things: generate a label from a fixed vocabulary, copy a new mention by pointing into the text, or point back to a node it has already created. The third option is the new piece. It lets the model link to or reuse an existing entity without ever forming the full set of entity pairs. The cost of decoding then scales with the size of the graph the model actually outputs, not with the number of possible pairs.

The motivation is that the two existing families each solve half the problem. Pointer-based parsers and generators avoid exhaustive enumeration, but they point only at words in the input, never at structure they have already built. Pairwise classifiers handle arbitrary relational graphs, but they pay quadratically for that generality. A decoder whose copy distribution covers both the source text and its own partial graph could keep the generality of the pairwise methods and the efficiency of the pointer methods. This note says how to build it and how to test whether the node pointer actually matters.

Core Claim

A pointer-generator is a decoder that, at each step, mixes a softmax over a fixed vocabulary with an attention distribution that copies source tokens. A scalar gate decides how much weight each part gets (Get To The Point: Summarization with Pointer-Generator Networks). We extend the copy side so that, at step $t$, the decoder state $s_t$ attends jointly over the $N$ document tokens and over the set $V_t$ of graph nodes created so far. Each node is represented by a vector that is updated whenever an edge attaches to it.

The output distribution has three parts:

$$P(a_t) = g^{gen}_t P_{vocab}(a_t) + g^{tok}_t P_{tok}(a_t) + g^{node}_t P_{node}(a_t).$$

Here the gates $g_t$ come from a three-way softmax over $s_t$. $P_{vocab}$ covers relation labels, entity types and the control actions "new entity", "add edge" and "stop". $P_{tok}$ points to the start and end tokens of a new mention. $P_{node}$ points to an existing node in $V_t$, either to add a coreferent mention to it or to make it an edge endpoint.

If the graph has $|V|$ nodes and $|R|$ edges, the number of actions $T$ grows like $|V|+|R|$. Each action costs one attention pass over $N+|V_t|$ items. Total scoring cost is therefore roughly $T(N+|V|)$, which is linear in $N$ for a fixed output graph. By contrast, scoring all $E(E-1)$ ordered pairs of $E$ entities costs $E^2$, regardless of how sparse the true graph is.

The claim we will test is narrower than "joint beats pipeline". It is this: on document-level extraction, pointing to existing nodes matches pairwise classifiers in F1 at a much lower cost, and it beats a linearized-text generator on entities that take part in many relations. A linearized generator has to re-spell an entity every time it appears in a relation, and it can spell it inconsistently.

How This Differs from the Closest Work

Four pieces of prior work supply the method.

Transition-based Semantic Dependency Parsing with Pointer Networks builds semantic graphs with two actions, Attach and Shift, driven by a pointer over words. It reaches 90.7 macro F1 on SemEval 2015 and runs almost linearly in practice. Its pointer, however, targets single sentence tokens, it never generates labels, and it needs post-hoc cycle checking. We keep its idea of an action loop driven by a pointer, but point at multi-token spans and at graph nodes, and add a generation branch.

A Double-Graph Based Framework for Frame Semantic Parsing grows a frame graph argument by argument, with a pointer marking span boundaries. It is confined to one sentence, and its static knowledge graph costs 18–27% of runtime. We need no external knowledge graph, and we work at document scale.

GRIT shows that pointing to entity boundaries with a shared encoder-decoder avoids span enumeration. It trains in under 40 minutes, against roughly 20 hours for DYGIE++. But it fills a single template in a fixed role order and emits no edges. Our node pointer is what lets one decoder produce an unknown number of interconnected entities.

Joint Extraction of Entities and Relations Based on a Novel Graph Scheme builds entity-relation graphs with Stack-LSTM transitions. Its recursive composition, which updates an entity's vector whenever a relation attaches to it, is the update rule we reuse for node vectors. Its action set is a small discrete classifier tested only on sentences, and its greedy decoding suffered from early errors that derail everything after them.

Pointer Graph Networks shows that learned pointers over a dynamic node set can track evolving structure. It works only on synthetic graphs with supervision from execution traces. We take the idea of pointers over latent nodes and supervise them with gold extraction graphs instead.

Two papers constrain the design. PURE found that sharing one representation between entity finding and relation classification hurts, and that separate encoders gain 1.7–2.8 relation F1. We take this seriously. The token pointer and the node pointer get separate query projections and separate upper encoder layers, and we ablate full sharing directly. ATLOP found that attention pooling over a plain transformer beats explicit graph networks on DocRED (63.4 against GAIN's 62.76 F1). That warns us that an explicit graph state may add nothing beyond cost. Our evaluation is built so that this outcome would be visible.

Research Program

The encoder is a pretrained transformer over the whole document. The decoder is a light autoregressive transformer whose memory concatenates token encodings with the current node vectors. Generation proceeds in a canonical order. Entities are introduced by first mention, left to right. Each entity's further mentions are attached through the node pointer, and each relation is emitted as "add edge", followed by a node-pointer choice of head, a node-pointer choice of tail, and a generated relation label.

Masks keep the output valid. They forbid duplicate edges, pointing to nodes that do not exist, and labels whose types violate the schema. This replaces the post-hoc repair that the semantic parsing work needed.

Since the decoder generates one action at a time, it is exposed to the same garden-path errors as the Stack-LSTM system. We will compare greedy decoding, small beams, and training with sampled prefixes. We will also measure sensitivity to the decoding order by training with randomly permuted edge orders.

The analysis has two parts. First, we measure wall-clock time and the number of scored candidates as functions of document length and entity count, and check them against the $T(N+|V|)$ prediction. Second, we break F1 down by entity degree, meaning how many relations an entity takes part in, and by whether the relation crosses sentences. This is where node pointing should matter most.

Baselines

The naive reference is a linearized-text generator. It uses the same encoder and decoder, keeps token copying and vocabulary generation, and drops node pointing. Each relation is written out as a head mention string, a label and a tail mention string, and string matching recovers the graph. This is also the key ablation, because it isolates the one new ingredient. It gets the same data, the same parameter count (within 1%) and the same hyperparameter search budget. We count our method as beating it only if it improves relation F1 on entities with degree three or more by a margin larger than three-seed variance, without losing overall F1.

The strongest pairwise competitor with gold entities is ATLOP, which reports 63.4 F1 on DocRED (ATLOP). We will run our model in a gold-entity mode in which entity nodes are pre-seeded and only edges are decoded. ATLOP will be re-run with the same encoder size and tuning budget. Here, beating it means matching its F1 within one point while scoring at least five times fewer candidates per document on the densest DocRED documents.

For end-to-end extraction from raw text, the strongest pipeline is PURE run at document level, with its batched marker approximation and its separate entity and relation encoders, tuned under the same budget. No reported result found on Lacuna for PURE or any end-to-end system on DocRED, and the file gives only PURE's relative gains on SciERC, not an absolute figure. So these numbers will be produced here.

On MUC-4, GRIT is the reference, at 54.50 micro F1 against 51.40 for DYGIE++ (GRIT). Beating GRIT there is not the goal. Our goal is to match it while removing the fixed-role-order assumption.

Why not just…?

Why not just linearize the graph and train a seq2seq generator with copying? This is the most serious threat. If mention strings are distinctive, string matching may recover entity identity well enough that a separate node pointer adds nothing. Nothing in the file tests this directly. The linearized ablation above settles it. If its degree-stratified F1 and its rate of inconsistent entity spellings match ours, then the claim that node pointing improves accuracy is false. What would remain is the efficiency claim, which we would then report on its own.

Why not just run a pipeline of separate entity and relation encoders, as PURE does? PURE's evidence against shared representations is real, which is why our two pointers have separate upper layers. But PURE still forms every candidate pair among the predicted entities, which is quadratic in entity count, and an entity missed in the first stage is lost for good. The candidate-count measurements and the cross-sentence recall breakdown will show whether those costs matter at DocRED scale.

Why not just prune pairs with a bi-encoder retriever and classify the survivors? Efficient Document-level Event Relation Extraction cuts inference time by about 70% this way and reports 90.8 F1 on ESC. However, pruning caps recall, and that paper had to add coreference chains by hand. We will report the retriever's recall ceiling on DocRED next to our recall. Our method is only interesting if it beats that ceiling at comparable cost.

Proposed Experiments

The main benchmark is DocRED, which has 5,053 human-annotated documents and 40.7% inter-sentence facts. We evaluate in both gold-entity and end-to-end modes, using relation F1, inference F1 restricted to facts that require reasoning across mentions, F1 stratified by entity degree, candidates scored per document, and wall-clock time. MUC-4 under CEAF-REE tests whether the same decoder subsumes template filling. SciERC tests short scientific documents, where pairwise methods should be at their strongest. There, the honest expectation is parity rather than a win.

The decisive check has two conditions. In gold-entity mode on DocRED, our F1 must stay within one point of ATLOP's 63.4 while candidate counts grow close to linearly in entity count. And our model must beat the linearized ablation on high-degree entities. If the first fails, the idea is not competitive. If only the second fails, then output-sensitive decoding is a useful speedup but not a modeling advance, and the paper should be written that way.