Résumé Technique : Filtrations de Cycles Sans Corde pour la Détection de Dimensionnalité dans les Réseaux Complexes via l'Analyse Topologique des Données

1. Énoncé du Problème

Les réseaux complexes issus de domaines divers (biologiques, sociaux, technologiques) présentent souvent des motifs structurels cohérents avec une géométrie hyperbolique latente sous-jacente. Déterminer la dimensionnalité effective ($D$) de cet espace latent est crucial pour comprendre la complexité structurelle, l'organisation communautaire, la navigation dans le réseau et la dynamique des systèmes. Bien que diverses définitions de la dimensionnalité des réseaux existent (par exemple, fractale, spectrale, métrique) et que des approches pilotées par des modèles (telles que le modèle $S^D/H^{D+1}$) aient réussi à estimer la dimensionnalité en projetant les fréquences des cycles sur des espaces de configuration, ces méthodes nécessitent souvent la génération de grands ensembles de réseaux de substitution synthétiques pour chaque nouveau réseau cible. Ce processus est intensif en calculs et manque d'un cadre unifié, piloté par les données, qui intègre l'Analyse Topologique des Données (ATD) avec l'apprentissage automatique pour contourner la génération de substitutions.

De plus, les applications standard de l'ATD en science des réseaux ont été limitées. L'homologie persistante ordinaire est mal adaptée aux graphes car les cycles (caractéristiques de dimension 1) ont une persistance infinie en l'absence de simplexes de dimension supérieure pour les combler. En outre, les schémas de filtration existants (par exemple, basés sur le degré des nœuds ou la courbure de Ricci) peuvent ne pas capturer les signatures géométriques spécifiques requises pour l'estimation de la dimensionnalité.

2. Méthodologie

Les auteurs proposent une approche à double volet combinant la topologie algébrique et l'apprentissage automatique pour estimer la dimensionnalité des réseaux.

A. Filtrations de Cycles Sans Corde et Persistance Étendue

L'innovation topologique centrale est un schéma de pondération basé sur les cycles sans corde (cycles sans cordes internes).

1. Pondération : Pour un réseau donné, trois graphes pondérés par les arêtes sont construits. Le poids d'une arête est défini par la densité locale de cycles sans corde de longueurs spécifiques : triangles ($C_t$), carrés ($C_s$) et pentagones ($C_p$).
2. Persistance Étendue : Puisque les cycles dans les graphes ne meurent pas dans les filtrations standard, les auteurs calculent la persistance étendue. Cela implique une technique pour transformer le graphe pondéré par les arêtes en un graphe pondéré par les nœuds topologiquement équivalent via une « subdivision par séparation de degré ». Cela permet d'utiliser des logiciels standards d'ATD (Gudhi) pour calculer la persistance étendue des cycles, définie comme la différence entre la valeur de naissance dans la filtration sous-niveau et la valeur de naissance dans la filtration sur-niveau.
3. Descripteurs : La Persistance Étendue Totale (la somme des valeurs de persistance pour tous les cycles indépendants) est calculée pour chacune des trois filtrations, produisant un vecteur de caractéristiques $(TP_t, TP_s, TP_p)$.

B. Approches d'Estimation de la Dimensionnalité

L'article présente deux méthodes pour estimer $D$ :

1. Voisinage k-Plus Proche (kNN) Basé sur des Substitutions :

   • Pour un réseau cible, un ensemble de substitutions synthétiques est généré en utilisant la procédure $D$-GR (Randomisation Géométrique). Cette méthode réarrange le réseau pour maximiser la vraisemblance du modèle $S^D/H^{D+1}$ tout en préservant la séquence de degrés exacte du réseau cible.
   • Le réseau cible et ses substitutions sont mappés dans un espace de configuration défini par $(TP_t, TP_s, TP_p)$.
   • Un classifieur kNN identifie la dimension $D$ des substitutions les plus proches du réseau cible.

2. Réseau de Neurones (DimNN) :

   • Pour éviter de générer des substitutions pour chaque nouveau réseau, les auteurs entraînent un Perceptron Multicouche Résiduel (DimNN).
   • Données d'Entraînement : Une base de données de 792 000 réseaux synthétiques (SynNet) générés à partir du modèle $S^D/H^{D+1}$ avec des dimensions connues ($D \in [1, 10]$) et des paramètres variables (hétérogénéité de degré $\gamma$, température inverse $\beta$).
   • Caractéristiques d'Entrée : Le modèle utilise un vecteur de caractéristiques de 12 dimensions incluant :
     • Statistiques du graphe : Nombre de nœuds ($N$), degré moyen ($\langle k \rangle$), second moment normalisé de la distribution des degrés ($\langle k^2 \rangle / \langle k \rangle^2$), degrés min/max, et degré moyen des voisins ($\langle k_{nn} \rangle$).
     • Densités de cycles : Densités moyennes de triangles, carrés et pentagones sans corde ($C_t, C_s, C_p$).
     • Descripteurs topologiques : Persistances étendues totales ($TP_t, TP_s, TP_p$).
   • Architecture : Un MLP profond avec 21 couches cachées, des activations ReLU, un dropout (50 %) et des connexions résiduelles, entraîné avec AdamW.
   • Validation : Un modèle de régression secondaire (utilisant une perte MSE) a été entraîné pour vérifier la robustesse, montrant une forte concordance avec le modèle de classification.

3. Contributions Clés

• Schéma de Filtration Novel : Introduction d'un schéma de filtration basé sur la densité de cycles sans corde pour les graphes, spécifiquement conçu pour capturer les propriétés géométriques pertinentes pour la dimensionnalité.
• Persistance Étendue pour les Graphes : Adaptation de la persistance étendue aux graphes pondérés par les arêtes via une subdivision par séparation de degré, permettant le calcul de durées de vie de cycles finies dans des contextes de réseaux où la persistance standard échoue.
• Estimation de Dimensionnalité Pilotée par les Données : Développement de DimNN, un réseau de neurones entraîné sur une base de données synthétique massive capable d'estimer la dimensionnalité d'un réseau directement à partir d'un seul réseau réel sans générer de substitutions.
• Intégration de l'ATD et de l'AM : Démonstration que les caractéristiques de l'ATD (persistance totale) améliorent considérablement la précision des modèles d'apprentissage automatique pour l'estimation de la dimensionnalité, surpassant les modèles utilisant uniquement les densités de cycles ou les statistiques de degré.

4. Résultats

• Corrélation : Une corrélation négative a été observée entre la dimensionnalité du réseau et les valeurs de persistance étendue totale, en particulier pour les carrés et les pentagones (coefficients de Pearson $\rho_s \approx -0,31$, $\rho_p \approx -0,24$).
• Validation sur Synthétiques :
  • La méthode de substitution kNN a atteint une précision raisonnable sur des cibles synthétiques, avec des matrices de confusion montrant une haute fidélité pour la plupart des dimensions, bien que certaines confusions se soient produites entre des dimensions adjacentes dans des réseaux hautement hétérogènes.
  • DimNN a atteint une précision de classification de 83,00 % sur l'ensemble de validation en utilisant le vecteur de caractéristiques complet.
  • Des études d'ablation ont confirmé que la combinaison de la persistance totale avec les densités moyennes de cycles et les caractéristiques liées au degré maximise les performances. Le retrait des caractéristiques d'ATD a entraîné une baisse significative de la précision.
• Application au Monde Réel :
  • La méthode a été appliquée à 10 réseaux réels bien connus (par exemple, Connectome Humain, collaboration Jazz, réseaux d'e-mails). Les dimensions inférées étaient cohérentes avec la littérature précédente (par exemple, les connectomes cérébraux proches de $D=3$, les réseaux sociaux nécessitant des dimensions légèrement supérieures).
  • Lorsqu'appliquée à un ensemble de données plus large de 53 réseaux réels, le modèle a prédit des dimensions allant de 1 (Logiciels, graphes Web) à 10 (certains réseaux sociaux).
  • Robustesse : Deux modèles entraînés indépendamment (classification et régression) ont montré une forte concordance (jusqu'à 88,86 % sur des données synthétiques), suggérant que les modèles capturent des relations sous-jacentes plutôt que de surajuster.
  • Validation : Les réseaux de substitutions générés en utilisant les dimensions prédites et les plongements D-Mercator ont réussi à reproduire les propriétés topologiques clés des réseaux originaux, y compris la distribution des degrés, le spectre de regroupement et les seuils de percolation.

5. Signification et Revendications

L'article revendique que ce travail comble le fossé entre la théorie des réseaux complexes et l'Analyse Topologique des Données en fournissant une méthode robuste et efficace pour révéler la géométrie cachée des réseaux complexes.

• Efficacité : L'approche par réseau de neurones offre un avantage computationnel significatif par rapport aux méthodes précédentes basées sur des substitutions, car elle ne nécessite ni réentraînement ni génération de substitutions pour de nouveaux réseaux.
• Expressivité : L'étude démontre que les filtrations conscientes des cycles et les descripteurs de persistance étendue sont des caractéristiques hautement expressives pour la détection de dimensionnalité, complétant les descripteurs géométriques traditionnels.
• Généralisation : Le modèle transfère avec succès des données d'entraînement synthétiques vers des réseaux réels, suggérant que les structures géométriques latentes des réseaux réels sont bien représentées par le modèle $S^D/H^{D+1}$ dans les régimes de paramètres testés.

Les auteurs notent modestement que le cadre cible principalement les réseaux géométriques ($\beta > D$) et que l'extension de l'approche aux régimes faiblement géométriques ou l'optimisation de l'architecture neuronale pour des décalages de distribution plus larges restent une direction pour un travail futur. L'article se positionne comme une preuve de concept de l'utilité des filtrations basées sur les cycles en ATD et de la faisabilité de l'estimation de dimensionnalité assistée par l'apprentissage profond.