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

Technische Samenvatting: Een Snel Algoritme voor de Finite Expression Method in Leerdynamica op Complexe Netwerken

Probleemstelling
Het artikel behandelt de uitdaging van het ontdekken van de onderliggende natuurkundige wetten en dynamische interacties binnen complexe netwerksystemen op basis van tijdreeksgegevens. Hoewel datagestuurde methoden geavanceerd zijn geworden in het blootleggen van vergelijkingen voor continue systemen (bijv. PDE's), blijft het extraheren van dynamica uit netwerkgegevens moeilijk door drie primaire factoren:

1. Computationele Complexiteit: In een netwerk met $N$ knopen resulteert het modelleren van volledige paargewijze interacties doorgaans in een $O(N^2)$ complexiteit, wat prohibitief is voor grootschalige real-world netwerken.
2. Datakwaliteit: Real-world netwerkgegevens zijn vaak ruizig, schaars en kunnen topologische onnauwkeurigheden bevatten (ontbrekende of spookverbindingen).
3. Interpreteerbaarheid en Voorkennis: Bestaande methoden zoals SINDy (Sparse Identification of Nonlinear Dynamics) vereisen vaak grote bibliotheken van kandidaatfuncties en directe toegang tot tijdsafgeleiden, die frequent niet beschikbaar zijn. Deep learning-benaderingen (bijv. Graph Neural Networks) missen interpreteerbaarheid en fungeren als "black boxes".

Methodologie: De Finite Expression Method (FEX)
De auteurs stellen de Finite Expression Method (FEX) voor, een nieuwe benadering die netwerkdynamica representeert met behulp van binaire bomen bestaande uit eindige wiskundige operatoren. De systeemdynamica wordt gemodelleerd als:
$$\frac{dx_i(t)}{dt} = F(x_i(t)) + \sum_{j=1}^N A_{ij}G(x_i(t), x_j(t))$$
waarbij $F$ de zelfdynamica representeert en $G$ de interactiedynamica representeert.

Kerncomponenten van FEX:

• Binaire Boomrepresentatie: Dynamica wordt gecodeerd als binaire bomen waarbij knopen wiskundige operatoren zijn (unair: $\sin, \cos, \exp$; binair: $+, -, \times$). Bladknopen opereren op invoervariabelen met leerbare gewichten en biases. Deze structuur maakt het mogelijk om complexe functionele composities te genereren uit een kleine woordenlijst van operatoren, wat de noodzaak voor grote vooraf gedefinieerde bibliotheken vermindert.
• Combinatorische Optimalisatie via Reinforcement Learning (RL): Het identificeren van de optimale boomstructuur wordt geframed als een combinatorisch optimalisatieprobleem. Een controller-netwerk (een volledig verbonden neuraal netwerk) wordt getraind met een policy gradient-aanpak om waarschijnlijkheidsmassafuncties te produceren voor de selectie van operatoren bij elke boomknoop. Het doel is om operatorsequenties te samplen die een beloningsscore maximaliseren.
• Stochastisch Algoritme voor Schaalbaarheid: Om de $O(N^2)$ bottleneck van het berekenen van paargewijze interacties te overwinnen, integreert FEX een stochastisch algoritme geïnspireerd door Random Batch Methods. Tijdens de optimalisatie van de verliesfunctie worden knopen gegroepeerd in willekeurige batches, en worden interacties alleen binnen deze batches berekend. Dit vermindert de computationele complexiteit van de structuurontdekking van $O(N^2)$ naar $O(N)$.
• Twee-fasen Optimalisatie:
  1. Coarse-tuning: De controller wordt getraind om hoog scorende operatorsequenties te vinden met een mix van eerste-orde (bijv. Adam) en tweede-orde (bijv. BFGS) optimalisatie op de continue parameters, waarbij gebruik wordt gemaakt van de stochastische batch-aanpak voor snelheid.
  2. Fine-tuning: Zodra de best presterende kandidaatstructuren zijn geïdentificeerd, worden de coëfficiënten verfijnd met behulp van het volledige interactiemodel om een hoge nauwkeurigheid te garanderen.

Belangrijkste Bijdragen

1. Nieuwe Representatie: FEX gebruikt een binaire boomstructuur om dynamica te representeren, wat het ontdekken van complexe vergelijkingen mogelijk maakt met een minimale woordenlijst van operatoren, in tegenstelling tot SINDy dat afhankelijk is van uitgebreide kandidaatbibliotheken.
2. Afgeleide-vrije Estimatie: De methode schat tijdsafgeleiden direct in van ruizige tijdreeksgegevens met behulp van numerieke differentiatie, waardoor de vereiste voor directe toegang tot afgeleiden die veel bestaande methoden teistert, wordt weggenomen.
3. Schaalbaarheid: Door een stochastische selectie van particle batches toe te passen tijdens de combinatorische optimalisatiefase, bereikt het FEX-algoritme een lineaire schaling ($O(N)$) in computationele kosten, wat het haalbaar maakt voor grote netwerken.
4. Robuustheid: De methode is ontworpen om lage-resolutie gegevens, observationele ruis en topologische onnauwkeurigheden (ontbrekende of spookverbindingen) te verwerken.

Experimentele Resultaten
De auteurs evalueerden FEX op drie klassieke dynamische systemen (Hindmarsh-Rose, FitzHugh-Nagumo en gekoppelde Rössler-oscillatoren) over diverse netwerktopologieën, inclus\n bij Erdős-Rényi en Scale-Free netwerken.

• Nauwkeurigheid: FEX identificeerde succesvol de correcte functionele vormen en coëfficiënten (met relatieve fouten vaak <1%) voor alle geteste dynamica.
• Ruisbestendigheid: In experimenten met Signal-to-Noise Ratios (SNR) van 40 en 45 presteerde FEX beter dan baseline-methoden (Two-Phase SINDy en ARNI), die moeite hadden met het identificeren van correcte termen of redundante termen produceerden onder ruizige omstandigheden.
• Topologische Robuustheid: FEX behield een hoge nauwkeurigheid, zelfs wanneer 15% van de netwerkverbindingen willekeurig werd toegevoegd of verwijderd.
• Dataschaarste: De methode bleef effectief met slechts 5% tot 10% van de oorspronkelijke tijdreeksgegevens beschikbaar.
• Efficiëntie: Log-log plots van de computationele tijd versus de netwerkgrootte toonden aan dat het stochastische-FEX algoritme lineair schaalt ($O(N)$), terwijl het volledige interactiemodel kwadratisch schaalt ($O(N^2)$).

Betekenis en Claims
Het artikel beweert dat FEX een robuust, interpreteerbaar en computationeel efficiënt kader biedt voor het leren van dynamica op complexe netwerken. Door reinforcement learning te combineren met stochastische optimalisatie voor schaalbaarheid, pakt FEX de beperkingen van huidige methoden aan met betrekking tot computationele kosten, datakwaliteit en de behoefte aan uitgebreide voorkennis. De auteurs stellen dat deze benadering de ontdekking van natuurkundige wetten in real-world complexe systemen mogelijk maakt waar de onderliggende vergelijkingen voorheen onbekend of onverkend waren, wat een pad biedt voor analyse in domeinen variërend van biologie tot epidemiologie. Het werk erkent beperkingen, zoals de huidige focus op paargewijze interacties en deterministische dynamica, en merkt op dat uitbreidingen naar hogere-orde koppelingen en stochastische differentiaalvergelijkingen potentiële toekomstige richtingen zijn.