🤖 AI

On the Theoretical Limitations of Embedding-based Link Prediction

Cet article démontre que les couches de sortie linéaires dans les modèles d'enchâssement de graphes de connaissances créent des goulots d'étranglement de rang qui limitent l'expressivité à mesure que la taille et la connectivité du graphe augmentent, et propose une couche de sortie non linéaire basée sur un mélange de paramètres, efficace, qui surmonte théoriquement et empiriquement ces limitations pour améliorer les performances sur des ensembles de données larges et denses.

Auteurs originaux : Samy Badreddine, Emile van Krieken, Luciano Serafini

Publié 2026-06-02

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Samy Badreddine, Emile van Krieken, Luciano Serafini

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

L'image globale : Le problème de la « table trop petite »

Imaginez que vous essayez d'organiser une immense bibliothèque de livres (le Graphe de Connaissances). Vous voulez qu'un ordinateur prédise quels livres vont ensemble. Pour ce faire, l'ordinateur donne à chaque livre et à chaque relation une « carte d'identité » (un embedding) qui est une courte liste de nombres.

Habituellement, ces cartes d'identité sont courtes et simples (faible dimension), comme un numéro de téléphone à 10 chiffres. Mais la bibliothèque contient des millions de livres (espace de sortie de haute dimension).

L'article soutient que la plupart des modèles informatiques actuels tentent de faire correspondre ces cartes d'identité courtes à la vaste bibliothèque en utilisant une couche de sortie linéaire. Voyez cette couche comme une petite table plate sur laquelle vous essayez d'étaler tous les livres.

Le Problème : Si vous avez un million de livres mais que votre table n'est assez grande que pour 100 articles, vous ne pouvez physiquement pas tous les disposer dans le bon ordre. Peu importe la qualité de vos cartes d'identité, la table est trop petite pour contenir toutes les dispositions possibles. L'article appelle cela un « goulot d'étranglement de rang » (Rank Bottleneck). C'est comme essayer de faire passer une sculpture en 3D sur une feuille de papier en 2D ; vous perdez de l'information et ne pouvez pas représenter la forme complète.

Les trois façons dont nous essayons de « lire » la bibliothèque

Les auteurs examinent trois façons différentes dont nous essayons d'utiliser ces modèles, et montrent que la « petite table » fait échouer chacune d'elles lorsque la bibliothèque devient grande :

Le Classement (Qui est le n°1 ?) : Nous voulons savoir quel est le meilleur livre correspondant.
- La Limite : Si la bibliothèque est immense, la petite table ne peut pas créer assez de « hauteurs » uniques pour classer correctement chaque livre. Certains livres seront toujours mal classés.
La Reconstruction de Signe (Oui ou Non ?) : Nous voulons savoir si un livre appartient à une catégorie (Vrai/Faux).
- La Limite : La petite table ne peut pas dessiner assez de zones distinctes « Oui » et « Non ». C'est comme essayer de dessiner une carte complexe avec seulement deux couleurs ; vous ne pouvez pas montrer les détails.
La Distribution (Quelle est la probabilité ?) : Nous voulons connaître la probabilité exacte d'une correspondance.
- La Limite : La petite table force les probabilités à suivre une ligne droite et rigide. La vie réelle est courbe et complexe. Le modèle ne peut pas courber les probabilités pour qu'elles correspondent à la réalité.

La Théorie : Les auteurs ont fait des calculs pour prouver que pour corriger cela avec l'ancienne méthode de la « petite table », il faudrait que les cartes d'identité soient aussi longues que le nombre de livres dans la bibliothèque. Pour une bibliothèque d'un million de livres, vos cartes d'identité devraient comporter un million de nombres. C'est impossible à entraîner et à utiliser en pratique.

La Solution : Le « Livre Pop-up » (KGE-MOS)

Puisque nous ne pouvons pas rendre les cartes d'identité énormes (c'est trop coûteux), les auteurs proposent une nouvelle façon d'utiliser la table. Ils introduisent KGE-MOS (Mixture of Softmaxes).

L'Analogie :
Au lieu d'une seule petite table plate, imaginez un Livre Pop-up.

L'Ancienne Méthode : Vous avez une seule page plate. Vous ne pouvez montrer qu'une seule disposition de livres.
La Nouvelle Méthode (KGE-MOS) : Vous avez un livre avec plusieurs couches (mélanges). Selon le livre que vous regardez, la page « surgit » (pop-up) pour prendre une forme 3D différente.

En mélangeant plusieurs vues différentes (softmaxes), le modèle peut créer une forme complexe et courbe qui s'adapte parfaitement aux données, même si les cartes d'identité sous-jacentes restent courtes.

Efficacité : C'est comme avoir un petit ensemble de briques Lego (les cartes d'identité) mais utiliser un manuel d'instructions ingénieux (le mélange) pour construire un immense château complexe. Vous n'avez pas besoin de plus de briques ; vous avez juste besoin d'une meilleure façon de les assembler.
Coût : Cette nouvelle méthode ajoute très peu de paramètres supplémentaires (coût de mémoire) par rapport au simple fait de rendre les cartes d'identité plus longues.

Ce que les expériences ont montré

Les auteurs ont testé cela sur plusieurs graphes de connaissances du monde réel (comme les réseaux de découverte de médicaments et les bases de données biologiques).

Petites Bibliothèques : Sur de petits ensembles de données (comme FB15k-237), la « petite table » fonctionnait bien. Le nouveau « Livre Pop-up » n'a pas beaucoup aidé et a parfois même confondu le modèle.
Grandes Bibliothèques Denses : Sur des ensembles de données plus grands et complexes (comme openbiolink ou ogbl-biokg), les anciens modèles ont eu du mal. Le « Livre Pop-up » (KGE-MOS) a considérablement amélioré la capacité à classer les éléments correctement et à prédire les probabilités.
Le Compromis : La nouvelle méthode est légèrement plus lente à entraîner (environ 2 fois plus lente), mais elle est beaucoup plus rapide que d'essayer de rendre les cartes d'identité énormes, ce qui nécessiterait une quantité massive de mémoire et échouerait souvent à s'adapter aux ordinateurs.

Résumé

Le Problème : Les modèles d'IA actuels pour lier les données utilisent un « goulot d'étranglement » qui limite la complexité de leurs prédictions. Ils essaient de faire entrer une énorme quantité d'informations dans un espace minuscule, perdant ainsi en précision.
La Preuve : L'article prouve mathématiquement que vous ne pouvez pas corriger cela en augmentant simplement légèrement la taille des données ; il vous faudrait des tailles de données impossibles.
La Solution : Ils ont construit une nouvelle couche de sortie (KGE-MOS) qui agit comme un livre pop-up à plusieurs couches. Cela permet au modèle de représenter des motifs complexes sans avoir besoin de quantités massives de mémoire.
Le Résultat : Pour les données réelles de grande ampleur, cette nouvelle méthode rend les prédictions plus précises et plus fiables, offrant un moyen pratique de passer à l'échelle l'IA pour les grands graphes de connaissances.

Résumé technique : Sur les limitations théoriques de la prédiction de liens basée sur l'enchâssement

1. Énoncé du problème

L'article traite d'une limitation fondamentale des modèles modernes d'enchâssement de graphes de connaissances (KGE - Knowledge Graph Embedding) : le goulot d'étranglement de rang introduit par les couches de sortie linéaires. Dans les architectures KGE standard, les entités et les relations sont projetées vers des plongements de faible dimension (typiquement $d \in [10^2, 10^4]$ ), qui sont ensuite projetés vers un espace de sortie de haute dimension composé d'entités (typiquement $|E| \in [10^5, 10^9]$ ) via une couche linéaire.

Les auteurs soutiennent que cette projection linéaire confine les scores de sortie du modèle à un sous-espace linéaire de dimension $d$ au sein de l'espace de dimension $|E|$ . Lorsque $d \ll |E|$ , cela crée un « goulot d'étranglement de rang » qui restreint sévèrement l'expressivité du modèle. Plus précisément, le modèle ne peut pas représenter des ordres de classement arbitraires, des motifs de signes (triplets positifs/négatifs) ou des distributions de probabilité requis pour des tâches de raisonnement complexes en aval (indépendamment de la puissance de l'encodeur neuronal en amont, tel que les réseaux de neurones sur graphes ou les Transformers).

2. Méthodologie

Analyse théorique

Les auteurs dérivent les bornes nécessaires pour la dimension d'enchâssement $d$ requise pour que les KGE à décodeur linéaire (LD-KGE) satisfont trois tâches de prédiction distinctes :

Reconstruction de classement (RR - Ranking Reconstruction) : Ordonner correctement les objets pour une requête.
Reconstruction de signe (SR - Sign Reconstruction) : Classer correctement les triplets comme vrais ou faux.
Reconstruction distributionnelle (DR - Distributional Reconstruction) : Assigner des probabilités calibrées aux triplets.

Ils analysent ces tâches sous deux conditions :

Universalité : La capacité de représenter tous les motifs possibles pour des graphes d'une taille donnée. L'article prouve que pour l'universalité, $d$ doit être au moins égal à $|E|-1$ (pour RR et DR) ou $|E|$ (pour SR). Ces bornes sont pratiquement impossibles à atteindre pour des graphes à grande échelle.
Réalisabilité : La capacité de représenter des motifs cohérents avec un graphe observé spécifique. Les auteurs montrent que la dimension nécessaire dépend du rang de signe de la matrice d'adjacence du graphe (ou de sa matrice de signe). Bien que le rang de signe soit généralement plus petit que le rang complet, il est NP-difficile à calculer.

Pour fournir une condition suffisante pratique, les auteurs relient le rang de signe à la connectivité du graphe. Ils démontrent que la dimension requise est bornée par le nombre maximal de changements de signe dans les lignes de la matrice d'adjacence. En utilisant une heuristique de type Reverse Cuthill-McKee (RCM) pour réordonner les entités, ils montrent que la dimension requise évolue avec la connectivité du graphe (spécifiquement, le nombre de blocs contigus d'entrées positives) plutôt qu'avec le nombre total d'entités. Cependant, même avec un ordonnancement optimal, les graphes denses nécessitent des dimensions dépassant de loin les pratiques standards.

Solution proposée : KGE-MOS

Pour briser ce goulot d'étranglement sans encourir le coût massif en paramètres lié à l'augmentation de $d$ , les auteurs proposent KGE-MOS (Knowledge Graph Embedding with Mixture of Softmaxes).

Architecture : Au lieu d'une seule couche linéaire suivie d'un softmax, KGE-MOS remplace la couche de sortie par un mélange de $K$ softmaxes.
Mécanisme : Pour une requête $(s, r)$ , le modèle calcule un mélange de $K$ distributions :
$P(O|s, r) = \sum_{k=1}^K \pi_k(h_{s,r}) \cdot \text{softmax}(f_k(h_{s,r})E^\top)$
où $h_{s,r}$ est l'état caché, $E$ est la matrice d'enchâssement partagée des entités, $f_k$ sont les projections non linéaires spécifiques aux composantes (MLP), et $\pi_k$ sont les poids du mélange.
Efficacité : Les enchâssements d'entités $E$ sont partagés entre toutes les composantes. Les paramètres supplémentaires sont limités aux poids de projection $f_k$ et aux poids du mélange $\pi_k$ , ce qui résulte en un coût de $O(Kd^2)$ , négligeable par rapport au coût de $O(d|E|)$ d'une augmentation de la dimension d'enchâssement $d$ .

3. Contributions clés

Bornes théoriques : L'article fournit les premières bornes nécessaires pour tous les LD-KGE (tant bilinéaires que neuronaux) concernant l'universalité et la réalisabilité. Il établit que les couches de sortie linéaires limitent fondamentalement l'expressivité dans les graphes larges et denses.
Analyse de la connectivité : Il dérive une dimension suffisante pour la réalisabilité basée sur la connectivité du graphe (changements de signe), montrant que les graphes denses sont théoriquement plus difficiles à ajuster que les graphes creux.
KGE-MOS : Il introduit une couche de sortie non linéaire "prête à l'emploi" qui brise efficacement le goulot d'étranglement de rang.
Validation empirique : Il démontre que KGE-MOS améliore à la fois la précision du classement (MRR) et l'ajustement probabiliste (NLL) sur des jeux de données larges et denses, tandis qu'une augmentation simple de la dimension d'enchâssement produit des rendements décroissants en raison de l'instabilité de l'entraînement (ex: contraintes de taille de lot).

4. Résultats expérimentaux

Les auteurs ont évalué KGE-MOS sur cinq jeux de données (FB15k-237, Hetionet, ogbl-biokg, openbiolink, WN18RR) en utilisant quatre modèles de référence (DISTMULT, COMPLEX, RESCAL, CONVE) et un encodeur neuronal (COMPGCN).

Performance sur les graphes larges/denses : Sur les trois jeux de données les plus grands et les plus densément connectés (Hetionet, ogbl-biokg, openbiolink), KGE-MOS a systématiquement surpassé les LD-KGE de référence en termes de MRR et de NLL. Les gains ont été plus prononcés dans le régime de haute connectivité, là où le goulot d'étranglement théorique est le plus sévère.
Performance sur les petits graphes : Sur le plus petit jeu de données FB15k-237, KGE-MOS n'a montré qu'une amélioration négligeable ou une légère dégradation, confirmant que le goulot d'étranglement est moins critique pour les graphes plus petits et moins denses.
Mise à l'échelle de la dimension : Augmenter la dimension d'enchâssement $d$ de 200 à 1000 a amélioré les performances des modèles de référence mais a nécessité de réduire la taille des lots (batch size) en raison des contraintes de mémoire GPU, ce qui a finalement nui aux performances. En revanche, KGE-MOS à $d=200$ a atteint des performances comparables aux modèles de référence à $d=1000$ avec nettement moins de paramètres.
Ablation : L'augmentation du nombre de composantes de softmax ( $K$ ) a systématiquement amélioré les performances. Les projections non linéaires $f_k$ ont également contribué aux gains, mais le mélange lui-même était le principal moteur de la rupture du goulot d'étranglement.
Rupture de rang : L'analyse empirique du rang de la matrice de log-probabilité a montré que, tandis que les modèles standards étaient limités à un rang de $d+1$ , KGE-MOS a atteint des rangs approchant la dimension complète de l'ensemble des entités, brisant ainsi efficacement le goulot d'étranglement.

5. Signification et affirmations

L'article affirme que le domaine de la prédiction de liens s'est concentré lourdement sur l'amélioration des encodeurs (en utilisant des GNN ou des Transformers) tout en négligeant les limitations de la couche de sortie. Les auteurs soutiennent que l'exploration de couches de sortie non linéaires plus expressives est une voie nécessaire et prometteuse pour mettre à l'échelle les KGE vers des graphes plus larges et plus denses.

Ils soulignent que KGE-MOS offre une solution "prête à l'emploi" qui améliore la performance et la fidélité probabiliste à un faible coût en paramètres, remettant en question l'hypothèse selon laquelle la simple augmentation des dimensions d'enchâssement est le seul moyen de gérer des graphes plus grands. Ce travail suggère que les recherches futures devraient dépasser les améliorations centrées sur l'encodeur pour s'attaquer aux limitations structurelles du processus de décodage dans les modèles basés sur l'enchâssement.