Qu'est-ce que l'intégration de graphiques?

Je suis récemment tombé sur l'intégration de graphiques tels que DeepWalk et LINE. Cependant, je n'ai toujours pas une idée claire de ce que l'on entend par intégration de graphiques et quand l'utiliser (applications)? Toutes les suggestions sont les bienvenues!

L'incorporation de graphiques apprend un mappage d'un réseau à 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 réseau ne peuvent utiliser qu'un sous-ensemble spécifique de mathématiques, de statistiques et d'apprentissage automatique. Les espaces vectoriels ont un ensemble d'outils plus riche de ces domaines. De plus, les opérations vectorielles sont souvent plus simples et plus rapides que les opérations de graphique équivalentes.

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

" Graph Embedding Techniques, Applications, and Performance: A Survey " est un article de présentation plus détaillé.

Que sont les plongements graphiques? "Graph Embeddings" est un domaine brûlant aujourd'hui dans l'apprentissage automatique. Cela signifie essentiellement trouver une "représentation vectorielle latente" des graphiques qui capture la topologie (au sens très basique) du graphique. Nous pouvons enrichir cette "représentation vectorielle" en prenant également en compte les relations vertex-vertex, les informations sur les arêtes, etc. sous-graphiques de différentes tailles):

• Incorporation de sommets - Vous trouverez ici une représentation vectorielle latente de chaque sommet dans le graphique donné. Vous pouvez ensuite comparer les différents sommets en traçant ces vecteurs dans l'espace et, de façon intéressante, les sommets "similaires" sont tracés plus près les uns des autres que ceux qui sont différents ou moins liés. C'est le même travail qui est fait dans "DeepWalk" par Perozzi.
• Intégrations de graphiques - Vous trouverez ici la représentation vectorielle latente de l'ensemble du graphique lui-même. Par exemple, vous avez un groupe de composés chimiques pour lequel vous souhaitez vérifier quels composés sont similaires les uns aux autres, combien de types de composés y a-t-il dans le groupe (grappes), etc. Vous pouvez utiliser ces vecteurs et les tracer dans l'espace et trouver toutes les informations ci-dessus. C'est le travail qui est fait 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 d'adjacence où | V | = 1M, il est difficile d'utiliser ou de traiter un nombre de 1M * 1M dans un algorithme. Ainsi, l'incorporation latente de la dimension 'd', où d << | V |, rendrait la matrice d'adjacence | V | * d et relativement plus facile à utiliser. Une autre application pourrait être - Considérons 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, ce qui facilite la recommandation. Ce sont quelques applications et il y en a d'autres. Vous pouvez vous référer à un beau papier d'enquête - Graph Embedding Techniques, a Survey .

D'où tout cela venait? 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" par Mikolov. Si vous voulez commencer la recherche sur les intégrations de graphiques, je recommanderais d'abord de comprendre comment fonctionne Word2Vec. Vous pouvez trouver de belles explications - explication de l' apprentissage des paramètres Word2Vec et conférence de Stanford . Ensuite, vous pouvez accéder aux documents que vous avez répertoriés. Ces œuvres peuvent être classées comme:

• Œuvres basées sur "Vertex Embeddings": - DeepWalk , Node2Vec , LINE .

• Œuvres basées sur "Graph Embeddings": - Deep Graph Kernels , Subgraph2Vec .

Dans l'article Un théorème central limite pour une intégration omnibus de graphes de produits scalaires aléatoires par Levin et.al. papier, un type spécifique d'intégration graphique (l'incorporation Omnibus) définit l'intégration graphique comme une méthodologie "dans laquelle les sommets d'un graphique sont mappés à des vecteurs dans un espace euclidien de faible dimension." Consultez le lien pour plus d'informations.