Decentralised Federated Learning over Temporal Networks: The Role of Heterogeneities

Technische Samenvatting: Gedecentraliseerd Federated Learning over Temporale Netwerken

Probleemstelling
Decentralised Federated Learning (DFL) maakt training van machine learning op apparaten mogelijk via peer-to-peer communicatie zonder een centrale coördinator, wat privacy en robuustheid tegen single points of failure biedt. Hoewel DFL vaak wordt geanalyseerd onder geïdealiseerde aannames—zoals synchrone updates, statische netwerktopologieën of regelmatige communicatie-intervallen—vertonen real-world edge-omgevingen (bijv. smartphones, IoT, autonome voertuigen) inherente structurele en temporale inhomogeniteiten. Deze omvatten onregelmatige connectiviteit, bursty communicatiepatronen en ruimtelijke beperkingen. Het artikel betoogt dat de rol van deze inhomogeniteiten in volledig gedecentraliseerde settings nog onvoldoende begrepen is, en dat standaard experimentele opstellingen de convergentiesnelheden systematisch overschatten door de complexe dynamiek van real-world temporale netwerken te negeren.

Methodologie
De auteurs vestigen een theoretische mapping tussen DFL-dynamica en diffusieprocessen op temporale netwerken. Hun aanpak omvat twee complementaire analytische kaders:

1. Vroege Synchronisatie: De auteurs modelleren de propagatie van initiële modelparameters als een lazy random-walk diffusieproces op een temporaal netwerk. Door de invloed van initiële knoopparameters op de systeemtoestand op tijdstip $t$ te volgen, demonstreren zij dat de mengingsdynamica isomorf is aan een tijd-omgekeerde lazy random walk. Zij maken gebruik van de Inverse Participation Ratio (IPR) van de waarschijnlijkheidsverdeling van de random walk als metriek voor de mengingssnelheid; een sneller verval van de IPR duidt op snellere delokalisatie en dus snellere convergentie.
2. Stationair Regime: In de stationaire fase, waar lokaal leren domineert, behandelen de auteurs lokale trainingsupdates als perturbaties. Zij tonen aan dat de herverdeling van deze perturbaties door het netwerk wordt beheerst door dezelfde lineaire diffusieoperator (de gewogen Laplaciaan van het temporale netwerk) afgeleid van de aggregatiestap, zelfs in aanwezigheid van niet-lineaire leerupdates (onder aannames van kleine discrepanties).

Om deze bevindingen te valideren, gebruikt de studie:

• Synthetische Netwerken: Geometrische random graphs om de effecten van ruimtelijke dimensionaliteit en afstand-verval te isoleren, en renewal/Hawkes-processen om burstiness en zelf-excitatie te isoleren.
• Real-World Netwerken: Drie verschillende datasets die menselijke nabijheid (high school RFID), voertuigtrajecten (San Francisco cabs) en infrastructuur-gemedieerde connectiviteit (KTH campus Wi-Fi) vertegenwoordigen.
• Microcanonical Randomised Reference Models: Deze modellen worden gebruikt om specifieke heterogeniteiten (bijv. ruimtelijke embedding, temporale correlaties) te vernietigen terwijl grove netwerkeigenschappen (knoopin-aantal, link-aantal, totaal aantal events) behouden blijven, waardoor de bijdrage van individuele heterogeniteiten geïsoleerd kan worden.

Kernbijdragen

1. Verenigde Diffusie-Mapping: Het artikel stelt vast dat DFL-convergentie, zowel in de vroege synchronisatiefase als in de stationaire fasen, wordt beheerst door dezelfde dynamica als een lazy random-walk diffusieproces op temporale netwerken. Dit biedt een analytisch hanteerbaar kader voor het begrijpen van DFL-convergentie.
2. Kwantificering van de Impact van Heterogeniteit: De studie demonstreert dat zowel structurele (bijv. laag-dimensionale ruimtelijke embedding) als temporale (bijv. bursty inter-event tijden, zelf-excitatie) heterogeniteiten de diffusieprocedure universeel vertragen.
3. Bias in Standaard Benchmarks: De auteurs tonen aan dat standaard experimentele opstellingen (gebruikmakend van homogene random graphs met regelmatige communicatie-intervallen) systematisch bevooroordeeld zijn naar onrealistisch snelle convergentie. In real-world netwerken kan een volledig gerandomiseerde baseline met identieke knoop/link/event-aantallen tientallen tot meer dan honderd keer sneller mengen dan het empirische netwerk.

Resultaten

• Ruimtelijke Dimensionaliteit: Lagere-dimensionale ruimtelijke embedding (bijv. 2D of 3D) verhoogt de relaxatietijd aanzienlijk vergeleken met hoog-dimensionale of mean-field modellen (Erdős–Rényri). Sterker afstand-verval (lagere "temperatuur" in geometrische grafen) vertraagt de diffusie verder.
• Temporale Burstiness: Heavy-tailed inter-event tijdsverdelingen (power-law renewal processen) en zelf-exciterende processen (Hawkes processen) verminderen de mengingssnelheid drastisch. Hoe geclusterder de events (hogere burstiness of zelf-excitatie), hoe langzamer de convergentie.
• Real-World Netwerken: Analyse van de drie real-world datasets bevestigt dat de samenkomst van meerdere heterogeniteiten leidt tot significante vertragingen. Microcanonical randomisatie onthult dat specifieke kenmerken zoals ruimtelijke beperkingen en temporale correlaties primaire drijfveren zijn van deze vertraging, waarbij ze vaak veroorzaken dat het empirische netwerk orders van grootte langzamer mixt dan een gerandomiseerde tegenhanger.

Betekenis en Claims
Het artikel claimt dat netwerkheterogeniteit geen secundair modelleringsdetail is, maar een primaire determinant van de convergentiesnelheid in gedecentraliseerd federated learning. De auteurs stellen dat het negeren van temporale en structurele inhomogeniteiten leidt tot een fundamentele misinterpretatie van simulatie-gebaseerde benchmarks, wat resulteert in te optimistische verwachtingen voor de prestaties van DFL in real-world implementaties. Bij consequentie suggereren de bevindingen een behoefte aan topologie- en tijd-adaptieve communicatiebeleid en een herwaardering van huidige evaluatieprotocollen die steunen op geïdealiseerde netwerk-aannames. Het werk overbrugt de netwerkwetenschap-theorie (diffusie op temporale netwerken) met machine learning system design, en biedt een realistischer perspectief voor het voorspellen van DFL-gedrag.