When mapping data across different domains—whether aligning entities between knowledge graphs, matching words across languages, or registering points in 3D space—the default strategy is often local and greedy. We compute vector representations for our items, calculate pairwise similarities, and map each source item to its nearest neighbor in the target space.
While intuitive, this independent, local matching strategy suffers from a fundamental flaw: it ignores the global topology of the datasets. This article explores why local matching fails and how reframing alignment as a global assignment optimization problem guarantees structurally coherent, one-to-one mappings.
The Pitfall of Local Decisions: Many-to-One Collapse
The primary failure mode of independent nearest-neighbor search is the "hubness" problem, or many-to-one collapse. In high-dimensional embedding spaces, certain target vectors naturally become "hubs"—points that appear close to an disproportionately large number of queries.
When every source entity selects its closest target independently, multiple distinct source entities frequently collapse onto the same target hub. As noted by Jiaji Huang et al. in Improving Bilingual Lexicon Induction for Low Frequency Words, these hub vectors dominate local matches, causing rarer or lower-frequency items to be completely misaligned.
Similarly, Xin Mao et al. demonstrate in From Alignment to Assignment: Frustratingly Simple Unsupervised Entity Alignment that greedy local searches are highly prone to mapping errors because they lack a mechanism to resolve competition. If Entity $A$ and Entity $B$ both find Entity $C$ to be their best local match, a greedy system assigns both to $C$, violating the logical assumption that distinct real-world concepts should map to distinct counterparts.
Local Greedy Matching (Many-to-One Collapse):
Source A ───\
├───> Target C (Hub)
Source B ───/
Global Assignment Matching (Bijective Enforcement):
Source A ─────────> Target C
Source B ─────────> Target D (Socially optimal shift)
Shifting to Global Assignment
To eliminate many-to-one collapse, we must shift our perspective from an individualistic query to a socially optimal allocation. Instead of asking, "What is the closest target for this specific node?", we ask, "What is the most efficient permutation that maps the entire set of source nodes to the entire set of target nodes simultaneously?"
By treating alignment as a global linear assignment or bipartite matching problem, we introduce a strict one-to-one (bijective) constraint. As argued by Kun Xu et al. in Coordinated Reasoning for Cross-Lingual Knowledge Graph Alignment, enforcing global constraints shifts the alignment process from isolated local decisions to a coordinated optimization.
This global view allows the system to resolve local ambiguities. For instance, if a source record has a high similarity to a target hub but is also the only viable match for a different, rarer target, the global optimization will force the correct pairing. As shown by Farid Movahedi Naini et al. in Where You Are Is Who You Are: User Identification by Matching Statistics, matching an entire population simultaneously allows the system to find the most likely global permutation, achieving high accuracy even when individual feature descriptors are highly ambiguous or noisy.
The Mechanics: Optimal Transport and the Sinkhorn Operator
While combinatorial matching guarantees a one-to-one mapping, discrete optimization (like finding a strict permutation matrix) is fundamentally non-differentiable, making it difficult to integrate directly into modern deep learning pipelines. To bridge this gap, researchers rely on Optimal Transport (OT) and entropy regularization.
Instead of searching for a hard, discrete permutation matrix, the problem is relaxed into finding a continuous "transport plan"—a matrix that dictates how to distribute probability mass from the source distribution to the target distribution with minimal cost.
To enforce the one-to-one constraint within this continuous framework, the Sinkhorn algorithm is applied. As explained by Qijie Ding et al. in Combating confirmation bias: a unified pseudo-labeling framework for entity alignment, the Sinkhorn algorithm takes an arbitrary similarity matrix and iteratively normalizes its rows and columns. This mathematical operation forces the matrix to become doubly stochastic, meaning every row and every column sums to exactly 1.
$$\sum_{j} P_{ij} = 1 \quad \text{and} \quad \sum_{i} P_{ij} = 1$$
This normalization acts as a soft one-to-one constraint. Because the total matching mass allocated to any single target cannot exceed 1, no single hub can monopolize the matches.
Renbo Zhu et al. leverage this mechanism in Adaptive Graph Convolutional Network for Knowledge Graph Entity Alignment to filter out local similarity noise, ensuring each entity is paired with its globally optimal counterpart. Furthermore, Xiaoze Liu et al. demonstrate in Unsupervised Entity Alignment for Temporal Knowledge Graphs that optimizing this global transport plan inherently prevents multiple source entities from collapsing onto a single target, providing a robust foundation for fully unsupervised alignment.
Combinatorial Alternatives: Hungarian and Stable Marriage
When differentiability during training is not required—such as during final inference or discrete post-processing steps—exact combinatorial algorithms offer rigid, non-probabilistic guarantees.
The Hungarian and Munkres Algorithms
For linear assignment problems where we want to maximize the absolute sum of alignment scores across a graph, the Hungarian (or Munkres) algorithm computes the exact maximum-weight matching in a bipartite graph. Thiago R. dos Santos et al. demonstrate in Graphbasierte Registrierung von Tubulären Strukturen that treating correspondence searches as an exact global assignment problem prevents the alignment from becoming trapped in local optima, ensuring structural consistency across complex branching architectures.
Stable Matching (Gale-Shapley)
Another powerful formulation treats similarity scores as subjective "preferences" rather than absolute costs, solving the alignment via the Gale-Shapley stable marriage algorithm. This approach ensures that no two entities would both prefer to break their current assignments to match with each other.
Bryan Li et al. utilize this in Exploring Content Selection in Summarization of Novel Chapters to prevent redundant text assignments. For graph structures, Qing Wang shows in Contrastive learning for supervised graph matching that integrating stable matching directly into the framework provides explicit theoretical guarantees for unique node pairings—a feat that continuous optimization objectives inherently struggle to resolve on their own.