Resumo Técnico: Teste de Hipótese de Duas Amostras para Igualdade de Subespaços em Dados de Redes

Formulação do Problema

O artigo aborda o desafio fundamental de determinar se dois conjuntos de dados com valores de rede independentes compartilham os mesmos padrões de conectividade estrutural subjacentes, especificamente suas estruturas de comunidades latentes, mesmo quando suas probabilidades de aresta diferem significativamente. Em muitas aplicações, como comparar redes sociais entre plataformas ou analisar a conectividade de aeroportos ao longo do tempo, as "comunidades" (grupos latentes) podem permanecer estáveis enquanto a densidade ou as probabilidades específicas de conexão flutuam.

Formalmente, sejam $A^{(1)}$ e $A^{(2)}$ duas matrizes de adjacência independentes de tamanho $n \times n$, geradas por matrizes de probabilidade simétricas e de baixo posto $P^{(1)}$ e $P^{(2)}$ de posto $k$. Os autores propõem testar a hipótese nula de que os espaços de colunas (subespaços) gerados pelos autovetores principais dessas matrizes de probabilidade são idênticos:
$$H_0: V^{(1)}(V^{(1)})^\top = V^{(2)}(V^{(2)})^\top$$
versus a alternativa $H_1$ onde os subespaços diferem. Aqui, $V^{(i)} \in \mathbb{R}^{n \times k}$ contém os autovetores ortonormais correspondentes aos autovalores não nulos de $P^{(i)}$.

Esta hipótese é mostrada como equivalente ao teste de igualdade de estruturas de comunidade em Modelos de Blocos Estocásticos (SBM) e Modelos de Blocos Estocásticos de Membros Mistos (MMSBM), até uma permutação e escala, e igualdade de espaços de características latentes em Grafos de Produto de Dot de Aleatórios Generalizados (GRDPG).

Metodologia

Estatística de Teste

A estatística de teste proposta baseia-se na norma de Frobenius da diferença entre as matrizes de projeção espectral empírica das duas redes. Seja $\hat{V}^{(i)}$ a matriz dos $k$ autovetores empíricos líderes de $A^{(i)}$. A estatística é definida como:
$$T_n := \| \hat{V}^{(1)}(\hat{V}^{(1)})^\top - \hat{V}^{(2)}(\hat{V}^{(2)})^\top \|_F^2$$

Teoria Assintótica

A principal contribuição teórica é um teorema de limite estabelecendo que, sob centramento e escala apropriados, $T_n$ converge em distribuição para uma variável aleatória Gaussiana padrão. Este resultado sustenta-se sob as seguintes condições:

1. Esparsidade: O grau esperado médio cresce pelo menos logaritmicamente com o número de vértices ($n\rho_n \gg \log n$).
2. Escalonamento de Autovalores: Os autovalores não nulos das matrizes de probabilidade escalam linearmente com $n\rho_n$.
3. Incoerência: As linhas dos autovetores da população estão uniformemente espalhadas (uma condição satisfeita por tamanhos de comunidade equilibrados em modelos de blocos).

A média ($\mu_2$) e a variância ($\sigma_2^2$) assintóticas da estatística são derivadas explicitamente em termos dos parâmetros da população. A derivação baseia-se em uma nova expansão de série de matrizes da diferença de projeção, decompondo a estatística em um termo dominante de segunda ordem e termos de resto de ordem superior. A prova utiliza um teorema de limite central de martingales para estabelecer o limite Gaussiano para o termo de segunda ordem, enquanto demonstra que os termos de ordem superior são assintoticamente desprezíveis.

Estimativa Baseada em Dados

Para tornar o teste operacional, os autores propõem estimadores de substituição (plug-in) consistentes para a média e variância assintóticas. Estes estimadores substituem os autovetores e autovalores da população desconhecidos por seus correspondentes empíricos. A consistência destes estimadores é provada sob uma suposição de "regime denso" ligeiramente mais forte ($n\rho_n \gg \sqrt{n}$), que garante que o erro de estimativa não distorça a distribuição limite.

Análogo de Uma Amostra

O artigo também estabelece um teorema de limite correspondente para um teste de uma amostra, que avalia a distância entre um subespaço empírico e um subespaço de referência conhecido. Este resultado serve como a base técnica para a prova de duas amostras e é apresentado como um resultado de interesse independente, fornecendo uma base para intervalos de confiança sobre a distância de projeção.

Principais Contribuições

1. Um Teste de Duas Amostras para Subespaços Comuns: Os autores propõem uma estatística de teste espectral para a igualdade de espaços de colunas de matrizes de probabilidade de baixo posto. Eles provam sua normalidade assintótica e fornecem estimadores consistentes para seus parâmetros, permitindo o controle rigoroso do Erro do Tipo I sem métodos de reamostragem computacionalmente intensivos como o bootstrapping.
2. Aplicação às Famílias de Modelos de Blocos: O arcabouço mostra-se aplicável tanto a SBMs quanto a MMSBMs. O teste detecta efetivamente mudanças na estrutura de comunidade (atribuições de membros), mesmo quando as probabilidades de aresta variam, distinguindo entre mudanças estruturais e meras flutuações de densidade.
3. Teorema de Limite para Distâncias de Projeção: O artigo deriva um teorema de limite para a distância de projeção entre os espaços próprios empíricos e os reais sob ruído de Bernoulli. Este resultado generaliza resultados anteriores que frequentemente assumiam ruído Gaussiano ou focavam em autovetores individuais, fornecendo uma teoria de distribuição global para erros de estimativa de subespaço.

Resultados

Simulações Numéricas

Os autores validam o método através de extensas simulações em dados sintéticos:

• Modelos de Blocos Estocásticos (SBM): O teste demonstra forte poder para distinguir redes com diferentes estruturas de comunidade. Mesmo pequenas perturbações (reatribuindo um pequeno número de nós) são detectadas com alta probabilidade conforme a densidade da rede aumenta.
• SBMs de Membros Mistos (MMSBM): O teste detecta com sucesso mudanças nos perfis de membros mistos. As simulações indicam que, embora o teste seja eficaz, detectar mudanças em regimes de atribuição suave (MMSBM) requer perturbações ligeiramente maiores ou redes mais densas em comparação com regimes de atribuição rígida (SBM).
• Controle de Tamanho: O tamanho empírico do teste permanece próximo ao nível de significância nominal ($\alpha = 0,05$) e melhora à medida que a densidade da rede aumenta.

Aplicação no Mundo Real

A metodologia é aplicada a dados de voos domésticos dos EUA (janeiro de 2016 – setembro de 2021) para analisar a rede de aeroportos.

• Períodos Estáveis: Comparações de redes de voos em janeiro e novembro em diferentes anos não mostram diferenças estruturais estatisticamente significativas, indicando estruturas de comunidade estáveis.
• Disrupção Estrutural: Comparações envolvendo junho de 2020 (o pico da interrupção causada pela pandemia de COVID-19) revelam diferenças estatisticamente significativas na estrutura do subespaço da rede em comparação com outros anos. Isso confirma a capacidade do teste de detectar grandes disrupções estruturais em dados de redes do mundo real.

Significância e Alegações

O artigo afirma fornecer um arcabouço rigoroso e computacionalmente eficiente para testes de hipóteses de redes que vai além de testar a igualdade de parâmetros específicos (ex: probabilidades exatas de aresta) para testar a estabilidade da estrutura geométrica subjacente (o subespaço).

• Robustez: Ao contrário de métodos que dependem de correspondência exata de parâmetros ou assumem estruturas de ruído específicas (como Gaussiana), esta abordagem é robusta a flutuações de densidade de arestas e é adaptada ao ruído de Bernoulli heterocedástico inerente aos dados de redes.
• Novidade Teórica: A derivação do limite Gaussiano para a distância de projeção sob ruído de Bernoulli é apresentada como um avanço teórico significativo, preenchendo uma lacuna na literatura onde tais resultados de distribuição anteriormente não estavam disponíveis para este cenário específico.
• Utilidade Prática: Ao fornecer distribuições limites de forma fechada e estimadores consistentes, o método evita o ônus computacional de testes de permutação ou procedimentos de bootstrap, tornando-o escalável para grandes conjuntos de dados de redes.

Os autores observam que, embora seus resultados sejam estabelecidos sob ruído de Bernoulli independente e limitado, trabalhos futuros poderiam estender estes teoremas de limite para distribuições de cauda pesada ou estruturas de arestas dependentes. Adicionalmente, a análise atual assume que o posto $k$ é conhecido, e incorporar a incerteza da seleção de posto permanece um desafio em aberto.