Resumo Técnico: Preservação Estrutural e a Expressividade Lógica de Redes Neurais de Grafos

1. Enunciado do Problema

Embora as conexões entre Redes Neurais de Grafos (GNNs) e formalismos lógicos tenham sido estabelecidas, trabalhos anteriores baseiam-se amplamente em fixar escolhas arquiteturais específicas (ex: funções de agregação, combinação e ativação) para definir classes restritas de GNNs. Essas caracterizações baseadas na arquitetura vinculam variantes específicas de GNN a extensões da lógica de primeira ordem (ex: com termos de contagem ou quantificadores de Presburger) ou formalismos baseados em regras como Datalog.

Este artigo aborda a necessidade de um arcabouço semântico que caracterize a expressividade lógica de classes de GNNs com base em propriedades de preservação estrutural, em vez de restrições sintáticas específicas. Especificamente, os autores investigam classificadores GNN que são preservados sob três relações estruturais distintas:

1. Embeddings (extensões).
2. Homomorfismos injetivos.
3. Homomorfismos.

O desafio central é determinar quais fragmentos de lógica correspondem a essas propriedades de preservação e fornecer representações finitas para as classes de grafos que elas definem, apesar da natureza infinita das estruturas de grafos.

2. Metodologia

Os autores adotam uma perspectiva semântica inspirada na teoria de modelos finitos, adaptando teoremas de preservação (como os teoremas de van Benthem–Rosen e de Rossman) para o contexto de GNNs. A metodologia procede através de três estágios principais:

A. Localidade e Desenrolamento (Unravelling)

Aproveitando a localidade inerente das GNNs (onde a saída de uma GNN de $L$ camadas depende apenas da vizinhança de $L$ saltos), os autores utilizam o conceito de $L$-desenrolamento ($L\text{-unravelling}$). Isso transforma um grafo pontuado $(G, v)$ em uma árvore enraizada de altura no máximo $L$. Uma propriedade fundamental estabelecida é que os classificadores GNN são invariantes sob essa transformação: $N(G, v) = N(\text{Unr}_L(G, v))$. Isso permite que a análise de GNNs seja reduzida à análise de estruturas de árvores.

B. Resultados de Bem-Quase-Ordenação (WQO)

Para lidar com o conjunto infinito de possíveis grafos, o artigo introduz um novo resultado combinatório referente a bem-quase-ordenações (WQO).

• Teorema 4: A relação de embedding em qualquer classe de árvores enraizadas com alturas uniformemente limitadas por uma constante fixa é uma bem-quase-ordenação.
• Corolário 5: Este resultado estende-se a homomorfismos injetivos e homomorfismos em árvores de altura limitada.
• Significância: Como as WQOs admitem apenas um número finito de elementos mínimos, qualquer classe de árvores invariante sob desenrolamento e preservada sob estas relações estruturais pode ser representada por um conjio finito de árvores mínimas. Esta finitude é crucial para estabelecer a definibilidade lógica.

C. Teoremas de Preservação

Combinando a invariância de desenrolamento com os resultados de WQO, os autores provam teoremas de preservação que vinculam propriedades estruturais à definibilidade lógica em fragmentos da Lógica Modal Graduada (GML):

• Classes preservadas sob embeddings correspondem à Lógica Modal Graduada Existencial ($\exists$GML).
• Classes preservadas sob homomorfismos injetivos correspondem à Lógica Modal Graduada Existencial-Positiva ($\exists^+$GML).
• Classes preservadas sob homomorfismos correspondem à Lógica Modal Existencial-Positiva ($\exists^+$ML).

D. Caracterização Sintática

O artigo complementa estes resultados semânticos identificando arquiteturas GNN específicas que realizam estas classes de expressividade. Os autores definem:

• GNNs Monotônicas (MGNNs): GNNs com funções de agregação e combinação não decrescentes.
• MAX-MGNNs: MGNNs que utilizam MAX como função de agregação.
• MGNNs Aumentadas: MGNNs precedidas por uma camada de transformação de características ponto a ponto.

3. Contribuições Principais e Resultados

Caracterizações Lógicas

O artigo estabelece correspondências estreitas entre propriedades de preservação e fragmentos lógicos (Teorema 7, Corolário 8):

• Embeddings $\iff$ $\exists$GML: GNNs preservadas sob embeddings têm a mesma expressividade que $\exists$GML.
• Homomorfismos Injetivos $\iff$ $\exists^+$GML: GNNs preservadas sob homomorfismos injetivos correspondem a $\exists^+$GML.
• Homomorfismos $\iff$ $\exists^+$ML: GNNs preservadas sob homomorfismos correspondem a $\exists^+$ML.

Realizações Arquiteturais

Os autores demonstram que estas classes semânticas podem ser capturadas por restrições arquiteturais específicas (Teorema 16):

• MGNNs Aumentadas são equivalentes em expressividade a $\exists$GML.
• MGNNs são equivalentes a $\exists^+$GML.
• MAX-MGNNs são equivalentes a $\exists^+$ML.
• MAX-MGNNs Aumentadas são equivalentes a $\exists$ML.

GNNs de Pesos Positivos

Uma descoberta significativa diz respeito às GNNs de pesos positivos (onde as matrizes de parâmetros possuem entradas não negativas). O artigo mostra que qualquer GNN preservada sob homomorfismos injetivos (incluindo todas as MGNNs) pode ser transformada em uma GNN de pesos positivos equivalente. Isso implica que a restrição sintática a pesos não negativos não é restritiva quanto à expressividade dentro desta classe.

Trocas de Expressividade (Trade-offs)

Os resultados revelam um compromisso fundamental:

• Propriedades de preservação mais fortes (ex: homomorfismos) levam a caracterizações lógicas mais simples (ex: $\exists^+$ML), mas a uma expressividade reduzida.
• Propriedades de preservação mais fracas (ex: embeddings) permitem fragmentos lógicos mais ricos (ex: $\exists$GML), capazes de expressar propriedades não monotônicas (como "o nó $v$ não possui o rótulo $A$"), mas são menos robustas a transformações estruturais.
• Especificamente, as MAX-MGNNs não podem expressar condições baseadas em limiares (ex: "pelo menos $k$ vizinhos") porque a agregação MAX é insensível a multiplicidades, enquanto as MGNNs podem expressar tais condições, mas não conseguem lidar com homomorfismos não injetivos que fundem nós.

4. Significância e Escopo

O artigo afirma fornecer um arcabouço semântico para analisar a expressividade de GNNs que é independente de escolhas arquiteturais específicas, sendo capaz, contudo, de identificar arquiteturas que atingem esses limites. Ao estabelecer correspondências exatas entre preservação estrutural, fragmentos lógicos e arquiteturas GNN, o trabalho oferece ferramentas principadas para:

• Analisar a expressividade de GNNs.
• Permitir métodos simbólicos para verificação e explicação.
• Compreender as limitações de MGNNs e GNNs de pesos positivos.

Os autores observam limitações: o arcabouço foca na classificação de nós (não na predição ao nível de grafo), assume comportamento de vizinhança local (ignorando mecanismos de raciocínio global), restringe-se a classificadores baseados em limiares e assume rótulos de nós discretos. Além disso, a correspondência captura o comportamento limitado pela localidade das GNNs e não contabiliza propriedades além do regime de desenrolamento limitado.

A contribuição técnica do novo resultado de WQO para árvores de altura limitada é destacada como sendo de interesse independente para o estudo de bem-quase-ordenações, distinta de sua aplicação às GNNs.