Spectral clustering with sampling : a graph signal processing perspective

Abstract

Die Graphsignalverarbeitung ist eine Erweiterung der klassischen Signalverarbeitung, bei der die Signale auf der Knotenmenge eines Graphen definiert sind. Diese Art der Signalverarbeitung ist notwendig, wenn die Daten, wie in einem sozialen Netzwerk, als Graph gegeben sind, oder wenn die Menge der Daten sehr groß ist. Üblicherweise werden die Daten zuerst in einen Graphen übergeführt, der die Ähnlichkeit der Datenpunkte repräsentiert. Anschließend wird die üblicherweise spärlich besetzte Gewichtsmatrix verwendet, um eine Analyse der Daten effizient durchzuführen. Eine Anwendung der Graphsignalverarbeitung ist die Identifikation von Gruppen von ähnlichen Datenpunkten. Dieses sogenannte Clustering wird zum Beispiel in der Biologie, der Bildverarbeitung oder im maschinellen Lernen eingesetzt. In dieser Arbeit beschäftigen wir uns mit Clustering-Algorithmen, wobei der Fokus auf vorzeichenbehaftetem Spectral Clustering mit Abtastung liegt. Dieser Algorithmus modifiziert die Gewichtsmatrix eines gegebenen Graphen basierend auf der abgetasteten Cluster-Zugehörigkeit. Anschließend wird vorzeichenbehaftetes Spectral Clustering auf die modifizierte Gewichtsmatrix angewendet. Verfahren, bei denen die Cluster-Zugehörigkeit abgetastet wird, wird in der Nomenklatur des maschinellen Lernens als semi-supervised Clustering Algorithmus. Zu Beginn werden die beiden Algorithmen -neighborhood Graph und k-nearest neighborhood Graph zum Lernen von Graphen präsentiert. Danach werden k-means und Spectral Clustering, als Beispiele für Clustering Algorithmen ohne Abtastung diskutiert. Anschließend wird Spectral Clustering zu vorzeichenbehaftetem Spectral Clustering mit Abtastung erweitert. Zum Abschluss wird der erweiterte Algorithmus mittels Monte-Carlo Simulationen mit zwei anderen Clustering Algorithmen verglichen. Es zeigt sich, dass der neue Algorithmus bessere Ergebnisse liefert als die beiden Vergleichsalgorithmen.

Graph signal processing is an extension of classical signal processing to signals that are defined over the vertex set of graphs. This type of signal processing is necessary in applications where the data is best represented by a graph (like in social networks) and when the amount of data is big. Usually a graph is generated that represents the similarity of different data points and then the typically sparse weight matrix can be used for efficient analysis. One application of graph signal processing is clustering, where the aim is to identify groups of similar data items. This is used for data analysis in several fields ranging from biology over image processing to machine learning. In this work we consider various clustering algorithms. We focus on signed spectral clustering with sampling, which is an algorithm that modifies the weight matrix of a given graph based on some sampled cluster labels and then performs signed spectral clustering. In machine learning nomenclature methods that are supported by sampled cluster labels are referred to as a semi-supervised clustering. At first, algorithms for graph learning are presented. They are used as a pre-processing stage for graph-based clustering. Those algorithms are the -neighborhood graph and the k-nearest neighborhood graph. Next, k-means and spectral clustering, which are well known examples of unsupervised clus- tering algorithms, are discussed and then we introduce an original method that combines signed spectral clustering with sampling. In the last part signed spectral clustering with sampling is compared to clustering by harmonic functions and singular value projection in Monte-Carlo simulations. Our numerical results show that signed spectral clustering with sampling performs superior compared to existing algorithms.