Orthogonal Path Scans for Entity Alignment When Names Fail

Knowledge graphs in different languages describe many of the same real-world things. Matching their entities, such as recognising that the Chinese node "苹果公司" and the English node "Apple Inc." refer to one company, is called cross-lingual entity alignment. The best current systems mostly win by comparing names. A multilingual sentence encoder, or a machine-translated name, does most of the work, and graph structure contributes a one-hop smoothing step. That works on the standard benchmarks. It breaks down where alignment is actually hard: transliterated or abbreviated names, entities absent from the encoder's vocabulary, and distant scripts. In those cases the evidence has to come from relational context several hops away, for example "the company whose founder was born in a city that hosts a university in Pennsylvania". Today that evidence is either ignored or summed so indiscriminately that it hurts.

This note proposes representing an entity by a set of individually kept relation paths. Each path moves a neighbour's features back to the starting entity through an ordered product of relation-specific reflections, which are rotations that preserve distances. A learned weight then decides which paths count. Because composing reflections is associative, the representations for every hop length along a sampled walk come out of a single parallel prefix computation. That computation is the scan machinery behind fast linear recurrent models. The claim to test is that per-path selection over distance-preserving transport lets multi-hop structure help alignment when names are unreliable. It should do so with few or no labelled seed pairs, where uniform multi-hop aggregation is known to degrade.

Core Claim

Three findings in the literature point to the same gap. SelfKG aligns graphs with zero seed pairs using frozen LaBSE name embeddings, a one-hop graph attention layer and contrast against negatives drawn from the same graph. Its authors report that going beyond one hop degraded accuracy. That result is the main constraint on this proposal: naive depth adds noise. RPR-RHGT shows the opposite side. It mines reliable two-hop paths near seed pairs and attends over them with a relation-aware graph transformer, gaining up to 8.62% Hits@1 on WK31-15K. Its path reliability score depends on labelled seeds, it is capped at two hops, and its quadratic attention makes training slow. This paper motivates the proposal: paths carry signal, provided someone chooses which paths. RREA supplies the geometry. It shows that unconstrained weight matrices in graph networks distort the cross-lingual embedding space. It replaces them with relation-specific Householder reflections $I - 2u_ru_r^\top$, which are orthogonal and so preserve distances, and it stays strong with 10% of seed pairs.

The proposal combines these. For an entity $e$ and a sampled walk $e = e_0 \xrightarrow{r_1} e_1 \cdots \xrightarrow{r_L} e_L$, define the transported feature at hop $t$ as

$$z_t = P_t\, x_{e_t}, \qquad P_t = Q_{r_1} Q_{r_2} \cdots Q_{r_t},$$

where $x_{e_t}$ is the frozen name embedding of the $t$-th entity on the walk and $Q_r$ is the orthogonal transform for relation $r$. The entity's signature is a selective pool over walks $w$ and hops $t$, $s(e) = \sum_{w,t} \alpha_{w,t}\, z^{(w)}_t$. Here $\alpha_{w,t}$ is a softmax weight computed from the path's relation sequence and $z_t$. It is the only non-linear component, and it never touches the transport itself.

Two design details matter. First, a single reflection is its own inverse, so it cannot tell a relation from its reverse. Each $Q_r$ is therefore a product of two reflections, $H_{u_r}H_{v_r}$, which makes it a rotation whose inverse $H_{v_r}H_{u_r}$ is different. Second, the prefix products $P_1,\dots,P_L$ are exactly what an associative scan computes, in $O(\log L)$ parallel steps instead of $L$ sequential ones. The compact WY form that DeltaNet uses to parallelise products of Householder reflections keeps each prefix at rank at most $2t$. The scan is therefore a computational tool here, not the scientific claim. Its role is to make many per-walk, per-hop signatures cheap enough to compute for every entity.

There is one fact any reviewer will notice, and the design is built around it. If $\alpha$ were uniform and every walk enumerated, $s(e)$ would collapse into linearised RREA-style propagation, $h^{(k)}_e = \sum_{(e,r,e')} Q_r h^{(k-1)}_{e'}$. That already sums ordered reflection products over all paths. What the proposal adds is therefore not order-aware composition on its own. It is selection over individual paths, which uniform summation destroys. That is the ingredient the experiments must isolate.

Research Program

The first component is the encoder described above. Each entity gets a fixed number of relation-typed random walks of length $L \le 16$, with edges traversed in both directions so that inverse relations receive the inverse rotation. Prefix transports are computed by an associative scan over the WY representation. The only learned parameters are the reflection vectors $u_r$ and $v_r$ and a small scoring network for $\alpha$. This keeps the parameter count close to the near-parameter-free regime in which SEU showed that alignment works best.

The second component is how the encoder learns with little or no labelling. In the label-free setting, initial anchors come from SEU-style Sinkhorn assignment over name features. SEU's own propagation is parameter-free graph convolution followed by global one-to-one assignment, which it solves as a linear assignment problem. Only mutual-best pairs are kept as pseudo-seeds. Training then combines two signals. One is a contrastive loss on pseudo-seeds. The other is SelfKG's same-graph negative sampling, which prevents a true cross-lingual match from being pushed away as a negative. Pseudo-seeds are re-assigned each round with global editing, as in BootEA, so that early mistakes can be withdrawn. This addresses the error drift that bootstrapping is known to suffer.

In the regime where names are masked there is nothing to bootstrap from. That regime uses 1%, 5% and 10% true seed pairs instead. We state plainly that fully label-free, structure-only alignment is not expected to work beyond whatever approximate graph isomorphism provides.

The third component is analysis. We log which paths receive high $\alpha$ and check whether they resemble the "reliable paths" that RPR-RHGT mines from seeds. A positive answer would mean selection is recovering seed-derived path reliability without seeds. We also measure how alignment accuracy changes with hop length $L$, separately for high-degree and low-degree entities. The prediction is that low-degree entities in the sparser graph benefit most, because their one-hop context is too thin to identify them.

Baselines

The naive reference point is name-only alignment. Frozen LaBSE embeddings of entity names are matched by Sinkhorn assignment, with no structure and no training. Every structural method must beat it, and in the masked-name regime it falls to chance by construction.

The strongest existing competitor is SEU. It reports Hits@1 of 0.900 on DBP15K ZH-EN in 16.2 seconds on a GPU SEU. It needs no labels and no training, which makes it the bar a learned model must justify itself against. It will be run with the same name features as our model, on the same splits, with its hop count tuned on the same validation pairs.

SelfKG is the strongest learned label-free competitor, with a reported macro Hits@1 of 84.0% on original DBP15K SelfKG. It will be rerun with the same frozen LaBSE features and an equal tuning budget. RREA is the strongest seeded structural model and is run at matched seed fractions. RPR-RHGT is the strongest path-based model. The file lists no code for it, so it will be reimplemented at two hops. If the reimplementation does not reproduce the paper's gains, that will be reported rather than hidden.

Three ablations isolate the key ingredient. Uniform $\alpha$ with exhaustive propagation reduces the model to linearised RREA and tests whether selection matters. A commutative variant replaces the product of rotations with a sum of relation vectors and tests whether order matters. A non-orthogonal variant uses general learned matrices and tests whether distance preservation matters.

"Beating" a baseline means a Hits@1 gain at least twice the standard deviation across five seeds, on the regimes where we predicted a win. Matching SEU in the full-name regime counts as acceptable, not as a success.

Why not just…?

Why not just run SEU with more hops of propagation? This is the most serious threat. Powers of the normalised adjacency matrix already reach multi-hop context at no training cost, and SEU's relational weighting already up-weights rare relations. Uniform propagation, though, averages every path, including the noisy ones SelfKG found harmful. SEU also assumes the two graphs are roughly isomorphic, which fails when one side is much sparser. The direct test is multi-hop SEU against our model on the masked-name and sparse splits. If multi-hop SEU matches us there, the selection hypothesis is wrong and we will report that.

Why not just stack RREA layers without non-linearities? As argued above, that is mathematically our model with uniform path weights. It is therefore the decisive ablation rather than a competitor to argue around. If uniform weighting performs as well as learned $\alpha$, the contribution reduces to a faster way of computing RREA. That would be a minor engineering result, not a modelling one.

Why not just extend RPR-RHGT to three or more hops? Its path mining needs seed pairs and its attention cost grows quadratically. Its own authors stopped at two hops, citing combinatorial explosion and slow training. Memory is the obvious obstacle at longer horizons, and Graph Mamba reports more than 11 GB for graph transformers against 3.85 GB for a linear-scan model on OGBN-Arxiv. We will measure memory and time directly on DWY100K rather than rely on that analogy.

Why not just use Graph Mamba or HeteGraph-Mamba? Both order nodes by degree or by predefined meta-paths before scanning. Equivalent entities in two languages often have very different degrees, and multilingual graphs have no shared meta-path schema. Those orderings would therefore feed matched entities different histories. HeteGraph-Mamba also scans node features with non-orthogonal state updates, which runs into RREA's distortion finding. A degree-ordered Mamba encoder trained with our objective will be included as an extra arm.

Proposed Experiments

The main benchmark is DBP15K (ZH-EN, JA-EN, FR-EN), run in three regimes. The first uses full names. The second corrupts names: a fraction of entities, from 20% to 80%, have their names replaced by uninformative identifiers in one graph only. The third masks all names. For the corrupted regime we found no reported result on Lacuna for any method. The closest reference point is JAPE, which reaches 41.18% Hits@1 on ZH-EN without translation using structure and attribute types JAPE. MGNI reports 70.7% Hits@1 on ZH-EN using name-derived features MGNI. For the fully masked, structure-only regime there is no reported result on Lacuna for any baseline, so every baseline will be rerun.

Sparsity is tested on WK31-15K and on the 15K cross-lingual OpenEA pairs (EN-FR, EN-DE). Scale and wall-clock cost are tested on DWY100K, where SelfKG reports 98.3% to 100% Hits@1 with zero labels. That number leaves no accuracy headroom, so DWY100K serves only for the efficiency comparison: scan against a sequential loop against two-hop attention. Metrics are Hits@1, Hits@10 and mean reciprocal rank, plus training time and peak GPU memory.

Three outcomes would decide the question. First, in the corrupted and masked regimes, learned per-path selection should beat both multi-hop SEU and uniform-weight propagation, with the gap widening as $L$ grows past two. The uniform-weight baselines, in contrast, should plateau or decline, reproducing SelfKG's one-hop finding. Second, the gain should concentrate on low-degree entities in the sparser graph. Third, the orthogonal model should beat the non-orthogonal variant at low seed fractions, extending RREA's 10%-seed robustness to longer paths. If none of these appear, multi-hop relational context does not help alignment beyond what uniform propagation already captures, and the honest conclusion is that SEU-style simplicity is sufficient.