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

Erlernen der Struktur von Verbindungsgraphen

Grundinformationen

  • Paper-ID: 2510.11245
  • Titel: Learning the Structure of Connection Graphs
  • Autoren: Leonardo Di Nino, Gabriele D'Acunto, Sergio Barbarossa, Paolo Di Lorenzo (Sapienza-Universität Rom & CNIT)
  • Klassifizierung: cs.LG (Maschinelles Lernen), eess.SP (Signalverarbeitung)
  • Einreichungsdatum: 13. Oktober 2025 bei arXiv eingereicht
  • Paper-Link: https://arxiv.org/abs/2510.11245v1

Zusammenfassung

Verbindungsgraphen (Connection Graphs, CGs) erweitern traditionelle Graphmodelle durch die Kopplung von Netzwerktopologie mit orthogonalen Transformationen und ermöglichen die Darstellung globaler geometrischer Konsistenz. Sie spielen eine Schlüsselrolle in Anwendungen wie Synchronisation, Riemannscher Signalverarbeitung und neuronaler Bündeldiffusion. Diese Forschung behandelt das inverse Problem des direkten Erlernens von Verbindungsgraphen aus beobachteten Signalen. Die Autoren schlagen einen prinzipiellen Rahmen basierend auf maximaler Pseudowahrscheinlichkeit unter Konsistenzannahmen vor, der spektrale Eigenschaften zwischen dem Verbindungs-Laplace-Operator und dem zugrunde liegenden kombinatorischen Laplace-Operator erzwingt. Basierend auf dieser Formulierung wird der Algorithmus für strukturiertes Verbindungsgraphen-Lernen (SCGL) eingeführt, ein Blockoptimierungsprozess auf Riemannschen Mannigfaltigkeiten, der gemeinsam Netzwerktopologie, Kantengewichte und geometrische Struktur inferiert.

Forschungshintergrund und Motivation

Problemdefinition

Das Kernproblem dieser Forschung ist das inverse Problem des Erlernens von Verbindungsgraphstrukturen aus beobachteten Signalen. Dies umfasst konkret:

  1. Wie man gleichzeitig Netzwerktopologiestruktur aus vektorwertigen Signaldaten inferiert
  2. Wie man orthogonale Transformationsmatrizen auf Kanten erlernt
  3. Wie man sicherstellt, dass der erlernte Verbindungsgraph geometrische Konsistenz erfüllt

Bedeutung des Problems

Traditionelle Graphsignalverarbeitung (GSP) kann nur lokale, paarweise Wechselwirkungen zwischen Knoten erfassen und begrenzt die Modellierungsfähigkeit für globale Netzwerkkonsistenz. Verbindungsgraphen können durch die Einführung orthogonaler Transformationen:

  • Reichhaltigere Synchronisationskonfigurationen als traditionelle Graphen darstellen
  • Globale geometrische Konsistenz modellieren
  • Fortgeschrittene Anwendungen wie Riemannsche Signalverarbeitung und neuronale Bündeldiffusion unterstützen

Einschränkungen bestehender Methoden

  1. Vector Diffusion Maps (VDM): Verwendet geometrische Prinzipien zur Approximation des Verbindungs-Laplace-Operators, ist aber eine Vorwärtsmethode und nicht für inverse Probleme geeignet
  2. SDP-Methoden: Verwendet semidefinite Programmierung zur Erweiterung des Bündel-Laplace-Operator-Lernens, kann aber die nicht-euklidischen geometrischen Eigenschaften von Verbindungsgraphen nicht korrekt wiederherstellen
  3. Traditionelles Graphenlernens: Konzentriert sich nur auf Topologie und Signalglätte, kann geometrische Struktur nicht verarbeiten

Forschungsmotivation

Bestehende Methoden können die Schlüsselherausforderungen beim Lernen von Verbindungsgraphen nicht wirksam bewältigen:

  • Nicht-euklidische geometrische Beschränkungen von orthogonalen Mannigfaltigkeiten
  • Gemeinsame Optimierung von Topologie und geometrischer Struktur
  • Durchsetzung von Konsistenzbedingungen

Kernbeiträge

  1. Theoretischer Rahmen: Schlägt eine Formulierung des maximalen Pseudowahrscheinlichkeitsproblems unter Konsistenzannahmen vor und erweitert spektrale Kontrolle von traditionellen Graphen auf Verbindungsgraphen
  2. Algorithmische Innovation: Entwickelt den SCGL-Algorithmus, der Blockabstieg-Optimierung auf Riemannschen Mannigfaltigkeiten nutzt, um Topologie und geometrische Muster gemeinsam wiederherzustellen
  3. Experimentelle Validierung: Demonstriert in synthetischen Experimenten mit zufälligen und geometrischen Graphen signifikante Verbesserungen von SCGL gegenüber bestehenden Baselines beim Verbindungsgraphen-Lernen
  4. Rechnerische Effizienz: Implementiert eine effizientere Parametrisierung als Kegelprogrammierungsmethoden und reduziert räumliche Komplexität von O(V²n²) auf O(Vn²)

Methodische Details

Aufgabendefinition

Eingabe: Beobachtete Signalsammlung X = {x₁, ..., xₘ}, wobei jedes Signal xᵢ ∈ ℝⁿᵛ aus lokalen Knotenmessungen xᵥ ∈ ℝⁿ gestapelt ist Ausgabe: Verbindungs-Laplace-Operator L, einschließlich:

  • Kombinatorischer Laplace-Operator des zugrunde liegenden Graphen L
  • Kantengewichte w
  • Knotenbasis-Orthogonale O = blkdiag({Oᵥ}ᵥ∈V)

Theoretische Grundlagen

Definition von Verbindungsgraphen

Ein Verbindungsgraph G = ⟨G,ℝⁿ,w,O(n)⟩ besteht aus folgenden Komponenten:

  • Zugrunde liegender Graph G := (V,E)
  • n-dimensionaler euklidischer Vektorraum ℝⁿ auf jedem Knoten v ∈ V
  • Nicht-negative Gewichte wₑ und orthogonale Matrizen Oₑ ∈ O(n) auf jeder Kante e ∈ E

Konsistenzbedingungen

Theorem 1 zeigt, dass Verbindungsgraph-Konsistenz äquivalent zu folgenden Bedingungen ist:

  1. Orthogonale Abbildungen entlang jeder Schleife des Graphen setzen sich zur Identitätsabbildung zusammen
  2. Eigenwerte des Verbindungs-Laplace-Operators sind n-fache Wiederholungen von Eigenwerten des kombinatorischen Laplace-Operators
  3. Es existieren Knoten-Orthogonalmatrizen, so dass Kantenmappings als Oᵢⱼ = Oᵢᵀ Oⱼ zerlegt werden können

Optimierungsproblem-Formulierung

Maximales Pseudowahrscheinlichkeitsproblem

Unter der Annahme, dass Signale einer Gaußverteilung N_nv(0,L†) folgen, ist das ursprüngliche Problem:

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

Umformulierung unter Konsistenzbeschränkungen

Unter Verwendung der Konsistenzbedingung L = Oᵀ(L⊗Iₙ)O wird das Problem transformiert zu:

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

Finales Optimierungsproblem

Durch Einführung von Kronecker-Struktur-Laplace-Operator und Lagrange-Relaxation:

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)

SCGL-Algorithmus

Blockkoordinaten-Abstieg-Optimierung

SCGL verwendet eine alternierende Blockminimierungsstrategie, die vier Variablenblöcke separat optimiert:

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

    Verwendet Minorization-Maximization (MM) Methode
  2. Orthogonale Basis-Update (O): Verwendet Riemannschen Gradientenabstieg auf der Produktmannigfaltigkeit SO(n)^v
  3. Eigenvektor-Update (U): Durch Berechnung von Haupteigenvektoren:
    U^{t+1} = [Eigenvecs{OᵀL_K(w)O}]_{:,(n+1):}
  4. Eigenwert-Update (Λ): Isotonisches Regressionsproblem mit geschlossener KKT-Lösung

Rechenkomplexität

Die Algorithmus-Komplexität beträgt O(V³n³), hauptsächlich durch Eigenzerlegung in orthogonalen Basis- und Eigenvektor-Optimierungsschritten bestimmt, was gegenüber strukturiertem Graphenlernens nur einen Skalierungsfaktor der Dimension n hinzufügt.

Experimentelle Einrichtung

Datensätze

  1. Erdős–Rényi (ER) Verbindungsgraphen:
    • Knotenzahl: |V| = 30
    • Kantenwahrscheinlichkeit: p_ER = 1.1 log V / V
    • Vektorraum-Dimension: n = 2
    • Kantengewichte: Unif(0.2, 3)
  2. Sphärische geometrische Verbindungsgraphen:
    • Sphäre in R³, diskretisiert mit Fibonacci-Gitter
    • 50 Punkte, k-NN-Graph mit k=4
    • Verbindungs-Laplace-Operator konstruiert mit Vector Diffusion Maps

Bewertungsmetriken

  1. Topologie-Wiederherstellung: F1-Score (spärliche Mustererkennung), Kantengewicht-MSE
  2. Geometrische Treue:
    • Empirische Gesamtvariation ÊL(Y) = M⁻¹ Tr(L̂YYᵀ)
    • Durchschnittliche spektrale Distanz σ(L,L̂) = 1/(nv) Σᵢ|Λᵢ(L)-Λᵢ(L̂)|
    • Integrierte Wärmediffusions-Distanz ξ(L,L̂)

Vergleichsmethoden

  1. KRON: Vereinfachte Version von SCGL mit lokalen Basen als Einheitsmatrizen
  2. SDP: Glättungs-Lernmethode basierend auf semidefiniter Programmierung
  3. SLGP: Frühere Arbeit der Autoren, Glättungs-Lernen mit geometrischen Priors

Datenverfügbarkeits-Szenarien

Nach Stichprobenquote r = M/(2|V|) werden drei Szenarien definiert:

  • Niedrig: r = 1.5
  • Mittel: r = 5
  • Hoch: r = 15

Experimentelle Ergebnisse

ER-Verbindungsgraph-Ergebnisse

  • Topologie-Wiederherstellung: Mit zunehmender Datenmenge zeigt SCGL signifikante Überlegenheit gegenüber allen Baselines beim F1-Score
  • Geometrische Treue: SCGL liegt beim empirischen Gesamtvariations-Wert dem theoretischen Erwartungswert am nächsten, was bessere Konsistenz anzeigt
  • Kantengewicht-Schätzung: SCGL schätzt Kantengewichte genau, wobei die meisten falsch-positiven Kanten vernachlässigbare Gewichte erhalten

Sphärische Verbindungsgraph-Ergebnisse

  • F1-Score: SCGL = 0,995 (höchst), SLGP = 0,927, SDP = 0,620, KRON = 0,425
  • Spektrale Distanz: SCGL = 0,90 (niedrigst), signifikant besser als andere Methoden
  • Wärmediffusions-Distanz: SCGL = 1,19 (niedrigst)
  • Kern-Dimension: SCGL behält korrekt dim(ker(L)) = 2 bei, garantiert Konsistenz

Wichtigste Erkenntnisse

  1. SCGL zeigt beste Leistung bei ausreichenden Daten, vergleichbar mit SLGP bei spärlichen Daten
  2. Optimierung von Knoten-Orthogonalbasen bringt signifikante Verbesserungen gegenüber festen Einheitsmatrizen
  3. SCGL erreicht gleichzeitig beste Topologie-Wiederherstellung und geometrische Treue
  4. Der Algorithmus bewahrt die Konsistenz des Verbindungsgraphen, was für geometrische Bedeutung entscheidend ist

Verwandte Arbeiten

Graphenlern-Feld

Traditionelles Graphenlernens verfolgt hauptsächlich zwei Ziele:

  1. Erzwingung gewünschter Topologie (Ausgleich zwischen Sparsität und Konnektivität)
  2. Förderung von Signalglätte (niedrige Variation zwischen verbundenen Knoten)

Bündel-Theorie-Methoden

  • Netzwerk-Bündel: Assoziieren strukturierte Daten auf Knoten und Kanten durch strukturbewahrende Abbildungen
  • Verbindungsgraphen: Spezialfall der Bündeltheorie, verwendet orthogonale Transformationen als strukturbewahrende Abbildungen
  • Anwendungen: Synchronisationsprobleme, Riemannsche Signalverarbeitung, neuronale Bündeldiffusion

Bestehende Verbindungsgraph-Lernmethoden

  1. Vector Diffusion Maps: Approximiert Verbindungs-Laplace-Operator durch geometrische Prinzipien
  2. SDP-Methoden: Erweitert glattes Graphenlernens auf Bündel-Laplace-Operator
  3. Kegelprogrammierungs-Methoden: Verwendet Procrustes-Ausrichtung und binäre Kantenstichproben

Schlussfolgerungen und Diskussion

Hauptschlussfolgerungen

  1. Schlägt ersten prinzipiellen Rahmen zum Erlernen von Verbindungsgraphen unter Konsistenzannahmen vor
  2. SCGL-Algorithmus kann gemeinsam Netzwerktopologie, Kantengewichte und geometrische Struktur wiederherstellen
  3. Experimente zeigen, dass SCGL bestehende Methoden sowohl bei Topologie-Wiederherstellung als auch geometrischer Treue übertrifft
  4. Algorithmus erreicht bessere Parametrisierung bei Beibehaltung rechnerischer Effizienz

Einschränkungen

  1. Konsistenzannahme: Methode setzt voraus, dass Verbindungsgraph konsistent ist, was in der Realität möglicherweise nicht immer zutrifft
  2. Gaußverteilungs-Annahme: Signalmodell-Annahme könnte zu vereinfacht sein
  3. Synthetische Daten: Experimente finden hauptsächlich auf synthetischen Daten statt, fehlt Validierung in der realen Welt
  4. Rausch-Robustheit: Leistung unter Rauschen und Modellverletzungen nicht ausreichend bewertet

Zukünftige Richtungen

  1. Erweiterung von SCGL zur Verarbeitung von Rauschen und Modellverletzungen
  2. Einbeziehung flexibler Topologie- und Geometrie-Priors
  3. Verarbeitung inkonsistenter Verbindungsgraphen
  4. Validierung des Rahmens auf realen Weltdaten

Tiefgehende Bewertung

Stärken

  1. Theoretischer Beitrag: Erweitert strukturiertes Graphenlernens auf Verbindungsgraphen mit solider theoretischer Grundlage
  2. Algorithmische Innovation: Kombiniert geschickt Riemannsche Optimierung und Blockkoordinaten-Abstieg zur Verarbeitung komplexer Mannigfaltigkeits-Beschränkungen
  3. Umfassende Experimente: Führt umfassende Bewertung auf verschiedenen Verbindungsgraph-Typen durch
  4. Rechnerische Effizienz: Erreicht effizientere Parametrisierung gegenüber bestehenden Methoden

Mängel

  1. Anwendbarkeitsbeschränkungen: Konsistenzannahme könnte Anwendungsbereich der Methode in der Praxis einschränken
  2. Experimentelle Einschränkungen: Fehlt Validierung auf realen Weltdatensätzen
  3. Rausch-Analyse: Analyse der Rausch-Robustheit nicht ausreichend tiefgehend
  4. Skalierungsbeschränkungen: Experimentelle Skalierung relativ klein (maximal 50 Knoten)

Auswirkungen

  1. Akademischer Wert: Bietet neue Werkzeuge für geometrie-bewusste Netzwerk-Topologie-Inferenz
  2. Anwendungspotenzial: Wichtige Anwendungsaussichten in Synchronisation, Riemannscher Signalverarbeitung und anderen Bereichen
  3. Methodologischer Beitrag: Bietet neues Optimierungs-Paradigma für Bündel-Lernen

Anwendungsszenarien

  1. Synchronisations-Netzwerke: Synchronisationsprobleme, die das Erlernen von Rotationsbeziehungen zwischen Knoten erfordern
  2. Riemannsche Signalverarbeitung: Signalverarbeitungsaufgaben auf Mannigfaltigkeiten
  3. Neuronale Netzwerke: Struktur-Lernen von Bündel-Neuronalen Netzwerken
  4. Robotik: Koordination und Lokalisierung von Multi-Roboter-Systemen

Literaturverzeichnis

Das Paper zitiert 29 verwandte Arbeiten, die wichtige Arbeiten aus mehreren Bereichen wie Graphsignalverarbeitung, Bündeltheorie und Riemannsche Optimierung abdecken und eine solide theoretische Grundlage für die Forschung bieten.

Gesamtbewertung: Dies ist ein hochqualitatives Paper mit wichtigen Beiträgen im Bereich des Verbindungsgraph-Lernens. Der von den Autoren vorgeschlagene SCGL-Algorithmus ist theoretisch innovativ und experimentelle Ergebnisse sind überzeugend. Trotz einiger Einschränkungen eröffnet das Paper neue Forschungsrichtungen für geometrie-bewusstes Graphenlernens und hat wichtigen akademischen Wert und Anwendungspotenzial.