Online Learning for Autoregressive Multilayer Stochastic Block Models under Stationarity and Non-Stationarity

1. Formulação do Problema

O artigo aborda o desafio de analisar redes multicamadas dinâmicas, onde um conjunto comum de nós interage através de múltiplos tipos de relacionamentos (camadas) que evoluem ao longo do tempo. Os métodos existentes frequentemente sofrem de três limitações:

1. Independência Temporal: Eles assumem que as instantes da rede são independentes, ignorando a dependência temporal intrínseca em sistemas do mundo real (por exemplo, redes de comércio, interações sociais).
2. Foco em Camada Única: Eles falham em capturar as correlações estruturais entre diferentes camadas.
3. Suposição de Estacionariedade: Eles assumem que a dinâmica subjacente da rede é estacionária, falhando em adaptar-se a desvios graduais ou mudanças estruturais abruptas (por exemplo, mudanças de políticas, crises).

Os autores visam desenvolver uma estrutura que modele explicitamente a dependência temporal por meio de um mecanismo autoregressivo, lide com estruturas multicamadas e forneça procedimentos de aprendizado online adaptativo para ambientes tanto estacionários quanto não estacionários.

2. Metodologia

A. O Modelo: AR(1)-MSBM

Os autores propõem o Modelo de Blocos Estocásticos Multicamadas Autoregressivo de Primeira Ordem (AR(1)-MSBM).

• Estrutura: Uma sequência de tensores de adjacência $\{A_t\}_{t \geq 0} \in \{0, 1\}^{n \times n \times L}$, onde $n$ é o número de nós, $L$ é o número de camadas e $K$ é o número de comunidades.
• Dinâmica das Arestas: Diferentemente de SBMs estáticos, as arestas evoluem por meio de um mecanismo de "atualização". Entre os tempos $t-1$ e $t$, uma aresta $(i, j, l)$ pode:
  • Formar-se (0 $\to$ 1) com probabilidade $\Theta_{i,j,l}$.
  • Dissolver-se (1 $\to$ 0) com probabilidade $\Delta_{i,j,l}$.
  • Persistir com probabilidade $1 - \Theta_{i,j,l} - \Delta_{i,j,l}$.
• Estrutura Latente: As probabilidades de transição são tensores de baixo posto determinados por uma matriz de pertencimento a comunidades compartilhada $Z$ e tensores de conectividade específicos por camada $W$ (formação) e $M$ (dissolução):
  $$\Theta_{i,j,l} = Z_i W_{:,:,l} Z_j^\top, \quad \Delta_{i,j,l} = Z_i M_{:,:,l} Z_j^\top$$
• Não Estacionariedade: No cenário não estacionário, $W_t$ e $M_t$ variam ao longo do tempo, permitindo tanto pontos de mudança abruptos quanto desvios graduais, enquanto $Z$ permanece fixo (embora a estrutura possa ser estendida para $Z$ variante no tempo).

B. Estimação Estacionária (Algoritmo 1)

Para o caso estacionário, os autores propõem um Procedimento de Estimação Online:

1. Estatísticas Suficientes Recursivas: Manter contagens cumulativas de transições de arestas (0$\to$1, 1$\to$0) e arestas ativas. Estas são atualizadas em tempo $O(n^2 L)$ por passo sem reavaliar dados passados.
2. Estimadores Iniciais: Computar Estimadores de Máxima Verossimilhança (EMV) de forma fechada para $\Theta$ e $\Delta$ baseados nessas contagens.
3. Refinamento Espectral de Tensores: Para melhorar a precisão, aplicar Análise de Componentes Principais Heterocedástica de Tensores (TH-PCA). Isso explora a estrutura de Tucker de baixo posto dos tensores. Crucialmente, este refinamento é realizado apenas em pontos de tempo geometricamente espaçados ($t = 2^m$) para minimizar o custo computacional.
4. Recuperação de Comunidades: Agrupar o subespaço singular estimado da matricização do modo-1 para recuperar as pertenças às comunidades.

C. Estimação Não Estacionária (Algoritmo 2)

Para o caso não estacionário, os autores introduzem um Algoritmo Online com Janela Adaptativa:

1. Janelamento Adaptativo: Em vez de usar uma janela fixa ou todo o histórico, o algoritmo seleciona dinamicamente um tamanho de janela de retrocesso $\hat{k}_t$.
2. Critério de Estabilidade: Inspirado por Huang e Wang (2024), o algoritmo compara a perda empírica da janela atual contra janelas aninhadas menores. Ele seleciona a maior janela que permanece "estável" (ou seja, a diferença de perda não excede um limiar de tolerância $\tau(t)$).
3. Grade Dinâmica: Para garantir eficiência computacional, os tamanhos de janela candidatos são restritos a uma grade geométrica dinâmica, reduzindo o armazenamento de $O(t)$ para $O(\log t)$.
4. Segmentação Quase Estacionária: A análise teórica assume que a série temporal pode ser particionada em "segmentos quase estacionários" onde o desvio é controlado por uma função $V(t)$ e satisfaz "monotonicidade dominante" (impedindo a cancelação de desvios positivos e negativos).

3. Principais Contribuições

1. Estrutura de Modelo Inovadora: Introdução do AR(1)-MSBM, que unifica a estrutura multicamada com dependência temporal explícita por meio de probabilidades de formação/dissolução de arestas.
2. Estimação Ótima Minimax (Estacionária):
   • Derivação de limites de estimação não assintóticos para os tensores de transição $\Theta$ e $\Delta$.
   • Prova de optimalidade minimax (estabelecendo o primeiro limite inferior minimax para modelos de redes multicamadas dinâmicas).
   • Demonstração de que alavancar a estrutura multicamada reduz a taxa de erro estocástico de $O(1/\sqrt{t})$ para $O(1/\sqrt{tL})$.
3. Aprendizado Adaptativo Não Estacionário:
   • Desenvolvimento de um algoritmo que se adapta automaticamente a mudanças estruturais desconhecidas (abruptas ou graduais) sem conhecimento prévio dos pontos de mudança.
   • Garantias teóricas mostrando que o erro de estimação corresponde à taxa estacionária quando aplicado segmento a segmento, com o tamanho efetivo da amostra determinado pelo comprimento do segmento local.
4. Garantias de Recuperação de Comunidades:
   • Estabelecimento de condições para recuperação de comunidades consistente em Hamming (erro fracionário desaparece) e exata (erro zero).
   • Melhoria sobre resultados existentes de camada única ao evitar termos de viés associados à normalização diagonal em métodos baseados em Laplaciano.

4. Resultados Teóricos

• Taxas de Estimação:
  • No cenário estacionário, o erro de Frobenius para estimar $\Theta$ e $\Delta$ escala como:
    $$\|\hat{\Theta}_t - \Theta\|_F \lesssim \sqrt{\frac{nK + Lr + K^2r}{t}} + \frac{n\sqrt{L}}{t}$$
    onde o primeiro termo é o erro estocástico e o segundo é o viés.
  • O termo de viés ($O(1/t)$) é um artefato conhecido de EMVs autoregressivos, mas torna-se negligenciável à medida que $t$ cresce em relação ao tamanho da rede.
• Limite Inferior Minimax: O artigo prova que a taxa $O(\sqrt{(rK^2 + n\log K + Lr)/T})$ é ótima, correspondendo ao limite superior até fatores logarítmicos e uma lacuna computacional ($K$ vs $\log K$).
• Taxas Não Estacionárias: Sob a estrutura de segmentação quase estacionária, o erro depende do comprimento do segmento local $t - T_{g-1}$ e do envelope de desvio $V(\cdot)$. Se $V(t) = t^{-1/2}$, a taxa corresponde à taxa estacionária aplicada localmente.

5. Resultados Experimentais

• Simulações:
  • Estacionário: O método proposto superou estimadores cumulativos estáticos (que ignoram dependência temporal) e estimadores agregados por camada (que perdem a estrutura específica da camada), particularmente em cenários com sinais fracos ou estruturas de camadas opostas.
  • Não Estacionário: O algoritmo adaptativo detectou com sucesso mudanças abruptas e rastreou desvios graduais. Consistentemente superou as linhas de base de histórico completo (alto viés após mudanças) e janela fixa (alta variância ou viés dependendo da escolha da janela).
• Dados Reais (Transporte Aéreo dos EUA):
  • Analisou dados mensais de voos (2015–2025) de 4 grandes companhias aéreas.
  • O algoritmo detectou uma ruptura estrutural significativa em meados de 2020 (pandemia de COVID-19), evidenciada por um pico nas taxas de troca de comunidades e uma contração da janela de retrocesso selecionada.
  • Pós-2022, o tamanho da janela expandiu, indicando estabilização da rede, e o modelo capturou o declínio gradual na conectividade da rede (persistência) e o aumento na rotatividade de rotas.

6. Significância

Este artigo preenche uma lacuna crítica na ciência de redes ao fornecer uma estrutura teórica e algorítmica rigorosa para redes dinâmicas, multicamadas e não estacionárias.

• Impacto Prático: Oferece uma ferramenta para monitoramento em tempo real de sistemas complexos (por exemplo, mercados financeiros, cadeias de suprimentos, redes sociais) onde os relacionamentos evoluem e os pontos de mudança são desconhecidos.
• Avanço Teórico: Estabelece os primeiros limites inferiores minimax para modelos multicamadas dinâmicos e demonstra como métodos espectrais baseados em tensores podem reduzir efetivamente a dimensionalidade e a variância em dados de séries temporais de redes de alta dimensão.
• Robustez: O mecanismo de janelamento adaptativo fornece uma solução robusta para o compromisso viés-variância em ambientes não estacionários, eliminando a necessidade de ajuste manual de tamanhos de janela.