Graph Neural Network (GNN)

Uma rede neural de grafos (GNN) é uma rede neural que opera diretamente em grafos: conjuntos de nós conectados por arestas, nos quais tanto os nós quanto as arestas podem conter características. Moléculas (átomos e ligações), redes sociais (usuários e conexões), redes rodoviárias (cruzamentos e trechos de estradas), malhas 3D e as articulações de um esqueleto humano são todos grafos. Um grafo não tem uma grade ou ordem fixa, e seus nós têm números diferentes de vizinhos; por isso, os filtros deslizantes de uma rede neural convolucional (CNN) e a leitura passo a passo de uma rede neural recorrente (RNN) não se aplicam diretamente. As GNNs lidam com isso por meio da passagem de mensagens: cada nó atualiza repetidamente seu vetor de características a partir dos vetores de seus vizinhos, produzindo embeddings de nós que codificam tanto os atributos do próprio nó quanto sua posição no grafo.

Como funciona a passagem de mensagens#

Uma camada GNN atualiza cada nó em três etapas. Cada vizinho envia uma mensagem, geralmente uma transformação aprendida das suas características. O nó agrega as mensagens recebidas com uma função que ignora a ordem, como soma, média ou máximo. Em seguida, combina a agregação com as próprias características para formar uma nova representação. Como a agregação ignora a ordem, o resultado não depende de como os nós são numerados. Em 2017, Justin Gilmer e colegas descreveram muitas GNNs como casos particulares desta estrutura de rede neural de passagem de mensagens. Após a última camada, uma cabeça específica para a tarefa lê as incorporações dos nós para classificá-los, prever arestas em falta ou classificar o grafo inteiro:

Cada camada amplia a vizinhança de um nó em um salto; assim, após k camadas, a incorporação de um nó depende de todos os nós a até k arestas de distância, o seu campo recetivo no grafo. O trecho de código PyTorch abaixo cria um grafo de caminho com seis nós, aplica três camadas de convolução em grafos com a normalização do GCN de Thomas Kipf e Max Welling e usa autograd para listar os nós de entrada que afetam o nó 0 após cada camada:

import torch
from torch import nn

# A path graph 0-1-2-3-4-5 as an adjacency matrix with self-loops
A = torch.eye(6)
for i in range(5):
    A[i, i + 1] = A[i + 1, i] = 1
deg = A.sum(dim=1)
A_hat = A / torch.sqrt(deg[:, None] * deg[None, :])  # GCN normalization D^-1/2 (A + I) D^-1/2

torch.manual_seed(0)
x = torch.randn(6, 4, requires_grad=True)  # 4 input features per node
layers = [nn.Linear(4, 4) for _ in range(3)]

h = x
for k, layer in enumerate(layers, start=1):
    h = torch.tanh(A_hat @ layer(h))  # each node mixes in its neighbors' transformed features
    grad = torch.autograd.grad(h[0].sum(), x, retain_graph=True)[0]
    print(f"After layer {k}, node 0 depends on nodes {grad.abs().sum(dim=1).nonzero().flatten().tolist()}")

O código imprime [0, 1], [0, 1, 2] e [0, 1, 2, 3]: o campo recetivo do nó 0 aumenta exatamente um salto por camada.

Arquiteturas GNN comuns#

• GCN: A rede convolucional em grafos calcula H′ = σ(D̃^(−1/2) à D̃^(−1/2) H W), em que à é a matriz de adjacência com autoarestas e D̃ é a respetiva matriz de graus: uma média ponderada pelo grau de cada nó e dos seus vizinhos, seguida de uma matriz de pesos W partilhada por todos os nós.
• GraphSAGE: Amostra um número fixo de vizinhos por nó e aprende o agregador, o que permite escalar para grafos muito grandes e incorporar nós que surgem após o treino.
• GAT: As redes de atenção em grafos atribuem a cada vizinho pesos baseados em pontuações de atenção aprendidas, em vez de pesos fixos baseados no grau.
• GIN: A rede de isomorfismo de grafos soma os vizinhos e aplica um MLP. Keyulu Xu e colegas provaram que isto permite distinguir grafos tão bem quanto o teste de Weisfeiler-Lehman, o limite superior da passagem de mensagens padrão.
• Transformers para grafos: Aplicam autoatenção a todos os nós e acrescentam codificações posicionais derivadas da estrutura do grafo. Um transformer padrão é, por si só, uma GNN num grafo totalmente conectado de tokens.

Empilhar muitas camadas provoca sobressuavização: a média repetida aproxima entre si as incorporações dos nós até se tornarem indistinguíveis. Por isso, muitas GNNs usam apenas duas ou três camadas, tal como o GCN original, que usava duas. PyTorch Geometric e a Deep Graph Library (DGL) implementam estas camadas de forma eficiente em listas esparsas de arestas.

Aplicações no mundo real#

• Previsão meteorológica: O GraphCast da Google DeepMind, publicado na Science em 2023, executa passagem de mensagens numa malha multiescala que cobre o globo e produz previsões para 10 dias com resolução de 0,25° em menos de um minuto. Supera os sistemas determinísticos operacionais mais precisos em 90% de 1.380 alvos de verificação.
• Descoberta de fármacos: Em 2020, investigadores do MIT treinaram uma rede de passagem de mensagens direcionada para prever a atividade antibacteriana a partir de grafos moleculares e usaram-na para identificar a halicina, um composto estruturalmente diferente dos antibióticos conhecidos que matou muitas bactérias resistentes a fármacos em testes laboratoriais.
• Sistemas de recomendação: O PinSage do Pinterest aprendeu incorporações de pins a partir de um grafo com 3 mil milhões de pins e pastas e 18 mil milhões de arestas, treinado com 7,5 mil milhões de exemplos.
• Reconhecimento de ações baseado em esqueletos: O ST-GCN trata as articulações do corpo como nós, conecta-as por ossos em cada fotograma e à mesma articulação nos fotogramas vizinhos, e classifica a ação com base no grafo espaço-temporal resultante. Os modelos de estimativa de pose YOLO26 devolvem 17 pontos-chave COCO por pessoa em cada fotograma: as coordenadas articulares usadas para construir esse grafo de esqueleto.

GNNs e conceitos relacionados#

• Grafo de conhecimento: Uma estrutura de dados que armazena factos como triplos entidade-relação-entidade. Uma GNN é um modelo que pode aprender com um grafo de conhecimento, por exemplo, para prever ligações em falta.
• Aprendizagem profunda geométrica: Campo mais abrangente de redes construídas em torno das simetrias dos respetivos dados, que inclui CNNs em grelhas, GNNs em grafos e modelos em malhas e variedades.
• CNN: Uma CNN aplicada a uma imagem é um caso especial de passagem de mensagens num grafo em grelha. Cada píxel tem o mesmo número de vizinhos em posições relativas fixas, pelo que uma CNN pode aprender um peso separado para cada posição de vizinho, algo que uma GNN num grafo irregular não consegue fazer.