Rede Neural de Grafos

Redes neurais de grafos (GNNs) são uma classe de redes neurais artificiais projetadas para operar em dados estruturados como grafos, onde as entradas consistem em nós (vértices) e arestas (conexões) que podem não ter uma ordenação canônica. Diferentemente das redes neurais padrão, que assumem entradas ordenadas e de tamanho fixo, as GNNs são construídas para lidar com grafos de tamanhos e topologias variados, tornando-as adequadas para domínios como química molecular, análise de redes sociais e otimização combinatória. A inovação central das GNNs reside no uso de passagem de mensagens entre pares, onde cada nó atualiza iterativamente sua representação agregando informações de seus vizinhos, permitindo que a rede capture padrões estruturais locais e dependências.

As GNNs são tipicamente projetadas para serem equivariantes a permutações, o que significa que reordenar os nós no grafo de entrada resulta em uma reordenação correspondente das representações dos nós produzidas pela rede. Para tarefas de predição em nível de grafo, como prever uma propriedade de uma molécula inteira, as GNNs empregam uma função de leitura invariante a permutações que agrega as representações dos nós em uma única saída de tamanho fixo, garantindo que o resultado não seja afetado pela ordenação dos nós. Essa propriedade é essencial porque os grafos não têm uma ordem natural de nós, e a saída da rede deve ser consistente independentemente de como o grafo é representado.

Desenvolvimento Histórico

O conceito de GNNs emergiu de trabalhos anteriores sobre redes neurais para dados estruturados, com ideias fundamentais que remontam à década de 1990. Abordagens iniciais, como redes neurais recorrentes aplicadas a grafos acíclicos direcionados, lançaram as bases para o processamento de estruturas semelhantes a grafos. No entanto, a formulação moderna das GNNs, baseada em passagem de mensagens e equivariância a permutações, ganhou destaque na década de 2010 com o avanço do aprendizado profundo. Pesquisadores de instituições como MIT CSAIL e Stanford AI Lab contribuíram para o desenvolvimento de arquiteturas capazes de lidar com grafos arbitrários, levando ao estabelecimento das GNNs como um subcampo distinto dentro do aprendizado de máquina.

No final da década de 2010, as GNNs se tornaram uma ferramenta padrão no aprendizado profundo, com inúmeras variantes propostas para melhorar seu poder expressivo e escalabilidade. O artigo de posicionamento de 2022 "Weisfeiler and Leman Go Neural" e trabalhos semelhantes formalizaram a relação entre GNNs e testes de isomorfismo de grafos, esclarecendo suas limitações teóricas e inspirando pesquisas em arquiteturas mais poderosas.

Arquitetura

A arquitetura de uma GNN genérica implementa várias camadas fundamentais que trabalham juntas para processar entradas estruturadas como grafos. Essas camadas incluem camadas equivariantes a permutações, camadas de pooling local e camadas de pooling global, cada uma servindo a um propósito distinto na transformação da representação do grafo.

As camadas equivariantes a permutações são o núcleo das GNNs, implementadas por meio de passagem de mensagens entre pares de nós do grafo. Em uma camada de passagem de mensagens, cada nó atualiza sua representação agregando mensagens recebidas de seus vizinhos imediatos. Esse processo aumenta o campo receptivo da GNN em um salto por camada, permitindo que a rede incorpore informações de vizinhanças progressivamente maiores. A operação de passagem de mensagens pode ser formalmente expressa como uma função que recebe características dos nós, características dos vizinhos e características das arestas como entradas e produz uma representação atualizada do nó.

As camadas de pooling local reduzem o grafo por meio de subamostragem, diminuindo o número de nós enquanto preservam informações estruturais importantes. Isso é análogo às camadas de pooling em redes neurais convolucionais (CNNs) e ajuda a aumentar o campo receptivo da GNN. Exemplos comuns incluem pooling de k-vizinhos mais próximos, pooling top-k e pooling por autoatenção, cada um selecionando um subconjunto de nós a serem mantidos com base em diferentes critérios.

As camadas de pooling global, também conhecidas como camadas de leitura, fornecem uma representação de tamanho fixo de todo o grafo. Essas camadas devem ser invariantes a permutações, o que significa que qualquer permutação dos nós e arestas do grafo não altera a saída final. Operações de soma, média e máximo elemento a elemento são escolhas típicas para pooling global, agregando as representações dos nós em um único vetor que pode ser usado para predições em nível de grafo.

Camadas de Passagem de Mensagens

As camadas de passagem de mensagens são o componente definidor das GNNs, implementando transformações equivariantes a permutações por meio de um processo conhecido como redes neurais de passagem de mensagens (MPNNs). Dado um grafo G = (V, E) com conjunto de nós V e conjunto de arestas E, cada nó u em V tem características associadas x_u, e cada aresta (u, v) em E tem características e_uv. A vizinhança de um nó u, denotada N_u, consiste em todos os nós v tais que (u, v) é uma aresta em E.

Uma camada MPNN atualiza a representação de cada nó u usando uma função de passagem de mensagens. A camada calcula mensagens de cada vizinho v para u, onde a mensagem é uma função das características do nó de origem, características do nó de destino e características da aresta. Essas mensagens são agregadas usando uma operação invariante a permutações, como soma, média ou máximo, e então combinadas com as próprias características do nó por meio de uma função de atualização diferenciável, tipicamente uma rede neural. Esse processo pode ser repetido por várias camadas, permitindo que a informação se propague pelo grafo.

O design das funções de passagem de mensagens varia entre diferentes arquiteturas de GNN. Algumas usam transformações lineares simples, enquanto outras empregam mecanismos de atenção mais complexos ou unidades recorrentes com portas. A escolha da operação de agregação também afeta o poder expressivo da rede e sua capacidade de capturar diferentes tipos de informação estrutural.

Poder Expressivo e Limitações

As GNNs padrão de passagem de mensagens são, no máximo, tão expressivas quanto o teste de isomorfismo de grafos de Weisfeiler-Lehman, um algoritmo clássico para determinar se dois grafos são isomorfos. Isso significa que existem estruturas de grafos distintas que não podem ser distinguidas por GNNs padrão, pois elas podem produzir representações idênticas para grafos não isomorfos. Essa limitação surge da natureza local da passagem de mensagens, que depende da agregação de informações de vizinhos imediatos e pode falhar em capturar padrões estruturais globais.

Para superar essas limitações, pesquisadores propuseram GNNs mais poderosas que operam em geometrias de dimensões superiores, como complexos simpliciais ou hipergrafos, que podem codificar interações de ordem superior além das arestas entre pares. A partir de 2022, se futuras arquiteturas superarão completamente o primitivo de passagem de mensagens permanece uma questão de pesquisa em aberto, com trabalhos contínuos explorando paradigmas alternativos, como transformadores de grafos e redes neurais equivariantes.

Aplicações

As GNNs encontraram aplicações em uma ampla gama de domínios, aproveitando sua capacidade de processar dados estruturados como grafos. Em biologia molecular e química, as moléculas são representadas como grafos com nós para átomos e arestas para ligações químicas, frequentemente incluindo propriedades químicas conhecidas como características. Tarefas em nível de grafo incluem prever a eficácia de uma molécula para uma aplicação médica específica, como eliminar bactérias E. coli, ou estimar propriedades físicas e químicas, como solubilidade e toxicidade. Isso torna as GNNs ferramentas valiosas no design de fármacos e na ciência dos materiais.

No processamento de linguagem natural, as GNNs podem ser aplicadas a árvores de dependência sintática ou grafos de papéis semânticos, capturando relações entre palavras em uma frase. Elas também são usadas na análise de redes sociais para modelar interações entre usuários, detectar comunidades e prever links. Redes de citação, onde os nós representam artigos e as arestas representam citações, são outra aplicação comum, permitindo tarefas como classificação e recomendação de artigos.

As GNNs também são relevantes para a física, onde podem modelar interações entre partículas ou simular sistemas dinâmicos, e para problemas de otimização combinatória NP-difíceis, onde podem aprender heurísticas para tarefas como coloração de grafos ou problemas do caixeiro viajante. A versatilidade das GNNs levou à sua adoção tanto na pesquisa acadêmica quanto em aplicações industriais.

Relação com Outras Arquiteturas de Redes Neurais

No contexto mais amplo do aprendizado profundo geométrico, certas arquiteturas de redes neurais existentes podem ser interpretadas como GNNs operando em grafos adequadamente definidos. Uma camada de rede neural convolucional (CNN), comumente usada em visão computacional, pode ser considerada uma GNN aplicada a grafos cujos nós são pixels, com arestas conectando apenas pixels adjacentes. Essa perspectiva destaca os princípios compartilhados de conectividade local e agregação de características entre CNNs e GNNs.

Da mesma forma, uma camada de transformador, amplamente usada em processamento de linguagem natural e grandes modelos de linguagem, pode ser vista como uma GNN aplicada a grafos completos cujos nós são palavras ou tokens em um trecho de texto. Nessa interpretação, o mecanismo de atenção nos transformadores atua como uma forma de passagem de mensagens, onde cada token agrega informações de todos os outros tokens. Essa conexão inspirou pesquisas para unificar essas arquiteturas e aplicar insights das GNNs para melhorar modelos baseados em transformadores.

Bibliotecas e Ferramentas de Software

Várias bibliotecas de código aberto foram desenvolvidas para facilitar a implementação e implantação de GNNs. PyTorch Geometric, construída sobre o framework PyTorch, fornece um conjunto abrangente de ferramentas para processamento de dados de grafos e camadas de passagem de mensagens. TensorFlow GNN oferece funcionalidade semelhante dentro do ecossistema TensorFlow. A Deep Graph Library (DGL) é uma biblioteca agnóstica de framework que suporta múltiplos backends, incluindo PyTorch, TensorFlow e Apache MXNet. Para usuários do Google JAX, jraph fornece uma biblioteca leve para redes neurais de grafos. Na linguagem de programação Julia, GraphNeuralNetworks.jl e GeometricFlux.jl oferecem implementações de GNN construídas sobre o framework de aprendizado de máquina Flux.

Essas bibliotecas reduziram a barreira de entrada para pesquisadores e profissionais, permitindo prototipagem rápida e experimentação com várias arquiteturas de GNN. Elas incluem implementações de camadas padrão de passagem de mensagens, operações de pooling e utilitários para carregar e processar conjuntos de dados de grafos, tornando as GNNs acessíveis a um público amplo.

Direções Futuras

A pesquisa sobre GNNs continua a evoluir, com áreas ativas de investigação incluindo melhoria do poder expressivo, escalabilidade para grafos grandes e robustez a dados ruidosos ou incompletos. O desenvolvimento de transformadores de grafos, que combinam mecanismos de atenção com estrutura de grafos, representa uma direção promissora para capturar dependências de longo alcance. Além disso, há interesse crescente em aplicar GNNs a grafos dinâmicos, onde nós e arestas mudam ao longo do tempo, e a grafos heterogêneos com múltiplos tipos de nós e arestas.

A partir do início da década de 2020, as GNNs se tornaram um componente padrão do kit de ferramentas de aprendizado de máquina, com contribuições contínuas de instituições acadêmicas e laboratórios de pesquisa da indústria. A compreensão teórica de suas capacidades e limitações continua a se aprofundar, orientando o design de arquiteturas de próxima geração que possam enfrentar problemas cada vez mais complexos baseados em grafos.