Optimale Transportmethoden für strukturierte Daten mit Anwendung auf Graphen

Diese Arbeit behandelt das Problem der Berechnung von Distanzen zwischen strukturierten Objekten wie ungerichteten Graphen, die als Wahrscheinlichkeitsverteilungen in einem bestimmten metrischen Raum betrachtet werden. Wir betrachten eine neue Transportdistanz (d.h. eine, die den gesamten Transportkosten der Wahrscheinlichkeitsmassen minimiert), die die geometrische Natur des Raums der strukturierten Objekte aufdeckt. Im Gegensatz zu den Wasserstein- oder Gromov-Wasserstein-Metriken, die sich ausschließlich und jeweils auf Merkmale (indem sie eine Metrik im Merkmalsraum betrachten) oder Struktur (indem sie Struktur als metrischen Raum sehen) konzentrieren, nutzt unsere neue Distanz beide Informationen gemeinsam aus und wird daher Fused Gromov-Wasserstein (FGW) genannt. Nach einer Diskussion ihrer Eigenschaften und berechnungstechnischen Aspekte zeigen wir Ergebnisse für eine Aufgabenstellung zur Klassifikation von Graphen, bei der unsere Methode sowohl Graphkerne als auch tiefe graphkonvolutionelle Netze übertrifft. Durch weitere Ausnutzung der metrischen Eigenschaften des FGW werden interessante geometrische Objekte wie Fréchet-Mittelwerte oder Baryzentren von Graphen illustriert und im Clustering-Kontext diskutiert.