Stable Marriage Problem

The algorithm's core property ensures that no blocking pair exists in the final matching. A blocking pair consists of two unmatched entities that would both prefer each other over their current assigned partners. This prevents logical inconsistencies in merged ontologies where a concept from Ontology A would rather map to a different concept in Ontology B than its current alignment, eliminating semantic drift and ensuring the merged knowledge graph remains coherent under reasoning.

The Gale-Shapley algorithm operates through an iterative proposal and provisional acceptance cycle:

• Proposers (e.g., source ontology entities) propose to their highest-ranked candidate that hasn't rejected them yet
• Receivers (e.g., target ontology entities) provisionally accept the best proposal received so far, rejecting previous engagements if a better match arrives
• This deferred decision-making prevents premature commitment to suboptimal alignments and guarantees convergence in O(n²) time complexity

The algorithm is asymmetric: the set that initiates proposals always receives their optimal stable matching, while the receiving set gets their pessimal stable outcome. In ontology alignment, this means the choice of which ontology acts as the proposer significantly impacts the final mapping. Source ontologies should typically be the proposers to ensure their concepts find the best possible matches. This property requires careful design consideration when aligning peer ontologies where neither should be privileged.

Unlike unconstrained similarity scoring, stable marriage enforces one-to-one mapping by design. This is critical for ontology alignment scenarios requiring:

• Functional properties: Each source class maps to exactly one target class
• Inverse functional constraints: Each target class receives at most one source mapping
• Global consistency: Prevents multiple source concepts from collapsing into a single target, preserving the distinctness of ontological categories and avoiding unintended equivalence assertions

The algorithm requires a complete preference ordering for each entity, not just raw similarity scores. In ontology matching, these rankings are typically derived from:

• Lexical matchers: Edit distance, Jaccard coefficient on labels
• Structural similarity: Graph convolutional network embeddings comparing neighborhood topology
• Logical confidence: Weighted combinations of multiple matcher outputs
• The ranking transformation converts continuous similarity scores into strict ordinal preferences, which can amplify small differences into significant ordering changes

The classic Hospitals/Residents Problem variant extends stable marriage to handle many-to-one matchings where each target entity (hospital) can accept multiple source entities (residents) up to a defined capacity. This is directly applicable to ontology scenarios where a general concept subsumes multiple specific concepts, enabling controlled one-to-many cardinality while maintaining stability guarantees through capacity-constrained deferred acceptance.

The algorithm finds a stable matching between two equally sized sets of elements, each with a ranked preference list for the other set. In ontology alignment, these sets are the classes or properties of two ontologies, and preferences are derived from similarity scores generated by lexical, structural, or embedding-based matchers. A matching is stable if no unmatched pair would mutually prefer each other over their current assigned partners, preventing logical inconsistencies in the final alignment.

Many ontology matchers produce a dense matrix of weighted correspondences, often suggesting multiple mappings for a single entity. The Stable Marriage algorithm enforces a strict one-to-one alignment cardinality, which is a common requirement for tasks like instance matching (linking owl:sameAs individuals) or schema merging. It selects the best global assignment from the similarity matrix, optimizing for mutual agreement rather than just local maximum similarity scores.

The quality of the final alignment is directly dependent on the input preference lists. These are constructed by sorting candidate matches for each entity based on a confidence value from a base matcher. Techniques include:

• Lexical Filtering: Using edit distance or Jaccard index on labels.
• Structural Scoring: Using Graph Convolutional Network (GCN) embeddings to compare neighborhood similarity.
• Composite Confidence: A weighted aggregation of multiple string, structural, and semantic similarity metrics.

The classic Gale-Shapley algorithm guarantees a stable but not necessarily globally optimal matching. In ontology alignment, the goal is often to maximize the sum of global similarity scores. This transforms the problem into the Assignment Problem, solvable by the Hungarian algorithm. However, the Stable Marriage framework is preferred when the logical consistency of the alignment, defined by the absence of blocking pairs, is prioritized over pure aggregate similarity.

A primary use case is linking individuals across knowledge graphs. When matching entities in a source ABox to a target ABox, the algorithm ensures each real-world object is linked to at most one counterpart. This prevents the creation of logically inconsistent identity closures where an entity is transitively declared owl:sameAs two distinct entities in the target graph, which would violate the semantics of the equality property.

The output of a stable matching algorithm serves as a high-quality input for the alignment repair phase. By enforcing one-to-one mappings, it reduces the search space for logical reasoners like those used in LogMap. The reasoner then checks the proposed correspondences against the TBox axioms to detect and remove any mappings that cause unsatisfiable classes or violate the conservativity principle, ensuring the final alignment is both stable and logically coherent.