Reconstructing Network Outbreaks under Group Surveillance

1. Problématique

L'article aborde le problème crucial de la reconstruction de la cascade épidémique à partir d'observations partielles lors d'une épidémie. Contrairement aux travaux antérieurs qui supposent des tests individuels (taille de pool = 1), ce travail se concentre sur le contexte de la surveillance de groupe (ou group surveillance), telle que le dépistage par eaux usées ou la surveillance des bioaérosols.

Dans ce cadre :

• Les échantillons de plusieurs individus sont regroupés en un seul "pool" et testés ensemble.
• Un résultat négatif libère tous les individus du pool.
• Un résultat positif indique qu'au moins un individu est infecté, mais ne révèle pas qui est infecté.

L'objectif est de trouver la cascade la plus probable (Maximum Likelihood Estimation - MLE) qui soit cohérente avec les résultats des tests de groupe. Le défi majeur réside dans le fait qu'un test positif impose une contrainte combinatoire complexe : la cascade reconstruite doit inclure au moins un nœud dans chaque pool positif, sans nécessairement inclure tous les nœuds du pool, tout en minimisant le coût probabiliste de la cascade.

2. Modélisation et Formulation

Les auteurs utilisent le modèle de propagation Independent Cascade (IC) sur un réseau non dirigé $G=(V, E)$.

• Données d'entrée : Un ensemble de pools $\Gamma = \Gamma_0 \cup \Gamma_1$, où $\Gamma_0$ sont les pools négatifs et $\Gamma_1$ les pools positifs.
• Contraintes de cohérence :
  1. La cascade ne doit contenir aucun nœud appartenant aux pools négatifs ($\Gamma_0$).
  2. La cascade doit contenir au moins un nœud de chaque pool positif ($\Gamma_1$).
• Fonction de coût (MLE) : La probabilité d'une cascade est transformée en un coût additif. Le coût d'une cascade $T$ inclut :
  • Le coût des arêtes utilisées pour la transmission ($c_e = -\log p_e$).
  • Le coût des arêtes non utilisées reliant la cascade à des nœuds sains ou à l'extérieur ($d_e = -\log(1-p_e)$).
• Problèmes définis :
  1. PoolCascadeMLE : Reconstruction d'une cascade à partir d'une graine connue (single-seed) sur plusieurs pas de temps.
  2. One-HopCascadeMLE : Cas restreint où la propagation ne dépasse pas un pas de temps après l'ensemencement (pertinent pour les eaux usées ou les fermes). Ici, la graine initiale est inconnue.

3. Résultats de Complexité (Hardness)

Les auteurs démontrent que ces problèmes sont computationnellement difficiles :

• PoolCascadeMLE est NP-dur à approximer dans un facteur de $O(\log^{2-\epsilon} k)$ (où $k$ est le nombre de pools positifs), sauf si P=NP. Cela contraste avec le cas de pools de taille 1, qui admet une approximation $O(\log k)$.
• One-HopCascadeMLE est également NP-dur à approximer dans un facteur de $O(\log k)$.

Ces résultats sont établis par réduction depuis le problème de l'Arbre de Steiner de Groupe (Group Steiner Tree) et du Couverture d'Ensemble Minimum (Minimum Set Cover).

4. Méthodologie et Algorithmes Proposés

Face à la difficulté d'approximation, les auteurs proposent deux algorithmes d'approximation :

A. ApproxCascade (pour PoolCascadeMLE)

Cette méthode réduit le problème au problème de l'Arbre de Steiner de Groupe (Group Steiner Tree - GST) sur un graphe pondéré.

1. Transformation : Le graphe original est transformé en un graphe $G'$ avec des poids sur les nœuds et les arêtes, dérivés des coûts $c_e$ et $d_e$. Les nœuds des pools négatifs sont supprimés.
2. Réduction : Le problème est réduit à trouver un arbre de poids minimum connectant la racine à au moins un nœud de chaque groupe (pool positif).
3. Approximation : En utilisant l'algorithme de Charikar et al. pour l'Arbre de Steiner Dirigé, l'algorithme atteint un ratio d'approximation de $O(k^\epsilon)$ pour un $\epsilon > 0$ fixé.
4. Complexité : $O(k n^{1/\epsilon})$.

B. RoundCascade (pour One-HopCascadeMLE)

Pour le cas "un saut", les auteurs formulent un Programme Linéaire en Nombres Entiers (PLNE) relaxé.

1. Formulation PLNE : Variables indicatrices pour l'ensemencement des nœuds et la transmission sur les arêtes, avec des contraintes assurant la couverture des pools positifs.
2. Relaxation et Arrondi : La solution du PLNE relaxé (valeurs fractionnaires) est arrondie de manière aléatoire (Randomized Rounding) avec un facteur d'échelle $\alpha = 1 + \ln k$.
3. Garantie : L'algorithme est un $(2 + 2 \ln k)$-approximation randomisée. La probabilité de produire une solution non réalisable est très faible ($O(1/n^c)$).

5. Résultats Expérimentaux

Les méthodes ont été évaluées sur des réseaux synthétiques (Barabási-Albert, Erdős-Rényi) et réels (réseau de l'ICU de l'hôpital UVA, réseau d'une petite ville virtuelle).

• Métriques : Récupération des infections manquantes (F1-score) et estimation de la prévalence (erreur relative).
• Comparaison : Les algorithmes proposés sont comparés à des baselines qui réduisent artificiellement la taille des pools à 1 (en choisissant un nœud aléatoire ou tous les nœuds du pool).
• Constats clés :
  • Performance supérieure : ApproxCascade surpasse significativement les baselines, surtout dans les régimes de faible probabilité de diffusion.
  • Impact de la taille du pool : La performance diminue à mesure que la taille du pool augmente (complexité combinatoire croissante), mais reste supérieure aux baselines.
  • Estimation de prévalence : La méthode tend à sous-estimer légèrement la taille de l'épidémie (typique des approches MLE), mais reste plus précise que les méthodes de base.
  • RoundCascade : Surpasse également la baseline aléatoire pour la récupération des infections dans le cas "un saut".

6. Limites et Observations Critiques

L'article met en lumière des limites importantes de l'approche MLE :

• Échec de reconstruction : Il existe des cas où la solution MLE ne retrouve aucune partie de la cascade réelle (ground truth). Cela se produit lorsque la structure des pools force la sélection d'un chemin "moins coûteux" mais incorrect, plutôt que le chemin réel plus coûteux.
• Sensibilité au bruit : Une petite quantité de bruit (faux positifs/négatifs) dans les tests peut modifier radicalement la solution MLE, la rendant très éloignée de la réalité.
• Importance des tests chevauchants : Les auteurs suggèrent que des tests de pools qui se chevauchent (partageant des nœuds) sont plus puissants pour la reconstruction que des tests disjoints, contrairement à certaines optimisations de dépistage classiques.

7. Contribution et Signification

Contributions principales :

1. Introduction formelle du problème PoolCascadeMLE, généralisant la reconstruction d'épidémies aux tests de groupe.
2. Preuve de la difficulté d'approximation (NP-dur) de ce problème, même pour des versions restreintes.
3. Développement d'algorithmes d'approximation théoriquement garantis (ApproxCascade et RoundCascade).
4. Validation empirique montrant que la prise en compte explicite de la structure des pools améliore considérablement la reconstruction par rapport aux méthodes qui traitent les pools comme des individus isolés.

Signification :
Ce travail est pionnier car il comble un vide entre la surveillance environnementale (eaux usées, etc.) et la modélisation mathématique des épidémies. Il fournit des outils algorithmiques pour interpréter les données de surveillance de groupe, ce qui est crucial pour la prise de décision en santé publique lorsque les tests individuels sont limités ou trop coûteux. Il souligne également la nécessité de concevoir des stratégies de surveillance (choix des pools) optimisées pour la reconstruction, et non seulement pour le dépistage.