The Polynomial Counting Capabilities of Message Passing Neural Networks

Resumo Técnico: As Capacidades de Contagem Polinomial das Redes Neurais de Passagem de Mensagens

Declaração do Problema
Pesquisas recentes estabeleceram que as Redes Neurais de Passagem de Mensagens (MPNNs) podem expressar propriedades lógicas envolvendo contagem até um limite ou satisfazendo restrições aritméticas lineares, frequentemente caracterizadas usando fragmentos da lógica de primeira ordem com contagem (FOC2) ou extensões com aritmética inteira linear. No entanto, permanece uma lacuna na compreensão do poder expressivo das MPNNs em relação a restrições de contagem polinomial (aritmética não linear), que são relevantes para técnicas avançadas de classificação de grafos, como kernels polinomiais. Este artigo investiga as condições sob as quais as MPNNs, especificamente aquelas que utilizam agregação por média, podem reconhecer propriedades definidas pela Lógica Modal Peano (PML). A PML estende a Lógica Modal Graduada permitindo restrições polinomiais (por exemplo, $x_1^2 \cdot x_2 \leq x_3$) em vez de apenas restrições lineares.

Metodologia
Os autores empregam uma estrutura formal para analisar as capacidades expressivas das MPNNs comparando-as com fragmentos da PML.

• Definição do Modelo: O estudo foca em MPNNs ($M_{mean}$) que utilizam agregação por média tanto para informações locais (vizinhança) quanto globais (grafo inteiro). Os autores também consideram variantes ($M_{mean, x}$) que permitem agregações adicionais de soma ou máximo.
• Definição da Lógica: Eles definem a PML, onde fórmulas modais $\langle \pi_1, \dots, \pi_m \rangle \psi(x_1, \dots, x_m)(\phi_1, \dots, \phi_m)$ contam nós satisfazendo subfórmulas $\phi_i$ dentro de vizinhanças específicas (definidas por modalidades $\pi \in \{id, E_{in}, E_{out}, \top\}$) e verificam se as contagens satisfazem uma restrição aritmética Peano $\psi$.
• Estrutura de Reconhecimento: Diz-se que uma MPNN "reconhece" uma fórmula $\phi$ sobre uma classe de grafos pontuados se o estado de saída da rede para o nó foco $v$ for não nulo (especificamente $\geq c(|V|)$) se o grafo satisfizer $\phi$, e zero caso contrário. A certeza $c(|V|)$ é permitida depender do tamanho do grafo.
• Estratégia de Construção: As provas envolvem a construção de arquiteturas específicas de MPNN camada por camada. Essas construções utilizam "gadgets" (combinações de neurônios ReLU) para realizar operações aritméticas (multiplicação, adição, comparação) em valores agregados. Um desafio técnico chave abordado é o manuseio de denominadores introduzidos pela agregação por média (por exemplo, $1/|V|$ ou $1/|neigh(v)|$) ao avaliar termos polinomiais de graus variados.

Principais Contribuições e Resultados
O artigo identifica suposições estruturais específicas sobre grafos de entrada que permitem que MPNNs de média capturem propriedades de contagem polinomial. Os resultados são categorizados pela profundidade das modalidades (rasa vs. aninhada) e pelo tipo de modalidades utilizadas (global vs. local).

1. Modalidades Globais (Profundidade Rasa):

   • Restrições Homogêneas: Para fórmulas usando apenas a modalidade global ($\top$) e termos Peano homogêneos (sem termos constantes, mesmo grau para todos os monômios), MPNNs de média podem reconhecer a lógica sem suposições adicionais sobre o grafo (Lema 1).
   • Restrições Polinomiais Gerais: Para reconhecer restrições polinomiais globais arbitrárias (incluindo termos não homogêneos e constantes), os grafos de entrada devem conter um nó marcado (um nó com uma cor única). Sob essa suposição, MPNNs de média podem alinhar denominadores a $|V|^k$ e reconhecer a lógica (Teorema 1).

2. Modalidades Locais (Profundidade Rasa):

   • Requisito de Regularidade: Para fórmulas usando apenas modalidades locais ($E_{in}, E_{out}$), MPNNs de média exigem que os grafos de entrada sejam regulares (todos os nós têm o mesmo grau de entrada/saída) e que o nó foco seja fortemente marcado (marcado e possuindo um laço próprio). Isso permite que a rede normalize os tamanhos das vizinhanças locais (Teorema 2).
   • Relaxamento da Regularidade: Se for permitido que a MPNN utilize agregação de soma ou máximo além da média, a suposição de regularidade pode ser descartada. A rede pode então reconhecer restrições polinomiais locais em qualquer grafo onde o foco seja fortemente marcado (Teorema 3).

3. Modalidades Mistas (Profundidade Rasa):

   • Ao combinar modalidades globais e locais, os resultados das seções anteriores podem ser combinados. MPNNs de média reconhecem essas fórmulas em grafos regulares e fortemente marcados (Teorema 4).
   • Com a adição de agregações de soma/máximo, a suposição de regularidade é novamente removível (Teorema 5).

4. Modalidades Aninhadas (Profundidade Arbitrária):

   • Aninhamento Global: Aninhar modalidades globais não aumenta o poder expressivo além da profundidade 1; elas podem ser achatadas (Proposição 1).
   • Aninhamento Local: Para fórmulas com modalidades locais aninhadas, o artigo introduz uma classe de grafos chamada $(T \circlearrowleft_\phi)^p_\bullet$. Estas são estruturas "semelhantes a árvores" onde o foco é marcado e a estrutura do grafo garante traços únicos para nós em distâncias específicas (evitando ambiguidade nas contagens de vizinhança).
   • Resultados: MPNNs de média podem reconhecer PML local aninhada nesses grafos semelhantes a árvores, regulares e fortemente marcados (Teorema 6). Se agregações de soma/máximo forem permitidas, a restrição de regularidade é removida, permitindo o reconhecimento em grafos gerais semelhantes a árvores e fortemente marcados (Teorema 7).

Significância e Alegações
O artigo alega identificar as condições mínimas necessárias para que as MPNNs generalizem além da aritmética linear para a contagem polinomial.

• Generalização Teórica: Os resultados sugerem que MPNNs com agregação por média podem generalizar técnicas usadas em classificação de grafos que dependem de kernels polinomiais (por exemplo, SVMs com kernels polinomiais), desde que os dados de entrada satisfaçam propriedades estruturais específicas (nós marcados, regularidade ou semelhança a árvores).
• Papel da Agregação: O estudo destaca que, embora a agregação por média seja suficiente para contagem polinomial sob suposições estruturais estritas, a inclusão de agregações de soma ou máximo relaxa significativamente esses requisitos (especificamente removendo a necessidade de regularidade do grafo).
• Limitações: Os autores afirmam explicitamente que, sem essas suposições estruturais (nós marcados, regularidade ou estruturas semelhantes a árvores), MPNNs de média não podem expressar todas as restrições polinomiais. Por exemplo, o Lema 2 demonstra que MPNNs de média não conseguem distinguir entre certos grafos não regulares que satisfazem uma restrição polinomial simples.

O artigo conclui que, embora as MPNNs possuam capacidades de contagem polinomial, realizá-las requer escolhas arquitetônicas específicas (adicionar soma/máximo) ou suposições específicas de pré-processamento de dados/estrutura (marcar nós, garantir regularidade ou estruturas semelhantes a árvores). Sugere-se trabalho futuro para explorar combinações booleanas arbitrárias de modalidades e comparar contagens em diferentes distâncias, que não são atualmente cobertas pelo framework PML utilizado.