Revisable Interlanguage Links: Online Matching with Recourse for Growing Low-Resource Wikipedias

Small Wikipedias, such as those in Tigrinya, Lao or Marathi, grow one article at a time. Each new article should be linked to its English counterpart, and that link is used immediately by readers, by knowledge-base builders, and by every downstream cross-lingual system that relies on Wikipedia's interlanguage links. Today such links are predicted one article at a time. A model scores English candidates for each article and takes the best one, and the decision is never revisited. That approach ignores a strong structural fact: the mapping is close to one-to-one. An English article has at most one Tigrinya counterpart. When two Tigrinya articles both point to the same English page, at least one link is wrong. The right repair may only become visible later, when the article that truly owns that English page finally appears.

We propose to treat this task as online bipartite matching with recourse. In online matching, items arrive one at a time and must be assigned on arrival. "Recourse" means the algorithm may also revise a small, bounded number of earlier assignments. The central claim is that a recourse budget of a few revisions per arrival, spent through freezing and short-repair rules from the online-algorithms literature, recovers most of the accuracy of a hindsight one-to-one assignment. It does so while emitting a link for every article at the moment it arrives. We further predict that the benefit of recourse is largest exactly where cross-lingual transfer is weakest: target languages whose best donor language is linguistically distant or written in a different script. In those cases the scores separating candidates are flat, so early mistakes are common.

Core Claim and What Is New

The scoring side of this problem is already well studied. Zero-Shot Neural Transfer for Cross-Lingual Entity Linking maps low-resource titles into a phonological representation and links them through a related high-resource "pivot" (donor) language. It reports a 17% average absolute accuracy gain over earlier zero-shot systems and a 36% absolute gain when source and pivot use different scripts. Design Challenges in Low-resource Cross-lingual Entity Linking shows that 80–90% of low-resource linking errors come from failing to generate the right candidate, and it names "global coherence and entity type constraints" as unfinished work. Both papers decide each item independently, with no constraint shared across items and no way to undo a past decision. Our proposal reuses their scorers unchanged as the cost function. What it adds is the decision layer on top of them.

The closest work in the file that combines streams with cross-lingual alignment is Fine-grained Coordinated Cross-lingual Text Stream Alignment for Endless Language Knowledge Acquisition. It aligns text streams with heuristics, without a matching constraint, a revision budget, or any guarantee. Static cross-lingual graph alignment, such as Cross-lingual Knowledge Graph Alignment via Graph Matching Neural Network, solves the matching offline over a fixed graph. As far as the file shows, no one has posed interlanguage linking as an online assignment where the size of the one-to-one gain is traded explicitly against how many published links get rewritten.

Research Program

The arrivals are low-resource Wikipedia titles, in their real creation order taken from page histories. The "servers" they are assigned to are English articles. Each arrival is linked on arrival, and each English article accepts at most one link. A dummy "no counterpart" server with a tuned fixed cost absorbs articles that have no English page.

The cost of a link is the angular distance between the arriving title and the English candidate in the pivot-based embedding space of Rijhwani et al. We choose angular distance on purpose because it is a true metric. That makes the general-metric result of PERMUTATION Strikes Back: The Power of Recourse in Online Metric Matching apply directly. That paper shows that re-solving dyadic time blocks optimally gives a $2\log k$-competitive assignment with $O(\log k)$ revisions per arrival, where $k$ is the number of servers. Without recourse, deterministic algorithms cannot beat $2k-1$.

We are candid about how far that guarantee reaches. It bounds total cost, not accuracy, and with $k$ in the millions it is loose. It is a safety floor, not the argument for the method.

The practical algorithm combines three mechanisms, each drawn from a cited result. First, it freezes links whose score margin over the runner-up is large. This follows the freezing scheme of Online Metric Matching on the Line with Recourse, which reaches an $O(1)$ competitive ratio with $O(\log n)$ amortized recourse on the line partly by locking cheap edges permanently. Second, when a new arrival competes for an English page that is already taken, it repairs the conflict only through short augmenting paths. An augmenting path is a chain of reassignments: the newcomer takes the page, the displaced article moves to its next-best page, and so on. This follows L-Greedy in Online maximum matching with recourse, whose short-path restriction beats long-path doubling strategies at small budgets: 1.5 versus more than 2.5 at $k=4$, where $k$ there denotes the per-edge recourse budget rather than the server count. Third, it applies a hard amortized budget $B$ of revisions per arrival, which we sweep from 0 to unbounded.

The linguistic-proximity part of the program is an analysis rather than a second method. For each target language we record the URIEL distance to its best pivot language, as used by Choosing Transfer Languages for Cross-Lingual Learning, and whether the scripts differ. We then test whether the accuracy gained per revision grows with that distance.

Baselines

The do-nothing reference is the Rijhwani et al. pivot-based linker taking its independent top-1 choice, with no one-to-one constraint and no revisions. This is the published system, re-run on our creation-ordered splits. For its accuracy, the file reports only relative gains (17% and 36% absolute improvements), not an absolute top-1 accuracy. No reported result was found on Lacuna for absolute Wikipedia title-linking accuracy of this system, so we re-measure it ourselves.

The second baseline is greedy capacitated linking with zero recourse. It enforces one-to-one but never revises. It isolates whether the constraint alone, applied irrevocably, helps or hurts. Under adversarial orders, theory predicts it can hurt.

The strongest practical competitor is periodic full re-solving. It runs the Hungarian algorithm, the standard exact method for one-to-one assignment, from scratch every $m$ arrivals. This yields near-hindsight accuracy at the price of unbounded rewriting. It receives the same costs, the same candidate lists, and the same compute. Its interval $m$ is tuned over the same grid as our budget $B$.

A lookahead baseline delays each decision by $d$ arrivals and then commits for good. It trades latency instead of recourse.

The hindsight Hungarian assignment over the whole stream is reported as an upper bound, not a competitor.

To beat the competitors, our method must lie strictly above the re-solve and delay baselines on the curve of time-averaged accuracy versus revisions per arrival, at budgets of $B \le 3$. It should also close at least half the gap between greedy and hindsight. Two ablations remove freezing and remove the short-path restriction, to show which mechanism carries the gain.

Why not just…?

Why not just wait and solve the one-to-one assignment offline? If a link can wait, the hindsight Hungarian solution is optimal and our method is pointless. The case for recourse rests on links being published and consumed on arrival. We test this directly with the lookahead baseline. If a delay of a few arrivals already matches our accuracy, then latency is the cheaper currency and we will say so.

Why not just re-run full matching periodically? This is the real threat. If downstream users tolerate heavy rewriting, it may simply win. Our answer is empirical: we report how many previously published links each re-solve changes, and compare full curves rather than single points. The bet, motivated by the short-path result of Angelopoulos et al., is that most of the hindsight gain comes from a few local repairs.

Why not just use a stronger scorer so that conflicts rarely happen? Better candidate generation, such as the query-log approach of Fu et al., could make independent top-1 choices nearly conflict-free. In that case one-to-one matching adds little. We measure the conflict rate (two arrivals sharing a top-1 English page) for both the Rijhwani scorer and a QuEL-style scorer. If conflicts vanish with the stronger scorer, the contribution shrinks to the distant-language regime. That is exactly what the proximity analysis tests.

Proposed Experiments

The data are the Wikipedia title-linking languages of Rijhwani et al. (nine low-resource targets, 54 candidate pivots), ordered by real article creation time. We also test random and adversarially perturbed orders, chosen to stress greedy linking. The metrics are final top-1 accuracy, time-averaged accuracy of the links as published, amortized and worst-case revisions per arrival, and empirical cost ratio against the hindsight assignment.

The first decisive check is a gate. Hindsight one-to-one matching must beat independent top-1 by a meaningful margin on real orders. If it does not, the hubness premise fails and the project stops.

The second check is that at $B \le 3$ our method dominates periodic re-solving on the accuracy-versus-revisions curve.

The third check asks whether per-language gains from recourse correlate positively with pivot distance and with script mismatch. A positive correlation would show that revisable decisions are most useful where cross-lingual transfer is weakest. A null result would show that recourse is a generic fix, unrelated to how close the donor language is.