Resumo Técnico: Poder de Separação de Redes Neurais Equivariantes

Declaração do Problema

A expressividade de modelos de aprendizado de máquina é frequentemente quantificada por sua universalidade — a capacidade de aproximar qualquer função dentro de uma classe específica. No entanto, para redes neurais equivariantes (aquelas que respeitam simetrias como permutações ou rotações), a universalidade é limitada pela incapacidade inerente da rede em distinguir entradas que são equivalentes sob o grupo de simetria. Essa limitação cria uma interação complexa entre a capacidade de uma rede de discriminar entradas distintas e as estruturas invariantes/equivariantes que ela deve preservar.

Embora a comunidade de aprendizado em grafos tenha estudado extensivamente o poder de separação de Redes Neurais de Grafos (GNNs) usando o teste de Weisfeiler-Leman (WL) e contagem de homomorfismos, essas ferramentas combinatórias possuem limitações severas quando aplicadas a classes mais amplas de modelos equivariantes, particularmente aqueles que processam dados geométricos ou utilizam convoluções regulares. Há uma carência de ferramentas analíticas refinadas para caracterizar o conjunto de entradas indistinguíveis (a relação de identificação) para redes neurais equivariantes gerais com ativações não polinomiais, representações de dimensão finita e equivariância de permutação.

Metodologia

O artigo introduz um arcabouço teórico para caracterizar o poder de separação $\rho(\mathcal{N})$ de uma família de redes neurais equivariantes $\mathcal{N}$. O poder de separação é definido como a relação de equivalência que identifica pares de entradas $(\alpha, \beta)$ tais que $f(\alpha) = f(\beta)$ para todo $f \in \mathcal{N}$.

A principal contribuição metodológica é o "Truque da Rede Gêmea" (Twin Network Trick), que transforma o problema de identificar entradas indistinguíveis em um problema de local de zeros. Ao construir uma rede gêmea $\hat{\eta}(\alpha, \beta) = \eta(\alpha) - \eta(\beta)$, os autores reformulam a relação de identificação como a busca pelo conjunto de pontos mapeados para zero pelo espaço da rede gêmea.

Essa redução permite que os autores apliquem técnicas recursivas derivadas da teoria de equações funcionais. Especificamente, eles utilizam resultados relativos a equações funcionais lineares envolvendo funções contínuas não polinomiais (ex: ReLU, sigmoid) para derivar uma fórmula explícita e recursiva para o local de zeros. Esta fórmula relaciona o local de zeros de uma rede de profundidade $d$ aos locais de zeros de redes de profundidade $d-1$, envolvendo uniões e interseções de subespaços específicos definidos pela arquitetura da rede e termos de viés (bias).

A análise assume:

1. Representações de Permutação: As redes atuam em espaços de funções de valores reais sobre conjuntos finitos, equivariantes sob grupos finitos que atuam como permutações.
2. Ativações Não Polinomiais: As funções de ativação são contínuas e não polinomiais.
3. Viés Completo (Complete Bias): As camadas afins incluem termos de viés subordinados à partição de órbita do espaço de representação.

Contribuições Principais e Resultados

1. Caracterização Completa de Entradas Indistinguíveis

O artigo fornece uma caracterização completa do conjunto de pares de entrada identificados por redes com uma arquitetura fixa.

• Teorema 1 (Teorema de Caracterização): Estabelece uma fórmula recursiva para o local de zeros de um espaço de rede. Esta fórmula decompõe a relação de identificação baseando-se na profundidade da rede, propriedades de ativação e na partição do espaço de representação induzida pelos termos de viés.

2. Equivalência de Ativações Não Polinomiais

• Teorema 2: Prova que, para uma arquitetura fixa, qualquer função de ativação contínua, real, elemento a elemento e não polinomial produz o mesmo poder de separação. Consequentemente, ativações comuns como ReLU, sigmoid e tanh são equivalentes em sua capacidade de distinguir entradas e todas alcançam o máximo poder de separação possível para aquela arquitetura. Ativações polinomiais são excluídas desta equivalência.

3. O Papel da Profundidade

• Teorema 3: Demonstra que o aumento da profundidade da rede amplia o poder de separação apenas até um limiar de repetição específico. Além deste limiar, adicionar mais camadas do mesmo tipo não melhora a capacidade de distinguir entradas; o poder de separação se estabiliza.
  • Para Redes de Grafos Invariantes de ordem $k$ (IGNs), este limiar é proporcional ao limiar do teste $k$-WL.
  • Para redes com representações ocultas regulares, a estabilização ocorre após apenas uma repetição de camada.

4. Independência da Largura de Características Ocultas e de Características Invariantes

• Teorema 4 & Observação 1: Mostra que o poder de separação é independente da multiplicidade de blocos em representações ocultas. Especificamente, aumentar a largura das características ocultas invariantes (ex: a dimensão do espaço de características em IGNs) não melhora a capacidade da rede de distinguir entradas. O poder de separação de uma rede com representação oculta $V \otimes \mathbb{R}^f$ é idêntico ao de uma rede com representação oculta $V$.

5. Hierarquia de Tipos de Representação

• Teorema 5: Estabelece uma hierarquia no poder de separação baseada no tipo de representação utilizada nas camadas. O poder de separação corresponde à ordenação parcial dos subgrupos do grupo de simetria.
  • Representações induzidas por subgrupos menores (ex: o subgrupo trivial $\{e\}$, correspondendo à representação regular) geram o poder de separação máximo.
  • Representações induzidas por subgrupos maiores (ex: o próprio grupo $G$, correspondendo a vetores invariantes) geram o poder de separação mínimo.
  • Isso implica que o uso de representações regulares ($\mathbb{R}^G$) em camadas ocultas é suficiente para atingir o máximo poder de separação permitido pela arquitetura.

Implicações para Modelos Práticos

Os autores aplicam estes resultados gerais a modelos práticos específicos:

• Redes de Grafos Invariantes (IGNs): Os resultados fortalecem descobertas anteriores ao mostrar que $k$-IGNs igualam o poder de separação do teste $k$-WL, independentemente das dimensões das características ocultas. Isso resolve a necessidade de resultados anteriores que exigiam larguras de características ocultas "grandes" para alcançar a universalidade.
• CNNs Circulares: O poder de separação de Redes Neurais Convolucionais Circulares mostra-se dependente do tamanho do filtro. Especificamente, redes com suportes de filtro maiores (aproximando-se do tamanho total do grupo) possuem um poder de separação estritamente mais fino do que aquelas com suportes menores, formando uma hierarquia estrita.

Significância e Alegações

O artigo afirma fornecer uma condição necessária para compreender a universalidade de redes neurais equivariantes. Ao caracterizar precisamente a relação de identificação $\rho(\mathcal{N})$, os autores permitem a classificação de hiperparâmetros e escolhas arquiteturais em duas categorias:

1. Determinantes da Separação: Escolhas que influenciam diretamente o conjunto de entradas distinguíveis (ex: tipo de ativação, profundidade até um limiar, tipo de representação). Estas impactam significativamente tanto a capacidade de aproximação quanto o custo computacional.
2. Independentes da Separação: Escolhas que não afetam o conjunto de entradas distinguíveis (ex: largura de característica oculta, multiplicidade de blocos). Estas podem influenciar a aproximação dentro das restrições do poder de separação, mas não expandem a classe de entradas distinguíveis.

Os autores enfatizam que seu arcabouço é limitado a representações de permutação e ativações não polinomiais. Eles reconhecem que sua abordagem não se estende atualmente a modelos que utilizam coeficientes de Clebsch-Gordan ou abordagens polinomiais, nem aborda totalmente casos onde os termos de viés estão ausentes (embora possa fornecer limites nesses casos). O trabalho serve como uma ferramenta teórica fundamental para analisar a expressividade de modelos equivariantes além das restrições combinatórias de testes específicos de grafos.