Contributions to Robust Graph Clustering: Spectral Analysis and Algorithms

This dissertation details the design of fast, and parameter free, graph clustering methods to robustly determine set cluster assignments. It provides spectral analysis as well as algorithms that adapt the obtained theoretical results to the implementation of robust graph clustering techniques. Sparsity is of importance in graph clustering and a first contribution of the thesis is the definition of a sparse graph model consistent with the graph clustering objectives. This model is based on an advantageous property, arising from a block diagonal representation, of a matrix that promotes the density of connections within clusters and sparsity between them. Spectral analysis of the sparse graph model including the eigen-decomposition of the Laplacian matrix is conducted. The analysis of the Laplacian matrix is simplified by defining a vector that carries all the relevant information that is contained in the Laplacian matrix. The obtained spectral properties of sparse graphs are adapted to sparsity-aware clustering based on two methods that formulate the determination of the sparsity level as approximations to spectral properties of the sparse graph models. A second contribution of this thesis is to analyze the effects of outliers on graph clustering and to propose algorithms that address robustness and the level of sparsity jointly. The basis for this contribution is to specify fundamental outlier types that occur in the cases of extreme sparsity and the mathematical analysis of their effects on sparse graphs to develop graph clustering algorithms that are robust against the investigated outlier effects. Based on the obtained results, two different robust and sparsity-aware affinity matrix construction methods are proposed. Motivated by the outliers’ effects on eigenvectors, a robust Fiedler vector estimation and a robust spectral clustering methods are proposed. Finally, an outlier detection algorithm that is built upon the vertex degree is proposed and applied to gait analysis. The results of this thesis demonstrate the importance of jointly addressing robustness and the level of sparsity for graph clustering algorithms. Additionally, simplified Laplacian matrix analysis provides promising results to design graph construction methods that may be computed efficiently through the optimization in a vector space instead of the usually used matrix space.

In dieser Dissertation wird der Entwurf von schnellen und parameterfreien Graphen-Clustering-Methoden beschrieben, die robuste Clusterzuordnungen bestimmen können. Die Dissertation bietet eine Spektralanalyse sowie Algorithmen, die die erhaltenen theoretischen Ergebnisse an die Implementierung robuster Graphen-Clustering-Techniken anpassen.

Ein erster Beitrag dieser Arbeit ist die Definition eines spärlichen Graphenmodells, das mit den Zielen des Graphenclustering vereinbar ist. Dieses Modell basiert auf einer vorteilhaften Eigenschaft, die sich aus einer blockdiagonalen Darstellung einer Matrix ergibt, die die Dichte der Verbindungen innerhalb von Clustern und die Spärlichkeit der Verbindungen zwischen ihnen fördert. Es wird eine Spektralanalyse des spärlichen Graphenmodells einschließlich der Eigenwertzerlegung der Laplace-Matrix durchgeführt. Die Analyse der Laplace-Matrix wird durch die Definition eines Vektors vereinfacht, der alle relevanten Informationen enthält, die in der Laplace-Matrix enthalten sind. Die gewonnenen spektralen Eigenschaften spärlicher Graphen werden auf der Grundlage von zwei Methoden, die die Bestimmung des Spärlichkeitsniveaus als Annäherungen an die spektralen Eigenschaften der spärlichen Graphenmodelle formulieren, an das Clustering angepasst.

Ein zweiter Beitrag dieser Arbeit besteht darin, die Auswirkungen von Ausreißern auf das Graphenclustering zu analysieren und Algorithmen vorzuschlagen, die die Robustheit und den Grad der Spärlichkeit gemeinsam berücksichtigen. Die Grundlage für diesen Beitrag ist die Spezifizierung grundlegender Ausreißertypen, die in Fällen extremer Spärlichkeit auftreten, und die mathematische Analyse ihrer Auswirkungen auf dünn besetzte Graphen, um Algorithmen für das Graphenclustering zu entwickeln, die gegenüber den untersuchten Ausreißereffekten robust sind. Basierend auf den erhaltenen Ergebnissen werden zwei verschiedene robuste und spärlichkeitsbasierte Methoden zur Konstruktion von Affinitätsmatrizen vorgeschlagen. Motiviert durch die Auswirkungen von Ausreißern auf Eigenvektoren, werden eine robuste Fiedler-Vektor-Schätzung und eine robuste spektrale Clustermethode vorgeschlagen. Desweiteren wird ein Algorithmus zur Erkennung von Ausreißern, der auf dem Vertex-Grad aufbaut, vorgeschlagen und auf die Ganganalyse angewendet.

Die Ergebnisse dieser Arbeit zeigen, wie wichtig es ist, die Robustheit und den Grad der Spärlichkeit von Graphen Clustering-Algorithmen gemeinsam zu berücksichtigen. Darüber hinaus liefert die vereinfachte Laplace-Matrix Analyse vielversprechende Ergebnisse für die Entwicklung von Graphenkonstruktionsmethoden, die durch die Optimierung in einem Vektorraum, anstelle des normalerweise verwendeten Matrixraums, effizient berechnet werden können.