🤖 machine learning

Universality and Approximation Rates of Graph Neural Networks with Random Features

Este artigo estabelece que redes neurais de grafos de passagem de mensagens com características de nós parcialmente aleatórias possuem capacidades de aproximação universal para funções invariantes e equivariantes à permutação em grafos direcionados de tamanho fixo, ao mesmo tempo em que deriva limites superiores teóricos em suas taxas de aproximação baseados na complexidade da rede.

Autores originais: Lukas Gonon, Thilo Meyer-Brandis, Niklas Weber

Publicado 2026-07-30

📖 6 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Lukas Gonon, Thilo Meyer-Brandis, Niklas Weber

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

O Enigma da Multidão de Formas Mutáveis

Imagine que você está tentando ensinar um computador a entender o mundo não como uma grade de pixels ou uma lista de palavras, mas como uma teia de conexões. Este é o reino das Redes Neurais de Grafos (GNNs), um ramo da inteligência artificial projetado para lidar com dados que se parecem com um mapa de amigos, moléculas ou rotas de tráfego. Nesses mapas, o mais importante não é apenas o que um item individual é, mas como ele se conecta aos seus vizinhos.

No entanto, há uma regra complicada que esses computadores devem seguir: a simetria. Se você tem um grupo de amigos e troca os nomes deles, o grupo continua sendo o mesmo grupo. Um bom IA de grafos não deveria se importar com quem está sentado na cadeira A ou na cadeira B; ele deve se importar apenas com o padrão de quem está conversando com quem. Isso é chamado de invariância por permutação (para o grupo todo) ou equivariância por permutação (para os indivíduos). O problema é que os modelos de IA padrão são péssimos nisso. Eles costem se confundir com a ordem em que os dados chegam, falhando em reconhecer que duas listas de nomes diferentes descrevem, na verdade, o mesmo círculo social.

Para corrigir isso, cientistas tentaram dar à IA "ruído aleatório" ou "IDs aleatórios" para ajudá-la a distinguir os nós, de forma semelhante a dar a cada pessoa em uma multidão um adesivo único temporário. Mas, até agora, não sabíamos totalmente se esse truque poderia tornar a IA inteligente o suficiente para aprender qualquer padrão possível, ou se havia limites para o quão bem ela poderia aprender regras complexas. Este artigo mergulha fundo nessa questão, perguntando: "Se dermos adesivos aleatórios a esses computadores que leem grafos, eles podem aprender a ser perfeitos ao entender qualquer estrutura de grafo?"

A Magia dos Adesivos Aleatórios

Os autores deste artigo, Lukas Gonon, Thilo Meyer-Brandis e Niklas Weber, propuseram-se a provar que um tipo específico de IA de grafos, chamado Rede Neural Permutação-Equivariante (PENN), torna-se incrivelmente poderosa quando você lhe fornece características de nós aleatórias. Pense em uma PENN como uma equipe de detetives tentando resolver um mistério em um mapa. Normalmente, se dois suspeitos parecem idênticos e têm os mesmos amigos, os detetives não conseguem distingui-los. Mas se você der a cada suspeito um adesivo aleatório e único (uma característica aleatória), os detetives podem finalmente distingui-los e resolver o caso.

A principal descoberta do artigo é uma garantia "universal". Os autores provaram matematicamente que, se você alimentar essas PENNs com adesivos aleatórios, elas podem aproximar qualquer função mensurável em um grafo de tamanho fixo com probabilidade arbitrariamente alta. Em termos simples: se você quer que a IA aprenda uma regra específica sobre uma rede (como prever se uma molécula é tóxica ou se uma rede financeira está em risco), e se você fornecer adesivos aleatórios suficientes, existe uma arquitetura PENN que pode aprender essa regra quase perfeitamente. Isso ocorre mesmo se a regra for desordenada ou complexa, e mesmo que os dados tenham muitos tipos diferentes de características anexadas aos nós e arestas.

O Quão Bom é "Bom o Suficiente"?

Mas o artigo não diz apenas "funciona"; ele diz o quão grande a IA precisa ser para realizar o trabalho. Os autores analisaram funções que são suaves e bem comportadas (matematicamente falando, " $k$ -vezes continuamente diferenciáveis", onde $k \ge 2$ ). Eles derivaram uma fórmula para as taxas de aproximação, que é basicamente um limite de velocidade sobre o quão rápido a IA pode aprender à medida que você a torna maior.

Eles descobriram que a profundidade da rede (o número de camadas) só precisa crescer logaritmicamente conforme você exige mais precisão. Isso é uma ótima notícia: se você quiser ser duas vezes mais preciso, não precisa dobrar o tamanho do cérebro; você só precisa de um pouco mais de profundidade. No entanto, o número de conexões (pesos não nulos) cresce polinomialmente conforme você exige mais precisão. Especificamente, a complexidade escala com uma potência de $1/\epsilon$ , onde $\epsilon$ é a sua margem de erro desejada. O artigo observa que esse poder depende da "suavidade" da regra que você está tentando aprender ( $k$ ) e do tamanho do grafo ( $N$ ). Essencialmente, para regras muito complexas e irregulares ou grafos muito grandes, você precisa de muito mais conexões, mas para regras suaves, a IA permanece eficiente.

O Truque da "Média" para Segurança

Uma das percepções mais lúdicas e práticas do artigo aborda um efeito colateral do uso de adesivos aleatórios. Como os adesivos são aleatórios, se você executar a IA uma vez, ela pode dar uma resposta ligeiramente diferente do que se você a executasse novamente com adesivos diferentes. Isso quebra a regra de simetria: a IA pode tratar o mesmo grupo de amigos de forma diferente apenas porque os adesivos mudaram.

Os autores sugerem uma correção inteligente: a média. Se você executar a IA muitas vezes com diferentes adesivos aleatórios e tirar a média dos resultados, a aleatoriedade se cancela e a IA torna-se perfeitamente simétrica novamente. Eles provaram que essa versão de "média" ainda retém o superpoder de ser capaz de aprender qualquer regra. É como pedir a uma multidão de pessoas para adivinhar o peso de uma abóbora; uma pessoa pode estar muito errada, mas se você tirar a média dos palpites de cem pessoas, terá uma resposta muito precisa. O artigo mostra que você pode obter essa simetria perfeita e a capacidade de aprendizado perfeita simultaneamente, simplesmente tirando a média de algumas execuções.

O Que Isso Significa para o Futuro

Os autores tomam o cuidado de declarar que esta é uma prova teórica, não uma simulação de um conjunto de dados específico. Eles demonstraram matematicamente que o potencial existe para que esses modelos sejam aproximadores universais. Eles excluem explicitamente a ideia de que você precise de arquiteturas complexas e construídas sob medida para alcançar isso; a estrutura padrão da PENN, quando aumentada com características aleatórias, é suficiente.

Eles também esclarecem que, embora as características aleatórias quebrem a "simetria perfeita" de uma única execução, elas não quebram a "simetria em expectativa" (o comportamento médio). Isso sugere que, na prática, o uso de características aleatórias é uma estratégia robusta. O artigo conclui que as PENNs com características aleatórias devem ser consideradas uma base sólida para tarefas de aprendizado de grafos. Elas não são apenas uma curiosidade teórica; elas oferecem um plano concreto e matematicamente fundamentado para construir IAs de grafos que são tanto poderosas quanto flexíveis, capazes de aprender padrões complexos em redes que variam de moléculas químicas a sistemas financeiros.

Resumo Técnico: Universalidade e Taxas de Aproximação de Redes Neurais de Grafos com Características Aleatórias

Declaração do Problema

As Redes Neurais de Grafos (GNNs), particularmente as arquiteturas de passagem de mensagem, alcançaram um sucesso empírico significativo, mas enfrentam limitações teóricas quanto ao seu poder expressivo. As GNNs de passagem de mensagem padrão são limitadas pelo teste 1-Weisfeiler–Leman (1-WL), o que significa que não conseguem distinguir certas estruturas de grafos não isomórficos. Embora existam estratégias para superar isso — como arquiteturas de ordem superior ou o enriquecimento de características de nós — há uma falta de resultados teóricos rigorosos que estabeleçam as capacidades de aproximação universal de arquiteturas específicas de GNNs quando aumentadas com características aleatórias. Além disso, os resultados de universalidade existentes frequentemente dependem de suposições restritivas, como exigir que as funções alvo sejam contínuas, que os domínios sejam compactos ou que as características sejam de dimensão finita, e muitas vezes falham em abordar as taxas de aproximação (limites de complexidade) para esses modelos.

Metodologia

Os autores investigam as Redes Neurais de Permutação-Equivariantes (PENNs), uma classe de GNNs que generaliza muitas arquiteturas populares de passagem de mensagem (ex: GCN, GIN, GraphSAGE, GAT). A inovação metodológica central é o aumento das características de nó padrão com características de nó aleatórias.

Definição da Arquitetura: O artigo define as PENNs como funções compostas por componentes de redes neurais feedforward (FNN) ( $\rho, \phi, \alpha, \psi$ ) que agregam informações de vizinhanças e atributos globais do grafo. Esta estrutura subjaz o framework de Agregação-Combinação-Leitura (ACR).
Características Aleatórias: Os autores introduzem características de nó aleatórias $R$ que fornecem "características de nó únicas finitas". Isso significa que, com alta probabilidade (ou quase certamente), as características aleatórias atribuem identificadores distintos a nós distintos, quebrando efetivamente a simetria que limita as GNNs padrão. O framework acomoda tanto características aleatórias independentes e identicamente distribuídas (i.i.d.) quanto identificadores únicos determinísticos (ou suas permutações aleatórias).
Framework de Aproximação: O estudo utiliza teoremas clássicos de aproximação universal para FNNs (ex: Leshno et al., 1993), mas os adapta para o domínio dos grafos. A ideia central é que, se as características dos nós forem únicas, qualquer função de permutação-equivariante pode ser representada como uma composição de FNNs atuando sobre essas características únicas.
Equivariância Baseada em Esperança: Reconhecendo que a permutação-equivariância por caminho (pathwise) é quebrada pelas características aleatórias fixas, os autores analisam a permutação-equivariância em esperança. Eles propõem a média das PENNs sobre múltiplas amostras de características aleatórias reamostradas para recuperar as propriedades de equivariância enquanto mantêm uma alta expressividade.

Principais Contribuições

1. Teoremas de Aproximação Universal

O artigo estabelece que as PENNs aumentadas com características aleatórias são aproximadores universais para funções de permutação-invariantes e de permutação-equivariantes mensuráveis em grafos direcionados com tamanho fixo e características de nó/aresta multidimensionais.

Generalidade: Ao contrário de trabalhos anteriores (ex: Abboud et al., 2020; Puny et al., 2020), este resultado não exige que a função alvo seja contínua, nem assume compacidade ou finitude do espaço de características. Aplica-se a funções mensuráveis em domínios não limitados.
Arquitetura Concreta: Os autores especificam uma arquitetura concreta (PENNs) para a qual a universalidade é válida, em vez de apenas afirmar a existência de alguma arquitetura abstrata.
Probabilidade: A aproximação ocorre com probabilidade arbitrariamente alta, desde que as características aleatórias induzam identificadores de nós únicos.

2. Taxas de Aproximação e Limites de Complexidade

Para funções $k$ vezes continuamente diferenciáveis ( $k \ge 2$ ) definidas em domínios compactos, o artigo deriva limites superiores explícitos na complexidade dos componentes da PENN necessários para alcançar um erro de aproximação $\varepsilon$ desejado.

Profundidade: O número de camadas necessário cresce logaritmicamente em relação a $1/\varepsilon$ ( $O(\log(1/\varepsilon))$ ).
Largura/Pesos: O número de pesos não nulos cresce polinomialmente em relação a $1/\varepsilon$ , especificamente como $O(\varepsilon^{-c/(k-1)})$ , onde $c$ depende das dimensões do grafo ( $N, d, d'$ ).
Maldição da Dimensionalidade: Os limites refletem uma forma de maldição da dimensionalidade em relação ao domínio do grafo, mas a severidade é mitigada para funções com maior regularidade ( $k$ ).

3. Permutação-Equivariância em Esperança

O artigo aborda o compromisso entre expressividade e simetria. Embora uma única realização de uma PENN com características aleatórias não seja de permutação-equivariância por caminho, os autores provam que a esperança da saída da PENN (condicional à entrada do grafo) é de permutação-equivariante. Além disso, eles mostram que a média sobre um número finito de amostras de características aleatórias i.i.d. preserva a propriedade de aproximação universal enquanto melhora o viés em direção à equivariância.

Resultados

Teorema 9: Estabelece que para qualquer função de permutação-equivariante mensurável $f$ e qualquer $\varepsilon, \delta > 0$ , existe uma PENN com características aleatórias tal que a probabilidade de o erro de aproximação exceder $\varepsilon$ é no máximo $\delta$ .
Teorema 11: Fornece uma versão teórica da medida para o resultado de universalidade, aplicável quando a própria distribuição do grafo induz características de nó únicas.
Teorema 16: Demonstra que a PENN média (usando $M$ cópias i.i.d. de características aleatórias) também satisfaz a propriedade de aproximação universal, com a probabilidade de erro limitada por $\delta$ .
Teorema 18: Fornece as taxas de aproximação quantitativas. Prova que, para funções suficientemente regulares, as PENNs com restrições arquiteturais específicas (profundidade e largura) podem aproximar uniformemente a função alvo com alta probabilidade. Os limites de complexidade espelham aqueles conhecidos para redes neurais feedforward padrão.

Significância e Alegações

Os autores alegam que este trabalho preenche lacunas substanciais na compreensão teórica das GNNs:

Ponte entre Teoria e Prática: Ao provar a universalidade para uma arquitetura concreta e eficiente em termos de memória (PENNs), em vez de modelos abstratos, os resultados fornecem uma base teórica para o uso de características aleatórias em aplicações práticas de GNN.
Generalização de Resultados Existentes: Os resultados generalizam teoremas de universalidade anteriores ao relaxar as suposições de continuidade, compacidade e a natureza das funções alvo (mensuráveis vs. contínuas).
Orientação Prática: As taxas de aproximação derivadas oferecem orientação teórica para a seleção de hiperparâmetros (profundidade e largura) com base na precisão desejada e na regularidade da função alvo.
Benchmarking: Os autores sugerem que as PENNs com características aleatórias devem ser consideradas bases fortes para tarefas de aprendizado em grafos, seja como alternativas competitivas aos modelos de última geração ou como um ponto de referência para validar as capacidades de outras arquiteturas.

O artigo conclui que, embora as características aleatórias possam introduzir uma perda de equivariância por caminho, os modelos resultantes possuem um poder expressivo superior e, quando calculada a média, retêm propriedades de simetria desejáveis, tornando-os uma ferramenta teórica e prática robusta para o aprendizado em grafos.