Skip to content
Retour aux résultats

Prédiction de liens — Inférence des arêtes manquantes et futures dans les réseaux

Année
2003
Type
Network inference task

Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais

Taille de police

À quoi sert-elle ?

La prédiction de liens est une tâche d'analyse de réseaux qui estime quelles arêtes sont manquantes dans un graphe observé ou quelles arêtes sont susceptibles de se former à l'avenir.

Formalisée par Liben-Nowell et Kleinberg (2003, 2007), elle couvre un éventail d'approches — des simples indices de similarité structurelle tels que les Voisins Communs, le coefficient de Jaccard et Adamic-Adar, à la factorisation matricielle et aux méthodes de réseaux neuronaux graphiques (GNN) — et est évaluée avec l'AUC et la Précision Moyenne pour tenir compte du ratio fortement déséquilibré d'arêtes réelles par rapport aux arêtes inexistantes.

L’intuition derrière la méthode

Dans tout réseau du monde réel, les arêtes enregistrées ne représentent qu'une fraction des connexions réelles : les plateformes d'amitié manquent de liens non divulgués, les bases de données de citations omettent des articles non indexés, et les essais d'interaction protéique laissent de nombreuses paires non testées. La prédiction de liens demande : étant donné les connexions que nous pouvons observer, quelles paires non observées sont les plus susceptibles d'être connectées ? L'intuition fondamentale est que deux nœuds partageant de nombreux voisins communs, ou se situant à proximité l'un de l'autre dans un espace d'intégration appris, sont plus susceptibles d'être liés que deux nœuds structurellement distants. Les indices basés sur la similarité rendent cela explicite avec une formule unique ; les approches basées sur les GNN apprennent quels motifs structurels prédisent le mieux la connectivité à partir d'exemples étiquetés.

Histoire

La tâche a été formellement définie par Liben-Nowell et Kleinberg dans un article de SODA en 2003 et sa version étendue dans JASIST en 2007, où ils ont comparé de simples indices de similarité structurelle sur des réseaux de co-auteurs et ont montré que la topologie seule porte un fort signal prédictif. Des travaux ultérieurs ont étendu la tâche aux modèles génératifs probabilistes et de factorisation matricielle. Le domaine a été considérablement avancé par Zhang et Chen (2018), qui ont proposé le cadre Seal — extraction de sous-graphes locaux englobants et leur classification avec un GNN — démontrant que les caractéristiques structurelles apprises surpassent systématiquement les indices de similarité artisanaux sur divers réseaux de référence.

Quand l’utiliser

La prédiction de liens convient à tout problème où le réseau est incomplet ou évolutif et où l'objectif est de récupérer ou d'anticiper des arêtes. Les scénarios appropriés incluent la recommandation de nouvelles connexions dans les réseaux sociaux, la prédiction de futures citations ou collaborations, l'inférence d'interactions protéine-protéine et la complétion de graphes de connaissances. La méthode nécessite au moins 50 nœuds et une densité suffisante d'arêtes observées pour que les motifs structurels soient apprenables. Lorsque moins de 20 nœuds sont disponibles, l'analyse de centralité est un choix plus sûr. La portion observée du graphe doit être représentative ; si le mécanisme d'échantillonnage est fortement biaisé, les arêtes inférées peuvent refléter des artefacts d'échantillonnage plutôt qu'une structure réelle.

Limites et points d’attention

  • Les performances dépendent de manière critique de la stratégie d'échantillonnage négatif ; différentes stratégies peuvent conduire à des conclusions différentes à partir du même modèle.
  • Les méthodes basées sur les GNN nécessitent un ensemble d'arêtes étiquetées suffisamment grand et des ressources de calcul importantes.
  • Les indices structurels supposent que la similarité dans la topologie observée implique une connectivité future, ce qui peut ne pas être vrai dans les réseaux avec une structure hétérophile.
  • La division temporelle entraînement-test est essentielle mais nécessite des horodatages fiables ; sans eux, la fuite d'informations gonfle les performances apparentes.

Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.

Points forts

  • Couvre une large gamme de complexité — les simples indices de Jaccard ou Adamic-Adar ne nécessitent aucun entraînement et fonctionnent directement sur la topologie du graphe, tandis que les méthodes basées sur les GNN apprennent des motifs structurels complexes.
  • Les indices de similarité sans modèle sont rapides, interprétables et robustes sur des graphes épars avec un signal d'entraînement limité.
  • Les approches GNN généralisent bien à travers les domaines (sociaux, biologiques, graphes de connaissances) et capturent la topologie d'ordre supérieur.
  • Le cadre d'évaluation AUC/AP est robuste au déséquilibre de classe sévère entre les arêtes réelles et inexistantes.

Applications

  • Recommandation d'amis ou de connexions dans les réseaux sociaux (Facebook People You May Know, LinkedIn).
  • Prédiction de futures collaborations de recherche ou de relations de citation dans les réseaux académiques.
  • Inférence d'interactions protéine-protéine manquantes dans les réseaux biologiques à partir de données expérimentales partielles.
  • Complétion de graphes de connaissances en prédisant les relations entre les entités.
  • Prédiction d'interactions médicament-cible dans les réseaux pharmacologiques.

Comment ça marche

Comment ça marche

1

Le réseau est assemblé à partir des arêtes observées et partitionné en ensembles d'entraînement et de test à l'aide d'une division temporelle ou aléatoire. La division temporelle est préférée chaque fois que des horodatages sont disponibles car elle empêche la fuite d'informations : les arêtes futures ne doivent pas informer le modèle sur les arêtes passées. Le graphe d'entraînement est le seul graphe que la méthode de notation peut observer.

2

Étant donné que la grande majorité des paires de nœuds ne sont pas connectées, l'évaluation de chaque paire absente est impraticable. Une stratégie d'échantillonnage négatif sélectionne un ensemble d'arêtes inexistantes pour servir d'exemples négatifs. La taille et la stratégie d'échantillonnage (aléatoire, négatif difficile, équilibré par degré) affectent considérablement les performances mesurées et doivent être rapportées avec les résultats.

3

Chaque paire candidate reçoit un score de probabilité. Les indices structurels calculent le score à partir de la topologie du graphe observé — Voisins Communs compte les voisins partagés, Jaccard normalise ce compte par l'union, et Adamic-Adar pondère les voisins partagés par l'inverse du logarithme de leur degré. Les méthodes de factorisation matricielle décomposent la matrice d'adjacence en facteurs latents dont le produit scalaire approxime la probabilité d'arête. Les méthodes basées sur les GNN, notamment le cadre Seal de Zhang et Chen (2018), extraient des sous-graphes locaux autour de chaque paire candidate et entraînent un classificateur de graphe pour distinguer les arêtes réelles des arêtes fallacieuses, capturant des motifs structurels d'ordre supérieur que les indices simples manquent.

4

Les prédictions sont classées par score et comparées aux arêtes positives et négatives mises de côté. L'AUC-ROC mesure la probabilité qu'une paire positive aléatoire soit classée avant une paire négative aléatoire. La Précision Moyenne (AP) résume la précision sur l'ensemble du classement et est plus informative lorsque les exemples positifs sont rares. Les deux métriques doivent être rapportées ; la précision seule est trompeuse en cas de déséquilibre de classe sévère.

Pièges courants

  • Fuir les arêtes futures dans le graphe d'entraînement — utilisez toujours des divisions temporelles ou strictement aléatoires et vérifiez qu'aucune arête de test n'apparaît dans la matrice d'adjacence d'entraînement.
  • Rapporter uniquement la précision ; comme les non-arêtes dépassent largement les arêtes réelles, la précision est presque dénuée de sens — rapportez toujours l'AUC et l'AP.
  • Ignorer la stratégie d'échantillonnage négatif lors de la comparaison des méthodes ; le changement d'échantillonnage peut inverser les classements entre les modèles.
  • Appliquer la prédiction de liens à des graphes avec moins de 20 nœuds — avec si peu de nœuds, les motifs structurels sont trop épars pour donner des prédictions fiables ; préférez l'analyse de centralité à la place.
  • Traiter un graphe observé biaisé comme un échantillon représentatif — si les arêtes observées manquent systématiquement de certains types de nœuds, les prédictions hériteront de ce biais.

Questions fréquentes

Quelle approche devrais-je choisir — un indice de similarité ou un GNN ?

Les indices de similarité (Voisins Communs, Jaccard, Adamic-Adar) sont un bon point de départ : ils ne nécessitent aucun entraînement, sont interprétables et fonctionnent étonnamment bien sur des graphes épars. Les méthodes basées sur les GNN comme Seal surpassent les indices sur les réseaux avec une structure d'ordre supérieur complexe, mais nécessitent un nombre suffisant d'arêtes étiquetées et plus de ressources de calcul. Lorsque les données sont limitées ou que l'interprétabilité est importante, commencez par les indices.

Comment diviser le graphe pour l'évaluation sans fuite d'informations ?

Si vos arêtes portent des horodatages, utilisez une division temporelle : entraînez-vous sur les arêtes observées avant une heure limite et testez sur les arêtes formées après. Sans horodatages, mettez de côté une fraction aléatoire d'arêtes comme positives et échantillonnez un nombre égal ou fixe de non-arêtes comme négatives, en vous assurant qu'aucune arête mise de côté n'apparaît dans la matrice d'adjacence d'entraînement.

Pourquoi l'AUC est-elle préférée à la précision ?

Dans tout réseau réel, le nombre d'arêtes absentes dépasse largement le nombre d'arêtes présentes — souvent de plusieurs ordres de grandeur. Un modèle trivial qui prédit 'pas d'arête' pour chaque paire obtient une précision quasi parfaite tout en ne prédisant rien d'utile. L'AUC-ROC et la Précision Moyenne sont des métriques basées sur le classement qui sont insensibles à ce déséquilibre et mesurent directement la qualité du classement.

La prédiction de liens peut-elle être appliquée aux graphes dirigés ou pondérés ?

Oui. Pour les graphes dirigés, les scores peuvent être calculés séparément dans chaque direction, et certains cadres GNN gèrent nativement l'adjacence dirigée. Pour les graphes pondérés, les indices de similarité peuvent incorporer les poids des arêtes dans le calcul du voisinage, et les méthodes GNN peuvent utiliser les caractéristiques des arêtes. Cependant, la plupart des études de référence portent sur des graphes non pondérés et non dirigés, donc une attention supplémentaire est nécessaire lors de l'adaptation des méthodes.

Méthodes associées

Sources

  1. Liben-Nowell, D. & Kleinberg, J. (2007). The Link-Prediction Problem for Social Networks. Journal of the American Society for Information Science and Technology, 58(7), 1019-1031.

    Ouvrir la référence DOI
    Copié.
  2. Zhang, M. & Chen, Y. (2018). Link Prediction Based on Graph Neural Networks. Advances in Neural Information Processing Systems (NeurIPS), 31.

    Ouvrir la référence de la publication
    Copié.