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!
13
Respuestas:
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.
fuente
¿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):
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:
Obras basadas en "Incrustaciones de vértices": - DeepWalk , Node2Vec , LINE .
Trabajos basados en "Incrustaciones de gráficos": - Deep Graph Kernels , Subgraph2Vec .
fuente
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.
fuente