Que sont lintégration de graphiques?

Lincorporation de graphes apprend un mappage dun réseau vers un espace vectoriel, tout en préservant les propriétés de réseau pertinentes.

Les espaces vectoriels se prêtent mieux à la science des données que les graphiques. Les graphiques contiennent des arêtes et des nœuds, ces relations de réseau ne peuvent utiliser quun sous-ensemble spécifique de mathématiques, de statistiques et dapprentissage automatique. Les espaces vectoriels ont un ensemble doutils plus riche de ces domaines. De plus, les opérations vectorielles sont souvent plus simples et plus rapides que les opérations graphiques équivalentes.

Un exemple est la recherche de voisins les plus proches. Vous pouvez effectuer des « sauts » dun nœud à un autre dans un graphique. Dans de nombreux graphiques du monde réel après quelques sauts, il y a peu dinformations significatives (par exemple, des recommandations damis ou damis damis). Cependant, dans les espaces vectoriels, vous pouvez utiliser des métriques de distance pour obtenir des résultats quantitatifs (par exemple, distance euclidienne ou similarité cosinus). Si vous avez des mesures de distance quantitatives dans un espace vectoriel significatif, il est simple de trouver les voisins les plus proches.

«  Techniques, applications et performances dincorporation de graphiques: une enquête « est un article de synthèse qui donne plus de détails.

Que sont les incorporations de graphes? « Les incorporations de graphes » sont aujourdhui un domaine brûlant de lapprentissage automatique. Cela signifie essentiellement trouver une «représentation vectorielle latente» des graphes qui capture la topologie (au sens très basique) du graphe. Nous pouvons enrichir cette «représentation vectorielle» en considérant également les relations sommet-sommet, les informations sur les bords, etc. Il y a à peu près deux niveaux de plongements dans le graphe (bien sûr, nous pouvons à tout moment définir plus de niveaux en divisant logiquement le graphe entier en sous-graphes de différentes tailles):

• Vertex Embeddings – Ici vous trouvez une représentation vectorielle latente de chaque sommet du graphe donné. Vous pouvez ensuite comparer les différents sommets en traçant ces vecteurs dans lespace et il est intéressant de noter que les sommets «similaires» sont tracés plus près les uns des autres que ceux qui sont dissemblables ou moins liés. Cest le même travail qui est fait dans « DeepWalk » par Perozzi.
• Graph Embeddings – Ici vous trouvez la représentation vectorielle latente du graphe entier lui-même. Par exemple, vous avez un groupe de composés chimiques pour lesquels vous souhaitez vérifier quels composés sont similaires les uns aux autres, combien de types de composés se trouvent dans le groupe (grappes), etc. Vous pouvez utiliser ces vecteurs et les tracer dans lespace et trouvez toutes les informations ci-dessus. Cest le travail qui est effectué dans « Deep Graph Kernels » par Yanardag.

Applications – En regardant attentivement, les plongements sont des représentations « latentes », ce qui signifie que si un graphe a un | V | * | V | matrice de contiguïté où | V | = 1M, il est difficile dutiliser ou de traiter un nombre de 1M * 1M dans un algorithme. Ainsi, lincorporation latente de la dimension « d », où d < < | V |, ferait la matrice de contiguïté | V | * d et relativement plus facile à utiliser. Une autre application pourrait être – Considérez un scénario simple où nous voulons recommander des produits aux personnes qui ont des intérêts similaires dans un réseau social.En obtenant des plongements de sommets (ici, cela signifie une représentation vectorielle de chaque personne), nous pouvons trouver les similaires en traçant ces vecteurs et cela facilite la recommandation. Ce sont des applications et il y en a dautres. Vous pouvez vous référer à un beau document denquête – Graph Embedding Techniques, a Survey .

Doù vient tout cela? Il y a eu beaucoup de travaux dans ce domaine et presque tous proviennent de la recherche révolutionnaire dans le domaine du traitement du langage naturel – « Word2Vec » de Mikolov. Si vous souhaitez commencer la recherche sur les incorporations de graphiques, je vous recommande de comprendre dabord comment fonctionne Word2Vec. Vous pouvez trouver de belles explications – Apprentissage des paramètres Word2Vec expliqué et Conférence de Stanford . Ensuite, vous pouvez accéder aux articles que vous avez répertoriés. Ces travaux peuvent être classés comme suit:

• Travaux basés sur « Vertex Embeddings »: – DeepWalk , Node2Vec , LINE .

• Fonctionne sur « Graph Embeddings »: – Deep Graph Kernels , Subgraph2Vec .

Commentaires

• Wowww !! Cest une réponse absolument parfaite. Merci beaucoup 🙂 Très bien 🙂
• Salut Mausam Jain. Pouvez-vous me faire savoir si je peux utiliser les représentations graphiques pour identifier les nœuds importants du réseau?
• Bonjour, Volka. Pour répondre à cette question, jai besoin de savoir sur quel type de graphique travaillez-vous; est-ce Twitter, Facebook, Reddit ou autre chose?
• Merci pour votre réponse. Je travaille actuellement dans un réseau social où je souhaite identifier les personnes les plus sociales 🙂
• Voici ‘ une version plus élaborée de cette réponse. versdatascience.com/…

Dans le document Un théorème de limite central pour une intégration omnibus de graphiques de produits scalaires aléatoires par Levin et.al. papier, un type spécifique dincorporation de graphes (lintégration Omnibus) définit lincorporation de graphes comme une méthodologie «dans laquelle les sommets dun graphe sont mappés en vecteurs dans un espace euclidien de faible dimension». Consultez le lien pour plus dinformations.

Commentaires

• Bienvenue sur le forum. Si vous souhaitez mentionner un article, veuillez également noter son nom dans le texte (car les liens peuvent être rompus).