Variational methods for semi-supervised node classification on signed graphs with multiple classes

Abstract

Bei der teilbeaufsichtigten Klassifizierung der Knoten eines Graphen handelt es sich um eine Problemstellung, bei der die zu Grunde liegende Klassenzugehörigkeit nur für eine (kleine) Menge von Knoten bekannt ist. Die restlichen Knoten sollen aufgrund der Struktur des Graphen jeweils einer Klasse zugeordnet werden. Diese Problemstellung wurde bereits in einer Vielzahl an Arbeiten untersucht; meist unter der Annahme, dass die Kanten des Graphen eine gewisse Form von Ähnlichkeitsstruktur vorgeben. In den letzten Jahren sind immer mehr Datensätze aufgetaucht, bei denen zusätzlich auch Information zur Unähnlichkeit von Datenpunkten vorhanden ist. In einem Graphen kann diese Unähnlichkeit mittels negativer Kanten erfasst werden, weswegen diese Graphen als vorzeichenbehaftet bezeichnet werden.Basierend auf der Theorie des strukturellen Gleichgewichts besitzen vorzeichenbehaftete Graphen die wünschenswerte Eigenschaft, dass die Kantenstruktur eine sehr natürliche Art bietet, um Gruppen von Knoten zu definieren. Dabei handelt es sich um eine Theorie welche ursprünglich in der Psychologie formuliert wurde und seither in vielen anderen Bereichen Anwendung gefunden hat.Bis zum jetzigen Zeitpunkt hat das Feld der teilüberwachten Klassifizierung von Knoten in vorzeichenbehafteten Graphen relativ wenig Beachtung gefunden. Wir stellen uns dieser Herausforderung, indem wir vier neue Methoden einführen und untersuchen:(i) Eine relaxierte Schätzung der Klassenzugehörigkeit mittels Maximierung der a-posteriori Wahrscheinlichkeit (MAP) für ein populäres statistisches Graph-Modell. Diese Methode dient als Bezugspunkt für andere Methoden und verwendet dafür die zugrundeliegenden Parameter des statistischen Modells.(ii) Eine projizierte orthogonale Iteration zur Lösung einer spektralen Relaxierung des Klassifizierungsproblems. Diese Methode soll schnell und ausreichend zuverlässig sein, sodass ihr Ergebnis als Initialwert für Methoden mit höherer Präzision verwendet werden kann.(iii) Eine konvexe l1 Relaxierung des Klassifizierungsproblems. Diese Methode ist vor allem von theoretischem Interesse da die Konvexität einfache Aussagen zur Optimalität und der Struktur der Ergebnisse erlaubt. Bei dieser Methode tritt jedoch manchmal das Problem auf, dass das Ergebnis der Relaxierung entartet ist.(iv) Eine nicht-konvexe Modifizierung der Nebenbedingungen für die konvexe l1 Relaxierung. Das Ziel dieser neuen Nebenbedingungen ist die Vermeidung von entarteten Lösungen und in unseren Experimenten werden wir zur Schau stellen, dass dieses Ziel tatsächlich erreicht wird.Wir konnten beobachten, dass unsere Methoden in ihren jeweiligen Kategorien den letzten Stand der Technik übertreffen. Die l1 Relaxierung in Kombination mit den nicht-konvexen Nebenbedingungen kommt dabei sogar nahe an die Leistung des MAP-Schätzers heran, ohne dafür Zugriff auf die zugrunde liegenden Modellparameter zu benötigen.Drei von vier unserer Methoden basieren auf nicht-konvexen Problemen. Das bedeutet, dass die Lösung nicht notwendigerweise dem globalen Optimum entspricht. Unsere Simulationen haben allerdings sehr gute Ergebnisse gezeigt, wodurch die Annahme naheliegt, dass die Ergebnisse zumindest nahe am globalen Optimum sind. Diese Nähe zum Optimum sollte in zukünftigen Arbeiten näher untersucht werden.

Semi-supervised node classification is the task of assigning the nodes of a graph to different classes based on the graph structure and the knowledge of a (small) portion of class associations for certain nodes. This problem has been extensively studied for unsigned graphs, where edges represent pairwise similarity between nodes. In recent years, more and more datasets also include information about the pairwise dissimilarity of nodes which can be represented by edges with negative weights in the graphs. This type of graph with both positive (i.e., similarity) edges and negative (i.e., dissimilarity) edges is termed a signed graph.Based on structural balance theory (a concept that originated in psychology and has found its way into many different fields of science), signed graphs have a very natural way of defining groups of nodes, which is a very desirable property in clustering and classification tasks. Up to now, the field of semi-supervised node classification on signed graphs has received relatively little attention. We here tackle this challenge by introducing and studying four new methods:(i) A new relaxation of the maximum a-posteriori (MAP) estimator for the class assignments in a popular statistical graph model. This algorithm serves as a benchmark for the performance of other methods by utilizing full knowledge of the model parameters.(ii) A projected orthogonal iteration that solves a spectral relaxation of the node classification problem. This method is intended to be fast and reasonably reliable such that it can be used as initialization for more accurate approaches.(iii) A convex l1 relaxation of the node classification problem. This method is interesting from a theoretical perspective as its convexity allows to derive detailed insight regard- ing the outcomes of the relaxation. However, it suffers from the known problem of sometimes obtaining degenerate solutions.(iv) A non-convex modification of the constraint set for the convex l1 relaxation. This new constraint set aims to avoid the degenerate solutions of the convex relaxation and we demonstrate its effectiveness at doing so in our experiments.All our methods are capable of handling multiple classes and we found that our methods outperform the state of the art within their respective category. The l1 relaxation together with the non-convex constraint set comes close to the performance of the relaxation of the MAP estimator even without knowledge of the model parameters.Three out of four of our methods involve non-convex problems, which means that optimality of the obtained solutions is not inherently given. The high performance of our algorithm, however, suggests that the obtained solutions are close to optimal, which motivates further research regarding this optimality.