Use dependency paths to propose, not assert, entity relations

Last updated: 6 Oct 20265 min read

tutorial

A short syntactic path can focus relation extraction, but negation, quotation and cross-sentence references still require evidence review.

Generate bounded candidates

For two reviewed entity spans in a sentence, identify their syntactic heads and the path connecting them through the dependency tree. Path length and relation sequence can help a classifier decide which pairs deserve scoring. Limit by sentence, entity type and a measured path budget; aggressive pruning can lose long-distance dependencies. The parse must pass tree validation first, and the entity spans must still round-trip to source text.

Keep syntax as a feature

“Service K did not restart Queue M” contains a path between two entities, but the negator changes the assertion. “The note says Service K restarts Queue M” reports a claim rather than an observed event. Passive voice can reverse apparent word order. Store the source clause, negation cue and speaker or quotation status with each candidate. A dependency path is a candidate generator, not a proof of relation. Relation provenance remains the release boundary.

Audit pruning loss

Measure candidate-pair recall before classifying relation labels. Include long sentences, parenthetical clauses, code-switched verbs and cross-sentence pronouns. If a required relation is often cross-sentence, add a separate discourse route rather than silently widening every path window. Keep candidate IDs tied to parser version and source revision. A new parser may change path length without any change in the underlying fact.

Select the simplest useful feature

Compare an entity-type plus local-word baseline, a dependency-path model and a contextual model against one incident-level split. A syntactic feature earns its cost only if it recovers reviewed relations or cuts false positives. Report end-to-end edge precision and recall, not path-classifier accuracy on gold pairs alone. The incident project turns this comparison into a release decision.

Implementation

def ancestor_chain(token_index, heads):
    chain = []
    while token_index != -1:
        chain.append(token_index)
        token_index = heads[token_index]
    return chain

def dependency_distance(left_token, right_token, heads):
    left_chain = ancestor_chain(left_token, heads)
    right_chain = ancestor_chain(right_token, heads)
    right_positions = {token: offset for offset, token in enumerate(right_chain)}
    return min((left_offset + right_positions[token]
                for left_offset, token in enumerate(left_chain) if token in right_positions),
               default=None)

parse_heads = [1, -1, 1, 2]
assert dependency_distance(0, 3, parse_heads) == 3

Performance and operating cost

Walking both ancestor chains is O(h) time and O(h) space for tree height h; comparing every entity pair still costs O(e²·h) for e entities without candidate restrictions. Cache chains per sentence if throughput matters. The measured cost should include parsing and relation inference, not only this distance function. Pruning saves compute but can lower recall, so publish candidate recall alongside latency.

Common Mistakes

Publishing a relation because two entities have a short path.
Dropping the negator or quoted context from evidence.
Evaluating only candidates that survived pruning.
Reusing paths after a parser or tokenizer update.