Clustering durch gewichtete Schnitte in gerichteten Graphen

In diesem Papier formulieren wir das spektrale Clustering in gerichteten Graphen als Optimierungsproblem, bei dem das Ziel ein gewichteter Schnitt im gerichteten Graphen ist. Dieses Ziel erweitert mehrere populäre Kriterien wie den normierten Schnitt und den durchschnittlichen Schnitt auf asymmetrische Affinitätsdaten. Wir zeigen, dass dieses Problem auf ein Rayleigh-Quotienten-Problem für eine symmetrische Matrix entspannt werden kann, die aus den ursprünglichen Affinitäten gewonnen wird, und daher ein großer Teil der Ergebnisse und Algorithmen, die für das spektrale Clustering symmetrischer Daten entwickelt wurden, unmittelbar auf asymmetrische Schnitte ausgeweitet werden kann.