Technische Samenvatting: Over de Theoretische Beperkingen van Embedding-gebaseerde Linkvoorspelling

1. Probleemstelling

Het artikel behandelt een fundamentele beperking in moderne Knowledge Graph Embedding (KGE) modellen: de rank-bottleneck die wordt geïntroduceerd door lineaire outputlagen. In standaard KGE-architecturen worden entiteiten en relaties gemapt naar laagdimensionale embeddings (typisch $d \in [10^2, 10^4]$), die vervolgens via een lineaire laag worden geprojecteerd naar een hoogdimensionale outputruimte van entiteiten (typisch $|E| \in [10^5, 10^9]$).

De auteurs stellen dat deze lineaire projectie de outputscores van het model beperkt tot een $d$-dimensionale lineaire subspace binnen de $|E|$-dimensionale ruimte. Wanneer $d \ll |E|$, creëert dit een "rank-bottleneck" die de expressiviteit van het model ernstig beperkt. Specifiek kan het model geen willekeurige rangordes, tekenpatronen (positieve/negabele triples) of waarschijnlijkheidsverdelingen representeren die vereist zijn voor complexe downstream reasoning-taken, ongeacht de kracht van de upstream neurale encoder (bijv. Graph Neural Networks of Transformers).

2. Methodologie

Theoretische Analyse

De auteurs leiden noodzakelijke grenzen af voor de embeddingdimensie $d$ die vereist is voor Linear-Decoder KGE's (LD-KGE's) om drie verschillende voorspellingstaken te vervullen:

1. Ranking Reconstruction (RR): Het correct ordenen van objecten voor een query.
2. Sign Reconstruction (SR): Het correct classificeren van triples als waar of onwaar.
3. Distributional Reconstruction (DR): Het toekennen van gekalibreerde waarschijnlijkheden aan triples.

Ze analyseren deze taken onder twee condities:

• Universality (Universaliteit): Het vermogen om alle mogelijke patronen voor grafen van een bepaalde grootte te representeren. Het artikel bewijst dat voor universaliteit $d$ ten minste $|E|-1$ moet zijn (voor RR en DR) of $|E|$ (voor SR). Deze grenzen zijn praktisch onmogelijk voor grootschalige grafen.
• Realisability (Realiseerbaarheid): Het vermogen om patronen te representeren die consistent zijn met een specifieke geobserveerde graaf. De auteurs tonen aan dat de noodzakelijke dimensie afhangt van de sign rank van de adjacency matrix (of de sign matrix) van de graaf. Hoewel sign rank over het algemeen kleiner is dan de volledige rank, is het berekenen ervan NP-hard.

Om een praktische voldoende voorwaarde te bieden, koppelen de auteurs sign rank aan graafconnectiviteit. Ze demonstreren dat de vereiste dimensie begrensd wordt door het maximaal aantal tekenveranderingen in de rijen van de adjacency matrix. Door gebruik te maken van een Reverse Cuthill-McKee (RCM) heuristiek om entiteiten te herordenen, laten ze zien dat de vereiste dimensie schaalt met de connectiviteit van de graaf (specifiek het aantal aaneengesloten blokken van positieve vermeldingen) in plaats van alleen het totale aantal entiteiten. Echter, zelfs met een optimale ordening vereisen dichte grafen dimensies die de standaardpraktijk ver overstijgen.

Voorgestelde Oplossing: KGE-MOS

Om deze bottleneck te doorbreken zonder de enorme parameterkosten van het verhogen van $d$ te dragen, stellen de auteurs KGE-MOS voor (Knowledge Graph Embedding met Mixture of Softmaxes).

• Architectuur: In plaats van een enkele lineaire laag gevolgd door een softmax, vervangt KGE-MOS de outputlaag door een mengeling van $K$ softmaxes.
• Mechanisme: Voor een query $(s, r)$ berekent het model een mengeling van $K$ verdelingen:
  $$P(O|s, r) = \sum_{k=1}^K \pi_k(h_{s,r}) \cdot \text{softmax}(f_k(h_{s,r})E^\top)$$
  waarbij $h_{s,r}$ de verborgen toestand is, $E$ de gedeelde entiteit-embedding matrix is, $f_k$ component-specifieke niet-lineaire projecties (MLP's) zijn, en $\pi_k$ de menggewichten zijn.
• Efficiëntie: De entiteit-embeddings $E$ worden gedeeld over alle componenten. De extra parameters zijn beperkt tot de projectiegewichten $f_k$ en de menggewichten $\pi_k$, wat resulteert in een kostenpost van $O(Kd^2)$, wat verwaarloosbaar is vergeleken met de $O(d|E|)$ kosten van het verhogen van de embeddingdimensie $d$.

3. Belangrijkste Bijdragen

1. Theoretische Grenzen: Het artikel biedt de eerste noodzakelijke grenzen voor alle LD-KGE's (zowel bilineair als neuraal) met betrekking tot universaliteit en realiseerbaarheid. Het stelt vast dat lineaire outputlagen de expressiviteit fundamenteel beperken in grote, dichte grafen.
2. Connectiviteitsanalyse: Het leidt een voldoende dimensie af voor realiseerbaarheid op basis van graafconnectiviteit (tekenveranderingen), waarbij wordt aangetoond dat dichte grafen theoretisch moeilijker te fitten zijn dan ijle (sparse) grafen.
3. KGE-MOS: Het introduceert een "drop-in" niet-lineaire outputlaag die de rank-bottleneck efficiënt doorbreekt.
4. Empirische Validatie: Het demonstreert dat KGE-MOS zowel de ranking nauwkeurigheid (MRR) als de probabilistische fit (NLL) verbetert op grote, dichte datasets, terwijl een eenvoudige verhoging van de embeddingdimensie $d$ verminderde meeropbrengsten oplevert door trainingsinstabiliteit (bijv. batch size beperkingen).

4. Experimentele Resultaten

De auteurs evalueerden KGE-MOS op vijf datasets (FB15k-237, Hetionet, ogbl-biokg, openbiolink, WN18RR) met behulp van vier baseline modellen (DISTMULT, COMPLEX, RESCAL, CONVE) en één neurale encoder (COMPGCN).

• Prestaties op Grote/Dichte Grafen: Op de drie grootste en meest dicht verbonden datasets (Hetionet, ogbl-biokg, openbiolink) presteerde KGE-MOS consequent beter dan de baseline LD-KGE's in zowel MRR als NLL. De winst was het meest uitgesproken in het regime van hoge connectiviteit waar de theoretische bottleneck het meest ernstig is.
• Prestaties op Kleine Grafen: Op de kleinere FB15k-237 dataset liet KGE-MOS verwaarloosbare verbetering of een lichte degradatie zien, wat bevestigt dat de bottleneck minder kritisch is voor kleinere, minder dichte grafen.
• Dimensie Schaling: Het verhogen van de embeddingdimensie $d$ van 200 naar 1000 verbeterde de prestaties voor baselines, maar vereiste het verlagen van de batch size vanwege GPU-geheugenbeperkingen, wat uiteindelijk de prestaties schaadde. In tegen tegenstelling hiertoe behaalde KGE-MOS bij $d=200$ prestaties die vergelijkbaar waren met baselines bij $d=1000$, met aanzienlijk minder parameters.
• Ablatie: Het verhogen van het aantal softmax-componenten ($K$) verbeterde consequent de prestaties. De niet-lineaire projecties $f_k$ droegen ook bij aan de winst, maar de mengeling zelf was de primaire drijfveer achter het doorbreken van de bottleneck.
• Rank Breaking: Empirische rank-analyse van de log-waarschijnlijkheidsmatrix toonde aan dat terwijl standaardmodellen beperkt waren tot rank $d+1$, KGE-MOS ranks bereikte die benaderen bij de volledige dimensie van de entiteitsset, waardoor de bottleneck effectief werd doorbroken.

5. Betekenis en Claims

Het artikel claimt dat het vakgebied van linkvoorspelling zich zwaar heeft gericht op het verbeteren van encoders (bijv. door gebruik te maken van GNN's of Transformers), terwijl de beperkingen van de outputlaag zijn verwaarloosd. De auteurs stellen dat het verkennen van meer expressieve niet-lineaire outputlagen een noodzakelijke en veelbelovende route is voor het opschalen van KGE's naar grote en dichte grafen.

Ze benadrukken dat KGE-MOS een "drop-in" oplossing biedt die de prestaties en probabilistische getrouwheid verbetert tegen lage parameterkosten, wat de aanname uitdaagt dat het simpelweg verhogen van de embeddingdimensies de enige manier is om grotere grafen aan te kunnen. Het werk suggereert dat toekomstig onderzoek verder moet gaan dan encoder-centrische verbeteringen om de structurele beperkingen van het decoderingsproces in embedding-gebaseerde modellen aan te pakken.