Incrustación de Redes — Node2Vec, DeepWalk, LINE
- Año
- 2014 (DeepWalk); 2016 (Node2Vec)
- Tipo
- Representation learning / unsupervised network method
Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés
¿Qué hace?
La incrustación de redes es una familia de métodos de aprendizaje de representaciones que mapean cada nodo de un grafo a un vector denso y de baja dimensionalidad, preservando las propiedades estructurales de la red.
El enfoque fue formalizado para datos de redes sociales por Perozzi, Al-Rfou y Skiena con DeepWalk (2014), que adaptó el modelo skip-gram de Word2Vec a caminatas aleatorias en grafos, y extendido por Grover y Leskovec con Node2Vec (2016), que introdujo una caminata aleatoria sesgada que equilibra la exploración en anchura y en profundidad. Estas incrustaciones convierten los datos relacionales en vectores de características que los clasificadores y algoritmos de agrupamiento de aprendizaje automático estándar pueden consumir directamente.
La intuición detrás del método
Un grafo está compuesto por nodos y aristas, pero la mayoría de los algoritmos de aprendizaje automático esperan una tabla de números. La incrustación de redes resuelve el problema de la traducción. Así como Word2Vec aprende significados de palabras observando qué palabras aparecen cerca unas de otras en las oraciones, DeepWalk aprende significados de nodos observando qué nodos aparecen cerca unos de otros en caminatas aleatorias a través del grafo. El resultado es una coordenada en un espacio vectorial — los nodos que son estructuralmente similares o que se visitan frecuentemente juntos terminan cerca. Una vez que cada nodo tiene un vector, se pueden alimentar esos vectores a un clasificador, agruparlos con k-means, o visualizarlos con UMAP, sin necesidad de escribir código específico para grafos.
Historia
La idea de aplicar Word2Vec a datos estructurados en grafos fue introducida por Perozzi, Al-Rfou y Skiena en DeepWalk (KDD 2014), que demostró que las caminatas aleatorias en un grafo social podían reemplazar las características diseñadas manualmente para la clasificación de nodos. Grover y Leskovec extendieron esto en Node2Vec (KDD 2016) introduciendo una caminata aleatoria sesgada de segundo orden parametrizada por p y q, proporcionando control explícito sobre el compromiso entre la exploración del vecindario basada en homofilia y la basada en equivalencia estructural. Alrededor del mismo período, Tang et al. propusieron LINE (WWW 2015), que aprende incrustaciones optimizando directamente objetivos de proximidad de primer y segundo orden en lugar de a través de caminatas aleatorias, lo que lo hace adecuado para grafos muy grandes. Juntas, estos tres métodos establecieron el campo del aprendizaje de representación de redes e inspiraron arquitecturas posteriores de redes neuronales de grafos.
Cuándo usarlo
La incrustación de redes es apropiada cuando se tiene un grafo de al menos 50 nodos y se necesitan características vectoriales continuas para tareas posteriores como clasificación de nodos, predicción de enlaces o agrupamiento de nodos. El método se adapta tanto a grafos no ponderados como ponderados, y maneja estructuras dirigidas o no dirigidas. Elija DeepWalk cuando una línea base simple de caminata aleatoria uniforme sea suficiente. Elija Node2Vec cuando desee ajustar el equilibrio entre homofilia y equivalencia estructural a través de los parámetros p y q. Si necesita incrustar nodos nuevos y previamente no vistos en tiempo de inferencia sin reentrenamiento, prefiera un método inductivo como GraphSAGE; la incrustación de redes en su forma estándar es transductiva. El método no requiere atributos de nodo distribuidos normalmente.
Limitaciones y consideraciones
- Transductivo: el modelo no puede incrustar nodos que no estuvieron presentes durante el entrenamiento sin un reentrenamiento completo.
- Sensibilidad a hiperparámetros: la dimensión de incrustación, la longitud de la caminata, el número de caminatas, el tamaño de la ventana, p y q afectan la calidad de la incrustación y requieren ajuste.
- Las caminatas aleatorias no capturan la estructura de grafo de orden superior (por ejemplo, hiperaristas o aristas multirelacionales) sin extensión.
- El rendimiento se degrada en grafos muy pequeños (menos de 50 nodos) donde el corpus de caminatas es demasiado disperso para aprender estadísticas fiables.
Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.
Fortalezas
- Convierte datos relacionales de grafos en vectores de longitud fija compatibles con cualquier canalización de aprendizaje automático estándar.
- Los parámetros p y q de Node2Vec permiten al analista ajustar el equilibrio entre incrustaciones sensibles a la comunidad y sensibles al rol.
- Los pesos de las aristas pueden incorporarse en las probabilidades de recorrido, capturando la fuerza de la relación sin pasos de modelado adicionales.
- Escala a grafos grandes a través de un muestreo eficiente de caminatas aleatorias y el procedimiento de entrenamiento skip-gram.
Aplicaciones
- Clasificación de nodos en redes de citas, plataformas sociales o grafos de interacción biológica.
- Predicción de enlaces — identificación de aristas faltantes o futuras comparando la similitud de las incrustaciones de nodos.
- Detección de comunidades agrupando vectores de nodos con k-means o métodos jerárquicos.
- Detección de anomalías — los nodos cuyas incrustaciones son valores atípicos en el espacio vectorial pueden representar roles estructurales inusuales.
- Sistemas de recomendación donde usuarios y elementos son nodos en un grafo de interacción bipartito o multiex.
Cómo funciona
Cómo funciona
El proceso comienza con un grafo G en el que los nodos son entidades y las aristas representan relaciones. Las aristas pueden ser dirigidas o no dirigidas y pueden tener pesos que influirán posteriormente en la probabilidad de recorrido. Si están presentes los pesos de las aristas, se incluyen en las probabilidades de recorrido; si están ausentes, todas las aristas reciben igual peso. En esta etapa, el analista también elige la variante del algoritmo — DeepWalk para caminatas aleatorias uniformes, Node2Vec para caminatas sesgadas controladas por los parámetros p (retorno) y q (entrada-salida), o LINE cuando la proximidad del vecindario de primer y segundo orden deben aprenderse por separado. La elección entre los regímenes de parámetros de Node2Vec se guía por la propiedad esperada de la red: homofilia (nodos similares se conectan, por lo que se prefiere la exploración en anchura, q < 1) o equivalencia estructural (nodos con roles similares pueden estar distantes, por lo que se prefiere la exploración en profundidad, p < 1).
Partiendo de cada nodo, el algoritmo simula una serie de caminatas aleatorias de longitud fija (típicamente 30 pasos) y las repite muchas veces (típicamente 200 caminatas por nodo). Cada caminata produce una secuencia de identificadores de nodo análoga a una oración de palabras. En DeepWalk, el siguiente nodo se elige uniformemente entre los vecinos. En Node2Vec, el siguiente nodo se elige según probabilidades de transición sesgadas por p y q: regresar al nodo anterior se penaliza con 1/p, mantenerse a la misma distancia se mantiene en 1, y alejarse se controla con 1/q. La colección de todas las caminatas forma un corpus de secuencias de nodos que codifica la topología del grafo.
El corpus de secuencias de nodos se alimenta a un modelo skip-gram (la misma arquitectura que Word2Vec). Para cada nodo en una caminata, el modelo predice los nodos de contexto circundantes dentro de una ventana (típicamente 10 pasos). Mediante descenso de gradiente estocástico, el modelo aprende una representación vectorial densa de dimensión fija — comúnmente 64 o 128 — para cada nodo, de modo que los nodos que co-ocurren en las caminatas tengan vectores similares. La dimensión es un hiperparámetro: dimensiones mayores capturan más estructura pero aumentan el cálculo y el riesgo de sobreajuste en grafos pequeños.
Una vez entrenado, el modelo proporciona un vector de incrustación por nodo. Estos vectores se utilizan como características para la clasificación de nodos (alimentándolos a una regresión logística o un clasificador neuronal), la predicción de enlaces (comparando vectores de pares de nodos candidatos), o la detección de comunidades (agrupando los vectores). Las incrustaciones son transductivas: son fijas para los nodos vistos durante el entrenamiento. Si se deben incrustar nodos nuevos después del entrenamiento, se debe usar un método inductivo como GraphSAGE, ya que un modelo estándar de Node2Vec o DeepWalk no puede generalizar a nodos no vistos sin reentrenamiento.
Errores comunes
- Aplicar un modelo Node2Vec a nodos nuevos que no estaban en el grafo de entrenamiento — el modelo no tendrá un vector para ellos; use un método inductivo (por ejemplo, GraphSAGE) cuando la incrustación transductiva no sea aceptable.
- Usar p=1, q=1 por defecto (equivalente a DeepWalk) sin examinar si la red sigue un patrón de homofilia o equivalencia estructural — ajustar p y q al patrón esperado puede mejorar sustancialmente el rendimiento de la tarea posterior.
- Tratar la dimensión de incrustación como una constante fija: en grafos pequeños, una dimensión de 64 o 128 puede sobreajustar; comience más bajo y valide en la tarea posterior.
- Ignorar el requisito de muestra mínima: los grafos con menos de 50 nodos producen corpus de caminatas demasiado delgados para entrenar incrustaciones fiables.
Preguntas frecuentes
¿Cuál es la diferencia entre DeepWalk, Node2Vec y LINE?
DeepWalk utiliza caminatas aleatorias uniformes y el modelo skip-gram de Word2Vec — es la línea base más simple. Node2Vec añade caminatas aleatorias sesgadas controladas por p y q, permitiendo al analista ajustar si la caminata explora como una búsqueda en anchura (homofilia) o una búsqueda en profundidad (equivalencia estructural). LINE no utiliza caminatas aleatorias en absoluto; optimiza objetivos de proximidad de primer y segundo orden directamente en la lista de aristas, lo que es más escalable a grafos muy grandes pero sacrifica la señal del vecindario basada en caminatas.
¿Cómo elijo los parámetros p y q en Node2Vec?
p controla la probabilidad de regresar al nodo anterior (p bajo = menos retrocesos), y q controla el radio de exploración (q < 1 favorece la exploración hacia afuera, q > 1 mantiene la caminata cerca de la fuente). Si espera que los nodos en la misma comunidad sean similares (homofilia), establezca q < 1 para que la caminata explore hacia afuera. Si espera que los nodos con el mismo rol estructural sean similares incluso si están distantes, establezca p < 1 para fomentar la exploración en profundidad. Valide ambos regímenes en la tarea posterior.
¿Puedo incrustar nodos nuevos después del entrenamiento sin reentrenar todo el modelo?
Node2Vec y DeepWalk estándar son transductivos: la matriz de incrustación cubre solo los nodos vistos durante el entrenamiento. Para la generalización inductiva a nodos nuevos y previamente no vistos, use un método de red neuronal de grafos inductivo como GraphSAGE, que aprende una función de agregación sobre los vecindarios de nodos que puede aplicarse a cualquier nodo en tiempo de inferencia.
¿Cuántas dimensiones debo usar para la incrustación?
Las opciones más comunes son 64 y 128, y funcionan bien para grafos medianos a grandes. Para grafos pequeños (50–200 nodos) comience con una dimensión menor (16 o 32) para evitar el sobreajuste, y evalúe la calidad de la incrustación midiendo el rendimiento de la tarea posterior (por ejemplo, precisión de clasificación de nodos) en lugar de solo el error de reconstrucción.
Métodos relacionados
Fuentes
Grover, A. & Leskovec, J. (2016). Node2Vec: Scalable Feature Learning for Networks. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 855-864.
Abrir referencia DOICopiado.Perozzi, B., Al-Rfou, R., & Skiena, S. (2014). DeepWalk: Online Learning of Social Representations. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 701-710.
Abrir referencia DOICopiado.