2025-11-23T19:40:17.292793

Learning the Structure of Connection Graphs

Di Nino, D'Acunto, Barbarossa et al.
Connection graphs (CGs) extend traditional graph models by coupling network topology with orthogonal transformations, enabling the representation of global geometric consistency. They play a key role in applications such as synchronization, Riemannian signal processing, and neural sheaf diffusion. In this work, we address the inverse problem of learning CGs directly from observed signals. We propose a principled framework based on maximum pseudo-likelihood under a consistency assumption, which enforces spectral properties linking the connection Laplacian to the underlying combinatorial Laplacian. Based on this formulation, we introduce the Structured Connection Graph Learning (SCGL) algorithm, a block-optimization procedure over Riemannian manifolds that jointly infers network topology, edge weights, and geometric structure. Our experiments show that SCGL consistently outperforms existing baselines in both topological recovery and geometric fidelity, while remaining computationally efficient.
academic

Imparare la Struttura dei Grafi di Connessione

Informazioni Fondamentali

  • ID Articolo: 2510.11245
  • Titolo: Learning the Structure of Connection Graphs
  • Autori: Leonardo Di Nino, Gabriele D'Acunto, Sergio Barbarossa, Paolo Di Lorenzo (Università Sapienza di Roma & CNIT)
  • Classificazione: cs.LG (Machine Learning), eess.SP (Signal Processing)
  • Data di Pubblicazione: Sottomesso ad arXiv il 13 ottobre 2025
  • Link Articolo: https://arxiv.org/abs/2510.11245v1

Riassunto

I grafi di connessione (Connection Graphs, CGs) estendono i modelli grafici tradizionali accoppiando la topologia di rete con trasformazioni ortogonali, consentendo di rappresentare la coerenza geometrica globale. Svolgono un ruolo cruciale in applicazioni quali sincronizzazione, elaborazione di segnali riemanniani e diffusione di fasci neurali. Questo studio affronta il problema inverso di imparare i grafi di connessione direttamente dai segnali osservati. Gli autori propongono un framework principiato basato sulla massima pseudo-verosimiglianza sotto ipotesi di coerenza, che impone un collegamento tra le proprietà spettrali dell'operatore laplaciano di connessione e l'operatore laplaciano combinatorio sottostante. Sulla base di questa formulazione, viene introdotto l'algoritmo SCGL (Structured Connection Graph Learning), un processo di ottimizzazione a blocchi su varietà riemanniane che consente l'inferenza congiunta della topologia di rete, dei pesi degli archi e della struttura geometrica.

Contesto di Ricerca e Motivazione

Definizione del Problema

Il problema centrale affrontato da questo studio è il problema inverso di imparare la struttura dei grafi di connessione dai segnali osservati. Nello specifico include:

  1. Come inferire simultaneamente la struttura topologica della rete dai dati di segnali vettoriali
  2. Come imparare le matrici di trasformazione ortogonale sugli archi
  3. Come garantire che il grafo di connessione appreso soddisfi la coerenza geometrica

Importanza del Problema

L'elaborazione tradizionale di segnali su grafi (GSP) può catturare solo interazioni locali e pairwise tra nodi, limitando la capacità di modellare la coerenza globale della rete. I grafi di connessione, introducendo trasformazioni ortogonali, consentono di:

  • Rappresentare configurazioni di sincronizzazione più ricche rispetto ai grafi tradizionali
  • Modellare la coerenza geometrica globale
  • Supportare applicazioni avanzate come l'elaborazione di segnali riemanniani e la diffusione di fasci neurali

Limitazioni dei Metodi Esistenti

  1. Vector Diffusion Maps (VDM): Utilizza principi geometrici per approssimare l'operatore laplaciano del grafo di connessione, ma è un metodo forward non adatto ai problemi inversi
  2. Metodi SDP: Utilizza programmazione semidefinita per estendere l'apprendimento del laplaciano di fasci, ma non riesce a recuperare correttamente le proprietà geometriche non euclidee del grafo di connessione
  3. Apprendimento Grafico Tradizionale: Si concentra solo sulla topologia e sulla levigatezza dei segnali, non può gestire la struttura geometrica

Motivazione della Ricerca

I metodi esistenti non riescono ad affrontare efficacemente le sfide chiave nell'apprendimento dei grafi di connessione:

  • Vincoli geometrici non euclidei della varietà ortogonale
  • Ottimizzazione congiunta della topologia e della struttura geometrica
  • Applicazione delle condizioni di coerenza

Contributi Principali

  1. Framework Teorico: Propone una formulazione del problema di massima pseudo-verosimiglianza basata su ipotesi di coerenza, estendendo il controllo spettrale dai grafi tradizionali ai grafi di connessione
  2. Innovazione Algoritmica: Sviluppa l'algoritmo SCGL, che utilizza l'ottimizzazione a discesa a blocchi su varietà riemanniane per recuperare congiuntamente la topologia e i pattern geometrici
  3. Verifica Sperimentale: Dimostra il significativo miglioramento di SCGL rispetto ai baseline esistenti nell'apprendimento dei grafi di connessione attraverso esperimenti sintetici su grafi casuali e grafi geometrici
  4. Efficienza Computazionale: Implementa una parametrizzazione più efficiente rispetto ai metodi di programmazione conica, riducendo la complessità spaziale da O(V²n²) a O(Vn²)

Spiegazione Dettagliata del Metodo

Definizione del Compito

Input: Insieme di segnali osservati X = {x₁, ..., xₘ}, dove ogni segnale xᵢ ∈ ℝⁿᵛ è composto da misurazioni locali dei nodi xᵥ ∈ ℝⁿ impilate Output: Operatore laplaciano di connessione L, che include:

  • Operatore laplaciano combinatorio del grafo sottostante L
  • Pesi degli archi w
  • Basi ortogonali dei nodi O = blkdiag({Oᵥ}ᵥ∈V)

Fondamenti Teorici

Definizione del Grafo di Connessione

Un grafo di connessione G = ⟨G,ℝⁿ,w,O(n)⟩ è costituito dai seguenti componenti:

  • Grafo sottostante G := (V,E)
  • Spazio vettoriale euclideo n-dimensionale ℝⁿ su ogni nodo v ∈ V
  • Peso non negativo wₑ e matrice ortogonale Oₑ ∈ O(n) su ogni arco e ∈ E

Condizioni di Coerenza

Il Teorema 1 mostra che la coerenza del grafo di connessione è equivalente alle seguenti condizioni:

  1. Le mappature ortogonali composte lungo ogni ciclo del grafo risultano nella mappatura identità
  2. Gli autovalori dell'operatore laplaciano di connessione sono n-fold ripetizioni degli autovalori dell'operatore laplaciano combinatorio
  3. Esistono matrici ortogonali dei nodi tali che le mappature degli archi possono essere decomposte come Oᵢⱼ = Oᵢᵀ Oⱼ

Formulazione del Problema di Ottimizzazione

Problema di Massima Pseudo-Verosimiglianza

Assumendo che i segnali seguano una distribuzione gaussiana N_nv(0,L†), il problema originale è:

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

Riformulazione con Vincoli di Coerenza

Utilizzando la condizione di coerenza L = Oᵀ(L⊗Iₙ)O, il problema si trasforma in:

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

Problema di Ottimizzazione Finale

Introducendo l'operatore laplaciano di struttura Kronecker e il rilassamento lagrangiano:

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)

Algoritmo SCGL

Ottimizzazione a Discesa a Blocchi Coordinati

SCGL adotta una strategia di minimizzazione a blocchi alternati, ottimizzando separatamente quattro blocchi di variabili:

  1. Aggiornamento dei Pesi degli Archi (w):
    w^{t+1} = P^+_{α/β Ψ}{w^t - 1/τ L*_K[f(w^t)]}

    Utilizza il metodo Minorization-Maximization (MM)
  2. Aggiornamento delle Basi Ortogonali (O): Utilizza la discesa del gradiente riemanniano sulla varietà prodotto SO(n)^v
  3. Aggiornamento dei Vettori Propri (U): Calcolato attraverso i vettori propri principali:
    U^{t+1} = [Eigenvecs{OᵀL_K(w)O}]_{:,(n+1):}
  4. Aggiornamento degli Autovalori (Λ): Problema di regressione isotonica con soluzione KKT in forma chiusa

Complessità Computazionale

La complessità dell'algoritmo è O(V³n³), determinata principalmente dalla decomposizione spettrale nei passaggi di ottimizzazione delle basi ortogonali e dei vettori propri, aumentando rispetto all'apprendimento di grafi strutturati solo per il fattore di scala della dimensione n.

Configurazione Sperimentale

Dataset

  1. Grafi di Connessione Erdős–Rényi (ER):
    • Numero di nodi: |V| = 30
    • Probabilità di arco: p_ER = 1.1 log V / V
    • Dimensione dello spazio vettoriale: n = 2
    • Pesi degli archi: Unif(0.2, 3)
  2. Grafi di Connessione Geometrici Sferici:
    • Sfera in ℝ³, discretizzata utilizzando il reticolo di Fibonacci
    • 50 punti, grafo k-NN con k=4
    • Operatore laplaciano di connessione costruito utilizzando Vector Diffusion Maps

Metriche di Valutazione

  1. Recupero della Topologia: Punteggio F1 (recupero di pattern sparsi), MSE dei pesi degli archi
  2. Fedeltà Geometrica:
    • Variazione totale empirica ÊL(Y) = M⁻¹ Tr(L̂YYᵀ)
    • Distanza spettrale media σ(L,L̂) = 1/(nv) Σᵢ|Λᵢ(L)-Λᵢ(L̂)|
    • Distanza di diffusione del calore integrata ξ(L,L̂)

Metodi di Confronto

  1. KRON: Versione semplificata di SCGL con basi locali fissate a matrici identità
  2. SDP: Metodo di apprendimento liscio basato su programmazione semidefinita
  3. SLGP: Lavoro precedente degli autori, apprendimento liscio con priori geometrici

Scenari di Disponibilità dei Dati

Definiti secondo il rapporto di campionamento r = M/(2|V|):

  • Basso: r = 1.5
  • Medio: r = 5
  • Alto: r = 15

Risultati Sperimentali

Risultati su Grafi di Connessione ER

  • Recupero della Topologia: Con l'aumento dei dati, SCGL mostra un significativo vantaggio rispetto a tutti i metodi baseline nel punteggio F1
  • Fedeltà Geometrica: SCGL è più vicino al valore di aspettativa teorica nella variazione totale empirica, indicando una migliore coerenza
  • Stima dei Pesi degli Archi: SCGL stima accuratamente i pesi degli archi, con la maggior parte dei falsi positivi assegnati a pesi trascurabili

Risultati su Grafi di Connessione Sferici

  • Punteggio F1: SCGL = 0.995 (massimo), SLGP = 0.927, SDP = 0.620, KRON = 0.425
  • Distanza Spettrale: SCGL = 0.90 (minimo), significativamente superiore agli altri metodi
  • Distanza di Diffusione del Calore: SCGL = 1.19 (minimo)
  • Dimensione del Nucleo: SCGL mantiene correttamente dim(ker(L)) = 2, garantendo la coerenza

Scoperte Chiave

  1. SCGL mostra le migliori prestazioni quando i dati sono sufficienti, con prestazioni comparabili a SLGP quando i dati sono scarsi
  2. L'ottimizzazione delle basi ortogonali dei nodi porta a miglioramenti significativi rispetto alla fissazione della matrice identità
  3. SCGL raggiunge contemporaneamente il miglior recupero della topologia e la fedeltà geometrica
  4. L'algoritmo mantiene la coerenza del grafo di connessione, che è cruciale per il significato geometrico

Lavori Correlati

Campo dell'Apprendimento Grafico

L'apprendimento grafico tradizionale persegue principalmente due obiettivi:

  1. Applicare la topologia desiderata (bilanciando sparsità e connettività)
  2. Promuovere la levigatezza dei segnali (variazione bassa tra nodi connessi)

Metodi della Teoria dei Fasci

  • Fasci di Rete: Associano dati strutturati su nodi e archi attraverso mappature che preservano la struttura
  • Grafi di Connessione: Caso speciale della teoria dei fasci, utilizzando trasformazioni ortogonali come mappature che preservano la struttura
  • Applicazioni: Problemi di sincronizzazione, elaborazione di segnali riemanniani, diffusione di fasci neurali

Metodi Esistenti di Apprendimento dei Grafi di Connessione

  1. Vector Diffusion Maps: Approssima l'operatore laplaciano del grafo di connessione attraverso principi geometrici
  2. Metodi SDP: Estendono l'apprendimento grafico liscio al laplaciano di fasci
  3. Metodi di Programmazione Conica: Utilizzano allineamento di Procrustes e campionamento binario degli archi

Conclusioni e Discussione

Conclusioni Principali

  1. Propone il primo framework principiato per l'apprendimento dei grafi di connessione basato su ipotesi di coerenza
  2. L'algoritmo SCGL può recuperare congiuntamente la topologia di rete, i pesi degli archi e la struttura geometrica
  3. Gli esperimenti dimostrano che SCGL supera i metodi esistenti sia nel recupero della topologia che nella fedeltà geometrica
  4. L'algoritmo raggiunge una migliore parametrizzazione mantenendo l'efficienza computazionale

Limitazioni

  1. Ipotesi di Coerenza: Il metodo assume che il grafo di connessione sia coerente, il che potrebbe non essere sempre vero nella realtà
  2. Ipotesi di Distribuzione Gaussiana: Il modello di segnale potrebbe essere eccessivamente semplificato
  3. Dati Sintetici: Gli esperimenti sono principalmente condotti su dati sintetici, mancando di validazione su dati del mondo reale
  4. Robustezza al Rumore: La valutazione della robustezza al rumore e alle violazioni del modello non è sufficientemente approfondita

Direzioni Future

  1. Estendere SCGL per gestire il rumore e le violazioni del modello
  2. Incorporare priori flessibili sulla topologia e sulla geometria
  3. Affrontare grafi di connessione non coerenti
  4. Validare il framework su dati del mondo reale

Valutazione Approfondita

Punti di Forza

  1. Contributo Teorico: Estende l'apprendimento grafico strutturato ai grafi di connessione, fornendo una base teorica solida
  2. Innovazione Algoritmica: Combina abilmente l'ottimizzazione riemanniana e la discesa a blocchi coordinati, affrontando vincoli complessi su varietà
  3. Esperimenti Completi: Conduce una valutazione completa su diversi tipi di grafi di connessione
  4. Efficienza Computazionale: Realizza una parametrizzazione più efficiente rispetto ai metodi esistenti

Carenze

  1. Limitazioni di Applicabilità: L'ipotesi di coerenza potrebbe limitare l'intervallo di applicazioni pratiche del metodo
  2. Limitazioni Sperimentali: Manca la validazione su dataset del mondo reale
  3. Analisi del Rumore: L'analisi della robustezza al rumore non è sufficientemente approfondita
  4. Limitazioni di Scala: La scala sperimentale è relativamente piccola (massimo 50 nodi)

Impatto

  1. Valore Accademico: Fornisce nuovi strumenti per l'inferenza della topologia di rete consapevole della geometria
  2. Potenziale Applicativo: Ha importanti prospettive di applicazione in sincronizzazione, elaborazione di segnali riemanniani e altri campi
  3. Contributo Metodologico: Fornisce un nuovo paradigma di ottimizzazione per l'apprendimento di fasci

Scenari Applicabili

  1. Reti di Sincronizzazione: Problemi di sincronizzazione che richiedono l'apprendimento delle relazioni di rotazione tra nodi
  2. Elaborazione di Segnali Riemanniani: Compiti di elaborazione di segnali su varietà
  3. Reti Neurali: Apprendimento della struttura di reti neurali su fasci
  4. Robotica: Coordinamento e localizzazione in sistemi multi-robot

Riferimenti Bibliografici

L'articolo cita 29 riferimenti correlati, coprendo importanti lavori in più campi quali elaborazione di segnali su grafi, teoria dei fasci e ottimizzazione riemanniana, fornendo una base teorica solida per la ricerca.

Valutazione Complessiva: Questo è un articolo di alta qualità con importanti contributi nel campo dell'apprendimento dei grafi di connessione. L'algoritmo SCGL proposto dagli autori è innovativo dal punto di vista teorico e i risultati sperimentali sono convincenti. Nonostante alcune limitazioni, apre nuove direzioni di ricerca nell'apprendimento grafico consapevole della geometria, possedendo importante valore accademico e potenziale applicativo.