RAwR: Role-Aware Rewiring via Approximate Equitable Partition

Resumo Técnico: RAwR: Reencaminhamento Consciente de Função via Partição Equitativa Aproximada

Declaração do Problema
Redes Neurais em Grafos (GNNs) demonstraram eficácia em tarefas de classificação de nós baseadas em informações de vizinhança local. No entanto, seu desempenho frequentemente degrada quando as tarefas de previsão dependem de interações de longo alcance. Essa limitação é atribuída ao esmagamento excessivo (oversquashing), um fenômeno onde gargalos estruturais restringem a propagação de sinais através da topologia da rede, comprimindo sinais de longo alcance antes que eles alcancem o nó alvo. Embora os métodos existentes de reencaminhamento de grafos (por exemplo, Nó Mestre, abordagens baseadas em curvatura, métodos espectrais) visem aliviar o esmagamento excessivo melhorando a propagação global de sinais, eles frequentemente falham em distinguir quais caminhos de comunicação de longo alcance são estruturalmente relevantes para tarefas específicas subsequentes. Em grafos heterofílicos ou cenários onde as classes de nós refletem funções estruturais em vez de adjacência imediata, o reencaminhamento indiscriminado pode não ser ótimo.

Metodologia
Os autores introduzem o RAwR (Reencaminhamento Consciente de Função), um framework computacionalmente eficiente e agnóstico ao modelo que aumenta o grafo de entrada com um grafo quociente derivado de Partições Equitativas Aproximadas (AEPs).

1. Partições Equitativas Aproximadas (AEPs):

   • Uma partição equitativa agrupa nós que possuem o mesmo número de vizinhos em cada bloco da partição. Isso induz um grafo quociente que resume exatamente as interações função-a-função.
   • O RAwR utiliza uma $\epsilon$-AEP, que relaxa a equivalência exata de funções através de um parâmetro de tolerância $\epsilon$. Isso permite o agrupamento de nós com funções estruturais semelhantes (mas não idênticas), tornando a abordagem robusta a ruídos em grafos do mundo real.
   • A partição é computada eficientemente usando o algoritmo $\epsilon$-BE em tempo polinomial.

2. Variantes de Reencaminhamento:
   Dado um grafo de entrada $G=(V, E)$ e uma $\epsilon$-AEP com matriz indicadora $R$ e matriz quociente $Q$, o RAwR constrói uma matriz de adjacência aumentada. Duas variantes específicas são propostas:

   • RepNodes: Conecta cada nó original a um único nó virtual representativo (VN) correspondente à sua função estrutural. Isso cria caminhos de comunicação de dois saltos entre nós que são topologicamente distantes, mas estruturalmente semelhantes. A matriz quociente é definida como zero ($Q=0$).
   • RepEdges: Além de conectar nós aos seus representantes, esta variante conecta os VNs representativos entre si de acordo com o grafo quociente não ponderado ($\bar{Q}$), permitindo comunicação entre funções que interagem.

3. Fundamentação Teórica (Análise Professor-Aluno):
   O artigo emprega um modelo professor-aluno de GNNs lineares para analisar o impacto do reencaminhamento.

   • Suposição: Rótulos verdadeiros são gerados por uma GNN "professora" operando em uma estrutura latente (o grafo aumentado pelo RAwR), enquanto uma GNN "aluno" tenta aprender a partir do grafo observado.
   • Levantamento Espectral de Função (SRL): A análise deriva um limite superior para o erro do aluno, levando à formulação do SRL, uma métrica definida como $\text{SRL} = \rho \sum_{j=1}^k \omega_j \Delta_j^2$. Aqui, $\rho$ mede a energia dos rótulos no subespaço de funções, $\Delta_j$ representa a diferença nos autovalores relevantes para funções entre os grafos original e reencaminhado, e $\omega_j$ são pesos de função.
   • Seleção Heurística: Uma heurística prática, SRL$^*$, é proposta para selecionar o parâmetro de tolerância $\epsilon$ ótimo. Ela combina o SRL com a métrica de Similaridade de Classe de Vizinhos a 2 Saltos (2NCS) para considerar casos onde os rótulos podem não residir estritamente no subespaço de funções.

Principais Contribuições

1. Framework RAwR: Um novo método de reencaminhamento que roteia informações através de caminhos estruturalmente significativos (funções estruturais) em vez de apenas melhorar a propagação global. Ele recupera a técnica do Nó Mestre como um caso limite (partição totalmente colapsada), mas oferece granularidade controlável via $\epsilon$.
2. Evidência Estrutural: Demonstração de que o RAwR reduz a resistência efetiva média do grafo de entrada, fornecendo evidência estrutural de que ele alivia gargalos de propagação de longo alcance independentemente da arquitetura da GNN subsequente.
3. Análise Teórica: Uma derivação formal usando um modelo professor-aluno que elucida como o reencaminhamento baseado em funções modifica a resposta espectral de modelos de passagem de mensagens. Isso leva à métrica SRL para selecionar partições ótimas.
4. Complementaridade: Evidência de que o RAwR não é apenas competitivo com soluções ao nível da arquitetura (como GRAIN) projetadas para abordar o esmagamento excessivo, mas também complementar, melhorando ainda mais o desempenho quando aplicado sobre tais modelos.

Resultados Experimentais
Os autores avaliaram o RAwR em uma suíte diversificada de benchmarks, incluindo homofílicos (por exemplo, Cora, Citeseer), heterofílicos (por exemplo, Chameleon, Squirrel) e conjuntos de dados sintéticos de longo alcance (ECHO).

• Desempenho: O RAwR alcança a melhor classificação média entre os métodos de reencaminhamento comparados (incluindo BORF, FOSR, SDRF, JDR, ComFy, TRIGON e Nó Mestre) em tarefas de classificação de nós.
• Ganhos de Longo Alcance e Heterofilia: As melhorias mais significativas são observadas em conjuntos de dados heterofílicos e de longo alcance (por exemplo, ECHO), onde a passagem de mensagens local é insuficiente. Por exemplo, no conjunto de dados "Caterpillar" do ECHO sem características de nós, a precisão melhorou de 38,82% (linha de base) para 76,47% com RepNodes.
• Estudos de Ablação:
  • RepNodes vs. RepEdges: RepNodes geralmente performa melhor em benchmarks do mundo real, sugerindo que a comunicação intra-função rápida é a principal fonte de melhoria.
  • Partições Aleatórias: Comparar o RAwR com partições aleatórias com o mesmo número de nós virtuais mostra que os ganhos são impulsionados pela atribuição de função estrutural, e não meramente pela adição de nós virtuais. O RAwR supera os controles aleatórios em uma média de +3,66 pontos percentuais.
  • Heurística SRL$^*$: A heurística SRL$^*$ seleciona efetivamente valores competitivos de $\epsilon$, frequentemente próximos aos melhores resultados de busca em grade, particularmente em conjuntos de dados do mundo real.

Significância e Limitações
O artigo afirma que o RAwR aborda uma lacuna crítica no reencaminhamento de grafos ao focar em onde as informações devem ser roteadas, e não apenas em como propagá-las mais facilmente. Ao alavancar funções estruturais, ele permite comunicação eficiente entre nós topologicamente distantes, mas estruturalmente semelhantes, abordando diretamente o fenômeno de esmagamento excessivo.

Os autores mantêm um tom modesto quanto às limitações:

• A avaliação atual está restrita a grafos não direcionados e não ponderados, embora as AEPs sejam definidas para casos direcionados/ponderados.
• A derivação do SRL assume GNNs lineares atuando como filtros polinomiais; a heurística pode ser menos informativa para arquiteturas como GAT ou GIN que não se encaixam facilmente neste modelo.
• O foco empírico está na classificação de nós; a extensão para outras tarefas de aprendizado em grafos é deixada para trabalhos futuros.

Em resumo, o RAwR fornece uma abordagem baseada em funções e principial para o reencaminhamento de grafos que melhora o desempenho da GNN em tarefas de longo alcance e heterofílicas, reduzindo a resistência efetiva e alinhando a passagem de mensagens com funções estruturais.