📊 statistics

$k$ -Nearest Neighbors in Gromov--Wasserstein Space

Este artigo implementa a classificação de $k$ -vizinhos mais próximos utilizando as distâncias de Gromov--Wasserstein e de Gromov--Wasserstein fundido para comparar grafos e grafos com atributos de nós, respectivamente, e prova a consistência universal desses classificadores ao mesmo tempo em que demonstra seu forte desempenho empírico em múltiplos conjuntos de dados.

Autores originais: Kaitlyn Hohmeier, Nicolas Fraiman, Caroline Moosmueller

Publicado 2026-06-10

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Kaitlyn Hohmeier, Nicolas Fraiman, Caroline Moosmueller

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 classificar uma pilha enorme de objetos diferentes. Alguns são formas simples, outros são redes complexas como mapas de metrô ou círculos sociais. Seu objetivo é descobrir a qual categoria um novo objeto, não visto anteriormente, pertence, observando os objetos que você já conhece. Este é o trabalho de um classificador de $k$ -Vizinhos Mais Próximos ( $k$ -NN).

Pense no $k$ -NN como um "concurso de popularidade" entre seus vizinhos. Se você soltar um novo objeto em uma sala de objetos conhecidos, você olha para os $k$ vizinhos mais próximos dele. Se a maioria desses vizinhos for "gatos", você supõe que o novo objeto também seja um gato.

O problema é: Como medir a "proximidade" quando os objetos são redes complexas (grafos) sem um tamanho ou forma padrão? Você não pode simplesmente medir a distância entre dois pontos em um mapa.

Este artigo apresenta uma nova maneira inteligente de medir essa distância usando algo chamado Gromov–Wasserstein (GW) e Fused Gromov–Wasserstein (fGW). Aqui está a divisão em termos simples:

1. O Problema: Comparando Maçãs com Laranjas (e Laranjas com Aviões)

Normalmente, para comparar duas coisas, elas precisam ter o mesmo tamanho. Se você quiser comparar dois grafos (redes de pontos e linhas), os métodos tradicionais muitas vezes forçam que eles tenham o mesmo tamanho ou os transformam em uma única lista de números (um "embedding"). Isso é como tentar comparar uma pequena árvore genealógica com um enorme organograma corporativo, espremendo ambos em uma mesma caixa minúscula. Você perde informação.

2. A Solução: A Régua "Transformadora de Formas"

Os autores usam uma ferramenta matemática chamada distância de Gromov–Wasserstein.

A Analogia: Imagine que você tem duas cidades diferentes. Uma é uma grade (como Manhattan) e a outra é uma teia de estradas sinuosas (como San Francisco). Elas parecem totalmente diferentes.
A Magia do GW: Em vez de comparar as ruas diretamente, o GW pergunta: "Se eu pudesse magicamente rearranjar as pessoas na Cidade A para corresponder à densidade populacional da Cidade B, o quanto a 'distância de relacionamento' entre os vizinhos mudaria?"
Ele não se importa se as cidades têm 100 pessoas ou 1.000 pessoas. Ele só se importa com o padrão de relacionamentos. Se a Cidade A tem um "hub" com muitas conexões e a Cidade B tem um "hub" semelhante, o GW diz: "Estas duas cidades são estruturalmente semelhantes", mesmo que pareçam diferentes em um mapa.

3. Adicionando "Características": A Versão Fundida

Às vezes, os pontos em sua rede possuem informações extras. Por exemplo, em um grafo de molécula, cada átomo tem um tipo específico (Carbono, Oxigênio). Em um grafo social, cada pessoa tem um cargo profissional.

A Analogia: Imagine comparar duas cidades novamente. O GW observa os padrões das estradas. Mas e se você também quiser comparar os tipos de edifícios?
A Magia do fGW: A distância Fused Gromov–Wasserstein (fGW) faz as duas coisas ao mesmo tempo. Ela verifica se os padrões de estradas coincidem e se os edifícios em locais semelhantes são do mesmo tipo. É como uma régua que mede tanto o formato da cidade quanto a cor das casas.

4. A Grande Afirmação: "Sempre Funciona" (Consistência Universal)

Os autores não apenas construíram uma nova régua; eles provaram matematicamente que usar esta régua com o método $k$ -NN sempre funciona a longo prazo.

A Garantia: Eles provaram que, se você continuar adicionando mais e mais dados de treinamento (mais exemplos de grafos), seu classificador $k$ -NN usando estas novas distâncias se tornará tão preciso quanto é teoricamente possível.
A Ressalva: Esta prova é válida para grafos de qualquer tamanho, desde que você siga regras específicas sobre como escolher seu "número de vizinhos" ( $k$ ) conforme seus dados crescem. Eles mostraram que o espaço de todos os grafos possíveis se comporta bem o suficiente para que esta matemática se sustente.

5. O Experimento: Isso realmente ajuda?

Os autores testaram seu método em dados do mundo real:

Moléculas: Classificando produtos químicos com base em sua estrutura e tipos de átomos.
Redes Sociais: Classificando redes de colaboração de filmes (ex: filmes de "Ação" vs. "Romance").
Dados Sintéticos: Redes criadas artificialmente para testar os limites.

Os Resultados:

O método deles (GW- $k$ -NN e fGW- $k$ -NN) teve um desempenho muito bom, muitas vezes superando ou igualando outros métodos populares, como Redes Neurais de Grafos (GCNs) e kernels de grafos complexos.
Descoberta Chave: Para moléculas com dados extras (tipos de átomos), a versão "Fundida" (fGW) foi a grande vencedora. Ela mostrou que olhar para a estrutura e para as características juntas é melhor do que olhar apenas para uma delas.
Eficiência: Embora a matemática seja pesada, o método foi surpreendentemente rápido e eficiente em comparação com alguns outros métodos complexos, especialmente para grafos sem atributos.

Resumo

O artigo diz: "Encontramos uma maneira de medir o quão semelhantes são dois sistemas complexos, independentemente de seu tamanho ou forma. Provamos que, se você usar essa medição para classificar novas redes com base em seus vizinhos mais próximos, o método é matematicamente garantido de melhorar cada vez mais à medida que você fornece mais dados. Nossos testes mostram que isso funciona muito bem em problemas do mundo real, como identificar moléculas e gêneros de filmes."

O que eles NÃO alegaram:

Eles não alegaram que isso funciona para todo tipo de dado (apenas grafos e objetos estruturados).
Eles não alegaram que este é o método mais rápido do mundo (eles notaram que pode ser computacionalmente pesado, embora tenham mostrado que é competitivo).
Eles não aplicaram isso a diagnósticos médicos ou usos clínicos; eles se limitaram estritamente a tarefas de classificação de grafos.

Resumo Técnico: $k$ -Vizinhos Mais Próximos no Espaço de Gromov–Wasserstein

Enunciado do Problema
O artigo aborda o desafio de classificar dados com estrutura de grafo, incluindo grafos sem atributos e grafos com atributos de nós, dentro de um rigoroso arcabouço de aprendizado métrico. Classificadores tradicionais de $k$ -vizinhos mais próximos ( $k$ -NN) dependem de funções de distância definidas em espaços métricos euclidianos ou padrões. No entanto, os grafos frequentemente possuem estruturas complexas onde a comparação direta é difícil, particularmente quando os grafos possuem números diferentes de nós ou carecem de um mapeamento canônico. Embora a distância de Gromov–Wasserstein (GW) forneça um arcabouço para comparar espaços de medida métrica (mm-spaces) e a distância de Gromov–Wasserstein fundida (fGW) estenda isso para incluir características de nós, as propriedades teóricas dos classificadores $k$ -NN operando dentro desses espaços métricos específicos eram anteriormente desconhecidas. Especificamente, não estava claro se o $k$ -NN é universalmente consistente (convergiu para o risco de Bayes ótimo) quando o espaço subjacente é o espaço de grafos equipado com as distâncias GW ou fGW.

Metodologia
Os autores implementam a classificação $k$ -NN utilizando distâncias GW e fGW e investigam sua consistência teórica. O núcleo de sua metodologia envolve estabelecer as propriedades topológicas dos espaços métricos em questão para satisfazer as condições exigidas para a consistência universal.

Definições de Espaço Métrico:
- Espaço GW ( $\mathbb{X}$ ): O espaço de classes de equivalência de mm-spaces com suporte finito e medida de probabilidade uniforme, equipado com a distância de Gromov–Wasserstein $p=2$ . Isso modela grafos sem atributos.
- Espaço fGW ( $\mathbb{Y}^f$ ): O espaço de classes de isomorfismo fraco de objetos estruturados (mm-spaces com mapas de características para $\mathbb{R}^d$ ), equipado com a distância de Gromov–Wasserstein fundida ( $p=1, q=2$ ). Isso modela grafos com atributos de nós.
Arcabouço Teórico:
Os autores baseiam-se em resultados estabelecidos na teoria do aprendizado (especificamente Chaudhuri e Dasgupta [9]), que afirmam que o $k$ -NN é universalmente consistente em um espaço métrico separável se o espaço possuir dimensão métrica $\sigma$ -finita (uma propriedade relacionada à condição de diferenciação de Lebesgue). Para provar isso para os espaços GW e fGW, os autores:
- Constroem modelos de dimensão finita para espaços de $n$ pontos dentro desses arcaboiços.
- Demonstram a existência de mapas bi-Lipschitz entre o espaço de grafos de $n$ pontos e espaços quocientes específicos de matrizes euclidianas (para GW) e espaços produto de matrizes e vetores de características (para fGW).
- Provam que esses espaços quocientes possuem dimensão Assouad-Nagata finita.
- Utilizam o Lema 2.4 para mostrar que a existência de mapas bi-Lipschitz para espaços com dimensão finita implica que os espaços alvo ( $\mathbb{X}$ e $\mathbb{Y}^f$ ) possuem dimensão métrica $\sigma$ -finita.
Experimentos Numéricos:
Os autores avaliam o desempenho dos classificadores GW- $k_n$ -NN e fGW- $k_n$ -NN em sete conjuntos de dados de referência:
- Grafos com Atributos: BZR, COX-2 e PROTEINS (conjuntos de dados moleculares).
- Grafos sem Atributos: IMDb-B, IMDb-M (redes sociais) e dois conjuntos de dados sintéticos (ERSBM1, ERSBM2).
- Linhas de Base (Baselines): Comparações com Redes Neurais Convolucionais de Grafos (GCN), vários métodos de kernel de grafo (Shortest Path, Graphlet, HOPPER, Propagation) e SVMs usando kernels GW/fGW.

Principais Contribuições
A principal contribuição deste trabalho é a prova da consistência universal para classificadores $k$ -NN no contexto de classificação de grafos usando distâncias GW e fGW.

Resultados Teóricos:
- Teorema 1.8: Prova que o classificador GW- $k_n$ -NN é universalmente fracamente consistente no espaço de grafos $(\mathbb{X}, GW_2)$ sob as condições $k \to \infty$ e $k/n \to 0$ . Ele é universalmente fortemente consistente se $k/\log(n) \to \infty$ .
- Teorema 1.9: Prova a mesma consistência para o classificador fGW- $k_n$ -NN no espaço de grafos com atributos de nós $(\mathbb{Y}^f, fGW_{\alpha,1,2})$ .
- Estes resultados são estabelecidos ao demonstrar que ambos os espaços são separáveis e possuem dimensão métrica $\sigma$ -finita, uma propriedade derivada via mapeamentos bi-Lipschitz em espaços quocientes de espaços euclidianos.
Resultados Empíricos:
- Nos conjuntos de dados de grafos com atributos (BZR, COX-2, PROTEINS), o fGW- $k_n$ -NN alcançou consistentemente a maior precisão média, superando as GCNs e outros métodos baseados em kernel. O GW- $k_n$ -NN também apresentou desempenho competitivo.
- Nos conjuntos de dados sem atributos, o GW- $k_n$ -NN alcançou precisão perfeita (100%) no conjunto de dados sintético ERSBM2 e um forte desempenho no IMDb-B, muitas vezes superando kernels de grafos e GCNs.
- Os autores observam que, embora os métodos GW/fGW sejam interpretáveis (pequenas distâncias implicam similaridade estrutural), eles podem ser computacionalmente intensivos em comparação com alguns métodos de kernel, embora ofereçam melhorias de eficiência sobre SVMs usando kernels GW em certos contextos.

Significância e Alegações
O artigo afirma estabelecer uma base teórica para o uso de classificadores métricos como $k$ -NN dentro do arcabouço de Gromov–Wasserstein. Ao provar a consistência universal, os autores argumentam que esses métodos não são meramente heurísticos, mas sim teoricamente sólidos para tarefas de classificação de grafos.

A significância reside em preencher a lacuna entre a teoria do transporte ótimo e a teoria do aprendizado estatístico para dados estruturados. Os autores enfatizam que sua abordagem oferece um "arcabouço altamente interpretável", onde a distância entre grafos mede diretamente a similaridade estrutural (o isomorfismo implica distância zero). Eles declaram explicitamente que, até onde sabem, esta é a primeira aplicação de GW- $k$ -NN para classificação de grafos e a primeira prova teórica de sua consistência.

O artigo permanece modesto quanto a generalizações futuras. Os autores reconhecem que, embora a consistência seja provada para parâmetros específicos ( $p=2$ para GW, $p=1, q=2$ para fGW), permanece um problema em aberto se esses resultados se sustentam para outras escolhas de parâmetros ou no cenário Z-Gromov–Wasserstein mais geral. Os autores conjecturam que, de forma semelhante ao espaço de Wasserstein, a consistência universal pode não ocorrer em total generalidade sem restrições específicas aos espaços de interesse.