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

1. Énoncé du problème

Le papier aborde le défi de l'analyse des réseaux multilayers dynamiques, où un ensemble commun de nœuds interagit à travers plusieurs types de relations (couches) qui évoluent dans le temps. Les méthodes existantes souffrent souvent de trois limitations :

1. Indépendance temporelle : Elles supposent que les instantanés du réseau sont indépendants, ignorant la dépendance temporelle intrinsèque des systèmes réels (par exemple, réseaux d'échanges, interactions sociales).
2. Focus monocouche : Elles échouent à capturer les corrélations structurelles entre les différentes couches.
3. Hypothèse de stationnarité : Elles supposent que la dynamique sous-jacente du réseau est stationnaire, échouant à s'adapter aux dérives progressives ou aux changements structurels abrupts (par exemple, changements de politiques, crises).

Les auteurs visent à développer un cadre qui modélise explicitement la dépendance temporelle via un mécanisme autorégressif, gère les structures multilayers et fournit des procédures d'apprentissage en ligne adaptatif pour les environnements stationnaires et non stationnaires.

2. Méthodologie

A. Le modèle : AR(1)-MSBM

Les auteurs proposent le Modèle de Blocs Stochastiques Multilayers Autorégressif d'Ordre 1 (AR(1)-MSBM).

• Structure : Une séquence de tenseurs d'adjacence $\{A_t\}_{t \geq 0} \in \{0, 1\}^{n \times n \times L}$, où $n$ est le nombre de nœuds, $L$ le nombre de couches et $K$ le nombre de communautés.
• Dynamique des arêtes : Contrairement aux SBM statiques, les arêtes évoluent via un mécanisme de « rafraîchissement ». Entre les temps $t-1$ et $t$, une arête $(i, j, l)$ peut :
  • Se former (0 $\to$ 1) avec la probabilité $\Theta_{i,j,l}$.
  • Se dissoudre (1 $\to$ 0) avec la probabilité $\Delta_{i,j,l}$.
  • Persister avec la probabilité $1 - \Theta_{i,j,l} - \Delta_{i,j,l}$.
• Structure latente : Les probabilités de transition sont des tenseurs de rang faible déterminés par une matrice d'appartenance communautaire partagée $Z$ et des tenseurs de connectivité spécifiques aux couches $W$ (formation) et $M$ (dissolution) :
  $$\Theta_{i,j,l} = Z_i W_{:,:,l} Z_j^\top, \quad \Delta_{i,j,l} = Z_i M_{:,:,l} Z_j^\top$$
• Non-stationnarité : Dans le cadre non stationnaire, $W_t$ et $M_t$ varient dans le temps, permettant à la fois des points de changement abrupts et des dérives progressives, tandis que $Z$ reste fixe (bien que le cadre puisse être étendu à un $Z$ variant dans le temps).

B. Estimation stationnaire (Algorithme 1)

Pour le cas stationnaire, les auteurs proposent une Procédure d'estimation en ligne :

1. Statistiques suffisantes récursives : Maintien des comptes cumulatifs des transitions d'arêtes (0$\to$1, 1$\to$0) et des arêtes actives. Ces comptes sont mis à jour en $O(n^2 L)$ par étape sans revisiter les données passées.
2. Estimateurs initiaux : Calcul d'estimateurs du maximum de vraisemblance (MLE) sous forme close pour $\Theta$ et $\Delta$ basés sur ces comptes.
3. Raffinement spectral tensoriel : Pour améliorer la précision, application de l'Analyse en Composantes Principales Hétéroscédastique Tensorielle (TH-PCA). Cela exploite la structure de Tucker de rang faible des tenseurs. Crucialement, ce raffinement n'est effectué qu'à des intervalles de temps géométriquement espacés ($t = 2^m$) pour minimiser le coût computationnel.
4. Récupération des communautés : Regroupement du sous-espace singulier estimé de la matricisation de mode-1 pour récupérer les appartenances communautaires.

C. Estimation non stationnaire (Algorithme 2)

Pour le cas non stationnaire, les auteurs introduisent un Algorithme en ligne adaptatif à fenêtre glissante :

1. Fenêtrage adaptatif : Au lieu d'utiliser une fenêtre fixe ou l'historique complet, l'algorithme sélectionne dynamiquement une taille de fenêtre de retour $\hat{k}_t$.
2. Critère de stabilité : Inspiré par Huang et Wang (2024), l'algorithme compare la perte empirique de la fenêtre actuelle à celle de fenêtres imbriquées plus petites. Il sélectionne la plus grande fenêtre restant « stable » (c'est-à-dire que la différence de perte ne dépasse pas un seuil de tolérance $\tau(t)$).
3. Grille dynamique : Pour assurer l'efficacité computationnelle, les tailles de fenêtres candidates sont restreintes à une grille géométrique dynamique, réduisant le stockage de $O(t)$ à $O(\log t)$.
4. Segmentation quasi-stationnaire : L'analyse théorique suppose que la série temporelle peut être partitionnée en « segments quasi-stationnaires » où la dérive est contrôlée par une fonction $V(t)$ et satisfait la « monotonie dominante » (empêchant l'annulation des dérives positives et négatives).

3. Contributions clés

1. Cadre de modèle novateur : Introduction du AR(1)-MSBM, qui unifie la structure multilayer avec une dépendance temporelle explicite via les probabilités de formation/dissolution des arêtes.
2. Estimation minimax optimale (Stationnaire) :
   • Dérivation de bornes d'estimation non asymptotiques pour les tenseurs de transition $\Theta$ et $\Delta$.
   • Preuve de l'optimalité minimax (établissant la première borne inférieure minimax pour les modèles de réseaux multilayers dynamiques).
   • Démonstration que l'exploitation de la structure multilayer réduit le taux d'erreur stochastique de $O(1/\sqrt{t})$ à $O(1/\sqrt{tL})$.
3. Apprentissage adaptatif non stationnaire :
   • Développement d'un algorithme qui s'adapte automatiquement aux changements structurels inconnus (abrupts ou progressifs) sans connaissance préalable des points de changement.
   • Garanties théoriques montrant que l'erreur d'estimation correspond au taux stationnaire lorsqu'elle est appliquée par segment, la taille d'échantillon effective étant déterminée par la longueur locale du segment.
4. Garanties de récupération des communautés :
   • Établissement de conditions pour une récupération des communautés cohérente au sens de Hamming (erreur fractionnelle qui s'annule) et exacte (erreur nulle).
   • Amélioration des résultats monocouches existants en évitant les termes de biais associés à la normalisation diagonale dans les méthodes basées sur le Laplacien.

4. Résultats théoriques

• Taux d'estimation :
  • Dans le cadre stationnaire, l'erreur de Frobenius pour l'estimation de $\Theta$ et $\Delta$ évolue comme suit :
    $$\|\hat{\Theta}_t - \Theta\|_F \lesssim \sqrt{\frac{nK + Lr + K^2r}{t}} + \frac{n\sqrt{L}}{t}$$
    où le premier terme est l'erreur stochastique et le second le biais.
  • Le terme de biais ($O(1/t)$) est un artefact connu des MLE autorégressifs mais devient négligeable lorsque $t$ croît par rapport à la taille du réseau.
• Borne inférieure minimax : Le papier prouve que le taux $O(\sqrt{(rK^2 + n\log K + Lr)/T})$ est optimal, correspondant à la borne supérieure à des facteurs logarithmiques et un écart computationnel ($K$ vs $\log K$) près.
• Taux non stationnaires : Dans le cadre de la segmentation quasi-stationnaire, l'erreur dépend de la longueur locale du segment $t - T_{g-1}$ et de l'enveloppe de dérive $V(\cdot)$. Si $V(t) = t^{-1/2}$, le taux correspond au taux stationnaire appliqué localement.

5. Résultats expérimentaux

• Simulations :
  • Stationnaire : La méthode proposée surpasse les estimateurs cumulatifs statiques (qui ignorent la dépendance temporelle) et les estimateurs agrégés par couche (qui perdent la structure spécifique aux couches), en particulier dans les scénarios à signaux faibles ou à structures de couches opposées.
  • Non stationnaire : L'algorithme adaptatif détecte avec succès les changements abrupts et suit les dérives progressives. Il surpasse systématiquement les références basées sur l'historique complet (biais élevé après les changements) et les fenêtres fixes (variance ou biais élevé selon le choix de la fenêtre).
• Données réelles (Transport aérien aux États-Unis) :
  • Analyse des données mensuelles de vols (2015–2025) à travers 4 grands transporteurs.
  • L'algorithme a détecté une rupture structurelle significative à mi-2020 (pandémie de COVID-19), témoignée par un pic dans les taux de basculement des communautés et une contraction de la fenêtre de retour sélectionnée.
  • Après 2022, la taille de la fenêtre s'est élargie, indiquant une stabilisation du réseau, et le modèle a capturé le déclin progressif de la connectivité du réseau (persistance) et l'augmentation du turnover des itinéraires.

6. Importance

Ce papier comble un fossé critique en science des réseaux en fournissant un cadre théorique et algorithmique rigoureux pour les réseaux dynamiques, multilayers et non stationnaires.

• Impact pratique : Il offre un outil pour la surveillance en temps réel de systèmes complexes (par exemple, marchés financiers, chaînes d'approvisionnement, réseaux sociaux) où les relations évoluent et où les points de changement sont inconnus.
• Avancement théorique : Il établit les premières bornes inférieures minimax pour les modèles multilayers dynamiques et démontre comment les méthodes spectrales basées sur les tenseurs peuvent efficacement réduire la dimensionalité et la variance dans les données de réseaux en séries temporelles de haute dimension.
• Robustesse : Le mécanisme de fenêtrage adaptatif fournit une solution robuste au compromis biais-variance dans les environnements non stationnaires, éliminant le besoin d'un réglage manuel des tailles de fenêtres.