Sintesi Tecnica: Sulle Limitazioni Teoriche della Predizione di Collegamenti basata su Embedding

1. Definizione del Problema

Il paper affronta una limitazione fondamentale nei modelli moderni di Knowledge Graph Embedding (KGE): il collo di bottiglia del rango (rank bottleneck) introdotto dagli strati di output lineari. Nelle architetture KGE standard, le entità e le relazioni vengono mappate in embedding a bassa dimensionalità (tipicamente $d \in [10^2, 10^4]$), che vengono poi proiettate in uno spazio di output ad alta dimensionalità di entità (tipicamente $|E| \in [10^5, 10^9]$) tramite un livello lineare.

Gli autori sostengono che questa proiezione lineare confina i punteggi di output del modello in un sottospazio lineare $d$-dimensionale all'interno dello spazio $|E$-dimensionale. Quando $d \ll |E|$, ciò crea un "collo di bottiglia del rango" che restringe severamente l'espressività del modello. Nello specifico, il modello non può rappresentare arbitri ordini di classificazione, pattern di segno (triple positive/negative) o distribuzioni di probabilità necessari per compiti di ragionamento complessi a valle, indipendentemente dalla potenza dell'encoder neurale a monte (ad esempio, Graph Neural Networks o Transformer).

2. Metodologia

Analisi Teorica

Gli autori derivano i limiti necessari per la dimensione dell'embedding $d$ richiesti affinché i Linear-Decoder KGEs (LD-KGEs) soddisfino tre distinti compiti di predizione:

1. Ricostruzione del Ranking (RR): Ordinare correttamente gli oggetti per una query.
2. Ricostruzione del Segno (SR): Classificare correttamente le triple come vere o false.
3. Ricostruzione Distribuionale (DR): Assegnare probabilità calibrate alle triple.

Analizzano questi compiti sotto due condizioni:

• Universalità: La capacità di rappresentare tutti i possibili pattern per grafi di una data dimensione. Il paper dimostra che per l'universalità, $d$ deve essere almeno $|E|-1$ (per RR e DR) o $|E|$ (per SR). Questi limiti sono praticamente impossibili per grafi su larga scala.
• Realisabilità: La capacità di rappresentare pattern coerenti con un specifico grafo osservato. Gli autori mostrano che la dimensione necessaria dipende dal sign rank (rango del segno) della matrice di adiacenza del grafo (o della sua matrice di segno). Sebbene il sign rank sia generalmente inferiore al rango completo, calcolarlo è NP-hard.

Per fornire una condizione sufficiente pratica, gli autori collegano il sign rank alla connettività del grafo. Dimostrano che la dimensione richiesta è limitata dal numero massimo di cambi di segno nelle righe della matrice di adiacenza. Utilizzando un'euristica Reverse Cuthill-McKee (RCM) per riordinare le entità, mostrano che la dimensione richiesta scala con la connettività del grafo (specificamente, il numero di blocchi contigui di voci positive) piuttosto che solo con il numero totale di entità. Tuttavia, anche con un ordinamento ottimale, i grafi densi richiedono dimensioni che superano di gran lunga le pratiche standard.

Soluzione Proposta: KGE-MOS

Per rompere questo collo di bottiglia senza incorrere nel costo massiccio di parametri derivante dall'aumento di $d$, gli autori propongono KGE-MOS (Knowledge Graph Embedding with Mixture of Softmaxes).

• Architettura: Invece di un singolo strato lineare seguito da un softmax, KGE-MOS sostituisce lo strato di output con una miscela di $K$ softmax.
• Meccanismo: Per una query $(s, r)$, il modello calcola una miscela di $K$ distribuzioni:
  $$P(O|s, r) = \sum_{k=1}^K \pi_k(h_{s,r}) \cdot \text{softmax}(f_k(h_{s,r})E^\top)$$
  dove $h_{s,r}$ è lo stato nascosto, $E$ è la matrice condivisa degli embedding delle entità, $f_k$ sono le proiezioni non lineari specifiche per componente (MLP) e $\pi_k$ sono i pesi della miscela.
• Efficienza: Gli embedding delle entità $E$ sono condivisi tra tutte le componenti. I parametri aggiuntivi sono limitati ai pesi di proiezione $f_k$ e ai pesi della miscela $\pi_k$, risultando in un costo di $O(Kd^2)$, che è trascurabile rispetto al costo di $O(d|E|)$ dell'aumento della dimensione dell'embedding $d$.

3. Contributi Chiave

1. Limiti Teorici: Il paper fornisce i primi limiti necessari per tutti i LD-KGE (sia bilineari che neurali) riguardo all'universalità e alla realisabilità. Stabilisce che gli strati di output lineari limitano fondamentalmente l'espressività in grafi grandi e densi.
2. Analisi della Connettività: Deriva una dimensione sufficiente per la realisabilità basata sulla connettività del grafo (cambi di segno), mostrando che i grafi densi sono teoricamente più difficili da adattare rispetto a quelli sparsi.
3. KGE-MOS: Introduce uno strato di output non lineare "drop-in" che rompe efficacementamente il collo di bottiglia del rango.
4. Validazione Empirica: Dimostra che KGE-MOS migliora sia l'accuratezza del ranking (MRR) che la fedeltà probabilistica (NLL) su dataset grandi e densi, mentre un semplice aumento della dimensione dell'embedding produce rendimenti decrescenti a causa dell'instabilità dell'addestramento (ad esempio, vincoli sulla dimensione del batch).

4. Risultati Sperimentali

Gli autori hanno valutato KGE-MOS su cinque dataset (FB15k-237, Hetionet, ogbl-biokg, openbiolink, WN18RR) utilizzando quattro modelli baseline (DISTMULT, COMPLEX, RESCAL, CONVE) e un encoder neurale (COMPGCN).

• Performance su Grafi Grandi/Densi: Sui tre dataset più grandi e densamente connessi (Hetionet, ogbl-biokg, openbiolink), KGE-MOS ha costantemente superato i baseline LD-KGE sia in MRR che in NLL. I guadagni sono stati più pronunciati nel regime di alta connettività, dove il collo di bottiglia teorico è più severo.
• Performance su Grafi Piccoli: Sul dataset più piccolo FB15k-237, KGE-MOS ha mostrato miglioramenti trascurabili o un leggero degrado, confermando che il collo di bottiglia è meno critico per grafi più piccoli e meno densi.
• Scalabilità della Dimensione: Aumentare la dimensione dell'embedding $d$ da 200 a 1000 ha migliorato le prestazioni per i baseline ma ha richiesto la riduzione della dimensione del batch a causa dei vincoli di memoria della GPU, il che ha ultimamente danneggiato le prestazioni. Al contrario, KGE-MOS a $d=200$ ha ottenuto prestazioni comparabili ai baseline a $d=1000$ con significativamente meno parametri.
• Ablazione: L'aumento del numero di componenti softmax ($K$) ha costantemente migliorato le prestazioni. Anche le proiezioni non lineari $f_k$ hanno contribuito ai guadagni, ma la miscela stessa è stata il driver principale per rompere il collo di bottiglia.
• Rottura del Rango: L'analisi empirica del rango della matrice di log-probabilità ha mostrato che, mentre i modelli standard erano limitati al rango $d+1$, KGE-MOS ha raggiunto ranghi che si avvicinano alla dimensione completa dell'insieme delle entità, rompendo effettivamente il collo di bottiglia.

5. Significato e Rivendicazioni

Il paper sostiene che il campo della predizione di collegamenti si è concentrato pesantemente sul miglioramento degli encoder (ad esempio, usando GNN o Transformer) trascurando le limitazioni dello strato di output. Gli autori sostengono che esplorare strati di output non lineari più espressivi è una via necessaria e promettente per scalare i KGE a grafi grandi e densi.

Evidenziano che KGE-MOS offre una soluzione "drop-in" che migliora le prestazioni e la fedeltà probabilistica a un basso costo di parametri, sfidando l'assunto che aumentare semplicemente le dimensioni dell'embedding sia l'unico modo per gestire grafi più grandi. Il lavoro suggerisce che la ricerca futura dovrebbe andare oltre i miglioramenti centrati sull'encoder per affrontare i limiti strutturali del processo di decodifica nei modelli basati su embedding.