Pondération entre les représentations de communauté et de nœud : intégration de graphes par détection de communautés

L’embedding de graphes est devenu un composant essentiel de nombreux systèmes d’analyse et d’extraction de données. Les approches actuelles d’embedding de graphes échantillonnent généralement un grand nombre de paires de nœuds à partir d’un graphe afin d’apprendre des représentations vectorielles de nœuds par optimisation stochastique, ou factorisent une matrice de proximité ou d’adjacence de haut ordre à l’aide de techniques de factorisation matricielle coûteuses en ressources computationnelles. Ces méthodes nécessitent en général des ressources importantes pour l’apprentissage et dépendent de nombreux paramètres, ce qui limite leur utilisation pratique. En outre, la plupart des techniques existantes d’embedding de graphes fonctionnent efficacement uniquement dans un espace métrique spécifique (par exemple, celui produit par la similarité cosinus), ne préservent pas les caractéristiques structurelles d’ordre supérieur du graphe d’entrée, et ne peuvent pas déterminer automatiquement un nombre significatif de dimensions d’embedding. En général, les embeddings générés sont peu interprétables, ce qui complique les analyses ultérieures et restreint leur applicabilité. Pour remédier à ces limitations, nous proposons DAOR, une technique d’embedding de graphes hautement efficace et sans paramètre, capable de produire des représentations compactes, interprétables et robustes vis-à-vis de l’espace métrique, sans nécessiter d’ajustement manuel. Comparée à une douzaine d’algorithmes d’embedding de graphes de pointe, DAOR obtient des résultats compétitifs tant pour la classification de nœuds (qui bénéficie de la proximité d’ordre supérieur) que pour la prédiction de liens (qui repose principalement sur la proximité d’ordre inférieur). Contrairement aux méthodes existantes, DAOR ne requiert aucune calibration de paramètres et améliore la vitesse de génération des embeddings de plusieurs ordres de grandeur. Notre approche vise donc à simplifier considérablement et à accélérer fortement les tâches d’analyse de données impliquant l’apprentissage de représentations de graphes.