The Logical Expressiveness of Topological Neural Networks

Título: A Expressividade Lógica das Redes Neurais Topológicas

Autores: Amirreza Akbari, Amauri H. Souza, Vikas Garg
Instituições: Aalto University, Federal Institute of Ceará, YaiYai Ltd.

---

1. Problema e Motivação

As Redes Neurais em Grafos (GNNs) são o paradigma padrão para aprendizado em dados estruturados em grafos. No entanto, sua capacidade expressiva é limitada, sendo frequentemente caracterizada pelo teste de Weisfeiler-Leman (WL) de 1 dimensão (1-WL) ou pela lógica de primeira ordem. GNNs padrão falham em distinguir grafos não isomorfos que o 1-WL não distingue e não conseguem capturar informações estruturais fundamentais (como ciclos ou componentes conectados).

Para superar essas limitações, surgiram as Redes Neurais Topológicas (TNNs), que operam em Complexos Combinatórios (CCs) — estruturas que generalizam grafos, hipergrafos e complexos celulares, permitindo relações de ordem superior. Embora as TNNs ofereçam maior poder representacional, uma questão fundamental permanecia em aberto: qual é a expressividade lógica exata das TNNs?

Não existia uma teoria lógica unificada para caracterizar quais classificadores binários as TNNs podem representar, nem uma compreensão precisa de como sua capacidade de distinguir estruturas cresce com a ordem das interações.

---

2. Metodologia

Os autores desenvolveram uma análise teórica baseada em um "tríade" clássica da teoria da complexidade descritiva, estendendo-a do domínio de grafos para complexos combinatórios atribuídos (ACCs). A metodologia consiste em três pilares interconectados:

A. Algoritmo: k-CCWL (k-dimensional Combinatorial Complex WL)

Os autores introduzem o k-CCWL, uma extensão do algoritmo de refinamento de cores (color refinement) para complexos combinatórios.

• Mecanismo: O algoritmo refina rótulos de $k$-tuplas de células (nós, arestas, faces, etc.) iterativamente.
• Diferencial: Diferente do WL clássico que opera em vértices, o k-CCWL considera quatro tipos de adjacências topológicas:
  1. Fronteira (Boundary): Células de rank inferior.
  2. Cofronteira (Coboundary): Células de rank superior.
  3. Adjacência Superior (Upper): Células do mesmo rank que compartilham uma célula de rank superior.
  4. Adjacência Inferior (Lower): Células do mesmo rank que compartilham uma célula de rank inferior.
• Mecanismo de Atualização: Utiliza uma "sequência de duplo deslocamento" (double shift sequence), onde o rótulo de uma $k$-tupla é atualizado com base nas substituições de pares de células $(\alpha, \beta)$, capturando interações de ordem superior.

B. Lógica: TCk (Topological Counting Logic)

Foi introduzida uma nova fragmentação da lógica de primeira ordem chamada Lógica de Contagem Topológica (TCk).

• Quantificador de Contagem Pares: A inovação central é o quantificador de contagem de pares $\exists^N(x_i, x_j) \phi(x_i, x_j)$.
• Motivação: Em grafos, arestas conectam diretamente dois vértices. Em complexos topológicos, relações entre células são frequentemente mediadas por outras células (ex: duas arestas são adjacentes porque compartilham um vértice). O quantificador de pares permite contar explicitamente quantos pares de células satisfazem uma propriedade $\phi$, capturando a agregação de sinais relacionais que as TNNs realizam.
• Expressividade: TCk estende a lógica de contagem clássica ($C_k$) para lidar com a estrutura hierárquica e não hierárquica dos CCs.

C. Teoria dos Jogos: Topological Pebble Game

Os autores definiram o Jogo de Pedras Topológico (Topological Pebble Game).

• Mecânica: Um jogo entre dois jogadores (Spoiler e Duplicador) em dois ACCs.
• Regra Chave: Para corresponder ao quantificador de pares da lógica, o jogador I seleciona um conjunto de pares de células em um complexo, e o jogador II deve responder com um conjunto de pares do mesmo tamanho no outro complexo.
• Objetivo: O jogo testa se os dois complexos são indistinguíveis sob as regras da lógica TCk.

---

3. Contribuições Principais

1. Generalização do WL para Complexos Combinatórios: Definição formal do teste k-CCWL, que subsume a expressividade de várias arquiteturas existentes de TNNs (como CW Networks, Redes Simpliciais de Mensagens, UniGCN, etc.).
2. Introdução da Lógica TCk: Definição da lógica de contagem topológica com o quantificador de pares, fornecendo a primeira caracterização lógica precisa para redes neurais que operam em estruturas topológicas de ordem superior.
3. Estabelecimento da Tríade de Equivalência: Prova rigorosa de que três conceitos distintos são equivalentes em poder de distinção para ACCs uniformes:
   • O algoritmo k-CCWL.
   • A lógica TC(k+2).
   • O Jogo de Pedras Topológico (k+2).
4. Hierarquia Estrita: Demonstração de que aumentar $k$ aumenta estritamente o poder expressivo. Existem pares de complexos não isomorfos que são distinguíveis por $k$-CCWL, mas não por $(k-1)$-CCWL.

---

4. Resultados Teóricos

O resultado central do artigo é a seguinte equivalência (Corolário 5.3):

$$\text{k-CCWL} \equiv \text{TC}_{k+2} \equiv \text{Topological } (k+2)\text{-pebble game}$$

Implicações deste resultado:

• Caracterização Exata: Determina exatamente quais propriedades estruturais as TNNs de ordem $k$ podem aprender. Se uma propriedade não pode ser expressa em TC(k+2), nenhuma TNN baseada em mensagens de ordem $k$ poderá distingui-la.
• Hierarquia Rigorosa: O poder de distinção cresce estritamente com $k$. Por exemplo, o 2-CCWL consegue distinguir complexos que o 1-CCWL (equivalente a GNNs padrão em complexos) não consegue, como a presença de triângulos em certas configurações de grafos cíclicos.
• Conexão com Grafos: Para ACCs de dimensão 1 (grafos), o k-CCWL tem o mesmo poder expressivo que o k-WL clássico, validando a generalização.
• Limitações: O artigo também identifica "pontos cegos" (blindspots) das TNNs, como propriedades globais que requerem quantificação ilimitada (ex: conectividade global em grafos grandes, homologia de alta ordem em ciclos muito grandes), que escapam de qualquer TCk fixo.

---

5. Significado e Impacto

Este trabalho estabelece a fundação teórica para o aprendizado profundo topológico (Topological Deep Learning).

• Para a Teoria: Preenche uma lacuna crítica ao fornecer a primeira caracterização lógica completa para TNNs, análoga ao que o teorema de Cai-Fürer-Immerman fez para GNNs.
• Para a Prática: Oferece diretrizes para o design de modelos. Os pesquisadores agora sabem que para capturar certas interações de ordem superior, é necessário aumentar a dimensão $k$ da arquitetura (usando k-CCWL ou lógica equivalente).
• Validação de Arquiteturas: Permite classificar arquiteturas existentes de TNNs com base em sua capacidade de distinguir estruturas, ajudando a escolher o modelo correto para tarefas específicas que exigem raciocínio topológico complexo.

Em resumo, o paper prova que as TNNs não são apenas heurísticas empíricas, mas possuem uma base lógica sólida e quantificável, onde a capacidade de distinguir estruturas complexas escala sistematicamente com a ordem das interações consideradas.