Beyond Edge Deletion: A Comprehensive Approach to Counterfactual Explanation in Graph Neural Networks

Este trabalho apresenta o XPlore, uma nova técnica baseada em gradientes que expande o espaço de busca para explicações contrafactuais em Redes Neurais em Grafos (GNNs) ao permitir não apenas a exclusão de arestas, mas também a inserção de arestas e perturbações de características dos nós, resultando em explicações mais coerentes e fiéis com melhorias significativas em relação aos métodos atuais.

O essencial

Imagine que você tem um oráculo mágico (uma Inteligência Artificial muito avançada) que consegue prever coisas incríveis, como se uma molécula será tóxica ou se uma transação bancária é fraude. O problema é que esse oráculo é um "caixa-preta": ele dá a resposta, mas não explica por que chegou a essa conclusão. É como se ele dissesse "Não compre este remédio" sem dizer qual ingrediente é o venenoso.

Para confiar nessa IA, precisamos de uma explicação. E o melhor tipo de explicação é o "E se...?" (o que chamamos de explicação contrafactual).

O Problema: O "Detetive" que só sabe apagar

Até agora, a maioria dos métodos para explicar essas IAs funcionava como um detetive muito teimoso que só sabia uma coisa: apagar coisas.

• Se a IA disse "Isso é venenoso", o detetive tentava apagar uma ligação entre dois átomos. Se a IA mudasse de ideia e dissesse "Ah, não é venenoso", ele achava que tinha resolvido.
• O limite: E se o veneno não fosse uma ligação que precisava ser apagada, mas sim uma nova ligação que precisava ser criada? Ou se o problema fosse a cor de um átomo, e não a sua conexão? O detetive antigo ficava travado, porque só sabia apagar.

A Solução: O XPlore (O Explorador Completo)

Os autores deste paper criaram uma nova ferramenta chamada XPlore. Pense nele como um arquiteto de realidade alternativa muito mais esperto e flexível.

Em vez de apenas apagar coisas, o XPlore tem três poderes:

1. Apagar conexões (como o detetive antigo).
2. Criar novas conexões (adicionar pontes onde não existiam).
3. Mudar as propriedades (pintar um átomo de outra cor ou mudar seu peso).

A Analogia da Receita de Bolo:
Imagine que a IA disse: "Este bolo vai explodir a cozinha!" (Previsão: Perigoso).

• Método Antigo: Tenta tirar um ovo da receita. Se o bolo ainda explodir, ele tenta tirar farinha. Ele só sabe tirar ingredientes.
• XPlore: Pensa: "E se eu adicionar um pouco de bicarbonato? E se eu trocar o açúcar por adoçante? E se eu conectar a massa de uma forma diferente?"
  O XPlore testa todas essas combinações (adicionar, remover, mudar) até encontrar a mínima mudança possível que transforma o "Bolo Explosivo" em um "Bolo Seguro".

Como ele funciona? (O GPS da Mudança)

O XPlore não chuta aleatoriamente. Ele usa um GPS baseado em gradientes.
Imagine que você está no topo de uma montanha (a decisão da IA) e quer chegar ao vale do outro lado (a decisão oposta) gastando o mínimo de energia possível.

• O XPlore olha para a "inclinação" da montanha. Ele sabe exatamente para onde dar um pequeno passo para descer mais rápido.
• Ele usa essa inclinação para decidir: "Preciso adicionar uma aresta aqui" ou "Preciso mudar esse número ali".
• Ele faz isso de forma automática e muito rápida, sem precisar de um "segundo cérebro" para aprender, apenas usando a lógica da própria IA original.

Por que isso é importante? (A Fidelidade)

Muitos métodos antigos criavam explicações que pareciam fazer sentido matematicamente, mas eram estranhas para o mundo real (chamado de Out-of-Distribution).

• Exemplo: Para explicar por que uma molécula é tóxica, o método antigo poderia sugerir uma molécula com 50 átomos de hidrogênio grudados no mesmo lugar. Isso é quimicamente impossível! A IA aceitaria, mas um químico saberia que é besteira.
• O XPlore: Usa uma régua chamada Semelhança Cosseno. Em vez de apenas contar quantas linhas foram apagadas, ele pergunta: "Essa nova versão da molécula ainda parece com a original em termos de 'alma' e estrutura?"
  • Ele garante que a explicação seja mínima (mudanças pequenas) e fiel (ainda faz sentido no mundo real).

Os Resultados

Os autores testaram o XPlore em 18 cenários diferentes (desde moléculas químicas até redes sociais e imagens de impressões digitais).

• Eles venceram: O XPlore foi muito mais bem-sucedido em encontrar explicações válidas do que os melhores métodos atuais (cerca de 15% a 50% melhor, dependendo do teste).
• Velocidade: Ele é rápido, quase tão rápido quanto os métodos antigos, mas muito mais completo.

Resumo em uma frase

O XPlore é como um tradutor de IA que não apenas diz "o que" a máquina pensou, mas simula o "E se?" de forma criativa (adicionando, removendo e mudando coisas), garantindo que a explicação seja a menor possível e que ainda faça sentido no mundo real, ajudando humanos a confiar e entender decisões complexas de Inteligência Artificial.

Resumo técnico

Título: Além da Exclusão de Arestas: Uma Abordagem Abrangente para Explicação Contrafactual em Redes Neurais em Grafos

1. Problema e Motivação

As Redes Neurais em Grafos (GNNs) são amplamente utilizadas em domínios de alto risco, como descoberta de fármacos, biologia molecular e detecção de fraudes financeiras. No entanto, sua natureza de "caixa preta" dificulta a interpretabilidade e a confiança nas decisões tomadas.

• Limitação das Abordagens Atuais: A maioria dos métodos existentes de explicação contrafactual (CF) para GNNs foca exclusivamente na exclusão de arestas (edge deletion) para alterar a previsão do modelo. Essa restrição limita o espaço de busca, impedindo a descoberta de explicações que requerem a adição de arestas ou a modificação de características dos nós (node features) para inverter a classificação de forma mínima e válida.
• Desafio da Distribuição: Métodos que realizam grandes alterações estruturais podem gerar instâncias "fora da distribuição" (Out-of-Distribution - OOD), onde a explicação perde o significado semântico original, mesmo que altere a previsão do modelo.

2. Metodologia: XPlore

O artigo propõe o XPlore, uma nova técnica que expande significativamente o espaço de busca para explicações contrafactuais, operando sob um único framework baseado em gradientes.

Principais Componentes:

1. Perturbação Abrangente de Entrada:

   • Diferente dos métodos anteriores, o XPlore permite simultaneamente:
     • Adição e Remoção de Arestas: O modelo não apenas "apaga" conexões, mas pode inserir novas arestas se isso for necessário para mudar a classe prevista.
     • Perturbação de Características dos Nós: O método ajusta os valores das características (features) dos nós, permitindo mudanças contínuas ou binárias (via gating), o que é crucial em domínios como química molecular (ex: alterar a carga de um átomo).
   • Mecanismo de Troca de Papéis: Para permitir a adição de arestas, o algoritmo inverte a lógica tradicional. Em vez de multiplicar a matriz de adjacência original por uma máscara de exclusão, ele inicializa uma matriz de perturbação com as arestas originais e uma matriz de "todos conectados" (ones), permitindo que o gradiente adicione ou remova conexões livremente.

2. Otimização Guiada por Gradiente:

   • O XPlore trata a GNN treinada como um "oráculo" fixo.
   • Utiliza os gradientes direcionais da função de perda interna do modelo para guiar as perturbações mínimas necessárias.
   • Função de Perda: Combina uma perda de previsão ($L_{pred}$), que força a mudança de classe, e uma perda de distância ($L_{dist}$), que penaliza alterações excessivas na estrutura e nas características.
   • Utiliza o estimador Straight-Through (STE) para permitir o backpropagation através de operações não diferenciáveis (como a binarização de arestas).

3. Métrica de Fidelidade Semântica (Cosine Similarity):

   • Para mitigar o problema de instâncias OOD, o artigo introduz uma métrica baseada na similaridade de cosseno entre os embeddings aprendidos do grafo original e do contrafactual.
   • Isso garante que, além de mudar a previsão, a explicação mantenha a coerência semântica e estrutural com o grafo original, preservando as pistas discriminativas da classe.

3. Contribuições Principais

1. Espaço de Perturbação Completo: O primeiro framework a unir adição/remoção de arestas e perturbação de características de nós em uma única otimização baseada em gradiente, superando a limitação de métodos que só deletam arestas.
2. Otimização Localmente Ótima: Garante que as explicações encontradas sejam as mais próximas no espaço de perda, alinhadas com as fronteiras de decisão aprendidas pelo oráculo.
3. Mitigação de OOD: A introdução da métrica de similaridade de cosseno e a capacidade de fazer ajustes finos (adição de arestas e ajuste de features) reduzem a geração de explicações sem sentido semântico.
4. Desempenho Empírico Superior: Validação extensiva em 13 conjuntos de dados reais e 5 sintéticos.

4. Resultados Experimentais

O XPlore foi comparado com o estado da arte (SoTA), incluindo métodos como CF-GNNExpl, CF2, CLEAR, RSGG-CE e D4Explainer.

• Validade (Validity): O XPlore obteve a melhor taxa de sucesso em 17 de 18 conjuntos de dados, com uma melhoria média de +56,3% em relação aos baselines. Em muitos casos (ex: TCR, BAS, TG), atingiu 100% de validade, enquanto outros métodos falharam em gerar explicações válidas.
• Fidelidade (Fidelity): Demonstrou uma melhoria de +52,8% na fidelidade, indicando que as explicações são mais fiéis ao comportamento real do modelo e às características verdadeiras dos dados.
• Eficiência Computacional: O método mantém um tempo de execução competitivo, sendo leve e não exigindo treinamento adicional de modelos generativos complexos.
• Análise de Distribuição: Visualizações t-SNE mostram que o XPlore consegue gerar contrafactuais que se posicionam corretamente na distribuição da classe alvo (ex: convertendo um grafo de "Árvore" para "Ciclo" mantendo a estrutura semântica), enquanto outros métodos frequentemente falham ou permanecem na distribuição original explorando efeitos OOD.

5. Significado e Conclusão

O trabalho "Beyond Edge Deletion" representa um avanço significativo na explicabilidade de GNNs. Ao demonstrar que a simples exclusão de arestas é insuficiente para explicar decisões complexas em grafos, o XPlore oferece uma lente mais rica e matizada para entender o comportamento dos modelos.

• Impacto Prático: Em aplicações críticas como a descoberta de medicamentos, a capacidade de sugerir a adição de uma ligação química ou a alteração de uma propriedade atômica (em vez de apenas remover partes da molécula) é vital para a geração de hipóteses acionáveis e quimicamente válidas.
• Robustez: O método oferece explicações mais robustas e menos suscetíveis a manipulações adversariais, ao garantir que as mudanças mínimas preservem a semântica do grafo.

Em resumo, o XPlore estabelece um novo padrão para a geração de explicações contrafactuais em grafos, equilibrando a necessidade de minimalidade das alterações com a fidelidade semântica e a abrangência do espaço de busca.