A Fast Algorithm for the Finite Expression Method in Learning Dynamics on Complex Networks

Résumé Technique : Un Algorithme Rapide pour la Méthode de l'Expression Finie dans l'Apprentissage de la Dynamique sur les Réseaux Complexes

Énoncé du Problème
Le document traite du défi consistant à découvrir les lois physiques régissantes et les interactions dynamiques au sein de systèmes de réseaux complexes à partir de données de séries temporelles. Bien que les méthodes pilotées par les données aient progressé dans la découverte d'équations pour les systèmes continus (par exemple, les EDP), l'extraction de la dynamique à partir de données de réseaux reste difficile en raison de trois facteurs principaux :

1. Complexité Computationnelle : Dans un réseau possédant $N$ nœuds, la modélisation des interactions par paires complètes entraîne généralement une complexité de $O(N^2)$, ce qui est prohibitif pour les réseaux réels à grande échelle.
2. Qualité des Données : Les données de réseaux du monde réel sont souvent bruitées, éparses et peuvent contenir des inexactitudes topologiques (liens manquants ou spécieux).
3. Interprétabilité et Connaissances Préalables : Les méthodes existantes comme SINDy (Identification Sparse de la Dynamique Non Linéaire) nécessitent souvent de vastes bibliothèques de fonctions candidates et un accès direct aux dérivées temporelles, qui sont fréquemment indisponibles. Les approches d'apprentissage profond (par exemple, les réseaux de neurones sur graphes) manquent d'interprétabilité, fonctionnant comme des « boîtes noires ».

Méthodologie : La Méthode de l'Expression Finie (FEX)
Les auteurs proposent la Méthode de l'Expression Finie (FEX), une approche novatrice qui représente la dynamique des réseaux à l'aide d'arbres binaires composés d'opérateurs mathématiques finis. La dynamique du système est modélisée comme :
$$\frac{dx_i(t)}{dt} = F(x_i(t)) + \sum_{j=1}^N A_{ij}G(x_i(t), x_j(t))$$
où $F$ représente l'autodynamique et $G$ représente la dynamique d'interaction.

Composants Clés de FEX :

• Représentation par Arbre Binaire : La dynamique est encodée sous forme d'arbres binaires où les nœuds sont des opérateurs mathématiques (unaires : $\sin, \cos, \exp$ ; binaires : $+, -, \times$). Les nœuds feuilles opèrent sur des variables d'entrée avec des poids et des biais apprenables. Cette structure permet la génération de compositions fonctionnelles complexes à partir d'un petit dictionnaire d'opérateurs, réduisant ainsi le besoin de vastes bibliothèques prédéfinies.
• Optimisation Combinatoire via l'Apprentissage par Renforcement (RL) : L'identification de la structure d'arbre optimale est formulée comme un problème d'optimisation combinatoire. Un réseau de contrôle (un réseau de neurones entièrement connecté) est entraîné à l'aide d'une approche de gradient de politique pour produire des fonctions de masse de probabilité pour la sélection d'opérateurs à chaque nœud de l'arbre. L'objectif est d'échantillonner des séquences d'opérateurs qui maximisent un score de récompense.
• Algorithme Stochastique pour la Scalabilité : Pour surmonter le goulot d'étranglement $O(N^2)$ du calcul des interactions par paires, FEX intègre un algorithme stochastique inspiré des méthodes de lots aléatoires (Random Batch Methods). Lors de l'optimisation de la fonction de perte, les nœuds sont regroupés en lots aléatoires, et les interactions sont calculées uniquement au sein de ces lots. Cela réduit la complexité computationnelle de la phase de découverte de structure de $O(N^2)$ à $O(N)$.
• Optimisation en Deux Phases :
  1. Affinage Grossier (Coarse-tuning) : Le contrôleur est entraîné pour trouver des séquences d'opérateurs à haut score en utilisant un mélange d'optimisations du premier ordre (ex: Adam) et du second ordre (ex: BFGS) sur les paramètres continus, en utilisant l'approche de lot stochastique pour la rapidité.
  2. Affinage Fin (Fine-tuning) : Une fois les structures candidates les plus performantes identifiées, les coefficients sont affinés à l'aide du modèle d'interaction complet pour garantir une haute précision.

Contributions Clés

1. Représentation Novatrice : FEX utilise une structure d'arbre binaire pour représenter la dynamique, permettant la découverte d'équations complexes avec un dictionnaire minimal d'opérateurs, contrairement à SINDy qui repose sur de vastes bibliothèques de candidats.
2. Estimation Sans Dérivée : La méthode estime les dérivées temporelles directement à partir de données de séries temporelles bruitées en utilisant la différenciation numérique, supprimant l'exigence d'un accès direct aux dérivées qui entrave de nombreuses méthodes existantes.
3. Scalabilité : En employant une sélection stochastique de lots de particules lors de la phase d'optimisation combinatoire, l'algorithme atteint une mise à l'échelle linéaire ($O(N)$) de son coût de calcul, ce qui le rend réalisable pour de grands réseaux.
4. Robustesse : La méthode est conçue pour gérer les données à basse résolution, le bruit d'observation et les inexactitudes topologiques (liens manquants ou spécieux).

Résultats Expérimentaux
Les auteurs ont évalué FEX sur trois systèmes dynamiques classiques (Hindmarsh-Rose, FitzHugh-Nagumo et oscillateurs de Rössler couplés) à travers diverses topologies de réseaux, incluant les réseaux d'Erdős-Rényi et Scale-Free.

• Précision : FEX a identifié avec succès les formes fonctionnelles et les coefficients corrects (avec des erreurs relatives souvent <1 %) pour toutes les dynamiques testées.
• Robustesse au Bruit : Dans des expériences avec des rapports signal sur bruit (SNR) de 40 et 45, FEX a surpassé les méthodes de référence (Two-Phase SINDy et ARNI), qui peinaient à identifier les termes corrects ou produisaient des termes redondants dans des conditions bruitées.
• Robustesse Topologique : FEX a maintenu une haute précision même lorsque 15 % des liens du réseau étaient ajoutés ou supprimés de manière aléatoire.
• Rareté des Données : La méthode est restée efficace avec seulement 5 % à 10 % des données de séries temporelles originales disponibles.
• Efficacité : Les graphiques log-log du temps de calcul par rapport à la taille du réseau ont démontré que l'algorithme stochastique-FEX passe à une échelle linéaire ($O(N)$), tandis que le modèle d'interaction complet passe à une échelle quadratique ($O(N^2)$).

Signification et Revendications
L'article affirme que FEX fournit un cadre robuste, interprétable et efficace sur le plan computationnel pour apprendre la dynamique sur des réseaux complexes. En combinant l'apprentissage par renforcement pour la recherche structurelle avec l'optimisation stochastique pour la scalabilité, FEX répond aux limitations des méthodes actuelles concernant le coût de calcul, la qualité des données et le besoin de connaissances préalables étendues. Les auteurs soutiennent que cette approche permet la découverte de lois physiques dans des systèmes complexes du monde réel dont les équations directrices sont auparavant inconnues ou sous-explorées, offrant une voie pour analyser des systèmes allant de la biologie à l'épidémiologie. Le travail reconnaît des limites, telles que l'accent actuel sur les interactions par paires et les dynamiques déterministes, notant que les extensions aux couplages d'ordre supérieur et aux équations différentielles stochastiques sont des directions futures potentielles.