Skip to content
Voltar aos resultados

Embedding de Rede — Node2Vec, DeepWalk, LINE

Ano
2014 (DeepWalk); 2016 (Node2Vec)
Tipo
Representation learning / unsupervised network method

Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês

Tamanho da fonte

O que ele faz?

Embedding de rede é uma família de métodos de aprendizado de representação que mapeiam cada nó de um grafo para um vetor denso e de baixa dimensão, preservando as propriedades estruturais da rede.

A abordagem foi formalizada para dados de redes sociais por Perozzi, Al-Rfou e Skiena com DeepWalk (2014), que adaptou o modelo skip-gram do Word2Vec para caminhadas aleatórias em grafos, e estendida por Grover e Leskovec com Node2Vec (2016), que introduziu uma caminhada aleatória enviesada que equilibra a exploração em largura e em profundidade. Esses embeddings transformam dados relacionais em vetores de características que classificadores e algoritmos de clusterização de aprendizado de máquina padrão podem consumir diretamente.

A intuição por trás do método

Um grafo é composto por nós e arestas, mas a maioria dos algoritmos de aprendizado de máquina espera uma tabela de números. O embedding de rede resolve o problema de tradução. Assim como o Word2Vec aprende significados de palavras observando quais palavras aparecem próximas umas das outras em frases, o DeepWalk aprende significados de nós observando quais nós aparecem próximos uns dos outros em caminhadas aleatórias pelo grafo. O resultado é uma coordenada em um espaço vetorial — nós que são estruturalmente semelhantes ou frequentemente co-visitados acabam próximos. Uma vez que cada nó tem um vetor, você pode alimentar esses vetores em um classificador, agrupá-los com k-means, ou visualizá-los com UMAP, sem escrever nenhum código específico para grafos.

História

A ideia de aplicar Word2Vec a dados estruturados em grafos foi introduzida por Perozzi, Al-Rfou e Skiena em DeepWalk (KDD 2014), que mostrou que caminhadas aleatórias em um grafo social poderiam substituir características criadas manualmente para classificação de nós. Grover e Leskovec estenderam isso em Node2Vec (KDD 2016) introduzindo uma caminhada aleatória enviesada de segunda ordem parametrizada por p e q, fornecendo controle explícito sobre o trade-off entre exploração de vizinhança baseada em homofilia e equivalência estrutural. Por volta do mesmo período, Tang et al. propuseram LINE (WWW 2015), que aprende embeddings otimizando objetivos de proximidade de primeira e segunda ordem diretamente, em vez de através de caminhadas aleatórias, tornando-o adequado para grafos muito grandes. Juntos, esses três métodos estabeleceram o campo de aprendizado de representação de rede e inspiraram arquiteturas subsequentes de redes neurais de grafos.

Quando usar

O embedding de rede é apropriado quando você tem um grafo de pelo menos 50 nós e precisa de características vetoriais contínuas para tarefas downstream, como classificação de nós, previsão de links ou clusterização de nós. O método é adequado para grafos não ponderados e ponderados, e lida com estruturas direcionadas ou não direcionadas. Escolha DeepWalk quando uma linha de base simples de caminhada aleatória uniforme for suficiente. Escolha Node2Vec quando você quiser ajustar o equilíbrio entre homofilia e equivalência estrutural através dos parâmetros p e q. Se você precisar embutir novos nós, nunca vistos antes, no tempo de inferência sem retreinamento, prefira um método indutivo como GraphSAGE; o embedding de rede em sua forma padrão é transdutivo. O método não requer atributos de nó normalmente distribuídos.

Limitações e considerações

  • Transdutivo: o modelo não pode embutir nós que não estavam presentes durante o treinamento sem retreinamento completo.
  • Sensibilidade a hiperparâmetros: dimensão de embedding, comprimento da caminhada, número de caminhadas, tamanho da janela, p e q afetam a qualidade do embedding e requerem ajuste.
  • Caminhadas aleatórias não capturam estrutura de grafo de ordem superior (por exemplo, hiperarestas ou arestas multirelacionais) sem extensão.
  • O desempenho degrada em grafos muito pequenos (menos de 50 nós), onde o corpus de caminhadas é muito esparso para aprender estatísticas confiáveis.

As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.

Pontos fortes

  • Converte dados de grafos relacionais em vetores de comprimento fixo compatíveis com qualquer pipeline de aprendizado de máquina padrão.
  • Os parâmetros p e q do Node2Vec permitem que o analista ajuste o equilíbrio entre embeddings sensíveis à comunidade e sensíveis ao papel.
  • Pesos de arestas podem ser incorporados às probabilidades de caminhada, capturando a força do relacionamento sem etapas extras de modelagem.
  • Escala para grafos grandes através de amostragem eficiente de caminhadas aleatórias e o procedimento de treinamento skip-gram.

Aplicações

  • Classificação de nós em redes de citação, plataformas sociais ou grafos de interação biológica.
  • Previsão de links — identificando arestas ausentes ou futuras comparando a similaridade de embeddings de nós.
  • Detecção de comunidades agrupando vetores de nós com k-means ou métodos hierárquicos.
  • Detecção de anomalias — nós cujos embeddings são outliers no espaço vetorial podem representar papéis estruturais incomuns.
  • Sistemas de recomendação onde usuários e itens são nós em um grafo de interação bipartido ou multiplexado.

Como funciona

Como funciona

1

O processo começa com um grafo G no qual os nós são entidades e as arestas representam relacionamentos. As arestas podem ser direcionadas ou não direcionadas e podem carregar pesos que influenciarão posteriormente a probabilidade de travessia. Se os pesos das arestas estiverem presentes, eles são incluídos nas probabilidades de caminhada; se ausentes, todas as arestas recebem peso igual. Nesta fase, o analista também escolhe a variante do algoritmo — DeepWalk para caminhadas aleatórias uniformes, Node2Vec para caminhadas enviesadas controladas pelos parâmetros p (retorno) e q (dentro-fora), ou LINE quando a proximidade de vizinhança de primeira e segunda ordem deve ser aprendida separadamente. A escolha entre os regimes de parâmetros do Node2Vec é guiada pela propriedade esperada da rede: homofilia (nós semelhantes se conectam, então a exploração em largura é preferida, q < 1) ou equivalência estrutural (nós com papéis semelhantes podem estar distantes, então a exploração em profundidade é preferida, p < 1).

2

A partir de cada nó, o algoritmo simula uma série de caminhadas aleatórias de comprimento fixo (tipicamente 30 passos) e as repete muitas vezes (tipicamente 200 caminhadas por nó). Cada caminhada produz uma sequência de identificadores de nós análoga a uma frase de palavras. No DeepWalk, o próximo nó é escolhido uniformemente entre os vizinhos. No Node2Vec, o próximo nó é escolhido de acordo com probabilidades de transição enviesadas por p e q: retornar ao nó anterior é penalizado por 1/p, permanecer à mesma distância é mantido em 1, e mover-se mais para fora é controlado por 1/q. A coleção de todas as caminhadas forma um corpus de sequências de nós que codifica a topologia do grafo.

3

O corpus de sequências de nós é alimentado em um modelo skip-gram (a mesma arquitetura do Word2Vec). Para cada nó em uma caminhada, o modelo prevê os nós de contexto circundantes dentro de uma janela (tipicamente 10 passos). Através de gradiente descendente estocástico, o modelo aprende uma representação vetorial densa de dimensão fixa — comumente 64 ou 128 — para cada nó, de modo que nós co-ocorrentes em caminhadas tenham vetores semelhantes. A dimensão é um hiperparâmetro: dimensões maiores capturam mais estrutura, mas aumentam a computação e o risco de overfitting em grafos pequenos.

4

Uma vez treinado, o modelo fornece um vetor de embedding por nó. Esses vetores são usados como características para classificação de nós (alimentando-os em um classificador de regressão logística ou neural), previsão de links (comparando vetores de pares de nós candidatos), ou detecção de comunidades (agrupando os vetores). Os embeddings são transdutivos: eles são fixos para os nós vistos durante o treinamento. Se novos nós precisam ser embutidos após o treinamento, um método indutivo como GraphSAGE deve ser usado em vez disso, pois um modelo padrão Node2Vec ou DeepWalk não pode generalizar para nós não vistos sem retreinamento.

Erros comuns

  • Aplicar um modelo Node2Vec a novos nós que não estavam no grafo de treinamento — o modelo não terá um vetor para eles; use um método indutivo (por exemplo, GraphSAGE) quando o embedding transdutivo não for aceitável.
  • Usar p=1, q=1 padrão (equivalente a DeepWalk) sem examinar se a rede segue um padrão de homofilia ou equivalência estrutural — ajustar p e q ao padrão esperado pode melhorar substancialmente o desempenho da tarefa downstream.
  • Tratar a dimensão de embedding como uma constante fixa: em grafos pequenos, uma dimensão de 64 ou 128 pode causar overfitting; comece com um valor menor e valide na tarefa downstream.
  • Ignorar o requisito mínimo de amostra: grafos com menos de 50 nós produzem corpora de caminhadas muito finos para treinar embeddings confiáveis.

Perguntas frequentes

Qual é a diferença entre DeepWalk, Node2Vec e LINE?

DeepWalk usa caminhadas aleatórias uniformes e o modelo skip-gram do Word2Vec — é a linha de base mais simples. Node2Vec adiciona caminhadas aleatórias enviesadas controladas por p e q, permitindo que o analista ajuste se a caminhada explora como busca em largura (homofilia) ou busca em profundidade (equivalência estrutural). LINE não usa caminhadas aleatórias; ele otimiza objetivos de proximidade de primeira e segunda ordem diretamente na lista de arestas, o que é mais escalável para grafos muito grandes, mas sacrifica o sinal de vizinhança baseado em caminhada.

Como escolho os parâmetros p e q no Node2Vec?

p controla a probabilidade de retornar ao nó anterior (p baixo = menos backtracking), e q controla o raio de exploração (q < 1 favorece a exploração externa, q > 1 mantém a caminhada próxima à origem). Se você espera que nós na mesma comunidade sejam semelhantes (homofilia), defina q < 1 para permitir que a caminhada vagueie para fora. Se você espera que nós com o mesmo papel estrutural sejam semelhantes, mesmo que distantes, defina p < 1 para incentivar a exploração em profundidade. Valide ambos os regimes na tarefa downstream.

Posso embutir novos nós após o treinamento sem retreinar todo o modelo?

Node2Vec e DeepWalk padrão são transdutivos: a matriz de embedding cobre apenas os nós vistos durante o treinamento. Para generalização indutiva para nós novos, nunca vistos antes, use um método indutivo de rede neural de grafos como GraphSAGE, que aprende uma função de agregação sobre vizinhanças de nós que pode ser aplicada a qualquer nó no tempo de inferência.

Quantas dimensões devo usar para o embedding?

As escolhas mais comuns são 64 e 128, e estas funcionam bem para grafos médios a grandes. Para grafos pequenos (50–200 nós), comece com uma dimensão menor (16 ou 32) para evitar overfitting e avalie a qualidade do embedding medindo o desempenho da tarefa downstream (por exemplo, precisão da classificação de nós) em vez de apenas o erro de reconstrução.

Métodos relacionados

Fontes

  1. 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 referência DOI
    Copiado.
  2. 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 referência DOI
    Copiado.