¿Qué son las incrustaciones de gráficos?

La incrustación de gráficos aprende un mapeo de una red a un espacio vectorial, al tiempo que conserva las propiedades de red relevantes.

Los espacios vectoriales son más adecuados para la ciencia de datos que los gráficos. Los gráficos contienen bordes y nodos, esas relaciones de red solo pueden usar un subconjunto específico de matemáticas, estadísticas y aprendizaje automático. Los espacios vectoriales tienen un conjunto de herramientas más rico de esos dominios. Además, las operaciones vectoriales suelen ser más sencillas y rápidas que las operaciones gráficas equivalentes.

Un ejemplo es encontrar vecinos más cercanos. Puede realizar «saltos» de un nodo a otro en un gráfico. En muchos gráficos del mundo real después de un par de saltos, hay poca información significativa (por ejemplo, recomendaciones de amigos o amigos de amigos). Sin embargo, en espacios vectoriales, puede usar métricas de distancia para obtener resultados cuantitativos (por ejemplo, distancia euclidiana o similitud de coseno). Si tiene métricas de distancia cuantitativas en un espacio vectorial significativo, encontrar los vecinos más cercanos es sencillo.

« Técnicas, aplicaciones y rendimiento de incorporación de gráficos: una encuesta «es un artículo de descripción general que entra en más detalles.

¿Qué son las incrustaciones de gráficos? Las «incrustaciones de gráficos» son un tema de actualidad en el aprendizaje automático. Básicamente significa encontrar una «representación vectorial latente» de gráficos que capture la topología (en un sentido muy básico) del gráfico. Podemos enriquecer esta «representación vectorial» considerando también las relaciones vértice-vértice, información de borde, etc. Hay aproximadamente dos niveles de incrustaciones en el gráfico (por supuesto, en cualquier momento podemos definir más niveles dividiendo lógicamente todo el gráfico en subgrafos de varios tamaños):

• Vertex Embeddings – Aquí encontrará una representación vectorial latente de cada vértice en el gráfico dado. A continuación, puede comparar los diferentes vértices trazando estos vectores en el espacio y, curiosamente, los vértices «similares» se trazan más cerca entre sí que los que son diferentes o menos relacionados. Este es el mismo trabajo que hizo Perozzi en «DeepWalk».
• Graph Embeddings – Aquí encuentra la representación vectorial latente de todo el gráfico en sí. Por ejemplo, tiene un grupo de compuestos químicos para los que desea verificar qué compuestos son similares entre sí, cuántos tipos de compuestos hay en el grupo (clústeres), etc. Puede usar estos vectores y trazarlos en el espacio y encuentre toda la información anterior. Este es el trabajo que realiza Yanardag en «Deep Graph Kernels».

Aplicaciones – Al mirar con atención, las incrustaciones son representaciones «latentes», lo que significa que si un gráfico tiene una | V | * | V | matriz de adyacencia donde | V | = 1 M, es difícil de usar o procesar números de 1 M * 1 M en un algoritmo. Entonces, la incrustación latente de la dimensión «d», donde d < < | V |, haría la matriz de adyacencia | V | * dy relativamente más fácil de usar. Otra aplicación podría ser: Considere un escenario simple en el que queremos recomendar productos a las personas que tienen intereses similares en una red social.Al obtener incrustaciones de vértices (aquí significa representación vectorial de cada persona), podemos encontrar las similares trazando estos vectores y esto facilita la recomendación. Estas son algunas aplicaciones y hay otras. Puede consultar un buen trabajo de encuesta: Técnicas de incorporación de gráficos, una encuesta .

¿De dónde vino todo esto? Ha habido muchos trabajos en esta área y casi todos provienen de la investigación pionera en el campo del procesamiento del lenguaje natural: «Word2Vec» de Mikolov. Si desea comenzar con la investigación sobre incrustaciones de gráficos, le recomendaría que primero comprenda cómo funciona Word2Vec. Puede encontrar buenas explicaciones: explicación del aprendizaje de parámetros de Word2Vec y Conferencia de Stanford . Luego, puede pasar a los documentos que enumeró. Estos trabajos se pueden clasificar como:

• Trabajos basados en «Incrustaciones de vértices»: – DeepWalk , Node2Vec , LINE .

• Funciona según «Embeddings de gráficos»: – Núcleos de gráficos profundos , Subgraph2Vec .

Comentarios

• Wowww !! Esta es una respuesta absolutamente perfecta. Muchas gracias 🙂 Muy bien hecho 🙂
• Hola Mausam Jain. ¿Me puede hacer saber si puedo usar incrustaciones de gráficos para identificar nodos importantes en la red?
• Hola, Volka. Para responder a esta pregunta, necesito saber en qué tipo de gráfico estás trabajando; ¿Es twitter, facebook, reddit o algo más?
• Gracias por su respuesta. De hecho, estoy trabajando en una red social en la que quiero identificar a las personas más sociales 🙂
• Aquí ‘ hay una versión más elaborada de esta respuesta. forwarddatascience.com/…

En el artículo Un teorema del límite central para una incrustación ómnibus de gráficos de productos escalares aleatorios de Levin et.al. papel, un tipo específico de incrustación de gráficos (la incrustación de Omnibus) define la incrustación de gráficos como una metodología «en la que los vértices de un gráfico se asignan a vectores en un espacio euclidiano de baja dimensión». Consulte el enlace para obtener más información.

Comentarios

• bienvenido al foro. Si desea mencionar un artículo, escriba su nombre como parte del texto también (porque los enlaces pueden romperse).