Resumo Técnico: GRAPHLCP

Declaração do Problema

Redes Neurais em Grafos (GNNs) estão cada vez mais sendo implantadas em domínios de alto risco, como descoberta de medicamentos, previsão do tempo e detecção de fraudes, tornando necessária uma quantificação confiável da incerteza (UQ). A Previsão Conformal (CP) oferece um framework livre de distribuição para construir previsões em forma de conjuntos com garantias de amostra finita. No entanto, aplicar CP a GNNs apresenta desafios únicos:

1. Dependências Estruturais: Nós em grafos são naturalmente dependentes, violando as suposições padrão de independência e distribuição idêntica (i.i.d.) exigidas para a CP clássica.
2. Limitações de Embeddings: Métodos de CP localizados existentes para grafos frequentemente dependem da proximidade no espaço de embeddings (por exemplo, estimativa de densidade de kernel em embeddings de GNN) para definir vizinhanças locais. Essa abordagem é frequentemente pouco confiável devido a:
   • Suavização Excessiva: A passagem de mensagens profunda reduz a variância das medidas de similaridade, tornando os embeddings indiscriminativos.
   • Esquadrinhamento Excessivo: Gargalos topológicos restringem o fluxo de informações globais, particularmente sob heterofilia.
   • Subconfiança: GNNs frequentemente exibem separabilidade insuficiente nas representações aprendidas.
3. Ineficiência das Soluções Existentes: Métodos de CP específicos para grafos atuais ou dependem do treinamento de modelos auxiliares (aumentando a sobrecarga computacional) ou utilizam partições estruturais rígidas (por exemplo, agrupamento rígido) que falham em capturar heterofilia local de granularidade fina. Consequentemente, os métodos existentes frequentemente produzem conjuntos de previsão excessivamente conservadores ou mal localizados em topologias complexas.

Metodologia: GRAPHLCP

Os autores propõem o GRAPHLCP, um framework de Previsão Conformal localizado baseado em proximidade projetado para incorporar explicitamente a topologia do grafo e as dependências inter-nós nas etapas de localização e ponderação. O método opera em um cenário transduzido onde a GNN é pré-treinada e congelada. O framework consiste em quatro etapas principais:

1. Densificação Consciente de Recursos

Para mitigar o viés de localidade em grafos esparsos e capturar dependências semânticas de longo alcance, os autores introduzem uma etapa de densificação antes do cálculo do kernel.

• Projeção PCA: Os embeddings dos nós são primeiro projetados via Análise de Componentes Principais (PCA) para desacoplar dimensões de recursos correlacionadas e condensar o espaço, abordando o ruído e a redundância causados pela suavização excessiva.
• Kernel Anisotrópico Adaptativo: Um kernel Gaussiano anisotrópico é construído usando os embeddings transformados por PCA. A largura de banda é adaptada com base nos autovalores da matriz de covariância para levar em conta escalas variadas entre dimensões.
• Aumento de Arestas: Novas arestas são adicionadas à matriz de adjacência do grafo se a similaridade entre nós não conectados (calculada via kernel Gaussiano) exceder um limiar dinâmico $\tau_d$. Esse limiar é ajustado automaticamente com base na razão de homofilia do grafo para equilibrar a adição de arestas informativas contra a introdução de ruído.

2. Kernel PageRank Personalizado (PPR)

Em vez de depender exclusivamente de distâncias de embeddings, o GRAPHLCP utiliza PPR para modelar proximidade estrutural.

• Localização: O PPR captura influência de múltiplos saltos enquanto mantém a localidade através de uma probabilidade de reinício ($\beta$). Ele fornece uma noção suave e probabilística de proximidade que se alinha naturalmente com a CP ponderada.
• Amostragem: Para um nó de teste, um nó âncora é amostrado a partir da distribuição induzida por PPR centrada no nó de teste. Isso garante que nós próximos exerçam maior influência na estimativa do quantil.
• Ponderação: Nós de calibração e de teste são ponderados de acordo com sua proximidade estrutural ao âncora amostrado. Os autores exploram a simetria normalizada pelo grau do PPR ($d_i H(u_i, u_j) = d_j H(u_j, u_i)$) para calcular pesos de forma eficiente, mesmo quando o número de amostras de calibração excede o número de amostras de teste.

3. Integração de Previsão Conformal Localizada Randomizada (RLCP)

O GRAPHLCP adapta o framework RLCP. Ao amostrar um nó âncora $\tilde{u}_{n+1}$ a partir da distribuição PPR do nó de teste $u_{n+1}$, o método constrói um conjunto de previsão com base em um quantil ponderado de escores de não-conformidade. Os pesos são derivados das pontuações PPR em relação ao âncora amostrado, permitindo que o método se adapte ao contexto local do grafo.

4. Construção de Previsão

O conjunto de previsão final $\hat{C}_n(u_{n+1})$ é construído como o conjunto de rótulos $y$ tais que o escore de não-conformidade $s(u_{n+1}, y)$ seja menor ou igual a um quantil ponderado $\hat{q}_{1-\alpha}$. Esse quantil é calculado usando os pesos derivados do kernel PPR e os escores de não-conformidade do conjunto de calibração.

Contribuições Principais

1. Localização Consciente de Estrutura: O artigo preenche a lacuna entre localização estrutural e baseada em recursos, substituindo a proximidade baseada apenas em embeddings por um kernel baseado em PPR. Isso incorpora explicitamente a topologia do grafo no processo de ponderação conformal.
2. Densificação Consciente de Recursos: Uma etapa de pré-processamento inovadora que aumenta a topologia do grafo usando similaridade de embeddings (via PCA e kernels anisotrópicos adaptativos) para mitigar a esparsidade e capturar dependências de longo alcance sem depender da ponderação contínua potencialmente ruidosa de embeddings.
3. Esquema de Ponderação Eficiente: O método fornece uma maneira eficiente de calcular pesos baseados em PPR para grafos não direcionados, aproveitando a simetria normalizada pelo grau, evitando a ineficiência computacional de calcular vetores PPR completos para grandes conjuntos de calibração.
4. Validade Teórica: A abordagem mantém as garantias de trocabilidade exigidas para cobertura marginal em cenários transduzidos, enquanto visa melhorar a cobertura condicional de teste relaxada.

Resultados Experimentais

Os autores avaliaram o GRAPHLCP em sete conjuntos de dados de regressão de nós e oito conjuntos de dados de classificação de nós (incluindo redes de citação, co-compra da Amazon e conjuntos de dados geográficos).

• Cobertura Marginal: Todos os métodos, incluindo o GRAPHLCP, satisfizeram a taxa de não-cobertura alvo ($\alpha = 0.1$), confirmando a validade da abordagem.
• Cobertura Condicional (WSC): Nos diagnósticos de Pior Caso de Lâmina (WSC), que buscam adversariamente a cobertura mínima através de direções de projeção, o GRAPHLCP alcançou os melhores ou segundos melhores resultados na maioria dos conjuntos de dados, superando baselines como CalLCP, RLCP e SCP.
• Cobertura Baseada em Grupos: O GRAPHLCP demonstrou cobertura superior em partições baseadas em homofilia, agrupamento de recursos, coeficiente de agrupamento e grau do nó. O método foi particularmente eficaz em regiões heterofílicas onde métodos padrão lutaram.
• Eficiência de Previsão: Enquanto o CalLCP frequentemente produzia conjuntos de previsão excessivamente grandes (sobre-cobertura), o GRAPHLCP alcançou comprimentos de previsão normalizados favoráveis, oferecendo um melhor compromisso entre cobertura e tamanho do conjunto.
• Estudos de Ablação:
  • Substituir o kernel PPR por um kernel Gaussiano (GSS) resultou em cobertura mais baixa e conjuntos de previsão maiores, confirmando a importância da localização consciente de estrutura.
  • A etapa de densificação foi identificada como o componente mais significativo, particularmente para tarefas de regressão.
  • A projeção PCA mostrou-se crucial para mitigar os efeitos negativos de recursos de embeddings correlacionados.

Significado e Alegações

O artigo afirma que o GRAPHLCP aborda com sucesso as limitações dos métodos de CP de grafos existentes ao modelar explicitamente dependências estruturais. Ao desacoplar pesos de codificadores de GNN potencialmente com perdas e utilizar um kernel baseado em PPR, o método cria um "caminho residual de menor ruído" para quantificação de incerteza.

Os autores afirmam que o GRAPHLCP garante cobertura marginal com amostras finitas enquanto atinge eficientemente uma cobertura condicional de teste favorável em vários cenários de condicionamento. Eles destacam que o método é particularmente robusto em topologias complexas onde similaridades baseadas em embeddings falham devido à suavização excessiva ou esquadrinhamento excessivo. O trabalho sublinha a necessidade de localização consciente de estrutura para UQ eficaz em grafos, indo além da dependência exclusiva da proximidade no espaço de recursos. Os autores notam modestamente que direções futuras incluem a extensão deste framework para grafos dinâmicos com topologias em evolução.