Resumo Técnico: TN-SHAP-G

Definição do Problema

Explicar previsões de redes neurais em grafos (GNNs) de caixa-preta exige atribuir importância a nós individuais e suas interações. Embora os valores de Shapley e índices de interação de ordem superior ofereçam atribuições axiomáticas e fundamentadas, sua computação exata é intratável para grafos, escalando como $O(2^n)$, onde $n$ é o número de nós. Os métodos de aproximação existentes enfrentam trade-offs significativos: explicadores específicos de arquitetura (ex: GNNExplainer) não se aplicam a modelos de caixa-preta genéricos, enquanto abordagens baseadas em amostragem (ex: GraphSVX, SHAP-IQ) exigem milhares de avaliações do modelo e sofrem de alta variância, particularmente para interações de ordem superior. Além disso, esses métodos de amostragem frequentemente falham em escalar para grafos maiores onde a enumeração exata é impossível.

Metodologia: TN-SHAP-G

Os autores propõem o TN-SHAP-G, um framework que explora as propriedades estruturais de entradas estruturadas em grafos para computar valores de Shapley e interações de forma eficiente e determinística. A ideia central é aprender um substituto (surrogate) de rede de tensores (TN) compacto e alinhado ao grafo que aproxime o comportamento de entrada mascarada do preditor.

1. O Jogo de Grafo Mascarado

O método formaliza a explicação de grafos como um jogo cooperativo induzido pelo mascaramento de nós. Para um grafo de entrada fixo $G=(V, E)$ com características $X$ e uma linha de base $X^0$, uma coalizão $S \subseteq V$ define uma matriz de características mascarada $X_S$, onde os nós em $S$ retêm suas características originais e os nós fora de $S$ são substituídos por características de linha de base. O valor do jogo é $\nu(S) = f(G, X_S)$, onde $f$ é o preditor de caixa-preta.

2. Extensão Multilinear e Contração de Tensores

A computação direta dos valores de Shapley requer a soma sobre $2^n$ coalizões. Os autores utilizam a extensão multilinear $\hat{\nu}(z)$, uma relaxação contínua do jogo discreto definido em $z \in [0, 1]^n$.

• Formulação de Tensor: A extensão multilinear pode ser expressa exatamente como uma contração de tensor: $\hat{\nu}(z) = \sum_{s \in \{0,1\}^n} T_s \prod_{v=1}^n b_v(z_v)^{s_v}$, onde $T$ é o tensor de coalizão e $b_v(z_v)$ são vetores seletores de Bernoulli.
• Recuperação Determinística: Valores de Shapley e índices de interação correspondem a integrais de derivadas parciais de $\hat{\nu}$ ao longo da diagonal $z = t\mathbf{1}$. Como $\hat{\nu}$ é multilinear, essas derivadas são polinômios univariados de grau no máximo $n-1$. Assim, atribuições exatas podem ser recuperadas via interpolação de Vandermonde a partir de um pequeno número de pontos de sondagem, eliminando a variância de Monte Carlo.

3. Substituto de Rede de Tensores Alinhado ao Grafo

Como o tensor de coalizão completo $T$ possui $2^n$ entradas, o TN-SHAP-G aprende um substituto de rede de tensores alinhada ao grafo $\hat{\nu}$ para aproximar a extensão multilinear.

• Topologia: A topologia da TN espelha o grafo de entrada $G$. Cada nó $v$ corresponde a um tensor central $A^{(v)}$ com um índice físico (codificando a participação na coalizão) e índices de ligação conectando-se aos vizinhos.
• Expressividade: A dimensão de ligação $\chi$ controla a capacidade de fluxo de informação através dos separadores do grafo. Os autores provam que, para jogos com baixo cut-rank através de separadores de grafo (uma propriedade de muitos padrões de dependência local em GNNs), esta estrutura alinhada ao grafo alcança maior expressividade com menos parâmetros do que fatorações baseadas em cadeias como Tensor Trains (TT), que sofrem de inflação de rank em grafos cíclicos ou complexos.
• Treinamento: O substituto é treinado via minimização do risco empírico em um pequeno conjunto de coalizões amostradas ($M \ll 2^n$). Garantias teóricas mostram que o orçamento de consultas necessário escala quase linearmente com o número de nós para grafos de grau limitado.

4. Inferência

Uma vez treinado, o substituto permite a computação determinística de:

• Valores de Shapley de primeira ordem: Via integração 1D da derivada da diagonal.
• Interações de ordem superior: Via derivadas parciais mistas e integração.
  Todas as quantidades são computadas a partir do único substituto treinado, sem consultas adicionais ao modelo de caixa-preta.

Principais Contribuições

1. Representação Alinhada ao Grafo com Princípios: Introdução de um substituto de rede de tensores que comprime a tabela de valores de coalizão exponencial em uma representação multilinear de baixo rank e alinhada ao grafo. Isso alinha o viés indutivo do substituto com os padrões de dependência local em preditores de grafos.
2. Computação Determinística Amortizada: Aproveitamento da estrutura multilinear para computar valores de Shapley e interações via interpolação de Vandermonde de forma fechada. Isso requer apenas $O(n)$ avaliações do substituto e não introduz variância de Monte Carlo. Um único substituto amortiza a computação de todos os índices de primeira e ordem superior.
3. Garantias Teóricas:
   • Prova de que o substituto aprendido determina unicamente a extensão multilinear, garantindo a recuperação exata das atribuições no substituto.
   • Caracterização da expressividade via argumentos de cut-rank, provando que TNs alinhadas ao grafo superam fatorizações de cadeia (como TT) em termos de desempenho.
   • Limites de complexidade de consulta ao professor (teacher-query) quase lineares para grafos de grau limitado.
   • Garantias de estabilidade vinculando o erro de aproximação do jogo ao erro de Shapley.
4. Desempenho Empírico: Demonstrou alta precisão e escalabilidade em benchmarks moleculares, alcançando $>0,99$ de similaridade de cosseno com valores de Shapley exatos com apenas 50 avaliações do modelo (10–100$\times$ menos que os baselines).

Resultados Experimentais

Os autores avaliaram o TN-SHAP-G em benchmarks moleculares (Mutagenicity, Benzene) e grafos de proteínas (PROTEINS).

• Corretude: Em grafos pequenos ($n \le 20$), o TN-SHAP-G aproxima-se de valores de Shapley exatos (O1) e índices de interação (O2), superando significativamente o GraphSVX e a amostragem por permutação tanto em precisão quanto em variância.
• Eficiência de Consulta: O TN-SHAP-G alcança alta precisão de atribuição com 10–100$\times$ menos consultas ao modelo do que estimadores baseados em amostragem (SHAP-IQ, GraphSVX).
• Escalabilidade: O método escala eficientemente para grafos com até 600 nós usando uma arquitetura de substituto baseada em coalescência, enquanto métodos de enumeração exata e amostragem tornam-se impraticáveis.
• Ablação de Estrutura: TNs alinhadas ao grafo superam consistentemente os substitutos Tensor Train (TT) sob condições de parâmetros equivalentes, confirmando a vantagem teórica de fatorizações de topologia alinhada.
• Proxy de Fidelidade: Uma forte correlação foi observada entre o $R^2$ de teste do substituto e a similaridade de cosseno dos valores de Shapley recuperados, validando o $R^2$ como um proxy prático para a precisão da atribuição.

Significância e Alegações

O artigo afirma que o TN-SHAP-G avança o estado da arte na explicabilidade de grafos ao fornecer um framework baseado em princípios e agnóstico ao modelo que supera a complexidade exponencial da computação de Shapley. Ao explorar a estrutura de baixo rank inerente aos jogos cooperativos estruturados em grafos, o método permite a atribuição determinística e livre de variância com complexidade de consulta quase linear.

Os autores enfatem que esta abordagem democratiza o acesso a métodos de explicação rigorosos para profissionais com recursos computacionais limitados, particularmente em domínios de alto risco como descoberta de fármacos e predição de propriedades moleculares. O framework é flexível, suportando várias semânticas de jogo (ex: mascaramento de nós, remoção de nós, valores de Myerson) e tipos de características, estendendo-se além das GNNs de passagem de mensagem padrão para outros preditores de grafos. O trabalho posiciona as redes de tensores não apenas como ferramentas de compressão, mas como um mecanismo fundamental para análise de jogos tratável em dados estruturados.