A Graphop Analysis of Graph Neural Networks on Sparse Graphs: Generalization and Universal Approximation

Resumo Técnico: Uma Análise de Graphop de Redes Neurais de Grafos em Grafos Esparsos

Definição do Problema
A análise teórica das Redes Neurais de Grafos de Passagem de Mensagens (MPNNs) em relação à generalização e aproximação universal historicamente enfrentou uma dicotomia. As abordagens existentes baseiam-se na definição de um espaço métrico compacto de grafos sob o qual as MPNNs são equicontínuas. No entanto, essas abordagens sofrem de um compromisso fundamental:

1. Grafos Densos: Métricas que permitem grafos de tamanhos ilimitados (necessários para limites de generalização) são tipicamente baseadas na teoria dos graphons. Essas métricas são apropriadas apenas para grafos densos; elas falam para grafos esparsos porque a agregação de soma normalizada (necessária para a convergência em limites de graphon) produz saídas próximas de zero para estruturas esparsas.
2. Grafos Esparsos: Abordagens que lidam com grafos esparsos (usando agregação de soma) tipicamente restringem o espaço métrico a grafos de tamanho uniformemente limitado. Isso impede a derivação de limites de generalização para tamanhos de grafos ilimitados e limita o escopo dos teoremas de aproximação universal.

Consequentemente, não há um framework unificado que forneça limites de generalização poderosos e teoremas de aproximação universal para MPNNs atuando tanto em grafos esparsos quanto densos.

Metodologia
Os autores propõem uma abordagem unificada baseada em Análise de Graphop, uma teoria de limite de grafos adequada para grafos esparsos, estendendo-a para lidar com características de nós (features) e MPNNs. A metodologia procede através das seguintes etapas:

1. Operadores de Fibra Limitados (Bofops): O artigo introduz uma subclasse de graphops chamada bounded fiber operators (bofops). Diferente dos graphops gerais, os bofops possuem uma estrutura de conectividade específica caracterizada por uma família de medidas (fibras) que representam vizinhanças de nós. Essa estrutura codifica naturalmente padrões de conectividade esparsos e densos. Os autores estendem a teoria de graphops para incluir características de nós, definindo bofop-signals como pares de um bofop e um sinal (mapeamento de características).
2. Métrica de Ação e Perfis: Para analisar MPNNs, os autores utilizam a métrica de ação, definida via a distância de Hausdorff entre "perfis" (histogramas de valores de saída sobre funções de entrada). Eles provam que o espaço de bofop-signals é compacto sob esta métrica e que as MPNNs são Lipschitz contínuas em relação a ela.
3. Distância DIDM-Mover's: A métrica de ação é muito fina para servir como base para aproximação universal, pois bofop-signals distintos podem gerar saídas de MPNN idênticas. Para resolver isso, os autores introduzem a distância DIDM-Mover's (Distribuição de Medidas de Grau Iteradas). Esta métrica é mais grosseira que a métrica de ação e é construída com base nas árvores computacionais subjacentes ao algoritmo 1-Weisfeiler-Leman (1-WL).
4. Comutação e Continuidade: Os autores demonstram que as MPNNs comutam com o algoritmo 1-WL em bofop-signals. Eles provam que as MPNNs são uniformemente equicontínuas em relação à distância DIDM-mover's e possuem o mesmo poder de separação que esta métrica (ou seja, distinguem exatamente aqueles bofop-signals que possuem distância DIDM-mover's não nula).
5. Densidade e Completude: O artigo estabelece que o espaço de sinais de grafos finitos (tanto esparsos quanto densos) é denso dentro do espaço de bofop-DIDMs sob a distância DIDM-mover's. Assim, os bofop-DIDMs servem como a completude do espaço de todos os grafos finitos.

Principais Contribuições

• Espaço Métrico Unificado: A definição de um espaço métrico compacto (bofop-signals) que inclui grafos de todos os tamanhos, tanto esparsos quanto densos.
• Extensão da Teoria de Graphop: A introdução de bofops e bofop-signals, que generalizam os graphons e permitem a modelagem natural de agregações de soma, soma normalizada e média simétrica dentro de um único framework.
• Garantias Teóricas:
  • Aproximação Universal: Um teorema afirmando que qualquer função contínua sobre o espaço de bofop-DIDMs (com relação à distância DIDM-mover's) pode ser uniformemente aproximada por uma MPNN. Como os grafos finitos são densos neste espaço, isso se aplica a funções contínuas em grafos.
  • Limites de Generalização: Uma prova de que as MPNNs admitem limites de generalização (onde o erro entre o risco de treinamento e de teste decai para zero conforme o tamanho da amostra aumenta) devido ao número de cobertura finito do espaço compacto de bofop-DIDMs e da equicontinuidade uniforme das MPNNs.
• Hierarquia de Espaços DIDM: O estabelecimento de uma hierarquia estrita onde os graphons-DIDMs (baseados em graphon) formam um subconjunto próprio dos bofop-DIDMs, que por sua vez formam um subconjunto próprio do espaço de todos os DIDMs formais.

Resultos
O artigo fornece provas rigorosas para o seguinte:

• O espaço de bofop-signals é compacto sob a métrica de ação e a distância DIDM-mover's.
• As MPNNs são Lipschitz contínuas em relação à métrica de ação e uniformemente equicontínuas em relação à distância DIDM-mover's.
• As MPNNs separam pontos no espaço de bofop-signals com relação à distância DIDM-mover's.
• O espaço de sinais de grafos finitos é denso no espaço de bofop-signals sob a distância DIDM-mover's.
• Consequentemente, o teorema de Stone-Weierstrass aplica-se às MPNNs em bofop-signals, garantindo a aproximação universal.
• Argumentos de número de cobertura garantem limites de generalização para MPNNs treinadas em distribuições de dados sobre grafos esparsos ou densos.

Significância e Alegações
O artigo afirma resolver a limitação de longa data onde as análises teóricas de GNNs eram restritas a grafos densos (via graphons) ou grafos esparsos de tamanho limitado. Ao utilizar a análise de graphop e a subclasse específica de bofops, os autores fornecem um framework teórico unificado que:

1. Trata grafos esparsos e densos de tamanhos ilimitados em pé de igualdade.
2. Fornece teoremas de aproximação universal e limites de generalização mais fortes do que trabalhos anteriores.
3. Esclarece a relação entre o poder computacional das MPNNs (poder de separação) e a estrutura topológica do espaço de entrada via a distância DIDM-mover's.

Os autores observam que sua construção de MPNNs sobre perfis é atualmente teórica, pois perfis são definidos como conjuntos de medidas sem uma estrutura computacional direta. Eles identificam a obtenção de limites explícitos sobre o número de cobertura dos espaços bofop como uma direção futura para tornar os limites de generalização mais concretos.