Résumé technique : Apprentissage de structures d'ordre supérieur à partir de données spatio-temporelles incomplètes

1. Formulation du problème

L'article aborde le défi de l'imputation spatio-temporelle dans les réseaux de capteurs, en se concentrant spécifiquement sur les scénarios où les données manquantes ne suivent pas un motif aléatoire uniforme, mais des motifs structurés. Les benchmarks standards supposent souvent une suppression aléatoire uniforme de cellules, pourtant les déploiements réels présentent des défaillances cohérentes telles que :

• Cell-MAR : Cellules manquantes dispersées.
• Block-MAR : Pannes de blocs temporels contigus (par exemple, fenêtres d'étalonnage de 30 minutes).
• Sensor-Kriging : Pannes complètes de capteurs (par exemple, défaillances d'armoires ou nouvelles installations sans historique).

Les méthodes existantes, y compris la complétion de tenseurs de faible rang et le lissage par Laplacien de graphe par paires, échouent souvent dans ces régimes. Elles supposent que les valeurs manquantes peuvent être reconstruites à partir de cellules observées voisines. Cependant, lorsque les lacunes se regroupent dans le temps, l'espace ou le long de capteurs entiers, les priors par paires ne peuvent pas capturer la cohérence de groupe d'ordre supérieur (par exemple, la conservation du flux à une jonction d'autoroute impliquant trois voies ou plus, ou une dérive d'étalonnage partagée au sein d'un cluster de capteurs). Le Laplacien de graphe classique pénalise les différences entre paires, taxant involontairement un mouvement de groupe cohérent que les contraintes physiques sous-jacentes permettent.

Le problème central consiste à récupérer une matrice latente $X^* \in \mathbb{R}^{N \times T}$ à partir d'observations bruitées et incomplètes $Y_{obs}$, où le masque de manquance $M$ crée des absences structurées qui violent les hypothèses des protocoles d'imputation standards.

2. Méthodologie : Laplaciens d'hypergraphes multi-échelles (MSHL)

Les auteurs proposent MSHL, un cadre en deux étapes conçu pour apprendre une structure d'ordre supérieur à partir d'observations incomplètes tout en maintenant des garanties de sécurité lorsque cette structure n'est pas identifiable.

Étape 1 : Découverte (Apprentissage de la structure)

L'étape de découverte construit un Hypergraphe Multi-Échelles $\hat{\mathcal{H}}$ à partir de données incomplètes.

• Squelette linéaire : Il commence par un estimateur de Tikhonov pondéré par la propension inverse (IPW). Ce squelette linéaire utilise un Laplacien de graphe par paires ($\mathcal{L}_G$) pour le lissage spatial et un Laplacien temporel ($\mathcal{L}_T$). Le facteur IPW débiaise la perte empirique pour tenir compte des taux de manquance non uniformes.
• Génération de candidats : Pour identifier des groupes d'ordre supérieur sans vérité terrain, MSHL utilise deux signaux complémentaires :
  1. Topologie a priori : Énumère les hyperarêtes basées sur l'adjacence physique (par exemple, les $K$ premiers voisins). Ce signal est robuste aux pannes complètes de capteurs où aucune observation n'existe.
  2. Corrélations résiduelles : Calcule les corrélations sur les résidus du pré-ajustement par paires. Ce signal capture des motifs de groupe latents (par exemple, des clusters de demande) non alignés avec l'adjacence physique, mais est robuste aux manquances dispersées où les observations conjointes basées sur la topologie sont rares.
• Sélection d'échelle : Le cadre emploie un sélecteur basé uniquement sur l'observation de style Lepski. Il évalue les candidats sur plusieurs tailles d'hyperarêtes ($s=2, \dots, S_{max}$) en utilisant des scores structurels (corrélation résiduelle moyenne et amélioration de l'erreur quadratique moyenne en leaving-one-out). Une pénalité de complexité par échelle $\rho(s-2)$ empêche la sur-sélection aux grandes échelles. Ce sélecteur s'adapte à la « meilleure échelle fixe » jusqu'à un facteur logarithmique sans nécessiter de connaissance préalable du régime.
• Laplacien multi-échelles : L'hypergraphe sélectionné $\hat{\mathcal{H}}$ est converti en un opérateur spatial $\mathcal{L}_H$ en utilisant un poids invariant d'échelle ($w_s = 1/\binom{s}{2}$). Cela garantit que les hyperarêtes de différentes tailles contribuent également à l'énergie de régularisation par paire, évitant ainsi un biais vers des groupes plus grands ou plus petits.

Étape 2 : Raffinement (Correction neuronale)

L'étape de raffinement ajoute un Réseau de Résidus Conditionné par Hypergraphe (HCRN) pour corriger les résidus non linéaires que le squelette linéaire ne peut pas capturer.

• Architecture : Un petit Perceptron Multicouche (MLP) prend en entrée les valeurs résiduelles observées des co-membres d'un capteur cible au sein de l'hypergraphe découvert. Crucialement, les caractéristiques d'entrée sont structurellement orthogonales à la propre valeur de la cellule cible pour éviter des solutions d'identité triviales.
• Mécanisme de sécurité (Différence) : Le réseau est entraîné avec une perte de Huber sur les cellules observées. La conception garantit que la correction nulle est toujours une configuration faisable. Si un capteur n'a aucun co-membre observé (par exemple, dans les régimes de kriging de capteurs), le vecteur de caractéristiques ne contient aucun signal informatif, et le réseau se reporte naturellement à l'estimation linéaire.
• Garantie : Le raffinement fournit une garantie unilatérale. L'erreur au pire cas de l'estimateur raffiné est bornée par l'écart de généralisation de l'estimateur linéaire plus un terme vanissant, garantissant que la correction ne dégrade jamais catastrophiquement les performances.

3. Contributions clés

1. Estimateur d'hypergraphe multi-échelles avec adaptation d'échelle prouvable : L'article introduit un Laplacien d'hypergraphe avec pondération invariante d'échelle et un sélecteur de style Lepski qui s'adapte à l'échelle d'interaction optimale jusqu'à un facteur logarithmique. Il utilise deux sources de candidats (topologie et résidus) avec des taux de récupération exponentiellement séparés pour couvrir le spectre complet des déploiements.
2. Garantie de raffinement unilatérale avec report intégré : Le HCRN est conçu de telle sorte que l'inflation au pire cas par rapport à l'estimateur linéaire s'annule au taux paramétrique. Il reporte automatiquement lorsque aucune caractéristique résiduelle informative n'est disponible, le rendant sûr à activer par défaut.
3. Théorie de bout en bout et validation au niveau du régime : Les auteurs prouvent les garanties de représentation, de découverte, de sélection d'échelle et de raffinement. Empiriquement, la méthode est validée sur deux réseaux de trafic réels (PEMS-BAY et METR-LA) à travers trois régimes de manquance et cinq taux de manquance, démontrant une robustesse là où les méthodes concurrentes s'effondrent.

4. Résultats expérimentaux

L'évaluation compare MSHL à cinq bases de référence (Moyenne des capteurs, kNN-spatial, LETC, WDGTC, et une ablation par paires uniquement Tikh-graph) à travers 30 conditions (2 jeux de données $\times$ 3 régimes $\times$ 5 taux).

• Performance : MSHL améliore la base de référence par graphe par paires (Tikh-graph) dans 22 conditions sur 30 et fait jeu égal dans les 8 restantes dans le bruit d'échantillonnage. Il ne sous-performe jamais la base de référence.
• Robustesse du régime :
  • Block-MAR : MSHL réalise les plus grands gains (jusqu'à 23 % de réduction de l'erreur absolue moyenne sur PEMS-BAY à de faibles taux de manquance) car il peut combler les lacunes en utilisant la cohérence au niveau du groupe lorsque les voisins par paires sont conjointement manquants.
  • Sensor-Kriging : MSHL se dégrade gracieusement vers le squelette linéaire (correspondant à Tikh-graph) lorsque des capteurs entiers sont manquants, tandis que les méthodes basées sur les tenseurs (WDGTC) s'effondrent vers des lignes nulles ou des moyennes globales.
  • Cell-MAR : MSHL surpasse constamment les méthodes de tenseurs et de graphes profonds, évitant les échecs de convergence observés dans les approches d'optimisation alternée à des taux de manquance élevés.
• Sensibilité aux hyperparamètres : La méthode est robuste aux choix d'hyperparamètres. Une seule configuration fonctionne sur tous les régimes et jeux de données, le sélecteur d'échelle se réduisant automatiquement aux ajustements par paires uniquement lorsque la structure d'ordre supérieur n'est pas identifiable.
• Analyse qualitative : Les visualisations montrent que MSHL préserve les cycles diurnes et les motifs des heures de pointe sans lissage spatial excessif ni artefacts temporels. Dans le kriging de capteurs, le lissage des capteurs mis de côté est attribué à la perte d'information nécessaire du squelette linéaire, et non à un échec de la méthode.

5. Signification et revendications

L'article affirme que les données manquantes doivent être traitées comme une preuve de structure à découvrir, et non simplement comme des entrées isolées à remplir.

• Au-delà des priors par paires : Le travail démontre que les motifs de conservation de groupe d'ordre supérieur (par exemple, la conservation du flux) sont des signaux distincts que les priors de graphe par paires ne peuvent pas encoder. MSHL extrait avec succès ces signaux à partir de données incomplètes.
• Sécurité dans le déploiement : La signification principale réside dans le mécanisme de report gracieux. Contrairement aux méthodes qui peuvent produire des sorties absurdes lorsque leurs hypothèses structurelles sont violées, MSHL est « sûr par construction ». Il améliore les estimations là où la structure d'ordre supérieur est identifiable et revient à une estimation linéaire sûre sinon.
• Protocole d'évaluation : Les auteurs soutiennent que les benchmarks standards utilisant une suppression aléatoire uniforme créent un « fossé de déploiement ». Leur protocole d'évaluation, mettant l'accent sur la robustesse du régime à travers des manquances structurées, révèle que les méthodes ajustées à la suppression aléatoire échouent souvent dans des scénarios structurés réels.
• Limitations : Les auteurs reconnaissent que le cadre suppose que la manquance est ignorable (MAR), alors que les capteurs réels peuvent tomber en panne en raison de la saturation du signal (non ignorable). De plus, le sélecteur et les poids non appris actuels garantissent des garanties prouvables mais limitent la découverte de structures imprévues.

En conclusion, MSHL offre une approche principée de l'imputation spatio-temporelle qui combine des priors structurés avec des corrections apprises, assurant la fiabilité dans les conditions spécifiques où les benchmarks actuels sont silencieux.