Apprentissage de la Structure des Graphes de Connexion

Informations de Base

• ID de l'article: 2510.11245
• Titre: Learning the Structure of Connection Graphs
• Auteurs: Leonardo Di Nino, Gabriele D'Acunto, Sergio Barbarossa, Paolo Di Lorenzo (Université Sapienza de Rome & CNIT)
• Classification: cs.LG (Apprentissage Automatique), eess.SP (Traitement du Signal)
• Date de soumission: 13 octobre 2025 sur arXiv
• Lien de l'article: https://arxiv.org/abs/2510.11245v1

Résumé

Les graphes de connexion (Connection Graphs, CGs) étendent les modèles graphiques traditionnels en couplant la topologie du réseau avec des transformations orthogonales, permettant de représenter la cohérence géométrique globale. Ils jouent un rôle crucial dans les applications de synchronisation, de traitement du signal riemannien et de diffusion de faisceaux neuronaux. Cette recherche aborde le problème inverse d'apprentissage des graphes de connexion directement à partir de signaux observés. Les auteurs proposent un cadre théorique basé sur la vraisemblance pseudo-maximale sous hypothèse de cohérence, qui impose une relation spectrale entre le laplacien de connexion et le laplacien combinatoire sous-jacent. Sur cette base, un algorithme d'apprentissage structuré des graphes de connexion (SCGL) est introduit, qui est un processus d'optimisation par blocs sur une variété riemannienne capable d'inférer conjointement la topologie du réseau, les poids des arêtes et la structure géométrique.

Contexte et Motivation de la Recherche

Définition du Problème

Le problème fondamental abordé par cette recherche est l'apprentissage de la structure des graphes de connexion à partir de signaux observés, un problème inverse. Il comprend spécifiquement:

1. Comment inférer simultanément la structure de topologie du réseau à partir de données de signaux vectoriels
2. Comment apprendre les matrices de transformations orthogonales sur les arêtes
3. Comment garantir que le graphe de connexion appris satisfait la cohérence géométrique

Importance du Problème

Le traitement classique des signaux sur graphes (GSP) ne peut capturer que les interactions locales et appariées entre nœuds, limitant la capacité de modélisation de la cohérence globale du réseau. Les graphes de connexion, en introduisant des transformations orthogonales, permettent de:

• Représenter des configurations de synchronisation plus riches que les graphes traditionnels
• Modéliser la cohérence géométrique globale
• Supporter des applications avancées comme le traitement du signal riemannien et la diffusion de faisceaux

Limitations des Méthodes Existantes

1. Vector Diffusion Maps (VDM): Utilise des principes géométriques pour approximer le laplacien du graphe de connexion, mais c'est une méthode directe inadaptée aux problèmes inverses
2. Méthodes SDP: Utilise la programmation semi-définie pour étendre l'apprentissage du laplacien de faisceau, mais ne peut pas récupérer correctement les propriétés géométriques non-euclidiennes du graphe de connexion
3. Apprentissage graphique traditionnel: Se concentre uniquement sur la topologie et la lissité des signaux, incapable de traiter la structure géométrique

Motivation de la Recherche

Les méthodes existantes ne peuvent pas traiter efficacement les défis clés de l'apprentissage des graphes de connexion:

• Les contraintes géométriques non-euclidiennes de la variété orthogonale
• L'optimisation conjointe de la topologie et de la structure géométrique
• L'application des conditions de cohérence

Contributions Principales

1. Cadre Théorique: Propose une formulation du problème de vraisemblance pseudo-maximale basée sur l'hypothèse de cohérence, étendant le contrôle spectral des graphes traditionnels aux graphes de connexion
2. Innovation Algorithmique: Développe l'algorithme SCGL, utilisant l'optimisation par descente par blocs sur une variété riemannienne pour récupérer conjointement la topologie et les motifs géométriques
3. Validation Expérimentale: Démontre dans des expériences synthétiques sur des graphes aléatoires et géométriques les améliorations significatives de SCGL par rapport aux méthodes de base existantes pour l'apprentissage des graphes de connexion
4. Efficacité Computationnelle: Réalise une paramétrisation plus efficace que les méthodes de programmation conique, réduisant la complexité spatiale de O(V²n²) à O(Vn²)

Détails de la Méthode

Définition de la Tâche

Entrée: Ensemble de signaux observés X = {x₁, ..., xₘ}, où chaque signal xᵢ ∈ ℝⁿᵛ est composé de mesures locales de nœuds xᵥ ∈ ℝⁿ empilées Sortie: Opérateur laplacien de connexion L, comprenant:

• L'opérateur laplacien combinatoire du graphe sous-jacent L
• Les poids des arêtes w
• Les bases orthogonales des nœuds O = blkdiag({Oᵥ}ᵥ∈V)

Fondements Théoriques

Définition des Graphes de Connexion

Un graphe de connexion G = ⟨G,ℝⁿ,w,O(n)⟩ est composé des éléments suivants:

• Graphe sous-jacent G := (V,E)
• Espace vectoriel euclidien n-dimensionnel ℝⁿ sur chaque nœud v ∈ V
• Poids non-négatifs wₑ et matrices orthogonales Oₑ ∈ O(n) sur chaque arête e ∈ E

Conditions de Cohérence

Le Théorème 1 établit que la cohérence du graphe de connexion est équivalente aux conditions suivantes:

1. La composition des applications orthogonales le long de chaque cycle du graphe est l'application identité
2. Les valeurs propres du laplacien de connexion sont des répétitions n-fois des valeurs propres du laplacien combinatoire
3. Il existe des matrices orthogonales de nœuds telles que les applications d'arêtes se décomposent comme Oᵢⱼ = Oᵢᵀ Oⱼ

Formulation du Problème d'Optimisation

Problème de Vraisemblance Pseudo-Maximale

En supposant que les signaux suivent une distribution gaussienne N_nv(0,L†), le problème original est:

min_{L∈CL} -log gdet(L) + Tr(SL)     (P1)

Reformulation sous Contraintes de Cohérence

En utilisant la condition de cohérence L = Oᵀ(L⊗Iₙ)O, le problème se transforme en:

min_{L∈GL, O∈O} -log gdet{Oᵀ(L⊗Iₙ)O} + Tr{SOᵀ(L⊗Iₙ)O}     (P2)

Problème d'Optimisation Final

En introduisant l'opérateur laplacien de Kronecker structuré et la relaxation lagrangienne:

min_{O,w,U,Λ} -n log gdet(Λ) + Tr{SOᵀL_K(w)O} + αΨ(w)
             + β/2 ||OᵀL_K(w)O - U(Λ⊗Iₙ)Uᵀ||²_F     (P3)

Algorithme SCGL

Optimisation par Descente de Coordonnées par Blocs

SCGL adopte une stratégie de minimisation alternée par blocs, optimisant séparément quatre blocs de variables:

1. Mise à jour des Poids des Arêtes (w):

   w^{t+1} = P^+_{α/β Ψ}{w^t - 1/τ L*_K[f(w^t)]}
   

   
   Utilisant la méthode Minorization-Maximization (MM)
2. Mise à jour des Bases Orthogonales (O): Utilisant la descente de gradient riemannien sur la variété produit SO(n)^v
3. Mise à jour des Vecteurs Propres (U): Par calcul des vecteurs propres principaux:

   U^{t+1} = [Eigenvecs{OᵀL_K(w)O}]_{:,(n+1):}
   

4. Mise à jour des Valeurs Propres (Λ): Problème de régression isotonique avec solution KKT en forme fermée

Complexité Computationnelle

La complexité de l'algorithme est O(V³n³), principalement déterminée par la décomposition en valeurs propres dans les étapes d'optimisation des bases orthogonales et des vecteurs propres, augmentant seulement du facteur d'échelle de dimension n par rapport à l'apprentissage structuré des graphes.

Configuration Expérimentale

Ensembles de Données

1. Graphes de Connexion Erdős–Rényi (ER):
   • Nombre de nœuds: |V| = 30
   • Probabilité d'arête: p_ER = 1.1 log V / V
   • Dimension de l'espace vectoriel: n = 2
   • Poids des arêtes: Unif(0.2, 3)
2. Graphes de Connexion Géométriques Sphériques:
   • Sphère dans ℝ³, discrétisée avec la grille de Fibonacci
   • 50 points, graphe k-NN avec k=4
   • Utilisant Vector Diffusion Maps pour construire l'opérateur laplacien de connexion

Métriques d'Évaluation

1. Récupération de Topologie: Score F1 (récupération de motif creux), MSE des poids des arêtes
2. Fidélité Géométrique:
   • Variation totale empirique ÊL(Y) = M⁻¹ Tr(L̂YYᵀ)
   • Distance spectrale moyenne σ(L,L̂) = 1/(nv) Σᵢ|Λᵢ(L)-Λᵢ(L̂)|
   • Distance de diffusion thermique intégrée ξ(L,L̂)

Méthodes de Comparaison

1. KRON: Version simplifiée de SCGL avec bases locales fixées à la matrice identité
2. SDP: Méthode d'apprentissage lissé basée sur la programmation semi-définie
3. SLGP: Travail antérieur des auteurs, apprentissage lissé avec prior géométrique

Scénarios de Disponibilité des Données

Selon le ratio d'échantillonnage r = M/(2|V|), trois scénarios sont définis:

• Faible: r = 1.5
• Moyen: r = 5
• Élevé: r = 15

Résultats Expérimentaux

Résultats sur Graphes de Connexion ER

• Récupération de Topologie: Avec l'augmentation des données, SCGL surpasse significativement toutes les méthodes de base en score F1
• Fidélité Géométrique: SCGL est le plus proche de la valeur théorique attendue en variation totale empirique, indiquant une meilleure cohérence
• Estimation des Poids des Arêtes: SCGL estime précisément les poids des arêtes, la plupart des faux positifs se voyant attribuer des poids négligeables

Résultats sur Graphes de Connexion Sphériques

• Score F1: SCGL = 0.995 (maximum), SLGP = 0.927, SDP = 0.620, KRON = 0.425
• Distance Spectrale: SCGL = 0.90 (minimum), surpassant significativement les autres méthodes
• Distance de Diffusion Thermique: SCGL = 1.19 (minimum)
• Dimension du Noyau: SCGL maintient correctement dim(ker(L)) = 2, garantissant la cohérence

Découvertes Clés

1. SCGL fonctionne au mieux avec des données suffisantes, avec des performances comparables à SLGP en cas de données rares
2. L'optimisation des bases orthogonales des nœuds apporte des améliorations significatives par rapport à la fixation de la matrice identité
3. SCGL réalise simultanément la meilleure récupération de topologie et fidélité géométrique
4. L'algorithme préserve la cohérence du graphe de connexion, qui est clé pour la signification géométrique

Travaux Connexes

Domaine de l'Apprentissage Graphique

L'apprentissage graphique traditionnel poursuit principalement deux objectifs:

1. Imposer une topologie souhaitée (équilibrer la parcimonie et la connectivité)
2. Promouvoir la lissité des signaux (variation faible entre nœuds connectés)

Approches de Théorie des Faisceaux

• Faisceaux Réseau: Associent des données structurées sur les nœuds et arêtes via des applications préservant la structure
• Graphes de Connexion: Cas particulier de la théorie des faisceaux, utilisant des transformations orthogonales comme applications préservant la structure
• Applications: Problèmes de synchronisation, traitement du signal riemannien, diffusion de faisceaux neuronaux

Méthodes Existantes d'Apprentissage des Graphes de Connexion

1. Vector Diffusion Maps: Approxime le laplacien du graphe de connexion via des principes géométriques
2. Méthodes SDP: Étend l'apprentissage lissé des graphes au laplacien de faisceau
3. Méthodes de Programmation Conique: Utilise l'alignement de Procrustes et l'échantillonnage binaire des arêtes

Conclusion et Discussion

Conclusions Principales

1. Propose le premier cadre théorique pour l'apprentissage des graphes de connexion basé sur l'hypothèse de cohérence
2. L'algorithme SCGL peut récupérer conjointement la topologie du réseau, les poids des arêtes et la structure géométrique
3. Les expériences démontrent que SCGL surpasse les méthodes existantes tant en récupération de topologie qu'en fidélité géométrique
4. L'algorithme réalise une meilleure paramétrisation tout en maintenant l'efficacité computationnelle

Limitations

1. Hypothèse de Cohérence: La méthode suppose que le graphe de connexion est cohérent, ce qui peut ne pas toujours être vrai en pratique
2. Hypothèse de Distribution Gaussienne: Le modèle de signal peut être trop simplifié
3. Données Synthétiques: Les expériences sont principalement menées sur des données synthétiques, manquant de validation sur des données réelles
4. Robustesse au Bruit: L'évaluation de la performance en présence de bruit et de violation de modèle est insuffisante

Directions Futures

1. Étendre SCGL pour traiter le bruit et la violation de modèle
2. Incorporer des priors flexibles sur la topologie et la géométrie
3. Traiter les graphes de connexion non-cohérents
4. Valider le cadre sur des données réelles

Évaluation Approfondie

Points Forts

1. Contribution Théorique: Étend l'apprentissage structuré des graphes aux graphes de connexion, fournissant une base théorique solide
2. Innovation Algorithmique: Combine intelligemment l'optimisation riemannienne et la descente par blocs de coordonnées, traitant les contraintes complexes de variété
3. Expériences Complètes: Évaluation complète sur différents types de graphes de connexion
4. Efficacité Computationnelle: Réalise une paramétrisation plus efficace que les méthodes existantes

Insuffisances

1. Limitations d'Applicabilité: L'hypothèse de cohérence peut limiter la portée des applications pratiques
2. Limitations Expérimentales: Manque de validation sur des ensembles de données réelles
3. Analyse du Bruit: L'analyse de la robustesse au bruit n'est pas suffisamment approfondie
4. Limitations d'Échelle: L'échelle expérimentale est relativement petite (maximum 50 nœuds)

Impact

1. Valeur Académique: Fournit de nouveaux outils pour l'inférence de topologie de réseau sensible à la géométrie
2. Potentiel d'Application: Perspectives d'application importantes dans les domaines de la synchronisation et du traitement du signal riemannien
3. Contribution Méthodologique: Fournit un nouveau paradigme d'optimisation pour l'apprentissage des faisceaux

Scénarios d'Application

1. Réseaux de Synchronisation: Problèmes de synchronisation nécessitant d'apprendre les relations de rotation entre nœuds
2. Traitement du Signal Riemannien: Tâches de traitement de signaux sur des variétés
3. Réseaux de Neurones: Apprentissage de structure pour les réseaux de neurones de faisceaux
4. Robotique: Coordination et localisation dans les systèmes multi-robots

Références

L'article cite 29 références pertinentes, couvrant des domaines importants tels que le traitement des signaux sur graphes, la théorie des faisceaux et l'optimisation riemannienne, fournissant une base théorique solide pour la recherche.

Évaluation Globale: Ceci est un article de haute qualité avec des contributions importantes dans le domaine de l'apprentissage des graphes de connexion. L'algorithme SCGL proposé par les auteurs est novateur sur le plan théorique et les résultats expérimentaux sont convaincants. Malgré certaines limitations, il ouvre une nouvelle direction de recherche pour l'apprentissage de graphes sensible à la géométrie, possédant une valeur académique importante et un potentiel d'application considérable.