Online Graph Dictionary Learning

Dictionary Learning ist ein zentrales Werkzeug für die Repräsentationslernen, das Daten als lineare Kombination weniger grundlegender Elemente beschreibt. Diese Analyse ist jedoch im Kontext des Graphenlernens nicht direkt anwendbar, da Graphen gewöhnlich unterschiedliche metrische Räume bilden. Wir schließen diese Lücke, indem wir einen neuen online-geeigneten Ansatz für das Graph Dictionary Learning vorschlagen, der die Gromov-Wasserstein-Divergenz als Datenanpassungsterm nutzt. In unserer Arbeit werden Graphen durch die paarweisen Beziehungen ihrer Knoten kodiert und als konvexe Kombination von Graph-Atomen – also Dictionary-Elementen – modelliert. Diese werden mittels eines online-stochastischen Algorithmus geschätzt, der auf einem Datensatz von nicht registrierten Graphen mit potenziell unterschiedlicher Knotenzahl operiert. Unser Ansatz lässt sich natürlich auf gelabelte Graphen erweitern und wird durch eine neuartige obere Schranke ergänzt, die als schnelle Approximation der Gromov-Wasserstein-Distanz im Einbettungsraum verwendet werden kann. Wir liefern numerische Belege für das Interesse unseres Ansatzes bei der unsupervisierten Einbettung von Graph-Datensätzen sowie bei der online-orientierten Schätzung und Verfolgung von Graph-Unteräumen.