Resumo Técnico: Uma Camada Tikhonov Generalizada para Redes Neurais em Grafos Interpretáveis por Design

Declaração do Problema

Redes Neurais em Grafos (GNNs) alcançaram sucesso significativo em tarefas de classificação de grafos e nós ao aprender a agregar características sobre a topologia do grafo. No entanto, sua interpretabilidade permanece um desafio crítico. Diferentemente das redes neurais clássicas, as GNNs devem explicar não apenas como as características de entrada são transformadas, mas também como a própria topologia do grafo é explorada. Métodos existentes de interpretabilidade frequentemente dependem de aproximações post-hoc (por exemplo, GNNExplainer, saliência de gradiente) que carecem de garantias de fidelidade, ou de arquiteturas de dois módulos onde um extrator de explicação é desconectado do classificador, permitindo que o classificador ignore a explicação enquanto minimiza a perda. Além disso, GNNs profundas sofrem de patologias como suavização excessiva (colapso das representações dos nós) e esmagamento excessivo (decaimento exponencial da sensibilidade de longo alcance).

Metodologia

Os autores propõem a camada Tikhonov, uma camada de rede neural em grafos projetada para ser interpretável por construção. A inovação central reside em restringir a matriz de propagação do grafo $R$ a uma solução de forma fechada específica derivada de um problema generalizado de regularização Tikhonov em grafos.

O Operador de Propagação

Para um grafo com Laplaciano normalizado $L$, a saída da camada para características de entrada $X$ é dada por:
$$X^{(k+1)} = \sigma \left( R X^{(k)} W \right)$$
onde a matriz de propagação $R$ é definida como:
$$R = (p(L) + Q)^{-1} Q$$
Aqui:

• $L$ é o Laplaciano normalizado do grafo.
• $Q = \text{diag}(q_1, \dots, q_n)$ é uma matriz diagonal aprendível de pontuações de importância de nós estritamente positivas.
• $p(\cdot)$ é um polinômio aprendível satisfazendo $0 < p(\lambda) < 1$ para $\lambda \in [0, 2]$.
• $\sigma$ é uma não-linearidade ponto a ponto e $W$ é uma matriz de pesos.

Interpretação Variacional

O operador $R$ é o minimizador único de forma fechada do problema Tikhonov generalizado:
$$R x = \arg \min_{z \in \mathbb{R}^n} \sum_{i \in V} q_i (x_i - z_i)^2 + z^\top p(L) z$$
Esta formulação troca explicitamente a fidelidade dos dados em nível de nó (ponderada por $q_i$) contra a regularização impulsionada pela topologia (governada por $p(L)$).

• $q_i$ grande: O nó $i$ confia pesadamente em suas próprias características; a saída $z_i$ permanece próxima de $x_i$.
• $q_i$ pequeno: O nó $i$ descarta suas próprias características em favor de uma solução impulsionada pela topologia do grafo (suavidade ou propriedades espectrais específicas definidas por $p$).
• Forma de $p(\lambda)$: Determina a natureza da influência topológica. Um $p$ crescente penaliza altas frequências (favorecendo homofilia/suavidade), enquanto um $p$ decrescente penaliza baixas frequências (favorecendo heterofilia).

Arquitetura e Expressividade

Para manter alta expressividade sem sacrificar a interpretabilidade, a arquitetura emprega uma separação de responsabilidades:

1. A Rede Q: Uma GNN dedicada, potencialmente profunda (por exemplo, ChebNet ou ARMA), que toma o grafo $(G, X)$ como entrada e produz as pontuações de importância dos nós $Q$. Este componente lida com a aprendizagem representacional complexa e adapta $q_i$ a estruturas e características locais do grafo.
2. A Camada Tikhonov: Uma única camada transparente que aplica a propagação $R$. Ela não contém não-linearidades ocultas ou etapas complexas de passagem de mensagens; seus parâmetros são os coeficientes polinomiais de $p$ e as saídas da rede Q.
3. Cabeça: Uma operação de agrupamento global seguida por um MLP para a previsão final.

O modelo suporta extensões multicanal onde múltiplas redes Q e polinômios independentes são usados, embora os experimentos se concentrem no caso de canal único ($J=1$).

Detalhes de Implementação

• Cálculo: Calcular $(p(L) + Q)^{-1}QX$ envolve resolver sistemas lineares. Os autores utilizam Gradiente Conjugado Pré-condicionado (PCG) com um pré-condicionador diagonal (Jacobi) para evitar o custo $O(n^3)$ da inversão densa, alcançando escalabilidade $O(dTKm)$ onde $T$ é o número de iterações.
• Diferenciação: Para evitar armazenar o grafo computacional do solucionador, os autores usam diferenciação implícita, exigindo apenas uma solução adicional de PCG no passo de retropropagação para calcular gradientes em relação a $Q$ e $p$.
• Restrições: O polinômio $p(\lambda)$ é parametrizado usando polinômios de Bernstein com ativações sigmóide para impor estritamente $0 < p(\lambda) < 1$. As pontuações $q_i$ são mapeadas para valores estritamente positivos através de uma função de limitação no espaço logarítmico.

Contribuições Principais e Propriedades Teóricas

1. Interpretabilidade Incorporada: O par $\{ \{q_i\}_{i \in V}, p(\cdot) \}$ constitui uma explicação direta e fiel. Um $q_i$ grande indica dependência de características; um $q_i$ pequeno indica dependência topológica. A forma de $p$ revela o viés espectral (homofilia, heterofilia, passagem de banda).
2. Acoplamento Estrutural: Os autores provam (Proposição 3.6) que o mapa $Q \mapsto R$ é injetor. Diferentemente de métodos post-hoc, alterar a explicação ($Q$) necessariamente altera o operador de propagação ($R$), garantindo que a explicação seja fiel ao cálculo.
3. Expressividade: A camada é mostrada como densa no espaço de filtros espectrais contínuos no caso homogêneo. Com $Q$ heterogêneo, ela estende estritamente a expressividade além dos filtros espectrais tradicionais ao quebrar a estacionariedade (Proposição 3.3).
4. Mitigação de Patologias de GNN:
   • Suavização Excessiva: Evitada pelo uso de uma única camada e pela invertibilidade de $p(L) + Q$. O colapso de nós ocorre apenas se o modelo deliberadamente levar todos $q_i \to 0$.
   • Esmagamento Excessivo: A taxa de decaimento da sensibilidade de longo alcance $|R_{ij}|$ é governada pelo número de condição $\kappa$ do sistema, que depende da $Q$ aprendida. O modelo pode aprender a reduzir $\kappa$ (ao diminuir $q_i$ específicos) para aumentar a sensibilidade de longo alcance onde necessário, trocando efetivamente precisão local por alcance global.

Resultados Experimentais

O modelo foi avaliado em benchmarks sintéticos e padrão, demonstrando tanto desempenho quanto interpretabilidade:

• Tarefas Sintéticas Controladas:
  • Colors-3: A tarefa depende exclusivamente de características de nós. O modelo aprendeu $q_i$ grandes em todos os lugares, ignorando efetivamente a topologia e comportando-se como um MLP, identificando corretamente que as características impulsionam a previsão.
  • Distância de Clique: Uma tarefa puramente estrutural. O modelo aprendeu $q_i$ pequenos para nós de caminho (confiando na topologia para perceber distância) e $q_i$ grandes para nós de clique (âncoras), alcançando 100% de precisão.
  • Triângulos: Uma tarefa estrutural detectando triângulos. O modelo atribuiu $q_i$ pequenos geralmente, mas $q_i$ maiores aos vértices do triângulo, apontando o motivo sem supervisão.
• CSBM (Modelo de Bloco Estocástico Contextual): O modelo rastreou com sucesso o limiar de transição de fase teórico para recuperação. Os valores de $q_i$ aprendidos transicionaram suavemente de regimes dominados por características ($q_i$ grandes) para regimes dominados por topologia ($q_i$ pequenos), identificando corretamente a fonte do sinal em regimes mistos.
• ECHO-diam (Propagação de Longo Alcance): Em uma tarefa de regressão de diâmetro de grafo, o modelo alcançou um Erro Absoluto Médio (MAE) de 1,17, superando baselines de GNN profundas (~1,6) e aproximando-se do desempenho de Transformers (1,05). A explicação revelou que o modelo atribuiu $q_i$ grandes a nós periféricos (extremidades) e $q_i$ pequenos a nós internos, usando o contraste entre extremidades ancoradas e interior suavizado para estimar o diâmetro.

Significado e Alegações

O artigo alega que a camada Tikhonov oferece uma abordagem nova para a interpretabilidade de GNNs ao projetar a camada para ser autoexplicável em vez de recuperar explicações post-hoc.

• Fidelidade: A explicação é o próprio modelo; não há subgrafo desconectado ou aproximação.
• Granularidade: Fornece uma resposta contínua e espacialmente resolvida (valores de $q_i$ graduados) em vez de seleção binária de subgrafos.
• Desempenho: O modelo iguala ou supera baselines opacas (como GIN, GAT e Transformers) em várias tarefas enquanto fornece insights sobre como a tarefa é resolvida (por exemplo, distinguindo entre raciocínio baseado em características e baseado em topologia).
• Limitações: Os autores reconhecem que algumas explicações podem ser complexas para humanos interpretarem e que o custo computacional do PCG pode ser alto para tarefas que exigem interações de longo alcance (embora sugiram álgebra linear numérica aleatória como uma direção futura para aproximação).

O trabalho estabelece que é possível restringir camadas de GNN a formas variacionais específicas para ganhar interpretabilidade sem sacrificar a capacidade de aprender filtros de grafos complexos e não estacionários.