Experiment with KG-based Recommendations

Scenario

Ash wants to go to the Pokémon Tower in Lavender Town in the Kanto region, but wants to research first what he might be facing in this tower to think about strategies:

• What of his Pokémon monster should he carry with himself?
• Are there any rare Pokémons to catch?
• Are there any moves that should be learned or improved by Pokémons?

After some minutes of searching, a personal knowledge graph was built from Ash`s search behaviour, and the following positive and negative samples were extracted.

Metrics

We define a knowledge graph as a directed, labelled graph: $$KG=(V,L,E) \text{, where}$$ $$\text{V … is the set of resource instances}$$ $$\text{L … is the set of contained literals}$$ $$\text{E … is the set of edges}$$

A sample S from a personal knowledge graph C is defined as:

$$S = \bigl\{(v, w_f(v)) | \forall v \in V(C), V(C) \sub V(KG)\bigr\}$$

$$ w_f: V(C) \longrightarrow [-1,1] $$

For the analysis of the complexity of the metrics, we want to define:

$$\text{n … |V(KG)|}$$ $$\text{k … |S|}$$

Simple Weighted Mean Distance (SMAD)

$$rec(n, S) = \argmin_{V' \sub V(KG), |V'| = n}{\sum_{u \in V'}\frac{\sum_{(v,w) \in S} w * dist(u, v)}{\sum_{(v,w) \in S} w}}$$

Runtime Complexity:

$$O(n*k) \text{ 😐 }$$

Storage Complexity:

$$\text{transE … }O(n) \text{ 🙂 }$$ $$\text{rdf2vec … }O(n) \text{ 🙂 }$$ $$\text{LDSD … }O(n^2) \text{ 😐 }$$

k-Neighbours of Centroid (kNC)

A weighted centroid is build from a given sample set S.

$$ \vec{c}(S) = \text{ tbd } $$

Then we are searching for the n number of neighbours.

$$rec(n, S) = \argmin_{V' \sub V(KG), |V'| = n}{\sum_{u \in V'}dist(\vec{u}, \vec{c}(S))}$$

Runtime Complexity:

$$O(k) \text{ 🙂 }$$

with appropriate vector storage solution

Storage Complexity:

$$\text{transE … }O(n) \text{ 🙂 }$$ $$\text{rdf2vec … }O(n) \text{ 🙂 }$$

Results

kNC and SMAD yield the same results.

TransE Cosine

SMAD	kNC
1. Haunter (Pokémon)	1. Haunter (Pokémon)
2. Dream Eater (Move)	2. Dream Eater (Move)
3. Gengar (Pokémon)	3. Gengar (Pokémon)
4. Night-Shade (Move)	4. Night-Shade (Move)
5. Shadow-Ball (Move)	5. Shadow-Ball (Move)
6. Power-Gem (Move)	6. Power-Gem (Move)
7. Polteageist (Pokémon)	7. Polteageist (Pokémon)
8. Destiny-Bond (Move)	8. Destiny-Bond (Move)
9. Phantom-Force (Move)	9. Phantom-Force (Move)
10. Lick (Move)	10. Lick (Move)