📊 statistics

Optimal Time Complexity Algorithms for Computing General Random Walk Graph Kernels on Sparse Graphs

Este artigo introduz os primeiros algoritmos randomized de tempo linear para aproximar sem viés kernels de caminhada aleatória gerais em grafos esparsos tanto rotulados quanto não rotulados, permitindo computação escalável em conjuntos de dados massivos sem construir o grafo de produto direto, ao mesmo tempo em que alcança acelerações significativas em relação aos métodos anteriores de tempo cúbico.

Autores originais: Krzysztof Choromanski, Isaac Reid, Arijit Sehanobish, Avinava Dubey

Publicado 2026-08-27

📖 4 min de leitura☕ Leitura rápida

CC BY 4.0

Autores originais: Krzysztof Choromanski, Isaac Reid, Arijit Sehanobish, Avinava Dubey

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

No mundo da ciência da computação, existe um desafio persistente em ensinar as máquinas a compreender a forma das coisas. Embora sejamos bons em reconhecer padrões em listas de números ou imagens, comparar as estruturas intrincadas de redes — como conexões sociais, ligações moleculares ou rotas de transporte — continua sendo difícil. Para fazer isso, pesquisadores utilizam ferramentas matemáticas chamadas kernels de grafos. Pense neles como uma forma de atribuir uma pontuação única a um par de redes, dizendo o quão semelhantes elas são. Uma pontuação alta significa que as duas redes compartilham um padrão de conexões semelhante; uma pontuação baixa significa que elas são fundamentalmente diferentes. Essa pontuação de similaridade é a base para muitas tarefas de aprendizado de máquina, como prever se um novo composto químico será eficaz ou agrupar redes sociais semelhantes.

No entanto, calcular essa pontuação tem sido historicamente um pesadelo computacional. Para redes complexas, os métodos padrão exigem tanto tempo e memória que se tornam impossíveis de usar assim que as redes crescem além de um certo tamanho. É como tentar contar todos os caminhos possíveis entre cada par de pessoas em uma cidade desenhando um mapa de cada conexão individual; o mapa torna-se grande demais para caber em uma única sala, e a contagem leva mais tempo do que uma vida humana. Esse gargalo manteve técnicas matemáticas poderosas fora do alcance de conjuntos de dados massivos do mundo real, forçando os cientistas a ignorar a complexidade total dos dados ou a se contentarem com aproximações grosseiras e menos precisas.

Uma equipe de pesquisadores resolveu agora este problema para uma ampla classe dessas ferramentas de similaridade. Eles desenvolveram um novo método que pode calcular essas comparações complexas de redes em um tempo que cresce linearmente com o tamanho da rede. Isso significa que, se uma rede dobrar de tamanho, o tempo necessário para calcular a pontuação de similaridade apenas dobra, em vez de explodir para um número incontrolável. A abordagem deles, que chamam de Graph Voyagers, funciona tanto para redes simples quanto para aquelas onde os pontos individuais possuem rótulos específicos, como diferentes tipos de átomos em uma molécula. O método é tão eficiente que pode lidar com redes de mais de dezesseis mil nós, uma escala que era anteriormente impossível de analisar com métodos exatos.

O cerne de sua inovação reside em como eles simulam o movimento através dessas redes. Tradicionalmente, para comparar duas redes, um computador teria que construir um mapa combinado massivo de ambas as redes de uma só vez, um passo que consome uma memória enorme. O novo método evita a construção desse mapa gigante inteiramente. Em vez disso, ele envia pares de caminhantes virtuais, um em cada rede, e os move passo a passo. Esses caminhantes são guiados por um conjunto compartilhado de sinais aleatórios. Se os caminhantes em ambas as redes derem o mesmo número de passos e chegarem a pontos com rótulos correspondentes, eles contribuem para a pontuação de similaridade final. Se derem números de passos diferentes ou chegarem a pontos desalinhados, suas contribuições se cancelam. Ao repetir esse processo milhares de vezes e tirar a média dos resultados, o algoritmo constrói uma estimativa altamente precisa da similaridade real sem nunca precisar armazenar o mapa combinado na memória.

Esta técnica não é apenas um truque teórico; ela produz uma nova maneira de representar redes inteiras como pontos em um espaço multidimensional. Nesse espaço, a distância entre dois pontos reflete o quão semelhantes são as redes. Como o método é tão rápido, ele permite que pesquisadores processem conjuntos inteiros de milhares de grafos de uma só vez, em vez de comparar um par de cada vez. Em testes em conjuntos de dados padrão usados para análise química e biológica, o novo método igualou ou até superou a precisão dos cálculos exatos e lentos. Também provou ser significamente mais rápido do que os métodos eficientes anteriores para grafos grandes, rodando até vinte e sete vezes mais rápido que as melhores alternativas existentes para grafos grandes.

Talvez o mais importante seja que essa velocidade abre as portas para aprender a melhor maneira de medir a similaridade automaticamente. No passado, os cientistas tinham que escolher manualmente as regras para como a pontuação de similaridade era calculada, muitas vezes recorrendo a uma fórmula padrão que poderia não se ajustar aos seus dados específicos. Com este novo método de tempo linear, os computadores agora podem aprender as regras otimizadas diretamente dos dados, ajustando o cálculo para encontrar os padrões mais úteis para uma determinada tarefa. Em experimentos, essa capacidade de aprender as regras melhorou a precisão da classificação de compostos químicos por uma margem significativa. Os pesquisadores mostraram que, ao remover a barreira computacional, podemos desbloquear maneiras mais poderosas e adaptáveis de as máquinas compreenderem as estruturas complexas que compõem o nosso mundo.

Resumo Técnico: Algoritmos de Complexidade de Tempo Ótima para Computação de RWKs Gerais em Grafos Esparsos

Declaração do Problema

O artigo aborda o gargalo computacional associado ao cálculo de Kernels de Caminhada Aleatória Gerais (RWKs) para grafos esparsos. Os RWKs são uma célebre família de funções simétricas e definidas positivas que atribuem pontuações de similaridade a pares de grafos, realizando uma soma ponderada de caminhadas de diferentes comprimentos no produto direto do grafo $G_1 \times G_2$ .

Embamente os RWKs abrangem kernels populares, como os kernels geométricos, exponenciais e marginalizados, sua computação exata é proibitivamente cara. Para grafos com $N$ vértices, a avaliação por força bruta via o grafo produto direto incurre em uma complexidade de $O(N^6)$ . Mesmo métodos otimizados, como os que resolvem equações de Sylvester ou utilizam decomposição espectral, tipicamente requerem tempo de $O(N^3)$ e frequentemente falham em lidar com grafos rotulados ou em escalar para conjuntos de dados massivos. Além disso, métodos subcúbicos existentes geralmente não conseguem lidar com sequências de coeficientes arbitrárias $(\mu_i)$ necessárias para o aprendizado dos parâmetros do kernel. Notavelmente, embora o trabalho anterior de Kang et al. (2012) tenha fornecido um algoritmo $O(N)$ , este era restrito ao caso específico de RWKs geométricos em grafos não rotulados.

A questão central colocada é: É possível computar estimativas não viesadas de RWKs gerais para grafos esparsos e rotulados com complexidade de tempo linear de $O(N)$ ?

Metodologia: Graph Voyagers (GVoys)

Os autores propõem os Graph Voyagers (GVoys), o primeiro algoritmo a alcançar a aproximação não viesada de RWKs gerais em tempo $O(N)$ para grafos esparsos tanto rotulados quanto não rotulados. O método generaliza os Graph Random Features (GRFs), mas introduz mecanismos específicos para evitar a instanciação do grafo produto direto $G_1 \times G_2$ na memória.

Mecanismo Central

Caminhadas Aleatórias Dependentes: Em vez de amostrar caminhadas no enorme grafo produto, os GVoys amostram caminhadas aleatórias de forma independente em $G_1$ e $G_2$ . Para emular caminhadas no grafo produto, essas caminhadas independentes são acopladas usando variáveis aleatórias compartilhadas.
Filtragem via Variáveis Aleatórias:
- Correspondência de Comprimento ( $g$ -variáveis): Para garantir que apenas caminhadas do mesmo comprimento contribuam para o kernel (conforme exigido pela definição da caminhada do grafo produto), o algoritmo multiplica as contribuições das caminhadas por variáveis aleatórias de Rademacher compartilhadas $g(l)$ em cada etapa $l$ . Como $E[g(l_1)g(l_2)] = \mathbb{I}(l_1 = l_2)$ , os termos cruzados onde os comprimentos das caminhadas diferem desaparecem na expectativa.
- Correspondência de Rótulos ( $z$ -variáveis): Para grafos rotulados, o algoritmo introduz variáveis aleatórias adicionais compartilhadas $z(l, i)$ correspondentes aos rótulos dos vértices. Isso filtra as contribuições de caminhadas onde a sequência de rótulos dos vértices não coincide, lidando efetivamente com a restrição de que as arestas no grafo produto só existem entre vértices com rótulos idênticos.
Embeddings de Nível de Grafo: O algoritmo constrói vetores de características de baixa dimensão para cada grafo. O produto escalar desses embeddings para qualquer par de grafos $(G_i, G_j)$ fornece uma estimativa não viesada do verdadeiro RWK $K_{RWK}(G_i, G_j)$ .
Eficiência de Memória: O método não armazena a matriz de adjacência do grafo produto. Ele utiliza representações esparsas e pontos de ancoragem para reduzir a dimensionalidade, garantindo que a complexidade de espaço permaneça linear no número de nós.

Detalhes Algorítmicos

Entrada: Grafos $G_i$ , função de modulação $f_\mu$ (derivada dos coeficientes $\mu_i$ ), probabilidade de terminação $p_{halt}$ , e número de caminhadas $m$ .
Processo:
1. Inicializar sequências aleatórias compartilhadas $g$ e $z$ .
2. Para cada grafo, simular $m$ caminhadas aleatórias partindo de vários vértices.
3. Acumular "depósitos" em vértices de ancoragem, ponderados pela função de modulação, pelas variáveis aleatórias e pela probabilidade da caminhada.
4. Construir matrizes de características $C_i$ e $D_i$ .
Saída: Vetores de características $\phi(G_i)$ tal que $K_{RWK}(G_i, G_j) = \mathbb{E}[\phi(G_i)^\top \phi(G_j)]$ .

Principais Contribuições

Complexidade de Tempo Linear: O artigo apresenta o primeiro algoritmo $O(N)$ para a aproximação não viesada de RWKs gerais (abrangendo sequências de coeficientes arbitrárias $(\mu_i)$ ) para grafos esparsos tanto rotulados quanto não rotulados. Isso vai além dos métodos $O(N)$ anteriores, que eram limitados a casos específicos como RWKs geométricos em grafos não rotulados.
Escalabilidade para Grandes Conjuntos de Dados: Ao evitar a instanciação do grafo produto direto, o método escala para grafos com $>2^{14}$ nós e conjuntos de dados com milhares de grafos, onde métodos anteriores falham devido a restrições de memória (OOM) ou de tempo.
Garantias Teóricas:
- Não Viesamento: O Teorema 4.1 prova que o estimador é não viesado.
- Concentração: O Teorema 4.2 fornece limites de concentração exponencial, mostrando que o estimador converge agudamente para o valor real do kernel.
- Otimalidade: O Teorema 4.3 demonstra que o uso de distribuições de Rademacher para as variáveis aleatórias minimiza a variância do estimador.
Aprendizado Implícito de Kernel: A capacidade de aproximar RWKs gerais (em vez de casos especiais fixos) permite o aprendizado de ponta a ponta da sequência de coeficientes $(\mu_i)$ , desbloqueando o aprendizado escalável de kernels de grafos implícitos.

Resultados Experimentais

Os autores avaliaram os GVoys no TUDataset e em grafos sintéticos de Erdős-Rényi:

Precisão: Os GVoys convergem para os valores exatos de RWK conforme o número de caminhadas aleatórias aumenta. Em tarefas de classificação de grafos (ex: MUTAG, ENZYMES, NCI1), os GVoys igualaram ou superaram o desempenho das linhas de base de RWK exato.
Velocidade:
- Para grafos com $>2^{10}$ nós, os GVoys superaram a decomposição espectral, o gradiente conjugado e os métodos de iteração de ponto fixo.
- Em grafos com $2^{13}$ nós, os GVoys foram 27 vezes mais rápidos que a iteração de ponto fixo.
- Em grafos com $2^{14}$ nós, os GVoys foram 8 vezes mais rápidos que o gradiente conjugado, enquanto outras linhas de base sofreram falta de memória ou tempo.
Aprendizado de Kernel: O aprendizado dos coeficientes $(\mu_i)$ usando GVoys no conjunto de dados MUTAG resultou em uma precisão de $88,3\%$ , um aumento de $8,5\%$ sobre a linha de base padrão de RWK geométrico ( $81,4\%$ ).

Significância e Alegações

O artigo afirma ter resolvido uma barreira computacional de longa data nos métodos de kernel de grafo. Ao alcançar complexidade de tempo e espaço lineares, os GVoys tornam viável a aplicação de kernels de caminhada aleatória gerais a conjuntos de dados reais e massivos que antes eram intratáveis.

Os autores enfatizam que seu método é o primeiro algoritmo subcúbico a alcançar a aproximação não viesada para RWKs gerais em grafos tanto rotulados quanto não rotulados. Embora algoritmos $O(N)$ anteriores existissem para instâncias específicas (como RWKs geométricos em grafos não rotulados), os GVoys são os primeiros a lidar com o caso geral com coeficientes arbitrários e vértices rotulados. A introdução de novos embeddings de grafos (características aleatórias) que preservam a estrutura do kernel permite o escalonamento linear em relação tanto ao número de nós em um grafo quanto ao número de grafos em um conjunto de dados. Essa capacidade é destacada como um pré-requisito para o aprendizado escalável de kernels de grafos implícitos, onde os próprios parâmetros do kernel são aprendidos a partir dos dados.

O artigo conclui que, embora o método seja não viesado para grafos não ponderados e não direcionados, a natureza estocástica do estimador pode oferecer robustez ao ruído em tarefas de jusante, potencialmente superando computações exatas de kernel em cenários de classificação.