Directed Graph Topology Inference via Graph Filter Identification

Résumé Technique : Inférence de la Topologie de Graphes Dirigés via l'Identification de Filtres de Graphe

Énoncé du Problème
L'article traite du défi de l'inférence de la topologie d'un graphe dirigé (digraphe) à partir de mesures nodales générées par une dynamique de diffusion linéaire. Contrairement aux travaux antérieurs axés sur les graphes non orientés avec des excitations de signaux blancs, ce problème considère un cadre général où :

1. Le réseau sous-jacent est un graphe dirigé avec un opérateur de décalage de graphe (GSO) non symétrique, $S$.
2. Les signaux observés, $y$, sont générés par un filtre de convolution de graphe (un polynôme de $S$) agissant sur des signaux d'entrée, $x$.
3. Les signaux d'entrée ne sont pas nécessairement blancs ; ils possèdent des corrélations arbitraires décrites par des matrices de covariance connues $C_{x,m}$.
4. Les coefficients du filtre et la structure du graphe sont inconnus.

La difficulté principale réside dans le fait que, pour les graphes dirigés, le GSO et la matrice de covariance d'observation ne sont pas simultanément diagonalisables, ce qui rend inapplicables les approches spectrales standards pour les graphes non orientés. L'objectif est de récupérer le GSO le plus creux possible qui explique les données observées compte tenu de la connaissance statistique préalable des entrées.

Méthodologie
Les auteurs proposent un cadre d'inférence en deux étapes, suivi d'une approche d'optimisation conjointe pour améliorer la complexité d'échantillonnage.

1. Étape 1 : Identification du Filtre de Diffusion Asymétrique

   • Formulation : Le problème est modélisé comme un système d'équations matricielles quadratiques : $C_{y,m} = H C_{x,m} H^\top$, où $H$ est le filtre inconnu et $C_{y,m}$ est la covariance de sortie estimée.
   • Identifiabilité : Les auteurs établissent que le filtre $H$ est identifiable (à un signe près) si les covariances d'entrée présentent une diversité spectrale suffisante. Plus précisément, le Théorème 1 prouve qu'avec $M=4$ processus, l'unicité est garantie si les bases propres des entrées sont suffisamment distinctes et si les valeurs propres satisfont des conditions de rang de Kruskal spécifiques.
   • Algorithme : Pour résoudre ce système non convexe, le problème est reformulé comme une minimisation quadratique lisse soumise à des contraintes de la variété de Stiefel (contraintes d'orthogonalité sur les matrices de rotation). Un algorithme de Minimisation Alternée Inexacte (IAM) est développé, utilisant la descente de gradient de Riemann pour les variables de la variété et des mises à jour en forme fermée pour le filtre $H$.

2. Étape 2 : Inférence de la Topologie du Digraphe

   • Formulation : Étant donné le filtre estimé $\hat{H}$, l'objectif est de trouver un GSO $S$ creux tel que $HS = SH$ (commutativité), garantissant que $H$ est un polynôme de $S$.
   • Algorithme : Les auteurs formulent cela comme un problème de minimisation de la norme $\ell_1$ convexe avec une contrainte de commutativité relaxée. Un algorithme de Gradient Proximal (PG) est employé, qui gère efficacement la contrainte de parcimonie et les contraintes structurelles (ex: poids non négatifs, absence de boucles sur soi-même) via un opérateur proximal personnalisé.

3. Identification Conjointe (Boucle Fermée)

   • Pour améliorer les performances, les auteurs proposent une formulation conjointe qui alterne entre l'identification du filtre et l'inférence de la topologie. Cette approche en "boucle fermée" utilise l'estimation actuelle de $S$ pour régulariser l'estimation du filtre et vice versa.
   • Convergence : Un algorithme prouvable de convergence (Algorithme 3) est présenté, qui alterne entre des étapes de Gradient Proximal pour $S$, des étapes de gradient de Riemann pour les variables de la variété, et des étapes de gradient euclidien pour $H$. L'analyse théorique confirme la convergence vers un point critique sous des hypothèses modérées.

Contributions Clés

• Généralisation aux Graphes Dirigés : Ce travail étend l'identification de filtres de graphe des opérateurs symétriques (non orientés) aux opérateurs asymétriques (dirigés), traitant la non-diagonalisabilité du GSO et de la covariance de sortie.
• Théorie de l'Identifiabilité : L'article fournit des conditions rigoureuses (Théorème 1) sous lesquelles un filtre de diffusion asymétrique est univoquement identifiable à partir des statistiques de second ordre de multiples processus d'entrée-sortie, soulignant la nécessité d'une diversité spectrale des entrées.
• Algorithmes Nouveaux :
  • Un algorithme IAM pour l'identification de filtres sur la variété de Stiefel.
  • Une méthode de Gradient Proximal pour récupérer des topologies dirigées creuses.
  • Un algorithme conjoint en boucle fermée qui renforce mutuellement l'estimation du filtre et de la topologie.
• Garanties de Convergence : L'article fournit une analyse de convergence pour le problème non convexe conjoint impliquant la parcimonie $\ell_1$, les contraintes de variété et le couplage de commutativité, en utilisant la propriété de Kurdyka–Łojasiewicz (KL).

Résultats Expérimentaux
Les méthodes proposées ont été évaluées sur des données synthétiques et des études de cas réels :

• Données Synthétiques : Les expériences sur des graphes Erdős–Rényi, Barabási–Albert et des modèles de blocs stochastiques (SBM) démontrent que l'approche conjointe (boucle fermée) surpasse significativement l'approche en deux étapes (boucle ouverte), particulièrement lorsque le nombre de processus d'entrée ($M$) ou d'échantillons ($P$) est limité. La méthode conjointe atteint une récupération de support quasi parfaite avec moins d'échantillons que la méthode en boucle ouverte.
• Données Réelles (Mobilité Urbaine) : Appliqué aux données de trajets Uber à New York, l'algorithme a inféré un graphe de mobilité dirigé. Contrairement aux modèles non orientés, la méthode proposée a capturé les flux de trafic asymétriques, identifiant correctement les flux sortants dominants de Manhattan vers les banlieues résidentielles et les aéroports, ce qui est cohérent avec les modèles de trajet du soir.
• Données Réelles (Optimisation de Portefeuille) : Dans une application financière utilisant des données boursières, les graphes inférés par la méthode proposée ont conduit à des portefeuilles présentant des rendements nettement plus élevés par rapport aux bases de référence (GFI, TITD) et à l'allocation uniforme, sous des stratégies de pondération par degré inverse et par centralité de vecteur propre inverse.

Signification et Revendications
L'article affirme que sa principale importance réside dans la fourniture d'un cadre unifié pour l'inférence de la topologie de réseaux dirigés qui ne repose pas sur l'hypothèse restrictive de stationnarité du graphe (qui implique la symétrie). En exploitant la relation structurelle entre les filtres de graphe et les opérateurs de décalage, la méthode récupère les relations causales ou directionnelles fondamentales dans un réseau.

Les auteurs notent que bien que l'approche soit efficace, elle comporte des compromis : elle nécessite plusieurs processus d'entrée pour assurer l'identifiabilité et implique une complexité de calcul cubique ($O(N^3)$) par itération. L'article se positionne comme une avancée méthodologique pour les applications où la directionnalité est critique, telles que la découverte causale, les réseaux de transport et la modélisation des dépendances financières, offrant une alternative plus précise aux outils d'apprentissage de graphes symétriques.