🤖 machine learning

Hierarchical Multi-Scale Graph Neural Networks: Scalable Heterophilous Learning with Oversmoothing and Oversquashing Mitigation

Este artigo apresenta o HAAR Multi-visão Hierárquico (HMH), um framework escalável de aprendizado espectral em grafos que mitiga o alisamento excessivo e o esmagamento excessivo em grafos heterofílicos ao construir uma hierarquia suave com bases de Haar ortonormais e filtros espectrais aprendíveis, superando assim as linhas de base mais avançadas em tarefas de classificação de nós e de grafos.

Autores originais: Md Sazzad Hossen, Avimanyu Sahoo

Publicado 2026-05-13

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Md Sazzad Hossen, Avimanyu Sahoo

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você está tentando entender uma cidade massiva e caótica caminhando por seus bairros. No mundo da ciência de dados, essa cidade é um grafo (uma rede de pontos conectados), e as pessoas que vivem lá são os nós.

Geralmente, quando ensinamos computadores a entender essas cidades, nos deparamos com três grandes problemas:

O Problema do "Vizinho Rico" (Dominação de Hubs): Se um bairro tem uma celebridade superpopular (um "hub" com milhares de amigos), a opinião deles abafa as vozes silenciosas dos bairros menores e menos conectados. O computador ouve apenas a celebridade.
O Problema da "Foto Embaçada" (Suavização Excessiva): Se você continuar perguntando aos vizinhos o que eles pensam, e eles continuarem perguntando aos seus vizinhos, eventualmente todos começarão a soar exatamente iguais. Os detalhes únicos são lavados e a imagem se torna uma mancha cinza embaçada.
O Problema do "Jogo do Telefone" (Espremimento Excessivo): Se você tentar enviar uma mensagem de um lado da cidade para o outro, a mensagem fica tão espremida ao passar por ruas lotadas que chega como um amontoado de palavras sem sentido.

O artigo apresenta uma nova solução chamada HMH (HAAR Hierárquico Multivista). Pense no HMH não como uma única pessoa caminhando pelas ruas, mas como um sistema inteligente de planejamento urbano multinível que usa um tipo especial de "lente de zoom".

Veja como funciona, passo a passo:

1. O Tradutor Inteligente (O Codificador Heterofílico)

Em muitas cidades, os vizinhos são semelhantes (gostam da mesma música). Em outras, os vizinhos são opostos (um ama jazz, o outro ama heavy metal). Isso é chamado de heterofilia.

Jeito antigo: Os computadores frequentemente assumem que todos são semelhantes e apenas fazem a média de suas opiniões. Isso falha quando os vizinhos são opostos.
Jeito HMH: Ele age como um tradutor que ouve com atenção. Se dois vizinhos são semelhantes, ele dá um "joinha" (peso positivo). Se são opostos, ele dá um "polegar para baixo" (peso negativo). Isso garante que o computador aprenda a identificar diferenças tão bem quanto semelhanças, sem ficar confuso com a inversão de sinais para frente e para trás.

2. A Lente de Zoom (Agrupamento Hierárquico)

Em vez de tentar analisar cada pessoa da cidade de uma só vez, o HMH constrói uma pirâmide de bairros.

Nível 1: Agrupa pessoas semelhantes em pequenos "agrupamentos" ou clusters.
Nível 2: Trata esses agrupamentos como "superpessoas" únicas e os agrupa em distritos maiores.
Nível 3: Continua ampliando a visão até ver a cidade inteira como algumas grandes regiões.

Isso é como olhar para um mapa: primeiro você vê as casas, depois os quarteirões, depois os bairros, e então a cidade inteira. Isso ajuda o computador a lidar com o Problema do "Vizinho Rico", porque os bairros pequenos e silenciosos ganham sua própria voz nos clusters menores antes de serem mesclados na imagem geral.

3. O Filtro Especial (Base de Haar)

Este é o ingrediente secreto. A maioria dos computadores usa um "filtro global" que tenta suavizar toda a cidade de uma vez, o que causa o problema da "foto embaçada".
O HMH usa algo chamado Base de Haar. Imagine isso como um conjunto de lanternas especializadas:

Algumas lanternas iluminam apenas uma única casa (detalhes locais).
Algumas iluminam um quarteirão inteiro (detalhes médios).
Algumas iluminam a cidade inteira (grandes tendências).

Como essas lanternas são ortogonais (elas não se sobrepõem ou interferem umas nas outras), o HMH pode ligar a lanterna de "detalhe local" sem desfocar acidentalmente a lanterna de "grande tendência". Mantém os detalhes de alta frequência (as diferenças entre vizinhos) nítidos, enquanto ainda entende o panorama geral.

4. O Elevador (Desagrupamento com Conexão de Salto)

Após analisar a cidade em cada nível de zoom, o HMH não para no topo. Ele usa um elevador para trazer todas essas informações de volta ao nível original da rua.

Ele pega os insights do "panorama geral" do topo da pirâmide.
Mistura-os com os "detalhes locais" da base.
Cada pessoa (nó) recebe um relatório final que inclui tanto as fofocas do bairro imediato quanto o contexto de toda a cidade.

Por que isso é uma grande novidade?

O artigo afirma que, ao usar este sistema de "Lente de Zoom + Lanternas Especiais + Elevador", o HMH resolve os três grandes problemas:

Fim da Dominação de Hubs: Os bairros pequenos não são abafados pelas celebridades porque são analisados em seus próprios clusters primeiro.
Fim das Fotos Embaçadas: As lanternas especiais mantêm os detalhes únicos nítidos, mesmo em camadas muito profundas.
Fim das Mensagens Espremidas: Como a cidade é organizada em uma hierarquia (como uma árvore), as mensagens não precisam se espremer por ruas lotadas; elas sobem e descem pela árvore, o que é muito mais rápido e claro.

O Resultado:
Os autores testaram isso em muitos tipos diferentes de "cidades" (conjuntos de dados), desde redes sociais até estruturas moleculares. Eles descobriram que o HMH foi mais rápido (escalando quase linearmente, o que significa que não fica sobrecarregado conforme a cidade cresce) e mais preciso do que métodos anteriores, especialmente em lugares onde os vizinhos são muito diferentes entre si. Ele alcançou melhores pontuações na identificação de quem pertence a qual grupo (classificação) sem perder a identidade única dos indivíduos.

Resumo Técnico: Redes Neurais Gráficas Hierárquicas Multiescala (HMH)

1. Declaração do Problema

Os grafos do mundo real frequentemente exibem heterofilia, onde nós adjacentes possuem rótulos ou características diferentes. Embora as Redes Neurais Gráficas (GNNs) existentes tenham avançado no tratamento de tais dados, elas sofrem de três patologias críticas, particularmente em grafos com desequilíbrio de grau (dominados por hubs):

Dominação de Hubs: Em grafos com nós "hubs" de alto grau, mecanismos convencionais de passagem de mensagens permitem que esses hubs dominem o processo de agregação. Isso sobrecarrega os sinais dos nós "raio" de baixo grau (pequenos clusters), fazendo com que os embeddings de clusters distintos converjam para uma representação comum induzida pelo hub, apagando assim as fronteiras de decisão.
Suavização Excessiva: À medida que a profundidade das GNNs aumenta, os embeddings dos nós tendem a convergir para uma distribuição estacionária (médias de classes), tornando as características indistinguíveis. Isso é exacerbado por filtros polinomiais subótimos que misturam sinais de regiões semanticamente não relacionadas.
Espremidura Excessiva: A informação de nós distantes decai exponencialmente com a distância no grafo, criando gargalos que impedem o fluxo de informação de longo alcance.

Abordagens espectrais existentes (por exemplo, ChebNet, BernNet) frequentemente dependem de bases polinomiais globais (Chebyshev, Jacobi) que assumem ortogonalidade contínua. No entanto, grafos reais possuem medidas espectrais discretas, levando ao vazamento de frequência, redução da expressividade e falha em adaptar-se à heterofilia estrutural local. Por outro lado, abordagens espaciais (por exemplo, Passagem de Mensagens Assinada) frequentemente sofrem com cancelamento de sinal entre camadas ou exigem etapas de agregação global dispendiosas que misturam sinais entre regiões.

2. Metodologia: HAAR Hierárquico Multivista (HMH)

Os autores propõem o HMH, um framework de aprendizado espectral em grafos projetado para escalar em tempo quase linear enquanto mitiga as patologias supracitadas. O framework opera por meio de uma análise hierárquica e multirresolução de sinais de grafos.

2.1. Codificador Adaptativo Heterofílico

O processo começa com um codificador consciente da heterofilia que aprende afinidades assinadas, conscientes de características e estrutura, sem exigir rótulos de nós.

Semelhança Adaptativa: O codificador calcula uma pontuação de semelhança combinando afinidade de características (pesos aprendíveis) e similaridade estrutural (baseada em vizinhos compartilhados de dois saltos).
Adjacência Assinada: Essas pontuações são transformadas em uma matriz de adjacência contínua e assinada ( $A_{adp}$ ). Alta semelhança gera pesos positivos (comportamento de passagem baixa), enquanto baixa semelhança gera pesos negativos (comportamento de passagem alta).
Estabilidade de Sinal: Diferentemente da Passagem de Mensagens Assinada (SMP) fixa, que sofre com inversão periódica de sinal ( $S^2 = I$ ), a adjacência adaptativa do HMH é recalculada em cada camada com base nos embeddings atuais, prevenindo oscilação rígida e cancelamento de sinal.

2.2. Aproximação Hierárquica de Grafos

Utilizando as pontuações dos nós do codificador, o HMH constrói uma hierarquia de grafo suave por meio de um processo de agrupamento recursivo:

Agrupamento: Os nós são agrupados em clusters (supernós) usando $k$ -means++ sobre os embeddings do codificador.
Atribuição Suave: Uma matriz de atribuição probabilística ( $A_s$ ) mapeia nós finos para clusters grosseiros, controlada por um parâmetro de temperatura.
Agregação: Características e arestas são agregadas para formar o próximo nível da hierarquia. Este processo se repete até que um limite seja atingido, criando uma estrutura de árvore.

2.3. Bases Haar Conscientes de Classe e Filtragem Espectral

Em cada nível hierárquico, o HMH constrói uma base de Haar esparsa eortonormal ( $U^{(\ell)}$ ) adaptada à estrutura específica de cluster daquele nível.

Construção da Base: A base consiste em um vetor de escala global (capturando tendências de baixa frequência) e wavelets. As wavelets são divididas em:
- Wavelets inter-cluster: Capturando contrastes entre diferentes supernós.
- Wavelets intra-cluster: Capturando variações localizadas dentro de um cluster.
Filtragem Diagonal: Sinais de grafos são projetados sobre esta base. Matrizes de ganho diagonal aprendíveis ( $\Lambda^{(\ell)}$ ) são aplicadas para amplificar seletivamente canais de alta frequência (heterofílicos) e atenuar sinais de baixa frequência (homofílicos) ou dominados por hubs.
Localidade: Como a base de Haar é estritamente localizada (suporte confinado a pequenas vizinhanças), ela previne vazamento de informação entre regiões não relacionadas do grafo, abordando diretamente a dominação de hubs.

2.4. Desagrupamento com Conexões de Resgate

Para recuperar a resolução original, o HMH emprega desagrupamento com conexões de resgate. Saídas de todos os níveis hierárquicos são agregadas de volta aos nós originais. Isso garante que cada nó retenha suas características básicas enriquecidas com contexto multiescala de todos os níveis da hierarquia, contornando efetivamente o decaimento exponencial associado à espremidura excessiva.

3. Contribuições Principais

O artigo reivindica quatro contribuições primárias:

Afinidade Assinada Adaptativa sem Rótulos: Um mecanismo que atribui pesos positivos/negativos com base na similaridade aprendida de características/estrutura, prevenindo a patologia de cancelamento de sinal encontrada em modelos SMP fixos.
Construção de Base Ortonormal em Tempo Quase Linear: O primeiro framework a construir uma base espectral ortonormal esparsa e multiescala (Haar) em tempo quase linear, evitando o custo $O(n^3)$ da decomposição espectral e o custo $O(n^2)$ de bases polinomiais densas.
Mitigação Teórica de Patologias: Provas rigorosas e evidências empíricas demonstrando que o HMH supera a dominação de hubs, a suavização excessiva e a espremidura excessiva. Especificamente, a base localizada confina a energia a vizinhanças de dois saltos, e a estrutura hierárquica encurta logaritmicamente os caminhos de comunicação.
Desempenho de Ponta: Demonstração de acurácia superior em tarefas de classificação de nós e grafos em conjuntos de dados homofílicos e heterofílicos, incluindo benchmarks em larga escala como OGBN-ArXiv.

4. Resultados Experimentais

Os autores avaliaram o HMH em uma suíte diversificada de conjuntos de dados:

Classificação de Nós: O HMH foi testado em benchmarks homofílicos padrão (Cora, Citeseer) e conjuntos de dados heterofílicos desafiadores (Chameleon, Squirrel, Texas, Roman-empire, Amazon-ratings, etc.).
- Desempenho: O HMH alcançou até uma melhoria de 3% em tarefas de classificação de nós em comparação com bases espectrais de ponta (por exemplo, ChebNetII, BernNet, UniFilter).
- Análise de Hubs: Em avaliações estratificadas por grau (Raios vs. Hubs), o HMH reduziu significativamente a lacuna de desempenho. Por exemplo, no conjunto de dados Penn94, ele melhorou a acurácia de "Raios" (baixo grau) em +10,8% em comparação com as bases, que tipicamente sofrem de dominação de hubs.
- Estabilidade de Profundidade: Diferentemente das GCNs que degradam rapidamente com a profundidade (suavização excessiva), o HMH permaneceu estável e até melhorou com a profundidade (atingindo o pico em 32–64 camadas no Penn94).
- Espremidura Excessiva: No benchmark Tree-NeighborsMatch, o HMH manteve >98% de acurácia na profundidade 10, enquanto as bases caíram para um palpite aleatório (50%) na profundidade 8.
Classificação de Grafos: Avaliado em conjuntos de dados TU (MUTAG, PROTEINS, etc.).
- Desempenho: O HMH alcançou uma melhoria de 7 pontos percentuais em conjuntos de dados de classificação de grafos, atingindo notavelmente 94,5% no MUTAG.
- Escalabilidade: O framework demonstrou escalabilidade quase linear. No conjunto de dados REDDIT-12K, o HMH foi 8,1 vezes mais rápido por época do que bases baseadas em decomposição espectral e utilizou 3,9 vezes menos memória.

5. Significado e Reivindicações

O artigo posiciona o HMH como uma solução para as limitações fundamentais das GNNs espectrais e espaciais atuais em cenários heterofílicos.

Significado Teórico: Os autores afirmam que, ao usar uma base Haar ortonormal localizada, eles confinam estritamente a energia do sinal, prevenindo o fenômeno de "aliasing de hub" onde pequenos clusters são ofuscados por nós de alto grau. A estrutura hierárquica é reivindicada como garantia teórica da ausência de espremidura excessiva ao reduzir logaritmicamente os comprimentos de caminho efetivos.
Significado Prático: O framework oferece uma alternativa escalável a métodos espectrais dispendiosos, tornando o aprendizado heterofílico de alto desempenho viável para grafos em larga escala (por exemplo, OGBN-ArXiv com ~170k nós).
Modéstia: Os autores reconhecem limitações atuais, observando que a formulação assume grafos estáticos e que estender o método para grafos dinâmicos ou multi-relacionais permanece uma direção para trabalho futuro. Eles enfatizam que suas melhorias são alcançadas mantendo a escalabilidade linear, um fator crucial para implantação no mundo real.