Geiselbrechtinger, M. (2023). Semi-supervised learning with total variation on graphs [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2023.106925
E180 - Fakultät für Informatik E389 - Institute of Telecommunications
-
Date (published):
2023
-
Number of Pages:
49
-
Keywords:
Semi-supervised learning; total variation; signed graphs; convex optimization; graph clustering
en
Abstract:
Graphen bieten ein nützliches Modell für viele Probleme da sie es ermöglichen auf flexible und effiziente Art die Datenstruktur zu abstrahieren. Um Gebrauch von den wachsenden Mengen an Daten zu machen ist Klassifizierung eine essentielle Aufgabe die auf eine Partitionierung der Daten in Ähnlichkeitsgruppen abzielt. Allerdings beinhalten viele reale Netzwerke auch Verbindungen die Unähnlichkeiten beschreiben. In Sozialen Netzwerken etwa können Nutzer ihre Sympathie oder Antipathie durch befreunden respektive blockieren ausdrücken. Um diese gegensätzlichen Informationen effektiv zu nutzen ist es nötig spezifische Algorithmen zu konstruieren, die auf vorzeichenbehafteten Graphenarbeiten. Das Hauptaugenmerk der Forschung in der Vergangenheit lag auf dem Clustern von vorzeichenlosen Graphen. Eine vielversprechende Methode des maschinellen Lernens ist empirische Risikominimierung um die Clusterbeschriftung an die bekannten Beschriftungen anzupassen. Um diesen beaufsichtigten Lernprozess zu unterstützen wird ein zusätzliches Ziel hinzugefügt, welches den Algorithmus dazu bringen soll eine Clusterbeschriftung zu generieren, die glatt über die Struktur des Graphen variiert. Es existieren mehrere verschiedene Glattheitsmetriken die für solch eine unbeaufsichtigte Regulierung eingesetzt werden können. Manche davon wurden auch auf vorzeichenbehaftete Graphen erweitert.In dieser Arbeit zielen wir darauf ab, zwei teilüberwachte Klassifizierungsalgorithmen zu verbessern indem wir die totale Variation als Glattheitsmetrik auf vorzeichenbehafteten Graphen einsetzen. Die totale Variation wurde in mehreren kürzlich entwickelten teilbeaufsichtigten Methoden eingesetzt und hat sich als effektive Zielfunktion herausgestellt.Um die totale Variation wirkungsvoll mit klassischem maschinellen Lernen zu verbinden machen wir Gebrauch von konvexer Optimierung. Insbesondere leiten wir zwei teilbeaufsichtigte Clusterzielfunktionen für vorzeichenbehaftete Graphen her und entwickeln die iterativen Algorithmen um die Optimierungsprobleme effizient zu lösen. Wir präsentieren eine Verhaltensanalyse der Parameter und vergleichen die Clusterperformanzvon unseren Methoden mit dem Stand der Technik. Zusätzliche numerische Experimente auf synthetischen Datenmodellen sollen die Fähigkeit unserer Algorithmen, Information über Unähnlichkeit auszunutzen, beurteilen. Die Tests ergaben, dass Algorithmen,welche Gebrauch von der totalen Variation machen, eine überlegene Clusterperformanz aufweisen. Des Weiteren haben wir unsere Methoden auf Daten eines echten sozialen Netzwerks eingesetzt. Unser Algorithmen haben dabei, trotz der widrigen Clusterstruktur,zufriedenstellende Ergebnisse erzielt.
de
Graphs are a natural fit for modeling a multitude of problems as they are flexible and efficient abstractions of complex datasets. To make use of the growing amounts of data, clustering is an essential task that aims at partitioning the data into groups that reflect similarity. However, many real world networks also contain links that describe dissimilarity. In social networks for example users can associate themselves by befriending or blocking each other, which expresses sympathy or antipathy, respectively. To effectivelyutilize such opposing information in clustering tasks it is necessary to construct specific algorithms that operate on signed graphs. The main focus of research in the past was directed towards clustering on unsigned graphs. A promising machine learning method isto deploy empirical risk minimization to fit the cluster labeling to a set of known labels.To aid this supervised learning process an additional objective is added that shouldincentivise the algorithm to produce cluster labelings that are smooth with respect to thegraph’s similarity structure. There exist several different smoothness metrics that can be deployed in such an unsupervised regularization and some have also been extended to signed graphs.In this thesis we aim to improve two semi-supervised clustering algorithms by utilizing the total variation as a smoothness metric on signed graphs. The total variation has been deployed in several recent semi-supervised methods and has shown to be an effective objective for graph clustering. To combine the total variation with classic machine learning algorithms we make use of convex optimization procedures. In particular wederive two semi-supervised clustering objectives for signed graphs and develop iterativealgorithms to efficiently solve the stated optimization problems. We provide an analysisof the behavior of our algorithm’s parameters and compare their clustering performance to state of the art methods. Additional numerical experiments are conducted on synthetic data models to asses the ability of our novel algorithms to exploit dissimilarity information.The tests revealed that algorithms which use the total variation indeed produce superiorclustering performance in both the unsigned and signed case. Furthermore, we employedour methods on data derived from a real world social network. Our algorithms achieved satisfactory results, despite the problem’s unfavorable cluster structure.