Redes Neurais em Grafos: uma Introdução

A inteligência artificial aprendeu a lidar com dados tabulares, sequenciais e em grade, mas essas três formas cobrem uma fração pequena dos dados que importam. Planilhas, texto e imagens são casos particulares, domesticados, de uma estrutura muito mais geral. O mundo real é relacional. Pessoas se conectam a pessoas, átomos se ligam a átomos, cidades se ligam por estradas, neurônios se ligam por sinapses. Essas conexões não são um detalhe decorativo sobre os dados. São o dado. Este artigo trata de como uma rede neural aprende quando a informação vive nas arestas tanto quanto nos vértices.

“As redes são o pré-requisito para descrever qualquer sistema complexo, indicando que a teoria da complexidade deve inevitavelmente apoiar-se nos ombros da teoria das redes.” (Albert-László Barabási)

O objeto que formaliza “coisas conectadas a coisas” é o grafo, e a arquitetura que aprende sobre grafos é a GNN, de Graph Neural Network (rede neural em grafos). Nosso plano é honesto e linear. Primeiro definimos grafos com o rigor necessário para que um computador os manipule. Depois mostramos por que uma rede convolucional ou recorrente comum fracassa diante deles e qual princípio de projeto, a invariância à permutação, resolve o problema. Em seguida deduzimos a propagação de mensagens, e dela extraímos a GCN, de Graph Convolutional Network (rede convolucional em grafos), símbolo por símbolo, calculando uma camada inteira à mão sobre um grafo de quatro vértices que reaparecerá em todos os laboratórios interativos. Fechamos com duas arquiteturas que corrigem defeitos da GCN, a GAT, de Graph Attention Network (rede de atenção em grafos), e a GraphSAGE, além do problema do over-smoothing, que impõe um limite incômodo a quem quer redes profundas.

1. Por que grafos importam

Uma rede não é uma coleção de números soltos nem uma sequência ordenada. Ela tem estrutura, contexto e significado, e esses três atributos vivem no padrão das conexões. Considere uma rede social: cada usuário é um vértice, cada amizade é uma aresta. A informação relevante para prever se dois usuários virarão amigos não está apenas nos perfis individuais, mas em quantos amigos eles têm em comum, quão densa é a vizinhança compartilhada, quão central cada um é na rede. Nenhum desses sinais aparece se tratarmos cada usuário como uma linha isolada de uma planilha.

O caso mais literal é a química. Uma molécula é, sem metáfora, um grafo: cada átomo é um vértice com identidade e atributos próprios, como número atômico, carga e hibridização, e cada ligação química é uma aresta que carrega seu próprio tipo, simples, dupla ou aromática. A topologia dessa rede não é decorativa. Ela ajuda a determinar a forma tridimensional da molécula, sua atividade farmacológica e seu papel em reações bioquímicas. Dois compostos com exatamente os mesmos átomos e conexões diferentes são substâncias diferentes. Uma arquitetura que ignore a estrutura de conexão está, literalmente, jogando fora a informação que define a molécula.

As redes que interessam à ciência de dados têm ainda duas propriedades que tabelas e sequências não têm: são grandes, pois grafos reais chegam a bilhões de vértices, e frequentemente dinâmicas, com vértices e arestas surgindo e desaparecendo. Precisamos de uma abordagem que respeite a estrutura, escale para o tamanho real e tolere a mudança. Essa abordagem começa na teoria dos grafos, que formalizamos a seguir.

2. Grafos: a estrutura fundamental

Um grafo é uma estrutura matemática que modela relações entre objetos. Formalmente, um grafo $G$ é definido pela tupla $G = (V, E)$, na qual $V$ é um conjunto finito de vértices, as entidades, e $E$ é um conjunto de arestas, as relações entre pares de vértices. Ao longo do texto usaremos $N = \vert V \vert$ para o número de vértices e $M = \vert E \vert$ para o número de arestas. Um vértice representa uma entidade: um usuário, um átomo, uma cidade. Uma aresta $e \in E$ está associada a um par de vértices e representa uma relação entre eles: uma amizade, uma ligação química, uma estrada.

2.1 Direção, peso e adjacência

Grafos se classificam, primeiro, pela natureza de suas arestas. Em um grafo direcionado, ou dígrafo, a aresta tem sentido: ela é um par ordenado $(u, v)$, e a relação vai de $u$ para $v$, não necessariamente de volta. A relação “segue” em uma rede social é o exemplo canônico: o usuário $u$ pode seguir $v$ sem que $v$ siga $u$. Em um grafo não direcionado, a aresta é um par não ordenado ${u, v}$ e a relação é simétrica, como a amizade mútua. A atenta leitora deve fixar a diferença de notação, porque ela reaparecerá nas matrizes: parênteses $(u, v)$ para o par ordenado do dígrafo, chaves ${u, v}$ para o par não ordenado do grafo simétrico.

Arestas também podem carregar um peso. Em um grafo ponderado, a cada aresta $(u, v)$ associa-se um valor numérico $w_{uv}$ que quantifica a força, o custo, a distância ou a capacidade da conexão. Numa rede rodoviária, $w_{uv}$ pode ser a distância em quilômetros entre duas cidades; numa rede social, a intensidade de uma amizade. Quando o grafo é não ponderado, convencionamos $w_{uv} = 1$ para toda aresta existente.

Três termos de conectividade fecham o vocabulário básico. Dois vértices são adjacentes quando existe uma aresta que os conecta diretamente. Uma aresta é incidente aos dois vértices que ela conecta. E a vizinhança de um vértice $v$, denotada $\mathcal{N}(v)$, é o conjunto dos vértices adjacentes a ele: $\mathcal{N}(v) = {u \mid {v, u} \in E}$. A vizinhança é o conceito central deste artigo inteiro, porque é dela que cada vértice, numa GNN, coletará informação.

2.2 Grau e o teorema do aperto de mão

O grau de um vértice $v$, denotado $\deg(v)$, é o número de arestas incidentes a ele. Em um grafo direcionado, distinguimos o grau de entrada, que conta quantas arestas chegam a $v$, do grau de saída, que conta quantas partem de $v$. Um laço, do inglês self-loop, é uma aresta $(v, v)$ que conecta um vértice a si mesmo; por convenção, um laço contribui com $2$ para o grau em grafos não direcionados, para manter a consistência com o resultado a seguir.

O grau conecta a estrutura local de cada vértice à estrutura global do grafo, e essa ponte tem nome.

Teorema do aperto de mão. Em qualquer grafo não direcionado $G = (V, E)$, a soma dos graus de todos os vértices é igual ao dobro do número de arestas:

\[\sum_{v \in V} \deg(v) = 2 \vert E \vert\]

A demonstração cabe em uma frase: cada aresta ${u, v}$ tem exatamente duas pontas, uma incidente a $u$ e outra a $v$, e portanto contribui com exatamente $2$ para a soma total dos graus. Somar os graus é contar pontas de arestas, e cada aresta tem duas. A intuitiva leitora pode pensar numa festa em que cada aperto de mão envolve exatamente duas pessoas: o número total de mãos apertadas é sempre o dobro do número de apertos. Um corolário imediato e útil: o número de vértices de grau ímpar é sempre par, porque uma soma par não pode ter uma quantidade ímpar de parcelas ímpares.

O teorema não é ornamento. Ele fornece um teste de sanidade barato para dados que representem um grafo não direcionado: se a soma dos graus for ímpar, os dados estão corrompidos, porque nenhum grafo não direcionado produz soma de graus ímpar. Vamos verificá-lo no exemplo que nos acompanhará. Considere o grafo-ciclo de quatro vértices, no qual cada vértice tem exatamente grau $2$:

O ciclo tem quatro arestas, e a conta fecha.

2.3 Caminhos e ciclos

Dois últimos objetos completam o necessário. Um caminho é uma sequência de vértices na qual cada par consecutivo é adjacente; seu comprimento é o número de arestas percorridas. Um ciclo é um caminho que começa e termina no mesmo vértice sem repetir arestas nem vértices intermediários. O grafo que usaremos em todos os exemplos é precisamente um ciclo não direcionado de quatro vértices, $v_1!-!v_2!-!v_3!-!v_4!-!v_1$, em que cada pessoa conhece exatamente duas outras. É pequeno o bastante para caber num cálculo manual e estruturado o bastante para que a propagação de mensagens tenha o que propagar.

Antes de mergulhar nas matrizes, vale manipular esses conceitos com as mãos. O laboratório a seguir permite construir um grafo, adicionar e remover arestas, e observar a adjacência, o grau e o Laplaciano se recalcularem ao vivo. Sugiro à leitora que verifique o teorema do aperto de mão diretamente: some a coluna de graus e compare com o dobro do número de arestas.

3. Representando grafos com matrizes

Para que um computador, e também a esforçada leitora, aplique algoritmos a grafos, precisamos representá-los numericamente. Três matrizes bastam para tudo que faremos, e uma quarta abrirá a porta para a teoria espectral.

3.1 A matriz de adjacência

Para um grafo com $N$ vértices, a matriz de adjacência $A$ é uma matriz $N \times N$ cuja entrada $A_{ij}$ descreve a conexão entre o vértice $i$ e o vértice $j$. Para grafos não ponderados, $A_{ij} = 1$ se existe aresta entre $i$ e $j$, e $A_{ij} = 0$ caso contrário. Para grafos ponderados, $A_{ij} = w_{ij}$ quando a aresta existe, e $0$ quando não. Se o grafo é não direcionado, a matriz é simétrica, isto é, $A_{ij} = A_{ji}$, porque a relação entre $i$ e $j$ é a mesma que entre $j$ e $i$.

Para o nosso grafo-ciclo, com $V = {v_1, v_2, v_3, v_4}$ e arestas ${v_1, v_2}$, ${v_2, v_3}$, ${v_3, v_4}$, ${v_4, v_1}$, a matriz de adjacência é:

Cada linha lista os vizinhos de um vértice: a linha $1$ tem $1$ nas colunas $2$ e $4$, indicando que $v_1$ conecta-se a $v_2$ e $v_4$; a linha $2$ conecta $v_2$ a $v_1$ e $v_3$; e assim por diante. A matriz é simétrica, como manda um grafo não direcionado. A leitora atenta observa que a matriz de adjacência é a estrutura que diz, diretamente, de onde cada vértice pode receber informação. É por isso que ela estará no centro da regra de propagação da GCN.

3.2 A matriz de grau

A matriz de grau $D$ é uma matriz diagonal $N \times N$ na qual cada elemento diagonal $D_{ii}$ é o grau do vértice $i$, e todos os elementos fora da diagonal são zero. Para grafos não ponderados e sem laços, $D_{ii} = \sum_{j} A_{ij}$: o grau de um vértice é a soma da sua linha na matriz de adjacência. Essa identidade é local; o teorema do aperto de mão aparece quando somamos essas quantidades sobre todos os vértices.

No grafo-ciclo, cada vértice tem grau $2$, e somar as linhas de $A$ confirma: $\deg(v_1) = 0 + 1 + 0 + 1 = 2$, e o mesmo para os demais. Logo:

A matriz de grau parece trivial, pois é apenas uma diagonal, mas seu papel é enorme: ela fornecerá os fatores de normalização que impedem vértices muito conectados de dominar a agregação, como veremos na Seção 6.

3.3 A matriz de características

Um grafo sem atributos nos vértices é apenas topologia. Na prática, cada vértice carrega informação. A matriz de características $X$, ou $H$ quando falamos das representações internas da rede, é uma matriz $N \times F$, na qual $N$ é o número de vértices e $F$ é o número de características por vértice. A linha $i$ dessa matriz, denotada $X_i$, é o vetor de características do vértice $i$: o perfil de um usuário, as propriedades de um átomo, ou mesmo atributos estruturais como o próprio grau.

Para o grafo-ciclo, atribuímos $F = 2$ características a cada vértice. Pense nelas como energia e sociabilidade de cada pessoa da rede:

Aqui reservamos $X$, ou equivalentemente $H^{(0)}$, para as características de entrada, os atributos originais dos vértices, e $H^{(l)}$ para as representações ocultas, isto é, os vetores produzidos pela camada $l$ da rede, do inglês hidden representations. A distinção importa: a rede começa em $H^{(0)} = X$ e, a cada camada, transforma essas características incorporando informação da vizinhança, produzindo $H^{(1)}, H^{(2)}, \dots$ que codificam padrões cada vez mais abrangentes. O índice sobrescrito $(l)$ marca a camada, uma convenção que carregaremos até o fim.

3.4 O Laplaciano do grafo

Uma quarta matriz não será usada nos cálculos manuais, mas é a raiz teórica de toda a família GCN, e por isso merece definição. O Laplaciano do grafo é $L = D - A$: a matriz de grau menos a matriz de adjacência. Sua versão simetricamente normalizada,

é o objeto cujos autovetores definem a transformada de Fourier em grafos, e é a manipulação dessa expressão que dá origem à regra de propagação da GCN. Guardemos a fórmula; ela reaparecerá, disfarçada, na Seção 6. A tabela a seguir consolida a notação que usaremos daqui em diante.

Tabela 1: Notação de grafos e GNNs

A escolha da representação não é neutra. A matriz de adjacência diz como a informação flui entre vizinhos; a matriz de grau fornece a normalização que estabiliza o aprendizado; a matriz de características define o ponto de partida. Embora a notação use uma matriz $N \times N$, implementações reais armazenam grafos esparsos em espaço proporcional a $N + M$, por exemplo com listas de adjacência ou formatos comprimidos. O desafio de processar vizinhanças enormes e treinar por minilotes é o que empurra a pesquisa em direção a métodos mais escaláveis, como a GraphSAGE da Seção 10.

4. Por que redes tradicionais falham em grafos

Antes de construir a arquitetura certa, é instrutivo entender por que as arquiteturas erradas não servem. Aplicar diretamente uma CNN, de Convolutional Neural Network (rede neural convolucional), ou uma RNN, de Recurrent Neural Network (rede neural recorrente), a um grafo esbarra em obstáculos que não são de engenharia, mas de princípio.

O primeiro é a estrutura irregular. Uma CNN pressupõe uma grade regular: excetuadas as bordas ou consideradas as condições de preenchimento, cada pixel tem quatro ou oito vizinhos nas mesmas posições relativas, acima, abaixo, à esquerda e à direita. Uma RNN pressupõe uma sequência ordenada: há um antes e um depois bem definidos. Um grafo não oferece nenhuma das duas coisas. Um vértice pode ter dois vizinhos ou dois milhões, e não existe “esquerda” nem “próximo” canônicos. O filtro convolucional de tamanho fixo simplesmente não tem onde se apoiar.

O segundo obstáculo é mais profundo e define o campo inteiro: a invariância à permutação. A ordem em que numeramos os vértices numa matriz de adjacência é arbitrária. Se permutarmos os rótulos dos vértices, trocando quem é $v_1$ e quem é $v_3$, as matrizes $A$ e $X$ mudam, com linhas e colunas reordenadas, mas o grafo subjacente é exatamente o mesmo, e a resposta correta para qualquer pergunta sobre ele deve ser a mesma. Formalmente, para qualquer matriz de permutação $P$, uma função $f$ que classifica o grafo inteiro precisa satisfazer

isto é, ser invariante à permutação; e uma função que produz uma saída por vértice, como a classificação de vértices, precisa satisfazer $f(PAP^\top, PX) = P f(A, X)$, ou seja, ser equivariante à permutação. A saída permuta junto com a entrada, mas o conteúdo não muda. Uma CNN e uma RNN violam isso de saída, porque ambas atribuem significado à posição. Uma GNN precisa ser cega à numeração.

Esse requisito não é uma restrição incômoda; é a bússola de projeto. Ele dita quais operações são permitidas. Para agregar informação de um conjunto de vizinhos sem depender da ordem em que eles aparecem, usamos uma função que não veja ordem alguma. Soma, média e máximo são as escolhas mais comuns, mas não as únicas: composições aprendidas dessas operações e somas ponderadas por atenção também podem ser invariantes à permutação. Somar ${a, b, c}$ dá o mesmo que somar ${c, a, b}$, e essa cegueira à ordem é o princípio compartilhado pelas agregações de uma GNN. A invariância à permutação é o que separa uma GNN de qualquer outra rede, e a próxima seção mostra como ela se materializa.

Some-se a isso a escala. Grafos reais têm milhões ou bilhões de vértices, o que torna proibitivo manipular $A$ como matriz densa. Há também a dinâmica, pois vértices e arestas aparecem e somem, desafiando modelos treinados sobre um grafo fixo. A propagação de mensagens resolve o problema estrutural e respeita a permutação dos vértices; escala e dinâmica exigem estratégias adicionais de armazenamento esparso, amostragem e inferência indutiva.

5. O coração das GNNs: propagação de mensagens

Imagine uma conversa numa festa. Cada pessoa escuta seus vizinhos imediatos, processa o que ouviu e forma uma nova opinião. Repita a rodada algumas vezes: pessoas que nunca se falaram diretamente passam a se influenciar, porque a informação atravessa a rede de vizinho em vizinho. Esse é, sem exagero de metáfora, o princípio de toda GNN. Chamamos esse mecanismo de propagação de mensagens, do inglês message passing, e ele se decompõe em dois passos que se repetem a cada camada.

O primeiro passo é a agregação: cada vértice coleta as representações de seus vizinhos e as combina numa única mensagem, usando uma função invariante à permutação, como soma, média ou máximo, pelas razões da seção anterior. O segundo passo é a atualização: cada vértice combina a mensagem agregada com sua própria representação atual para produzir sua nova representação. Em uma fórmula que engloba praticamente toda a família de GNNs:

Nessa expressão, $h_i^{(l)}$ é o vetor de características do vértice $i$ na camada $l$, correspondente à $i$-ésima linha de $H^{(l)}$, e $\mathcal{N}(i)$ é a vizinhança de $i$, definida na Seção 2.1. A função AGREGA recebe o conjunto das representações dos vizinhos e o comprime em um único vetor; a função ATUALIZA mistura esse vetor com a representação do próprio vértice.

Uma consequência da estrutura em camadas merece destaque, porque será a origem de um problema na Seção 12. Após uma camada, cada vértice conhece apenas seus vizinhos diretos, a distância $1$. Após duas camadas, conhece os vizinhos dos vizinhos, a distância $2$, porque a mensagem que um vizinho lhe entrega já contém a informação que ele próprio agregou dos seus vizinhos. Em geral, $l$ camadas dão a cada vértice acesso à sua vizinhança de raio $l$. Empilhar camadas é aumentar o horizonte de percepção de cada vértice, o que é bom até deixar de ser. As diferentes arquiteturas de GNN são, no fundo, escolhas diferentes para AGREGA e ATUALIZA. A GCN faz a escolha mais simples e elegante, e é por ela que começamos.

6. GCN: a arquitetura fundamental

A GCN de Kipf e Welling resolve a propagação de mensagens com uma única expressão de álgebra linear que processa todos os vértices de uma vez. A regra de propagação de uma camada é:

À primeira vista, um amontoado de símbolos. Vamos desmontá-lo peça por peça, porque cada fator resolve um problema concreto, e a atenta leitora tem o direito de exigir que nenhum apareça por decreto.

6.1 O termo $H^{(l)} W^{(l)}$: transformar antes de misturar

O fator mais à direita é $H^{(l)} W^{(l)}$. Aqui $H^{(l)}$ é a matriz $N \times F_l$ das representações atuais, e $W^{(l)}$ é uma matriz de pesos $F_l \times F_{l+1}$, os parâmetros treináveis que a rede de fato aprende. O produto $H^{(l)} W^{(l)}$ é uma transformação linear que projeta cada vetor de características de $F_l$ para $F_{l+1}$ dimensões, exatamente como faria uma camada densa comum. Este é o único lugar onde moram os parâmetros aprendíveis da camada; todo o resto da fórmula é estrutura fixa do grafo. É útil pensar em $W^{(l)}$ como “o que aprender de cada característica” e no restante como “de quem receber”.

6.2 O termo $\tilde{A}$: incluir a si mesmo

Se agregássemos usando a matriz de adjacência $A$ crua, cada vértice receberia informação de seus vizinhos e nenhuma contribuição direta de si mesmo, porque a diagonal de $A$ é zero. Após algumas camadas, sua representação original poderia ficar diluída na dos vizinhos. A correção é adicionar laços a todos os vértices:

na qual $I_N$ é a matriz identidade $N \times N$. A adjacência com laços $\tilde{A}$ tem $1$ na diagonal, de modo que, na agregação, cada vértice passa a incluir diretamente a própria representação junto com a dos vizinhos.

6.3 O termo $\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$: normalizar pela popularidade

Resta o problema da escala. Um vértice com mil vizinhos receberia uma mensagem agregada muito maior que a de um vértice com um vizinho, e essa disparidade poderia desestabilizar o treinamento conforme a popularidade do vértice. A solução é normalizar pela matriz diagonal de somas de linha de $\tilde{A}$, que chamamos $\tilde{D}$, com $\tilde{D}{ii} = \sum_j \tilde{A}{ij}$. Essa quantidade é o grau usado pelo operador da GCN, no qual a entrada diagonal acrescentada por $I_N$ conta uma vez; ela não deve ser confundida com o grau combinatório da Seção 2.2, no qual um laço de um grafo não direcionado contribui com $2$.

A escolha ingênua seria $\tilde{D}^{-1}\tilde{A}$, que faz cada linha somar $1$ e produz uma média simples dos vizinhos. A GCN usa algo mais fino, a normalização simétrica $\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$, cujo elemento $(i, j)$ vale

na qual $\tilde{d}_i$ e $\tilde{d}_j$ são os graus, com laço, de $i$ e $j$. Cada conexão é ponderada pela raiz dos dois graus envolvidos: uma aresta entre dois vértices populares pesa menos que uma aresta entre dois vértices obscuros, o que equilibra a influência independentemente da popularidade. A leitora que comparou esta expressão com o Laplaciano normalizado $L^{\text{sym}} = I - D^{-1/2}AD^{-1/2}$ da Seção 3.4 percebeu que não é coincidência: a regra da GCN é, essencialmente, uma propagação baseada no Laplaciano do grafo com laços, e daí vem toda a sua fundamentação espectral. Por fim, $\sigma(\cdot)$ é uma função de ativação não linear, tipicamente a ReLU, de rectified linear unit (unidade linear retificada), $\sigma(x) = \max(0, x)$, sem a qual empilhar camadas colapsaria numa única transformação linear.

Reunindo tudo: a camada GCN transforma as características com $W^{(l)}$, agrega cada vértice com seus vizinhos e consigo mesmo via $\tilde{A}$, pondera essa agregação pela popularidade via $\tilde{D}^{-1/2}(\cdot)\tilde{D}^{-1/2}$, e aplica uma não linearidade. Nada foi inventado; cada símbolo responde a uma necessidade. Passemos da fórmula ao número.

7. Uma camada GCN calculada à mão

Vamos calcular uma camada inteira sobre o grafo-ciclo de quatro vértices, reutilizando a matriz de adjacência e as características $H^{(0)}$ da Seção 3. Os pesos, que numa rede real seriam aprendidos, aqui são fixados para produzir números limpos:

Passo 1: adicionar laços. Somamos a identidade à adjacência:

Passo 2: somas de linha com laço. Somando cada linha de $\tilde{A}$, todo vértice tem valor de normalização $\tilde{d}_i = 3$ (dois vizinhos mais a entrada diagonal), logo $\tilde{D} = 3 I_4$.

Passo 3: normalização simétrica. Como todos os valores de normalização valem $3$, temos $\tilde{D}^{-1/2} = \tfrac{1}{\sqrt{3}} I_4$, e portanto $\hat{A} = \tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2} = \tfrac{1}{3}\tilde{A}$:

Neste grafo regular, a normalização simétrica coincide com a média simples, porque todos os graus são iguais; em um grafo irregular, as duas divergem, e é aí que a normalização simétrica mostra seu valor.

Passo 4: propagar. Multiplicamos $\hat{A} H^{(0)}$, o que faz cada vértice tornar-se a média de si mesmo e dos dois vizinhos:

A título de conferência, a primeira linha é $\tfrac{1}{3}(h_1 + h_2 + h_4) = \tfrac{1}{3}([1{,}0, 0{,}5] + [0{,}8, 0{,}2] + [0{,}6, 0{,}1]) = [0{,}800, 0{,}267]$, exatamente como aparece.

Passo 5: transformar. Multiplicamos pela matriz de pesos, $(\hat{A} H^{(0)}) W^{(0)}$:

Passo 6: ativar. Aplicamos a ReLU. Como todos os valores são positivos, ela não altera nada, e a saída da camada é:

Cada vértice possui agora uma representação que codifica tanto suas características originais quanto as de sua vizinhança imediata. Uma segunda camada estenderia esse alcance para a vizinhança de raio $2$; neste grafo de quatro vértices, isso já cobre o grafo inteiro.

O laboratório a seguir reproduz exatamente esses seis passos. A leitora pode alterar as características de entrada e os pesos e ver cada matriz intermediária, $\tilde{A}$, $\hat{A}$, a propagação e a transformação, se recalcular. Sugiro começar reproduzindo os números acima e depois zerar uma característica para observar como a informação de um vértice se espalha pelos vizinhos em uma única camada.

8. A mesma camada em C++

O cálculo da Seção 7 traduz-se diretamente em código. A implementação a seguir, em C++23, executa os seis passos na ordem em que os deduzimos e reproduz $H^{(1)}$ ao milésimo. Não usamos nenhuma biblioteca externa: o objetivo é que cada operação da fórmula fique visível, não que seja rápida. Compilamos com g++ -O3 -std=c++23 -o gcn gcn_layer.cpp.

// gcn_layer.cpp, uma camada GCN em C++23
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <string_view>
#include <vector>

using Matrix = std::vector<std::vector<double>>;

// Produto matricial C = A * B, com A de m x k e B de k x n.
static Matrix matmul(const Matrix& A, const Matrix& B) {
    const std::size_t m = A.size(), k = B.size(), n = B[0].size();
    Matrix C(m, std::vector<double>(n, 0.0));
    for (std::size_t i = 0; i < m; ++i)
        for (std::size_t p = 0; p < k; ++p)
            for (std::size_t j = 0; j < n; ++j)
                C[i][j] += A[i][p] * B[p][j];
    return C;
}

// Uma camada GCN: sigma( D^{-1/2} A~ D^{-1/2} H W ), com A~ = A + I.
static Matrix gcn_layer(const Matrix& A, const Matrix& H, const Matrix& W) {
    const std::size_t N = A.size();

    // Passo 1: A~ = A + I.
    Matrix At = A;
    for (std::size_t i = 0; i < N; ++i) At[i][i] += 1.0;

    // Passos 2 e 3: graus com laco e D^{-1/2}.
    std::vector<double> dinv(N);
    for (std::size_t i = 0; i < N; ++i) {
        double d = 0.0;
        for (std::size_t j = 0; j < N; ++j) d += At[i][j];
        dinv[i] = 1.0 / std::sqrt(d);
    }

    // Passo 3: A_hat = D^{-1/2} A~ D^{-1/2}.
    Matrix Ah(N, std::vector<double>(N, 0.0));
    for (std::size_t i = 0; i < N; ++i)
        for (std::size_t j = 0; j < N; ++j)
            Ah[i][j] = dinv[i] * At[i][j] * dinv[j];

    // Passos 4 e 5: propagacao e transformacao linear.
    Matrix out = matmul(matmul(Ah, H), W);

    // Passo 6: ativacao ReLU.
    for (auto& row : out)
        for (double& x : row) x = std::max(0.0, x);
    return out;
}

static void print_matrix(std::string_view name, const Matrix& M) {
    std::cout << name << " =\n" << std::fixed << std::setprecision(3);
    for (const auto& row : M) {
        for (double x : row) std::cout << std::setw(8) << x;
        std::cout << '\n';
    }
    std::cout << '\n';
}

int main() {
    Matrix A = { {0, 1, 0, 1}, {1, 0, 1, 0},
                 {0, 1, 0, 1}, {1, 0, 1, 0} };
    Matrix H = { {1.0, 0.5}, {0.8, 0.2},
                 {0.3, 0.7}, {0.6, 0.1} };
    Matrix W = { {0.5, 0.3}, {0.1, 0.4} };

    Matrix H1 = gcn_layer(A, H, W);
    print_matrix("H^(1)", H1);
    return 0;
}

A saída reproduz, ao milésimo, a matriz $H^{(1)}$ que calculamos à mão:

H^(1) =
   0.427   0.347
   0.397   0.397
   0.317   0.303
   0.360   0.363

A validação por comparação com o cálculo manual não é zelo excessivo: é uma forma barata de confirmar que a ordem das multiplicações, primeiro $\hat{A}H$ e depois $\cdot\, W$, foi respeitada e que a normalização não trocou linhas por colunas. Empilhar camadas é encadear chamadas de gcn_layer, alimentando a saída de uma como $H$ da próxima, com uma matriz $W$ nova por camada.

9. GAT: quando nem todo vizinho pesa igual

A GCN comete uma simplificação que às vezes atrapalha: ela pondera os vizinhos apenas por seus graus, fixados pela estrutura do grafo, e não pelo conteúdo. Todo vizinho de mesmo grau contribui igualmente, independentemente de ser relevante ou ruído. A GAT, de Veličković e colaboradores, substitui esse peso fixo por um peso aprendido que depende das características dos dois vértices. Trata-se de um mecanismo de atenção da mesma família conceitual usada nos Transformers, mas aplicado à vizinhança do grafo por uma função aditiva, não pela atenção de produto escalar escalonado.

A ideia é calcular, para cada aresta $(i, j)$, um coeficiente de atenção $\alpha_{ij}$ que diz quanto o vértice $i$ deve ouvir o vértice $j$. Mantemos a convenção das seções anteriores, na qual cada $h_i$ é um vetor linha, e projetamos as características com uma matriz de pesos $W$, obtendo $z_i = h_i W$. Para incluir o próprio vértice, definimos $\tilde{\mathcal{N}}(i) = \mathcal{N}(i) \cup {i}$. Depois computamos um escore não normalizado para cada par $(i, j)$ com $j \in \tilde{\mathcal{N}}(i)$:

na qual $[z_i \Vert z_j]$ é a concatenação dos dois vetores projetados, $\mathbf{a}$ é um vetor de pesos de atenção também aprendido, e a LeakyReLU, de leaky rectified linear unit (unidade linear retificada com vazamento), é $\text{LeakyReLU}(x) = x$ se $x \ge 0$ e $\alpha x$ com $\alpha = 0{,}2$ caso contrário. Os escores são então normalizados por uma softmax sobre a vizinhança, para que os pesos de cada vértice somem $1$:

Por fim, a nova representação de $i$ é a soma dos vizinhos projetados, ponderada pela atenção, seguida de uma não linearidade:

Vale ver um número. Tomemos o vértice $v_1$ do grafo-ciclo, com vizinhos $v_2$ e $v_4$ além de si mesmo, usando as características $H^{(0)}$ e a matriz $W^{(0)}$ da Seção 7, e escolhendo o vetor de atenção $\mathbf{a} = [1{,}0,\ 0{,}5,\ 1{,}0,\ 0{,}5]^\top$. As projeções $z_i = h_i W$ dos três vértices envolvidos são $z_1 = [0{,}55,\ 0{,}50]$, $z_2 = [0{,}42,\ 0{,}32]$ e $z_4 = [0{,}31,\ 0{,}22]$. Os escores antes da softmax resultam em $e_{11} = 1{,}60$, $e_{12} = 1{,}38$ e $e_{14} = 1{,}22$, e a softmax os transforma nos pesos

que somam $1$, como devem. O vértice $v_1$ decidiu, a partir do conteúdo, dar mais atenção a si mesmo do que aos vizinhos, e mais ao vizinho $v_2$ do que ao $v_4$, uma distinção que a GCN, presa aos graus iguais, jamais faria. A representação resultante, antes da ativação, é $h_1’ = [0{,}4420,\ 0{,}3649]$. Na prática, a GAT usa várias cabeças de atenção em paralelo e concatena ou promedia suas saídas para estabilizar o aprendizado, como também ocorre em arquiteturas Transformer.

10. GraphSAGE: amostrar e agregar

Na forma matricial e em treinamento por lote completo, GCN e GAT podem exigir que uma grande porção do grafo participe de cada atualização, o que é inviável quando há bilhões de vértices. Isso não torna as arquiteturas inerentemente dependentes do grafo inteiro nem necessariamente transdutivas; a própria GAT também pode operar em cenários indutivos. A GraphSAGE, de Hamilton, Ying e Leskovec, cujo nome vem de SAmple and aggreGatE (amostrar e agregar), torna explícitas duas escolhas úteis para escala e generalização.

A primeira é a amostragem: em vez de agregar todos os vizinhos de um vértice, a GraphSAGE amostra um número fixo deles a cada camada, digamos, $25$ vizinhos, mesmo que o vértice tenha milhões. Para profundidade e quantidade amostrada por camada fixas, isso torna o custo independente do grau original do vértice e viabiliza o treinamento por minilotes em grafos gigantes; o total visitado ainda cresce com o produto das quantidades amostradas nas camadas. A segunda é a separação explícita entre a representação própria e a agregada. Mantendo os vetores como linhas, uma camada GraphSAGE com agregador de média calcula:

na qual $\mathcal{S}(i)$ é o conjunto amostrado de vizinhos, e $W_{\text{self}}$ e $W_{\text{neigh}}$ são duas matrizes de pesos distintas: uma para o que o vértice já sabe, outra para o que a vizinhança lhe traz. Manter os dois pesos separados dá à rede a liberdade de tratar a informação própria e a alheia de formas diferentes, o que a GCN, que soma tudo com o mesmo $W$, não permite.

Um número torna a fórmula concreta. Para o vértice $v_1$, com vizinhos $v_2$ e $v_4$, a média das características vizinhas é $\text{média}{[0{,}8, 0{,}2], [0{,}6, 0{,}1]} = [0{,}70,\ 0{,}15]$. Usando $W_{\text{self}} = W^{(0)}$ da Seção 7 e $W_{\text{neigh}} = \begin{bmatrix} 0{,}2 & 0{,}6 \ 0{,}7 & 0{,}1 \end{bmatrix}$, a representação antes da ativação é $h_1’ = h_1 W_{\text{self}} + [0{,}70, 0{,}15] W_{\text{neigh}} = [0{,}795,\ 0{,}935]$. O agregador de média é apenas um entre vários: a GraphSAGE também admite um agregador por pooling, que transforma cada vizinho e depois toma o máximo elemento a elemento. Essa operação é invariante à permutação, como exige a Seção 4. A capacidade de generalizar para vértices nunca vistos durante o treino, chamada de inferência indutiva, faz da GraphSAGE uma escolha comum para grafos de produção que crescem continuamente.

11. Treinamento: das representações às tarefas

Uma GNN não existe para produzir matrizes $H^{(L)}$ bonitas; ela existe para resolver tarefas, e a tarefa determina o que colocamos no topo da rede. Três famílias cobrem quase tudo.

Na classificação de vértices, como separar um usuário legítimo de um spammer ou classificar um artigo científico por área, aplicamos uma camada final com softmax sobre a representação de cada vértice, $\text{softmax}(H^{(L)} W_{\text{class}})$, obtendo uma distribuição de probabilidade por classe para cada vértice. Na classificação de grafos, como decidir se uma molécula é tóxica, precisamos de um único vetor para o grafo inteiro, obtido por uma operação de pooling global que agrega as representações de todos os vértices, tipicamente por soma ou média, respeitando a invariância à permutação da Seção 4; sobre esse vetor aplica-se então um classificador. Na predição de arestas, como sugerir amizades ou recomendar produtos, pontuamos um par de vértices pela similaridade de suas representações, por exemplo $\text{score}(h_i, h_j) = h_i^\top h_j$, e usamos um limiar para decidir se a aresta deve existir.

O laço de treinamento é o das redes neurais de sempre. A estrutura do grafo determina as dependências da passagem para a frente e, por consequência, o caminho pelo qual os gradientes retornam durante a retropropagação. Propagamos os dados pela pilha de camadas GNN até obter as representações e, delas, as predições; calculamos uma função de perda comparando as predições com os rótulos verdadeiros, tipicamente entropia cruzada para classificação; obtemos os gradientes da perda em relação a todos os pesos $W^{(l)}$ por retropropagação; atualizamos os pesos com um otimizador como Adam ou SGD, de stochastic gradient descent (descida de gradiente estocástica); e repetimos até a convergência. Os parâmetros ajustados incluem as matrizes de pesos das camadas e do classificador e, na GAT, os vetores de atenção. A estrutura do grafo permanece como dado fixo, não como parâmetro.

12. O limite incômodo: over-smoothing

Fecharemos com o problema que impede a solução ingênua de “basta empilhar mais camadas”. Vimos na Seção 5 que $l$ camadas dão a cada vértice acesso à sua vizinhança de raio $l$. Seria natural supor que redes bem fundas, com dezenas de camadas, capturariam estruturas ricas. Em muitas GNNs baseadas em difusão, porém, camadas sucessivas tornam as representações dos vértices cada vez mais semelhantes. Esse fenômeno é o over-smoothing, que traduzimos livremente por suavização excessiva: a rede perde progressivamente a capacidade de distinguir um vértice do outro.

A causa é a própria operação que torna a GCN elegante. Cada camada substitui a representação de um vértice por uma média ponderada de sua vizinhança. Aplicar repetidamente uma média é um processo de difusão, e a difusão, por natureza, homogeneíza: repetida o bastante, ela leva tudo ao mesmo valor de equilíbrio. No nosso grafo-ciclo, isso é visível e mensurável. Definindo a dispersão de uma característica como a diferença entre seu valor máximo e mínimo entre os quatro vértices, e aplicando $\hat{A}$ repetidamente, a dispersão da primeira característica evolui assim:

A cada camada, a dispersão encolhe por um fator de aproximadamente $3$. Depois de seis camadas, os quatro vértices, que começaram nitidamente distintos, tornaram-se praticamente indistinguíveis, e suas representações convergem para a média global $[0{,}675,\ 0{,}375]$. Isso ocorre porque o sinal constante sobre os quatro vértices é o autovetor dominante de $\hat{A}$, com autovalor $1$; a média global fornece os dois coeficientes desse sinal limite, um para cada característica. A rede profunda quase não distingue mais a estrutura local; vê uma sopa uniforme.

O laboratório a seguir torna o colapso visível. A leitora pode empilhar camadas uma a uma e observar os quatro pontos, inicialmente espalhados, convergirem para um único ponto. Sugiro empurrar até dez camadas para ver o desastre completo, e depois notar que o estrago já está praticamente feito na quinta.

As soluções conhecidas atacam a difusão sem abandoná-la. As conexões residuais, do inglês skip connections, somam a entrada de uma camada à sua saída, preservando um traço da representação original que a média não consegue apagar. É a mesma ideia que permitiu treinar redes convolucionais com centenas de camadas. Camadas de normalização projetadas para grafos podem preservar a dispersão das representações a cada passo. A própria GAT, da Seção 9, também pode mitigar o problema quando a atenção aprende a reduzir a influência de certos vizinhos. Nenhuma dessas estratégias garante eliminar o over-smoothing; elas apenas empurram o limite de profundidade um pouco mais para longe.

13. Conclusão

Percorremos o caminho do dado relacional até uma rede que aprende sobre ele. Vimos que grafos são a estrutura que formaliza “coisas conectadas a coisas”, que a invariância à permutação é o princípio que força qualquer arquitetura de grafos a agregar vizinhos com funções cegas à ordem, e que a propagação de mensagens, composta por agregar e atualizar, é o mecanismo que dela decorre. Deduzimos a GCN símbolo por símbolo, calculamos uma de suas camadas à mão e em C++, e vimos a GAT trocar pesos fixos por atenção aprendida e a GraphSAGE trocar o grafo inteiro por vizinhanças amostradas. Fechamos com o over-smoothing, o lembrete de que a operação que dá poder à GCN é também a que limita sua profundidade.

Uma ideia atravessa tudo isso e vale carregar adiante: em uma GNN, a informação não está apenas nos vértices, mas no padrão das conexões; aprender sobre um grafo é aprender a propagar informação pela sua estrutura sem jamais depender de como seus vértices foram numerados. As arquiteturas avançadas que a leitora encontrará a seguir, como Graph Transformers, GNNs heterogêneas e redes sobre grafos dinâmicos, são todas variações sobre esse mesmo tema.

Referências

BARABÁSI, Albert-László. Linked: a nova ciência dos networks: como tudo está conectado a tudo e o que isso significa para os negócios, relações sociais e ciências. Tradução de Jonas Pereira dos Santos. São Paulo: Leopardo, 2009.

BRONSTEIN, M. M.; BRUNA, J.; COHEN, T.; VELIČKOVIĆ, P. Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges. 2021. Disponível em: https://arxiv.org/abs/2104.13478.

GILMER, J.; SCHOENHOLZ, S. S.; RILEY, P. F.; VINYALS, O.; DAHL, G. E. Neural Message Passing for Quantum Chemistry. Proceedings of the 34th International Conference on Machine Learning, PMLR, v. 70, p. 1263–1272, 2017. Disponível em: https://arxiv.org/abs/1704.01212.

HAMILTON, W. L.; YING, R.; LESKOVEC, J. Inductive Representation Learning on Large Graphs. Advances in Neural Information Processing Systems, v. 30, 2017. Disponível em: https://arxiv.org/abs/1706.02216.

KIPF, T. N.; WELLING, M. Semi-Supervised Classification with Graph Convolutional Networks. International Conference on Learning Representations (ICLR), 2017. Disponível em: https://arxiv.org/abs/1609.02907.

LI, Q.; HAN, Z.; WU, X.-M. Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning. Proceedings of the AAAI Conference on Artificial Intelligence, v. 32, 2018. Disponível em: https://arxiv.org/abs/1801.07606.

SCARSELLI, F.; GORI, M.; TSOI, A. C.; HAGENBUCHNER, M.; MONFARDINI, G. The Graph Neural Network Model. IEEE Transactions on Neural Networks, v. 20, n. 1, p. 61–80, 2009. DOI: https://doi.org/10.1109/TNN.2008.2005605.

VELIČKOVIĆ, P.; CUCURULL, G.; CASANOVA, A.; ROMERO, A.; LIÒ, P.; BENGIO, Y. Graph Attention Networks. International Conference on Learning Representations (ICLR), 2018. Disponível em: https://arxiv.org/abs/1710.10903.

XU, K.; HU, W.; LESKOVEC, J.; JEGELKA, S. How Powerful Are Graph Neural Networks?. International Conference on Learning Representations (ICLR), 2019. Disponível em: https://arxiv.org/abs/1810.00826.