Labeling Trick : Une Théorie de l'Utilisation des Réseaux Neuronaux Graphiques pour l'Apprentissage de la Représentation Multi-Nœuds

Dans cet article, nous présentons une théorie de l'utilisation des réseaux neuronaux sur graphes (GNN) pour l'apprentissage de représentations multi-nœuds (où l'on s'intéresse à apprendre une représentation pour un ensemble de plus d'un nœud, comme par exemple un lien). Nous savons que les GNN sont conçus pour apprendre des représentations mono-nœud. Lorsque nous souhaitons apprendre une représentation d'ensemble de nœuds impliquant plusieurs nœuds, une pratique courante dans les travaux antérieurs consiste à agréger directement les représentations mono-nœud obtenues par un GNN en une représentation conjointe d'ensemble de nœuds. Dans cet article, nous mettons en évidence une contrainte fondamentale de cette approche, à savoir l'impossibilité de capturer la dépendance entre les nœuds dans l'ensemble de nœuds, et nous soutenons que l'agrégation directe des représentations individuelles de nœuds ne conduit pas à une représentation conjointe efficace pour plusieurs nœuds.Ensuite, nous observons que quelques travaux réussis antérieurs sur l'apprentissage de représentations multi-nœuds, tels que SEAL, Distance Encoding et ID-GNN, ont tous utilisé le marquage des nœuds. Ces méthodes commencent par marquer les nœuds du graphe selon leurs relations avec l'ensemble cible de nœuds avant d'appliquer un GNN. Ensuite, les représentations de nœuds obtenues dans le graphe marqué sont agrégées en une représentation d'ensemble de nœuds. En examinant leurs mécanismes internes, nous unifions ces techniques de marquage des nœuds sous une forme unique et la plus générale possible -- la technique du "marquage astucieux" (labeling trick). Nous démontrons que grâce à la technique du "marquage astucieux", un GNN suffisamment expressif peut apprendre les représentations d'ensemble de nœuds les plus expressives, résolvant ainsi en principe toutes les tâches d'apprentissage conjoint sur les ensembles de nœuds. Des expériences menées sur une tâche importante d'apprentissage de représentations bi-nœuds, la prédiction de liens, ont validé notre théorie.Notre travail explique la performance supérieure des méthodes précédentes basées sur le marquage des nœuds et établit une base théorique solide pour l'utilisation des GNNs dans l'apprentissage de représentations multi-nœuds.