Power properties of the two-sample test based on the nearest neighbors graph

Resumo Técnico: Propriedades de Potência do Teste de Duas Amostras Baseado no Grafo de Vizinhos Próximos

Enunciado do Problema
Este artigo aborda o problema não paramétrico de duas amostras: testar a igualdade de duas distribuições multivariadas, $H_0: F = G$ versus $H_1: F \neq G$, sem assumir formas paramétricas específicas. Embora os testes baseados em grafos, que utilizam distâncias entre pontos para construir um grafo (por exemplo, Árvores Geradoras Mínimas ou grafos de $K$-Vizinhos Próximos), ofereçam uma alternativa livre de distribuição aos métodos baseados em postos (ranks), sua compreensão teórica tem sido limitada. Especificamente, a teoria assintótica existente baseia-se no framework de "grafos estabilizantes" de Penrose e Yukich, que se aplica a grafos onde a estrutura local é independente de pontos distantes. Este framework é válido para um $K$ fixo, mas falha quando o número de vizinhos $K$ aumenta com o tamanho da amostra $N$. O artigo investiga as propriedades de potência do teste de $K$-vizinhos próximos ($K$-NN) quando $K = k_N$ cresce com $N$, um regime que carecia anteriormente de justificativa teórica rigorosa.

Metodologia
Os autores empregam um cenário poissonizado para facilitar a análise assintótica, onde o tamanho da amostra segue uma distribuição de Poisson, permitindo o uso de propriedades de independência espacial. O estatístico do teste $T(G)$ conta o número de arestas no grafo construído que conectam pontos de duas amostras diferentes.

Principais etapas metodológicas incluem:

1. Superação da Não-Estabilização: Como o grafo $k_N$-NN não é estabilizante quando $k_N \to \infty$, os autores não podem depender de teoremas de limite padrão para funcionais estabilizantes. Em vez disso, eles realizam uma análise "direta" (hands-on) do estatístico do teste, quantificando explicitamente a estrutura de dependência local induzida pelo crescimento do número de vizinhos.
2. Normalidade Assintótica: Usando o método de Stein para grafos de dependência aplicado a uma versão truncada do estatístico, os autores estabelecem um Teorema de Limite Central (TLC) para o estatístico do teste sob alternativas gerais. Eles provam que, para $k_N = o(N^{1/4})$, o estatístico padronizado converge para uma distribuição normal.
3. Análise Condicional vs. Incondicional: O artigo deriva TLCs tanto para o estatístico incondicional quanto para um estatístico condicional (condicionado às localizações dos pontos, relevante para testes de permutação). O TLC condicional é válido para uma gama mais ampla de $k_N$ ($k_N = o(N)$), enquanto o TLC incondicional requer o critério mais restrito de $k_N = o(N^{1/4})$ devido à maior dependência entre os pontos na distribuição marginal.
4. Análise de Potência Local: Os autores analisam os limiares de detecção para alternativas locais onde a diferença de parâmetros $\|\theta_N - \theta_1\|$ decai a uma taxa $\epsilon_N$. Eles definem uma dimensão crítica $d_c(\gamma) = \lfloor 8(1-\gamma) \rfloor$ (assumindo que $k_N = N^\gamma$) para categorizar o comportamento do teste.

Principais Contribuições

1. Extensão do Framework Teórico: O artigo estende a compreensão teórica dos testes baseados em grafos além do framework de estabilização para o caso de $K$ crescente, especificamente para o grafo $K$-NN.
2. Limiares de Detecção: Os autores derivam limiares de detecção exatos para as versões uni-caudais (1-sided) e bi-caudais (2-sided) do teste. Eles demonstram que o comportamento desses testes diverge significativamente quando a dimensão $d$ excede a dimensão crítica $d_c(\gamma)$.
3. Resolução do "Gap de Exponente": Uma contribuição primária é a proposta e análise de um teste bi-caudal. Os autores mostram que o teste uni-caudal tradicional sofre de um "gap de expoente" em altas dimensões ($d > d_c(\gamma)$), onde sua potência depende criticamente da direção da alternativa (sofrendo de uma "maldição da dimensionalidade" em algumas direções). O teste bi-caudal elimina este gap, fornecendo limiares de detecção estáveis, independentemente da direção da alternativa.
4. Aumento de Potência via Densidade do Grafo: Os resultados fornecem justificativa teórica para a observação empírica de que aumentar o número de vizinhos próximos (grafos mais densos) impulsiona a potência do teste, particularmente para a versão bi-caudal, conforme o limiar de detecção se aproxima da taxa paramétrica ($N^{-1/2}$) à medida que $k_N$ aumenta.

Resultos

• Abaixo da Criticidade ($d \leq d_c(\gamma)$): Tanto os testes uni-caudais quanto os bi-caudais compartilam o mesmo limiar de detecção de $N^{-1/4}$. A potência limite é determinada pela CDF normal padrão.
• Acima da Criticidade ($d > d_c(\gamma)$):
  • Teste Uni-caudal: Exibe um gap de expoente. O limiar de detecção é ou $N^{-1/2 - 2(1-\gamma)/d}$ (uma "benção da dimensionalidade") ou $N^{-2(1-\gamma)/d}$ (uma "maldição da dimensionalidade"), dependendo da direção da alternativa. No intervalo entre essas taxas, a potência é 0 ou 1, dependendo do sinal de um termo direcional específico $b(h, \theta_1)$.
  • Teste Bi-caudal: Demonstra comportamento estável com um único limiar de detecção de $N^{-1/2 - 2(1-\gamma)/d}$. Ele não sofre com o gap de expoente e sua potência melhora com a dimensão, aproximando-se da taxa paramétrica $N^{-1/2}$ conforme $k_N$ cresce.
• Simulações: Resultados empíricos em dados sintéticos (perturbações de escala Gaussiana, famílias log-normais) e dados reais (20 Newsgroups) validam os achados teóricos. Eles confirmam que a potência do teste uni-caudal é altamente sensível à direção da alternativa em altas dimensões, enquanto o teste bi-caudal permanece robusto. As simulações também sugerem que aumentar $K$ melhora a potência, sendo que $K \leq N/30$ oferece um compromisso prático entre potência e a validade da aproximação normal.

Significância
O artigo afirma preencher uma lacuna crítica na literatura ao ligar o crescimento de $K$ à potência de testes de duas amostras em famílias paramétricas. Ao analisar rigorosamente o grafo $K$-NN não estabilizante, os autores fornecem a primeira justificativa teórica para o uso de grafos mais densos para melhorar a potência do teste. Além disso, a identificação do gap de expoente nos testes uni-caudais e a demonstração de que uma versão bi-caudal remove essa instabilidade oferece uma melhoria metodológica concreta para profissionais que trabalham com dados de alta dimensão. O trabalho sugere que, embora os testes uni-caudais possam ser pouco confiáveis em altas dimensões devido à sensibilidade direcional, os testes bi-caudais baseados em grafos mais densos oferecem uma alternativa robusta e poderosa.