¿Qué son las incrustaciones de gráficos?

13

Recientemente me encontré con la incrustación de gráficos como DeepWalk y LINE. Sin embargo, todavía no tengo una idea clara de lo que se entiende por incrustaciones de gráficos y cuándo usarlo (aplicaciones). Cualquier sugerencia es bienvenida!

Volka
fuente
1
¡Una incrustación de gráficos es una incrustación de gráficos! Por lo tanto, toma un gráfico y devuelve las incrustaciones para el gráfico, las aristas o los vértices. Las incrustaciones permiten la búsqueda de similitudes y, en general, facilitan el aprendizaje automático al proporcionar representaciones .
Emre
@Emre, ¿qué significa incrustar? :)
Volka
1
Según el significado de la inserción, fijar cosas en algo. La incrustación de gráficos es como fijar vértices en una superficie y dibujar bordes para representar, por ejemplo, una red. Así, por ejemplo, ser como un gráfico plano puede incrustarse en una superficie sin cruce de bordes. Se pueden asignar pesos a las aristas y longitudes de arista apropiadas a saber. nos ayuda a entender / estimar como @Emre mencionó la búsqueda de similitud, etc.2D
Kiritee Gak
@ KiriteeGak Gracias :) ¿Cuáles son sus aplicaciones en el mundo real? ¿Dicen que pueden usarse para recomendación y todo? ¿pero cómo?
Volka
1
La recomendación de video de YouTube se puede visualizar como un modelo en el que el video que está viendo actualmente es el nodo en el que se encuentra y los siguientes videos que están en su recomendación son los que son más similares a usted en función de lo que los usuarios similares han visto a continuación y muchos más factores, por supuesto, que es una gran red para atravesar. Este documento es una buena lectura simple sobre cómo entender la aplicación.
Kiritee Gak

Respuestas:

19

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

Los espacios vectoriales son más susceptibles a la ciencia de datos que los gráficos. Los gráficos contienen aristas 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 a menudo son más simples y rápidas que las operaciones gráficas equivalentes.

Un ejemplo es encontrar vecinos más cercanos. Puede realizar "saltos" de nodo a otro nodo 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 de 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 vecinos más cercanos es sencillo.

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

Brian Spiering
fuente
26

¿Qué son las incrustaciones de gráficos? Las "incrustaciones de gráficos" son un área de actualidad en el aprendizaje automático. Básicamente significa encontrar una "representación vectorial latente" de gráficos que captura 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):

  • Incrustaciones de vértices : aquí encontrará una representación vectorial latente de cada vértice en el gráfico dado. Luego, puede comparar los diferentes vértices trazando estos vectores en el espacio y, de manera interesante, los vértices "similares" se trazan más cerca el uno del otro que los que son diferentes o menos relacionados. Este es el mismo trabajo que realiza Perozzi en "DeepWalk".
  • Incrustaciones de gráficos : aquí encontrará la representación vectorial latente de todo el gráfico. 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 (grupos), etc. Puede usar estos vectores y trazarlos en el espacio y Encuentra toda la información anterior. Este es el trabajo que Yanardag realiza en "Deep Graph Kernels".

Aplicaciones: al observar cuidadosamente, las incrustaciones son representaciones "latentes", lo que significa que si un gráfico tiene un | V | * | V | matriz de adyacencia donde | V | = 1M, es difícil de usar o procesar números 1M * 1M en un algoritmo. Entonces, la incrustación latente de la dimensión 'd', donde d << | V |, haría la matriz de adyacencia | V | * d y 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 al trazar estos vectores y esto hace que la recomendación sea fácil. Estas son algunas aplicaciones y hay otras. Puede consultar un buen documento de encuesta: Técnicas de incrustación de gráficos, una encuesta .

¿De dónde vino todo? Se han realizado muchos trabajos en esta área y casi todos provienen de la investigación innovadora 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 entienda cómo funciona Word2Vec. Puede encontrar buenas explicaciones: explicación del aprendizaje de parámetros de Word2Vec y Stanford Lecture . Luego puede saltar a los documentos que enumeró. Esos trabajos se pueden clasificar como:

flyingDope
fuente
2
Wowww !! Esta es absolutamente una respuesta perfecta. Muchas gracias :) Muy bien hecho :)
Volka
Hola Mausam Jain ¿Puede decirme si puedo usar incrustaciones de gráficos para identificar nodos importantes en la red?
Volka
Hola volka Para responder a esta pregunta, necesito saber en qué tipo de gráfico está trabajando; ¿es twitter, facebook, reddit o alguna otra cosa?
flyingDope
Gracias por su respuesta. De hecho, estoy trabajando en una red social donde quiero identificar a las personas más sociales :)
Volka
0

En el artículo Un teorema del límite central para una incrustación ómnibus de gráficos de productos de puntos aleatorios por Levin et.al. En el documento, un tipo específico de incrustación de gráficos (la incrustación 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 más información.

chivo3million
fuente
Bienvenido al foro. Si desea mencionar un documento, escriba también su nombre como parte del texto (porque los enlaces pueden romperse).
Mark.F