Some ideas from Maximilian.

Recap Pseudo Code

Look at the Pseudo code again:

Input: KG K:⟨E,R,F⟩\mathcal K:\langle\mathcal E,\mathcal R,\mathcal F\rangle, triple xhrt=(h,r,t)∈Fx_{hrt}=(h,r,t)\in\mathcal F, embedding score function s:E×R×E→Rs:\mathcal E\times\mathcal R\times\mathcal E\to\mathbb R, sample size k∈Nk\in\mathbb N

Output: ReliKLB(xhrt)ReliK_{LB}(x_{hrt}) or ReliKApx(xhrt)ReliK_{Apx}(x_{hrt})

  1. SH←S_H\gets sample kk triples from N−(h)\mathcal N^-(h); ST←S_T\gets sample kk triples from N−(t)N^-(t).

  2. rankH←1rank_H\gets1; rankT←1rank_T\gets1

  3. for xh′r′t′∈SH∪STx_{h'r't'}\in S_H\cup S_T do

    • If s(xhrt)≤s(xh′r′t′)s(x_{hrt})\le s(x_{h'r't'}) then

      • if h′=hh'=h then

        rankH←rankH+1rank_H\gets rank_H+1

      • if t′=tt'=t then

        rankT←rankT+1rank_T\gets rank_T+1

  4. return 12(1rankH+∣N−(h)∣−∣SH∣+1rankT+∣N−(t)∣−∣ST∣)\frac{1}{2}\left(\frac{1}{rank_H+|\mathcal N^-(h)|-|S_H|}+\frac{1}{rank_T+|\mathcal N^-(t)|-|S_T|}\right) for ReliKLBReliK_{LB}

    or 12(1rankHN−(h)∣SH∣+1rankTN−(t)∣ST∣)\frac{1}{2}\left(\frac{1}{rank_H\frac{\mathcal N^-(h)}{|S_H|}}+\frac{1}{rank_T\frac{\mathcal N^-(t)}{|S_T|}}\right) for ReliKApxReliK_{Apx}

Ideas for Parallelization

Idea 1 Parallel Sampling

Sampling the negative sets SHS_H and STS_T can be done in parallel for both head and tail entities. GPU-based libraries like PyTorch can handle large-scale sampling efficiently on GPUs.

I will think about it.

Idea 2 Rank Update

For each sampled triple xh′r′t′x_{h'r't'}, it can be parallelized across all samples in SH∪STS_H\cup S_T. For-parallel

GPUs are very efficient at handling this kind of parallel computation, especially with batched matrix operations.

✅I will be working on this.

Will there be some write-after-write or read-after-write issues? Should I add some write-lock?