GrafoLab

Resumo — Como transformamos um grafo complexo em números que um modelo de Machine Learning possa entender? A resposta é Graph Embeddings: a criação de um “DNA” numérico (um vetor) para cada nó da rede. Existem duas filosofias principais para isso: a “clássica”, baseada em caminhadas aleatórias (como DeepWalk e Node2Vec), e a “moderna”, baseada em agregação de mensagens (GNNs). Este post explica a intuição por trás de cada uma e, o mais importante, quando usar cada uma.

---

1. O Que é um Graph Embedding e Por Que Precisamos Dele?

Um grafo é uma estrutura de conexões. Um modelo de ML (como um classificador ou um sistema de recomendação) não entende “conexões”; ele entende números. Um embedding é a tradução.

É um vetor de números (ex: [0.2, -0.9, 0.5, ... 0.1]) que captura a “posição” e o “papel” de um nó no grafo. Nós que são “similares” no grafo devem ter vetores de embedding similares.

Uma vez que temos esses embeddings, podemos usá-los para tarefas como:

• Link Prediction: Prever se dois nós deveriam ter uma aresta (ex: “Você conhece o Fulano?”).
• Classificação de Nós: Rotular um nó (ex: “Este usuário é um bot ou um humano?”).
• Visualização: Encontrar clusters e comunidades na rede.

A grande questão é: como calcular esses vetores?

2. Método 1: Aprender “Andando” (DeepWalk & Node2Vec)

A primeira família de algoritmos se baseia em uma intuição poderosa: “Diga-me com quem andas, e te direi quem és.”

Para entender um nó, esses métodos simulam “passeios aleatórios” (random walks) que começam nele, como um andarilho pulando de nó em nó. A sequência de nós visitados (ex: Nó A -> Nó C -> Nó F -> Nó B) é tratada como uma “frase” que descreve o ponto de partida.

DeepWalk (Perozzi et al., 2014)

O DeepWalk foi o pioneiro. Sua ideia foi uma genial “reciclagem” de uma técnica de NLP (Processamento de Linguagem Natural):

1. Faça Passeios: A partir de cada nó, gere milhares de random walks curtos.
2. Use Word2Vec: Trate esses passeios como se fossem frases e os nós como se fossem palavras.
3. Treine o Skip-gram: Use o algoritmo Skip-gram (do Word2Vec) para aprender os embeddings. O Skip-gram é treinado para prever as “palavras de contexto” (nós vizinhos no passeio) dado um nó central.

O resultado? Nós que aparecem frequentemente nos mesmos “passeios” (ou seja, são estruturalmente próximos) acabarão com vetores de embedding muito similares.

Node2Vec (Grover & Leskovec, 2016)

O Node2Vec refinou essa ideia. Ele argumentou que “passeios aleatórios” puros são muito simples. O Node2Vec introduziu “passeios enviesados” (biased random walks), controlados por dois parâmetros:

• (Return parameter): Controla a chance de o passeio “voltar” para o nó que acabou de visitar. Um alto incentiva o passeio a explorar novos territórios.
• (In-out parameter): Controla a chance de o passeio ir para longe (DFS-like) ou ficar na vizinhança local (BFS-like).

Ao ajustar e , o Node2Vec permite ao pesquisador escolher se quer embeddings que capturem homofilia (quem são seus vizinhos imediatos, tipo BFS) ou similaridade estrutural (quem tem o mesmo “papel” na rede que você, como ser uma “ponte” entre comunidades, tipo DFS).

3. Método 2: Aprender “Agregando” (GNNs)

A segunda família de algoritmos, as Graph Neural Networks (GNNs), tem uma filosofia diferente. Em vez de “andar”, ela se baseia na intuição: “Diga-me o que seus vizinhos dizem.”

Uma GNN aprende o embedding de um nó através de um processo de agregação de mensagens (message passing). Em cada “camada” da GNN, o embedding de um nó é atualizado com base em duas coisas:

1. O embedding atual do próprio nó.
2. Uma “agregação” das mensagens (embeddings) de seus vizinhos imediatos.

Arquiteturas famosas de GNN fazem isso de formas diferentes:

• GCN (Graph Convolutional Network): Agrega os vizinhos usando uma “média normalizada”. É simples e eficaz.
• GraphSAGE (Hamilton et al., 2017): Pode usar agregadores mais complexos, como um max-pooling ou um LSTM, e é projetado para escalar massivamente.
• GAT (Graph Attention Network): Usa um mecanismo de “atenção” para dar pesos diferentes a vizinhos diferentes (ex: o “vizinho A” é mais importante que o “vizinho B” para definir quem eu sou).

A maior vantagem das GNNs é que elas podem naturalmente incorporar features (atributos) dos nós. O embedding final de um nó não é apenas sua posição na rede, mas uma combinação de sua posição E seus atributos (ex: idade, foto de perfil, texto, etc.).

4. O Duelo: Quando Usar Cada Abordagem?

Não existe “bala de prata”. A escolha depende do seu problema e dos seus recursos.

Característica	DeepWalk / Node2Vec (Walkers)	GNNs (GCN, GraphSAGE, etc.)
Filosofia Principal	Aprende por proximidade (caminhadas)	Aprende por agregação (vizinhança)
Uso de Atributos	Não (apenas estrutura do grafo)	Sim (estrutura + atributos dos nós/arestas)
Supervisão	Não-supervisionado	Supervisionado (mais comum)
Custo (Treino)	Rápido, paralelizável	Lento, mais complexo de treinar
Ponto Forte	Grafos gigantes, baselines rápidos, tarefas não-supervisionadas	Tarefas com atributos ricos, performance de ponta
Risco	Pode perder sinais de atributos	Over-smoothing (nós ficam parecidos demais)

Regra de bolso:

• Se seu grafo é enorme, você tem poucos (ou nenhuns) atributos de nós, e você precisa de um baseline rápido e não-supervisionado, comece com DeepWalk ou Node2Vec.
• Se você tem atributos ricos nos nós (texto, imagens, números), um rótulo claro para treinar (classificação, regressão), e precisa da melhor performance possível, use uma GNN.

5. A Tática Híbrida (O Melhor dos Dois Mundos)

Uma tática de especialista é usar os dois:

1. Rode o DeepWalk/Node2Vec no seu grafo gigante para gerar embeddings estruturais (não-supervisionados).
2. Use esses embeddings como as features iniciais (atributos de nó) para alimentar uma GNN.

Dessa forma, a GNN começa com um conhecimento profundo da estrutura do grafo e foca seu aprendizado em como refinar esse conhecimento usando os outros atributos e os rótulos supervisionados.

Conclusão

Tanto os “walkers” (DeepWalk, Node2Vec) quanto os “aggregators” (GNNs) são ferramentas essenciais no arsenal de quem trabalha com grafos. Os walkers são rápidos, escaláveis e ótimos para capturar a estrutura pura. As GNNs são mais caras, mas muito mais poderosas, pois combinam a estrutura do grafo com os atributos dos dados, permitindo um aprendizado end-to-end mais rico.

---

Referências

• Perozzi, B., Al-Rfou, R., & Skiena, S. (2014). DeepWalk: Online Learning of Social Representations. KDD 2014.
• Grover, A., & Leskovec, J. (2016). Node2Vec: Scalable Feature Learning for Networks. KDD 2016.
• Kipf, T. N., & Welling, M. (2016). Semi-Supervised Classification with Graph Convolutional Networks. arXiv.
• Hamilton, W., Ying, Z., & Leskovec, J. (2017). Inductive Representation Learning on Large Graphs (GraphSAGE). NeurIPS 2017.
• Veličković, P. et al. (2018). Graph Attention Networks (GAT). ICLR 2018.

Sobre o autor

Rener Menezes
Cofundador & CTO — FitBank

Rener Menezes é cofundador e CTO do FitBank, fintech brasileira de Banking-as-a-Service. Com mais de 25 anos de experiência projetando sistemas financeiros em larga escala, é bacharel em Sistemas de Informação e mestrando na Unifor, onde pesquisa Redes Neurais de Grafos e aprendizado por reforço para detecção de fraude. Interesses: sistemas distribuídos, infraestrutura de pagamentos e graph ML.

Links: LinkedIn · ORCID · contato@grafolab.ia.br