Enforcing Transitive Consistency in Pairwise Matching

69 concepts58 papers1 proposal

Many foundational tasks in machine learning require grouping items into equivalence classes based on identity or similarity. Examples span multiple domains: coreference resolution (grouping textual mentions of the same entity), face clustering (grouping images of the same person), and record linkage (deduplicating database entries across multiple sources).

A natural and highly scalable way to frame these problems is pairwise classification: training a binary classifier to predict whether any given pair of items $(A, B)$ matches. Early breakthroughs, such as the machine learning approach to coreference resolution by Soon et al. in Corpus-Based Learning for Noun Phrase Coreference Resolution, relied heavily on this localized pairwise paradigm.

However, treating global clustering as a collection of independent binary decisions introduces a fundamental flaw: transitivity violations. In an ideal equivalence relation, if item $A$ matches item $B$, and item $B$ matches item $C$, then item $A$ must match item $C$. Independent pairwise classifiers possess no inherent mechanism to respect this mathematical law, creating a severe local-global consistency gap.

Why Transitivity Breaks Down

When a model evaluates pairs in isolation, it relies entirely on local features. For instance, in coreference resolution, a model might look at the pair (A: "the president", B: "he") and find a strong match based on gender agreement and textual proximity. It might then look at (B: "he", C: "the company") in a different sentence and find a spurious local justification for a link. But when evaluating (A: "the president", C: "the company"), the semantic incompatibility is glaringly obvious.

As Cardie et al. observe in Noun Phrase Coreference as Clustering, pairwise models frequently struggle with transitivity, failing to recognize when local decisions form an impossible global structure. This results in what Qin et al. call "triangular contradictions" in Unsupervised Coreference Resolution with HyperGraph Partitioning, where mutually exclusive attributes are accidentally collapsed into a single entity cluster.

   [A: "the president"]  <-- (P=0.8) -->  [B: "he"]
            ^                                   |
            |                                   |
     (True P = 0.0)                      (P=0.7)
            |                                   |
            v                                   v
   [C: "the company"]   <-----------------------+

   (Result: A logically impossible triangular contradiction)

This problem is compounded by noisy data. In computer vision, as highlighted by Shi et al. in Face Clustering: Representation and Pairwise Constraints, unconstrained similarity scores routinely violate transitivity, leading to fragmented or highly inconsistent identity groups.

The Illusion of Success

Why did the field tolerate these violations for so long? Part of the reason lies in how these models were traditionally evaluated. In Multipartite Entity Resolution: Motivating a K-Tuple Perspective (Student Abstract), Aberbach et al. demonstrate that evaluating multi-source entity resolution using standard pairwise metrics creates a misleading "illusion of success."

Pairwise metrics grant partial credit for individual correct links even when the resulting cluster is logically contradictory and fails to form a coherent, fully connected group. This masks global consistency failures, making systems appear far more accurate than they are in practice.

Enforcing Transitivity via Global Constraints

To bridge the local-global gap, researchers first attempted to overlay logical and structural constraints on top of pairwise predictions, forcing the model's outputs to conform to transitive closure.

Logical and Optimization Constraints

One approach is to formulate the clustering problem as a global optimization task where transitivity rules are explicitly enforced during inference. For example, Jiang et al. in Joint Learning for Coreference Resolution with Markov Logic utilize Markov Logic Networks (MLNs) to jointly learn local pairwise features alongside global clustering constraints.

Similarly, Thi et al. in Adapting Coreference Resolution for Narrative Processing use Integer Linear Programming (ILP) to inject domain-specific linguistic rules as soft constraints, preventing the system from making independent decisions that violate document-level consistency.

Graph-Based Regularization

Another strategy integrates transitivity directly into the network's loss function or graph structure. In Face Clustering: Representation and Pairwise Constraints, Shi et al. enforce transitivity within a Conditional Random Field (CRF) framework using triplet constraints.

In the domain of deep graph networks, Kim et al. note in Edge-Labeling Graph Neural Network for Few-Shot Learning that edge-based relationship predictions inherently lack transitive consistency. To solve this, they suggest mechanisms like cycle losses to penalize the model during training if it predicts that $A$ is similar to $B$ and $B$ to $C$ while declaring $A$ and $C$ dissimilar.

Shifting to Entity-Centric and Higher-Order Modeling

While post-hoc constraints help patch pairwise models, a more robust solution is to abandon independent pair comparisons altogether in favor of architectures that evaluate entire clusters natively.

In a comprehensive retrospective, Ng tracks this paradigm shift in Machine Learning for Entity Coreference Resolution: A Retrospective Look at Two Decades of Research, detailing how the field moved from local mention-pair classifications to global entity-based models. By representing the properties of an entire cluster (such as its collective gender, number, or semantic type), models can immediately reject locally tempting but globally inconsistent links.

 Pairwise Paradigm (Prone to Violations)
 [Mention] <---> [Mention] <---> [Mention]

 Entity-Centric Paradigm (Globally Consistent)
 [Mention] ---> [ Existing Cluster Representation ]
                - Gender: Masculine
                - Type: Person
                - Mentions: {"the president", "he"}

For instance, Manning et al. demonstrate in Entity-Centric Coreference Resolution with Model Stacking that entity-centric architectures allow the system to use information about a whole group of mentions to resolve ambiguous individual links.

To scale this higher-order reasoning efficiently, Lee et al. in Higher-Order Coreference Resolution with Coarse-to-Fine Inference introduce an iterative attention mechanism. Instead of computing isolated pairwise scores, the model refines mention representations based on the clusters they belong to, achieving global consistency without a prohibitive computational explosion.

By moving from local, independent pairs to globally coordinated structures—whether through explicit logical constraints or higher-order architectures—modern systems ensure that the local relationships they discover add up to a coherent, logically sound whole.

Key Foundational Work

Noun Phrase Coreference as Clustering (1999) — contributed 1 concept elements to this direction.
Probabilistic Coreference in Information Extraction (1997) — contributed 1 concept elements to this direction.
Corpus-Based Learning for Noun Phrase Coreference Resolution (1999) — contributed 1 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 57 papers
  2. Version 1 · 2026-10-04 · 37 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_transitivity_violation_2fd2dd85,
  title = {transitivity violation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/transitivity-violation/rdr_2fd2dd858bad449c90e533be94fa704f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_transitivity_violation_2fd2dd85_v2,
  title = {transitivity violation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/transitivity-violation/rdr_2fd2dd858bad449c90e533be94fa704f/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake